Определение счетного множества

Будем говорить, что множество X счетно, если оно равномощно множеству натуральных чисел N.

Пример 1. Пусть X множество нечетных натуральных чисел. Покажем, что X счетно. Для этого нужно установить биекцию множества X на множество натуральных чисел, т.е. занумеровать элементы множества X так, чтобы каждому элементу X соответствовал ровно один номер, а любому натуральному числу соответствовал ровно один элемент из X. Очевидно, соответствие N, удовлетворяет этим требованиям:

Таким образом, ½X½=½N½ и X счетно.

Пример 2. Пусть X=N´N – декартово произведение множества N на себя. Покажем, что X счетно. Расположим все элементы X в виде матрицы (рис. 1.24) и занумеруем его элементы “ по диагоналям ”: номер 1 присвоим элементу (1,1), номер 2 – элементу (2,1), 3 – (1,3) и т.д.

Полученное отображение X на N также является биекцией (хотя записать формулу в явном виде сложнее, чем в примере 1).

Мощность счетного множества обозначается À₀. Когда мы пишем ½X½=À₀, мы утверждаем, что множество X счетно, т.е. относится к тому же классу эквивалентности, что и множество натуральных чисел. А множество N считается эталоном (образцом) счетных множеств.

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

Покажем, что класс счетных множеств расположен в ряду мощностей левее любых других классов бесконечных множеств, а предшествуют ему только классы конечных множеств (рис. 1.25).

Основой для такого утверждения служат следующие теоремы о счетных множествах.

Теорема 1. Любое подмножество счетного множества конечно или счетно.

Пусть X – счетное множество, а – произвольное его подмножество. Занумеруем элементы множества и выберем тот элемент, который имеет минимальный номер и принадлежит подмножеству Y, – обозначим его . Затем рассмотрим множество и найдем в нем элемент с минимальным номером, принадлежащий Y, - обозначим , и т.д. Если на n-ом шаге мы не обнаружим в множестве элементов множества Y, то Y конечно и ½Y½=n. В противном случае (если процесс будет продолжаться бесконечно) множество Y счетное, т.к. указан способ нумерации его элементов.

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

Пусть X – бесконечное множество. Выберем произвольный элемент . Так как X бесконечно, то Æ. Обозначим произвольный элемент из . Далее найдется . Поскольку X бесконечно, этот процесс не может оборваться из-за “нехватки” элементов, и мы получим счетное подмножество Y множества X: .

Теорема 3. Объединение конечного или счетного количества счетных множеств есть множество счетное.

Пусть , где - счетные множества. Будем считать, что они попарно не пересекаются (в противном случае перейдем от множеств к множествам , которые попарно не пересекаются и ). Все элементы множества X запишем в виде бесконечной матрицы:

,

где в первой строке записаны элементы множества , во второй – и т.д. Занумеруем эти элементы “по диагонали”(как в примере 2 из 1.4.5), при этом устанавливается биекция между множествами X и N, т.е. X – счетное множество.

Теорема 4. Пусть X бесконечное множество, а Y – счетное. Тогда .

Теорема утверждает, что добавление счетного множества элементов не увеличивает мощность бесконечного множества.

Доказательство. Рассмотрим множество и представим его в виде объединения непересекающихся множеств где . Так как Y счетно, то конечно или счетно (по теореме 1). Множество X бесконечно, значит, существует счетное подмножество (по теореме 2). Тогда , а

.

По теореме 3 счетно, т.е . Поэтому . Теорема доказана.

В примере 1 из 1.4.5 мы установили, что множество N равномощно своему собственному подмножеству. Рассуждения, близкие к доказательству теоремы 4, позволяют утверждать, что таким свойством обладает не только множество N, но любые бесконечные множества.

Рассмотренные четыре теоремы показывают, что среди бесконечных множеств счетные множества являются наименьшими по мощности. Существуют ли множества более чем счетные?

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

Рассмотрим множество R. Сравним его с множеством N. Очевидно, что ½N½. Действительно, отрезок [0;1] содержит счетное подмножество , значит, является не менее, чем счетным. Покажем, что [0;1] и N не являются равномощными множествами, т.е. что .

Теорема. Множество точек отрезка [0;1] не является счетным.

Проведем доказательство методом “от противного”. Предположим, что множество [0;1] счетно, т.е. существует биекция N на [0;1], и каждому элементу отрезка можно присвоить номер: N}. Каждый элемент отрезка [0;1] представляется в виде бесконечной десятичной дроби , где – j-я десятичная цифра i-го элемента. Запишем все элементы N, в порядке возрастания номеров. Покажем, что найдется элемент b, принадлежащий отрезку [0;1], но не совпадающий ни с одним из занумерованных элементов N. Метод построения такого элемента называется диагональной процедурой Кантора и заключается в следующем. Будем строить элемент b в виде бесконечной десятичной дроби , где – i-я десятичная цифра. В качестве возьмем любую цифру, не совпадающую с , – любую цифру, не совпадающую с , и т.д., при любых N (рис. 1.26). Построенный таким образом элемент b принадлежит отрезку[0;1], но отличается от каждого из занумерованных элементов хотя бы одной цифрой. Следовательно, предположение о том, что существует биекция N ® [0;1]ошибочно, и множество [0;1] не является счетным.

Рис. 1.26. Диагональная процедура Кантора

Итак, мы показали, что ½[0;1]½>½N½, т.е. класс эквивалентности, которому принадлежит отрезок [0;1], расположен правее класса À₀ счетных множеств в ряду мощностей (рис. 1.25). Обозначим этот класс À (без индекса). Множества, принадлежащие этому классу, называются несчетными или множествами мощности континуум (континуум – непрерывный). Этому классу принадлежат и интервал (0;1), и множество R действительных чисел, и множество точек круга на плоскости.

Пример. Множество R имеет мощность континуума, т.к. равномощно отрезку [0;1]. Действительно, по теореме Кантора-Бернштейна (см. 1.4.3) ½[0;1]½= ½(0;1)½. Биекцию интервала (0;1)на множество R можно задать с помощью сложной функции , где имеет вид и отображает интервал (0;1)на интервал , а отображает интервал на R по закону .