Понять доказательство теоремы Цермело

[Charlz_Klug]

Приведу начало доказательства теоремы

Цитата:

Теорема: Каждое множество может быть вполне упорядочено.

Доказательство: Пусть $S$ — произвольное множество. Определим функцию $\varphi$, выбрав произвольно из каждого непустого подмножества $S$ один элемент. Это можно на основании аксиомы выбора.
Рассмотрим класс $\mathcal{C}$ всех упорядоченных подмножеств множества $S$, обладающих следующим свойством: каждый элемент $x$ подмножества $A \in \mathcal{C}$ определяется как элемент, который функция $\varphi$ ставит в соответствие дополнению в $S$ множества $B_x$ всех элементов множества $A$, предшествующих $x$:

$$x=\varphi(S \setminus B_x)$$

Очевидно, что класс $\mathcal{C}$ не пуст. В частности, ему принадлежат все конечные подмножества множества $S$ с первым элементом $x_1 = \varphi(S \setminus \emptyset) = \varphi(S)$ и последующими элементами, определяемыми вышепреведённой формулой: $x_n = \varphi(S \emptyminus \{ x_1, ..., x_{n-1} \})$.
Докажем сначала, что все множества класса $\mathcal{C}$ вполне упорядочены. Для этого заметим, что в каждом подмножестве множества $A \in \mathcal{C}$, содержащем некоторый его отрезок, минимальным элементом служит общий первый элемент $\varphi(S)$ всех множеств класса $\mathcal{C}$. Для каждого подмножества $B$ множества $A$, не содержащего никакого отрезка множества $A$, существует максимальный отрезок $C$ множества $A$, не пересекающийся с $B$. Элемент $\varphi(A \setminus C)$ множества $A$, определяющий его отрезок $C$, представляет собой минимальный элемент подмножества $B \in A$. Таким образом, каждое подмножество множества $A \in \mathcal{C}$ имеет минимальный элемент, что и доказывает полную упорядоченность множества $A \in \mathcal{C}$.

Тут столько крутых поворотов в сюжете, что я теряю нить повествования. Пусть у меня $A$ — множество $\{ 0,1,2,3 \}$. Если я правильно понял, получается что множество $B$ — это множество $\{ 3 \}$?

[Charlz_Klug]

Вместо

Charlz_Klug в сообщении #1325703 писал(а):

определяемыми вышепреведённой формулой: $x_n = \varphi(S \{ x_1, ..., x_{n-1} \})$.

Следует читать

Charlz_Klug в сообщении #1325703 писал(а):

определяемыми вышепреведённой формулой: $x_n = \varphi(S \setminus \{ x_1, ..., x_{n-1} \})$.

-- 10.07.2018, 20:40 --

Charlz_Klug в сообщении #1325703 писал(а):

Пусть у меня $A$ — множество $\{ 0,1,2,3 \}$. Если я правильно понял, получается что множество $B$ — это множество $\{ 3 \}$?

Хочу написать по-другому: пусть $S = \{0,1,2,3\}$. Можно ли тогда $\varphi$ определить так:

$$\varphi(S) = 0,$$

$$\varphi(S \setminus \{ 0\}) = 1,$$

$$\varphi(S \setminus \{ 0, 1\}) = 2,$$

$$\varphi(S \setminus \{ 0,1,2\}) = 3\text{?}$$

[Someone]

Charlz_Klug в сообщении #1325703 писал(а):

Пусть у меня $A$ — множество $\{ 0,1,2,3 \}$. Если я правильно понял, получается что множество $B$ — это множество $\{ 3 \}$?

Предполагается, что $0=\varphi(S)$, $1=\varphi(S\setminus\{0\})$, $2=\varphi(S\setminus\{0,1\})$, $3=\varphi(S\setminus\{0,1,2\})$? Тогда $B$ — любое подмножество $A$ не содержащее $0$.
Замечание. Под отрезком множества $A$ я понимаю любое его подмножество вида $\{x\in A:x\leqslant k\}$, где $k\in A$. Если в вашем источнике под отрезком понимается что-то другое, то будет хорошо, если Вы нас проинформируете.

