"Диагональное" доказательство теоремы Кантора

[mihaild]

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

если взять Вашу последовательность [...] то это не поможет нам доказать несчетности множества точек отрезка

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

[Vladimir Pliassov]

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

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

Я подумал, что эта точка -- именно предельная точка последовательности. Теперь вижу, в чем недоразумение: это не та точка.

Но почему Вы здесь говорите: "произвольная последовательность точек отрезка"? У Кантора просто "произвольная последовательность", это, наверное, предпочтительнее, потому что принцип более общий?

Да и Вы сами только что написали:

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

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

[mihaild]

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

Теперь вижу, в чем недоразумение: это не та точка

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

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

У Кантора просто "произвольная последовательность", это, наверное, предпочтительнее, потому что принцип более общий?

Одно и то же - точки из последовательности, не принадлежащие отрезку, ни на что не влияют.

[Vladimir Pliassov]

Хорошо, что недоразумение разъяснилось. Спасибо большое!

[Vladimir Pliassov]

Кажется, я начинаю признавать "диагональное" доказательство.

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

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

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

Нет, не основывается. В нём вообще нет слова "квадратная"

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

но у этой матрицы просто нет диагонали -- такой, какая есть у квадратной матрицы, то есть такой, которая идет от верхнего левого элемента к нижнему правому

Диагональю в данном случае называются именно элементы $a_{11}$, $a_{22}$ и т.д. Никакого нижнего правого элемента нет.

В этом сообщении имеется два важных момента: первый -- что матрица не предполагается квадратной, -- и второй -- что диагональю считается не множество элементов матрицы, идущих от левого верхнего элемента к правому нижнему (что возможно только для квадратной матрицы), а "$a_{11}$, $a_{22}$ и т.д. ", то есть главная диагональ прямоугольной (неквадратной) матрицы.

Таким образом, во-первых, диагональ есть, и во-вторых, ни при каком конечном $n$ диагональ матрицы не может быть равна какой-либо ее строке.

Другими словами, для произвольной последовательности $S$ бесконечных последовательностей нулей и единиц найдется такая бесконечная последовательность нулей и единиц, которой нет в $S$.

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

для произвольной последовательности $S$ бесконечных последовательностей нулей и единиц

(для произвольной последовательности $S$ точек отрезка)

найдется такая бесконечная последовательность нулей и единиц, которой нет в $S$,

(найдется такая точка отрезка, которой нет в $S$).

2.

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

Но, к счастью, в этом нет необходимости, достаточно выписать всего лишь $n$ первых членов каждой из $n$ первых последовательностей, что и сделано в доказательстве:

Цитата:

$$\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} $$

потому что, если начала последовательностей разные, то и последовательности разные.

И то, что последовательность, равная диагонали, отличается от последовательности, равной любой из первых $n$ строк, видно при любом $n>1$.

(При этом, разумеется, исключается матрица, все строки которой равны.)

[Someone]

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

Из несчетности всех точек отрезка следует несчетность всех бесконечных последовательностей нулей и единиц

Доказательство теоремы про последовательности технически проще доказательства теоремы про числа.

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

потому что, если начала последовательностей разные, то и последовательности разные.

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

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

При этом, разумеется, исключается матрица, все строки которой равны.

Зачем нужно её исключать?

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

[maximav]

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

В этом сообщении имеется два важных момента: первый -- что матрица не предполагается квадратной

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

1. Взаимно-однозначное соответствие

2. Бесконечность (теоретико-множественная ... создана в ZFC)

Рассуждения с использованием п.1 про все, что задействует п.2 и его разновидности, осуществляются по нашему human being умолчанию (это можно обсуждать, но это другой вопрос). Язык рассуждений про всякие бесконечности с использованием тех же средств (равномощность и т.д.), что прилагались к конечному. "Конечное" у нас - тоже элемент первичного языка. Языка, который есть еще до математики и мат логики. Поэтому в канторовском доказательстве нельзя увеличивать, как вы делаете в своих постах, количество используемых слов/сущностей, а жестко оперировать только тем, что разрешает ZFC и мат логика. Чем меньше, тем лучше. Этому надо заставить себя. Тогда ваши многие вопросы сами по себе отпадут. Вы начинаете/пытаетесь строить некоторый новый бесконечный объект, но не получается ... не совпадают его элементы. Возможность построить уходит вся целиком в астральную бесконечность. Все. Невозможность построить - это и есть несуществование и конец доказательства.

(Оффтоп)

