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

[mihaild]

Вы куда-то не туда полезли. Может быть я зря написал $-$.
В общем просто придумайте, как вообще по любой $P$ доказать $(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$.

[Vladimir Pliassov]

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

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

Вы имеете в виду, что мы сейчас рассматриваем только формулы, в которых нет других чисел, кроме натуральных?

[mihaild]

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

Вы имеете в виду, что мы сейчас рассматриваем только формулы, в которых нет других чисел, кроме натуральных?

Мы вообще рассматриваем формулы ZF.
Они позволяют говорить о сложении - в рамках ZF можно определить арифметику на натуральных числах. Но это пока неважно.

[Vladimir Pliassov]

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

Мы вообще рассматриваем формулы ZF.

Откуда в ZF берутся формулы? Я знаю, что в ZF есть аксиомы и схемы (не очень хорошо понимаю, чем они отличаются). Формулы получаются из аксиом? Или в ZF есть еще что-то, из чего они получаются?

[mihaild]

Формулы ZF - это формулы (утверждения) в сигнатуре ZF, т.е. состоящие из кванторов, переменных, логических связок, скобок и символа $\in$.

[Vladimir Pliassov]

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

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

Кажется, понял. Для того, чтобы доказать в ZF эту теорему, надо

1) показать, что утверждение $P(0)$ справедливо;

2) доказать, что $\forall n \in \mathbb N: P(n) \rightarrow P(S(n))$.

Тем самым в ZF будет доказана эта теорема.

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)$$

Метод есть (?), докажу теорему.

$\lhd$ 1) из $y - 0 = 17$ следует $y=17$, отсюда $\exists y: y - 0= 17$.

2) В формуле $\exists y: y - n = 17$ обозначим $y$ через $y_n$, тогда $y_n - n = 17$, откуда $n=y_n-17$. В формуле $\exists y: y - S(n) = 17$ обозначим $y$ через $y_{S_n}$,

тогда $y_{S_n} - S(n) = 17$, откуда $y_{S_n} - S(y_n-17)=17$. Поскольку $y_n-17=n$, возвращаемся к формуле $y_{S_n} - S(n) = 17$ (то есть берем обратную импликацию

к импликации, которая была несколькими словами ранее: $ y_{S_n} - S(y_n-17)=17$, откуда $y_{S_n} - S(n) = 17$).

$S(n)=n+1$ (вот это надо обосновать, и я не знаю как),

поэтому

$y_{S_n} - S(n) = 17$,

$y_{S_n} - (n+1) = 17$,

$y_{S_n} - n-1= 17$,

$y_{S_n} - n= 18$,

$y_{S_n}=n+ 18\to \exists y: y - S(n) = 17$.

Таким образом, доказано, что $\forall n \in \mathbb N: (\exists y: y - n = 17)$. $\rhd$

[mihaild]

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

Для того, чтобы доказать в ZF эту теорему, надо

1) показать, что утверждение $P(0)$ справедливо;

2) доказать, что $\forall n \in \mathbb N: P(n) \rightarrow P(S(n))$.

Совершенно не так.
Вам нужно доказать ровно то утверждение, которое написано выше, а не разбирать его на части.
Нужно это утверждение для того, чтобы если потом мы сможем ещё и доказать, что Ваши два пункта выполнены, то выполнено и заключение принципа индукции.
Более того, утверждение выше (принцип индукции) справедлив и для формул, для которых скажем $P(0)$ неверно, или $P(16) \rightarrow P(17)$ неверно.
О принципе индукции стоит думать как о свойстве именно $\mathbb N$, которое можно использовать для любой формулы, а не о свойстве конкретной формулы.

[Vladimir Pliassov]

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

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

Если Вы имеете в виду принцип индукции:

