Множества счётные и несчётные

Фундаментальным понятием в математике является счётное множество. Понятие это не так уж и сложно само по себе, но знакомство с ним обычно вызывает сложности у вчерашних школьников.Существует, однако, вполне корректное, но гораздо более популярное определение счётности, легко доступное для понимания. Вот как оно выглядит.

Множество называется счётным, если его можно представить в виде Книги, составленной по следующим правилам:

  • На каждой странице Книги указан ровно один элемент множества.
  • Каждый элемент множества указан ровно на одной странице Книги.
  • Все страницы Книги обычным образом пронумерованы последовательно увеличивающимися натуральными числами, начиная с единицы.
  • Каким бы не было натуральное число, в Книге есть страница с соответствующим номером.

Достаточно очевидно, что само множество натуральных чисел является счётным. Действительно, в Книге Натуральных Чисел на \(n\)-ой странице достаточно указать число \(n\).

Множество чётных натуральных чисел также счётно. В Книге Чётных Натуральных Чисел каждая страница с номером \(n\) должна содержать число \(2n\).

Множество нечётных натуральных чисел счётно: в его Книге на каждой \(n\)-ой странице нужно указать число \((2n-1)\).

Множество натуральных чисел, являющихся точными квадратами, тоже счётно. В его Книге всякая страница с номером \(n\) должна нести на себе число \(n^2\). Этот факт заметил ещё Галилей.

Существуют, однако, и несчётные множества. Так, например, несчётно множество \(\mathfrak{X}\) всех подмножеств натуральных чисел. Докажем это.


Предположим от противного, что \(\mathfrak{X}\) счётно и его можно представить в виде Книги Натуральных Подмножеств (КНП).

Разделим все натуральные числа на две категории: «чёрные» и «серые». Будем называть натуральное число \(n\) чёрным, если оно является элементом множества, указанного на \(n\)-ой странице КНП и серым в противном случае. Пусть \(\mathfrak{M}\) — множество всех серых, и только серых натуральных чисел. Очевидно, \(\mathfrak{M}\) есть подмножество натуральных чисел, так что оно является элементом \(\mathfrak{X}\).

Множество \(\mathfrak{M}\) должно быть указано на одной из страниц КНП; пусть эта страница имеет номер \(m\). Может ли \(m\) быть серым числом? Нет, поскольку на \(m\)-ой странице указано множество всех серых чисел \(\mathfrak{M}\), и \(m\) должно входить в него, что по определению делает \(m\) чёрным числом. Но если \(m\) является чёрным, то из его присутствия на данной странице следует, что множество \(\mathfrak{M}\) содержит по меньшей мере одно чёрное число, что противоречит построению.

Итак, множество серых чисел \(\mathfrak{M}\) не может быть указано ни на одной странице КНП, а значит, \(\mathfrak{X}\) несчётно.