2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Несчётность множества 2^N
Сообщение17.02.2025, 17:06 


20/03/22
9
Помогите, пожалуйста, найти ошибку в рассуждениях. Читаю Дороговцева "Математический анализ. Краткий курс в современном изложении", и немного завис на упражнении №39: доказать, что множество $2^N$ несчётно.

Скорее всего, доказательство, которое предполагает автор, опирается на теорему №8, в доказательстве которой с помощью диагонального метода Кантора обосновывается несчётность множества, составленного из всех возможных бесконечных последовательностей, членами которых есть лишь 0 и 1, т.е. последовательностей такого вида: $x=(0,1,1,0,1,0,...)$. Насколько я понимаю, любому подмножеству $M$ натуральных чисел можно поставить в взаимно-однозначное соответствие последовательность $x$ по следующему правилу: если $i\in M$, то i-й элемент последовательности $x$ равен 1, а если $i\notin M$, то i-й элемент последовательности $x$ равен 0. Отсюда и получим несчётность множества $2^N$.

Однако я подумал о иной конструкции, в ходе построения которой у меня вышло, что $2^N$ - счётное множество, и никак не могу найти ошибку в рассуждениях :(

Пусть $N_1$ - множество одноэлементных подмножеств множества $N$. Каждому элементу $\{a\}\in N_1$ биективно соответствует элемент $a\in N$, т.е. $N_1$ - счётное множество.

Пусть $N_2$ - множество двухэлементных подмножеств. Каждому множеству $\{a,b\}\in N_2$ поставим в соответствие упорядоченную пару $(\min\{a,b\}, \max\{a,b\})$. Таким образом, будет построена инъекция между множеством $N_2$ и неким подмножеством $N\times N$. Это будет означать, что $N_2$ не более чем счётно.

Далее продолжаем этот процесс. Например, каждому элементу $\{a,b,c\}\in N_3$ будет поставлена в соответствие упорядоченная тройка, состоящая из тех же элементов, но расположенных по возрастанию, т.е. $N_3$ тоже не более чем счётно.

Тогда получим, что $2^N = \emptyset \cup N_1 \cup N_2 \cup ...$

А объединение счётного числа не более чем счётных множеств есть счётное множество.

В этих рассуждениях явно есть какая-то ошибка, но не могу понять, какая :(
Может, суть в том, что тут не учтены бесконечные подмножества?

 Профиль  
                  
 
 Re: Несчётность множества 2^N
Сообщение17.02.2025, 17:21 
Заслуженный участник
Аватара пользователя


20/08/14
8816
TurboBeaver в сообщении #1675182 писал(а):
Далее продолжаем этот процесс.
А что насчет множества всех счетных подмножеств $\mathbb N$? Как Вы его получите в этой конструкции?

TurboBeaver в сообщении #1675182 писал(а):
Тогда получим, что $2^N = \emptyset \cup N_1 \cup N_2 \cup ...$
Это равенство неверно.

 Профиль  
                  
 
 Re: Несчётность множества 2^N
Сообщение17.02.2025, 17:22 


21/12/16
1297
к слову сказать

(Оффтоп)

Докажем от противного, что $\mathbb{R}$ несчетно. Предположим, что множество $\mathbb{R}$ счетно. Т.е. $\mathbb{R}=\{x_1,x_2\ldots\}$ Возьмем отрезок $I_1$ так, что $x_1\notin I_1$. Теперь возьмем отрезок $I_2\subset I_1$ так, что $x_2\notin I_2$.
и т.д. Пересечение вложенных отрезков непусто: $\exists\tilde x\in\bigcap_{i=1}^\infty I_i$.
Ясно, что $\tilde x$ не совпадает ни с одним $x_k$. Противоречие.

 Профиль  
                  
 
 Re: Несчётность множества 2^N
Сообщение17.02.2025, 17:28 


04/06/24
239
:) :) :) У множества натуральных чисел кроме конечных есть ещё и бесконечные подмножества.

 Профиль  
                  
 
 Re: Несчётность множества 2^N
Сообщение17.02.2025, 17:29 
Заслуженный участник
Аватара пользователя


20/08/14
8816

(Оффтоп)

drzewo в сообщении #1675184 писал(а):
Пересечение вложенных отрезков непусто
Это утверждение опирается на полноту $\mathbb R$, которая доказывается не сильно проще континуальности.

 Профиль  
                  
 
 Re: Несчётность множества 2^N
Сообщение17.02.2025, 17:31 


20/03/22
9
Спасибо всем, кто отписался, - дело и верно в бесконечных подмножествах, а я банально затупил :)

 Профиль  
                  
 
 Re: Несчётность множества 2^N
Сообщение17.02.2025, 18:03 


21/12/16
1297
Anton_Peplov в сообщении #1675188 писал(а):
которая доказывается не сильно проще континуальности.

континуальность тут вроде не обсуждается

 Профиль  
                  
 
 Re: Несчётность множества 2^N
Сообщение18.02.2025, 15:31 
Заслуженный участник
Аватара пользователя


20/08/14
8816
drzewo в сообщении #1675194 писал(а):
континуальность тут вроде не обсуждается
Да, я оговорился. Имел в виду несчетность. Континуальность - более сильное утверждение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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



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

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


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

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