0/1 1/1 2/1 3/1 . . .

–1/1 –2/1 –3/1 –4/1 . . .

1/2 2/2 3/2 4/2 . . .

–1/2 –2/2 –3/2 –4/2 . . .

. . . . . . . . . . . . .

Из элементов этой таблицы построим последовательность по следующему правилу a₁=0/1; a₂=1/1; a₃= –1/1; a₄=1/2; a₅= –2/1; a₆=2/1 и т.д. Очевидно, в эту последовательность войдут все рациональные числа. Более того, в ней многие числа будут повторяться. Следовательно, мощность множества элементов данной последовательности не меньше мощности множества рациональных чисел. С другой стороны, эта последовательность эквивалентна натуральному ряду, т.е. подмножеству множества Q, а значит, она не может иметь мощность, большую, чем  Q. Значит, мощности множеств рациональных чисел и натурального ряда равны, т.е. множество рациональных чисел счетно.

Бесконечное множество не являющееся счетным называется несчетным.

Контрольные вопросы и задания

1. Найти взаимно однозначное отображение отрезка [0, 1] на отрезок [a, b].

2. Отобразить взаимно однозначно луч [0, +) на всю числовую прямую.

3. Построить взаимно однозначное отображение окружности единичного радиуса на отрезок [0, 1].

4. Установить взаимно однозначное соответствие между открытым единичным кругом E={(x, y) | x² +y² < 1} и множеством точек плоскости, являющемся дополнением к замкнутому единичному кругу (замкнутый круг – K={(x, y) | x² +y²  1}.

5. Установить взаимно однозначное соответствие между открытым единичным кругом и замкнутым единичным кругом.

6. Установить взаимно однозначное соответствие между окружностью и прямой.

7. Установить взаимно однозначное соответствие между сферой с одной выколотой точкой и плоскостью.

8. Установить взаимно однозначное соответствие между сферой и плоскостью.

9. Установить взаимно однозначное соответствие между множеством всех многочленов с рациональными коэффициентами и множеством всех натуральных чисел.

10. Установить взаимно однозначное соответствие между множеством всех конечных подмножеств натурального ряда чисел и множеством натуральных чисел.

11. Установить взаимно однозначное соответствие между множеством всех последовательностей действительных чисел и множеством всех последовательностей натуральных чисел.

12*. Установить взаимно однозначное соответствие между множеством всех последовательностей натуральных чисел и множеством всех строго возрастающих последовательностей натуральных чисел.

13. Установить взаимно однозначное соответствие между

множеством всех строго возрастающих последовательностей натуральных чисел и множеством всех бесконечных двоичных дробей, которые соответствуют числам интервала (0, 1].

14*. Доказать, что если A \ B ~ B \ A, то A ~ B.

15. Верно ли утверждение: "Если A ~ C, B ~ D, причем A  B, C  D, то A \ B ~ C \ D"?

16. Пусть A  C, B  D, C  D ~ C. Доказать, что A  D~A.

17. Верно ли утверждение: "Если A ~ B, C  A, C  B, то C \ A ~ C \ B"?

18. Верно ли утверждение: "Если A ~ B, A  C, B  C, то A \ C ~ B \ C"?

Примеры решения

Задача 12.

Рассмотрим произвольную последовательность натуральных чисел

n₁, n₂, . . . , n_k, . . .

Поставим ей в соответствие возрастающую последовательность

m₁ < m₂ < . . . < m_k < . . . ,

где m₁ = n₁, m₂ = m₁ + n₂, . . . , m_k=m_k-1 + n_k, . . . Легко видеть, что это соответствие – взаимно однозначное.

Задача 14.

Для произвольных множеств A и B справедливо равенство A = (A \ B)  (A  B), где (A \ B)  (A  B) = . Аналогично B = (B \ A)  (A  B), где (B \ A)  (A  B) = . Так как оба множества A и B являются объединением непересекающихся множеств, A \ B ~ B \ A по условию, и (A  B) ~ (A  B), то A ~B.