Сравнение мощностей

В этом параграфе более формально докажем те свойства равномощности и сравнения мощностей, которыми на интуитивном уровне пользовались уже ранее.

1⁰. Любое множество равномощно самому себе: " X |X| = |X| (рефлексивность).

Это очевидно, т.к. для любого множества X биективно тождественное отображение e_X : X ® X, заданное правилом " x Î X e_X(x) = x .

2⁰. Если X равномощно Y, то Y равномощно X:

" X, Y |X| = |Y| ® |Y| = |X| (симметричность).

Действительно, если f : X ® Y – биективное отображение, то для него существует обратное g = f ^–1 : Y ® X , которое тоже биективно.

3⁰. Если X равномощно Y, а Y равномощно Z, то X равномощно Z:

" X, Y, Z |X| = |Y| Ù |Y| = |Z| ® |X| = |Z | (транзитивность).

Это следует из того, что если f : X ® Y и g : Y ® Z – взаимно однозначны, то биективна и их композиция (суперпозиция) go f : X ® Z, заданная правилом " x Î X g o f(x) = g(f(x)).

Таким образом, доказано, что отношение равномощности множеств обладает свойствами рефлексивности, симметричности и транзитивности, т.е. оно аналогично отношению равенства. Это отношение не является отношением эквивалентности, т.к. невозможно указать множество, на котором оно задано (множество всех множеств множеством не является). С другой стороны, если задано множество U, то это отношение равномощности будет отношением эквивалентности на множестве B(U).

Напомним, что мощность множества X меньше или равна мощности множества Y, если существует инъективное отображение f : X ® Y. В этом случае пишут |X| £ |Y|.

Точно так же, как в свойствах 1⁰ , 2⁰ доказываются следующие свойства

4⁰. " X |X| £ |X| (рефлексивность).

5⁰. " X, Y, Z |X| £ |Y| Ù |Y| £ |Z| ® |X| £ |Z| (транзитивность).

Это показывает, что введённое отношение похоже на отношение порядка. Однако, для полного сходства необходимо доказать свойство антисимметричности.

6⁰. " X, Y |X| £ |Y| Ù |Y| £ |X| ® |X| = |Y| (антисимметричность).

Более развёрнуто: если существуют вложения f : X ® Y и g : Y ® X, то существует биекция h : X ® Y , т.е. |X| = |Y|.

Если одно из отображений сюръективно, то доказывать нечего, т.к. оно является и биективным. В противном случае проведём, следуя Маклейну, следующее остроумное рассуждение.

Пусть Æ ¹ X₁ = X \ Im(g) Í X, где Im(g) = {x Î X | $ y Î Y x = g(y)}, и если X_n Í X уже определено, то X_n+1 = g o f(X_n) Í X . Пусть X_∞ = X_n (см. рисунок ниже).

Тогда для любого элемента x Ï X_∞ верно x Ï X₁ = X \ Im(g), т.е. x Î Im(g). Таким образом, доказано, что X \ X_∞ Í Im(g).

Поскольку функция g : Y ® Im(g) – биективна, то существует обратная функция g ^–1: Im(g) ® Y, которая, как показано выше, определена на множестве X \ X_∞ Í Im(g). Теперь формулой h(x) = определим функцию h : X ® Y . Ясно, что h – отображение, т.е. функция h определена для любого x Î X.

Это отображение инъективно. Действительно, если для x₁ ¹ x₂ Î X верно h(x₁) = h(x₂), то (ввиду инъективности функций f и g ^–1 ) не могут одновременно выполняться включения x₁ , x₂ Î X_∞ или x₁ , x₂ Î X \ X_∞ . Поэтому можно считать x₁ Î X_∞ , а x₂ Ï X_∞ . Таким образом, f(x₁) = h(x₁) = h(x₂) = g ^–1(x₂), т.е. x₂ = g(f(x₁)) = gof(x₁). Поскольку x₁ Î X_k для некоторого k Î N, то получается x₂ = gof(x₁) Î gof(X_k) = X_k+1 Í X_∞ , т.е. x₂ Î X_∞ – противоречие.

