Счетные и несчетные множества

[hanik]

Доброго времени суток!
Прошу помочь в решении задач и указать на ошибки.
Есть три задачи из учебника Зорича по Математическому анализу, которые я пытаюсь решить.
a) Любое бесконечное множество содержит счетное подмножество.
b) Объединение бесконечного множества и не более чем счетного множества имеет ту же мощность, что и исходное множество.
c) Множество иррациональных чисел имеет мощность континуума.

Решение.
a) Пусть $A$ - бесконечное множество. Оно не пусто, поэтому найдём в нем хотя бы один элемент $x_{1}$. Далее, в множество $A-\{x_{1}\}$ также не пусто, так как если бы оно было пусто, то $A$ оказалось конечным множеством. Из $A-\{x_{1}\}$ берем элемент $x_{2}$. Продолжая, если у нас уже есть $n$ элементов $x_{1}, ..., x_{n}$, из бесконечного множества $A-\{x_{1}, ..., x_{n}\}$ возьмем элемент $x_{n + 1}$. Согласно принципу индукции, из $A$ мы можем выделить счетное подмножество.
b) Пусть $A$ - конченое или счетное множество, $B$ - бесконечное множество. Согласно доказаному утверждению в задаче a) в $B$ есть счетное подмножество $C = \{c_{1},...,c_{n},...\}$.
Построим биективное отображение $g: C \rightarrow A \cup C$
- если $A$ конечно, то $A = \{a_{1},...,a_{m}\}$ и
$g(c_{n}) = \begin{cases} a_{n} &\mbox{if } n \le m\\ c_{n+m} & \mbox{if } n > m\end{cases} $
- если $A$ счетно, то $A = \{a_{1},...,a_{n},...\}$ и
$g(c_{n}) = \begin{cases} a_{n} &\mbox{if } n = 2k + 1, k \in \mathbb{N} \\ c_{n} & \mbox{if } n = 2k, k \in \mathbb{N}\end{cases} $
Теперь можно определить биекцию $f: B \rightarrow A \cup B$:
$f(x) = \begin{cases} g(x) &\mbox{if } x \in C\\ x & \mbox{if } x \not\in C\end{cases} $.
c) Из определения иррациональных чисел известно что $\mathbb{I} = \mathbb{R} - \mathbb{Q}$. Это значит что $\mathbb{I} \cup \mathbb{Q} = \mathbb{R}$. Нам надо показать что $card(\mathbb{I} \cup \mathbb{Q}) = card\mathbb{I}$.
Покажем что $\mathbb{I}$ - бесконечное множество. Если бы оно было конечным, то по доказанному в задаче b) получилось что $card\mathbb{Q} = card (\mathbb{I} \cup \mathbb{Q})$, а это бы означало что множество $ \mathbb{R}$ счетно, но мы знаем что множество действительных чисел несчетно. Значит $\mathbb{I}$ - бесконечное.
Применяя утверждение из задачи b) , где $\mathbb{I}$ - бесконечное множество, а $\mathbb{Q}$ счетное множество, получаем: $card (\mathbb{I} \cup \mathbb{Q}) = card\mathbb{I}$, а это означает, что $card \mathbb{R} = card\mathbb{I}$.

[Brukvalub]

hanik в сообщении #1094295 писал(а):

- если $A$ счетно, то $A = \{a_{1},...,a_{n},...\}$ и

$$g(c_{n}) = \begin{cases} a_{n} &\mbox{if } n = 2k + 1, k \in \mathbb{N} \\ c_{n} & \mbox{if } n = 2k, k \in \mathbb{N}\end{cases} $$

Здесь есть ошибка.

[svv]

Ещё замечание по b).
Учтите коварную возможность, когда множества $A$ и $C$ имеют непустое пересечение (например, $a_2=c_2$), отчего определённая Вами $g$ может не быть биекцией (даже после исправления ошибки, о которой говорит Brukvalub).

[hanik]

$g(c_{n}) = \begin{cases} a_{(n + 1)/2} &\mbox{if } n = 2k + 1, k \in \mathbb{N} \\ c_{n / 2} & \mbox{if } n = 2k, k \in \mathbb{N}\end{cases} $
Так?

[svv]

Да.

[hanik]

Насчет непустого пересечения - ошибка остаётся?

-- 26.01.2016, 00:46 --

Если да - то делаем так: берем один элемент из $A$, затем один элемент из $C$, если он нам еще не встречался, потом из $A$ один, если он уникален, и так далее. Если выразить это формально, то нужно построить две последовательности индексов, правильно?

[svv]

hanik в сообщении #1094309 писал(а):

Насчет непустого пересечения - ошибка остаётся?

