Доказательство теоремы Цермело

[AGu]

В рамках обсуждения темы «Полное решение континуум-проблемы»
возникло пожелание увидеть достаточно строгое и подробное
доказательство (в ZFC) теоремы Цермело о вполне упорядочении.
Откликаясь на это пожелание, ваш покорный сочинил
один из возможных вариантов такого доказательства.
Следует отметить, что при этом ничего нового изобретено не было.
Это всего лишь слегка осовремененное и чуть-чуть оптимизированное
доказательство, изложенное в монографии П.С.Александрова
«Введение в теорию множеств и общую топологию» (глава 3, §5).

Текст доказательства можно скачать в виде PDF-файла.
По традиции этот текст дублирован ниже в теле сообщения.
Итак...

Теорема Цермело
Любое множество может быть вполне упорядочено
Подробное доказательство в ZFC

Пусть $s$ — произвольное непустое множество.
По аксиоме выбора существует такая функция $f:\mathcal P(s)\backslash\{\varnothing\}\to s$,

что $f(x)\in x$ для всех $x\in\mathcal P(s)\backslash\{\varnothing\}$.

Для $x\in\mathcal P(s)\backslash\{s\}$ положим $\sigma_x:=f(s\backslash x)$. Заметим, что $\sigma_x\notin x$.
Для $x\in\mathcal P(s)\backslash\{s\}$ положим $x^+:=x\cup\{\sigma_x\}$.
Введем обозначение $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y$ для отношения сравнимости: $(x\subseteq y$ или $y\subseteq x)$.

Лемма 1. Пусть $x,y\in\mathcal P(s)\backslash\{s\}$, $x\subseteq y^+$, $y\subseteq x^+$. Тогда $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$.

Итак, пусть $x\subseteq y\cup\{\sigma_y\}$ и $y\subseteq x\cup\{\sigma_x\}$.
Наша цель — показать, что $x\cup\{\sigma_x\}\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y\cup\{\sigma_y\}$.
Если $\sigma_x\in y$, то $x\cup\{\sigma_x\}\subseteq y\cup\{\sigma_y\}\cup\{\sigma_x\}=y\cup\{\sigma_y\}$.
Если $\sigma_y\in x$, то $y\cup\{\sigma_y\}\subseteq x\cup\{\sigma_x\}\cup\{\sigma_y\}=x\cup\{\sigma_x\}$.
Пусть теперь $\sigma_x\notin y$ и $\sigma_y\notin x$.

Поскольку $x\subseteq y\cup\{\sigma_y\}$ и $\sigma_y\notin x$, мы имеем $x\subseteq y$.
Поскольку $y\subseteq x\cup\{\sigma_x\}$ и $\sigma_x\notin y$, мы имеем $y\subseteq x$.
Следовательно, $x=y$, а значит, $x\cup\{\sigma_x\}=y\cup\{\sigma_y\}$.

Положим $\mathbb S:=\bigl\{X\subseteq\mathcal P(s):\varnothing\in X,\,(\forall\,Y\subseteq X)({\cup}Y\in X),\,(\forall\,x\in X\backslash\{s\})(x^+\in X)\bigr\}$.
Заметим, что $\mathbb S\ne\varnothing$, так как, например, $\mathcal P(s)\in\mathbb S$.
Положим $S:={\cap}\mathbb S$.
Как легко видеть, $\varnothing\in S,\ (\forall\,Y\subseteq S)({\cup}Y\in S),\ (\forall\,x\in S\backslash\{s\})(x^+\in S)$.
Иными словами, $S\in\mathbb S$.
Следовательно, $S$ — наименьший по включению элемент $\mathbb S$, т.е. $S=\min\mathbb S$.
Для $x\in S$ обозначим через $[x]$ множество всех элементов $S$, сравнимых с $x$,

т.е. положим $[x]:=\{y\in S : x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y\}$.

Для $X\subseteq S$ обозначим через $[X]$ множество всех элементов $S$,

сравнимых со всеми элементами $X$, т.е. положим

