Мощность множества всех последовательностей

[Anton_Peplov]

Заинтересовал вопрос о мощности множества всех последовательностей натуральных чисел. Попробую доказать, что оно континуально.

При доказательстве я буду опираться на утверждение, что если система множеств $\Omega$ счетна, а каждое множество из $\Omega$ континуально, то декартово произведение всех множеств из $\Omega$ континуально. Попробовал с ходу это доказать, но что-то у меня застопорилось с построением биекции. Если это утверждение неверно, просьба сказать мне, и тогда дальше можно не читать.

Для удобства я буду придерживаться того варианта терминологии, который называет счетными множествами не только равномощные $\mathbb{N}$, но и конечные, потому что ниже для нас не будет никакой разницы, конечно множество или равномощно $\mathbb{N}$, а все время говорить "не более чем счетное" неудобно.

Пусть $\Sigma$ - множество всех последовательностей натуральных чисел. Рассмотрим произвольную последовательность $\alpha \in \Sigma$. Обозначим $A(\alpha)$ множество всех чисел, входящих в $\alpha$. Например, для $\alpha = 01010101...$ $A = \{0, 1\}$. Понятно, что $\Sigma$ распадается на классы последовательностей, имеющих одно множество $A$. Понятно, что этих классов столько же, сколько различных множеств $A$, то есть континуум (поскольку множество всех $A$ есть множество всех подмножеств $\mathbb{N}$). Осталось выяснить, сколько последовательностей отвечает каждому $A$.
Рассмотрим произвольную последовательность $\alpha$ из данного $A$-класса. Каждому элементу $x \in A$ отвечает множество $N(x, \alpha)$ номеров, которые он имеет в последовательности $\alpha$. Например, для $\alpha = 01010101...$ $N(0, \alpha)$ - множество всех нечетных, а $N(1, \alpha)$ - множество всех четных чисел. Таким образом, последовательности $\alpha$ взаимно однозначно отвечает система множеств $\{N(x, \alpha), N(y, \alpha), N(z, \alpha)...\}$, равномощная $A$. Другими словами, последовательности $\alpha$ отвечает элемент декартова произведения $S \times S \times$, где $S$ - система всех подмножеств $\mathbb{N}$, а количество членов декартова произведения равномощно $A$. (На самом деле в роли $\{N(x, \alpha), N(y, \alpha), N(z, \alpha)...\}$ могут выступать не любые подмножества $\mathbb{N}$, а только попарно не пересекающиеся, т.к. на одном и том же месте в последовательности не могут стоять два элемента одновременно, но на мощности это не скажется). Множество $A$ по построению счетно, поэтому произведение $S \times S \times$ континуально.

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

Вопрос: есть ли ошибки?

[AlexDem]

А почему нельзя просто сказать, что $2^{\aleph_0} = {\aleph_0}^{\aleph_0}$?

[Xaositect]

Все правильно, но как-то сложно. В частности, вот это утверждение

Anton_Peplov в сообщении #1053810 писал(а):

(На самом деле в роли $\{N(x, \alpha), N(y, \alpha), N(z, \alpha)...\}$ могут выступать не любые подмножества $\mathbb{N}$, а только попарно не пересекающиеся, т.к. на одном и том же месте в последовательности не могут стоять два элемента одновременно, но на мощности это не скажется)

В принципе не сильно проще исходного.

Все можно сделать гораздо проще через теорему Кантора-Шредера-Бернштейна.

[Anton_Peplov]

Xaositect в сообщении #1053826 писал(а):

Все можно сделать гораздо проще через теорему Кантора-Шредера-Бернштейна.

Это та, которую все пытаются доказать вот здесь? post1053835.html

[Xaositect]

Да.

[Anton_Peplov]

Ну из $A \subset \Sigma$ в $[0, 1]$ построить биекцию просто. Берем у произвольного числа все десятичные знаки после запятой, они образуют последовательность натуральных чисел из отрезка $0 \leqslant n < 10$. Это, правда, не совсем биекция, т.к. каждое рациональное число имеет в $A$ два прообраза, но на мощности это сказаться не должно. А вот из какого $B \subset [0, 1]$ и как построить биекцию в $\Sigma$ - это я думал-думал-не-придумал.

[Slav-27]

Xaositect в сообщении #1053826 писал(а):

Все можно сделать гораздо проще через теорему Кантора-Шредера-Бернштейна.

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

И раз уж мы верим, что $\text{мощность }2^\mathbb{N}=\text{мощности континуума}$:

Anton_Peplov в сообщении #1053810 писал(а):

Понятно, что этих классов столько же, сколько различных множеств $A$, то есть континуум (поскольку множество всех $A$ есть множество всех подмножеств $\mathbb{N}$).

- то этим, мне кажется, исчерпывается дело.

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

[Anton_Peplov]

Slav-27 в сообщении #1053880 писал(а):

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

Черт. И как я до этого не додумался! У меня как раз все упиралось в то, как сделать пробел. Я думал о префиксных кодах типа Шеннона-Фано, но не уверен, что с ними не возникает проблем при бесконечных множествах.

[Dan B-Yallay]

Slav-27 в сообщении #1053880 писал(а):

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

А последовательность натуральных чисел может содержать нолики? А три/семь/стопицот подряд ноликов?

[venco]

Ну прибавьте один, если для вас ноль не натуральное число.

[Anton_Peplov]

Dan B-Yallay
Здесь удобно не считать $0$ натуральным числом (его то считают, то не считают - мощность $\mathbb{N}$ от этого не меняется). Но если считать, то прибавим к каждому числу в последовательности натуральных чисел единицу и получим последовательность без нулей, которая однозначно соответствует исходной последовательности с нулями. Проблем-то.

Хотя... При построении обратной биекции (из двоичной последовательности в произвольную) проблемы таки возникают. Как, например, расшифровать $01001000100001000001...$? Если включить известную нам по Excel опцию "считать последовательные разделители одним", получится уже не биекция. В частности, вышеупомянутая последовательность будет прочитана так же, как $0101010101...$ и как все остальные последовательности, где нет двух идущих подряд единиц.

[Xaositect]

Ну можно сначала почитать количество единиц, потом количество нулей и т.д.

[Slav-27]

В чём проблема, не пойму?

Anton_Peplov в сообщении #1053909 писал(а):

Если включить известную нам по Excel опцию "считать последовательные разделители одним"

Зачем одним-то? наоборот разными! И $0$ удобнее считать таки натуральным. Его менять на $0$ единиц, сиречь пустое место. $0011100110...$ при расшифровке даст $(0;0;3;0;2...)$

[Anton_Peplov]

Ага, то есть при обратной расшифровке считаем первый ноль из подряд идущих нулей пробелом, все остальные - просто нулями?

[Slav-27]

После каждого нуля ставим палочку: $0|0|1110|0|110|...$ Потом считаем количество единичек в каждой из секций.

-- 16.09.2015, 21:47 --

Вот чтобы вот таким вот не страдать, и делают 2 инъекции.

-- 16.09.2015, 21:55 --

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