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

[iifat]

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

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

(О вреде иллюстраций, призванных пояснить сложные рассуждения) Вас таки заклинило на этих матрицах. Нет в диагональном доказательстве никаких матриц. Это иллюстрация, которая показалась кому-то помогающей понять доказательство (мне тоже кажется), но вы упорно зацикливаетесь на слове «матрица», которых — без кавычек — в доказательстве отсутствует, поскольку матрицы конечны.
Есть функция $f:\mathbb N\to 2^{\mathbb N}$; есть бесконечная последовательность, которая строится по известному вам закону; она не может быть образом никакого числа в силу способа построения. Всё. Никаких матриц, никаких диагоналей, никаких, простите, глупых и непонятных $B_n$ (что такое у вас $B_n$? Сужение функции на отрезке отображает отрезок на множество из $n$ элементов. Если вы хотите, чтобы оно отображало отрезок в множество из $2^n$ элементов, вам надо определить эти $2^n-n$ элементов, помимо $n$ значений $f(i)$!)

[xagiwo]

(может, если ещё раз просто подробно выписать доказательство, ТС поймёт?)

Возьмём любую (не обязательно биекцию, вообще никаких ограничений) функцию $f: \mathbb{N} \to 2^\mathbb{N}$ (то есть $f$ "берёт" натуральные числа и возвращает бесконечные последовательности нулей и единиц).
Пусть $f(1) = (a_1, a_2, a_3, …)$; $f(2) = (b_1, b_2, b_3, …)$; $f(3) = (c_1, c_2, c_3, …)$ итд. Тогда последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ не совпадает ни с одной из последовательностей $f(1), f(2), f(3), …$ (почему?). А значит, функция $f$ не является биекцией между $\mathbb{N}$ и $2^\mathbb{N}$, т. к. как минимум один из элементов $2^\mathbb{N}$ она не возвращает. И раз уж для любой функции верно, что она — не биекция, то биекции не существует. А для счётности нужна биекция. Слов "таблица" сказано: 0.

И всё таки не матрица, а таблица, матрица по определению конечна

[xagiwo]

Ии на всякий случай: $2^\mathbb{N}$ не означает возведения в степень, это только обозначение такое.

Vladimir Pliassov, Вы думаете, что раз количество элементов в $\mathbb{N}$ бесконечно, то можно для какого-то "бесконечного числа" $n$ записать "кол-во эл-тов в $\mathbb{N} = n$" и, соответственно, "кол-во эл-тов в $2^\mathbb{N} = 2^n$"? Это не так, потому что нигде не дано определения "бесконечных чисел" и операций над ними. У натуральных чисел есть строгое определение, у множества натуральных чисел — тоже, и у понятия равномощности тоже. Работайте с понятиями, которым дано строгое определение, а не с "бесконечными $n$"

[mihaild]

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

Но у меня $\{1, 2, \ldots, n\}$ отображается в подмножество $B_n$

Что такое $B_n$?

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

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

Я тоже говорил о бесконечных последовательностях, но содержащих лишь конечное число единиц.

[Vladimir Pliassov]

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

но вы упорно зацикливаетесь на слове «матрица»

Мне странно, что Вы это говорите: в моей попытке доказательства нет слова "матрица" (так же как и слова "диагональ").

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

Есть функция $f:\mathbb N\to 2^{\mathbb N}$; есть бесконечная последовательность, которая строится по известному вам закону; она не может быть образом никакого числа в силу способа построения.

Здесь я не понимаю. Если Вы имеете в виду одну из бесконечных последовательностей нулей и единиц в отношении функции $f:\mathbb N\to 2^{\mathbb N}$, то всякая такая последовательность как раз может быть образом некоторого натурального числа в силу этой функции (какие из этих последовательностей являются образами, а какие нет, зависит от определения функции). Но если Вы имеете в виду построение последовательности, то да, при построении последовательности в нее не отображается никакое число, при ее построении натуральные числа отображаются не в нее, а в множество $\{0, 1\}$, но я и не говорю, что при построении последовательности в нее отображается какое-то число.

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

(что такое у вас $B_n$?

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

Что такое $B_n$?

$B_n$ это конечное подмножество множества $\{0, 1\}^\mathbb N$, состоящее из $2^n$ бесконечных последовательностей нулей и единиц, имеющих разные начала из $n$ членов и одно и то же продолжение. Чтобы получить его при $n=3$ возьмем множество $\{0, 1\}^3$ всевозможных конечных последовательностей нулей и единиц длины $3$:

$$\{0, 1\}^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)} $$

и к каждой последовательности (условно говоря) припишем одно и то же бесконечное продолжение $b_3=\beta_1, \beta_2, \ldots$ (где $\beta_1, \beta_2$ могут быть равны либо $0$, либо $1$), получим восемь бесконечных последовательностей, составляющих множество $B_3$:

