§ 4. Равномощные множества. Счётные множества

Определения и обозначения

Равномощные множества — множества, между элементами которых можно установить взаимно однозначное соответствие. Иными словами, каждому элементу одного множества соответствует ровно один элемент другого, и каждый элемент второго тоже имеет ровно одну пару. Это понятие нужно, чтобы сравнивать множества по числу элементов, в том числе бесконечные.

Взаимно однозначное соответствие — правило, которое каждому элементу первого множества ставит в соответствие единственный элемент второго, причём каждый элемент второго получается ровно один раз. Поэтому недостаточно подобрать несколько подходящих пар: правило должно охватывать оба множества целиком. Такая проверка показывает, что элементы не потерялись и не повторились.

Счётное множество — бесконечное множество, элементы которого можно занумеровать натуральными числами, то есть установить взаимно однозначное соответствие с множеством натуральных чисел. Тогда каждому элементу можно назначить номер 1, 2, 3 и так далее. Это определение позволяет говорить о размере бесконечных множеств.

Бесконечное множество — множество, которое не является конечным. У такого множества нет последнего элемента в смысле количества элементов, но это не запрещает ему быть равномощным собственному подмножеству. Например, натуральные числа можно попарно сопоставить с одними только чётными числами.

Как это устроено

Чтобы проверить равномощность, нужно искать правило, которое связывает элементы двух множеств, а не сравнивать их внешний вид или порядок записи. Затем проверяют две стороны соответствия: каждому элементу первого множества назначен один элемент второго, и каждый элемент второго назначен ровно один раз. Если правило не охватывает хотя бы один элемент или приводит к повторам, доказательство не завершено. Для конечных множеств такое правило существует именно тогда, когда в них одинаковое число элементов.

Рассмотрим натуральные числа 1, 2, 3, … и чётные натуральные числа 2, 4, 6, … . Правило n ↔ 2n назначает каждому натуральному числу чётное: например, 3 соответствует 6. Обратно, любое чётное натуральное число имеет вид 2n для единственного натурального n, поэтому все чётные числа получаются и ни одно не повторяется. Значит, эти множества равномощны, хотя чётные числа составляют лишь часть натуральных.

Целые числа можно перечислить в порядке 0, 1, −1, 2, −2, 3, −3, … . Первому натуральному номеру соответствует 0, следующему — 1, затем −1, далее 2 и −2; так положительные и отрицательные числа чередуются. Любое целое число встречается в этой последовательности: для числа k или −k достаточно дойти до соответствующей пары после нуля. Поэтому каждому номеру соответствует одно целое число, и каждое целое получает конечный номер.

Счётность означает, что множество можно перечислить без пропусков, даже если элементов бесконечно много. Каждому элементу должен соответствовать натуральный номер, причём этот номер конечен: нельзя оставить элемент на бесконечно далёком месте. Если в списке есть повтор, один номер потрачен зря, а если элемент пропущен, список не охватывает множество полностью. Именно поэтому при доказательстве счётности проверяют и полноту перечисления, и отсутствие повторов.

Пары натуральных чисел удобно представить в таблице: номер строки задаёт первую координату, номер столбца — вторую. Если перечислять пары только по строкам, до некоторых строк можно никогда не дойти, потому что каждая строка бесконечна. Вместо этого проходят диагонали: сначала (1,1), затем пары с суммой координат 3, потом с суммой 4 и далее. У каждой пары сумма координат конечна, поэтому она попадёт на одну из диагоналей и получит конечный номер.

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

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

Разбор задач

Задача 1. Докажите, что множество чётных натуральных чисел равномощно множеству натуральных чисел. Нужно не только предложить правило, но и проверить, что оно связывает множества в обе стороны. Для этого рассмотрим соответствие n ↔ 2n.

1. Каждому натуральному n сопоставим число 2n. Оно натуральное и чётное, значит, правило ведёт в нужное множество.
2. Любое чётное натуральное число можно записать как 2n. Значение n определяется единственным образом, поэтому разные натуральные числа не дают одного и того же чётного.
3. Следовательно, правило взаимно однозначно: ни одно чётное число не пропущено и повторов нет.

