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

[mihaild]

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

этом $c\ne P$

$c \not \in P$.

Всё правильно, вот только

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

При этом построении задается биекция $P\rightarrow S$, при которой каждая точка $x_i\in P$ отображается в отрезок $\Delta_i$, которому не принадлежит

лишнее - не нужно, и только запутывает. А по модулю этого одно и то же рассуждение.

[Vladimir Pliassov]

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

$c \not \in P$.

Да, конечно, не $c\ne P$, а $c\notin P$. Спасибо.

[Vladimir Pliassov]

Попробую применить тот же трюк к диагональному доказательству. Приведу сначала доказательство из http://math-info.hse.ru/f/2014-15/CompL ... hestva.pdf стр. 26:

Цитата:

Теорема 7 (Кантора). Множество бесконечных последовательностей нулей и единиц несчётно.

$\rhd$ Предположим, что оно счётно. Тогда все последовательности нулей и единиц можно перенумеровать: $\alpha_0, \alpha_1, \ldots$ Составим бесконечную вниз таблицу, строками которой будут наши последовательности:

$$\begin {matrix} \alpha_0=&\alpha_{00}&\alpha_{01}&\alpha_{02}&\ldots\\ \alpha_1=&\alpha_{10}&\alpha_{11}&\alpha_{12}&\ldots\\ \alpha_2=&\alpha_{20}&\alpha_{21}&\alpha_{22}&\ldots\\ \hdotsfor [1.5] {5} \\ \end {matrix} $$

(через $\alpha_{ij}$ мы обозначаем $j$-й член $i$-й последовательности). Теперь рассмотрим последовательность, образованную стоящими на диагонали членами $\alpha_ {00}, \alpha_ {11}, \alpha_ {22}, \ldots$; её $i$-й член есть $\alpha_{ii}$ и совпадает с $i$-м членом $i$-й последовательности. Заменив все члены на противоположные, мы получим последовательность $\beta$, у которой

$$\beta_i=1-\alpha_{ii},$$

так что последовательность $\beta$ отличается от любой из последовательностей $\alpha_i$ (в позиции $i$) и потому отсутствует в таблице. Это
противоречит нашему предположению о том, что таблица включает в себя все последовательности. $\lhd$

$\rhd$ Возьмем произвольное счетное подмножество $P$ множества $Q$ всех бесконечных последовательностей нулей и единиц. Перенумеруем последовательности, которые являются элементами множества $P$, и расположим их строками таблицы. Инвертируем диагональ таблицы, получим последовательность, которой нет в $P$. При этом она есть в $Q$, и значит, $P\ne Q$, таким образом, $Q$ не является своим счетным подмножеством, то есть $Q$ несчетно.$\lhd$

Получилось?

[mihaild]

Да, это вроде бы повтор одного и того же немного разными словами. Вы видите какую-то существенную разницу в этих двух вариантах?

[Vladimir Pliassov]

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

Вы видите какую-то существенную разницу в этих двух вариантах?

Разница в том, что это две разные теоремы. А сходство в том, что обе они доказываются одним и тем же трюком. Но ведь и оригинальные доказательства используют один и тот же трюк: предполагается, что множество счетно, исходя из этого, предполагается, что оно перенумеровывается, элементы вносятся в список или в таблицу (что в принципе одно и то же), затем обнаруживается элемент, которого нет в списке (в таблице).

[mihaild]

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

Разница в том, что это две разные теоремы

Первая говорит, что $Q$ несчетно. Вторая, что любое счетное подмножество множества $Q$ отличается от $Q$. Вы про это различие?

[Vladimir Pliassov]

Здесь две теоремы:

1) Множество точек отрезка $[0,1]$ несчетно,

2) Множество бесконечных последовательностей нулей и единиц несчётно.

Или они не разные?

[mihaild]

А, я имел в виду что в каждом из Ваших двух постов два утверждения, и утверждения в первом посте совпадают, а также утверждения во втором посте совпадают.
Утверждения в первом посте действительно отличаются от утверждений во втором посте.

