Введем несколько терминов. В математике множество — это набор объектов. Это пример математического определения — такого, что описывает новое понятие (а именно, «множество») повседневным языком. Обычно мы обозначаем множество прописной латинской буквой, например S, T или U. Существует целая ветвь математики под названием «теория множеств», она лежит в основании большинства других областей математики. Отцом современной теории множеств обычно считают Георга Кантора (1845–1918). Ее основание относится к концу девятнадцатого и началу двадцатого века.
Хотя в этой книге не место излагать введение в теорию множеств, мы определим некоторые термины, полезные для дальнейшего обсуждения. Пусть S — множество. Мы говорим, что x является элементом множества S и записываем 
, если x — один из объектов, входящих в множество S. В качестве примера рассмотрим множество S положительных целых чисел:
Тогда 1 — элемент множества S. А также 2 — элемент множества S и 3 тоже и так далее. В таком случае мы записываем 
, 
, 
и так далее. Отметим, что π не является элементом множества S. Раз π=3,14159265... не является целым числом, оно не является и объектом из S. Записывают это так: 
.
Теперь можно вернуться к обсуждению саги о теории множеств. В 1902 г. Готтлоб Фреге (1848–1925) радовался тому, что второй том его значительного труда «Основные законы арифметики» [FRE2] находился в печати, когда получил вежливое и скромное письмо от Бертрана Расселла, предложившего такой парадокс[29]:
Пусть S — набор всех множеств, которые не являются элементом себя. Может ли S быть элементом множества S?
Что здесь парадоксального[30]?
Проблема вот в чем. Если 
, то по определению множества оно не является элементом множества S. А если S не является элементом множества S, то, согласно тому же определению, S — элемент множества S. В любом случае обнаруживается противоречие.
Сейчас самое время вспомнить Архимедов закон исключенного третьего. Должно выполняться что-то одно: или , или 
, но на самом деле в обоих случаях ситуация приводит к противоречию. В этом и состоит парадокс Расселла. Фреге пришлось еще раз обдумать свою книгу и сделать заметные поправки, чтобы справиться с вопросами, поднятыми парадоксом Расселла[31].
После интенсивной переписки с Расселлом Фреге модифицировал одну из своих аксиом и добавил приложение, объясняющее, как эта модификация учитывает вопросы, поднятые парадоксом Расселла. К несчастью, эта модификация отменяла некоторые результаты из первого тома работы Фреге — уже опубликованного. Второй том в конце концов появился на свет ([FRE2]). Но Фреге был до того обескуражен этой историей, что продуктивность его исследований заметно снизилась. Третий том так и не вышел.
Уже после смерти Фреге Лесневский доказал, что обновленная система аксиом, вышедшая из печати, несовместна. Тем не менее Фреге считается одной из самых важных фигур в основаниях математики. Он был одним из первых на пути формализации правил, по которым живет математика, и в этом смысле он был настоящим пионером. Многие соглашаются, что его более ранняя работа «Begriffsschrift und andere Aufsätze» [FRE1] — самая важная из когда-либо написанных работ по логике. Она закладывает фундамент современной логики. Пол Коэн, один из самых выдающихся логиков двадцатого века, так описывает вклад Фреге:
После публикации эпической работы Фреге «Begriffsschrift» в 1879 г. понятие формальной системы получило ясную форму. Важная работа такого рода была проделана Булем и Пирсом, позднее Пеано продемонстрировал подобный подход, но только с работой Фреге, впервые в истории человеческой мысли, понятие логического вывода получило полную точную формулировку. Работа Фреге включает не только описание языка (теперь мы можем называть его «машинным языком»), но и описание правил работы на этом языке; сейчас мы называем его исчислением предикатов… Но это была веха на пути. Впервые стало можно точно говорить о доказательствах и аксиоматических системах. Работа широко воспроизводилась другими авторами, например Расселом и Уайтхедом, которые дали свои формулировки обозначения, и даже Гильбертом были сделаны попытки переформулировать основные понятия формальной системы.
30
Вдумчивый читатель может задаться вопросом: а возможно ли для множества быть элементом самого себя? Здесь есть что-то от жонглирования словами, и выглядит оно сомнительно. Однако рассмотрим такое множество S:
Набор всех множеств, которые можно описать менее чем пятьюдесятью словами.
Заметьте, что S — множество и его можно описать менее чем пятьюдесятью словами. Ага! Тогда да, конечно же, S — элемент самого себя.
31
Имеется популярная версия парадокса Расселла. В некотором городе по договору парикмахер (подразумевается мужчина) бреет каждого мужчину, который не бреется сам. Парикмахер не соглашается прикасаться ни к одному мужчине, который когда-либо брился сам. Кто бреет парикмахера? Если он бреется сам, то по договоренности он относится к тем, кого парикмахер не бреет. А если парикмахер не бреется сам, то относится к тем, кого парикмахер брить должен. В любом случае получается противоречие. Такой парикмахер не может существовать.