ОПРЕДЕЛЕНИЕ 15. Множество, равномощное множеству N, называется счетным.
Иными словами счетными являются такие множества, элементы которых можно занумеровать натуральными числами (например, так: ).
Подтверждением высказанного странного утверждения о «малости» такой бесконечности являются следующие результаты.
Теорема 9. Во всяком бесконечном множестве содержится счетное подмножество.
Доказательство. Пусть множество A бесконечное. Поскольку оно непустое, выберем в нем какой-нибудь элемент .
Множество A бесконечное, поскольку при удалении одного элемента множество не может из бесконечного стать конечным. Выберем в нем какой-нибудь элемент .
Множество A также бесконечное. Выберем в нем какой-нибудь элемент .
Этот процесс продолжается неограниченно. В результате получаем множество – счетное подмножество A, что и требовалось.
Теорема 10. Всякое бесконечное подмножество счетного множества является счетным.
Доказательство. Пусть AÌB, причем множества A – бесконечное, а B – счетное. По предыдущей теореме в A существует счетное подмножество C. Тогда |C|≤|A|≤|B|, причем |C|=|B| (оба множества счетные). В силу антисимметричности отношения порядка мощностей, отсюда |C|=|A|=|B|, т.е. множество A счетное, что и требовалось.
Следующая теорема имеет важные следствия.
Теорема 11. Объединение счетного семейства счетных множеств является счетным.
Доказательство. Пусть каждое из множеств A1,A2,…,An,… счетное. Можно считать, что эти множества попарно не пересекаются (в противном случае повторяющиеся элементы можно удалить). Расположим эти множества в виде таблицы
| A1: | a11 | a12 | a13 | a14 | a15 | … |
| A2: | a21 | a22 | a23 | a24 | a25 | … |
| A3: | a31 | a32 | a33 | a34 | a35 | … |
| A4: | a41 | a42 | a43 | a44 | a45 | … |
| A5: | a51 | a52 | a53 | a54 | a55 | … |
| … | … | … | … | … | … | … |
Выпишем элементы объединения в следующем порядке:
a11, a21, a12, a31, a22, a13, a41, a32, a23, a14,…. Занумеруем все эти элементы последовательно. (Каким будет номер элемента aij?). Теорема доказана.
Следствие. Множество рациональных чисел Q счетное.
Доказательство. Рациональные числа это числа, которые представимы в виде , где числа p,q целые, q¹0. Достаточно проверить утверждение для положительных рациональных чисел (почему?). Q= , где
. Таким образом, множество положительных рациональных чисел является объединением счетного семейства счетных множеств, т.е. счетное.
Разумеется, счетным является и множество рациональных чисел из отрезка [0,1]. В то же время, множество точек отрезка является несчетным (в нем точек «больше», чем в счетном – теорема 8!). Несмотря на это, рациональные точки всюду плотны на отрезке в следующем смысле: какой бы интервал (a,b)Ì [0,1] мы ни взяли (длина его может быть сколь угодно малой!), в нем содержится рациональное число! Действительно, если натуральное число q столь велико, что , то хотя бы одно число вида принадлежит интервалу (a,b). Так что, несчетное множество приближается счетным.