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

ОПРЕДЕЛЕНИЕ 15. Множество, равномощное множеству N, называется счетным.

Иными словами счетными являются такие множества, элементы которых можно занумеровать натуральными числами (например, так: ).

Подтверждением высказанного странного утверждения о «малости» такой бесконечности являются следующие результаты.

Теорема 9. Во всяком бесконечном множестве содержится счетное подмножество.

Доказательство. Пусть множество A бесконечное. Поскольку оно непустое, выберем в нем какой-нибудь элемент .

Множество A\ бесконечное, поскольку при удалении одного элемента множество не может из бесконечного стать конечным. Выберем в нем какой-нибудь элемент .

Множество A\ также бесконечное. Выберем в нем какой-нибудь элемент .

Этот процесс продолжается неограниченно. В результате получаем множество – счетное подмножество A, что и требовалось.

Теорема 10. Всякое бесконечное подмножество счетного множества является счетным.

Доказательство. Пусть A Ì B, причем множества A – бесконечное, а B – счетное. По предыдущей теореме в A существует счетное подмножество C. Тогда | C|≤ | A | ≤ | B |, причем | C|= | B | (оба множества счетные). В силу антисимметричности отношения порядка мощностей, отсюда | C|= | A |=| B |, т.е. множество A счетное, что и требовалось.

Следующая теорема имеет важные следствия.

Теорема 11. Объединение счетного семейства счетных множеств является счетным.

Доказательство. Пусть каждое из множеств A ₁, A ₂,…, A_n,… счетное. Можно считать, что эти множества попарно не пересекаются (в противном случае повторяющиеся элементы можно удалить). Расположим эти множества в виде таблицы

A 1:	a 11	a 12	a 13	a 14	a 15	…
A 2:	a 21	a 22	a 23	a 24	a 25	…
A 3:	a 31	a 32	a 33	a 34	a 35	…
A 4:	a 41	a 42	a 43	a 44	a 45	…
A 5:	a 51	a 52	a 53	a 54	a 55	…
…	…	…	…	…	…	…

Выпишем элементы объединения в следующем порядке:

a ₁₁, a ₂₁, a ₁₂, a ₃₁, a ₂₂, a ₁₃, a ₄₁, a ₃₂, a ₂₃, a ₁₄,…. Занумеруем все эти элементы последовательно. (Каким будет номер элемента a_ij?). Теорема доказана.

Следствие. Множество рациональных чисел Q счетное.

Доказательство. Рациональные числа это числа, которые представимы в виде , где числа p,q целые, q ¹0. Достаточно проверить утверждение для положительных рациональных чисел (почему?). Q = , где

. Таким образом, множество положительных рациональных чисел является объединением счетного семейства счетных множеств, т.е. счетное.

Разумеется, счетным является и множество рациональных чисел из отрезка [0,1]. В то же время, множество точек отрезка является несчетным (в нем точек «больше», чем в счетном – теорема 8!). Несмотря на это, рациональные точки всюду плотны на отрезке в следующем смысле: какой бы интервал (a,b)Ì [0,1] мы ни взяли (длина его может быть сколь угодно малой!), в нем содержится рациональное число! Действительно, если натуральное число q столь велико, что , то хотя бы одно число вида принадлежит интервалу (a,b). Так что, несчетное множество приближается счетным.