Теорема Кантора о несчетности множества точек отрезка [0, 1]

[Vladimir Pliassov]

mihaild в сообщении #1614680 писал(а):

Ну и нужно доказать, что пересечение индуктивных множеств индуктивно - Вы понимаете, как это сделать?

Если бы можно было доказывать по индукции, то то, что каждому множеству принадлежит $0$, было бы базой индукции. Но, наверное, по индукции доказывать нельзя? Потому что метод индукции использует натуральные числа.

[mihaild]

Vladimir Pliassov в сообщении #1614683 писал(а):

Если бы можно было доказывать по индукции

Тут непонятно, по какому параметру индукция.
Индукция по натуральным числам доказывает утверждения вида $\forall n \in \mathbb N: P(n)$. А Вам нужно доказать утверждение $\forall X \neq \varnothing ((\forall x \in X: x - \text{индуктивно}) \rightarrow (\cap_{x \in X}x) - \text{индуктивно})$.

[Vladimir Pliassov]

mihaild в сообщении #1614680 писал(а):

Ну и нужно доказать, что пересечение индуктивных множеств индуктивно - Вы понимаете, как это сделать?

В https://ikfia.ysn.ru/wp-content/uploads ... 1966ru.pdf, стр. 108 второй абзац снизу - 109

приводится доказательство существования наименьшего индуктивного множества, изложу его своими словами.

$\lhd$ Пусть дано произвольное индуктивное множество $Y$. Возьмем множество всех его подмножеств ${\mathcal P}(Y)$ и в силу аксиомы выделения выделим из него подмножество $\overline {{\mathcal P}} (Y)$, элементами которого являются все индуктивные подмножества $Y$ ...

Дальше там говорится: "Ясно, что пересечение $Y_0=\bigcap \overline {{\mathcal P}} (Y)$ представляет собой индуктивное множество ..." $\rhd$

Но нам-то это не ясно ("нам-то" -- в определенном смысле), а как доказать, не вижу.

Дальше в доказательстве еще что-то трудное для понимания, пытаюсь разобраться.

[Vladimir Pliassov]

Кажется, нашел.

$\lhd$ Каждый элемент $x$ пересечения индуктивных множеств, включая нуль, принадлежит каждому из множеств, при этом его последователь $x\cup \{x\}$ также принадлежит каждому из множеств, то есть принадлежит их пересечению, таким образом, пересечение индуктивных множеств индуктивно. $\rhd$

[mihaild]