Наконец, h сюръективно. В самом деле, если y Î Y, то возможны два случая: либо g(y) Ï X_∞ , либо g(y) Î X_∞ . В первом случае y = g ^–1(g(y)) = = h(g(y)) Î Im(h). Во втором случае g(y) Î X_k для некоторого k Î N. При этом k > 1, т.к. g(y) Î Im(g). Значит g(y) Î X_k = gof(X_k–1), и g(y) = gof(x_k–1) для некоторого x_k–1 Î X_k–1 , откуда (учитывая инъективность функции g) получим y = f(x_k–1) = h(x_k–1) Î Im(h).

Итак, h – биективное отображение множества X на множество Y, что и требовалось.

Аналог антисимметричности для сравнения мощностей доказан.

Теперь докажем свойство линейности полученного порядка мощностей.

7⁰. Для любых множеств X и Y верно одно и только одно из трёх: либо |X| < |Y| , либо |X| = |Y| , либо |X| > |Y|.

Ясно, что пустое множество Æ содержится в любом, так что имеем |Æ| = |Æ| и |Æ| < |M| для любого непустого множества M. Поэтому в дальнейшем можно считать, что X ¹ Æ ¹ Y.

Допустим, что не существует вложения множества X во множество Y.Построим вложение множества Y во множество X. Для этого введём на множестве всех вложений

I = { f : B ® A | A Í X, B Í Y, A = Im(f), f – вложение}

бинарное отношение, полагая f p g тогда и только тогда, когда функция g является продолжением функции f, т.е. f : B ® A , g : D ® C, B Í D, A Í C и " b Î B f(b) = g(b). Ясно, что множество I ¹ Æ, т.к. в нём содержится функции f : {y} ® {x} с одноэлементными областями определения и значений при любых x Î X, y Î Y.

Отношение p удовлетворяет, очевидно, следующим свойствам:

