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

Поскольку n e N, M_n ={1,2,3,..., n }c= N, то N > n.

Итак, N - бесконечная мощность. Она обозначается a или IC₀ (читается: алеф-нуль, алеф IC - это первая буква древнееврейского алфавита, аналог a греческой).

Таким образом, все множества A~N имеют эту мощность.

Определение

Множество, эквивалентное множеству N , называется счетным множеством.

Из самого определения имеем, что A = a тогда и только тогда, когда существует биекция f : N « A. По-другому можно сказать так: множество A счетно тогда и только тогда, когда все его элементы можно перенумеровать всеми натуральными числами. Это дает нам и инструмент для установления счетности множеств. Изучим простейшие свойства счетных множеств.

1) Из каждого бесконечного множества можно выделить счетное подмножество, причем так, что останется бесконечное множество. Доказательство

Выберем произвольно t\ e A. Поскольку A бесконечно, то можно взять еще q e A: q Ф t\. Так как A бесконечно, то можно выбрать t, e A, c₂ e A так, что t, Ф t\, c₂ Ф q Ф t\.

Этот процесс можно продолжить бесконечно, т. к. А бесконечно. Обозначим: B = { Ъ₁, £2, . ., b_n,...), B - счетно.

C = {с₁, С2,..., c_n,...) . Поскольку C с А\ B, то А \ B бесконечно. Свойство доказано.

2. Каждое бесконечное подмножество счетного множества само счетно.

Доказательство

Пусть A = a, B с A, B - бесконечно. Возможность нумерации элементов A означает возможность их расположения в бесконечную последовательность a₁, a_L,..., a_n,... попарно различных элементов.

Будем двигаться по этой последовательности, строго увеличивая номера, в поисках элементов множества B . Они найдутся, так как B с А. Пусть a е B - с наименьшим

номером.

Обозначим a_n = t₁ . Двигаясь далее, находим t₂ = a_n и т. д. Поскольку B бесконечно, для нумерации элементов придется использовать все числа из N. Это значит, что B счетно. Свойство доказано. Следствие

Счетная мощность есть наименьшая бесконечная мощность, т. е. IC₀ есть кардинальное наименьшее бесконечное число.

2. Если А счетно, B конечно, то A u B счетно. Доказательство

Очевидно, достаточно считать А п B = 0 . В других случаях получается тем более. Применим принцип счетности - возможность нумерации.

^Пу^{сть А} = { ^a_u ^aL^,...^{, a}n^,...) ^{, B} = { ^t1^{, b}L^,...^, К ) . C = Au B. Нумеруем: q = b_l, c_m = Ъ_т, с_ш+1 = a_b... Свойство доказано. Следствие

Если A счетно, B - конечно, то A \ B счетно

.

4) Объединение конечного числа счетных множеств счетно. Доказательство

Достаточно считать данное семейство множеств { Д }_i=l+m

дизъюнктным. Расположим все элементы семейства в виде бесконечной матрицы и покажем стрелками ход нумерации:

А ^{: a}i1, ^ai2,..., ^ain,...

^A2 ^{: a}21, ^ai2 ,..., ^a2n,...

^Am ^{: a}m1,®^am2,...., ^amn,".

Ф

t

^am2,

Свойство доказано.

Теперь мы уже можем решить вопрос о множестве целых чисел. Следствие

Множество Z = Nu {0} u (-N). Поскольку (-N) счетно в силу биекции f := n « (-n), Nu (-N) по свойству 4) счетно. По 3- му свойству Z = (Nu (-N)) и{0} счетно.