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

Счётное множество — это в теории множеств бесконечное множество, элементы которого можно пронумеровать натуральными числами, то есть установить взаимно однозначное соответствие (биекцию) между данным множеством и множеством натуральных чисел N = {1, 2, 3, …}. Понятие счётного множества введено в конце XIX века немецким математиком Георгом Кантором и является одним из фундаментальных в теории множеств, математическом анализе и топологии.

Определение и основные свойства

Множество A называется счётным, если существует биекция f: N → A, где N — множество натуральных чисел. Иными словами, все элементы счётного множества можно расположить в бесконечную последовательность a₁, a₂, a₃, …, где каждый элемент встречается ровно один раз. Конечные множества также иногда называют счётными (в этом случае говорят о «не более чем счётных» множествах), но в классическом определении счётное множество — это бесконечное множество, равномощное N.

Основные свойства счётных множеств:

• Любое подмножество счётного множества не более чем счётно (то есть либо конечно, либо счётно).
• Объединение конечного или счётного числа счётных множеств является счётным множеством.
• Декартово произведение конечного числа счётных множеств является счётным множеством.
• Множество всех конечных последовательностей элементов счётного множества является счётным.
• Множество всех бесконечных последовательностей элементов счётного множества (например, множество всех подмножеств N) является несчётным (континуальным).

История

Понятие счётного множества впервые было явно сформулировано Георгом Кантором в 1873—1874 годах в ходе его работы над теорией трансфинитных чисел. В 1874 году Кантор опубликовал статью, в которой доказал, что множество рациональных чисел счётно, а множество действительных чисел — несчётно. Это открытие произвело революцию в математике, показав, что существуют разные «размеры» бесконечностей. Кантор ввёл понятие мощности (кардинального числа) и обозначил мощность счётного множества как ℵ₀ (алеф-нуль) — первое бесконечное кардинальное число.

Примеры счётных множеств

Множество натуральных чисел N

Очевидно, является счётным по определению.

Множество целых чисел Z

Биекция между N и Z может быть задана, например, следующим образом: 1 → 0, 2 → 1, 3 → -1, 4 → 2, 5 → -2, 6 → 3, 7 → -3 и так далее. Таким образом, Z счётно.

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

Кантор доказал счётность Q, используя диагональный метод или метод «решета». Рациональные числа можно расположить в виде таблицы (матрицы), где в строке m и столбце n стоит дробь m/n. Затем, двигаясь по диагоналям, можно занумеровать все дроби, исключая повторяющиеся (например, 1/2 и 2/4). Это даёт биекцию между N и Q.

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

Алгебраическое число — это корень многочлена с целыми коэффициентами. Кантор показал, что множество всех алгебраических чисел (включая рациональные и иррациональные) также счётно. Доказательство основано на том, что многочлены с целыми коэффициентами можно занумеровать, а каждый многочлен имеет конечное число корней.

Множество всех конечных слов над конечным алфавитом

Например, множество всех конечных последовательностей букв русского алфавита (или любого другого конечного алфавита) счётно. Это свойство используется в теории формальных языков и информатике.

Счётное объединение счётных множеств

Пусть A₁, A₂, A₃, … — счётные множества. Тогда их объединение ∪ Aₙ также счётно. Доказательство проводится с помощью диагональной нумерации: элементы каждого множества выписываются в строку, а затем нумеруются по диагоналям, как в случае с рациональными числами.

Примеры несчётных множеств

Множество действительных чисел R

Кантор доказал несчётность R с помощью диагонального аргумента. Предположим, что все действительные числа от 0 до 1 можно занумеровать. Тогда можно построить новое число, отличающееся от каждого из них в n-м знаке после запятой. Это противоречие показывает, что R несчётно. Мощность R называется континуумом (обозначается c или 2^ℵ₀).

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

Поскольку Q счётно, а R несчётно, то множество иррациональных чисел (R \ Q) также несчётно.

Множество всех подмножеств натуральных чисел

Мощность множества всех подмножеств N (булеана N) равна 2^ℵ₀, что совпадает с мощностью континуума. Это множество несчётно.

Канторово множество

Канторово множество (множество Кантора) — это пример несчётного множества, имеющего меру нуль. Оно строится путём удаления средних третей из отрезка [0,1] и является классическим примером фрактала.

Применение и значение

Понятие счётного множества лежит в основе многих разделов математики:

• Математический анализ: счётность используется при определении сходимости рядов, меры Лебега, теории функций.
• Топология: счётные множества важны для понятий сепарабельности (существование счётного всюду плотного множества) и первой аксиомы счётности.
• Теория вероятностей: счётные пространства элементарных исходов (например, при бросании монеты до первого выпадения орла) являются моделью дискретных вероятностных пространств.
• Информатика: счётность множества всех вычислимых функций (функций, которые может вычислить машина Тьюринга) показывает, что большинство функций невычислимы.
• Логика и теория моделей: счётные языки и теории являются основой для теорем компактности и полноты.

Интересные факты

• Существует гипотеза континуума (ГК), сформулированная Кантором: не существует множества, мощность которого строго больше ℵ₀ и строго меньше мощности континуума. В 1963 году Пол Коэн доказал, что ГК не зависит от стандартной аксиоматики теории множеств (ZFC) — её нельзя ни доказать, ни опровергнуть в рамках ZFC.
• Множество всех действительных чисел, которые можно определить с помощью конечного числа слов (например, «наименьшее положительное число, квадрат которого больше 2»), является счётным, так как каждое такое определение — это конечная строка символов. Однако это множество содержит все числа, которые мы можем явно описать, что порождает парадокс: «почти все» действительные числа не могут быть описаны никаким конечным образом.
• В теории меры счётные множества имеют меру Лебега нуль, то есть они «пренебрежимо малы» в смысле длины, площади, объёма. Однако это не означает, что они малы в топологическом смысле: например, множество рациональных чисел всюду плотно на числовой прямой.

Источники

• Кантор Г. «Труды по теории множеств» (сборник статей).
• Колмогоров А. Н., Фомин С. В. «Элементы теории функций и функционального анализа».
• Хаусдорф Ф. «Теория множеств».
• Энгелькинг Р. «Общая топология».
• Дж. Л. Келли «Общая топология».