$$B_3=\begin {matrix} 0&0&0&\beta_1& \beta_2&\ldots\\ 1&1&1&\beta_1& \beta_2&\ldots\\ 0&1&0&\beta_1& \beta_2&\ldots\\ 1&0&0&\beta_1& \beta_2&\ldots\\ 0&1&1&\beta_1& \beta_2&\ldots\\ 1&0&1&\beta_1& \beta_2&\ldots\\ 0&0&1&\beta_1& \beta_2&\ldots\\ 1&1&0&\beta_1& \beta_2&\ldots \end {matrix} \eqno {(4)} $$

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

Пусть нам дана функция $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$

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

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

Сужение функции на отрезке отображает отрезок на множество из $n$ элементов. Если вы хотите, чтобы оно отображало отрезок в множество из $2^n$ элементов, вам надо определить эти $2^n-n$ элементов, помимо $n$ значений $f(i)$!)

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

xagiwo в сообщении #1528282 писал(а):

Работайте с понятиями, которым дано строгое определение, а не с "бесконечными $n$"

Вы агитируете меня как раз против того, против чего и я сам пытаюсь агитировать: против $n=\infty$.

[mihaild]

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

Пусть функция $f$ будет определена таким образом, что при при каждом $n$ ее cужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ на подмножество $\{1, 2, \ldots, n\}$ будет отображать $\{1, 2, \ldots, n\}$ в подмножество $B_n$

А если $f$ определена не так? Нам же нужно доказать теорему не для некоторых $f$, а для всех.

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

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

Его бы нужно доказать, но оно неверно.
Докажем аналогичным образом, что функция $f: \mathbb N \to \mathbb N$, $f(x) = x$ не является биекцией. Действительно, сужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ отображает $\{1, 2, \ldots, n\}$ в подмножество $C_n = \{1, 2, \ldots, n + 42\}$. Тогда $C_n$ будет состоять из $n + 42$ элементов, откуда следует, что отображение из $\{1, 2, \ldots, n\}$ в $B_n$ не может быть биективным.

[xagiwo]

Vladimir Pliassov, интереса ради — Канторово доказательство в моём изложении Вы поняли?

[Vladimir Pliassov]

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

Его бы нужно доказать, но оно неверно.
Докажем аналогичным образом, что функция $f: \mathbb N \to \mathbb N$, $f(x) = x$ не является биекцией. Действительно, сужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ отображает $\{1, 2, \ldots, n\}$ в подмножество $C_n = \{1, 2, \ldots, n + 42\}$. Тогда $C_n$ будет состоять из $n + 42$ элементов, откуда следует, что отображение из $\{1, 2, \ldots, n\}$ в $B_n$ не может быть биективным.

Да, вижу, что в общем случае предложение "поскольку ни при каком $n$ сужение $f{\big |}_{ \{1, 2, \ldots, n\}}$ не является биективным, то и вся функция $f$ не является биективной " неверно. Но все же Ваше отображение при сужении произвольное, а то, о котором я говорю, обусловлено тем, что по функции $\mathbb N \to \{0, 1\}$ каждое натуральное число "имеет выбор": отобразиться в нуль или в единицу, -- и это выражается в том, что, во всяком случае, для предложенного определения функции $f\colon \mathbb N \to \{0, 1\}^\mathbb N$, число элементов в множестве-прообразе $\{1, 2, \ldots, n\}$ равно $n$, а число элементов в множестве-образе $B_n$ равно $2^n$.

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

А если $f$ определена не так? Нам же нужно доказать теорему не для некоторых $f$, а для всех.

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

Что если взять приведенное частное определение:

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

и потом сделать произвольную перестановку натуральных чисел? Тогда получится произвольная функция?

xagiwo в сообщении #1528293 писал(а):

интереса ради — Канторово доказательство в моём изложении Вы поняли?

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

[xagiwo]

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

Докажем, что не существует биекции $\mathbb{N} \to \mathbb{N}^2$. Рассмотрим любую функцию $f: \mathbb{N} \to \mathbb{N}^2$ и её сужение $f\big{|}_{\{1,2,…,n\}}$. Поскольку для любого $n$ это сужение очевидно не является биекцией между $\{1, 2,…, n\}$ и $\{1, 2,…, n\}^2$, то сама функция $f$ не является биекцией $\mathbb{N} \to \mathbb{N}^2$.

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

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

Вы думаете, что биекцию, если она есть, какими-то перетасовками можно превратить в такую функцию? Это требует доказательства и это неверно. Сделайте, как Вам предложил mihaild: ограничтесь только последовательностями, в которых число единиц конечно. Начала последовательностей (первые $n$ членов при любом $n$) при этом могут оказаться какими угодно, так что Ваши рассуждения для этого случая тоже "срабатывают". Но множество последовательностей с конечным числом единиц как раз счётно

[mihaild]

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

Но все же Ваше отображение при сужении произвольное

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

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

надо найти такое общее определение функции $f$