Забыл добавить к давнему. То, что музыкант (https://www.youtube.com/watch?v=DYRwkUET9ZM) занимается мат-логикой, можно только поприветствовать.

[Vladimir Pliassov]

1.

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

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

Из несчетности всех точек отрезка следует несчетность всех бесконечных последовательностей нулей и единиц

Доказательство теоремы про последовательности технически проще доказательства теоремы про числа.

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

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

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

потому что, если начала последовательностей разные, то и последовательности разные.

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

Последовательность, равная инвертированной диагонали, и последовательность, равная произвольной строке, при любом $n$ разные.

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

[Таким образом, рассматриваемая в доказательстве последовательность всех бесконечных последовательностей нулей и единиц (то есть последовательность строк матрицы) является не произвольной, а такой, в которой нет повторяющихся членов.]

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

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

При этом, разумеется, исключается матрица, все строки которой равны.

Зачем нужно её исключать?

Здесь, если рассматривать саму по себе квадратную матрицу, то есть безотносительно к доказательству, я неправильно сказал: я забыл, что строкам должна быть не равна не диагональ, а инвертированная диагональ. Я забыл об этом также, когда писал два следующих предложения:

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

Таким образом, во-первых, диагональ есть, и во-вторых, ни при каком конечном $n$ диагональ матрицы не может быть равна какой-либо ее строке.

(Должно быть: "ни при каком конечном $n$ инвертированная диагональ матрицы не может быть равна какой-либо ее строке.")

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

И то, что последовательность, равная диагонали, отличается от последовательности, равной любой из первых $n$ строк, видно при любом $n>1$.

(Должно быть: "последовательность, равная инвертированной диагонали".)

(Но, как сказано, матрица, все строки которой равны, исключается по ходу доказательства.)

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

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

Если матрица берется при произвольном конечном $n$, то ее можно не брать в кавычки, а бесконечного $n$ не существует.

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

Убедительнее это будет, если не пытаться предполагать, что $n$ может быть бесконечным: если предполагать, что $n$ может быть только конечным, то и матрица будет конечной (и вполне понятной).

Правда, при этом взгляд на матрицу в доказательстве и само доказательство надо несколько изменить.

Вместо

Цитата:

Составим бесконечную вниз таблицу, строками которой будут наши последовательности:

$$\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} $$

скажем: составим матрицу, строками которой будут начала $n$ бесконечных последовательностей нулей и единиц -- по $n$ первых членов каждой из этих последовательностей в каждой строке:

$$\begin {matrix} \alpha_1=&\alpha_{11}&\alpha_{12}&\ldots&\alpha_{1n}\\ \alpha_2=&\alpha_{21}&\alpha_{22}&\ldots&\alpha_{2n}\\ \hdotsfor [1.5] {5} \\ \alpha_n=&\alpha_{n 1}&\alpha_{n 2}&\ldots&\alpha_{nn} \end {matrix} $$

Для любого конечного $n>1$ инвертированная диагональ матрицы не равна ни одной из строк,

при этом ни одна из последовательностей, получающихся при дописывании остальных членов к первым $n$ элементам инвертированной диагонали, не будет равна ни одной из последовательностей, получающихся при дописывании остальных членов к первым $n$ элементам произвольной строки, потому что, если начала последовательностей разные, то и последовательности разные.

2.

Кстати, то, что произвольная последовательность бесконечных последовательностей нулей и единиц может состоять из одинаковых последовательностей, не противоречит утверждению: "для произвольной последовательности $S$ бесконечных последовательностей нулей и единиц найдется такая бесконечная последовательность нулей и единиц, которой нет в $S$", так что аналогия, о которой я говорил, справедлива.

3.

maximav в сообщении #1527998 писал(а):

в канторовском доказательстве нельзя увеличивать, как вы делаете в своих постах, количество используемых слов/сущностей, а жестко оперировать только тем, что разрешает ZFC и мат логика. Чем меньше, тем лучше.

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

maximav в сообщении #1527998 писал(а):

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

Мне кажется (но, может быть, я опять ошибаюсь), что мне удалось найти доказательство (оно немного выше в этом сообщении) без привлечения астральной бесконечности, по крайней мере, по отношению к матрице. То есть я не пытался построить бесконечный объект, я построил конечный объект -- матрицу порядка $n$. Затем я, конечно, апеллировал к бесконечности, но только в том отношении, что за началом бесконечной последовательности следует ее хвост, который -- да -- теряется в бесконечности, но это бесконечность такого свойства, что всегда можно добавить еще один член к тем, которые уже есть (в конечном числе), такую бесконечность я признаю, хотя и не понимаю, как она возможна. А бесконечность, когда $n=\infty$ -- такую бесконечность Вы называете астральной? -- я не признаю.

(Оффтоп)

Цитата:

