О возможности упорядочения множества в ZFC и акс. фундирован

[alex_dorin]

Необходима ли аксиома фундирования для возможности упорядочения множества в ZFC ?

[Anton_Peplov]

Нет, не необходима. В книге
К. Куратовский, А. Мостовский. Теория множеств. М.: Мир, 1970
основные теоремы ZFC доказываются без использования аксиомы фундирования.

Чтобы всякое множество могло быть вполне упорядочено тем или иным отношением порядка, необходима аксиома выбора. Для счетных множеств не нужна даже и она - они упорядочиваются по номерам своих элементов.

[AGu]

В рамках древней-придревней dxdy-темы возникло пожелание
увидеть достаточно строгое и подробное доказательство (в 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$ может быть вполне упорядочено.