Правильно. Итого у нас есть индуктивное множество (по аксиоме), взяли пересечение всех его индуктивных подмножеств, получили снова индуктивное множество, причем минимальное по включению среди вообще всех индуктивных множеств. Это множество и называется множеством натуральных чисел и обозначается $\mathbb N$.
Теперь можно доказать, что для множества натуральных чисел выполнен принцип индукции (чем и обусловлено название "индуктивное множество"): если $P(x)$ - некоторая формула, то выполнено: $(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$. Покажите это, пользуясь минимальностью $\mathbb N$.
Обратите внимание, что принцип индукции для натуральных чисел не является теоремой ZF, т.к. теорема ZF не может говорить про "произвольные формулы". Это мета-теорема, которая говорит, что для любой формулы $P$, утверждение, получающееся подстановкой $P$ в принцип индукции, является теоремой ZF.

[Vladimir Pliassov]

mihaild в сообщении #1614794 писал(а):

Теперь можно доказать, что для множества натуральных чисел выполнен принцип индукции

Но прежде мне хотелось бы разобраться до конца с доказательством в https://ikfia.ysn.ru/wp-content/uploads ... 1966ru.pdf, стр. 108, второй абзац снизу - стр. 109. Там написано что-то непостижимое! Я переписал часть, которую не могу понять, но, конечно, без того, чтобы пройти по ссылке, разобраться не получится.

Цитата:

Пересечение $Z''_0=Z_0\cap Z'_0$ опять-таки обладает обоими вышеуказанными свойствами;

то есть оно индуктивно

Цитата:

поскольку $Z''_0\subseteq Z$ и $Z''_0\subseteq Z'$, то $Z_0\subseteq Z''_0$ и $Z'_0\subseteq Z''_0$

к этому примечание ниже.

Цитата:

Следовательно, $Z''_0=Z_0=Z'_0$.

Дальше примечание.

Цитата:

Именно $Z''_0$ является в силу сказанного одним из $u$, т.е. $Z_0\in U$

Здесь опечатка? Должно быть: $Z''_0\in U$?

Цитата:

а потому пересечение всех $u$ из $\overline {U}$, то есть $Z_0$, является подмножеством $Z''_0$; аналогично получается и $Z'_0\subseteq Z''_0$. - Прим. ред.

Все ли здесь правильно?

[mihaild]

Vladimir Pliassov в сообщении #1614846 писал(а):

Здесь опечатка? Должно быть: $Z''_0\in U$?

Кажется да.

Vladimir Pliassov в сообщении #1614846 писал(а):

Все ли здесь правильно?

Ну да. Поскольку $Z''_0 \in U$, а $Z_0$ это пересечение всего из $U$, то $Z_0 \subseteq Z''_0$.

Но на мой взгляд возятся с $Z_0'$ там зря, проще сразу рассмотреть $Z_0 \cap Z'$.

[Vladimir Pliassov]

По-моему, тут напутано и у авторов, и в примечании. Из того, что $Z''_0\subseteq Z$, не следует, что $Z_0\subseteq Z''_0$.

То, что $Z''_0 \in U$, не удивительно, ведь $Z''_0$ это подмножество $Z$, а $U={\mathcal P} (Z)$ -- множество всех подмножеств $Z$. И из того, что $Z''_0 \in U$, не следует, что "пересечение всех $u$ из $\overline {U}$, то есть $Z_0$, является подмножеством $Z''_0$".

Тут надо обратить внимание на то, что $Z''_0 \in \overline{U}$ и $Z_0=\bigcap \overline U$, отсюда следует, что $Z_0\subseteq Z''_0$.

Но это, если я правильно понимаю, недоработанная деталь в доказательстве, а в целом оно верно.

Интересно, что в примечании авторов сказано:

Цитата:

наши аксиомы не позволяют нам построить множество всех множеств, обладающих свойствами a) и b)

то есть множество всех индуктивных множеств. Другими словами, в теории множеств Цермело — Френкеля (ZF) (Zermelo–Fraenkel set theory) не существует множества всех индуктивных множеств (а почему?). Так что в этой теории не получится доказать, что один из элементов этого множества является наименьшим по включению индуктивным множеством. То, что в ZF существует наименьшее по включению индуктивное множество, доказывается по-другому.

Когда уже доказано, что в произвольном индуктивном множестве $Z$ есть наименьшее по включению индуктивное подмножество $Z_0$

(и доказано только это, но еще не доказано, что не может быть, чтобы наименьшее по включению индуктивное подмножество какого-то другого индуктивного множества было не равно $Z_0$),

берется еще одно произвольное индуктивное множество $Z'$. В нем есть подмножество "$Z'_0$ -- пересечение, образованное из $Z'$ таким же образом, как $Z_0$ образовано из $Z$". Пересечение $Z''_0=Z_0\cap Z'_0$ тоже индуктивно, и, как сказано, из $Z''_0 \in \overline{U}$ и $Z_0=\bigcap \overline U$ следует, что $Z_0\subseteq Z''_0$. Аналогично и $Z'_0\subseteq Z''_0$. Но и $Z''_0\subseteq Z_0$ и $Z''_0\subseteq Z'_0$, так как $Z''_0=Z_0\cap Z'_0$. "Следовательно, $Z''_0=Z_0=Z'_0$."

То есть в ZF существует единственное наименьшее по включению индуктивное множество $Z_0$.

Цитата:

$Z_0$ можно представить как множество всех неотрицательных целых чисел

[mihaild]

Vladimir Pliassov в сообщении #1614903 писал(а):

И из того, что $Z''_0 \in U$, не следует, что "пересечение всех $u$ из $\overline {U}$, то есть $Z_0$, является подмножеством $Z''_0$".

