Билет 2 Счётные множества

Множество a называется счетным, если существует взаимно однозначное соответствие между a и множеством натуральных чисел N. Другими словами, множество называется счётным, если все его элементы можно пересчитать, но для пересчёта придётся использовать не первые несколько натуральных чисел, как мы привыкли, а все натуральные числа.

Равномощные множества

Два множества называют равномощными, если между ними можно установить взаимно однозначное соответствие, при котором каждому элементу одного множества соответствует ровно один элемент другого.

Для конечных множеств это означает, что в них одинаковое число элементов, но определение имеет смысл и для бесконечных множеств. Например, отрезки и равномощны, поскольку отображение осуществляет искомое соответствие.

Определение 1. Будем говорить, что множество А равномощно множеству В , если существует биективное отображение .

Предложение 1. Отношение равномощности множеств является отношением эквивалентности.

Определение 2. Класс эквивалентности множества А называется мощностью А и обозначается через или card A .

Пример 1. Мощностью любого конечного множества можно считать число его элементов.

Определение 3. Будем говорить, что мощность множества A меньше либо равна мощности B множества , и писать , если существует инъективное отображение.

Теорема (Кантора-Бернштейна). Если для множеств A и B имеем и , то .

Определение 4. Если множество S равномощно множеству натуральных чисел, то S называется счетным.

Пример 2. Множество алгебраических чисел счетно.

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

Школьная математика имеет дело в основном с рациональными числами.

Рациональным числом называется число вида:

Что мы умеем делать с этими числами?

1) Складывать и вычитать:

Если, то

2) Умножать и делить:

3) Сравнивать:

Если

Но в связи с изучаемыми понятиями для нас нужна следующая теорема.

Теорема. Множество рациональных чисел счетно.

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

Представим множество всех рациональных чисел в виде бесконечной таблицы.

Оценим, как строятся строки этой таблицы.

Первая строка – это все целые числа, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.

Вторая строка – это все несократимые дроби со знаменателем 2, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.

Третья строка – это все несократимые дроби со знаменателем 3, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.

Вообще,n-ая строка это все несократимые дроби со знаменателем n, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.

Очевидно, что в этой таблице находятся все рациональные числа. Используя снова прием диагонализации представим R в виде:

Так как R представилось в форме последовательности, то отсюда следует, что R –счетное множество. <