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

Определение 1. Множество называется счётным, если оно эквивалентно множеству натуральных чисел.

A – счётно A ~ N,

Теорема 1. Для того чтобы множество A было счётным, необходимо и достаточно, чтобы A можно было представить в виде: , где попарно различны.

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

1) Необходимость. Дано: A – счётно. Доказать: A можно представить в виде: .

A ~ N. Пусть f биекция из N на A, обозначим:

, , , ……

Тогда: и все попарно различны.

2) Достаточность. Дано: Доказать: A – счётно.

Определим отображение следующим образом:

, , , ……

Таким образом, - биекция A на N.

Следовательно, A ~ N, A – счётно.

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

Доказательство: самостоятельно (Виленкин, учебник МГЗПИ, стр. 14).

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

Доказательство: Пусть A – бесконечное множество, возьмём произвольный элемент , рассмотрим – бесконечное множество.

Возьмём , -бесконечное множество.

…………………………………………………………

Получим множество .

- счётно (по теореме 1) и . Теорема доказана.

Теорема 4. Объединение конечного или счётного семейства счётных множеств является счётным множеством.

Рассмотрим счётное семейство: - счётные множества, докажем, что – счётно.

Доказательство: Так как счётны, то по теореме 1 получаем:

…………………………..

Будем нумеровать элементы по диагоналям.

Получим: . Множество A записали в виде последовательности.

При этом, если в таблице появляется элемент ранее встречавшийся, то теперь мы его пропускаем и не записываем в последовательность.

Таким образом, A записали в виде последовательности, в которой все элементы попарно различны, следовательно, A – счётно (по теореме 1).

Теорема 5. Если к бесконечному множеству добавить конечное или счётное, то мощность множества не изменится.

Доказательство: Пусть A – бесконечное множество, B - счётное или конечное множество. Докажем, что ~ A.

Возьмём счётное множество (по теореме 3), тогда – счётное множество (по теореме 4). Существует биекция .

Определим отображение :

Это отображение f есть биекция. A ~ , что и требовалось доказать.

Следствие. Множество рациональных чисел счётно.

Доказательство: Представим множество рациональных чисел в виде объединения множеств . Докажем, что множество положительных рациональных чисел счётно.

Пусть – счётное множество (по теореме 1)

- счётное множество (по теореме 1)

………………………………………………….

- счётное множество (по теореме 4) - счётное множество.

Очевидно, множество всех отрицательных рациональных чисел - счётно, так как ~ .

Тогда – счётное множество (по теоремам 4, 5).

Определение 2. Декартовым произведением конечного семейства множеств называется множество, элементами которого являются кортежи длины n, в которых для каждого . Оно обозначается или .

Теорема 6. Декартово произведение конечного числа счётных множеств является счётным множеством.

Дано: - счётные множества. Доказать: - счётно.

Доказательство: Доказательство проведём методом математической индукции по числу сомножителей произведения n.

1) Докажем, что счётно (n=2).

- счётное множество (по теореме 1, фиксировано )

……………………………………………………………………………………………….

- счётно (по теореме 4) - счётно.

2) допустим, что утверждение выполняется для n=k. Докажем, что оно истинно для n=k+1.

Множество счётно по индуктивному предположению, - счётно. Тогда множество счётно как декартово произведение двух счётных множеств. Теорема доказана.

Задача. Доказать, что множество всех конечных последовательностей натуральных чисел счётно.

Доказательство: Пусть - множество всех конечных последовательностей натуральных чисел.

Пусть - множество последовательностей из одного элемента.

- счётно, так как ~ N.

- счётно (по теореме 6), так как .

……………………………………………………………………………

Тогда - счётно (по теореме 4).

Определение 3. Бесконечное множество называется несчётным, если оно не является счётным.

Теорема 7. Если из несчётного множества удалить конечное или счётное, то мощность множества не изменится.

Доказательство: Пусть A - несчётное множество, B – счётное множество. Докажем, что A\B ~ B.

Обозначим A\B=C.

1) Докажем, что множество C – бесконечно.

Если бы C было конечным, что множество ~ B было бы счётным (по теореме 5). Но . Получаем противоречие: несчётное множество A эквивалентно счётному множеству B: A ~ B. Следовательно, C - бесконечное множество.

2) ~ C по теореме 5, но A ~ C A ~ A\B, что и требовалось доказать.

Определение 4. Действительное число называется алгебраическим числом, если является корнем многочлена с целыми коэффициентами.

Любое рациональное число является алгебраическим, так как оно является корнем уравнения . Но среди иррациональных чисел также встречаются алгебраические, например , которое является корнем уравнения .

Теорема 8. Множество алгебраических чисел счётно.

Доказательство: самостоятельно (Виленкин, учебник МГЗПИ).