Мысль о том, что бесконечные множества бывают «разных размеров» и их можно сравнивать, впервые высказал немецкий математик Георг Кантор во второй половине XIX века. Сначала её встретили враждебно, а теперь Кантора считают основателем теории множеств.
Определение. Множество называется счётным, если между ним и множеством N натуральных чисел можно установить взаимно однозначное соответствие, — иначе говоря, если оно бесконечно и все его элементы можно занумеровать: a₁, a₂, …, a_n, … Счётны, например, множество чётных чисел и множество Z.
Теорема 1. Любое бесконечное множество содержит счётное подмножество. (Выбираем элемент a₁, из оставшихся — a₂, и так далее.)
Теорема 2. Любое бесконечное подмножество B счётного множества A = {a₁, a₂, …} счётно: идём по номерам 1, 2, 3, … и нумеруем по порядку те a_n, которые лежат в B, — каждый элемент B получит свой номер.
Теорема 3. Объединение счётного и конечного, а также двух счётных множеств счётно: в первом случае сначала нумеруем конечное множество, потом счётное; во втором — нумеруем «через один»: a₁, b₁, a₂, b₂, … (общие элементы — один раз).
Теорема 4. Множество Q счётно. Положительные дроби p/q запишем в таблицу: в p-й строке и q-м столбце — p/q. Обходим таблицу по диагоналям p + q = 2, 3, 4, … и пропускаем уже встречавшиеся значения: 1; 1/2; 2; 1/3; 3; 1/4; 2/3; 3/2; 4; … — все положительные рациональные числа получили номера. Отрицательные нумеруются так же (r → -r), а Q = Q₊ ∪ Q₋ ∪ {0} счётно по теореме 3.
Несчётность. Бесконечное множество, которое не является счётным, называют несчётным; по теореме 1 оно «мощнее» N.
Теорема 5. Множество R несчётно. Достаточно доказать, что несчётен промежуток [0; 1) (если бы R было счётным, то и его бесконечная часть [0; 1) была бы счётной). От противного: пусть все числа [0; 1) занумерованы: a₁ = 0,a₁₁a₁₂a₁₃…, a₂ = 0,a₂₁a₂₂a₂₃…, … Составим число b = 0,b₁b₂b₃…, у которого k-я цифра отличается от k-й цифры числа a_k (и не равна 0 и 9). Тогда b отличается от каждого a_k — противоречие («диагональный метод» Кантора).
Следствия. Интервал (0; 1) несчётен (иначе, добавив 0, получили бы счётное [0; 1)). Любой интервал (a; b) эквивалентен (0; 1): x = a + t(b - a), t ∈ (0; 1), — значит, тоже несчётен. Множество иррациональных чисел несчётно: иначе R было бы объединением двух счётных множеств.