Искать определение $f$ не надо, оно уже есть. $f$ - произвольная функция из натуральных чисел в последовательности.

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

Тогда получится произвольная функция?

Нет. $f$ может быть такой, что вообще для любых $x$ и $y$ последовательности $f(x)$ и $f(y)$ различаются в бесконечном числе членов.

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

Оно, конечно, очень ясно изложено, спасибо, но, может быть, это только кажущаяся ясность

Подумайте, спрашивайте. Но я бы советовал стараться разобраться в нём, а не пытаться придумать своё, с ним не связанное. Тем более что направление, в котором вы пытаетесь думать, к успеху точно не приведет (ну не переносятся такие свойства с конечных множеств на бесконечные).

[Vladimir Pliassov]

xagiwo в сообщении #1528300 писал(а):

Докажем, что не существует биекции $\mathbb{N} \to \mathbb{N}^2$. Рассмотрим любую функцию $f: \mathbb{N} \to \mathbb{N}^2$ и её сужение $f\big{|}_{\{1,2,…,n\}}$. Поскольку для любого $n$ это сужение очевидно не является биекцией между $\{1, 2,…, n\}$ и $\{1, 2,…, n\}^2$, то сама функция $f$ не является биекцией $\mathbb{N} \to \mathbb{N}^2$.

Это убедительно (то есть то, что это не доказательство). Что же касается следующего доказательства:

xagiwo в сообщении #1528266 писал(а):

Возьмём любую (не обязательно биекцию, вообще никаких ограничений) функцию $f: \mathbb{N} \to 2^\mathbb{N}$ (то есть $f$ "берёт" натуральные числа и возвращает бесконечные последовательности нулей и единиц).
Пусть $f(1) = (a_1, a_2, a_3, …)$; $f(2) = (b_1, b_2, b_3, …)$; $f(3) = (c_1, c_2, c_3, …)$ итд. Тогда последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ не совпадает ни с одной из последовательностей $f(1), f(2), f(3), …$ (почему?). А значит, функция $f$ не является биекцией между $\mathbb{N}$ и $2^\mathbb{N}$, т. к. как минимум один из элементов $2^\mathbb{N}$ она не возвращает.

то я просто подставлю вместо последовательностей целые числа:

Возьмём функцию $f: \mathbb{N} \to \mathbb Z$ (то есть $f$ "берёт" натуральные числа и возвращает целые числа).

Пусть $f(1)=1$; $f(2)=2$; $f(3)=3$ и т. д.. Число $-1$ не совпадает ни с одним из чисел $1, 2, 3, \ldots\, .$ А значит, функция $f$ не является биекцией между $\mathbb{N}$ и $\mathbb Z$, так как минимум один из элементов $\mathbb Z$ она не возвращает.

[mihaild]

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

А значит, функция $f$ не является биекцией между $\mathbb{N}$ и $\mathbb Z$

Правильно, вы доказали, что ваша конкретная $f$ не является биекцией. Но вы не доказали, что никакая $f$ не является биекцией. Рассуждение же xagiwo доказывает, что для любой $f$ есть не лежащая в её образе последовательность.

[Vladimir Pliassov]

Если функцию $f: \mathbb{N} \to \mathbb Z$ определить не как $f(1)=1$; $f(2)=2$; $f(3)=3$ и т. д., а как $f(1)=0$; $f(2)=1$; $f(3)=-1$ и т.д., то она будет биекцией.

Так же и с функцией $f\colon \mathbb N \to \{0, 1\}^\mathbb N$ (а что, вместо $\{0, 1\}^\mathbb N$ можно писать $2^\mathbb N?$):

если ее определить не как $f(1) = (a_1, a_2, a_3, …)$; $f(2) = (b_1, b_2, b_3, …);$ $f(3) = (c_1, c_2, c_3, …);$ ... , а как

$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ... , то она будет биекцией.

Если кто-то возразит, что последовательность $(1-a_1, 1-b_2, 1-c_3, …)$ следует определять только после того, как определены последовательности $(a_1, a_2, a_3, …)$; $(b_1, b_2, b_3, …)$; $(c_1, c_2, c_3, …);$ ... , это будет означать признание $n=\infty.$

[Geen]

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

то она будет биекцией

Да с чего бы вдруг?

-- 08.08.2021, 19:26 --

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

а что, вместо $\{0, 1\}^\mathbb N$ можно писать $2^\mathbb N?$

А что такое $2$ по Вашему? (с учётом того, что, если не ошибаюсь, прямо в этой теме об этом писали)

[Vladimir Pliassov]

Geen в сообщении #1528342 писал(а):

Да с чего бы вдруг?

Биекция это взаимно-однозначное отображение. Разве

$f(1) = (a_1, a_2, a_3, …)$; $f(2) =(1-a_1, 1-b_2, 1-c_3, …)$; $f(3)=(b_1, b_2, b_3, …)$; $f(4) = (c_1, c_2, c_3, …);$ ...

это не взаимно-однозначное отображение?