$[X]\,:=\,\bigcap_{x\in X}[x]\,=\,\bigl\{y\in S : (\forall\,x\in X)(x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y)\bigr\}\,=\,\{y\in S : X\subseteq [y]\}$.

Отметим, что $[x]=[\{x\}]$ для всякого $x\in S$.

Лемма 2. Пусть $X\subseteq S$ и $Y\subseteq [X]$. Тогда ${\cup}Y\in [X]$.

Положим $\bar y:={\cup}Y$ и покажем, что $\bar y\in [X]$.
Поскольку $Y\subseteq [X]\subseteq S$, мы имеем ${\cup}Y\in S$, т.е. $\bar y\in S$.
Пусть $x\in X$. Покажем, что $\bar y\in [x]$, т.е. $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,\bar y$.

Поскольку $Y\subseteq [X]\subseteq [x]$, мы имеем $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y$ для всех $y\in Y$.
Если $y\subseteq x$ для всех $y\in Y$, то $\bar y\subseteq x$.
Если же $y\nsubseteq x$ для некоторого $y\in Y$, то $x\subseteq y$, а значит, $x\subseteq\bar y$.

Лемма 3. Пусть $x\in [S]\backslash\{s\}$, $y\in [x^+]\backslash\{s\}$. Тогда $y^+\in [x^+]$.

Поскольку $y\in [x^+]\backslash\{s\}\subseteq S\backslash\{s\}$, мы имеем $y^+\in S$.
Покажем, что $y^+\in [x^+]$, т.е. $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$.

Поскольку $x\in [S]$ и $y^+\in S$, мы имеем $x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$.
Если $y^+\subseteq x$, то, очевидно, $y^+\subseteq x^+$.
Пусть теперь $x\subseteq y^+$.

Поскольку $y\in [x^+]$, мы имеем $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y$.
Если $x^+\subseteq y$, то, очевидно, $x^+\subseteq y^+$.
Если же $y\subseteq x^+$, то $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$ по лемме 1.

Лемма 4. Справедливо включение $[S]\in\mathbb S$.

По определению $[S]=\bigl\{y\in S : (\forall\,x\in S)(x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y)\bigr\}=\{y\in S : [y]=S\}$.
Ясно, что $\varnothing\in [S]$.
Условие $(\forall\,Y\subseteq [S])({\cup}Y\in [S])$ следует из леммы 2 (для $X=S$).
Осталось показать, что $(\forall\,x\in [S]\backslash\{s\})(x^+\in [S])$.

Итак, пусть $x\in [S]\backslash\{s\}$. Покажем, что $x^+\in [S]$.
Поскольку $x\in [S]\backslash\{s\}\subseteq S\backslash\{s\}$, мы имеем $x^+\in S$.
Покажем, что $[x^+]\in\mathbb S$.

Ясно, что $\varnothing\in [x^+]$.
Условие $(\forall\,Y\subseteq [x^+])({\cup}Y\in [x^+])$ следует из леммы 2 (для $X=\{x^+\}$).
Условие $(\forall\,y\in [x^+]\backslash\{s\})(y^+\in [x^+])$ следует из леммы 3.
Поскольку $[x^+]\in\mathbb S$ и $[x^+]\subseteq S=\min\mathbb S$, мы имеем $[x^+]=S$, т.е. $x^+\in [S]$.

Лемма 5. Множество $S$ вполне упорядочено отношением $\subseteq$.

Покажем линейность порядка: $(\forall\,x,y\in S)(x\subseteq y$ или $y\subseteq x)$.

По лемме 4 мы имеем $[S]\in\mathbb S$. С другой стороны, $[S]\subseteq S=\min\mathbb S$.
Следовательно, $[S]=S$, т.е. $(\forall\,x,y\in S)(x\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y)$.
Покажем, что всякое непустое подмножество $S$ имеет наименьший элемент.

