Введение в теорию множеств

Лемма Цорна и свойства операций

Разбить на страницы
Показывать лекцию целиком

Лемма Цорна и ее применения

В современных учебниках редко встречается трансфинитная индукция как таковая: она заменяется ссылкой на так называемую лемму Цорна. Сейчас мы покажем, как это делается, на примере теоремы о существовании базиса в линейном пространстве.

Теорема 30 (лемма Цорна) Пусть $$Z$$ - частично упорядоченное множество, в котором всякая цепь имеет верхнюю границу. Тогда в этом множестве есть максимальный элемент, и, более того, для любого элемента $$a\hm\in Z$$ существует элемент $$b\hm\ge a$$, являющийся максимальным в $$Z$$. ( Цепь - это подмножество, любые два элемента которого сравнимы. Верхняя граница цепи - элемент, больший или равный любого элемента цепи.)

Доказательство. Прежде всего отметим, что $$Z$$ лишь частично упорядочено, поэтому надо различать максимальные и наибольшие элементы. По этой же причине мы вынуждены употреблять грамматически некорректную конструкцию " больший или равный любого (любому?)", поскольку сказать " не меньше любого" (стандартный выход из положения) означало бы изменить смысл.

Доказательство повторяет рассуждения при построении базиса, но в более общей ситуации (теперь у нас не линейно независимые семейства, а произвольные элементы $$Z$$ ).

Пусть дан произвольный элемент $$a$$. Предположим, что не существует максимального элемента, большего или равного $$a$$. Это значит, что для любого $$b\hm\ge a$$ найдется $$c\hm>b$$. Тогда $$c\hm>a$$ и потому найдется $$d\hm>c$$ и т.д Продолжая этот процесс достаточно долго, мы исчерпаем все элементы $$Z$$ и придем к противоречию.

Проведем рассуждение аккуратно (пока что мы даже не использовали условие леммы, касающееся цепей). Возьмем вполне упорядоченное множество $$I$$ достаточно большой мощности (большей, чем мощность $$Z$$ ). Построим строго возрастающую функцию $$f\colon I\hm\to Z$$ по трансфинитной рекурсии. Ее значение на минимальном элементе $$I$$ будет равно $$a$$. Предположим, что мы уже знаем все ее значения на всех элементах, меньших некоторого $$i$$. В силу монотонности эти значения попарно сравнимы. Поэтому существует их верхняя граница $$s$$, которая, в частности, больше или равна $$a$$. Возьмем какой-то элемент $$t\hm>s$$ и положим $$f(i)\hm=t$$ ; по построению монотонность сохранится. Тем самым $$I$$ равномощно части $$Z$$, что противоречит его выбору.

В этом рассуждении, формально говоря, есть пробел: мы одновременно определяем функцию по трансфинитной рекурсии и доказываем ее монотонность с помощью трансфинитной индукции. Наше рекурсивное определение имеет смысл, лишь если уже построенная часть функции монотонна. Формально говоря, надо воспользоваться теоремой 19, считая, что следующее значение не определено, если уже построенный участок не монотонен, и получить функцию, определенную на всем $$I$$ или на начальном отрезке. Если она определена на некотором начальном отрезке, то она монотонна на нем по построению, поэтому следующее значение тоже определено - противоречие.

Как и при построении базиса Гамеля (задача 115), можно обойтись без множества большей мощности. Вполне упорядочим множество $$Z$$ с помощью теоремы Цермело. Этот порядок никак не связан с исходным порядком на $$Z$$ ; мы будем обозначать его символом $$\prec$$. Построим с помощью трансфинитной рекурсии функцию $$f\colon Z \hm\to Z$$ с такими свойствами: (1) $$f(z) \hm\ge a$$ для любого $$z\hm\in Z$$ ; (2) $$f$$ монотонна в следующем смысле: если $$x\hm\prec y$$, то $$f(x)\hm\le f(y)$$ ; (3) $$f(z)$$ не может быть строго меньше $$z$$ (в смысле исходного порядка $$\le$$ ) ни при каком $$z$$.