Ответ: множества равномощны, поскольку им соответствует правило n ↔ 2n. Например, 1 ↔ 2, 2 ↔ 4, 3 ↔ 6. Это показывает, почему бесконечное множество может быть равномощно собственному подмножеству.

Задача 2. Пронумеруйте все целые числа натуральными числами и объясните, почему ни одно целое число не пропущено. Простое перечисление положительных чисел не подойдёт: в нём не окажется ни нуля, ни отрицательных чисел. Поэтому будем после каждого положительного числа включать соответствующее отрицательное.

1. Запишем последовательность: 0, 1, −1, 2, −2, 3, −3, … . Поставим в соответствие членам последовательности номера 1, 2, 3, 4, 5, 6, 7 и так далее.
2. Ноль стоит первым, а для каждого натурального k числа k и −k появляются в очередной паре. Значит, любое целое число встречается на определённом конечном месте.
3. Каждое число в списке встречается один раз: ноль не повторяется, а положительные и отрицательные числа различаются знаком.

Ответ: указанная последовательность задаёт нумерацию целых чисел натуральными номерами. Она охватывает все целые числа и не повторяет их, следовательно, множество целых чисел счётно.

Задача 3. Покажите, что множество пар натуральных чисел можно занумеровать натуральными числами. Представим пары в таблице: первая координата задаёт строку, вторая — столбец. Перечислять всю первую строку, а затем переходить ко второй нельзя, потому что в первой строке бесконечно много элементов.

1. Начнём с пары (1,1), а затем пройдём диагональ, содержащую пары (1,2) и (2,1).
2. Дальше перечислим следующую диагональ: (3,1), (2,2), (1,3); затем продолжим тем же способом для диагоналей с большей суммой координат.
3. У любой пары (a,b) сумма a + b конечна, поэтому она лежит на одной из этих диагоналей. Каждую пару включаем один раз, просматривая её диагональ без повторов.

Ответ: перечисление по диагоналям даёт каждой паре конечный натуральный номер. Так как каждая пара встретится и ни одна не будет записана дважды, множество пар натуральных чисел счётно.

Типичные ошибки

Ошибка: считать, что бесконечное множество не может быть равномощно своему подмножеству. Такое рассуждение переносят с конечных множеств, где часть обычно содержит меньше элементов; но для бесконечных множеств это не всегда верно. Проверка: построить соответствие n ↔ 2n и убедиться, что каждое чётное число имеет единственный прообраз.

Ошибка: назвать правило взаимно однозначным, проверив только, что оно каждому элементу первого множества назначает элемент второго. При этом можно не заметить, что часть элементов второго осталась без пары или несколько элементов первого ведут к одному. Проверка: пройти соответствие в обе стороны и подтвердить, что каждый элемент второго получается ровно один раз.

Ошибка: объявить множество счётным по списку, в котором есть пропуски или повторы. Повторы сами по себе не обязательно мешают перечислить множество, но в списке, используемом как взаимно однозначная нумерация, они означают, что элементам присвоены не уникальные позиции. Проверка: выяснить, появляется ли каждый элемент на конечном месте и встречается ли он там только один раз.

Ошибка: путать счётное множество с конечным. Слово «счётное» может навести на мысль, что элементов обязательно конечное число, однако в этом определении речь идёт о бесконечном множестве, которое можно занумеровать натуральными числами. Проверка: уточнить, есть ли последний элемент; если множество бесконечно, но его элементы получают номера 1, 2, 3 и так далее, оно счётное.

Связь с другими темами

Для понимания равномощности нужны понятия множества, его элементов и подмножества, а также знание натуральных чисел. Натуральные числа служат номерами, которыми перечисляют элементы счётного множества. Идея взаимно однозначного соответствия пригодится при сравнении бесконечных множеств и изучении их мощности. Она помогает не пересчитывать элементы, а доказывать равенство размеров с помощью точного правила сопоставления.

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

• Равномощность устанавливают взаимно однозначным соответствием.
• Для конечных множеств равномощность означает одинаковое число элементов.
• Бесконечное множество может быть равномощно своему собственному подмножеству.
• Счётное множество можно занумеровать натуральными числами.
• При нумерации нельзя пропускать элементы и повторять номера.
• Множество целых чисел можно перечислить последовательностью 0, 1, −1, 2, −2, …