*Schönfinkel Seminar*
*Теорема Цермело*
*Sergei Tropanets <trop.ser...@gmail.com>*
Как и обещал, в качестве дополнения к лекции No. 2, написал текст о
теореме Цермело. В тексте использованы следующие обозначения:
"(∀x)" -- "для любого x"
"(x ∈ M)" -- "для любого x из множества M"
"(∃x)" -- "существует x"
"~" -- "не"
"=>" -- "следует"
"⋀" -- "и"
"⋁" -- "или"
"∈" -- "принадлежит"
"⊂" -- "подмножество"
"⊊" -- "собственное подмножество"
Любые замечания, исправления, вопросы и уточнения приветствуются.
Теорема Цермело
Теорема Цермело гласит: "На любом множестве существует полный
порядок."
Зачем потребовалось упорядочивать множества и что значит полный
порядок?
В конце XIX века математики поняли, что кроме обычного порядка '<' на
натуральных,
рациональных или действительных числах(5 < 12, 2/3 < 5/2, e < pi)
имеет смысл строить и
другие порядки (например, такие, при которых 10 < 2). Более того,
упорядочивать можно и
полезно не только числа, но и, скажем, точки плоскости или
пространства и, вообще, любые
другие множества. Мы будем дальше использовать символ '<' не только
как привычный порядок на
числах, но и как любой другой возможный порядок на некотором
(необязательно числовом) множестве. Самым главным свойством
натуральных чисел
является то, что их обычный порядок удовлетворяет одному очень
полезному принципу -- принципу
полной индукции: если 1 обладает свойством Ф и из того, что все k
меньшие n обладают
свойством Ф следует, что и n обладает свойством Ф, то ВСЕ натуральные
числа обладают
свойством Ф. На языке первого порядка:
{Ф(1) ⋀ (∀n) [(∀k)(k<n => Ф(k)) => Ф(n)]} => (∀n)Ф(n)
Большинство нетривиальных свойств натуральных чисел доказываются
именно с применением этого
принципа. Естественно было бы попытаться обобщить этот полезный
принцип и на другие множества. Но для
этого нужно сначала уметь упорядочивать множества, причем так, чтобы
принцип полной индукции
действительно имел место для любого возможного свойства. В таком
случае математики надеялись
обобщить полную индукцию на все другие множества и по аналогии с
натуральными числами получить
интересные результаты об этих множествах.
Такая обобщенная полная индукция называется трансфинитной индукцией, а
порядок для которого
выполняется трансфинитная индукция -- полным порядком. Итак, порядок
на некотором множестве
называется полным, если (i) существует наименьший по отношению к этому
порядку элемент
(как 1 в натуральных числах), (ii) этот порядок удовлетворяет принципу
трансфинитной
индукции. Если на множестве задан полный порядок, то говорят, что это
множество вполне
упорядочено.
Приведем пример. Докажем, что если множество всех прямых на плоскости
можно вполне упорядочить,
то можно построить такое множество X точек на плоскости, что КАЖДАЯ
прямая на плоскости пересекает
пересекает X ТОЧНО в двух точках. Действительно, если множество всех
прямых плоскости вполне
упорядочено, то для этого множества справедлива трансфинитная
индукция. Мы, более того,
можем предположить, что множество всех прямых вполне упорядочено так,
что для любой прямой
y множество всех прямых x меньших y имеет размер (мощность) меньшую
чем размер множества
всех прямых на плоскости. [Это следует из теории множеств Кантора. Для
сведующих: множество
всех прямых на плоскости имеет размер континуума, так как множество
всех невертикальных
прямых континуально (ибо каждая такая прямая однозначно задается парой
коэффициентов (a, b)
своего уравнения ax+b=0, а континуум * континуум = континуум) и
множество всех вертикальных
прямых континуально (ибо каждая из них однозначно задается точкой на
оси иксов через которую
она проходит)), а континуум + континуум = континуум. Поскольку
ординалы вполне упорядочены,
то во множестве всех континуальных ординалов найдется наименьший -- С.
Тогда все ординалы
меньшие С -- менее чем континуальны. Упорядочим множество всех прямых
по ординалу С. Тогда
все отрезки будут иметь размер меньший континуума. Если вдобавок
предположить истинность
континуум гипотезы, то выйдет, что любое континуальное множество можно
так вполне упорядочить,
что каждый его отрезок {y | y<x} будет счетным, что само по себе
удивительно!] Возьмем самую
первую прямую в нашем полном порядке. Выберем произвольно две
различные точки на ней. Это и
будут первые две точки нашего будущего множества. Пусть теперь мы уже
построили множество V
точек такое, что каждые три из его точек не лежат на одной прямой и
каждая прямая меньшая
прямой x проходит ТОЧНО через две точки этого множества. Покажем как
расширить множество V
до множества W так, чтобы, аналогично, никакие три точки W не лежали
на одной прямой и чтобы
каждая прямая меньшая ЛИБО РАВНАЯ прямой x проходила ТОЧНО через две
точки множества W. Могут
представиться следующие случаи. 1) Прямая x проходит точно через две
точки из V, тогда можно
положить W=V. 2) Прямая x проходит точно через одну точку из V, тогда
поскольку множество всех
прямых, проходящих через две точки множества V меньше чем
континуум(так как V имеет размер
меньше чем континуум, что, в свою очередь, следует из того, что
множество всех прямых
меньших x имеет размер меньший чем континуум), а всех точек на самой x
ровно континуум, то найдется точка A на x, через которую не проходит
никакая прямая
проходящая через две точки из V (и, в частности, никакая прямая
меньшая x). Эту точку A мы и
добавим в V получив тем самым W. 3) На прямой x нет точек из V. В этом
случае, аналогично
предыдущему можно выбрать две точки A и B на x, через которые не
проходит никакая прямая меньшая x, и
добавить их к V получив W. Так, "последовательно" можно рассмотреть
все прямые, одну за
другой, расширяя множество V и получить искомое множество точек X.
Это рассуждение не до конца строгое поскольку не совсем понятно, что
значит "последовательно". Однако его можно без труда сделать строгим
введя ординалы Кантора и ведя
трансфинитную индукция по ординалам.
Другие примеры приложения трансфинитной индукции
можно найти здесь:
И. В. Ященко Парадоксы теории множеств
и здесь:
ru.wikipedia: Трансфинитная_индукция
Теорема Цермело была доказана Цермело в 1904 году спустя 3 месяца
после Третьего Интернационального Конгресса математиков, на котором Кениг представил (как в последствии
выяснилось) ошибочное доказательство того, что континуальные множества
(например, множество
всех действительных чисел) НЕЛЬЗЯ вполне упорядочить. После
публикации, доказательство Цермело было
подвергнуто жесткой критике со стороны ведущих математиков того
времени. Под давлением этой
критики, Цермело выделил самые существенные методы рассуждений на
которые опирается
доказательство и в итоге, по существу, пришел к тому, что мы называем
сегодня аксиомами
теории множеств Цермело. Особую роль в доказательстве играла т. н.
аксиома выбора. Пытаясь
придать доказательству более убедительную форму, Цермело обходит
применение результатов Кантора
о мощностях, но в то же время замечает, что аксиома выбора не только
влечет его теорему, но
и по существу эквивалентна ей. Это в дальнейшем послужило поводом для
недоверия к аксиоме выбора. Новое
упрощенное доказательство он публикует четыре года спустя, в 1908
году. Изложим это
доказательство (с некоторыми незначительными упрощениями обозначений).
Перед тем, как приводить доказательство Цермело, докажем
вспомагательный факт, а именно, что
если множество М упорядочено так, что выполнены свойства:
1) (∀x)(∀y) (x<y => ∼(y<x)) (антисимметричность)
2) (∀x)(∀y)(∀z) [(x<y ⋀ y<z) => x<z] (транзитивность)
3) (∀x)(∀y) (x<y ⋁ x=y ⋁ y<x) (линейность)
4) Для любого непустого подмножества K множества M существует элемент
x из K такой, что для любого другого
элемента y из К справедливо x < y (т.е. x --наименьший элемент в K),
то такой порядок на М является полным.
Действительно, пусть M упорядочено так, что имеют место свойства 1) -
4). Тогда, в силу 4),
М имеет наименьший элемент, поскольку М -- подмножество себя. Теперь
покажем, что имеет место
трансфинитная индукция. Для этого предположим, что для некоторого
свойства Ф имеет место
i) Ф(1),
ii) из того, что имеет место Ф(y) для всех y<x следует, что имеет
место Ф(x),
и докажем, что тогда имеет место Ф(x) для любого x из М.
Предположим противное, т.е. что для некоторого Ф, выполнены i) и ii)
но не для всех x имеет
место Ф(x). Тогда множество таких x, что Ф(x) не имеет место --
непусто. Значит, в силу 4),
в нем есть наименьший элемент z. Тогда для всех y<z, Ф(y) имеет место.
Но тогда, в силу ii),
получаем, что Ф(z) должно иметь место. Таким образом, Ф(z)
одновременно имеет место и не
имеет место, противоречие.
Цермело фактически доказал, что любое множество можно упорядочить так,
чтобы выполнялись
свойства 1) - 4) и, значит, можно вполне упорядочить.
Итак, пусть М -- произвольное множество. Пусть функция f сопоставляет
каждому непустому
подмножеству М некоторый из его элементов, т. е. f(A) ∈ A для каждого
подмножества A
множества М. Существование такого соответствия и есть аксиома выбора.
Для каждого подмножества
А определим: А' = A\{f(A)}. Далее, Цермело определяет понятия тета-
цепи подмножеств.
Множество T подмножеств множества M называется тета-цепью, если
i) М ∈ T
ii) из того, что A ∈ T следует, что A' ∈ T
iii) пересечение любого набора множеств из T снова есть элемент Т.
Очевидно, что пересечение любого набора тета-цепей -- вновь тета-цепь.
Рассмотрим пересечение
ВСЕХ тета-цепей. Обозначим его через |M. Очевидно, что любое
подмножество |M, которое
является тета-цепью совпадает с |M. Некоторые элементы A тета-цепи |M
(например, M) обладают
тем свойством, что
(*) (X ∈ |M) (∼(X = A) => (X ⊊ A ⋁ A ⊊ X)).
Далее, Цермело показывает, что множество всех A из |M обладающих
свойством (*) само является
тета-цепью и, значит, совпадает с |M. Для этого, он показывает
сначала, что если A обладает
свойством (*), то множество
{X ∈ |M | X ⊂ A'} U {X ∈ |M | A ⊊ X} U {A} является тета-
цепью, т. е. совпадает с |M. Это делается несложно, прямой проверкой
свойств i), ii), iii) в
определении тета-цепи. Из равенства
{X ∈ |M | X ⊂ A'} U {X ∈ |M | A ⊊ X} U {A} = |M
можно получить (X ∈ |M) (∼(X = A') => (X ⊊ A' ⋁ A' ⊊ X)), т. е. что
A' также удовлетворяет
свойству (*). Несложно видеть также, что пересечение любого набора
элементов |M,
удовлетворяющих (*), также удовлетворяет (*). Таким образом,
действительно, множество всех
A из |M обладающих свойством (*) само является тета-цепью и, значит,
совпадает с |M. Итак,
все элементы |M обладают свойством (*). А тогда
(A ∈ |M)(B ∈ |M)(B ⊂ A' ⋁ A ⊂ B').
Последнее позволяет вполне упорядочить M следующим образом. Каждое
подмножество P множества
M порождает элемент P_0 минимальной тета-цепи |M который является
пересечением всех элементов
|M, которые содержат P как подмножество, причем f(P_0) ∈ P (поскольку
иначе P_0'=P_0\{f(P_0)} ∈ |M и P ⊂ P_0' и тогда P_0 ⊊ P_0', что
невозможно). На самом деле, существует точно одно
P_0 ∈ |M такое, что P ⊂ P_0 и f(P_0) ∈ P. Действительно, пусть P_1 не
= P_0 и P ⊂ P_1.
Тогда P_0 ⊊ P_1 и, по предыдущему, P_0 ⊂ P_1', т.е. f(P_1) не ∈ P.
Возьмем {a} в качестве P
(где a ∈ M). Через R(a) обозначим элемент |M, который пораждается
P={a}. Таким образом,
каждый элемент a из M определяет единственный елемент R(a) из |M
такой, что f(R(a))=a.
Следйющим шагом Цермело определяет порядок на M так:
для любых a и b из M: a < b если b ∈ R(a).
Покажем, что это полный порядок на M. Пусть a и b из M, а не равно b.
Пусть P={a, b}
порождает P_0 е |M. Тогда либо R(a)=P_0 либо R(b)=P_0, но не вместе.
Тогда либо b ∈ R(a) либо
a ∈ R(b), но не вместе. Это дает антисимметричность и линейность.
Пусть a, b, c --попарно
различные элементы M и b ∈ R(a), c ∈ R(b). Пусть P={a, b, c} порождает
P_0 е |M. Легко
проверить, что P_0=R(a) (предположив, что P_0=R(b) или P_0=R(c) легко
получить противоречие).
Следовательно, c ∈ R(a). Таким образом, получаем транзитивность.
Теперь покажем свойство
полноты 4). Пусть P подмножество M. Пусть P_0 порождает P и
f(P_0) ∈ P. Поскольку, P_0=R(f(P_0)), то для любого x ∈ P верно
x ∈ P_0=R(f(P_0)), а значит f(P_0) < x, т.е. f(P_0)
-- наименьший элемент P.
Сергей