Делается это так. Значение $$f(z_0)$$ для $$\prec$$ - наименьшего элемента $$z_0$$ мы положим равным либо $$a$$, либо $$z_0$$ (последнее - если $$z_0 \hm> a$$ ). Значение $$f(z)$$ для остальных $$z$$ есть либо верхняя граница значений $$f(z')$$ при $$z'\hm\prec z$$ (по предположению индукции множество таких значений линейно упорядочено и потому имеет некоторую верхнюю границу $$\alpha$$ ), либо само $$z$$ (последнее - если $$z\hm>\alpha$$ ).

В силу монотонности множество значений функции $$f$$ линейно упорядочено и имеет верхнюю границу. Эта граница (обозначим ее $$\beta$$ ) больше или равна $$a$$ (которое есть $$f(z_0)$$ ) и является искомым максимальным элементом: если $$\beta \hm< z$$ для некоторого $$z$$, то $$f(z)\hm\le\beta\hm<z$$, что противоречит свойству (3).

Теперь повторим доказательство теоремы о базисе, используя лемму Цорна. Пусть $$V$$ - произвольное векторное пространство. Рассмотрим частично упорядоченное множество $$Z$$, состоящее из линейно независимых подмножеств пространства $$V$$. Порядок на $$Z$$ задается отношением "быть подмножеством".

Проверим, что условия леммы выполнены. Пусть имеется некоторая цепь, то есть семейство линейно независимых множеств, причем любые два множества этого семейства сравнимы. Объединим все эти множества и покажем, что полученное множество будет линейно независимым (тем самым оно будет верхней границей элементов цепи). В самом деле, нетривиальная линейная комбинация включает в себя какое-то конечное число векторов, каждый из своего множества. Этих множеств конечное число, и потому среди них есть наибольшее по включению (в конечном линейно упорядоченном множестве есть наибольший элемент). Это наибольшее множество содержит все векторы нетривиальной линейной комбинации, и линейно независимо по предположению, так что наша нетривиальная линейная комбинация отлична от нуля.

Таким образом, можно применить лемму Цорна и заключить, что любое линейно независимое множество векторов содержится в максимальном линейно независимом множестве векторов. К нему уже нельзя добавить ни одного вектора, не создав линейной зависимости, и оно является искомым базисом.

Аналогичным образом можно доказать существование ортогонального базиса в гильбертовом пространстве (там определение базиса другое: разрешаются бесконечные линейные комбинации, понимаемые как суммы рядов) или существование базиса трансцендентности (максимальная алгебраически независимая система элементов в расширении полей).

Мы приведем другой пример применения леммы Цорна, где фигурируют уже известные нам понятия.

Теорема 31. Всякий частичный порядок может быть продолжен до линейного.

Доказательство. Пусть $$(X,\le)$$ - частично упорядоченное множество. Теорема утверждает, что существует отношение порядка $$\le'$$ на $$X$$, продолжающее исходное (это значит, что $$x\hm\le y\Rightarrow x \le' y$$ ) и являющееся отношением линейного порядка. (Кстати, отметим, что слово "линейного" в формулировке теоремы нельзя заменить на слово "полного" - например, если исходный порядок линейный, но не полный.)

Готовясь к применению леммы Цорна, рассмотрим частично упорядоченное множество $$Z$$, элементами которого будут частичные порядки на $$X$$ (то есть подмножества множества $$X\hm\times X$$, обладающие свойствами рефлексивности, транзитивности и антисимметричности), упорядоченные по включению: $$\le_1$$ считается меньшим или равным $$\le_2$$, если $$\le_2$$ продолжает $$\le_1$$ (из $$x\le_1 y$$ следует $$x\le_2 y$$ ).

Легко проверить, что условие леммы Цорна выполнено: если у нас есть семейство частичных порядков, линейно упорядоченное по включению, то объединение этих порядков является частичным порядком, и этот порядок будет верхней границей семейства. (Проверим, например, что объединение обладает свойством транзитивности. Пусть $$x\le_1 y$$ в одном из порядков семейства $$(\le_1)$$, а $$y\le_2 z$$ в другом; один из порядков (например, $$\le_1$$ ) продолжает другой, тогда $$x\le_1 y \le_1 z$$ и потому $$x\hm\le z$$ в объединении. Рефлексивность и антисимметричность проверяются столь же просто.)

Следовательно, по лемме Цорна на множестве $$X$$ существует максимальный частичный порядок, продолжающий исходный. Обозначим его как $$\le$$ (путаницы с исходным порядком не возникнет, так как исходный нам больше не нужен). Нам надо показать, что он будет линейным. Пусть $$x,y\hm\in X$$ - два несравнимых элемента. Расширим порядок до нового порядка $$\le'$$, при котором $$x\le' y$$. Этот новый порядок определяется так: $$a\le' b$$, если (1) $$a\le b$$ или (2) $$a\le x$$ и $$y\hm\le b$$. Несложно проверить, что $$\le'$$ будет частичным порядком. Рефлексивность очевидна. Транзитивность: если $$a\le'b$$ и $$b\le' c$$, то есть четыре возможности. Если в обоих случаях имеет место случай (1), то $$a\hm\le b \hm\le c$$ и все очевидно. Если $$a\le' b$$ в силу (1), а $$b\le c$$ в силу (2), то $$a\hm\le b\hm\le x$$ и $$y\hm\le c$$, так что $$a \le' c$$ в силу (2). Аналогично рассматривается и симметричный случай. Наконец, двукратная ссылка на (2) невозможна, так как тогда $$(a\hm\le x)$$, $$(y\hm\le b)$$, $$(b\hm\le x)$$ и $$(y\hm\le c)$$, и получается, что $$y\hm\le b\hm\le x$$, а мы предполагали, что $$x$$ и $$y$$ не сравнимы. Антисимметричность доказывается аналогично. Таким образом, отношение $$\le'$$ будет частичным порядком, строго содержащим $$\le$$, что противоречит максимальности.

120. Покажите, что любое бинарное отношение без циклов (цикл образуется, если $$xRx$$, или $$xRyRx$$, или $$xRyRzRx$$ и т.д) может быть продолжено до линейного порядка. (Для конечных множеств поиск такого продолжения обычно называют " топологической сортировкой ".)

121. Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит соединяющий их отрезок. Покажите, что любые два непересекающихся выпуклых множества можно разделить прямой (каждое множество лежит по одну сторону от прямой, возможно, пересекаясь с ней). (Указание. Используя лемму Цорна, можно расширить исходные непересекающиеся множества $$A$$ и $$B$$ до взаимно дополнительных выпуклых множеств $$A'$$ и $$B'$$. Затем можно убедиться, что граница между $$A'$$ и $$B'$$ представляет собой прямую.)

Свойства операций над мощностями

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

Теорема 32. Если $$A$$ бесконечно, то множество $$A\hm\times\bbN$$ равномощно $$A$$.

Доказательство. Вполне упорядочим множество $$A$$. Мы уже знаем , что всякий элемент множества $$A$$ однозначно представляется в виде $$z\hm+n$$, где $$z$$ - предельный элемент (не имеющий непосредственно предыдущего), а $$n$$ - натуральное число. Это означает, что $$A$$ равномощно $$B\hm\times\bbN$$, где $$B$$ - множество предельных элементов. (Тут есть небольшая трудность - последняя группа элементов конечна, если в множестве есть наибольший элемент. Но мы уже знаем, что добавление конечного или счетного множества не меняет мощности, так что этим можно пренебречь.)

Теперь утверждение теоремы очевидно: $$A\hm\times\bbN$$ равномощно $$(B\hm\times\bbN)\hm\times\bbN$$, то есть $$B\hm\times(\bbN\hm\times\bbN)$$ и тем самым $$B\hm\times\bbN$$ (произведение счетных множеств счетно), то есть $$A$$.

По теореме Кантора - Бернштейна отсюда следует, что промежуточные мощности (в частности, $$|A|\hm+|A|$$, а также любое произведение $$A$$ и конечного множества) совпадают с $$|A|$$. Еще одно следствие полезно выделить:

Теорема 33. Сумма двух бесконечных мощностей равна их максимуму.

Доказательство. Прежде всего напомним, что любые две мощности сравнимы (теорема 25). Пусть, скажем, $$|A|\hm\le |B|$$. Тогда $$|B|\hm\le |A|+|B| \hm\le |B|+|B| \hm\le |B|\hm\times\aleph_0 \hm= |B|$$ (последнее неравенство - утверждение предыдущей теоремы). Остается воспользоваться теоремой Кантора- Бернштейна и заключить, что $$|B|\hm=|A\hm+B|$$.

Теперь можно доказать более сильное утверждение.

Теорема 34. Если $$A$$ бесконечно, то $$A\hm\times A$$ равномощно $$A$$.

Доказательство. Заметим, что для счетного множества (как, впрочем, и для континуума - но это сейчас не важно) мы это уже знаем. Поэтому в $$A$$ есть подмножество, равномощное своему квадрату.

Рассмотрим семейство всех таких подмножеств вместе с соответствующими биекциями. Элементами этого семейства будут пары $$\langle B, f\rangle$$, где $$B$$ - подмножество $$A$$, а $$f\colon B\hm\to B\hm\times B$$ - взаимно однозначное соответствие. Введем на этом семействе частичный порядок: $$\langle B_1, f_1\rangle\hm\le \langle B_2,f_2\rangle$$, если $$B_1 \hm\subset B_2$$ и ограничение отображения $$f_2$$ на $$B_1$$ совпадает с $$f_1$$ (рис. рис.11.1).

(рис 11.1)

Отображение $$f_1$$ - взаимно однозначное соответствие между малым квадратом и его стороной; $$f_2$$ добавляет к нему взаимно однозначное соответствие между $$B_2\hm\setminus B_1$$ и " уголком" $$(B_2\hm\times B_2)\setminus(B_1\hm\times B_1)$$.