$$(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$$

то вот доказательство:

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

(Я его переделал: после Вашего замечания заменил фразу "поскольку по определению индуктивного множества для любого $n\ne 0$ существует $m: n=S(m)=m\cup \{m\}$" -- это не верно -- на "поскольку для любого $n: n\in \mathbb N \wedge n\ne 0$ существует $m: n=S(m)=m\cup \{m\}$".)

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

О принципе индукции стоит думать как о свойстве именно $\mathbb N$, которое можно использовать для любой формулы, а не о свойстве конкретной формулы.

Я в этом доказательстве и использую свойство $\mathbb N$, а именно, то что каждый элемент $m\in \mathbb N$ имеет следователя $n=S(m)=m\cup \{m\}$, и каждый элемент $n$, кроме нуля, имеет предшественника $m: S^{-1}(n)$

Есть еще доказательство (я из него взял прием от противного: "пусть не для всех $n$ выполняется принцип индукции"), но оно основывается на принципе наименьшего числа, которое, по-моему, надо доказывать, и еще на том, что $S(n)=n\cup \{n\}=n+1$ -- это тоже надо доказывать, причем я не представляю как.

Цитата:

Предположим, что утверждение $A(n)$ верно не при любых $n$. Рассмотрим множество тех чисел, для которых оно неверно. В нем есть наименьшее число $N$. Это число не равно $1$, так как $A(1)$ истинно. Но тогда $A(N - 1)$ истинно по выбору $N$. Значит, и $A(N)= A(N - 1 + 1)$ истинно. Пришли к противоречию.

Еще один момент. В утверждение $P(n)$ обязательно входит переменная, принимающая натуральные значения (иначе его нельзя было бы доказывать по индукции). Правильно?

[mihaild]

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

По первому условию принципа индукции он выполняется для $n=0$

В принцип индукции $n$ не входит свободно (только под квантором). Поэтому говорить "он выполнен для $n = 0$" нельзя.

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

Но, поскольку для любого $n: n\in \mathbb N \wedge n\ne 0$ существует $m: n=S(m)=m\cup \{m\}$

Это правда, но это нужно доказать. И непосредственно этого для принципа индукции недостаточно, нужно еще одно наблюдение.
Напоминаю, что единственное, что нам на текущий момент известно про $\mathbb N$ - это что оно является минимальным индуктивным множеством.

Возможно, для лучшего понимания происходящего Вам будет полезно построить пример индуктивного множества, отличного от $\mathbb N$. Давайте возьмем произвольное множество $X$. Докажите, что существует индуктивное множество, содержащее $X$ (как подмножество).

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

но оно основывается на принципе наименьшего числа

Да, принцип наименьшего числа - "в любом непустом подмножестве $\mathbb N$ есть наименьший элемент", вместе с утверждением о существовании у любого элемента кроме $0$ предшественника, эквивалентен принципу индукции.

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

и еще на том, что $S(n)=n\cup \{n\}=n+1$

Это доказывать не надо, это определение $S$ и $+1$.

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

В утверждение $P(n)$ обязательно входит переменная, принимающая натуральные значения (иначе его нельзя было бы доказывать по индукции). Правильно?

Тут чуть тоньше. Поскольку мы везде в принципе индукции подставляем в $P$ только натуральные числа, то как она ведет себя на аргументах, не являющихся натуральными числами, неважно.

[Vladimir Pliassov]

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

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

и еще на том, что $S(n)=n\cup \{n\}=n+1$

Это доказывать не надо, это определение $S$ и $+1$.

То есть это определение и для $S$, и для $+1$?

Для $+1$ это как будто понятно, но не с точки зрения того, что мне известно из теории множеств. О натуральных числах я знаю только, что они являются элементами множества

$$\Bigg\{\varnothing, \{\varnothing\}, \big \{\varnothing, \{\varnothing\} \big \}, \Big \{\varnothing, \{\varnothing\}, \big \{\varnothing, \{\varnothing\} \big \} \Big \}, \ldots \Bigg\} \eqno (1)$$

Как можно сложить, например, $\{\varnothing\}$ и $\{\varnothing\}$? Существует ли вообще понятие сложения множеств? Не объединения, а именно сложения? При этом я не имею в виду объединение непересекающихся множеств.

[mihaild]

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

То есть это определение и для $S$, и для $+1$?

Тут всё несколько хитрее - арифметику на натуральных числах надо вводить отдельно. Множества в общем случае складывать нельзя, но мы можем на некоторых множествах ввести функцию двух аргументов, которую назовем "сложение", и дальше записывать как обычное сложение.
На натуральных числах сложение как раз определяется по индукции: $n + 0 = n$, $n + S(m) = S(n + m)$. И с использованием принципа индукции можно доказать, что существует ровно одна функция, удовлетворяющая этому определению.

[Vladimir Pliassov]

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

Множества в общем случае складывать нельзя

Вы имеете в виду, что -- пока в теории множеств не введена операция сложения, -- множества можно складывать тогда и только тогда, когда они не пересекаются? (Тогда это сложение есть объединение непересекающихся множеств и оно обозначается $+$, как обычное сложение). Или -- еще до введения операции сложения -- множества можно складывать также и в каком-то другом случае?

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

но мы можем на некоторых множествах

например, на $\mathbb N$,

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

ввести функцию двух аргументов, которую назовем "сложение"

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

[mihaild]

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

Вы имеете в виду, что -- пока в теории множеств не введена операция сложения, -- множества можно складывать тогда и только тогда, когда они не пересекаются?

Нет, я имею в виду, что пока не введена операция сложения, множества вообще нельзя складывать.
После того, как введена операция сложения, можно складывать множества, являющиеся натуральными числами. Тут немного тоньше - на самом деле мы можем написать формулу, утверждающую "множество $a$ соответствует натуральному числу, являющемуся суммой натуральных чисел, соответствующих множествам $b$ и $c$". Но удобно, и почти никогда не возникает проблем, если мы договоримся, что $a = b + c$ как раз расшифровывается в эту формулу.

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

Для этого должна быть определена неупорядоченная пара элементов

А функция определяется как раз на упорядоченных парах.

Но это всё потом - чтобы было удобно вводить сложение на натуральных числах, нужен принцип индукции. Напоминаю задание: доказать, что для произвольной формулы $P$, $\text{ZF} \vdash (P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$.
Или же, если хотите, доказать следующие два утверждения: $\forall n \in \mathbb N: n \neq 0 \rightarrow \exists m: S(m) = n$, и $\forall A \subseteq \mathbb N: A \neq \varnothing \rightarrow \exists x \in A \forall y \in A: x \leqslant y$, и потом вывести из них принцип индукции.
Первое доказывается просто, но самое простое доказательство второго, из найденных мной за пару минут, сложнее доказательства принципа индукции (хотя может быть есть и какое-то простое, которое я пропустил).

[Vladimir Pliassov]

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

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

Но, поскольку для любого $n: n\in \mathbb N \wedge n\ne 0$ существует $m: n=S(m)=m\cup \{m\}$

Это правда, но это нужно доказать.

$\lhd$ Существует функция $S(m)=m\cup \{m\}$ (надо ли это доказывать?) с областью определения $\mathrm {dom} \,S=\mathbb N \; 0\in \mathbb N$ и с областью значений $\mathrm {ran} \,S=\mathbb N\setminus \{0\}$.

Так как $m\cap \{m\}=\varnothing$, то $S(m)\setminus \{m\}=m$, то есть для функции $S(m)$ существует обратная функция $S^{-1}(n)=S^{-1}(S(m))=S(m)\setminus \{m\}=m$ с областью определения $\mathrm {dom} \,S^{-1}=\mathbb N\setminus \{0\}$ (равной области значений функции $S(m)$) и областью значений $\mathrm {ran} \,S^{-1}=\mathbb N$.

Таким образом, для любого $n: n\in \mathbb N \wedge n\ne 0$ существует $m: n=S(m)=m\cup \{m\}$. $\rhd$

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

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

Вообще, хотелось бы выяснить, что можно делать в теории ZF до того, как в ней введена операция сложения. Например, как я понимаю, в ней еще до введения операции сложения можно определить строгую упорядоченность и равенство элементов $\mathbb N$, то есть элементов множества

$$\Bigg\{\varnothing, \{\varnothing\}, \big \{\varnothing, \{\varnothing\} \big \}, \Big \{\varnothing, \{\varnothing\}, \big \{\varnothing, \{\varnothing\} \big \} \Big \}, \ldots \Bigg\} \eqno (1)$$

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

Каждый элемент $m\in \mathbb N$ имеет следователя $n=S(m)$ и (как доказано выше -- если доказано) каждый элемент $n\in \mathbb N$, кроме нуля, имеет предшественника $m= S^{-1}(n)$.

Определим потомка элемента $k$ как $l=S(S(\ldots(k)\ldots))$, а предка элемента $l$ как $k=S^{-1}(S^{-1}(\ldots(l)\ldots))$, и если $l$ является потомком $k$ (и, соответственно, $k$ является предком $l$), будем считать, что $l>k$. Если же ни $l$ не является потомком $k$, ни $k$ не является потомком $l$, будем считать, что $k=l$.

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

Но это всё потом - чтобы было удобно вводить сложение на натуральных числах, нужен принцип индукции. Напоминаю задание: доказать, что для произвольной формулы $P$, $\text{ZF} \vdash (P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$.

То есть надо доказать, что для произвольной формулы $P$ из аксиом ZF выводится принцип индукции $(P(0) \wedge \forall n \in \mathbb N: P(n) \rightarrow P(S(n))) \rightarrow \forall n \in \mathbb N: P(n)$?

[mihaild]

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

Существует функция $S(m)=m\cup \{m\}$ (надо ли это доказывать?) с областью определения $\mathrm {dom} \,S=\mathbb N \; 0\in \mathbb N$ и с областью значений $\mathrm {ran} \,S=\mathbb N\setminus \{0\}$.

Лучше это как-то иначе обозначить, сохранив $S(x)$ для обозначения терма $x \cup \{x\}$ - т.е. везде, где в формулах мы пишем $S$, на самом деле подразумевается такая запись, $S$ не является функцией и вообще объектом ZF.
Функцию можно ввести, но про неё нужно будет доказывать всё то же самое, поэтому проще не станет. Ключевой момент вот этот:

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

с областью значений $\mathrm {ran} \,S=\mathbb N\setminus \{0\}$.

Тут нужно как-то явно сослаться на свойства $\mathbb N$ (напоминаю, что оно нам известно как минимальное индуктивное множество).
Возможно, чтобы стало понятнее, в чем загвоздка, полезно посмотреть на индуктивные множества, отличные от $\mathbb N$.

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

Давайте возьмем произвольное множество $X$. Докажите, что существует индуктивное множество, содержащее $X$ (как подмножество).

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

Определим потомка элемента $k$ как $l=S(S(\ldots(k)\ldots))$, а предка элемента $l$ как $k=S^{-1}(S^{-1}(\ldots(l)\ldots))$,

Так писать нельзя - нельзя писать формулы переменной длины.
Такое определение натуральных чисел хорошо тем, что в нём неравенство легко выражается через теоретико-множественные операции: $n \leqslant m$ равносильно $n \subseteq m$.

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

То есть надо доказать, что для произвольной формулы $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$", или что-то подобное, чтобы не перепутать с мета-теоремой - принципом индукции для произвольной формулы).