Итак, пусть $\varnothing\ne Z\subseteq S$. Покажем, что $Z$ имеет наименьший элемент.
Положим $Y:=\{y\in S : (\exists\,z\in Z)(z\subseteq y)\}$.
Достаточно показать, что $Y$ имеет наименьший элемент.
Положим $X:=S\backslash Y$.
Как легко видеть, $X=\{x\in S : (\forall\,y\in Y)(x\subset y)\}$.
Положим $\bar x:=\cup X$.
Поскольку $(\forall\,y\in Y)(\forall\,x\in X)(x\subset y)$, мы имеем $(\forall\,y\in Y)(\bar x\subseteq y)$.
Поскольку $X\subseteq S$, мы имеем $\cup X\in S$, т.е. $\bar x\in S$.
Если $\bar x\in Y$, то с учетом $(\forall\,y\in Y)(\bar x\subseteq y)$ мы имеем $\bar x=\min Y$.
Пусть теперь $\bar x\notin Y$, т.е. $\bar x\in X$.

Заметим, что $\bar x=\max X$ и $(\forall\,y\in Y)(\bar x\subset y)$.
Поскольку $\bar x\notin Y$ и $s\in Y$, мы имеем $\bar x\ne s$.
Поскольку $\bar x\in S\backslash\{s\}$, мы имеем $\bar x^+\in S$.
Поскольку $\bar x=\max X$, мы имеем $\bar x^+\notin X$, т.е. $\bar x^+\in Y$.
Покажем, что $\bar x^+=\min Y$.

Если бы нашелся $y\in Y$ такой, что $y\subset\bar x^+$, то мы бы
имели $\bar x\subset y\subset\bar x\cup\{\sigma_{\bar x}\}$, что, очевидно, невозможно.

Лемма 6. Функция $x\mapsto\sigma_x$ является биекцией $S\backslash\{s\}$ на $s$.

Пусть $x,y\in S\backslash\{s\}$, $x\ne y$. Покажем, что $\sigma_x\ne\sigma_y$.

Не нарушая общности, будем считать, что $x\subset y$.
Поскольку $x\in S\backslash\{s\}$, мы имеем $x^+\in S$.
Ясно, что $x^+=x\cup\{\sigma_x\}=\min\{z\in S : x\subset z\}$.
Следовательно, $x\cup\{\sigma_x\}\subseteq y$, а значит, $\sigma_x\in y$.
С другой стороны, $\sigma_y\notin y$ и поэтому $\sigma_x\ne\sigma_y$.
Пусть $\sigma\in s$. Покажем, что $(\exists\,x\in S\backslash\{s\})(\sigma_x=\sigma)$.

Положим $Y:=\{y\in S : \sigma\notin y\}$ и $x:=\cup Y$.
Поскольку $Y\subseteq S$, мы имеем $\cup Y\in S$, т.е. $x\in S$.
По определению $x$ мы имеем $\sigma\notin x$. В частности, $x\ne s$.
Поскольку $x\in S\backslash\{s\}$, мы имеем $x^+\in S$.
Покажем, что $\sigma_x=\sigma$.

Действительно, если бы $\sigma_x\ne\sigma$, то с учетом $\sigma\notin x$
мы бы имели $\sigma\notin x\cup\{\sigma_x\}=x^+\in S$ и тем самым $x^+\in Y$,
что противоречит соотношениям $x=\cup Y$ и $x\subset x^+$.

Из лемм 5 и 6 следует, что множество $s$ может быть вполне упорядочено.

[Инт]

Доказательство Александрова я перепроверил. Там ошибок не нашёл. В том, что Ваше рассуждение по существу правильное, я верю. Но сразу бросается в глаза, что, например, для обоснования бесконечного пересечения ни как не ссылаетесь на другие аксиомы. А там они имеют значение. Этому вопросу надо уделить внимание для того, чтобы исключить использование в доказательстве каких-нибудь неявных положений, не входящих в ZFC. Строго говоря, вполнеупорядочение множества эквивалентно комплексу аксиом, включающему аксиому выбора.

[Виктор Викторов]

Инт в сообщении #237289 писал(а):

Строго говоря, вполнеупорядочение множества эквивалентно комплексу аксиом, включающему аксиому выбора.

