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

[mihaild]

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

То, что она обнаружилась, служит доказательством несчетности $[0, 1]$ именно потому, что в исходном списке заявлены были все элементы $Q$, правильно?

Почти так. Это получается доказательство того, что в любом списке не содержатся все точки отрезка. Значит полного списка не существует, значит отрезок несчетен.
На самом деле метод от противного тут не особо нужен (ну разве что все доказательства несуществования считать доказательством от противного).

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

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

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

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

Наверное, при доказательстве счетности или несчетности множества надо брать его или его замену (при доказательстве от противного) не по частям, а целиком

Тут вопрос не понятен - чью замену, что берем "по частям"?

[Vladimir Pliassov]

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

Тут вопрос не понятен - чью замену?

Например, замену $[0, 1]$ на $Q=\{x_1, x_2, \; \ldots, \; x_n, \; \ldots\}$ при предположении, что отрезок $[0, 1]$ счетен.

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

что берем "по частям"?

Это о том, что

"Если бы они были заявлены не все, то -- если бы они составляли бесконечное подмножество $Q$, -- все равно можно было бы задать биекцию между ними и множеством $\{\Delta_1, \Delta_2, \ldots \Delta_{n-1}, \Delta_n \ldots\}$, но тогда обнаружение точки $c$ не служило бы доказательством."

-- 12.09.2023, 15:46 --

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

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

По-моему, он предполагался не произвольным (если не говорить о порядке следования последовательностей), а полным, то есть предполагалось, что он содержит все возможные последовательности.

[mihaild]

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

По-моему, он предполагался не произвольным (если не говорить о порядке следования последовательностей), а полным, то есть предполагалось, что он содержит все возможные последовательности

Это действительно стандартный способ изложения доказательства Кантора, но, ИМХО, неудачный (и вроде бы оригинальный был лучше) - предположение "список полон" никак на самом деле не используется. Мы можем доказать, что любой список неполон, напрямую (для любого списка предъявив элемент не из него) - из этого уже следует, что нет полного списка.

(Оффтоп)

И вроде бы даже есть варианты логики, принимающие рассуждение "любой $x$ суть не-$X$, следовательно, не существует $x$ суть $X$", но не принимающие "(если $x$ суть $X$, то противоречие), следовательно, не существует $x$ суть $X$". Но не уверен, что такое правда существует, и уверен, что оно Вам не надо.

[Vladimir Pliassov]

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

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

Мне представляется, что, например, когда речь идет о натуральных числах, список натуральных чисел "$1, 2, 3 \ldots$" полный (если не считать нуля), в том смысле, что если для бесконечного множества задан алгоритм нахождения каждого из его элементов, то этот алгоритм заменяет их полный список.

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

Это действительно стандартный способ изложения доказательства Кантора, но, ИМХО, неудачный (и вроде бы оригинальный был лучше)

А где можно познакомиться с оригинальным?

А еще я не могу найти доказательство несчетности отрезка (которое уже разбиралось на форуме), в котором показано, что для произвольной последовательности в отрезке найдется точка, не являющаяся членом этой последовательности.

[mihaild]

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

А где можно познакомиться с оригинальным?

"Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen", легко находятся переводы на английский. Там как раз доказывается что для любой последовательности вещественных чисел есть вещественное число, ей не принадлежащее. Про мощность отрезка ничего в явном виде не говорится.
Но это всё представляет только исторический интерес.

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

А еще я не могу найти доказательство несчетности отрезка (которое уже разбиралось на форуме), в котором показано, что для произвольной последовательности в отрезке найдется точка, не являющаяся членом этой последовательности

Так процитированное Вами в первом посте этой теме рассуждение это и доказывает.

[Vladimir Pliassov]

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

"Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen", легко находятся переводы на английский.

Спасибо!

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

Так процитированное Вами в первом посте этой теме рассуждение это и доказывает.

Нет, там другое доказательство, и мы с Вами его уже обсуждали, попытаюсь его найти.

[iifat]

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

Действуя методом от противного

Что-то у меня от ваших рассуждений крепнет чувчтво, что вы как-то не понимаете метод доказательства от противного, извините.
Доказательство от противного — это: берём отрицание доказываемого утверждения; приходим к противоречию. Точка.
Действуя этим методом, Кантор:
а) предполагая противное, предполагает, что таки есть нумерация действительных чисел отрезка, сиречь биекция промежду точками отрезка и натуральными числами (не задаёт он никаких туманных биекций, а только берёт предполагаемую — любую! — биекцию);
б) по предполагаемой биекции строит систему отрезков;
в) по принципу вложенных отрезков — найдётся точка, не входящая в нумерацию. На этом всё. Ибо пришли к противоречию.
На кой вам ваши туманные и неряшливые рассуждения — не понимаю.

