Лысов Ю. П.

Каких чисел больше?Лысов Ю. П. Каких чисел больше? // Квант. — 1973. — № 12. — С. 26‍—‍28.‍‍

Что мы делаем, если желаем ответить на вопрос: кого в классе больше — девочек или мальчиков? Обычно мы поступаем так: пересчитываем девочек, мальчиков, а затем сравниваем полученные два числа. Этот способ даёт возможность сравнивать различные конечные множества. Но всегда ли мы им пользуемся?

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

Вы установили соответствие между зрителями и частью кресел. Этот принцип взаимного соответствия поможет нам в сравнении бесконечных множеств. (Впрочем, в неявном виде соответствие было установлено и в первом примере с девочками и мальчиками.)

Определение 1. Взаимно однозначным соответствием множеств $A$‍‍ и $B$‍‍ называется правило, которое каждому элементу множества $A$‍‍ ставит в соответствие один определённый элемент множества $B$‍,‍ так что при этом каждый элемент множества $B$‍‍ поставлен в соответствие ровно одному элементу множества $A$‍.‍

Задача 1. Установите взаимно однозначное соответствие между множеством $A$‍‍ натуральных чисел и множеством $B$‍‍ целых чисел, меньших $0$‍.‍

Натуральному числу $k$‍,‍ принадлежащему множеству $A$‍,‍ ставим в соответствие число $-k$‍,‍ принадлежащее множеству $B$‍.‍ Легко заметить, что это соответствие является взаимно однозначным.

Построенное соответствие показывает, что в множестве $A$‍‍ столько же элементов, сколько в $B$‍.‍ Полученный результат хорошо согласуется с нашими наглядными представлениями.

Задача 2. Установите взаимно однозначное соответствие между множеством $A$‍‍ натуральных чисел и множеством $B$‍‍ чётных натуральных чисел.

Натуральному числу $n$‍‍ поставим в соответствие чётное число $2n$‍.‍

Получаем, что натуральных чисел $(A)$‍‍ столько же, сколько и чётных натуральных $(B)$‍.‍ Но множество $B$‍‍ целиком содержится в множестве $A$‍.‍ Нет ли здесь ошибки? Ошибки нет. Всё верно, и в этом легко убедиться, если на одной числовой прямой отметить натуральные числа, а на другой — чётные и расположить эти прямые одну под другой (см. рисунок; на прямых разный масштаб).

Рисунок

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

Определение 2. Два множества $A$‍‍ и $B$‍‍ называются эквивалентными (количественно эквивалентными, равномощными), если между ними существует взаимно однозначное соответствие.

Задача 3. Докажите, что множество всех целых чисел эквивалентно множеству всех натуральных чисел.

Мы видим, что целые числа расположены на прямой не так, как натуральные, но всё-таки эти множества эквивалентны. Множества, эквивалентные натуральному ряду, для упрощения формулировок, называют счётными множествами.

Определение 3. Множество называется счётным, если оно эквивалентно множеству натуральных чисел, т. е. элементы этого множества можно выписать в строчку в соответствии с присвоенными им номерами.

В множестве целых чисел у каждого элемента имеются два «соседних». Может быть, в множестве, в котором не для каждого элемента можно указать «соседа», будет больше элементов, чем в счётном? Рассмотрим, например, множество правильных дробей. Для любых двух дробей $a$‍‍ и $b$‍‍ ($a \lt b$‍)‍ найдётся правильная дробь $c$‍‍ такая, что $a \lt c \lt b$‍,‍ т. е. «соседа» нет. И тем не менее это множество тоже счётно.

Задача 4. Докажите, что множество правильных дробей счётно.

Указание. Воспользуйтесь тем, что число правильных дробей со знаменателем, равным $N$‍,‍ конечно.

Задача 5. Докажите, что множество всех рациональных чисел счётно.

Решение задачи 5 можно получить, используя в качестве леммы задачу 4.

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

Задача 6. Докажите, что нельзя установить взаимно однозначное соответствие между множеством натуральных чисел и множеством бесконечных последовательностей из 0 и 1.

Решение этой задачи приведено на с. 8, но если вы ещё его не читали, попробуйте решить задачу самостоятельно. (Автор статьи знаком с большим количеством школьников, решивших её.)

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

Задача 7. Множество всевозможных русских слов счётно (мы, разумеется, считаем, что каждое слово состоит из конечного числа букв).

Задача 8. Множество всевозможных конечных наборов целых чисел счётно.

Если учесть, что любое уравнение степени $n$‍‍ имеет не более $n$‍‍ корней, то легко получается решение следующей задачи.

Задача 9. Множество чисел, каждое из которых является решением какого-то уравнения с целыми коэффициентами, счётно.

Множество чисел из задачи 9 называется множеством алгебраических чисел. Докажите, что все рациональные числа и всевозможные комбинации радикалов и рациональных чисел являются алгебраическими числами. Алгебраическими являются и некоторые числа, которые нельзя записать в радикалах (существование таких чисел в 1824 году доказал норвежский математик Нильс Хенрик Абель). Из задач 6 и 9 следует существование неалгебраических чисел. Такие числа называются трансцендентными.

В заключение предлагаем вашему вниманию более трудные задачи.

Задача 10. Множество $M$‍‍ состоит из восьмёрок, лежащих на плоскости и не пересекающих друг друга (восьмёрка — пара касающихся окружностей, каждая из которых может быть любого размера). Докажите, что $M$‍‍ конечно или счётно.

Нетрудно заметить, что, располагая на плоскости непересекающиеся буквы «Г» или «О», можно получить несчётное множество. Существует ли ещё какая-нибудь буква, обладающая тем же свойством, что и восьмёрка?

Задача 11. Множество $M$‍‍ состоит из букв «Т», лежащих на плоскости и не пересекающих друг друга. Докажите, что $M$‍‍ конечно или счётно.

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

Задача 12. Число $x_0$‍‍ называется максимумом функции $f(x)$‍,‍ если существует положительное число $\delta$‍‍ такое, что $f(x)$‍‍ в интервале $(x_0 - \delta,\ x_0 + \delta)$‍‍ больше всякого другого значения функции в этом интервале. Докажите, что множество максимумов любой функции конечно или счётно.