2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Континуальность бесконечных последовательностей натуральных
Сообщение30.01.2025, 20:39 


19/01/24
33
Доказать что $\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}$

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение30.01.2025, 20:47 
Заслуженный участник


07/08/23
1428
У вас $\infty = \mathbb N$, что ли?

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение30.01.2025, 20:54 


19/01/24
33
dgwuqtj в сообщении #1672139 писал(а):
У вас $\infty = \mathbb N$, что ли?

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

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение30.01.2025, 23:03 


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

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение30.01.2025, 23:04 
Заслуженный участник


07/08/23
1428
А так рассуждения правильные.

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение31.01.2025, 07:40 
Заслуженный участник
Аватара пользователя


30/01/09
7357
gosetrov в сообщении #1672137 писал(а):
Доказать что $\mathbb{N}^\infty\sim2^\mathbb{N}$

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

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение31.01.2025, 08:23 


19/01/24
33
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}$ ?


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

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение31.01.2025, 14:11 


04/06/24
288
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}$ также имеет мощность континуум, и утверждение остается верным, вне зависимости от того как интерпретировать обозначение.

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение01.02.2025, 09:40 
Заслуженный участник
Аватара пользователя


20/08/14
8962
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).

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение01.02.2025, 10:16 


16/12/23
35
Можно так ещё:
$\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\}$)

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение05.02.2025, 14:50 
Заслуженный участник
Аватара пользователя


20/08/14
8962
Куратовский и Мостовский доказывают это свойство через арифметику кардинальных чисел (свойства степеней). Нужно доказать, что ${\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}$. Теорема доказана.

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение06.02.2025, 10:48 
Заслуженный участник
Аватара пользователя


20/08/14
8962
Похоже, верен более общий факт: для любой бесконечной мощности $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$. Теорема доказана.

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

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение06.02.2025, 11:59 
Заслуженный участник


07/08/23
1428
Anton_Peplov в сообщении #1673437 писал(а):
для любой бесконечной мощности $a$ верно $a^a = 2^a$.

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

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение06.02.2025, 12:52 


16/12/23
35
dgwuqtj
поправка: при $2 \leq \kappa \leq \lambda$

 Профиль  
                  
 
 Re: Континуальность бесконечных последовательностей натуральных
Сообщение06.02.2025, 15:52 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: HungryLion, teleglaz


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group