[Vladimir Pliassov]

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

"Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen", легко находятся переводы на английский.

Я думаю, я нашел перевод: https://en.wikipedia.org/wiki/Cantor%27 ... ty_theorem, вот его перевод на русский:

Цитата:

Для любой последовательности действительных чисел $x_1, x_2, x_3, \ldots$ и любого отрезка $[a, b]$ существует число в $[a, b]$, которое не содержится в данной последовательности.

Чтобы найти число в $[a, b]$, которое не содержится в данной последовательности, постройте две последовательности действительных чисел следующим образом: Найдите первые два числа данной последовательности, которые находятся в открытом промежутке $(a, b)$.

Обозначим меньшее из этих двух чисел $a_1$, а большее - $b_1$. Подобным же образом найдите первые два числа заданной последовательности, которые находятся в $(a_1, b_1)$. Обозначим меньшее через $a_2$, а большее через $b_2$. Продолжение этой процедуры генерирует последовательность интервалов $(a_1, b_1), \; (a_2, b_2), \; (a_3, b_3), \; \ldots\; ,$ такую, что каждый интервал в последовательности содержит все последующие интервалы, то есть генерирует последовательность вложенных интервалов. Это означает, что последовательность $a_1, a_2, a_3, \ldots$ возрастает, а последовательность $b_1, b_2, b_3, \ldots$ убывает.

Либо количество сгенерированных интервалов конечно, либо бесконечно. Если конечно, пусть $(a_L, b_L)$ будет последним интервалом. Если бесконечно, возьмем пределы $a_\infty=\lim_{n\to \infty} a_n$ и $b_\infty = \lim_{n\to \infty} b_n$. Поскольку $a_n<b_n$ для всех $n$, либо $a_\infty = b_\infty$, либо $a_\infty < b_\infty$. Таким образом, следует рассмотреть три случая:

Случай 1: есть последний интервал $(a_L, b_L)$. Поскольку в этом интервале может быть не более одного $x_n$, каждый $y$ в этом интервале, кроме $x_n$ (если он существует), не содержится в данной последовательности.

Случай 2: $a_\infty = b_\infty$. Тогда $a_\infty$ не содержится в данной последовательности, поскольку для всех $n$: $a_\infty$ принадлежит интервалу $(a_n, b_n)$, но $x_n$ не принадлежит $(a_n, b_n)$. В символах: $a_\infty\in (a_n, b_n)$ , но $x_n\notin (a_n, b_n)$.

Случай 3: $a_\infty < b_\infty$. Тогда каждый $y$ из $[a_\infty, b_\infty]$ не содержится в данной последовательности, поскольку для всех $n$: $y$ принадлежит $(a_n, b_n)$, а $x_n$ нет.

Доказательство завершено, поскольку во всех случаях было найдено хотя бы одно действительное число в $[a, b]$ которое не содержится в данной последовательности.

Я сделал его сам, надеюсь, что в нем нет ошибок. Эту же статью, как я узнал позже, можно найти здесь:

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

Георг Кантор. Труды по теории множеств. Москва, "Наука", 1985. Вторая статья в этом сборнике.

Вторая теорема отсюда эта та самая, которую я имел в виду и которую мы с Вами уже обсуждали.

В этом доказательстве, по-моему, неудачные обозначения (например, в cлучае 2 индексы при $a$ и $x$ записаны одной и той же буквой $n$, при том что $a_1, a_2, a_3, \ldots$ является подпоследовательностью $x_1, x_2, x_3, \ldots \; ,$ чаще всего не совпадая с ней), но если разобраться, то становится ясно следующее.

В случае 2 из последовательности $x_1, x_2, x_3, \ldots$ выделяются подпоследовательности $a_1, a_2, a_3, \ldots$ и $b_1, b_2, b_3, \ldots \; ,$ которые обе сходятся к точке $a_\infty = b_\infty$, не достигая ее, и которые можно объединить в последовательность $c_1, c_2, c_3, \ldots \; ,$ такую, что если $c_k$ находится слева от $a_\infty = b_\infty$, то $c_{k+1}$ находится от нее справа. Точку $a_\infty = b_\infty$ можно обозначить $c_\infty$. Таким образом, из последовательности $x_1, x_2, x_3, \ldots$ выделяется подпоследовательность $c_1, c_2, c_3, \ldots \; ,$ которая сходится к пределу $c_\infty$, который для нее, а значит, и для всей последовательности $x_1, x_2, x_3, \ldots$ недостижим, то есть не содержится в ней.

Если разобраться со случаем 2, то случай 3 понимаются довольно легко, а случай 1 и сам по себе не трудный.

iifat в сообщении #1608977 писал(а):