Charlz_Klug в сообщении #1325715 писал(а):

Можно ли тогда $\varphi$ определить так:

Нет. Функцию выбора Вы должны определить до того, как начнёте определять что-либо ещё.

Charlz_Klug в сообщении #1325703 писал(а):

Элемент $\varphi(A \setminus C)$ множества $A$, определяющий его отрезок $C$, представляет собой минимальный элемент подмножества $B \in A$.

Тут, вроде бы, должно быть $\varphi(S\setminus C)$.

[george66]

Идея такая: мы выбираем элемент за элементом, пользуясь заданной заранее функцией выбора, пока множество не кончится. На первом шаге мы выбираем элемент $x_1=\varphi(S)$. На втором шаге выбираем $x_2=\varphi(S-\{x_1\})$. На третьем $x_3=\varphi(S-\{x_1,x_2\})$. Допустим, мы уже выбрали счётное число элементов $\{x_1,x_2,x_3\ldots\}$, но остаток множества $S$ ещё не пустой. Тогда выбираем из этого остатка элемент $\varphi(S-\{x_1,x_2,x_3\ldots\})$ и это будет элемент $x_{\omega}$. Затем выбираем $x_{\omega+1}$,$x_{\omega+2}$ и так далее, пока $S$ не кончится.

[Charlz_Klug]

Из "Лекций по функциональному анализу" В.С. Пугачёв, страница 33:

Цитата:

Отрезком упорядоченного множества $A$, определяемым элементом $a \in A$, называется множество всех элементов $A$, строго предшествующих $a$.

-- 11.07.2018, 11:20 --

george66, с этим мне удалось разобраться, вроде бы. Мне не понятно про отрезки.

-- 11.07.2018, 11:26 --

Как я понимаю, понятие отрезка по Пугачёву отличается от понятия отрезка по Someone. Потому что по Пугачёву получаются отрезками в $A$ следующие множества: для $1$ — $\{0\}$, для $2$ — $\{0, 1\}$, для $3$ — $\{0,1,2\}$.

-- 11.07.2018, 11:28 --

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

Предполагается, что $0=\varphi(S)$, $1=\varphi(S\setminus\{0\})$, $2=\varphi(S\setminus\{0,1\})$, $3=\varphi(S\setminus\{0,1,2\})$?

Да, именно так.

-- 11.07.2018, 11:31 --

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

Тут, вроде бы, должно быть $\varphi(S\setminus C)$.

Я списал точно с книги (страница 34).

-- 11.07.2018, 11:48 --

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

Под отрезком множества $A$ я понимаю любое его подмножество вида $\{x\in A:x\leqslant k\}$, где $k\in A$.

Как я понял по вашему определению получается, что для, например, $2$ отрезками могут служить и $\{0\}$ и $\{0,1\}$ и $\{0,1,2\}$ и $\{1\}$ и $\{1,2\}$ и $\{2\}$?

[Someone]

Charlz_Klug в сообщении #1325817 писал(а):

Как я понимаю, понятие отрезка по Пугачёву отличается от понятия отрезка по Someone.

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

Charlz_Klug в сообщении #1325703 писал(а):

Для каждого подмножества $B$ множества $A$, не содержащего никакого отрезка множества $A$, существует максимальный отрезок $C$ множества $A$, не пересекающийся с $B$

пустой отрезок нужно исключить, потому что он содержится в любом $B$. Поскольку цитируемый Вами автор ничего не сказал о пустом отрезке, я подумал, что используемое им определение не допускает пустых отрезков, поэтому так и сформулировал. При том определении, которое Вы привели, процитированная выше фраза должна быть такой: "Для каждого подмножества $B$ множества $A$, не содержащего никакого непустого отрезка множества $A$, …".

