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

[Инт]

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

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

Ординалы определяем по Фон Нейману.

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

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

Ординалы определяем по Фон Нейману.

Вы можете определять ординалы, как Вам угодно. Суть дела изложена. Я с удовольствием и детально читаю доказательство о вполне упорядочении в аранжировке AGu. So, I am out.

[Инт]

А правильно надо было ответить так: По аксиоме выделения во вполнеупорядоченном множестве $s$ выделяется непустое подмножество, элементы которого однозначно сопоставлены ординалам. По аксиоме подстановки если $x$ пробегает $s$, то сопоставленные ординалы пробегают множество. Объединение по множеству ординалов - ординал, по аксиоме объединения. Далее, доказывается, что выделенное подмножество совпадает с $s$.

[AGu]

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

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^+$.
[...]

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

Думаю, все же не стоит.
Например, если $\alpha,\beta\in s$, $\alpha\ne\beta$, $x=\{\alpha\}$, $y=\{\beta\}$, $\sigma_x=\beta$ и $\sigma_y=\alpha$,
то $x,y\in\mathcal P(s)\backslash\{s\}$, $x\subseteq y^+$, $y\subseteq x^+$ и $\sigma_x\in y$, но $x^+\ne y$.

[Someone]

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

А правильно надо было ответить так: ...

Правильно было ответить так: поскольку ни в формулировке теоремы Цермело, ни в её доказательстве ординалы никак не участвуют, то выдумку

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

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

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

[Инт]

Someone в сообщении #237437 писал(а):

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

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

[Someone]

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

Ещё раз: упоминаемая Вами теорема никакого отношения к теореме Цермело или к аксиоме выбора не имеет. Она важна, но здесь не нужна.

[Инт]

Someone в сообщении #237444 писал(а):

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

Вот это последнее, я и требовал отметить, доказать. Иначе, если бы подобия не было, то нельзя было бы говорить о полноценном вполнеупорядочении.

[Someone]

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

если бы подобия не было, то нельзя было бы говорить о полноценном вполнеупорядочении

???
Что значит - "нельзя было бы"? Не выполнялось бы определение вполне упорядоченного множества? В этом определении что-нибудь говорится об ординалах?

Уж Вы извините, но нормально начатая тема Вашими стараниями превращается в какое-то идиотствование.

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

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

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

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^+$.
[...]

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

Думаю, все же не стоит.
Например, если $\alpha,\beta\in s$, $\alpha\ne\beta$, $x=\{\alpha\}$, $y=\{\beta\}$, $\sigma_x=\beta$ и $\sigma_y=\alpha$,
то $x,y\in\mathcal P(s)\backslash\{s\}$, $x\subseteq y^+$, $y\subseteq x^+$ и $\sigma_x\in y$, но $x^+\ne y$.

Заврался я. Спасибо, что поправили.

[AGu]

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

Someone в сообщении #237444 писал(а):

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

Вот это последнее, я и требовал отметить, доказать. Иначе, если бы подобия не было, то нельзя было бы говорить о полноценном вполнеупорядочении.

Я бы не назвал это утверждение тривиальным (несмотря на его «почти очевидность»). Во всяком случае, если у этого утверждения и есть элементарное доказательство, то я им не владею. А неэлементарным — владею. Так что набрать его мне не составит труда — тем более, что мне самому это будет интересно и полезно. Завтра утречком поделюсь результатом.

[AGu]

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

Любое вполне упорядоченное множество
порядково изоморфно некоторому ординалу

Подробное доказательство в ZFC


Для упорядоченного множества $X$ и элемента $x\in X$ условимся
обозначать множество $\{y\in X:y<x\}$ символом $x{\downarrow}$.

Индукция по элементам вполне упорядоченного множества

Для любой теоретико-множественной формулы $\varphi$
следующее утверждение является теоремой ZFC.

Если $Y$ — произвольное вполне упорядоченное множество
и для любого $y\in Y$ из $(\forall\,z\in y{\downarrow})\,\varphi(z)$ следует $\varphi(y)$,
то $\,\varphi(y)$ для всех $y\in Y$.


Положим $Y_0:=\{y\in Y:\neg\varphi(y)\}$.
Предположим вопреки доказываемому, что $Y_0\ne\varnothing$.
Положим $y:=\min Y_0$.
Поскольку $(\forall\,z\in y{\downarrow})(z\notin Y_0)$, мы имеем $(\forall\,z\in y{\downarrow})\,\varphi(z)$.
Следовательно, $\varphi(y)$, что противоречит включению $y\in Y_0$.

Обозначим через $f:D\to\mathbb V$ формализацию утверждения

« множество $f$ является функцией с областью определения $D$».

Для $f:D\to\mathbb V$ и $E\subseteq D$ положим $f[E]:=\{f(e):e\in E\}$.

