Кратко и по делу: типичная ошибка — из бесконечности множества делать вывод о существовании биекции с $\mathbb{N}$. Ниже — разбор ошибок, правильные формулировки и классические примеры.
Типичные ошибки
- Путаница «бесконечное» ⇄ «счётное»: факт $S$ бесконечно не даёт автоматически биекции $\mathbb{N}\to S$.
- Неправильное использование перечисления: показать процесс перечисления элементов (алгоритм) — недостаточно, нужно доказать, что каждый элемент попадёт в список (нет повторов/нет пропусков).
- Считать наличие инъекции $\mathbb{N}\to S$ достаточным для счётности: такая инъекция лишь показывает, что $S$ бесконечно (в смысле Дедекинда), но не обязательно даёт биекцию с $\mathbb{N}$.
- Игнорирование тонкостей представления чисел (например, десятичные представления с повторяющимися 9), когда делают диагональный аргумент неверно.
- Неразличение «взаимно однозначно перечислено» (биекция) и «есть процедура, которая, возможно, перечисляет» (без доказательства полноты).
Правильные определения (коротко)
- «Счётно бесконечно» (или просто «счётно» в узком смысле): существует биекция $f:\mathbb{N}\to S$.
- «Не более чем счётно» (at most countable): $S$ конечно или счётно бесконечно; эквивалентно существованию инъекции $g:S\to \mathbb{N}$.
- «Счётное» в широком смысле часто означает «не более чем счётно».
- «Несчётно» (ункаунтабл): нет биекции $\mathbb{N}\to S$ (то есть $S$ не является счётным).
Классические контрпримеры
1) Рациональные числа $\mathbb{Q}$ — счётны.
Краткая конструкция: представим положительные рационалы как дроби $p/q$ с $p,q\in \mathbb{N}$. Рассматриваем всю решётку пар $(p,q)$ и перечисляем её по диагоналям (канонический «серая улитка» или канторово упорядочение). При этом пропускаем дроби, не приведённые к несократимому виду, чтобы не дублировать. Получаем сюръекцию $\mathbb{N}\to {\mathbb{Q}}_{>0}$; добавлением знака и нуля покрываем все $\mathbb{Q}$. Следовательно $|\mathbb{Q}|=|\mathbb{N}|$. (Формально: существует биекция $\mathbb{N}\to \mathbb{Q}$.)
2) Действительные числа $\mathbb{R}$ — несчётны (Канторовский диагональный аргумент).
Предположим противное: существует перечисление всех чисел в интервале $(0,1)$,
$$x_1,x_2,x_3,\dots$$ и пусть каждое $x_n$ записано в десятичном виде $x_n=0.d_{n1}{d}_{n2}{d}_{n3}\dots$ (исключим двусмысленные представления, например всегда используем представление, не оканчивающееся бесконечной последовательностью 9). Построим число $y=0.c_1{c}_2{c}_3\dots$, где $c_n$ выбирается так, чтобы $c_n\ne d_{nn}$ (например $c_n=1$ если $d_{nn}\ne 1$, иначе $c_n=2$). Тогда по построению $y\ne x_n$ для любого $n$, значит $y$ не в списке — противоречие. Следовательно никакой биекции $\mathbb{N}\to (0,1)$ не существует, т.е. $\mathbb{R}$ несчётно.
Дополнительные утверждения
- $|\mathbb{Q}|={\aleph }_0$ и $|\mathbb{R}|=2^{{\aleph }_0}>{\aleph }_0$.
- Множество всех подмножеств натуральных чисел $\mathcal{P}(\mathbb{N})$ имеет мощность $2^{{\aleph }_0}$ и в биекции с $\mathbb{R}$ (интервалом $(0,1)$).
Как правильно доказывать счётность/несчётность (рецепт)
- Чтобы доказать, что $S$ счётно: построить явно биекцию $f:\mathbb{N}\to S$ или по крайней мере сюръекцию $g:\mathbb{N}\to S$ и показать, что образ покрывает $S$. Если приводите перечисление — докажите, что каждый элемент встретится в нём.
- Чтобы доказать, что $S$ несчётно: показать, что никакая функция $f:\mathbb{N}\to S$ не может быть сюръекцией (обычно используют диагональный аргумент или теорему Кантора о том, что для любого множества $X$ мощность $\mathcal{P}(X)$ строго больше мощности $X$).
Вывод: утверждение «любое бесконечное множество биективно с $\mathbb{N}$» — неверно. Надо различать «бесконечное» и «счётное» и при доказательствах конструктивно показывать биекцию/сюръекцию или приводить контрпример (например, $\mathbb{R}$).