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

[gosetrov]

Доказать что $\mathbb{N}^\infty\sim2^\mathbb{N}$.

Сопоставим натуральные числа последовательностям нулей и единиц следующим образом:
1. $1\to1$
2.$2\to01$
...
k.$k\to0..01$, где перед единицей будет $k-1$ нулей

Тогда любую последовательность натуральных чисел можно закодировать таким образом в последовательность нулей и единиц. Т.о. мы построили инъекцию. В обратную сторону можно 0 сопоставить 1, а 1 сопоставить 2. Тогда по теореме Кантора-Бернштейна $\mathbb{N}^\infty\sim2^\mathbb{N}$.

Можно также сопоставлять в обратную строну по первому способу, останется только проблема с последовательностями с бесконечными нулями на конце. Таких последовательностей будет счетное число - бесконечные нули начинаются с некоторого номера, а до них конечное число комбинаций, т.е. это счетное объединение конечных множеств. Известно, что объединение счетного множества и бесконечного не меняет мощность бесконечного, тогда $\mathbb{N}^\infty\sim2^\mathbb{N}$

[dgwuqtj]

У вас $\infty = \mathbb N$, что ли?

[gosetrov]

dgwuqtj в сообщении #1672139 писал(а):

У вас $\infty = \mathbb N$, что ли?

Да, извините, исправил.

[drzewo]

Континуальность множества отображений $f:\mathbb{N}\to \mathbb{N}$ это должен быть какой-то стандартный факт. Учебники смотреть надо.

[dgwuqtj]

А так рассуждения правильные.

[мат-ламер]

gosetrov в сообщении #1672137 писал(а):

Доказать что $\mathbb{N}^\infty\sim2^\mathbb{N}$

А что тут обозначает знак $\infty$ ? Может вместо него лучше использовать символ $\mathbb{N}$ ?

[gosetrov]

drzewo в сообщении #1672147 писал(а):

Континуальность множества отображений $f:\mathbb{N}\to \mathbb{N}$ это должен быть какой-то стандартный факт. Учебники смотреть надо.

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

-- 31.01.2025, 08:23 --

мат-ламер в сообщении #1672153 писал(а):

gosetrov в сообщении #1672137 писал(а):

Доказать что $\mathbb{N}^\infty\sim2^\mathbb{N}$

А что тут обозначает знак $\infty$ ? Может вместо него лучше использовать символ $\mathbb{N}$ ?

Да, можно и так.

[skobar]

gosetrov в сообщении #1672137 писал(а):

Доказать что $\mathbb{N}^\infty\sim2^\mathbb{N}$.

С рассуждениями все правильно, но здесь, думаю, интересно пояснить логику обозначений. В общем случае, если $X$ и $Y$ множества, то через $X^Y$ обычно обозначают множество всех функций из $Y$ в $X$. Согласно такому подходу множество бесконечных последовательностей натуральных чисел должно обозначаться $\mathbb{N}^\mathbb{N}$. С обозначением $2^\mathbb{N}$ все интереснее. Если вспомнить, что согласно теоретико-множественному определению натуральных чисел $2=\{0,1\}$, то становится понятным, почему множество бесконечных последовательностей из нулей и единиц обозначается $2^\mathbb{N}$.

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

[Anton_Peplov]

gosetrov в сообщении #1672137 писал(а):

Сопоставим натуральные числа последовательностям нулей и единиц следующим образом

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

-- 01.02.2025, 09:48 --

drzewo в сообщении #1672147 писал(а):

Континуальность множества отображений $f:\mathbb{N}\to \mathbb{N}$ это должен быть какой-то стандартный факт. Учебники смотреть надо.

Заглянул в пару учебников: Верещагин, Шень. Начала теории множеств и Куратовский, Мостовский. Теория множеств. Стандартный факт - это что булеан (множество всех подмножеств) множества $A$ равномощен множеству всех функций $A \to \{0, 1\}$, т.е. $P(A) \sim 2^A$. Это следствие того очевидного факта, что каждому множеству $X \subset A$ соответствует его характеристическая функция. Таким образом, за определение континуума можно взять мощность $2^{\mathbb N}$. Про мощность множества $\mathbb{N^N}$ Верещагин и Шень вроде не упоминают (если только где-то в упражнениях). Куратовский и Мостовский доказывают, что она континуальна, в гл. V (с. 200).

[schmetterling]

Можно так ещё:
$\mathbb{N} \subset 2^\mathbb{N}$
$\mathbb{N} \times \mathbb{N} \cong \mathbb{N}$, так что
$\mathbb{N}^\mathbb{N} \subset (2^\mathbb{N})^\mathbb{N} \cong 2^{\mathbb{N} \times \mathbb{N}} \cong 2^\mathbb{N}$ и $2^\mathbb{N} \subset \mathbb{N}^\mathbb{N}$

-- 01.02.2025, 10:18 --

(здесь $2 = \{0, 1\}$)

[Anton_Peplov]

Куратовский и Мостовский доказывают это свойство через арифметику кардинальных чисел (свойства степеней). Нужно доказать, что ${\aleph_0}^{\aleph_0} \le \mathfrak c$ и $\mathfrak c \le {\aleph_0}^{\aleph_0}$. Докажем, что ${\aleph_0}^{\aleph_0} \le \mathfrak c$. Действительно, ${\aleph_0}^{\aleph_0} \le \mathfrak c^{\aleph_0} \le (2^{\aleph_0})^{\aleph_0} \le 2^{\aleph_0 \times \aleph_0} \le 2^{\aleph_0} \le \mathfrak c$. Доказать, что $\mathfrak c \le {\aleph_0}^{\aleph_0}$, еще легче: $2^{\aleph_0} \le {\aleph_0}^{\aleph_0}$. Теорема доказана.

[Anton_Peplov]

Похоже, верен более общий факт: для любой бесконечной мощности $a$ верно $a^a = 2^a$.

Нам понадобится известная теорема, что если хотя бы одна из мощностей $a, b$ бесконечна, то $a \times b = \max \{a, b\}$, откуда для бесконечной мощности $a$ верно $a \times a = a$.

Далее действуем как Куратовский и Мостовский. Очевидно, что $2^a \le a^a$. Докажем, что и $a^a \le 2^a$. Действительно, $a^a \le (2^a)^a \le 2^{a \times a} \le 2^a$. Теорема доказана.

Вроде же нигде не проврался?

[dgwuqtj]

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

для любой бесконечной мощности $a$ верно $a^a = 2^a$.

Можно тогда сразу писать $\kappa^\lambda = 2^\lambda$ при $2 \leq \kappa \leq 2^\lambda$, если $\lambda$ — бесконечный кардинал. Доказательство то же самое.

[schmetterling]

dgwuqtj
поправка: при $2 \leq \kappa \leq \lambda$

[dgwuqtj]

schmetterling
$2^\lambda \leq \kappa^\lambda \leq (2^\lambda)^\lambda = 2^{\lambda^2} = 2^\lambda$, всё в порядке.