Начальный отрезок натурального ряда [0;n−1]={1,2,…,n−1} конечен и содержит n элементов. Сам же натуральный ряд N={0,1,2,…} бесконечен. Поэтому не может быть инъективным никакое отображение Nв [0;n−1]. Следовательно, |N|>n, то есть мощность натурального ряда превосходит любое натуральное число. Множества, равномощные натуральному ряду, называются счетными. Для обозначения мощности счетных множеств используется символ ℵ0 (читается «алеф ноль»). Если множество A конечно или счетно, его элементы могут быть занумерованы, то есть расположены в виде списка
a0, a1, a2, a3, … ,
так, что всякий элемент множества A рано или поздно встретится в этом списке. Если множество A конечно, то и список конечен; в противном случае список оказывается бесконечным. Ясно, что при таких обозначениях отображение i→ai – это и есть та самая биекция начального отрезка или всего натурального ряда на множество A, которая устанавливает конечность или счетность множества A.
Пример.Множество четных чисел счетно; их можно представить списком 0,2,4,6,… . Соответствие очевидно: n↔2n. Точно так же счетно и множество нечетных чисел 1,3,5,… . Здесь можно положить n↔2n+1.
Пример.Множество рациональных чисел счетно. Напомним, что всякое рациональное число однозначно записывается в виде несократимой дроби p/q, где p и q – взаимно простые целые числа и q>0. Составим список, содержащий все рациональные числа, в порядке возрастания величины |p|+q:
0; −1/1; 1/1; −2/1; −1/2; 1/2; 2/1; …
Ясно, что любая дробь p/q появится в этом списке через конечное число шагов и получит свой номер.
Укажем некоторые свойства счетных множеств.
1. Всякое подмножество счетного множества конечно или счетно.
Доказательство. Достаточно доказать справедливость утверждения для множества натуральных чисел: всякое подмножество A множества натуральных чисел конечно или счетно. Составим список элементов множества A в порядке их возрастания. Если этот список конечен – множество A конечно; если бесконечен – счетно.
Из предыдущего предложения вытекает, что счетные множества являются наименьшими по мощности бесконечными множествами: если |A|≤ℵ0, то A конечно или счетно.
2. Образ счетного множества относительно произвольного отображения является конечным или счетным множеством.
Доказательство. Пусть множество В является образом счетного множества A относительно некоторого отображения. Тогда, по теореме из предыдущего пункта, |B|≤|A| и, значит, B конечно или счетно.
Если элементы множества A представлены списком с повторениями
a0, a1, a2, a3, … ,
то есть списком, в котором некоторые элементы могут попадаться многократно, это означает, что отображение i→ai сюръективно (но не инъективно). Таким образом, множество A является образом натурального ряда, и потому конечно или счетно.
3. Всякое бесконечное множество содержит счетное подмножество.
Доказательство. Пусть A – бесконечное множество. Тогда |A|≥ℵ0. Но это неравенство означает, что существует инъективное отображение множества натуральных чисел в A. Образ этого отображения – счетное подмножество множества A.
4. Объединение любого конечного (непустого) или счетного семейства счетных множеств счетно.
Доказательство. Пусть счетные множества A0, A1, … представлены списками своих элементов: A0 = {a00, a01, a02, a03, … };
A1 = {a10, a11, a12, a13, … };
A2 = {a20, a21, a22, a23, … };
A3 = {a30, a31, a32, a33, … };
…………………………….
Составим список объединения этих множеств A, располагая элементы объединения в порядке возрастания суммы индексов:
A = { a00, a01, a10, a02, a11, a20, a03, …}.
(если некоторые из множеств имеют общие элементы, в этом списке возможны повторения). Множество A бесконечно, и, значит, счетно.
Из предыдущего утверждения вытекает, что объединение счетного числа конечных множеств конечно или счетно.
5. Декартово произведение конечного числа счетных множеств счетно.
Доказательство. Пусть
A = { a0, a1, a2, a3, …}, B = { b0, b1, b2, b3, …}
– счетные множества. Покажем, что счетно декартово произведение A×B. Составим список его элементов подобно тому, как составлялся список рациональных чисел:
Если счетны множества A, B, C, то счетно A×B, а вместе с ним и A×B×С = (A×B)×С как произведение двух счетных множеств. Аналогично устанавливается счетность любого конечного семейства счетных множеств.
6. Пусть L = {a,b, …, } счетный алфавит. Тогда множество слов над алфавитом L (то есть конечных упорядоченных наборов символов алфавита) счетно.
Доказательство. Множество n-буквенных слов можно естественным образом отождествить с Ln, счетность которого следует из утверждения 5. Теперь достаточно сослаться на утверждение 4: множество всех слов представляет собой объединение счетного семейства счетных множеств: слов из одной буквы; слов из двух букв, и т. д.