Всюду ниже $X$ — произвольное вполне упорядоченное множество.
Для $x\in X$ и $f:x{\downarrow}\to\mathbb V$ будем писать $x\vartriangleleft f$ вместо $(\forall\,y\in x{\downarrow})\bigl(\,f(y)=f[y{\downarrow}]\,\bigr)$.
Положим $X_\vartriangleleft:=\bigl\{x\in X:(\exists\,f:x{\downarrow}\to\mathbb V)(x\vartriangleleft f)\bigr\}$.

Лемма 1. Если $x\in X_\vartriangleleft$, то $(\exists!\,f:x{\downarrow}\to\mathbb V)(x\vartriangleleft f)$.

Пусть $x\in X$, $f,g:x{\downarrow}\to\mathbb V$, $x\vartriangleleft f$ и $x\vartriangleleft g$.
Докажем $(\forall\,y\in x{\downarrow})\bigl(\,f(y)=g(y)\,\bigr)$ индукцией по $y\in x{\downarrow}$.
Пусть $y\in x{\downarrow}$ и $(\forall\,z\in y{\downarrow})\bigl(\,f(z)=g(z)\,\bigr)$. Покажем, что $f(y)=g(y)$.

Из $x\vartriangleleft f$ следует $f(y)=f[y{\downarrow}]$.
Из $x\vartriangleleft g$ следует $g(y)=g[y{\downarrow}]$.
Из $(\forall\,z\in y{\downarrow})\bigl(\,f(z)=g(z)\,\bigr)$ следует $f[y{\downarrow}]=g[y{\downarrow}]$.

Таким образом, для всякого $x\in X_\vartriangleleft$ имеется единственная функция $f^x:x{\downarrow}\to\mathbb V$,
удовлетворяющая условию $x\vartriangleleft f^x$, т.е. такая, что $f^x(y)=f^x[y{\downarrow}]$ для всех $y\in x{\downarrow}$.

Лемма 2. Пусть $x\in X_\vartriangleleft$ и $y\in x{\downarrow}$. Тогда $y\in X_\vartriangleleft$ и $f^y=f^x|_{y{\downarrow}}$.

Как легко видеть, из $x\vartriangleleft f^x$ вытекает $y\vartriangleleft f^x|_{y{\downarrow}}$.
Следовательно, $y\in X_\vartriangleleft$.
Поскольку $y\vartriangleleft f^x|_{y{\downarrow}}$ и $y\vartriangleleft f^y$, мы имеем $f^y=f^x|_{y{\downarrow}}$ по лемме 1.

Определим функцию $F:X\to\mathbb V$, полагая

$F(x):=\begin{cases}% f^x[x{\downarrow}],&\text{если }x\in X_\vartriangleleft\,;\\ \varnothing,&\text{если }x\notin X_\vartriangleleft\,. \end{cases}$

(Отметим, что существование такой функции $F$ можно обосновать
с помощью схемы аксиом подстановки.)

Лемма 3. Пусть $x\in X_\vartriangleleft$. Тогда $F(x)=F[x{\downarrow}]$.

Покажем, что $F|_{x{\downarrow}}=f^x$.

Пусть $y\in x{\downarrow}$. Покажем, что $F(y)=f^x(y)$.

По лемме 2 мы имеем $y\in X_\vartriangleleft$ и $f^y=f^x|_{y{\downarrow}}$.
Следовательно, $F(y)=f^y[y{\downarrow}]=f^x|_{y{\downarrow}}[y{\downarrow}]=f^x[y{\downarrow}]=f^x(y)$.
Таким образом, $F(x)=f^x[x{\downarrow}]=F|_{x{\downarrow}}[x{\downarrow}]=F[x{\downarrow}]$.

Лемма 4. Справедливо равенство $X_\vartriangleleft=X$.

Достаточно показать, что $(\forall\,x\in X)\,x\vartriangleleft F|_{x{\downarrow}}$.
Докажем последнее утверждение индукцией по $x\in X$.
Пусть $x\in X$ и $(\forall\,y\in x{\downarrow})(y\vartriangleleft F|_{y{\downarrow}})$. Покажем, что $x\vartriangleleft F|_{x{\downarrow}}$.

Пусть $y\in x{\downarrow}$. Покажем, что $F|_{x{\downarrow}}(y)=F|_{x{\downarrow}}[y{\downarrow}]$.

Поскольку $y\vartriangleleft F|_{y{\downarrow}}$, мы имеем $y\in X_\vartriangleleft$.
По лемме 3 мы имеем $F(y)=F[y{\downarrow}]$.
Следовательно, $F|_{x{\downarrow}}(y)=F(y)=F[y{\downarrow}]=F|_{x{\downarrow}}[y{\downarrow}]$.

