Несчётность множества 2^N

[TurboBeaver]

Помогите, пожалуйста, найти ошибку в рассуждениях. Читаю Дороговцева "Математический анализ. Краткий курс в современном изложении", и немного завис на упражнении №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 ...$

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

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

[Anton_Peplov]

TurboBeaver в сообщении #1675182 писал(а):

Далее продолжаем этот процесс.

А что насчет множества всех счетных подмножеств $\mathbb N$? Как Вы его получите в этой конструкции?

TurboBeaver в сообщении #1675182 писал(а):

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

Это равенство неверно.

[drzewo]

к слову сказать

(Оффтоп)

Докажем от противного, что $\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$. Противоречие.

[skobar]

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

[Anton_Peplov]

(Оффтоп)

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

Пересечение вложенных отрезков непусто

Это утверждение опирается на полноту $\mathbb R$, которая доказывается не сильно проще континуальности.

[TurboBeaver]

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

[drzewo]

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

которая доказывается не сильно проще континуальности.

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

[Anton_Peplov]

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

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

Да, я оговорился. Имел в виду несчетность. Континуальность - более сильное утверждение.