X Y

A b c

Рис. 1.23. Правило включения-исключения

Теорема(обобщенное правило включения – исключения).

Пусть конечное множество Xявляется объединениемrконечных множеств:Тогда

Теорема доказывается методом математической индукции по числу rблоков покрытия множестваX.

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

Будем говорить, что множество 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) и т.д.

	1	2	3	…
1	(1,1)1	(1,2)3	(1,3)6	…
2	(2,1)2	(2,2)5	(2,3)9	…
3	(3,1)4	(3,2)8	(3,3)13	…
…	…	…	…	…

Рис. 1.24. Множество X=NN

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

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

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

Покажем, что класс счетных множеств расположен в ряду мощностей левее любых других классов бесконечных множеств, а предшествуют ему только классы конечных множеств (рис. 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, но любые бесконечные множества.

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