Теорема о вполне упорядочении эквивалентна аксиоме выбора. Это значит, что из ZF и теоремы о вполне упорядочении выводится аксиома выбора и наоборот (что очевидно по обсуждаемой теме) из ZF и аксиомы выбора выводится теорема о вполне упорядочении.

[AGu]

Инт в сообщении #237289 писал(а):

для обоснования бесконечного пересечения ни как не ссылаетесь на другие аксиомы. А там они имеют значение.

Пусть $\mathbb X$ — произвольное непустое множество.
По аксиоме объединения существует множество $U:=\cup\mathbb X$,

т.е. такое множество $U$, что $(\forall\,x)\bigl(x\in U\,\Leftrightarrow\,(\exists\,X\in\mathbb X)(x\in X)\bigr)$.

По принципу выделения существует множество $V:=\{x\in U:(\forall\,X\in\mathbb X)(x\in X)\}$,

т.е. такое множество $V$, что $(\forall\,x)\bigl(x\in V\,\Leftrightarrow\,x\in U$ и $(\forall\,X\in\mathbb X)(x\in X)\bigr)$.

Покажем, что $V=\cap\mathbb X$, т.е. $(\forall\,x)\bigl(x\in V\,\Leftrightarrow\,(\forall\,X\in\mathbb X)(x\in X)\bigr)$.

Пусть $x$ — произвольное множество.
Если $x\in V$, то, очевидно, $(\forall\,X\in\mathbb X)(x\in X)$.
Если же $(\forall\,X\in\mathbb X)(x\in X)$, то ввиду непустоты $\mathbb X$

имеем $(\exists\,X\in\mathbb X)(x\in X)$, т.е. $x\in U$;
следовательно, $x\in U$ и $(\forall\,X\in\mathbb X)(x\in X)$, т.е. $x\in V$.

-- 2009.08.23 21:56 --

Виктор Викторов в сообщении #237309 писал(а):

Опепятка

Очень даже может такое быть.
Подскажите поточнее, пожалуйста, — исправлю.

[Виктор Викторов]

AGu в сообщении #237313 писал(а):

Виктор Викторов в сообщении #237309 писал(а):

Опепятка

Очень даже может такое быть.
Подскажите поточнее, пожалуйста, — исправлю.

У меня, а не у Вас опепятка. Я нажал не ту кнопку.

-- Вс авг 23, 2009 11:33:30 --

AGu в сообщении #237268 писал(а):

Лемма 1. Пусть $x,y\in\mathcal P(s)\backslash\{s\}$, $x\subseteq y^+$, $y\subseteq x^+$. Тогда $x^+\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y^+$.

Итак, пусть $x\subseteq y\cup\{\sigma_y\}$ и $y\subseteq x\cup\{\sigma_x\}$.
Наша цель — показать, что $x\cup\{\sigma_x\}\,{\raise.75pt\hbox{$\subset$}\mskip-10mu\lower.75pt\hbox{$\supset$}}\,y\cup\{\sigma_y\}$.
Если $\sigma_x\in y$, то $x\cup\{\sigma_x\}\subseteq y\cup\{\sigma_y\}\cup\{\sigma_x\}=y\cup\{\sigma_y\}$.
Если $\sigma_y\in x$, то $y\cup\{\sigma_y\}\subseteq x\cup\{\sigma_x\}\cup\{\sigma_y\}=x\cup\{\sigma_x\}$.
Пусть теперь $\sigma_x\notin y$ и $\sigma_y\notin x$.

Поскольку $x\subseteq y\cup\{\sigma_y\}$ и $\sigma_y\notin x$, мы имеем $x\subseteq y$.
Поскольку $y\subseteq x\cup\{\sigma_x\}$ и $\sigma_x\notin y$, мы имеем $y\subseteq x$.
Следовательно, $x=y$, а значит, $x\cup\{\sigma_x\}=y\cup\{\sigma_y\}$.

Стоит заметить, что, если $\sigma_x\in y$, то $x^+= y$.

