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

[Vladimir Pliassov]

В сообщении подвергается сомнению "диагональное" доказательство теоремы Кантора.

Цитата:

Теорема 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$

http://math-info.hse.ru/f/2014-15/CompL ... hestva.pdf стр. 26

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

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

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

Обозначим через $n$ число членов последовательностей. При $n=0$ последовательностей вообще нет, при $n=1$ имеем

$$\begin {matrix} 0\\ 1 \end {matrix} \eqno {(1)} $$

при $n=2$:

$$\begin {matrix} 0&0\\ 1&1\\ 0&1\\ 1&0 \end {matrix} \eqno {(2)} $$

при $n=3$:

$$\begin {matrix} 0&0&0\\ 1&1&1\\ 0&1&0\\ 1&0&0\\ 0&1&1\\ 1&0&1\\ 0&0&1\\ 1&1&0 \end {matrix} \eqno {(3)} $$

Мы видим, что уже при $n=1$ и $n=2$, то есть сразу же, матрица не квадратная: отношение числа ее строк к числу столбцов равно $2$, а при $n=3$ оно равно уже $8/3$, при $n=4$ -- $16/4$, при $n=5$ -- $32/5$, где $2<8/3<16/4<32/5$, то есть с ростом $n$ это отношение только растет, поскольку число всевозможных последовательностей здесь, то есть число строк матрицы, равно $2^n.$ (Для любого же конечного $a>2$, где $a$ -- число элементов, из которых строятся последовательности, с ростом $n$ отношение $a^n$ к $n$ только растет).

И я не вижу оснований полагать, что, условно говоря, при $n=\infty$ матрица вдруг станет квадратной. Скорее она при этом бесконечно вытянется по вертикали, то есть станет бесконечно неквадратной.

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

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

Это во всяком случае так для конечного $n$, для $n=1, 2, 3$ в этом можно убедиться на примере матриц (1), (2), (3).

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

Для справки:

Цитата:

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

$${\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\end{bmatrix},\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\0&0&0\end{bmatrix}}.$$

Википедия.

Или я что-то не так понимаю?

[mihaild]

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

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

Нет, не основывается. В нём вообще нет слова "квадратная" (и оно там не нужно). Да и таблица тут для красоты, главное - у нас есть функция $\mathbb N \to (\mathbb N \to \{0, 1\})$ - т.е. из натуральных чисел в последовательности.

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

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

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

[Dan B-Yallay]

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

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

Присоединяюсь к предыдущему ответу в части того, что в доказательстве нет слова "квадратная". Но если вам так уж хочется, то обращу внимание на факт, что у той "матрицы" ширина и высота равны друг другу. Если это не "квадратная", то какая тогда? ))

[Vladimir Pliassov]

Dan B-Yallay в сообщении #1526606 писал(а):

Но если вам так уж хочется, то обращу внимание на факт, что у той "матрицы" ширина и высота равны друг другу. Если это не "квадратная", то какая тогда? ))

Вы хотите сказать, что длина и ширина матрицы, о которой идет речь, равна бесконечности?

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

Цитата:

Составим бесконечную вниз таблицу

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

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

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

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

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

[Aritaborian]

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

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

В данном случае они одинаковой мощности. Ну а главное здесь, как уже указали, что для любого $n$ можно взять элемент $a_{nn}$, в этом и состоят квадратность с бесконечностью.

[mihaild]

Vladimir Pliassov, это какая-то дурная философия. "Составим бесконечную таблицу" - это просто чуть более красивый способ сказать "рассмотрим функцию двух натуральных аргументов".
Рассуждать о бесконечных множествах, конечно же, можно, почти вся математика в этом и состоит.

[Dan B-Yallay]

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

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

У вас есть какие-то сомнения в том, что натуральных чисел бесконечно много? Или сомнения в том, что возможно создать функцию из $\mathbb N $ в {0,1}?

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

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

А я говорю, что столбцов в той "матрице" -- счётное количество: тупо по определению бесконечных последовательностей нулей и единиц. А строчек счётное количество потому, что теорема Кантора как раз об этом.
Так что получается "квадратная"

[Ivan_B]

Мое пояснение может оказаться неверным.

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

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

Это доказательство от противного. Здесь посылка ложная. Предполагается, что можно построить такую "квадратную" "матрицу". Потом доказывается, что это ведет к противоречию, то есть нельзя такую "матрицу" построить.

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

И я не вижу оснований полагать, что, условно говоря, при $n=\infty$ матрица вдруг станет квадратной. Скорее она при этом бесконечно вытянется по вертикали, то есть станет бесконечно неквадратной.

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

[Dan B-Yallay]

Ivan_B в сообщении #1526628 писал(а):

Это доказательство от противного. Здесь посылка ложная. Предполагается, что можно построить такую "квадратную" "матрицу". Потом доказывается, что это ведет к противоречию, то есть нельзя такую "матрицу" построить.

Лень искать, но здесь, на форуме, неоднократно пояснялось старшими товарищами, что теорема Кантора не нуждается в аргументе "от противного". Доказательство идёт таким образом:

Пусть дан какой-либо перенумерованный список бесконечных последовательностей нулей и единиц. Покажем, что он "не полон", то есть существует такая последовательность нулей и единиц, которой нет в данном списке. И стрoится диагональ Кантора

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

[Aritaborian]

Aritaborian в сообщении #1526614 писал(а):

В данном случае они одинаковой мощности.

