Парадо́кс Ра́ссела (антино́мия Ра́ссела, также парадо́кс Ра́ссела — Це́рмело) — теоретико-множественный парадокс (антиномия), открытый в 1901 году. британским математиком Бертраном Расселом и демонстрирующий противоречивость логической системы Фреге, являвшейся ранней попыткой формализации наивной теории множеств Георга Кантора. Был открыт ранее, но не опубликован Эрнстом Цермело.
На неформальном языке парадокс можно описать следующим образом. Условимся называть множество «обычным», если оно не является своим собственным элементом. Например, множество всех людей является «обычным», так как само множество — не человек. Примером «необычного» множества является множество всех множеств, так как оно само является множеством, а следовательно, само является собственным элементом.
Можно рассмотреть множество, состоящее только из всех «обычных» множеств, такое множество называется ра́сселовским мно́жеством. Парадокс возникает при попытке определить, является ли это множество «обычным» или нет, то есть содержит ли оно себя в качестве элемента. Есть две возможности. С одной стороны, если оно «обычное», то оно должно включать себя в качестве элемента, так как оно по определению состоит из всех «обычных» множеств. Но тогда оно не может быть «обычным», так как «обычные» множества — это те, которые себя не включают. Остаётся предположить, что это множество «необычное». Однако оно не может включать себя в качестве элемента, так как оно по определению должно состоять только из «обычных» множеств. Но если оно не включает себя в качестве элемента, то это «обычное» множество. В любом случае получается противоречиеАнтиномия Рассела // Словарь по логике. Ивин А. А., Никифоров А. Л. — М.: Туманит, ВЛАДОС, 1997. — 384 с. — ISBN 5-691-00099-3..
Формулировка парадокса Парадокс Рассела можно сформулировать в наивной теории множеств. Следовательно, наивная теория множеств является противоречивой. Противоречив фрагмент наивной теории множеств, который можно определить как теорию первого порядка с бинарным отношением принадлежности и схемой свёртывания: для каждой логической формулы с одной свободной переменной в наивной теории множеств есть аксиома . Эта схема аксиом говорит, что для всякого условия существует множество состоящее из тех которые удовлетворяют условию .
Этого оказывается достаточно, чтобы сформулировать парадокс Рассела следующим образом. Пусть есть формула (То есть означает, что множество не содержит себя в качестве элемента, или, в нашей терминологии, является «обычным» множеством.) Тогда, по аксиоме свёртывания, найдётся множество (расселовское множество) такое, что . Так как это верно для любого то верно и для То есть
Из этого следует, что в наивной теории множеств выводится противоречие.
Парадокс не возник бы, если предположить, что расселовского множества не существует. Однако само такое предположение парадоксально: в канторовской теории множеств считается, что любое свойство определяет множество элементов, удовлетворяющих этому свойству. Так как свойство множества быть «обычным» выглядит корректно определённым, то должно существовать множество всех «обычных» множеств. Сейчас такая теория называется наивной теорией множеств.
Популярные версии парадокса Существует несколько вариантов парадокса Рассела. В отличие от самого парадокса, они, как правило, не могут быть выражены на формальном языке.
Парадокс лжеца
Парадокс Рассела связан с известным ещё с античных времён парадоксом лжеца, который заключается в следующем вопросе. Дано высказывание: Данное высказывание — ложно. Истинно ли это высказывание или нет? Легко показать, что это высказывание не может быть ни истинным, ни ложным.
Рассел про этот парадокс писал:
Это древняя загадка, к которой никто не относился более, чем как к шутке, пока не было обнаружено, что этот вопрос имеет отношение к таким важным и практическим задачам, как существование наибольшего кардинального или ординального числа.
Сам Рассел так объяснял парадокс лжеца. Чтобы говорить что-нибудь о высказываниях, надо сначала определить само понятие «высказывания», при этом не используя не определённых пока понятий. Таким образом, можно определить высказывания первого типа, которые ничего не говорят о высказываниях. Потом можно определить высказывания второго типа, которые говорят о высказываниях первого типа, и так далее. Высказывание же «данное высказывание — ложно» не попадает ни под одно из этих определений, и таким образом не имеет смысла.
Парадокс брадобрея Рассел упоминает следующий вариант парадокса, сформулированный в виде загадки, которую ему кто-то подсказал. Пусть в некой деревне живёт брадобрей, который бреет всех жителей деревни, которые не бреются сами, и только их. Бреет ли брадобрей сам себя? Любой ответ приводит к противоречию. Рассел замечает, что этот парадокс не эквивалентен его парадоксу и легко решается. Действительно, точно так же, как парадокс Рассела показывает, что не существует расселовского множества, парадокс брадобрея показывает, что такого брадобрея просто не существует. Разница состоит в том, что в несуществовании такого брадобрея ничего удивительного нет: не для любого свойства найдётся брадобрей, который бреет людей, обладающих этим свойством. Однако то, что не существует множества элементов, заданных некоторым вполне определённым свойством, противоречит наивному представлению о множествах и требует объяснения.
Вариант о каталогах Наиболее близким по формулировке к парадоксу Рассела является следующий вариант его изложения: Библиографические каталоги — это книги, которые описывают другие книги. Некоторые каталоги могут описывать другие каталоги. Некоторые каталоги могут описывать даже сами себя. Можно ли составить каталог всех каталогов, которые не описывают сами себя? Парадокс возникает при попытке решить, должен ли этот каталог описывать сам себя. Несмотря на кажущуюся близость формулировок (это фактически парадокс Рассела, в котором вместо множеств используются каталоги), этот парадокс, так же, как и парадокс брадобрея, разрешается просто: такой каталог составить нельзя.
Парадокс Греллинга — Нельсона
Этот парадокс был сформулирован немецкими математиками и Леонардом Нельсоном в 1908 году. Он фактически является переводом первоначального варианта парадокса Рассела, изложенного им в терминах логики предикатов (см. письмо к Фреге ниже), на нематематический язык. Будем называть прилагательное рефлексивным, если это прилагательное обладает свойством, определяемым этим прилагательным. Например, прилагательные «русское», «многосложное» — обладают свойствами, которые они определяют (прилагательное «русское» является русским, а прилагательное «многосложное» является многосложным), поэтому они являются рефлексивными, а прилагательные «немецкое», «односложное» — являются нерефлексивными. Будет ли прилагательное «нерефлексивное» рефлексивным или нет? Любой ответ приводит к противоречию. В отличие от парадокса брадобрея, решение этого парадокса не такое простое. Нельзя просто сказать, что такого прилагательного («нерефлексивный») не существует, так как мы его только что определили. Парадокс возникает из-за того, что определение термина «нерефлексивный» некорректно само по себе. Определение этого термина зависит от значения прилагательного, к которому оно применяется. А так как слово «нерефлексивный» само является прилагательным в определении, возникает порочный круг.
История Рассел, вероятно, открыл свой парадокс в мае или июне 1901 года. Согласно самому Расселу, он пытался найти ошибку в доказательстве Кантора того парадоксального факта (известного как парадокс Кантора), что не существует максимального кардинального числа (или же множества всех множеств). В результате Рассел получил более простой парадокс. Рассел сообщил свой парадокс другим логикам, в частности Уайтхеду и Пеано. В своём письме к Фреге 16 июня 1902 года он писал, что обнаружил противоречие в «» — книге Фреге, опубликованной в 1879 году. Он изложил свой парадокс в терминах логики, а потом в терминах теории множеств, используя определение Фреге для функции:
Я испытал трудности только в одном месте. Вы утверждаете (стр. 17), что функция может сама выступать в качестве неизвестного. Раньше я тоже так считал. Но теперь такой взгляд мне кажется сомнительным из-за следующего противоречия. Пусть w предикат: «быть предикатом, который не приложим к самому себе». Может ли w быть приложим к самому себе? Из любого ответа следует обратное. Следовательно, мы должны заключить, что w — не предикат. Аналогично не существует класса (как целого) тех классов, которые, взятые как целое, не принадлежат себе. Отсюда я заключаю, что иногда определённое множество не формирует целостного образования.
Фреге получил письмо как раз в то время, когда завершил работу над вторым томом «Основных законов арифметики» (). У Фреге не было времени исправить свою теорию множеств. Он лишь добавил приложение ко второму тому с изложением и своим анализом парадокса, которое начиналось со знаменитого замечания:
Вряд ли с учёным может приключиться что-нибудь худшее, чем если у него из-под ног выбьют почву в тот самый момент, когда он завершит свой труд. Именно в таком положении оказался я, получив письмо от Бертрана Рассела, когда моя работа уже была завершена.
Далее Фреге предлагал следующий способ исправить свою теорию, чтобы избежать парадокса Рассела. Вместо аксиомы: , которая говорила, что можно построить множество элементов, удовлетворяющих свойству он предложил использовать следующую аксиому: , таким образом исключив возможность для множества быть элементом самого себя. Однако небольшая модификация парадокса Рассела доказывает, что и эта аксиома тоже приводит к противоречию: а именно, можно рассмотреть множество всех синглетонов таких, что , тогда утверждение будет антиномией.
Рассел опубликовал свой парадокс в своей книге «» в 1903 году.
Эрнст Цермело утверждал, что открыл этот парадокс, независимо от Рассела, и сообщил о нём до 1903 года Гильберту и другим. Это подтвердил и Гильберт, написав Фреге 7 ноября 1903 года, что он знал об этом парадоксе. Гильберт писал: «я думаю Цермело нашёл его года 3—4 назад… Я нашёл другие ещё более убедительные противоречия ещё 4—5 лет назад». Кроме того, в 1978 году в бумагах Эдмунда Гуссерля была обнаружена формулировка этого парадокса, которую Цермело сообщил Гуссерлю 16 апреля 1902 года. В этой формулировке доказывается, что множество M, содержащее все свои подмножества в качестве элементов, приводит к противоречию. Для доказательства рассматривается подмножество M, состоящее из множеств, которые не содержат себя сами.
Варианты решения В парадоксе Рассела нет ошибки: он действительно доказывает противоречивость наивной теории множеств. Чтобы избавиться от противоречия, нужно исправить теорию множеств так, чтобы она не допускала расселовское множество. Это можно сделать несколькими способами. Наиболее естественным путём является запрещение тем или иным способом множеств, которые могут содержать себя в качестве элемента. Таким образом будет запрещено и множество всех множеств (по крайней мере, совокупность всех множеств не будет сама являться множеством). Однако необходимо иметь в виду, что, с одной стороны, просто одного запрещения множеству иметь себя в качестве элемента недостаточно, чтобы избавиться от противоречия (как показала первая попытка Фреге исправить свою систему). С другой стороны, само по себе разрешение множествам включать себя в качестве элемента не приводит к противоречиям. Например, ничто не мешает создать каталог, который будет включать в себя все каталоги, в том числе описывать самого себя. Многие языки программирования позволяют контейнерам включать себя в качестве элемента. Существуют логические системы, свободные от парадоксов типа расселовских, которые позволяют множествам содержать себя (например, У. В. О. Куайна).
Ниже приведены несколько из возможных подходов к построению системы аксиом, свободной от расселовских парадоксов.
Теория типов Рассела