118

d D d D.

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

Начальный отрезок натурального ряда [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.

119

Точно так же счетно и множество нечетных чисел 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. Образ счетного множества относительно произвольного отображения является конечным или счетным множеством.

120

Доказательство. Пусть множество В является образом счетного множества A относительно некоторого отображения.

Тогда, по теореме из предыдущего пункта, |B|≤|A| и, значит, B

конечно или счетно.

Если элементы множества A представлены списком с повторениями

a0, a1, a2, a3, … ,

то есть списком, в котором некоторые элементы могут попадаться многократно, это означает, что отображение i→ai сюръективно (но не инъективно). Таким образом, множество A является образом натурального ряда, и потому конечно или счетно.

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

Доказательство. Пусть A – бесконечное множество.

Тогда |A|≥ 0. Но это неравенство означает, что существует инъективное отображение множества натуральных чисел в A. Образ этого отображения – счетное подмножество множества A.

4. Объединение любого конечного (непустого) или счетного семейства счетных множеств счетно.

Доказательство. Пусть счетные множества A0, A1, … представлены списками своих элементов:

121

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. Составим список его элементов подобно тому, как составлялся список рациональных чисел:

(a0,b0), (a0,b1), (a1,b0), (a0,b2), (a1,b1), (a2,b0), … .

Если счетны множества A, B, C, то счетно A×B, а вместе с ним и A×B×С = (A×B)×С как произведение двух счетных