Так $Z''_0$ это не просто элемент $U$, это еще и элемент $\overline{U}$. Потому что оно является элементом $U$ (уже доказали) и индуктивно (как пересечение индуктивных $Z_0$ и $Z'_0$).

Vladimir Pliassov в сообщении #1614903 писал(а):

Другими словами, в теории множеств Цермело — Френкеля (ZF) (Zermelo–Fraenkel set theory) не существует множества всех индуктивных множеств (а почему?).

Их слишком много. Любое множество является подмножеством некоторого индуктивного. Не самое простое технически, но вроде простое идейно доказательство: пусть $A$ - множество всех индуктивных множеств. Возьмем $B = \bigcup\limits_{a \in A} A$, возьмем $C$ - множество мощности большей чем $B$ (например $\mathcal P(B)$), и возьмем $D$ - индуктивное множество, содержащее $C$. Тогла, с одной стороны, $D \in A$, значит $D \subseteq B$, а с другой стороны мощность $D$ больше мощности $B$.
(кстати так можно опровергнуть и существование множества всех множеств, но тут получается существенно сложнее, чем аргумент Рассела; а вот для индуктивных множеств я сходу аналог аргумента Рассела придумать не могу, хотя скорее всего он есть)

[Vladimir Pliassov]

mihaild в сообщении #1614916 писал(а):

Так $Z''_0$ это не просто элемент $U$, это еще и элемент $\overline{U}$.

Я об этом и написал:

Vladimir Pliassov в сообщении #1614903 писал(а):

Пересечение $Z''_0=Z_0\cap Z'_0$ тоже индуктивно, и, как сказано, из $Z''_0 \in \overline{U}$ и $Z_0=\bigcap \overline U$ следует, что $Z_0\subseteq Z''_0$. Аналогично и $Z'_0\subseteq Z''_0$. Но и $Z''_0\subseteq Z_0$ и $Z''_0\subseteq Z'_0$, так как $Z''_0=Z_0\cap Z'_0$. "Следовательно, $Z''_0=Z_0=Z'_0$."

[mihaild]

Сообразил, что собственно из множества всех индуктивных множеств элементарно строится множество всех множеств: если $A$ - множество всех индуктивных множеств, то $\cup\mathcal P(\cup A)$ - множество всех множеств.

[Vladimir Pliassov]

mihaild в сообщении #1614794 писал(а):

Теперь можно доказать, что для множества натуральных чисел выполнен принцип индукции (чем и обусловлено название "индуктивное множество"): если $P(x)$ - некоторая формула, то выполнено: $(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$. Покажите это, пользуясь минимальностью $\mathbb N$.
Обратите внимание, что принцип индукции для натуральных чисел не является теоремой ZF, т.к. теорема ZF не может говорить про "произвольные формулы". Это мета-теорема, которая говорит, что для любой формулы $P$, утверждение, получающееся подстановкой $P$ в принцип индукции, является теоремой ZF.

Мне надо сначала доказать теорему

"если $P(x)$ - некоторая формула, то выполнено: $(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$",

то есть принцип индукции (причем доказывать не обязательно используя только аксиомы ZF, так как это не теорема ZF?), а затем доказать, что для множества натуральных чисел выполнен принцип индукции?

[Vladimir Pliassov]

mihaild в сообщении #1614794 писал(а):

Теперь можно доказать, что для множества натуральных чисел выполнен принцип индукции (чем и обусловлено название "индуктивное множество"): если $P(x)$ - некоторая формула, то выполнено: $(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$. Покажите это, пользуясь минимальностью $\mathbb N$.
Обратите внимание, что принцип индукции для натуральных чисел не является теоремой ZF, т.к. теорема ZF не может говорить про "произвольные формулы". Это мета-теорема, которая говорит, что для любой формулы $P$, утверждение, получающееся подстановкой $P$ в принцип индукции, является теоремой ZF.

$S(x)=x\cup \{x\}$ это следователь элемента $x$. Так как $x\cap \{x\}=\varnothing$, то $S(x)\setminus \{x\}=x$. Назовем $x$ предшественником $S(x)$.

$\lhd$ По первому условию принципа индукции он выполняется для $n=0$. Пусть принцип индукции выполняется не для всех $n \ne 0$, тогда найдется такое $n\ne 0$, для которого он не выполняется. Но, поскольку по определению индуктивного множества для любого $n\ne 0$ существует $m: n=S(m)=m\cup \{m\}$ (где $m$ является предшественником $n$, а $n$ -- следователем $m$), а по второму условию принципа индукции имеем $\forall m \in \mathbb N: P(m) \rightarrow P(S(m))=P(n)$, то при соблюдении этого условия не найдется такое $n\ne 0$, для которого принцип индукции не выполняется, таким образом, он выполняется для всех $n \in \mathbb N$. $\rhd$

1) Я что, доказал сейчас мета-теорему (если доказал)?

2) По-моему, я здесь не пользовался минимальностью $\mathbb N$. Надо найти доказательство с ее использованием? А как?

[mihaild]

Нет, Вам нужно придумать, как для любой формулы $P$, доказать в ZF теорему $(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$. Т.е. я Вам завтра принесу какую-нибудь формулу $P(x)$, например $\exists y: y - x = 17$, и Ваш метод должен сказать, как доказать в ZF теоерему

$$((\exists y: y - 0 = 17) \wedge \forall n \in \mathbb N: (\exists y: y - n = 17) \rightarrow (\exists y: y - S(n) = 17)) \rightarrow \forall n \in \mathbb N: (\exists y: y - n = 17)$$

Принцип индукции для натуральных чисел - это утверждение о том, что подстановкой в схему выше любой формулы получится теорема ZF. "Для натуральных чисел" он как раз потому что мы рассматриваем истинность формулы на натуральных числах.

Vladimir Pliassov в сообщении #1615030 писал(а):

Но, поскольку по определению индуктивного множества для любого $n\ne 0$ существует $m: n=S(m)=m\cup \{m\}$

Такого в определении индуктивного множества нет. Более того, существуют индуктивные множества, для котороых это неверно.
Кроме того, даже для тех индуктивных множеств, для которых это верно, принцип индукции может быть не выполнен. Ну хорошо, не верно что $P(n)$, тогда неверно и $P(S^{-1}(n))$. В чем противоречие?

[Vladimir Pliassov]

mihaild в сообщении #1615032 писал(а):

Т.е. я Вам завтра принесу какую-нибудь формулу $P(x)$, например $\exists y: y - x = 17$, и Ваш метод должен сказать, как доказать в ZF теорему

$$((\exists y: y - 0 = 17) \wedge \forall n \in \mathbb N: (\exists y: y - n = 17) \rightarrow (\exists y: y - S(n) = 17)) \rightarrow \forall n \in \mathbb N: (\exists y: y - n = 17)$$

Для того, чтобы в ZF существовала такая теорема, в ZF

1) множество $\mathbb N$ должно быть расширено до $\mathbb Z$;

2) на множестве $\mathbb Z$ должна быть определена операция по сложению так, чтобы $\mathbb Z$ превратилось в аддитивную группу;