Charlz_Klug в сообщении #1325817 писал(а):

Как я понимаю, понятие отрезка по Пугачёву отличается от понятия отрезка по Someone. Потому что по Пугачёву получаются отрезками в $A$ следующие множества: для $1$ — $\{0\}$, для $2$ — $\{0, 1\}$, для $3$ — $\{0,1,2\}$.

Ага. А для $0$ — $\varnothing$. А моё определение для $0$ даёт $\{0\}$, для $1$ — $\{0,1\}$ и т.д., не давая при этом $\varnothing$.

Charlz_Klug в сообщении #1325817 писал(а):

Я списал точно с книги (страница 34).

Значит, там опечатка. Элементы же определяются как $\varphi(S\setminus C)$.

Charlz_Klug в сообщении #1325817 писал(а):

Как я понял по вашему определению получается, что для, например, $2$ отрезками могут служить и $\{0\}$ и $\{0,1\}$ и $\{0,1,2\}$ и $\{1\}$ и $\{1,2\}$ и $\{2\}$?

И каким же образом Вы получили два первых и три последних? У меня получается только $\{0,1,2\}$. (Кстати, если в перечислении союз "и" повторяется, то перед ним ставится запятая, за исключением самого первого.)

На всякий случай: $\{x\in A:\Phi(x)\}$ обозначает совокупность всех элементов множества $A$, для которых формула $\Phi(x)$ (со свободной переменной $x$) истинна.

[Charlz_Klug]

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

$\{x\in A:\Phi(x)\}$

Я это понял как произвольно взятые $x$ для которых истинно $\Phi(x)$. А оно оказалось для всех $x$.

[Someone]

Это стандартное обозначение. Я никогда не встречал других толкований.

[Charlz_Klug]

Спасибо, буду знать.

[Charlz_Klug]

Теперь хочу выяснить про

Charlz_Klug в сообщении #1325703 писал(а):

Для каждого подмножества $B$ множества $A$, не содержащего никакого отрезка множества $A$, существует максимальный отрезок $C$ множества $A$, не пересекающийся с $B$.

Значит ли это что максимальный отрезок $C$ един для всяких разных подмножеств $B$, или для каждого разного $B$ существует свой отдельный максимальный отрезок $C$?

-- 11.07.2018, 16:00 --

Да, я упустил когда печатал про

Charlz_Klug в сообщении #1325703 писал(а):

Для каждого подмножества $B$ множества $A$, не содержащего никакого отрезка множества $A$, существует максимальный отрезок $C$ множества $A$, не пересекающийся с $B$.

Полностью должно было быть так:

Цитата:

Для каждого подмножества $B$ множества $A$, не содержащего никакого отрезка множества $A$, существует максимальный отрезок $C$ множества $A$, не пересекающийся с $B$, который, очевидно, представляет собой объединение всех отрезков множества $A$, не пересекающихся с $B$.

-- 11.07.2018, 16:01 --

Так понимаю, что для каждого $B$ есть свой максимальный отрезок $C$?

[Someone]

Charlz_Klug в сообщении #1325929 писал(а):

Так понимаю, что для каждого $B$ есть свой максимальный отрезок $C$?

Да. Отрезок $C$ ведь определяется с помощью конкретного подмножества $B\subset A$ и даёт минимальный элемент именно для $B$, поэтому нет оснований предполагать, что $C$ один и тот же для всех $B$.

Charlz_Klug в сообщении #1325929 писал(а):

не содержащего никакого отрезка

Ещё раз уточняю: не содержащего никакого непустого отрезка. Раз уж стандартное определение допускает пустой отрезок, его надо исключить (и отдельно объяснить, как найти минимальный элемент, если $A\setminus B$ не содержит непустых отрезков).

[Charlz_Klug]

Someone, большое спасибо за разъяснения! Стало понятно.