Если пересечение $A$ и $B$ непусто (что вполне возможно), то при неудачном выборе $C$ некоторые его элементы будут также элементами $A$. Тогда один и тот же элемент $A\cup C$ встретится в правой части Вашего определения функции $g$ дважды, при двух различных $n$: как элемент $A$ и как элемент $C$. Это, конечно, уже не биекция.

hanik в сообщении #1094309 писал(а):

Если да - то делаем так: берем один элемент из $A$, затем один элемент из $C$, если он нам еще не встречался, потом из $A$ один, если он уникален, и так далее. Если выразить это формально, то нужно построить две последовательности индексов, правильно?

Ну, или покажите, что $C$ всегда можно выбрать так, чтобы оно не пересекалось с $A$.

-- Пн янв 25, 2016 22:55:30 --

Нет, я неправ насчёт своего предложения. Возможен вариант, когда $A,B$ — счётные множества, и $A=B$.

[hanik]

Хорошо.
Предположим, уже выбрали $n$ уникальных элементов из $A \cup C$.
Пусть $n$- нечетно. $n$ конечно, поэтому в множестве $\{a_{n},...,a_{n+n}\}$ хотя бы один элемент будет отличен от выбранных ранее.
Аналогично с множеством $C$.

[svv]

Другими словами можно так: составляем последовательность
$a_1, c_1, a_2, c_2, a_3, c_3, ...$,
затем вычеркиваем из неё все элементы, совпадающие с одним из предыдущих (где-то это называлось «прополка»), и элементы полученной последовательности уже ставим в соответствие $(c_n)$ поэлементно.

[hanik]

Да. В остальном правильно?

[Someone]

б) По-моему, перемудрили с этими $A$ и $C$. Поскольку $A\cup B=(A\setminus B)\cup B$, без ограничения общности можно считать, что $A\cap B=\varnothing$; в противном случае можно заменить $A$ на $A'=A\setminus B$.

[hanik]

Someone в сообщении #1094330 писал(а):

б) По-моему, перемудрили с этими $A$ и $C$. Поскольку $A\cup B=(A\setminus B)\cup B$, без ограничения общности можно считать, что $A\cap B=\varnothing$; в противном случае можно заменить $A$ на $A'=A\setminus B$.

В этом случае $C$ нужно выбрать из $B - A$?

[Someone]

hanik в сообщении #1094333 писал(а):

В этом случае $C$ нужно выбрать из $B - A$?

Someone в сообщении #1094330 писал(а):

без ограничения общности можно считать, что $A\cap B=\varnothing$

[hanik]

Someone в сообщении #1094330 писал(а):

без ограничения общности можно считать, что $A\cap B=\varnothing$

Я не очень понимаю выражение "без ограничения общности". Здесь говорится про частный случай объединения, разве это не ограничение общности?

Помогите решить следующую задачу из того же учебника Зорича:
Множество $\{n_{1} < n_{2} < ...\}$ возрастающих последовательностей натуральных чисел равномощно множеству дробей вида $0,a_{1}a_{2}...$.
Насколько я понял, нужно показать, что множество этих последовательностей имеет мощность континуума.
Пусть $P$ - множество возрастающих последовательностей натуральных чисел.
Я могу показать, что $cardP \ge card\mathbb_{N}$ следующим образом:
Каждому $k \in \mathbb_{N}$ сопоставим последовательность $k, k+1, k+2,...$. Значит $P$ не менее чем счетное множество.
Проблема в том, чтобы показать что оно равномощно континууму.
Предположим, что $cardP = card\mathbb_{N}$. Тогда последовательности можно выстроить вот так:
$n_{1,1}, n_{1,2}, n_{1,3},...$
$n_{2,1}, n_{2,2}, n_{2,3},...$
$n_{3,1}, n_{3,2}, n_{3,3},...$
$.$

$.$

$.$

$n_{k,1}, n_{k,2}, n_{k,3},...$
где при элементе $n_{i,j}$: $i$ - номер последовательности, $j$ - номер элемента в этой последовательности.
Построим последовательность $a_{n}$.
$a_{1} = n_{1,1}$. Для $a_{2}$ выберем такой элемент из второго столбца, который бы не равнялся $n_{1,2}$ и был бы больше $a_{1}$. Так, если мы уже выбрали $q$ элементов, то для $a_{q+1}$ выберем элемент из $(q+1)$-го столбца такой что $a_{q+1} > a_{q}$ и $a_{q+1} \not\in \{n_{1,q+1}, n_{2,q+1}, ..., n_{q, q+1}\}$. Таким образом получается последовательность, которая отличается от всех последовательностей $\{n_{k}\}$, но все же принадлежит к их множеству. Вот...
Что-то не так со второй частью доказательства.

[Brukvalub]

Попробуйте позвать дедушек Кантора с Бернштейном.