Лемма 5. Для всякого $x\in X$ мы имеем $F(x)=\{F(y):\,y\in X,\ y<x\}$.
В частности, если $x,y\in X$ и $y<x$, то $F(y)\in F(x)$.

Утверждение леммы 5 непосредственно вытекает из лемм 3 и 4.

Лемма 6. Для всякого $x\in X$ множество $F(x)$ является ординалом.

Покажем, что для всякого $x\in X$ множество $F(x)$ транзитивно.

Пусть $x\in X$ и $\gamma\in\beta\in F(x)$. Покажем, что $\gamma\in F(x)$.

По лемме 5 найдутся $y,z\in X$ такие, что $z<y<x$, $\gamma=F(z)$ и $\beta=F(y)$.
Поскольку $z<x$, по лемме 5 мы имеем $\gamma=F(z)\in F(x)$.
Покажем, что для всякого $x\in X$ все элементы множества $F(x)$ транзитивны.

По лемме 5 все элементы множества $F(x)$ имеют вид $F(y)$,
а значит, они транзитивны по доказанному выше.
Таким образом, для всякого $x\in X$ множество $F(x)$ транзитивно
и все его элементы транзитивны, т.е. $F(x)$ является ординалом.

Положим $A:=F[X]=\{F(x):x\in X\}$.

Лемма 7. Множество $A$ является ординалом.

По лемме 6 все элементы множества $A$ транзитивны.
Остается показать, что само множество $A$ транзитивно.

Пусть $\beta\in\alpha\in A$. Покажем, что $\beta\in A$.

Поскольку $\alpha\in A$, имеется $x\in X$ такой, что $\alpha=F(x)$.
Поскольку $\beta\in\alpha=F(x)$, по лемме 5 имеется $y\in X$ такой, что $\beta=F(y)$.
Следовательно, $\beta=F(y)\in A$.

Лемма 8. Функция $F$ является порядковым изоморфизмом $X$ на ординал $A$.

По определению $A$ функция $F$ является сюръекцией $X$ на $A$.
Покажем, что для любых $x,y\in X$ из $y<x$ следует $F(y)<F(x)$.

По лемме 5 из $y<x$ следует $F(y)\in F(x)$, т.е. $F(y)<F(x)$.
Покажем, что для любых $x,y\in X$ из $F(y)<F(x)$ следует $y<x$.

Пусть $F(y)<F(x)$. Покажем, что $y<x$.

Если бы $x=y$ или $x<y$, то с учетом доказанного выше мы бы имели

$F(x)=F(y)$ или $F(x)<F(y)$ вопреки неравенству $F(y)<F(x)$.
Следовательно, $y<x$ (в силу линейности порядка на $X$).

[Инт]

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

[Инт]

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

Для любой теоретико-множественной формулы $\varphi$
следующее утверждение является теоремой ZFC.

Если $Y$ — произвольное вполне упорядоченное множество
и для любого $y\in Y$ из $(\forall\,z\in y{\downarrow})\,\varphi(z)$ следует $\varphi(y)$,
то $\,\varphi(y)$ для всех $y\in Y$.


Положим $Y_0:=\{y\in Y:\neg\varphi(y)\}$.
Предположим вопреки доказываемому, что $Y_0\ne\varnothing$.
Положим $y:=\min Y_0$.
Поскольку $(\forall\,z\in y{\downarrow})(z\notin Y_0)$, мы имеем $(\forall\,z\in y{\downarrow})\,\varphi(z)$.
Следовательно, $\varphi(y)$, что противоречит включению $y\in Y_0$.

А откуда известно, что $Y_0$ существует? Хотя бы в виде пустого множества. Нужно ведь исключить случай существования класса в $Y$, т.е. $\exists y \neg\varphi(y)$, но $Y_0$ не существует. Т.е. нужно исключить существование внутри множества $Y$ не-множества.

Я так же вижу, что моя старая идея:

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

По аксиоме выделения во вполнеупорядоченном множестве $s$ выделяется непустое подмножество, элементы которого однозначно сопоставлены ординалам. По аксиоме подстановки если $x$ пробегает $s$, то сопоставленные ординалы пробегают множество.

также не проходит. Так как аксиома подстановки использует формулу $\forall x \exists! y P(x, y)$ в посылке, а нам известно не это, а только то, что $\exists x \exists! y P(x, y)$, где $P(x, y)$ означает элементу $x$ соответствует ординал $y$.

[Xaositect]

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

А откуда известно, что существует? Хотя бы в виде пустого множества. Нужно ведь исключить случай существования класса в , т.е. , но не существует. Т.е. нужно исключить существование внутри множества не-множества.

Аксиома выделения:

Цитата:

Положим $Y_0 = \{y\in Y: \neg \varphi(y)\}$