[Инт]

Считаю, что надо ещё уточнить вопрос о том, почему существует функция, отображающая некоторое множество ординалов на вполнеупорядоченное (как интерпретируется при доказательстве) множество $s$.

-- Вс авг 23, 2009 20:44:16 --

Это, чтобы исключить такую интерпретацию теоремы: каждое множество можно неограниченно вполнеупорядочивать.

[Виктор Викторов]

Инт в сообщении #237335 писал(а):

Считаю, что надо ещё уточнить вопрос о том, почему существует функция отображающая некоторое множество ординалов, на вполнеупорядоченное (как интерпретируется при доказательстве) множество $s$.

О какой функции идёт речь?

Инт в сообщении #237335 писал(а):

Это, чтобы исключить такую интерпретацию теоремы: каждое множество можно неограниченно вполнеупорядочивать.

Что значит «неограниченно вполнеупорядочивать»?

[Инт]

Виктор Викторов в сообщении #237338 писал(а):

О какой функции идёт речь?

Отображающей некоторое множество ординалов, на множество $s$.

[Xaositect]

То есть нужно доказать, что если $s$ - вполне упорядоченное множество, то оно изоморфно некоторому ординалу?

[Инт]

Да.

[Виктор Викторов]

Инт в сообщении #237340 писал(а):

Виктор Викторов в сообщении #237338 писал(а):

О какой функции идёт речь?

Отображаюей некоторое множество ординалов, на множество $s$.

Xaositect в сообщении #237341 писал(а):

То есть нужно доказать, что если $s$ - вполне упорядоченное множество, то оно изоморфно некоторому ординалу?

Масло, как известно, масленое. Если множество вполне упорядоченно, то оно «оно изоморфно некоторому ординалу». По-моему всё очевидно. А вот что такое «неограниченно вполнеупорядочивать» так и останется тайной.

[Инт]

Виктор Викторов в сообщении #237348 писал(а):

Масло, как известно, масленое. Если множество вполне упорядоченно, то оно «оно изоморфно некоторому ординалу». По-моему всё очевидно.

Множество всех ординалов тоже очевидно. Так что хотелось бы простого и короткого доказательства, тем более, что оно почти очевидно.

Виктор Викторов в сообщении #237348 писал(а):

А вот что такое «неограниченно вполнеупорядочивать» так и останется тайной.

А не берите в голову. Ведь это только неформальная интерпретация.

[Виктор Викторов]

Инт в сообщении #237349 писал(а):

Виктор Викторов в сообщении #237348 писал(а):

Масло, как известно, масленое. Если множество вполне упорядоченно, то оно «оно изоморфно некоторому ординалу». По-моему всё очевидно.

Множество всех ординалов тоже очевидно. Так что хотелось бы простого и короткого доказательства, тем более, что оно почти очевидно.

Доказательство чего?

Инт в сообщении #237349 писал(а):

Виктор Викторов в сообщении #237348 писал(а):

А вот что такое «неограниченно вполнеупорядочивать» так и останется тайной.

А не берите в голову. Ведь это только неформальная интерпретация.

Так дело не пойдёт. И так «неограниченно вполнеупорядочивать» бессмысленное словосочетание.

[Инт]

Виктор Викторов в сообщении #237352 писал(а):

Доказательство чего?

Xaositect в сообщении #237341 писал(а):

нужно доказать, что если $s$ - вполне упорядоченное множество, то оно изоморфно некоторому ординалу

[Виктор Викторов]

Xaositect в сообщении #237341 писал(а):

нужно доказать, что если $s$ - вполне упорядоченное множество, то оно изоморфно некоторому ординалу

Это очевидно. Ординал (порядковое число) – порядковый тип вполне упорядоченного множества. Каждое вполне упорядоченное множество подобно вполне упорядоченному множеству всех ординалов строго меньших того ординала, который и есть тип данного вполне упорядоченного множества. Мне лень влезать в тег. Этот материал подробно изложен в той самой книге П. С. Александрова. (Правда, там нет слова ординал).