Первая трудность теории множеств состоит в самой дефиниции понятия «множество», так как его очень сложно определить, не используя само понятие «множество» или один из его синонимов — объединение, группа и т. д.
Одно из наиболее удачных определений, в котором не используются синонимы слова «множество» (по крайней мере, явным образом), принадлежит Бертрану Расселу: «Множество есть совокупность различных элементов, мыслимая как единое целое». Это интересная точка зрения, так как в ней понятие множества определяется как результат мыслительной деятельности, и это означает, что речь идет о фундаментальном понятии.
* * *
СЧЕТ С ПОМОЩЬЮ КАМНЕЙ
Интересно отметить, что человек научился считать раньше, чем появились системы счисления, поэтому, вопреки распространенной точке зрения, можно утверждать, что понятие биективного отображения появилось одновременно с понятием числа или даже раньше. Например, пастуху, который хотел сосчитать число овец в стаде, требовалась сумка с камнями. Когда очередная овца выходила из загона, пастух вынимал из сумки один камень. Вечером, пригнав овец обратно в загон, пастух устанавливал взаимно однозначное соответствие между овцами и камнями. (От латинского слова calculus — «камень» происходит, например, современное слово «калькулятор».)
* * *
Как мы уже говорили, фундаментальным также является понятие подсчета элементов множества. При счете мы в действительности сравниваем элементы двух множеств. Например, если мы хотим узнать, сколько человек находится в помещении (то есть сколько элементов содержит множество людей, находящихся в помещении), мы берем за основу известное множество, образованное натуральными числами 1, 2, 3, …, и присваиваем каждому человеку в помещении порядковый номер без повторений. Закончив подсчет, мы смотрим, какое число мы присвоили последним. Если это число равно, например, 23, мы говорим, что в помещении находится 23 человека. В действительности мы сравнили два множества — множество людей и множество чисел {1, 2, 3, …, 22, 23}, установив так называемое взаимно однозначное соответствие. Взаимно однозначное соответствие можно установить между множествами разной природы, важно лишь, чтобы при этом соблюдались определенные правила. Например, если даны множество заглавных букв {А, F, H, P, V} и множество строчных букв {a, b, с, d, е}, то между ними можно установить следующее отношение:
Каждому элементу первого множества должен соответствовать один и только один элемент второго множества, и наоборот. Это единственное правило, которому должны подчиняться биективные, то есть взаимно однозначные отображения.
На рисунке ниже мы также видим соответствия:
Однако они не удовлетворяют этому правилу.
Таким образом, Кантор определил простейшее понятие подсчета, а также ввел понятие кардинальности множества.
Если мы рассмотрим множества, между которыми можно установить биективное отображение, то увидим, что число элементов в этих множествах одинаково.
Но если одно множество состоит из четырех элементов, а другое — из трех, между ними нельзя установить биективное отображение: какой-либо элемент остается без пары или какому-либо элементу будет сопоставлено сразу несколько элементов.
Кантор определил эквивалентность множеств следующим образом: «Кардинальность двух множеств одинакова, если между ними можно установить биективное (взаимно однозначное) отображение». О множествах с одинаковой кардинальностью говорят, что они являются равномощными, то есть имеют одинаковое число элементов.
Таким образом, если дано произвольное множество, например коробка цветных карандашей, которое мы обозначим А, и можно установить взаимно однозначное соответствие между множеством A и множеством N = {1, 2, 3, 4, 5, 6}, то говорят, что кардинальность А и N одинакова:
|A| — |N| = 6.
Может показаться, что мы усложняем очевидное, но это впечатление обманчиво: новый логический аппарат позволил дать четкое определение бесконечному множеству.
Для этого сначала определим, что такое конечное множество. Непустое множество А (иными словами, содержащее как минимум один элемент) является конечным, если для некоторого числа n множество А имеет ту же кардинальность, что и множество {1, 2, 3, …, n}. Следовательно, n будет числом элементов множества A. В противном случае говорят, что множество А бесконечное.
Аналогично: множество А бесконечно, если существует собственное подмножество В множества А, имеющее ту же кардинальность, что и само А. В противном случае множество А является конечным.
На последнем определении стоит остановиться подробнее ввиду его чрезвычайной важности. Во-первых, следует пояснить, что понимается под собственным подмножеством. Это очень просто: если дано произвольное множество А, например {a, b, с, d}, его собственным подмножеством будет любое подмножество, которое можно составить из элементов А, при этом нельзя использовать их все. Примерами собственных подмножеств А будут:
{а} {а, Ь} {а, b, с} {а, с, d} {d} {b, с, d}.
В соответствии с вышесказанным кажется логичным, что между множеством и его собственным подмножеством нельзя установить взаимно однозначное соответствие: собственное подмножество всегда будет содержать меньше элементов, чем само множество.
Но существуют примеры, когда это не так. Рассмотрим — множество всех натуральных чисел и его собственное подмножество Р, образованное всеми четными числами. Очевидно, что между обоими множествами можно установить взаимно однозначное соответствие: для этого каждому натуральному числу n нужно поставить в соответствие это же число, умноженное на 2.
n —> 2n
В соответствии с этим
1 —> 2
2 —> 4
3 —> 6
…
Иными словами, каждому натуральному числу соответствует четное число и, напротив, каждому четному числу соответствует натуральное число. Это означает, что кардинальность этих множеств одинакова, и утверждение «существует столько же натуральных чисел, сколько четных» вовсе не парадокс, хотя оно явно противоречит интуиции. Таким образом, альтернативное определение бесконечного множества звучит так: множество является бесконечным, если между этим множеством и какой-либо из его частей (каким-либо его собственным подмножеством) можно установить взаимно однозначное соответствие.
В этом случае парадокс, сформулированный Галилеем (см. главу 3), — это уже не парадокс, а констатация факта: множество натуральных чисел является бесконечным.
Путем аналогичных рассуждений можно доказать, что множество натуральных чисел и множество целых чисел имеют одинаковую кардинальность. Чтобы подтвердить это, достаточно установить взаимно однозначное соответствие между ними, сопоставив всем положительным числам четные, а всем отрицательным — нечетные. Таким образом, существует столько же целых чисел, сколько натуральных.
Счетные множества
Кантор также сформулировал очень важное понятие счетного множества. По определению, множество А называется счетным, если можно установить взаимно однозначное соответствие между А и подмножеством . В основе этого определения лежит очень простая идея, которую мы часто используем в повседневной жизни.
Когда мы заявляем, что места в зале кинотеатра пронумерованы, мы говорим о взаимно однозначном соответствии между подмножеством натуральных чисел и множеством кресел и сопоставляем каждому креслу число.
Мы уже показали, что множество целых чисел является счетным. Далее Кантор получил поистине удивительный результат: множество рациональных чисел также является счетным. Он доказал, что существует столько же рациональных чисел, сколько и натуральных. Чтобы установить соответствие между натуральными и рациональными числами, Кантор использовал настолько простую схему, что остается только удивляться, почему никто не сделал этого раньше. Возможно, причина в том, что никто не считал это возможным, так как это противоречит элементарной интуиции.
Схема, придуманная Кантором, такова. Нужно построить таблицу рациональных чисел (напомним, что речь идет о дробях) следующим образом: в первой строке записываются дроби, числитель которых равен 1, во второй — дроби, числитель которых равен 2, в третьей — 3 и т. д. Вычеркнем из каждой строки повторяющиеся дроби. Например, 2/2 — это то же самое, что 1/1 или 3/3, 2/4 — то же, что и 1/2, и т. д. Построив таблицу, обойдем все числа в порядке, указанном стрелками, начиная с 1/1. Мы обойдем все рациональные числа ровно один раз. Таким образом, взаимно однозначное соответствие между натуральными и рациональными числами устанавливается следующим образом:
