2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Мощность множества всех последовательностей
Сообщение16.09.2015, 15:53 
Заслуженный участник
Аватара пользователя


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

При доказательстве я буду опираться на утверждение, что если система множеств $\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$ есть объединение континуальной системы континуальных множеств, то есть континуально, что и требовалось доказать.

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

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 16:33 
Заблокирован
Аватара пользователя


07/08/06

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

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


06/10/08
6422
Все правильно, но как-то сложно. В частности, вот это утверждение
Anton_Peplov в сообщении #1053810 писал(а):
(На самом деле в роли $\{N(x, \alpha), N(y, \alpha), N(z, \alpha)...\}$ могут выступать не любые подмножества $\mathbb{N}$, а только попарно не пересекающиеся, т.к. на одном и том же месте в последовательности не могут стоять два элемента одновременно, но на мощности это не скажется)
В принципе не сильно проще исходного.

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

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 17:46 
Заслуженный участник
Аватара пользователя


20/08/14
8506
Xaositect в сообщении #1053826 писал(а):
Все можно сделать гораздо проще через теорему Кантора-Шредера-Бернштейна.

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

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 17:49 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Да.

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 17:59 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 18:41 
Заслуженный участник


14/10/14
1220
Xaositect в сообщении #1053826 писал(а):
Все можно сделать гораздо проще через теорему Кантора-Шредера-Бернштейна.
А ещё можно без особенных проблем зашифровать каждую последовательность натуральных чисел последовательностью ноликов и единичек. (Например, записать каждое натуральное число из последовательности соответствующим числом единичек, а соседей разгородить ноликами: и получится, представьте себе, биекция!..)

И раз уж мы верим, что $\text{мощность }2^\mathbb{N}=\text{мощности континуума}$:
Anton_Peplov в сообщении #1053810 писал(а):
Понятно, что этих классов столько же, сколько различных множеств $A$, то есть континуум (поскольку множество всех $A$ есть множество всех подмножеств $\mathbb{N}$).
- то этим, мне кажется, исчерпывается дело.

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

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 18:54 
Заслуженный участник
Аватара пользователя


20/08/14
8506
Slav-27 в сообщении #1053880 писал(а):
(Например, записать каждое натуральное число из последовательности соответствующим числом единичек, а соседей разгородить ноликами: и получится, представьте себе, биекция!..)

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

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


11/12/05
10056
Slav-27 в сообщении #1053880 писал(а):
А ещё можно без особенных проблем зашифровать каждую последовательность натуральных чисел последовательностью ноликов и единичек. (Например, записать каждое натуральное число из последовательности соответствующим числом единичек, а соседей разгородить ноликами: и получится, представьте себе, биекция!..)
А последовательность натуральных чисел может содержать нолики? А три/семь/стопицот подряд ноликов?

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 19:10 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 19:56 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 20:29 
Заслуженный участник
Аватара пользователя


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

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


14/10/14
1220
В чём проблема, не пойму?
Anton_Peplov в сообщении #1053909 писал(а):
Если включить известную нам по Excel опцию "считать последовательные разделители одним"
Зачем одним-то? наоборот разными! И $0$ удобнее считать таки натуральным. Его менять на $0$ единиц, сиречь пустое место. $0011100110...$ при расшифровке даст $(0;0;3;0;2...)$

 Профиль  
                  
 
 Re: Мощность множества всех последовательностей
Сообщение16.09.2015, 20:41 
Заслуженный участник
Аватара пользователя


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

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


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

-- 16.09.2015, 21:47 --

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

-- 16.09.2015, 21:55 --

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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