Я имею в виду — то, что мы строим. А так-то мы доказываем, что полная таблица по вертикали «бесконечнее», да.

[Vladimir Pliassov]

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

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

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

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

Мне кажется, что все же основывается. Слова "квадратная" действительно нет, но то, что матрица предполагается квадратной, следует из того, что исключается возможность для ее инвертированной диагонали быть равной одной из ее строк, это исключение возможно только если матрица квадратная. Если добавить еще хотя бы одну строку, не равную остальным строкам, она случайно может оказаться равной инвертированной диагонали.

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

Это для конечного $n$. Но автор доказательства (а это сам Кантор, не правда ли?) использует конечные принципы, оперируя с бесконечными вещами там, где эти конечные принципы, на мой взгляд, сомнительны. То есть он именно основывает свое доказательство на том, что матрица квадратная.

Прошу обратить внимание, что я выражаю сомнение не в самой теореме, а в ее диагональном доказательстве.

Хотя другого доказательства я пока что нигде не нашел, везде предлагают именно его. Нет ли какого-нибудь другого?

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

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

Правильно ли я понимаю: $\mathbb N \to \{0, 1\}$ это не обязательно всевозможные последовательности нулей и единиц, то есть не обязательно как бесконечные последовательности, так и последовательности всевозможных конечных длин (так что для каждого $n$ длина каждой последовательности равна $n$, а число последовательностей равно $2^n$, где $n\in \mathbb N$ и $n$ принимает всевозможные значения)? Ведь в доказательстве рассматриваются не последовательности всевозможных длин, а только последовательности одной и той же, причем бесконечной, длины. Наверное, для этой теоремы $\mathbb N \to \{0, 1\}$ надо определить точнее, то есть указать, что имеются в виду именно бесконечные последовательности? Но как это сделать? Написать, что $n=\infty$? Разве так делается?

Если уже определено, что имеются в виду бесконечные последовательности, то функция $\mathbb N \to (\mathbb N \to \{0, 1\})$, хотя и может быть инъективной, но сюръективной быть не может, так как число последовательностей слишком велико?

И именно это надо доказать. Но как? (Иначе, чем в приведенном доказательстве.)

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

Рассуждать о бесконечных множествах, конечно же, можно, почти вся математика в этом и состоит.

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

Dan B-Yallay в сообщении #1526622 писал(а):

У вас есть какие-то сомнения в том, что натуральных чисел бесконечно много? Или сомнения в том, что возможно создать функцию из $\mathbb N $ в {0,1}?

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

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

"Диагональное" доказательство Кантора, по-моему, такого рода. Поэтому я ищу другое, более убедительное.

Aritaborian в сообщении #1526614 писал(а):

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

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

В данном случае они одинаковой мощности.

Кто одинаковой мощности? Множество последовательностей и любая из последовательностей? Но разве последовательность повторяющихся элементов это множество? Или она может иметь мощность, несмотря на то, что не является множеством?

[mihaild]

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

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

Нет, диагонали привлекаются чисто для красоты, всё легко переписывается в чисто алгебраической форме и сразу для бесконечных последовательностей.

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

Правильно ли я понимаю: $\mathbb N \to \{0, 1\}$ это не обязательно всевозможные последовательности нулей и единиц

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

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

Но как это сделать? Написать, что $n=\infty$?

Не путайте $\mathbb N$ (множество натуральных чисел) и $n$ (переменная, обычно целочисленная).

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

И именно это надо доказать. Но как? (Иначе, чем в приведенном доказательстве.)

Не иначе, а просто более алгебраично.
У нас есть функция $a: \mathbb N \to (\mathbb N \to \{0, 1\})$, которая из натурального числа делает последовательность (которая тоже является функцией). Зададим последовательность $b$ формулой $b(n) = 1 - a(n)(n)$. Легко показывается, что $\forall k: a(k) \neq b$. Следовательно, $b$ не лежит в образе $a$, т.е. $a$ не является нумерацией всех возможных последовательностей.

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

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

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

[Vladimir Pliassov]

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

Зададим последовательность $b$ формулой $b(n) = 1 - a(n)(n)$

Здесь все правильно написано? Если правильно, то зачем еще одно $(n)$ при $a(n)$?

Если должно быть $b(n) = 1 - a(n)$, то $b(n) = 1 - a(n)$ означает, что каждый член последовательности $b(n)$ равен единице минус соответствующий член последовательности $a(n)$?

$a(n)$ это последовательность номер $n$ (из всех последовательностей, которые являются значениями функции $a(n)$)?

[Mikhail_K]

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

Если должно быть $b(n) = 1 - a(n)$

Ну как же так должно быть, если Вы сами пишете

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

$a(n)$ это последовательность номер $n$

Как из числа $1$ можно вычесть последовательность?

Здесь $a$ - это функция из $\mathbb{N}$ в множество функций из $\mathbb{N}$ в $\{0,1\}$.
Для любого $n\in\mathbb{N}$, $a(n)$ есть значение функции $a$ при аргументе $n$, поэтому $a(n)$ есть функция из $\mathbb{N}$ в $\{0,1\}$ (которую мы представляем себе как $n$-ю последовательность), а $a(n)(n)$ есть значение функции $a(n)$ при аргументе $n$, поэтому $a(n)(n)\in\{0,1\}$ (это $n$-й элемент $n$-й последовательности).

[Vladimir Pliassov]

Спасибо! Кажется, понял.