Забыл добавить к давнему. То, что музыкант (https://www.youtube.com/watch?v=DYRwkUET9ZM) занимается мат-логикой, можно только поприветствовать.

Спасибо!

[Vladimir Pliassov]

Может возникнуть вопрос [и я задавал этот вопрос, когда понимал меньше, чем теперь (как мне кажется)]: почему при каждом конечном $n$ мы вносим в список не все $2^n$, а только $n$ последовательностей? (Если бы можно было вносить в список все $2^n$ последовательностей, то среди них оказалась бы и инвертированная диагональ.) Ответ на этот вопрос заключается в следующем предложении:

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

у нас есть функция $\mathbb N \to (\mathbb N \to \{0, 1\})$ - т.е. из натуральных чисел в последовательности.

Какова область определения этой функции? $\mathbb N,$ потому что при каждом конечном $n$ каждому натуральному числу от $1$ до $n$ ставится в соответствие одна последовательность.

А если бы при каждом конечном $n$ в список вносились все $2^n$ последовательностей, то последовательности ставились бы в соответствие не $n$, а $2^n$ натуральным числам, и область определения функции была бы не $\mathbb N$, а $2^\mathbb N$, то есть это была бы другая функция: не $\mathbb N \to (\mathbb N \to \{0, 1\})$, а $2^\mathbb N \to (\mathbb N \to \{0, 1\})$.

Последняя функция является биекцией, в противоположность первой.

[Someone]

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

Убедительнее это будет, если не пытаться предполагать, что $n$ может быть бесконечным

Кто это предполагал, кроме Вас?

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

если предполагать, что $n$ может быть только конечным, то и матрица будет конечной (и вполне понятной).

Правда, при этом взгляд на матрицу в доказательстве и само доказательство надо несколько изменить.

Вместо …
скажем: составим матрицу, строками которой будут начала $n$ бесконечных последовательностей нулей и единиц -- по $n$ первых членов каждой из этих последовательностей в каждой строке: …

Увы, как ни старались объяснить — не доходит. Забудьте, наконец, про эту матрицу. Нет её. Есть последовательность последовательностей.

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

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

А без дурной псевдофилософии обойтись никак нельзя? "Астральная бесконечность" — это исключительно ваше изобретение, а Кантор обходился просто натуральным рядом.

[Vladimir Pliassov]

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

Забудьте, наконец, про эту матрицу. Нет её. Есть последовательность последовательностей.

Вот доказательство без привлечения матрицы.

Пусть нам дана функция $f\colon \mathbb N \to $\{0, 1\}^\mathbb N$$ (из множества натуральных чисел в множество всевозможных бесконечных последовательностей нулей и единиц). Надо доказать, что эта функция не является биективной.

$\rhd$ Пусть функция $f$ будет определена таким образом, что при при каждом $n$ ее cужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ на подмножество $\{1, 2, \ldots, n\}$ будет отображать $\{1, 2, \ldots, n\}$ в подмножество $B_n$ множества $\{0, 1\}^\mathbb N$, состоящее из бесконечных последовательностей нулей и единиц, имеющих разные начала из $n$ членов и одно и то же продолжение.

Тогда $B_n$ будет состоять из $2^n$ элементов, тогда как $\{1, 2, \ldots, n\}$ состоит из $n$ элементов, откуда следует, что отображение из $\{1, 2, \ldots, n\}$ в $B_n$ не может быть биективным.

Поскольку ни при каком $n$ сужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ не является биективным, то и вся функция $f$ не является биективной. $\lhd$

(Не знаю, надо ли доказывать последнее предложение.)

Но это не "диагональное " доказательство.

[mihaild]

Это вообще не доказательство. Нельзя просто так вводить произвольные ограничения - например

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

при при каждом $n$ ее cужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ на подмножество $\{1, 2, \ldots, n\}$ будет отображать $\{1, 2, \ldots, n\}$ в подмножество $B_n$ множества $\{0, 1\}^\mathbb N$, состоящее из бесконечных последовательностей нулей и единиц, имеющих разные начала из $n$ членов и одно и то же продолжение

Если мы хотим доказать что-то про произвольную функцию, то говорить "а пусть функция такая" нельзя.

[Vladimir Pliassov]

Во всяком случае, при любом $n$ cужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ отображает $\{1, 2, \ldots, n\}$ в некоторое подмножество $B_n$ множества $\{0, 1\}^\mathbb N$, состоящее из $2^n$ элементов (из $2^n$ бесконечных последовательностей), это ведь так?

[mihaild]

Нет, сужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ - это функция из $\{1, \ldots, n\}$ в $\{0, 1\}^\mathbb N$. Образ её, естественно, состоит не более чем из $n$ элементов.
Я, кажется, догадываюсь, что вы хотите сделать: заметить, что ни при каком $n$ мы не получим, что первые $n$ последовательностей имеют все возможные начала длины $n$, и из этого вывести, что функция не биекция. Это рассуждение, скорее всего, обречено на провал. Любое доказательство несчетности множества последовательностей должно содержать переход, который разваливается, если мы вместо множества всех последовательностей рассмотрим множество всех последовательностей, содержащих конечное число единиц (в диагональном доказательстве - построенная последовательность может содержать бесконечное число единиц, в рассуждении с отрезками - для двоично-рациональных чисел принцип вложенных отрезков не выполнен).

[Vladimir Pliassov]

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

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

Но у меня $\{1, 2, \ldots, n\}$ отображается в подмножество $B_n$, состоящее из бесконечных последовательностей нулей и единиц (при этом число этих бесконечных последовательностей в $B_n$ конечно, оно равно $2^n$).