и еще хорошо бы (а может быть, и необходимо?)

3) на основании п. 2) каким-то образом представить $S(n)=n\cup \{n\}$ как $S(n)=n+1$.

Тогда эту теорему можно легко доказать.

По п. 1): как в ZF доказать существование, например, $-1$, то есть $-\{\varnothing\}$?

По п. 2): вот, что нашел в Википедии ("Система Цермело — Френкеля"):

Цитата:

2.2. Схемы образования множеств с помощью математически корректных суждений

Среди математических высказываний встречаются аксиомы связи, включая:

а) аксиому связи между алгебраической операцией $+$ (сложить) и алгебраической операцией $\cdot$ (умножить)

$$\forall x\forall y\forall z\ (x\in \mathbb {R} \land \ y\in \mathbb {R} \land z\in \mathbb {R} \to (x+y)\cdot z=x\cdot z+y\cdot z),$$

б) аксиому связи между отношением порядка $\leq$ (меньше или равно) и алгебраической операцией $+$ (сложить)

$$\forall x\forall y\forall z\ (x\in \mathbb {R} \land y\in \mathbb {R} \land z\in \mathbb {R} \to (x\leq y\to x+z\leq y+z))$$

Но тут речь сразу о связи между $+$ (сложить) и $\cdot$ (умножить) и о связи между отношением порядка $\leq$ (меньше или равно) и $+$ (сложить), а как в ZF определяются эти операции и отношение, не говорится.

Операцию $+$ можно определить как функцию от двух аргументов: пара элементов отображается в третий, -- но среди аксиом ZF я не вижу подходящей, есть аксиома преобразования, но она определяет функцию от одного аргумента -- или я ошибаюсь?

К тому же как определить пару элементов, когда они равны? Ведь тогда $\{x, x\}=\{x\}$, и пары не получается.

О п. 3) можно поговорить после выяснения по пунктам 1) и 2).