рефлексивности (" f : B ® A f p f),

транзитивности (" f : B ® A, g : D ® C, h : F ® E f p g Ù g p h ® f p h),

антисимметричности (" f : B ® A, g : D ® C f p g Ù g p f ® f = g).

Последнее следует из общепринятого определения равенства функций: из f p g следует B Í D, A Í C, а g p f означает, что D Í B, C Í A и " d Î D f(d) = g(d). Таким образом, B = D, A = C и " d Î D f(d) = g(d), т.е. f = g.

Итак, p – отношение порядка.

Кроме того, введённый порядок индуктивен, т.е. удовлетворяет следующему условию: любая возрастающая цепочка f₁ p f₂ p … p f_n p … имеет верхнюю грань – существует вложение f со свойством " n Î N f_n p f. Действительно, если дана цепочка указанного вида, то для f_n : B_n ® A_n имеют место включения B₁ Í B₂ Í … , A₁ Í A₂ Í … , а каждая функция f_n+1 является продолжением функции f_n , а значит, и всех предыдущих. Рассмотрим B = B_n , A = A_n , и построим вложение f : B ® A , продолжающее все вложения цепочки. Именно, для b Î B_n положим f(b) = f_n(b). Значение f(b) не зависит от номера n: если b Î B_m , то f_n(b) = f_m(b), т.к. при n ³ m функция f_n продолжает f_m , а при m ³ n – f_m продолжает f_n . Функция f будет вложением, т.к. каждая функция f_n переводит разные элементы в разные. Очевидно, что f продолжает все функции цепочки, так что f – верхняя граньрассматриваемой цепи: f₁ p f₂ p … p f_n p … p f.

Итак, I – упорядоченное множество со свойством индуктивности. К нему можно применить лемму Цорна:

Лемма Цорна: Любое упорядоченное множество со свойством индуктивности имеет максимальный элемент.

Эта лемма, как отмечалось выше, эквивалентна аксиоме выбора. Таким образом, у множества Iесть максимальный элемент, т.е. такой элемент i Î I, что " f Î I f p i. Докажем, что i : Y ® U – вложение. Ясно, что i : V ® U – вложение, т.к. i Î I. Предположим, что V ¹ Y. Тогда U ¹ X, иначе i : V ® X – биективно и существует обратное вложение i ^–1: X ® V Í Y вопреки первоначальному предположению. Итак, V ¹ Y и U ¹ X, значит можно выбрать элементы y Î Y \ V, x Î X \ U и продолжить вложение i до вложения j Î I, где j : V È {y} ® U È {x}, " v Î V j(v) = i(v), j(y) = x. Это противоречит максимальности вложения i, т.к. должно быть j p i, а это не так: V È {y} V.

Итак, найдено вложение i : Y ® U Í X, что и требовалось.

То, что никакие два условия |X| < |Y|, |X| > |Y|, |X| = |Y| не могут выполняться одновременно ясно из определений отношения < для мощностей.

Полученная теория сравнения мощностей имеет смысл, если бесконечных мощностей бесконечно много. Это действительно так, что следует из теоремы Кантора-Бернштейна:

8⁰. Теорема Кантора-Бернштейна: Любое множество не равномощноно множеству всех своих подмножеств. Более точно: если X – множество и B(X) – булеан множества X (множество всех подмножеств множества X), то существует инъекция f : X ® B(X), но не существует биекции g : B(X) ® X.

Функцию f : X ® B(X) построить легко: можно задать f(x) = {x} Î B(X).

Предположим, вопреки доказываемому, что есть биекция g : B(X) ® X. Используем диагональный метод Кантора, чтобы получить противоречие. Рассмотрим множество M Í X, где M = {x Î X | x Ï g^–1(x)} . Зададимся вопросом g(M) Î M ?

Если x = g(M) Î M, то (по определению множества M) имеем x Ï g^–1(x) = = g^–1(g(M)) = M, т.е. x Ï M – противоречие.

Если же x = g(M) Ï M, то (по определению множества M) x Î g^–1(x) = = g^–1(g(M)) = M, т.е. x Î M – противоречие. Таким образом, g не может быть биекцией.

Теорема Кантора-Бернштейна доказана.

На самом деле, аналогичным образом можно доказать значительно больше. Пусть для множеств X, Y символ X^Y обозначает множество всех отображений из Y в X : X^Y = {f: Y ® X | D(f) = Y} . В частности, если X = {0, 1}, то множество {0, 1}^Y обычно обозначают 2^Y и отождествляют с булеаном B(Y). Более точно, существует биекция l: {0, 1}^Y ® B(Y), которую можно задать, например, так: l(f) = {y Î Y | f(y) = 1}. Это действительно биекция:

инъ: если l(f) = l(g), то отображения f: Y ® {0, 1} и g: Y ® {0, 1} принимают значение 1 на одном и том же множестве, вне которого они одновременно принимают значение 0. Значит, f = g.

сюръ: для любого множества Z Î B(Y), т.е. для Z Í Y построим отображение f: Y ® {0, 1} по правилу f(y) = . Очевидно, что l(f) = Z.

Итак, можно отождествить функцию f Î 2^Y с множеством l(f) Î B(Y), т.е. отождествить 2^Y c B(Y). Кстати, для конечного множества Y из n элементов получаем равенство |2^Y| = 2ⁿ = |B(Y)| , которое и оправдывает обозначение 2^Y.

9⁰. Если X и Y – множества, причём |X| > 1, то |X^Y| > |Y| , т.е. существует вложение l: Y ® X^Y, но не существует биективного отображения m : Y ® X^Y.

Доказательство аналогично доказательству свойства 9⁰. Зафиксируем два различных элемента x₁ и x₂ множества X.

Функцию l : Y ® X^Y построить легко: например, можно задать l(y) = c_y , где c_y : Y ® X – задаётся правилом c_y(u) = . Отображение l инъективно: если y₁ ¹ y₂ , то , так что .

Предположим, вопреки доказываемому, что нашлась биекция m : Y ® X^Y. Чтобы получить противоречие, используем диагональный метод Кантора: построим отображение f: Y ® X, не содержащееся в образе отображения m .

Положим f(y) = . Тогда f(y) ¹ m(y)(y), и значит, f отлична от любой функции m(y), т.е. f Ï Im(µ) = X^Y – противоречие.