На кой вам ваши туманные и неряшливые рассуждения — не понимаю.

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

iifat в сообщении #1608977 писал(а):

Доказательство от противного — это: берём отрицание доказываемого утверждения; приходим к противоречию. Точка.
Действуя этим методом, Кантор:
а) предполагая противное, предполагает, что таки есть нумерация действительных чисел отрезка, сиречь биекция промежду точками отрезка и натуральными числами (не задаёт он никаких туманных биекций, а только берёт предполагаемую — любую! — биекцию);

Вот то, что он берет предполагаемую биекцию между точками отрезка и натуральными числами, и есть то самое, что мне не очень понятно, потому что я ведь знаю, что этой биекции не может быть. Поэтому я, пытаясь как-то это представить, говорю, что Кантор задает биекцию между счетным множеством $\{\Delta_1, \Delta_2, \ldots \Delta_{n-1}, \Delta_n \ldots\}$ и счетным множеством $Q=\{x_1, x_2, \; \ldots, \; x_n, \; \ldots\}$, которое является заменой $[0, 1]$. Согласен, что это не ясное высказывание, но и то, что несчетное множество предполагается счетным, мне тоже не очень ясно.

Хотя если исходить из того, что неизвестно, счетно множество $[0, 1]$ или нет, то становится яснее.

[mihaild]

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

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

Если внимательно посмотреть на даже Ваш перевод (я не вчитывался, мог какие-то ошибки пропустить, но в целом похоже на правду), то видно, что предположения "пронумерованы все точки отрезка" вообще нет, и оно не нужно.

Но в целом конструкция "чтобы доказать, что что-то не существует, предположим, что существует, и придем к противоречию" крайне распространена. Например стандартное доказательство иррациональности корня из двух: пусть рационален, тогда его можно записать как $p / q$, и дальше всем известно.
Общая схема - хотим доказать, что для любого $x$ выполнено $P(x)$ - например "$x$ не является биекцией между натуральными числами и отрезком" или "$x$ не является рациональным числом, квадрат которого равен двум". Предполагаем противное: пусть существует $x_0$, для которого не выполнено $P(x_0)$. Если дальнейшие рассуждения приводят к противоречию (например к тому что таки выполнено $P(x_0)$, или там что $0 = 1$), то значит предположение было неверным.
Есть теорема, что метод доказательства от противного не дает ничего нового: а именно, если приняв предположение $A$ можно доказать $\bot$ (противоречие), то можно без принятия всяких предположений доказать, что $A \rightarrow \bot$, что эквивалентно $\neg A$. Но на практике он часто оказывается гораздо более удобным.

[iifat]

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

потому что я ведь знаю, что этой биекции не может быть

Вы знаете то, что провозгласили аксиомой, либо то, что сумели доказать. Пока нет ни того, ни другого — вы не знаете ничего.

[Vladimir Pliassov]

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

Если внимательно посмотреть на даже Ваш перевод (я не вчитывался, мог какие-то ошибки пропустить, но в целом похоже на правду), то видно, что предположения "пронумерованы все точки отрезка" вообще нет, и оно не нужно.

Это другое доказательство: Вы сейчас имеете в виду доказательство из "Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen", а я, говоря о предположении "пронумерованы все точки отрезка", имел в виду доказательство из первого поста настоящей темы.

iifat в сообщении #1609000 писал(а):

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

потому что я ведь знаю, что этой биекции не может быть

Вы знаете то, что провозгласили аксиомой, либо то, что сумели доказать. Пока нет ни того, ни другого — вы не знаете ничего.

Здесь вопрос скорее не математический, психологический: я имел в виду, что я довольно много читал несчетности отрезка $[0, 1]$, и поэтому мне не так легко предположить, что он счетен.

[epros]

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

я довольно много читал несчетности отрезка $[0, 1]$, и поэтому мне не так легко предположить, что он счетен.

Если речь о рациональном отрезке, то непонятно, почему это "не так легко". На самом деле определить последовательность всех рациональных точек от 0 до 1 можно очень легко и в явном виде.

[Vladimir Pliassov]

epros в сообщении #1609011 писал(а):

Если речь о рациональном отрезке, то непонятно, почему это "не так легко". На самом деле определить последовательность всех рациональных точек от 0 до 1 можно очень легко и в явном виде.

Да, конечно, "змейкой"? Но здесь речь о вещественном отрезке $[0, 1]$. Однако тут надо, по-моему, руководствоваться принципом:

iifat в сообщении #1609000 писал(а):

Вы знаете то, что провозгласили аксиомой, либо то, что сумели доказать. Пока нет ни того, ни другого — вы не знаете ничего.

