Пусть R – бинарное отношение на множестве X. Отношение R называется рефлексивным, если (x, x) Î R для всех x Î X; симметричным – если из (x, y) Î R следует (y, x) Î R; транзитивным числу 23 соответствует вариант 24 если (x, y) Î R и (y, z) Î R влекут (x, z) Î R.
Пример 1
Будем говорить, что x Î X имеет общее с элементом y Î X, если множество
x Ç y не пусто. Отношение иметь общее будет рефлексивным и симметричным, но не транзитивным.
Отношением эквивалентности на X называется рефлексивное, транзитивное и симметричное отношение. Легко видеть, что R Í X ´ X будет отношением эквивалентности тогда и только тогда, когда имеют место включения:
IdX Í R (рефлексивность),
R-1 Í R (симметричность),
R ° R Í R (транзитивность).
В действительности эти три условия равносильны следующим:
IdX Í R, R-1 = R, R ° R = R.
Разбиением множества X называется множество А попарно непересекающихся подмножеств a Í X таких, что UA = X. С каждым разбиением А можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого a Î A.
Каждому отношению эквивалентности ~ на X соответствует разбиение А, элементами которого являются подмножества, каждое из которых состоит из находящихся в отношении ~. Эти подмножества называются классами эквивалентности. Это разбиение А называется фактор-множеством множества X по отношению ~ и обозначается: X/~.
Пример 2
Определим отношение ~ на множестве w натуральных чисел, полагая x ~ y, если остатки от деления x и y на 3 равны между собой. Тогда w/~ состоит из трёх классов эквивалентности, соответствующих остаткам 0, 1 и 2.
Отношение порядка
Бинарное отношение R на множестве X называется антисимметричным, если из x R y и y R x следует: x = y. Бинарное отношение R на множестве X называется отношением порядка, если оно рефлексивно, антисимметрично и транзитивно. Легко видеть, что это равносильно выполнению следующих условий:
1) IdX Í R (рефлексивность),
2) R Ç R-1 (антисимметричность),
3) R ° R Í R (транзитивность).
Упорядоченная пара (X, R), состоящая из множества X и отношения порядка R на X, называется частично упорядоченным множеством.
Пример 1
Пусть X = {0, 1, 2, 3}, R = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (3, 3)}.
Поскольку R удовлетворяет условиям 1 – 3, то (X, R) – частично упорядоченное множество. Для элементов x = 2, y = 3, неверно ни x R y, ни y R x. Такие элементы называют несравнимыми. Обычно отношение порядка обозначают £. В приведенном примере 0 £ 1 и 2 £ 2, но неверно, что 2 £ 3.
Пример 2
Пусть < – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.
Элементы x, y Î X частично упорядоченного множества (X, £) называются сравнимыми, если x £ y либо y £ x.
Частично упорядоченное множество (X, £) называется линейно упорядоченным или цепью, если любые два его элемента сравнимы. Множество из примера 2 будет линейно упорядоченным, а из примера 1 – нет.
Подмножество A Í X частично упорядоченного множества (X, £) называется ограниченным сверху, если существует такой элемент x Î X, что a £ x для всех a Î A. Элемент x Î X называется наибольшим в X, если y £ x для всех y Î X. Элемент x Î X называется максимальным, если нет отличных от x элементов y Î X, для которых x £ y. В примере 1 элементы 2 и 3 будут максимальными, но не наибольшими. Аналогично определяются ограничение снизу подмножества, наименьший и минимальный элементы. В примере 1 элемент 0 будет и наименьшим и минимальным. В примере 2 этими свойствами также обладает 0, но в (w, £) нет ни наибольшего, ни максимального элемента.
Пусть (X, £) – частично упорядоченное множество, A Í X – подмножество. Отношение на А, состоящее из пар (a, b) элементов a, b Î A, для которых a £ b, будет отношением порядка на А. Это отношение обозначают тем же символом: £. Таким образом, (A, £) – частично упорядоченное множество. Если оно является линейно упорядоченным, то будем говорить, что А – цепь в (X, £).
Принцип максимальности
Некоторые математические утверждения невозможно доказать без аксиомы выбора. Про эти утверждения говорят, что они зависят от аксиомы выбора или справедливы в теории ZFC, на практике вместо аксиомы выбора для доказательства используют обычно либо аксиому Цермело, либо лемму Куратовского-Цорна, либо любое другое утверждение, равносильное аксиоме выбора.
Лемма Куратовского-Цорна. Если каждая цепь в частично упорядоченном множестве (X, £) ограничена сверху, то в X есть по крайней мере один максимальный элемент.
Эта лемма равносильна аксиоме выбора, и поэтому её можно принять в качестве аксиомы.
Теорема. Для любого частично упорядоченного множества (X, £) существует отношение, содержащее отношение £ и превращающее X в линейно упорядоченное множество.
Доказательство. Множество всех отношений порядка, содержащих отношение £, упорядочено отношением включения Í. Поскольку объединение цепи отношений порядка будет отношением порядка, то по лемме Куратовского-Цорна существует максимальное отношение R, такое, что x £ y влечет x R y. Докажем, что R – отношение, линейно упорядочивающее X. Предположим противное: пусть существуют a, b Î X такие, что ни (a, b), ни (b, a) не принадлежат R. Рассмотрим отношение:
R¢ = R È {(x, y): x R a и b R y}.
Оно получается добавлением пары (a, b) к R и пар (x, y), которые должны быть добавлены к R¢ из условия, что R¢ – отношение порядка. Легко видеть, что R¢ рефлексивно, антисимметрично и транзитивно. Получаем R Ì R¢, противоречащее максимальности R, следовательно, R – искомое отношение линейного порядка.
Линейно упорядоченное множество X называется вполне упорядоченным, если всякое его непустое подмножество A Í X содержит наименьший элемент a Î A. Лемма Куратовского-Цорна и аксиома выбора эквивалентны также следующему утверждению:
Аксиома Цермело. Для каждого множества существует отношение порядка, превращающее его во вполне упорядоченное множество.
Например, множество w натуральных чисел является вполне упорядоченным. Принцип индуктивности обобщается следующим образом:
Трансфинитная индукция. Если (X, £) – вполне упорядоченное множество и F(x) – свойство его элементов, верное для наименьшего элемента x0 Î X и такое, что из истинности F(y) для всех y < z следует истинность F(z), то F(x) верно для всех x Î X.
Здесь y < z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x1, и выполнение F(y) для всех y < x1 приводит к выполнению F(x1), противоречащему предположению.
Понятие мощности
Пусть f: X à Y и g: Y à Z – отображения множеств. Поскольку f и g – отношения, то определена их композиция g ° f(x) = g(f(x)). Если h: Z à T – отображение множеств, то h ° (g ° f) = (h ° g) ° f. Отношения IdX и IdY – функции, стало быть, определены композиции IdY ° f = f ° Idx = f. При X = Y определим f2 = f ° f, f3 = f2 ° f, …, fn+1 = fn ° f.
Отображение f: X àY называется инъекцей, если для любых элементов x1 ¹ x2 множества X справедливо f(x1) ¹ f(x2). Отображение f называется сюръекцией, если для каждого y ÎY существует такой x Î X, что f(x) = y. Если f является и сюръекцией, и инъекцией, то f называется биекцией. Легко видеть, что f – биекция тогда и только тогда, когда обратное отношение f-1 Í Y ´ X является функцией.
Будем говорить, что справедливо равенство |X| = |Y|, если существует биекция между X и Y. Положим |X| £ |Y|, если существует инъекция f: X à Y.
Теорема Кантора-Шредера-Бернштейна. Если |X| £ |Y| и |Y| £ |X|, то |X| = |Y|.
Доказательство. По условию, существуют инъекции f: X à Y и g: Y à X. Пусть A = g¢¢Y = Img – образ множества Y относительно отображения g. Тогда
(X \ A) Ç (gf)¢¢(X \ A) = Æ,
(gf)¢¢(X \ A) Ç (gf)2¢¢(X \ A) = Æ, …,
(gf)n¢¢(X \ A) Ç (gf)n+1¢¢(X \ A) = Æ, …
Рассмотрим отображение j: X à A, заданное как j(x) = gf(x), при
x Î (X \ A) È (gf)¢¢(X \ A) È (gf)2¢¢(X \ A) È …, и j(x) = x в остальных случаях. Легко видеть, что j – биекция. Искомая биекция между X и Y будет равна g-1 ° j.
Антиномия Кантора
Положим |X| < |Y|, если |X| £ |Y| и не существует биекции между X и Y.
Теорема Кантора. Для любого множества X справедливо |X| < |P(X)|, где P(X) – множество всех подмножеств множества X.
Доказательство. Ясно, что |X| £ |P(X)|. Предположим, что существует биекция f: X à P(X). Рассмотрим подмножество:
A = {x Î X: x Ï f(x)}.
Если существует y Î X, для которого f(y) = A, то из y Î A будет следовать: y Ï f(y) = A; а из y Ï A = f(y) следует: y Î A. Отсюда нет элементов y Î X, таких, что f(y) = A, и, стало быть, f – не биекция. Теорема доказана. Эта теорема показывает, что необходимость уточнения понятия множества была известна Георгу Кантору:
Антиномия Кантора. Предположим, что все множества составляют некоторое множество U. Тогда каждое подмножество A Í U принадлежит U. Стало быть, P(U) Í U и имеет место |P(U)| £ |U|, что противоречит теореме Кантора. Следовательно, собрание всех множеств не является множеством.