[Vladimir Pliassov]

Вы имеете в виду, что мои доказательства мало отличаются от доказательств Кантора? (Как я полагаю, оба эти доказательства принадлежат ему.)

[mihaild]

Да, что то, что в блоке "Цитата", слабо отличается от того, что под ним.

[Vladimir Pliassov]

Конечно, в главном принципе отличия нет (в том, что обнаруживается еще одна последовательность), но отличие все же есть: я не предполагаю вначале, что все множество $Q$ счетно -- а потом выясняется, что оно несчетно, -- а беру его произвольное счетное подмножество $P$, которое в самом деле счетно, и поэтому мне понятнее, что его элементы можно перенумеровать. Затем в $Q$ обнаруживается еще один элемент, кроме элементов подмножества $P$, и это тоже мне понятно. Мне кажется, что мое доказательство проще для понимания, чем доказательство Кантора, хотя и его я, пусть и с некоторым трудом, но начинаю понимать. То есть мне надо еще немного до него дорасти, а свое я уже понимаю.

Однако есть один вопрос. Я начинаю с того, что беру произвольное счетное подмножество $P$ множества $Q$, значит, сначала должно быть доказано, что в любом бесконечном множестве есть счетное подмножество.

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

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

[mihaild]

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

То есть мне надо еще немного до него дорасти, а свое я уже понимаю

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

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

Я начинаю с того, что беру произвольное счетное подмножество $P$ множества $Q$, значит, сначала должно быть доказано, что в любом бесконечном множестве есть счетное подмножество

Совершенно не обязательно.
Вы хотите в итоге доказать, что $Q$ не является счетным. Для этого достаточно доказать, что любое его счетное подмножество отличается от самого $Q$.

Кстати существование счетного подмножества в бесконечном множестве - довольно тонкая штука.

[Vladimir Pliassov]

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

Кстати существование счетного подмножества в бесконечном множестве - довольно тонкая штука.

Почему? Я сейчас посмотрел доказательство по индукции (http://www.pm298.ru/kbmnozh7.php) и ничего тонкого не увидел.

[mihaild]

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

Я сейчас посмотрел доказательство по индукции (http://www.pm298.ru/kbmnozh7.php ) и ничего тонкого не увидел

Потому что это доказательство на самом деле неправильное:)
Попробуйте найти ошибку, если не получится - расскажу (это действительно нетривиальный момент, который нужно специально учиться замечать).
Сформулируйте, какое в точности утверждение там доказывается по индукции?

[Vladimir Pliassov]

Я всмотрелся, и теперь мне здесь не все ясно.

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

Сформулируйте, какое в точности утверждение там доказывается по индукции?

Утверждение $P_1$ -- можно выбрать $a_1$, утверждение $P_2$ -- можно выбрать $a_1, a_2$, утверждение $P_3$ -- можно выбрать $a_1, a_2, a_3$, и так далее.

Если это доказательство по индукции, то, как я понимаю, база индукции: выбрано $a_1$ (с этим все в порядке), -- но вот индукционный переход вызывает у меня сомнение: из того, что выбраны $n$ элементов $a_1, a_2, \ldots , a_n$, следует, что можно выбрать $n+1$ элементов $a_1, a_2, \ldots , a_n, a_{n+1}$. Это не очень понятно: то, что можно выбрать конечное подмножество элементов, по-моему, следует непосредственно из того, что множество $M$ бесконечное.

Если взять другие утверждения: утверждение $P_1$ -- существует $a_1$, утверждение $P_2$ -- существуют $a_1, a_2$, утверждение $P_3$ -- существуют $a_1, a_2, a_3$, и так далее, то и тут непонятно, почему из того, что существуют элементы $a_1, a_2, \ldots , a_n$, следует, что существуют элементы $a_1, a_2, \ldots , a_n, a_{n+1}$.

Может быть, это доказательство не по индукции?