Теперь применим лемму Цорна. Для этого нужно убедиться, что любое линейно упорядоченное (в смысле описанного порядка) множество пар указанного вида имеет верхнюю границу. В самом деле, объединим все первые компоненты этих пар; пусть $$B$$ - их объединение. Как обычно, согласованность отображений (гарантируемая определением порядка) позволяет соединить отображения в одно. Это отображение (назовем его $$f$$ ) отображает $$B$$ в $$B\hm\times B$$. Оно будет инъекцией: значения $$f(b')$$ и $$f(b'')$$ при различных $$b'$$ и $$b''$$ различны (возьмем большее из множеств, которым принадлежат $$b'$$ и $$b''$$ ; на нем $$f$$ является инъекцией по предположению). С другой стороны, $$f$$ является сюръекцией: для любой пары $$\langle b',b''\rangle\hm\in B\hm\times B$$ возьмем множества, из которых произошли $$b'$$ и $$b''$$, выберем из них большее и вспомним, что мы имели взаимно однозначное соответствие между ним и его квадратом.

По лемме Цорна в нашем частично упорядоченном множестве существует максимальный элемент. Пусть этот элемент есть $$\langle B,f\rangle$$. Мы знаем, что $$f$$ есть взаимно однозначное соответствие между $$B$$ и $$B\hm\times B$$ и потому $$|B|\hm=|B|\hm\times|B|$$. Теперь есть две возможности. Если $$B$$ равномощно $$A$$, то $$B\hm\times B$$ равномощно $$A\hm\times A$$ и все доказано. Осталось рассмотреть случай, когда $$B$$ не равномощно $$A$$, то есть имеет меньшую мощность (большей оно иметь не может, будучи подмножеством). Пусть $$C$$ - оставшаяся часть $$A$$, то есть $$A\hm\setminus B$$. Тогда $$|A|\hm=|B|\hm+|C|\hm=\max(|B|,|C|)$$, следовательно, $$C$$ равномощно $$A$$ и больше $$B$$ по мощности. Возьмем в $$C$$ часть $$C'$$, равномощную $$B$$, и положим $$B'\hm=B\hm+C'$$ (рис. рис 11.2(рис 11.2) Продолжение соответствия с B на B'=B+C'Обе части множества $$B'$$ равномощны $$B$$. Поэтому $$B'\hm\times B'$$ разбивается на $$4$$ части, каждая из которых равномощна $$B\hm\times B$$, и, следовательно, равномощна $$B$$ (напомним, что у нас есть взаимно однозначное соответствие $$f$$ между $$B$$ и $$B\hm\times B$$ ). Соответствие $$f$$ можно продолжить до соответствия $$f'$$ между $$B'$$ и $$B'\hm\times B'$$, дополнив его соответствием между $$C'$$ и $$(B'\hm\times B')\hm\setminus(B\hm\times B)$$ (эта разность состоит из трех множеств, равномощных $$B$$, так что равномощна $$B$$ ). В итоге мы получаем большую пару $$\langle B',f'\rangle$$, что противоречит утверждению леммы Цорна о максимальности. Таким образом, этот случай невозможен.

Выведем теперь некоторые следствия из доказанного утверждения.

Теорема 35. (а) Произведение двух бесконечных мощностей равно большей из них. (б) Если множество $$A$$ бесконечно, то множество $$A^n$$ всех последовательностей длины $$n\hm>0$$, составленных из элементов $$A$$, равномощно $$A$$. (в) Если множество $$A$$ бесконечно, то множество всех конечных последовательностей, составленных из элементов $$A$$, равномощно $$A$$.

Доказательство. Первое утверждение доказывается просто: если $$|A|\hm\le |B|$$, то $$|B|\hm\le |A|\hm\times |B| \hm\le |B|\hm\times |B| \hm= |B|$$.

Второе утверждение легко доказывается индукцией по $$n$$: если $$|A^n|\hm=|A|$$, то $$|A^{n+1}|\hm=|A^n|\hm\times |A|\hm=|A|\hm\times |A|\hm=|A|$$.

Третье тоже просто: множество конечных последовательностей есть $$1\hm+A\hm+A^2\hm+A^3\hm+\ldots$$ ; каждая из частей (кроме первой, которой можно пренебречь) равномощна $$A$$ (по доказанному), и потому все вместе есть $$|A|\hm\times\aleph_0\hm=|A|$$.

Заметим, что из последнего утверждения теоремы вытекает, что семейство всех конечных подмножеств бесконечного множества $$A$$ имеет ту же мощность, что и $$A$$ (подмножеств не больше, чем конечных последовательностей и не меньше, чем одноэлементных подмножеств).

122. Пусть $$A$$ бесконечно. Докажите, что $$|A^A|=|2^A|$$.

123. Рассмотрим мощность $$\alpha\hm=\aleph_0\hm+2^{\aleph_0}\hm+2^{(2^{\aleph_0})}\hm+\ldots$$ (счетная сумма). Покажите, что $$\alpha$$ - минимальная мощность, которая больше мощностей множеств $$\bbN$$, $$P(\bbN)$$, $$P(P(\bbN))$$, $$\dots$$ Покажите, что $$\alpha^{\aleph_0}\hm=2^{\alpha}\hm>\alpha$$.

Теперь мы можем доказать упоминавшееся ранее утверждение о равномощности базисов.

Теорема 36. Любые два базиса в бесконечномерном векторном пространстве имеют одинаковую мощность.

Доказательство. Пусть даны два базиса - первый и второй. Для каждого вектора из первого базиса фиксируем какой-либо способ выразить его через векторы второго базиса. В этом выражении участвует конечное множество векторов второго базиса. Таким образом, есть некоторая функция, которая каждому вектору первого базиса ставит в соответствие некоторое конечное множество векторов второго. Как мы только что видели, возможных значений этой функции столько же, сколько элементов во втором базисе. Кроме того, прообраз каждого значения состоит из векторов первого базиса, выражающихся через данный (конечный) набор векторов второго, и потому конечен. Выходит, что первый базис разбит на группы, каждая группа конечна, а всего групп не больше, чем векторов во втором базисе. Поэтому мощность первого базиса не превосходит мощности второго, умноженной на $$\aleph_0$$ (от чего, как мы знаем, мощность бесконечного множества не меняется). Осталось провести симметричное рассуждение и сослаться на теорему Кантора- Бернштейна.

Страницы:

Лемма Цорна и ее применения

В современных учебниках редко встречается трансфинитная индукция как таковая: она заменяется ссылкой на так называемую лемму Цорна. Сейчас мы покажем, как это делается, на примере теоремы о существовании базиса в линейном пространстве.

Теорема 30 (лемма Цорна) Пусть $$Z$$ - частично упорядоченное множество, в котором всякая цепь имеет верхнюю границу. Тогда в этом множестве есть максимальный элемент, и, более того, для любого элемента $$a\hm\in Z$$ существует элемент $$b\hm\ge a$$, являющийся максимальным в $$Z$$. ( Цепь - это подмножество, любые два элемента которого сравнимы. Верхняя граница цепи - элемент, больший или равный любого элемента цепи.)

Доказательство. Прежде всего отметим, что $$Z$$ лишь частично упорядочено, поэтому надо различать максимальные и наибольшие элементы. По этой же причине мы вынуждены употреблять грамматически некорректную конструкцию " больший или равный любого (любому?)", поскольку сказать " не меньше любого" (стандартный выход из положения) означало бы изменить смысл.

Доказательство повторяет рассуждения при построении базиса, но в более общей ситуации (теперь у нас не линейно независимые семейства, а произвольные элементы $$Z$$ ).

Пусть дан произвольный элемент $$a$$. Предположим, что не существует максимального элемента, большего или равного $$a$$. Это значит, что для любого $$b\hm\ge a$$ найдется $$c\hm>b$$. Тогда $$c\hm>a$$ и потому найдется $$d\hm>c$$ и т.д Продолжая этот процесс достаточно долго, мы исчерпаем все элементы $$Z$$ и придем к противоречию.

Проведем рассуждение аккуратно (пока что мы даже не использовали условие леммы, касающееся цепей). Возьмем вполне упорядоченное множество $$I$$ достаточно большой мощности (большей, чем мощность $$Z$$ ). Построим строго возрастающую функцию $$f\colon I\hm\to Z$$ по трансфинитной рекурсии. Ее значение на минимальном элементе $$I$$ будет равно $$a$$. Предположим, что мы уже знаем все ее значения на всех элементах, меньших некоторого $$i$$. В силу монотонности эти значения попарно сравнимы. Поэтому существует их верхняя граница $$s$$, которая, в частности, больше или равна $$a$$. Возьмем какой-то элемент $$t\hm>s$$ и положим $$f(i)\hm=t$$ ; по построению монотонность сохранится. Тем самым $$I$$ равномощно части $$Z$$, что противоречит его выбору.

В этом рассуждении, формально говоря, есть пробел: мы одновременно определяем функцию по трансфинитной рекурсии и доказываем ее монотонность с помощью трансфинитной индукции. Наше рекурсивное определение имеет смысл, лишь если уже построенная часть функции монотонна. Формально говоря, надо воспользоваться теоремой 19, считая, что следующее значение не определено, если уже построенный участок не монотонен, и получить функцию, определенную на всем $$I$$ или на начальном отрезке. Если она определена на некотором начальном отрезке, то она монотонна на нем по построению, поэтому следующее значение тоже определено - противоречие.

Как и при построении базиса Гамеля (задача 115), можно обойтись без множества большей мощности. Вполне упорядочим множество $$Z$$ с помощью теоремы Цермело. Этот порядок никак не связан с исходным порядком на $$Z$$ ; мы будем обозначать его символом $$\prec$$. Построим с помощью трансфинитной рекурсии функцию $$f\colon Z \hm\to Z$$ с такими свойствами: (1) $$f(z) \hm\ge a$$ для любого $$z\hm\in Z$$ ; (2) $$f$$ монотонна в следующем смысле: если $$x\hm\prec y$$, то $$f(x)\hm\le f(y)$$ ; (3) $$f(z)$$ не может быть строго меньше $$z$$ (в смысле исходного порядка $$\le$$ ) ни при каком $$z$$.

Делается это так. Значение $$f(z_0)$$ для $$\prec$$ - наименьшего элемента $$z_0$$ мы положим равным либо $$a$$, либо $$z_0$$ (последнее - если $$z_0 \hm> a$$ ). Значение $$f(z)$$ для остальных $$z$$ есть либо верхняя граница значений $$f(z')$$ при $$z'\hm\prec z$$ (по предположению индукции множество таких значений линейно упорядочено и потому имеет некоторую верхнюю границу $$\alpha$$ ), либо само $$z$$ (последнее - если $$z\hm>\alpha$$ ).

В силу монотонности множество значений функции $$f$$ линейно упорядочено и имеет верхнюю границу. Эта граница (обозначим ее $$\beta$$ ) больше или равна $$a$$ (которое есть $$f(z_0)$$ ) и является искомым максимальным элементом: если $$\beta \hm< z$$ для некоторого $$z$$, то $$f(z)\hm\le\beta\hm<z$$, что противоречит свойству (3).

Теперь повторим доказательство теоремы о базисе, используя лемму Цорна. Пусть $$V$$ - произвольное векторное пространство. Рассмотрим частично упорядоченное множество $$Z$$, состоящее из линейно независимых подмножеств пространства $$V$$. Порядок на $$Z$$ задается отношением "быть подмножеством".

Проверим, что условия леммы выполнены. Пусть имеется некоторая цепь, то есть семейство линейно независимых множеств, причем любые два множества этого семейства сравнимы. Объединим все эти множества и покажем, что полученное множество будет линейно независимым (тем самым оно будет верхней границей элементов цепи). В самом деле, нетривиальная линейная комбинация включает в себя какое-то конечное число векторов, каждый из своего множества. Этих множеств конечное число, и потому среди них есть наибольшее по включению (в конечном линейно упорядоченном множестве есть наибольший элемент). Это наибольшее множество содержит все векторы нетривиальной линейной комбинации, и линейно независимо по предположению, так что наша нетривиальная линейная комбинация отлична от нуля.

Таким образом, можно применить лемму Цорна и заключить, что любое линейно независимое множество векторов содержится в максимальном линейно независимом множестве векторов. К нему уже нельзя добавить ни одного вектора, не создав линейной зависимости, и оно является искомым базисом.

Аналогичным образом можно доказать существование ортогонального базиса в гильбертовом пространстве (там определение базиса другое: разрешаются бесконечные линейные комбинации, понимаемые как суммы рядов) или существование базиса трансцендентности (максимальная алгебраически независимая система элементов в расширении полей).

Мы приведем другой пример применения леммы Цорна, где фигурируют уже известные нам понятия.

Теорема 31. Всякий частичный порядок может быть продолжен до линейного.

Доказательство. Пусть $$(X,\le)$$ - частично упорядоченное множество. Теорема утверждает, что существует отношение порядка $$\le'$$ на $$X$$, продолжающее исходное (это значит, что $$x\hm\le y\Rightarrow x \le' y$$ ) и являющееся отношением линейного порядка. (Кстати, отметим, что слово "линейного" в формулировке теоремы нельзя заменить на слово "полного" - например, если исходный порядок линейный, но не полный.)

Готовясь к применению леммы Цорна, рассмотрим частично упорядоченное множество $$Z$$, элементами которого будут частичные порядки на $$X$$ (то есть подмножества множества $$X\hm\times X$$, обладающие свойствами рефлексивности, транзитивности и антисимметричности), упорядоченные по включению: $$\le_1$$ считается меньшим или равным $$\le_2$$, если $$\le_2$$ продолжает $$\le_1$$ (из $$x\le_1 y$$ следует $$x\le_2 y$$ ).

Легко проверить, что условие леммы Цорна выполнено: если у нас есть семейство частичных порядков, линейно упорядоченное по включению, то объединение этих порядков является частичным порядком, и этот порядок будет верхней границей семейства. (Проверим, например, что объединение обладает свойством транзитивности. Пусть $$x\le_1 y$$ в одном из порядков семейства $$(\le_1)$$, а $$y\le_2 z$$ в другом; один из порядков (например, $$\le_1$$ ) продолжает другой, тогда $$x\le_1 y \le_1 z$$ и потому $$x\hm\le z$$ в объединении. Рефлексивность и антисимметричность проверяются столь же просто.)

Следовательно, по лемме Цорна на множестве $$X$$ существует максимальный частичный порядок, продолжающий исходный. Обозначим его как $$\le$$ (путаницы с исходным порядком не возникнет, так как исходный нам больше не нужен). Нам надо показать, что он будет линейным. Пусть $$x,y\hm\in X$$ - два несравнимых элемента. Расширим порядок до нового порядка $$\le'$$, при котором $$x\le' y$$. Этот новый порядок определяется так: $$a\le' b$$, если (1) $$a\le b$$ или (2) $$a\le x$$ и $$y\hm\le b$$. Несложно проверить, что $$\le'$$ будет частичным порядком. Рефлексивность очевидна. Транзитивность: если $$a\le'b$$ и $$b\le' c$$, то есть четыре возможности. Если в обоих случаях имеет место случай (1), то $$a\hm\le b \hm\le c$$ и все очевидно. Если $$a\le' b$$ в силу (1), а $$b\le c$$ в силу (2), то $$a\hm\le b\hm\le x$$ и $$y\hm\le c$$, так что $$a \le' c$$ в силу (2). Аналогично рассматривается и симметричный случай. Наконец, двукратная ссылка на (2) невозможна, так как тогда $$(a\hm\le x)$$, $$(y\hm\le b)$$, $$(b\hm\le x)$$ и $$(y\hm\le c)$$, и получается, что $$y\hm\le b\hm\le x$$, а мы предполагали, что $$x$$ и $$y$$ не сравнимы. Антисимметричность доказывается аналогично. Таким образом, отношение $$\le'$$ будет частичным порядком, строго содержащим $$\le$$, что противоречит максимальности.

120. Покажите, что любое бинарное отношение без циклов (цикл образуется, если $$xRx$$, или $$xRyRx$$, или $$xRyRzRx$$ и т.д) может быть продолжено до линейного порядка. (Для конечных множеств поиск такого продолжения обычно называют " топологической сортировкой ".)

121. Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит соединяющий их отрезок. Покажите, что любые два непересекающихся выпуклых множества можно разделить прямой (каждое множество лежит по одну сторону от прямой, возможно, пересекаясь с ней). (Указание. Используя лемму Цорна, можно расширить исходные непересекающиеся множества $$A$$ и $$B$$ до взаимно дополнительных выпуклых множеств $$A'$$ и $$B'$$. Затем можно убедиться, что граница между $$A'$$ и $$B'$$ представляет собой прямую.)

Свойства операций над мощностями

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

Теорема 32. Если $$A$$ бесконечно, то множество $$A\hm\times\bbN$$ равномощно $$A$$.

Доказательство. Вполне упорядочим множество $$A$$. Мы уже знаем , что всякий элемент множества $$A$$ однозначно представляется в виде $$z\hm+n$$, где $$z$$ - предельный элемент (не имеющий непосредственно предыдущего), а $$n$$ - натуральное число. Это означает, что $$A$$ равномощно $$B\hm\times\bbN$$, где $$B$$ - множество предельных элементов. (Тут есть небольшая трудность - последняя группа элементов конечна, если в множестве есть наибольший элемент. Но мы уже знаем, что добавление конечного или счетного множества не меняет мощности, так что этим можно пренебречь.)

Теперь утверждение теоремы очевидно: $$A\hm\times\bbN$$ равномощно $$(B\hm\times\bbN)\hm\times\bbN$$, то есть $$B\hm\times(\bbN\hm\times\bbN)$$ и тем самым $$B\hm\times\bbN$$ (произведение счетных множеств счетно), то есть $$A$$.

По теореме Кантора - Бернштейна отсюда следует, что промежуточные мощности (в частности, $$|A|\hm+|A|$$, а также любое произведение $$A$$ и конечного множества) совпадают с $$|A|$$. Еще одно следствие полезно выделить:

Теорема 33. Сумма двух бесконечных мощностей равна их максимуму.

Доказательство. Прежде всего напомним, что любые две мощности сравнимы (теорема 25). Пусть, скажем, $$|A|\hm\le |B|$$. Тогда $$|B|\hm\le |A|+|B| \hm\le |B|+|B| \hm\le |B|\hm\times\aleph_0 \hm= |B|$$ (последнее неравенство - утверждение предыдущей теоремы). Остается воспользоваться теоремой Кантора- Бернштейна и заключить, что $$|B|\hm=|A\hm+B|$$.

Теперь можно доказать более сильное утверждение.

Теорема 34. Если $$A$$ бесконечно, то $$A\hm\times A$$ равномощно $$A$$.

Доказательство. Заметим, что для счетного множества (как, впрочем, и для континуума - но это сейчас не важно) мы это уже знаем. Поэтому в $$A$$ есть подмножество, равномощное своему квадрату.

Рассмотрим семейство всех таких подмножеств вместе с соответствующими биекциями. Элементами этого семейства будут пары $$\langle B, f\rangle$$, где $$B$$ - подмножество $$A$$, а $$f\colon B\hm\to B\hm\times B$$ - взаимно однозначное соответствие. Введем на этом семействе частичный порядок: $$\langle B_1, f_1\rangle\hm\le \langle B_2,f_2\rangle$$, если $$B_1 \hm\subset B_2$$ и ограничение отображения $$f_2$$ на $$B_1$$ совпадает с $$f_1$$ (рис. рис.11.1).

(рис 11.1)

Отображение $$f_1$$ - взаимно однозначное соответствие между малым квадратом и его стороной; $$f_2$$ добавляет к нему взаимно однозначное соответствие между $$B_2\hm\setminus B_1$$ и " уголком" $$(B_2\hm\times B_2)\setminus(B_1\hm\times B_1)$$.

Теперь применим лемму Цорна. Для этого нужно убедиться, что любое линейно упорядоченное (в смысле описанного порядка) множество пар указанного вида имеет верхнюю границу. В самом деле, объединим все первые компоненты этих пар; пусть $$B$$ - их объединение. Как обычно, согласованность отображений (гарантируемая определением порядка) позволяет соединить отображения в одно. Это отображение (назовем его $$f$$ ) отображает $$B$$ в $$B\hm\times B$$. Оно будет инъекцией: значения $$f(b')$$ и $$f(b'')$$ при различных $$b'$$ и $$b''$$ различны (возьмем большее из множеств, которым принадлежат $$b'$$ и $$b''$$ ; на нем $$f$$ является инъекцией по предположению). С другой стороны, $$f$$ является сюръекцией: для любой пары $$\langle b',b''\rangle\hm\in B\hm\times B$$ возьмем множества, из которых произошли $$b'$$ и $$b''$$, выберем из них большее и вспомним, что мы имели взаимно однозначное соответствие между ним и его квадратом.

По лемме Цорна в нашем частично упорядоченном множестве существует максимальный элемент. Пусть этот элемент есть $$\langle B,f\rangle$$. Мы знаем, что $$f$$ есть взаимно однозначное соответствие между $$B$$ и $$B\hm\times B$$ и потому $$|B|\hm=|B|\hm\times|B|$$. Теперь есть две возможности. Если $$B$$ равномощно $$A$$, то $$B\hm\times B$$ равномощно $$A\hm\times A$$ и все доказано. Осталось рассмотреть случай, когда $$B$$ не равномощно $$A$$, то есть имеет меньшую мощность (большей оно иметь не может, будучи подмножеством). Пусть $$C$$ - оставшаяся часть $$A$$, то есть $$A\hm\setminus B$$. Тогда $$|A|\hm=|B|\hm+|C|\hm=\max(|B|,|C|)$$, следовательно, $$C$$ равномощно $$A$$ и больше $$B$$ по мощности. Возьмем в $$C$$ часть $$C'$$, равномощную $$B$$, и положим $$B'\hm=B\hm+C'$$ (рис. рис 11.2(рис 11.2) Продолжение соответствия с B на B'=B+C'Обе части множества $$B'$$ равномощны $$B$$. Поэтому $$B'\hm\times B'$$ разбивается на $$4$$ части, каждая из которых равномощна $$B\hm\times B$$, и, следовательно, равномощна $$B$$ (напомним, что у нас есть взаимно однозначное соответствие $$f$$ между $$B$$ и $$B\hm\times B$$ ). Соответствие $$f$$ можно продолжить до соответствия $$f'$$ между $$B'$$ и $$B'\hm\times B'$$, дополнив его соответствием между $$C'$$ и $$(B'\hm\times B')\hm\setminus(B\hm\times B)$$ (эта разность состоит из трех множеств, равномощных $$B$$, так что равномощна $$B$$ ). В итоге мы получаем большую пару $$\langle B',f'\rangle$$, что противоречит утверждению леммы Цорна о максимальности. Таким образом, этот случай невозможен.

Выведем теперь некоторые следствия из доказанного утверждения.

Теорема 35. (а) Произведение двух бесконечных мощностей равно большей из них. (б) Если множество $$A$$ бесконечно, то множество $$A^n$$ всех последовательностей длины $$n\hm>0$$, составленных из элементов $$A$$, равномощно $$A$$. (в) Если множество $$A$$ бесконечно, то множество всех конечных последовательностей, составленных из элементов $$A$$, равномощно $$A$$.

Доказательство. Первое утверждение доказывается просто: если $$|A|\hm\le |B|$$, то $$|B|\hm\le |A|\hm\times |B| \hm\le |B|\hm\times |B| \hm= |B|$$.

Второе утверждение легко доказывается индукцией по $$n$$: если $$|A^n|\hm=|A|$$, то $$|A^{n+1}|\hm=|A^n|\hm\times |A|\hm=|A|\hm\times |A|\hm=|A|$$.

Третье тоже просто: множество конечных последовательностей есть $$1\hm+A\hm+A^2\hm+A^3\hm+\ldots$$ ; каждая из частей (кроме первой, которой можно пренебречь) равномощна $$A$$ (по доказанному), и потому все вместе есть $$|A|\hm\times\aleph_0\hm=|A|$$.

Заметим, что из последнего утверждения теоремы вытекает, что семейство всех конечных подмножеств бесконечного множества $$A$$ имеет ту же мощность, что и $$A$$ (подмножеств не больше, чем конечных последовательностей и не меньше, чем одноэлементных подмножеств).

122. Пусть $$A$$ бесконечно. Докажите, что $$|A^A|=|2^A|$$.

123. Рассмотрим мощность $$\alpha\hm=\aleph_0\hm+2^{\aleph_0}\hm+2^{(2^{\aleph_0})}\hm+\ldots$$ (счетная сумма). Покажите, что $$\alpha$$ - минимальная мощность, которая больше мощностей множеств $$\bbN$$, $$P(\bbN)$$, $$P(P(\bbN))$$, $$\dots$$ Покажите, что $$\alpha^{\aleph_0}\hm=2^{\alpha}\hm>\alpha$$.

Теперь мы можем доказать упоминавшееся ранее утверждение о равномощности базисов.

Теорема 36. Любые два базиса в бесконечномерном векторном пространстве имеют одинаковую мощность.

Доказательство. Пусть даны два базиса - первый и второй. Для каждого вектора из первого базиса фиксируем какой-либо способ выразить его через векторы второго базиса. В этом выражении участвует конечное множество векторов второго базиса. Таким образом, есть некоторая функция, которая каждому вектору первого базиса ставит в соответствие некоторое конечное множество векторов второго. Как мы только что видели, возможных значений этой функции столько же, сколько элементов во втором базисе. Кроме того, прообраз каждого значения состоит из векторов первого базиса, выражающихся через данный (конечный) набор векторов второго, и потому конечен. Выходит, что первый базис разбит на группы, каждая группа конечна, а всего групп не больше, чем векторов во втором базисе. Поэтому мощность первого базиса не превосходит мощности второго, умноженной на $$\aleph_0$$ (от чего, как мы знаем, мощность бесконечного множества не меняется). Осталось провести симметричное рассуждение и сослаться на теорему Кантора- Бернштейна.

Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^