Счётные и несчётные множества: свойства счётных множеств, счётность рациональных чисел и диагональный процесс Кантора

Бесконечное множество называется счётным, если оно равномощно \(\mathbb N\). Конечные и счётные множества вместе называют не более чем счётными. Подмножество счётного множества конечно или счётно, \(\mathbb N\times\mathbb N\) счётно, а объединение не более чем счётного семейства не более чем счётных множеств снова не более чем счётно.¹

Множество рациональных чисел \(\mathbb Q\) счётно. Каждое положительное рациональное число имеет единственную несократимую запись \(\frac pq\) с \(p,q\in\mathbb N\). Такие дроби перечисляют через пары \((p,q)\in\mathbb N\times\mathbb N\), оставляя пары с взаимно простыми \(p\) и \(q\). Затем отдельно добавляют 0 и отрицательные рациональные числа.^{1, 2} Диагональный процесс Кантора показывает несчётность множества всех бинарных последовательностей: из любого предполагаемого полного списка строится новая последовательность, отличающаяся от \(k\)-й строки в \(k\)-й позиции.^{1, 2}

Что важно запомнить

Счётное множество равномощно \(\mathbb N\).
«Не более чем счётное» означает конечное или счётное.
Подмножество счётного множества конечно или счётно.
\(\mathbb N\times\mathbb N\) счётно. Пары можно перечислять по диагоналям.
Объединение не более чем счётного семейства не более чем счётных множеств не более чем счётно.
\(\mathbb Q\) счётно.
Диагональный процесс Кантора строит элемент, отсутствующий в любом предполагаемом полном списке.

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

Множество \(A\) называется счётным, если существует биекция между \(A\) и \(\mathbb N\). Конечные и счётные множества называют не более чем счётными. Всякое подмножество счётного множества либо конечно, либо счётно.¹

Ключевой технический факт — счётность \(\mathbb N\times\mathbb N\). Пары натуральных чисел перечисляют по диагоналям таблицы. Из этого следует, что объединение не более чем счётного семейства не более чем счётных множеств также не более чем счётно: элементы записывают в таблицу и обходят её по той же схеме, пропуская повторы.¹

Счётность рациональных чисел

Сначала рассмотрим положительные рациональные числа. Каждое из них имеет единственную несократимую запись \(\frac{p}{q}\), где \(p,q\in\mathbb N\) и \(p,q\) взаимно просты. Пары \((p,q)\) перечисляют по диагоналям \(\mathbb N\times\mathbb N\) и оставляют пары с взаимно простыми компонентами. Поэтому каждое положительное рациональное число появляется ровно один раз, и множество положительных рациональных чисел счётно.^{1, 2}

Число 0 добавляют отдельно. Отрицательные рациональные числа получают из положительных заменой \(r\) на \(-r\), поэтому они образуют равномощную копию положительных рациональных чисел. Конечное объединение \(\{0\}\), положительных и отрицательных рациональных чисел не более чем счётно. Поскольку \(\mathbb N\subseteq\mathbb Q\), множество \(\mathbb Q\) бесконечно. Следовательно, \(\mathbb Q\) счётно.^{1, 2}

Диагональный процесс Кантора

Рассмотрим множество всех бесконечных последовательностей из 0 и 1. Предположим, что их удалось занумеровать: \(s_1,s_2,\ldots\). Построим последовательность \(t\) так, чтобы её \(k\)-й элемент отличался от \(k\)-го элемента \(s_k\). Если там стоит 0, ставим 1. Если стоит 1, ставим 0.^{1, 2}

Последовательность \(t\) отличается от \(s_1\) в первой позиции, от \(s_2\) во второй и вообще от \(s_k\) в \(k\)-й позиции. Поэтому \(t\) отсутствует в предполагаемом полном списке. Получено противоречие, и множество всех бинарных последовательностей несчётно.^{1, 2}

Пример простыми словами

Диагональную нумерацию \(\mathbb N\times\mathbb N\) можно начать так: \((1,1)\); затем \((1,2),(2,1)\); затем \((1,3),(2,2),(3,1)\) и так далее. Каждая пара попадает на одну из диагоналей и получает натуральный номер.¹

Частые ошибки

Путать «счётное» с «не более чем счётным»: конечное множество не является счётным в принятом здесь определении.
Делать вывод о счётности \(\mathbb Q\), не объяснив, как устраняются повторные записи одной и той же дроби.
В диагональном доказательстве изменить последовательность так, что она не гарантированно отличается от каждой \(k\)-й строки именно в \(k\)-й позиции.

Другие вопросы

Источники

1 Бегунц А. В., Шапошников С. В. Примерный конспект курса математического анализа Первый семестр. Механико-математический факультет МГУ имени М. В. Ломоносова, 2018 г. С. 9–10.
2 Бадерко Е. А. Лекции по математическому анализу I семестр. Механико-математический факультет МГУ. Билет 1.