То есть надо исходить из того, что не знаешь, счетен он или нет, тогда есть две возможности: что он счетен и что он несчетен. Проверим первую возможность: раз он счетен, то его элементы можно перенумеровать: $x_1, x_2, \; \ldots, \; x_n, \; \ldots \; .$ и так далее.

[Vladimir Pliassov]

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

На самом деле метод от противного тут не особо нужен (ну разве что все доказательства несуществования считать доказательством от противного).

А как можно переделать это доказательство:

Цитата:

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

↓Предположим, что множество точек $[0,1]$ счетно: $x_1, x_2, \; \ldots, \; x_n, \; \ldots \; .$ Разделим отрезок $[0,1]$ на $3$ равные части: $[0, \frac {1}{3}]; [\frac {1}{3}; \frac {2}{3}]; [\frac {2}{3}; 1]$, и выберем тот из отрезков, который не содержит $x_1$ ни внутри, ни на границе. Обозначим его через $\Delta_1$, т.е. $x_1$ не принадлежит $\Delta_1$. $\Delta_1$ также поделим на $3$ равные части и выберем ту часть, которая не содержит $x_2$ ни внутри, ни на границе. Обозначим эту часть $\Delta_2$, т.е. $x_2$ не принадлежит $\Delta_ 2$, и $\Delta_2\subset \Delta _1$. Продолжая эту процедуру, мы получим последовательность вложенных друг в друга отрезков $\Delta_1\supset \Delta_2\supset \ldots\supset \Delta_{n-1}\supset \Delta_n\supset \ldots \; .$ Причем длины этих отрезков стремятся к нулю и $\forall n \; x_n\notin \Delta_n$. В силу принципа вложенных отрезков существует точка $c\in \Delta_n$ для $\forall n$, причем $c\ne x_n \; \forall n$. А следовательно, точка $c$ в исходном списке точек отрезка отсутствует, т.е. точка $c$ оказалась незанумерованной. Это противоречие доказывает теорему. ↑

так, чтобы получилось доказательство не от противного?

[Vladimir Pliassov]

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

Цитата:

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

↓Предположим, что множество точек $[0,1]$ счетно: $x_1, x_2, \; \ldots, \; x_n, \; \ldots \; .$ Разделим отрезок $[0,1]$ на $3$ равные части: $[0, \frac {1}{3}]; [\frac {1}{3}; \frac {2}{3}]; [\frac {2}{3}; 1]$, и выберем тот из отрезков, который не содержит $x_1$ ни внутри, ни на границе. Обозначим его через $\Delta_1$, т.е. $x_1$ не принадлежит $\Delta_1$. $\Delta_1$ также поделим на $3$ равные части и выберем ту часть, которая не содержит $x_2$ ни внутри, ни на границе. Обозначим эту часть $\Delta_2$, т.е. $x_2$ не принадлежит $\Delta_ 2$, и $\Delta_2\subset \Delta _1$. Продолжая эту процедуру, мы получим последовательность вложенных друг в друга отрезков $\Delta_1\supset \Delta_2\supset \ldots\supset \Delta_{n-1}\supset \Delta_n\supset \ldots \; .$ Причем длины этих отрезков стремятся к нулю и $\forall n \; x_n\notin \Delta_n$. В силу принципа вложенных отрезков существует точка $c\in \Delta_n$ для $\forall n$, причем $c\ne x_n \; \forall n$. А следовательно, точка $c$ в исходном списке точек отрезка отсутствует, т.е. точка $c$ оказалась незанумерованной. Это противоречие доказывает теорему. ↑

Еще одна попытка доказательства.

$\rhd$ Возьмем произвольное счетное подмножество $P=\{x_1, x_2, x_3 \ldots\}$ множества всех точек отрезка $[0, 1]$. На отрезке $[0, 1]$ построим счетную систему $S=\Delta_1\supset \Delta_2\supset \ldots\supset \Delta_{n-1}\supset \Delta_n\supset \ldots $ вложенных друг в друга стягивающихся к нулю отрезков, описанную в доказательстве Кантора (подчеркну, что, в отличие от этого доказательства, здесь $\{x_1, x_2, x_3 \ldots\}$ рассматривается как подмножество множества $[0, 1]$, но, исходя из $\{x_1, x_2, x_3 \ldots\}$, построение $S$ то же самое). При этом построении задается биекция $P\rightarrow S$, при которой каждая точка $x_i\in P$ отображается в отрезок $\Delta_i$, которому не принадлежит.

Множество $P$ не может быть равно $[0, 1]$, потому что, в силу принципа вложенных отрезков, существует точка $c\in \Delta_n$ для $\forall n$, и значит, $c\in [0, 1]$, и при этом $c\ne P$. Таким образом, $[0, 1]$ не является своим счетным подмножеством, то есть $[0, 1]$ несчетно. $\lhd$

Теперь получилось?