Мощности и отображения

[Asker Tasker]

1) Доказать, что мощность бесконечного множества А не изменится, если объединить его со счётным множеством В.
Решение
А - бесконечное множество, поэтому (это предполагается известным) у него имеется счётное подмножество $A_{1}$. В - также счётное множество, следовательно $B \bigcup A_{1}$ - также счётное множество. По определению счётного множества между множеством $B \bigcup A_{1}$ и множеством натуральных чисел можно установить биекцию. Со множеством $A_{1}$ сделаем тоже самое. Композиция этих биекций будет являться биекцией множеств $A_{1}$ и $B \bigcup A_{1}$. Если в рамках того же отображения перевести оставшиеся элементы множества А сами в себя, то получим биекцию множеств А и $A \bigcup B$, а следовательно, по определению, эти множества равномощны.

2) Пусть В - данное несчётное множество, а множество А - счётное. Доказать, что можно построить биекцию множеств $A$ и $A \backslash B$.
Решение
Если бы множество $B \backslash A$ было счётным, то (это свойство счётных множество предполагается известным) было бы счётным и объединение этого множества со счётным множеством А, но $( B \backslash A ) \bigcup A = B $ - несчётное множество. Полученное противоречие означает, что множество $B \backslash A$. А алгоритм построения биекции между несчётным множеством и его объединением со счётным множеством был приведён в решении прошлой задачи.

Как Вы считаете, эти доказательства верны? Если да, то как подобрать счётное подмножество (см. решение 1) в конкретном примере? Пусть, например, нужно построить биекцию между некоторым отрезком (пусть будет $[0; 1]$) и множество иррациональных точек содержащихся в этом отрезке: $f : [0; 1] \leftrightarrow ([0; 1] \backslash \mathbb{Q}) $. Как это сделать?

-- 25.06.2012, 03:05 --

P.S.
Пусть например, нужна биекция $[ 0; + \infty ) \leftrightarrow ( 0; \infty ) $. Рассмотрим последовательность $\{ \frac{1}{n} \}_{n=1}^{\infty}$ - это, очевидно, счётное множество. Тогда биекцию можно построить следующую: все точки множества $(0; \infty) $, кроме членов выбранной последовательности, переходят сами в себя, а для остальных чисел укажем следующее взаимно однозначное правило:
$ 1 \rightarrow 0 $

$ \frac{1}{2} \rightarrow 1 $

$ \frac{1}{3} \rightarrow \frac{1}{2} $

$ \frac{1}{n} \rightarrow \frac{1}{n-1} (n > 1) $

А вот как делать в указанном примере - ума не приложу. Кажется, что всё по аналогии, но пока сообразить не получилось. Ведь если делать "по аналогии", то нужно выбрать последовательность иррациональных чисел, а как? Последовательность $\{ \frac{1}{\sqrt{n}} \}_{n=1}^{\infty}$ или её подобная (со степенями) не подойдёт - среди членов попадутся рациональные числа, а сказать "все члены последовательности, кроме рациональных чисел" - как-то слишком неконструктивно

[Xaositect]

Доказательства верны.

Последовательность иррациональных чисел можно взять очень простую --- $\frac{\alpha}{n}$, где $\alpha$ --- иррационально, например, $\frac{1}{\sqrt{2}}$. Ну и кстати "все элементы посл-ти $\frac{1}{\sqrt{n}}$, кроме рациональных" --- это достаточно конструктивно. $\sqrt{n}$ иррационально тогда и только тогда, когда $n$ не является квадратом целого числа, что легко проверяемо.

[Asker Tasker]

Xaositect в сообщении #588727 писал(а):

не является квадратом целого числа, что легко проверяемо.

А какой алгоритм проверки? Первое, что приходит в голову для общего случая, - перебрать все числа от одного до $ [\frac{n}{2}] $ с учётом чётности-нечётности исходного числа, но звучит как-то долговато. Может, какой-то алгоритм факторизации нужно использовать или всё проще?

P.S.
Можно ещё последнюю цифру сразу проверять, ведь только 0, 1, 4, 5, 6, 9 подходят.

[Xaositect]

Asker Tasker в сообщении #588729 писал(а):

А какой алгоритм проверки?

Извлекать корень, например, методом Ньютона, с точностью до первого знака после запятой. В случае, если первый знак после запятой 0 или 9, проверить, является ли ближайшее целое точным корнем из $n$.

[Asker Tasker]

Спасибо!