Отношение эквивалентности и фактор-множество

Пусть 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 будет отношением эквивалентности тогда и только тогда, когда имеют место включения:

Id_X Í R (рефлексивность),

R^-1 Í R (симметричность),

R ° R Í R (транзитивность).

В действительности эти три условия равносильны следующим:

Id_X Í 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) Id_X Í 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) – свойство его элементов, верное для наименьшего элемента x₀ Î X и такое, что из истинности F(y) для всех y < z следует истинность F(z), то F(x) верно для всех x Î X.

Здесь y < z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x₁, и выполнение F(y) для всех y < x₁ приводит к выполнению F(x₁), противоречащему предположению.

Понятие мощности

Пусть f: X à Y и g: Y à Z – отображения множеств. Поскольку f и g – отношения, то определена их композиция g ° f(x) = g(f(x)). Если h: Z à T – отображение множеств, то h ° (g ° f) = (h ° g) ° f. Отношения Id_X и Id_Y – функции, стало быть, определены композиции Id_Y ° f = f ° Id_x = f. При X = Y определим f² = f ° f, f³ = f² ° f, …, fⁿ⁺¹ = fⁿ ° f.

Отображение f: X àY называется инъекцей, если для любых элементов x₁ ¹ x₂ множества X справедливо f(x₁) ¹ f(x₂). Отображение 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)²¢¢(X \ A) = Æ, …,

(gf)ⁿ¢¢(X \ A) Ç (gf)ⁿ⁺¹¢¢(X \ A) = Æ, …

Рассмотрим отображение j: X à A, заданное как j(x) = gf(x), при

x Î (X \ A) È (gf)¢¢(X \ A) È (gf)²¢¢(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|, что противоречит теореме Кантора. Следовательно, собрание всех множеств не является множеством.