Парадокс Рассела - Russell's paradox

В математической логике , парадокс Рассела (также известный как антиномии Рассела ), является теоретико-множественным парадокс обнаружен британским философом и математиком Бертраном Расселом в 1901. парадокс шоу Рассела , что каждая теория множеств , которая содержит неограниченный принцип понимания приводит к противоречиям. Парадокс был открыт независимо в 1899 году немецким математиком Эрнстом Цермело . Однако Цермело не опубликовал эту идею, которая оставалась известной только Дэвиду Гильберту , Эдмунду Гуссерлю и другим ученым в Институте.Геттингенский университет . В конце 1890-х годов Георг Кантор, считавшийся основателем современной теории множеств, уже осознал, что его теория приведет к противоречию, о чем он письменно сообщил Гильберту и Ричарду Дедекинду .

Согласно принципу неограниченного понимания, для любого достаточно четко определенного свойства существует набор всех и только объектов, обладающих этим свойством. Пусть R будет множеством всех множеств, которые не являются членами самих себя. Если R не является членом самого себя, то из его определения следует, что он является членом самого себя; если он является членом самого себя, то он не является членом самого себя, поскольку это набор всех множеств, которые не являются членами самих себя. Возникающее противоречие - парадокс Рассела. В символах:

Рассел также показал, что версия парадокса может быть выведена в аксиоматической системе, построенной немецким философом и математиком Готлобом Фреге , тем самым подрывая попытку Фреге свести математику к логике и подвергая сомнению программу логики . Два влиятельных способа избежать парадокса оба были предложены в 1908 году: собственный Рассела теории типа и теории множеств Цермело . В частности, аксиомы Цермело ограничивали принцип неограниченного понимания. С дополнительным вкладом Абрахама Френкеля теория множеств Цермело превратилась в стандартную теорию множеств Цермело – Френкеля (широко известную как ZFC, если включает аксиому выбора ). Основное различие между решением Рассела и Цермело парадокса состоит в том, что Цермело модифицировал аксиомы теории множеств , сохранив стандартный логический язык, в то время как Рассел модифицировал сам логический язык. Язык ZFC с помощью Торальфа Сколема оказался языком логики первого порядка .

Неформальная презентация

Большинство часто встречающихся наборов не являются членами самих себя. Например, рассмотрим набор всех квадратов на плоскости . Этот набор сам по себе не является квадратом на плоскости, поэтому он не является членом самого себя. Назовем набор «нормальным», если он не является членом самого себя, и «ненормальным», если он является членом самого себя. Ясно, что каждый набор должен быть либо нормальным, либо ненормальным. Набор квадратов в плоскости нормальный. Напротив, дополнительный набор, содержащий все, что не является квадратом на плоскости, сам по себе не является квадратом на плоскости, поэтому он является одним из его собственных элементов и поэтому является ненормальным.

Теперь мы рассматриваем множество всех нормальных множеств, R , и пытаемся определить, является ли R нормальным или ненормальным. Если бы R был нормальным, он содержался бы в наборе всех нормальных множеств (сам) и, следовательно, был бы ненормальным; с другой стороны, если бы R был ненормальным, он не содержался бы во множестве всех нормальных множеств (сам) и, следовательно, был бы нормальным. Это приводит к выводу, что R не является ни нормальным, ни ненормальным: парадокс Рассела.

Официальная презентация

Термин « наивная теория множеств » используется по-разному. В одном случае наивная теория множеств представляет собой формальную теорию, которую мы можем назвать NST, которая сформулирована на языке первого порядка с бинарным нелогическим предикатом и включает в себя аксиому экстенсиональности :

и схема аксиомы неограниченного понимания :

для любой формулы с переменной x как свободной переменной внутри . Подставим для . Затем путем экзистенциальной реализации (повторного использования символа ) и универсальной реализации мы имеем

противоречие. Следовательно, NST несовместим .

Теоретико-множественные ответы

Из принципа взрыва в классической логике , любое предложение может быть доказано от противного . Следовательно, наличие противоречий, подобных парадоксу Рассела, в аксиоматической теории множеств катастрофически; поскольку, если какая-либо формула может быть доказана, она разрушает общепринятый смысл истины и лжи. Кроме того, поскольку теория множеств рассматривалась как основа для аксиоматического развития всех других разделов математики, парадокс Рассела поставил под угрозу основы математики в целом. Это мотивировало множество исследований на рубеже 20-го века с целью разработки последовательной (свободной от противоречий) теории множеств.

В 1908 году Эрнст Цермело предложил аксиоматизацию теории множеств, которая позволила избежать парадоксов наивной теории множеств, заменив произвольное понимание множеств более слабыми аксиомами существования, такими как его аксиома разделения ( Aussonderung ). Модификации этой аксиоматической теории, предложенные в 1920-х годах Абрахамом Френкелем , Торальфом Сколемом и самим Цермело, привели к появлению аксиоматической теории множеств под названием ZFC . Эта теория получила широкое признание после того, как аксиома выбора Цермело перестала быть спорной, и ZFC остается канонической аксиоматической теорией множеств до наших дней.

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

ZFC ничего не говорит о типах, хотя в совокупной иерархии есть понятие слоев, которые напоминают типы. Сам Цермело никогда не принимал формулировку ZFC Сколема на языке логики первого порядка. Как отмечает Хосе Феррейрос, Цермело вместо этого настаивал на том, что «пропозициональные функции (условия или предикаты), используемые для отделения от подмножеств, а также функции замены, могут быть« полностью произвольными » [ganz trustbig ]»; современная интерпретация этого утверждения состоит в том, что Цермело хотел включить количественную оценку более высокого порядка , чтобы избежать парадокса Сколема . Примерно в 1930 году Цермело также ввел (очевидно, независимо от фон Неймана) аксиому основания , таким образом, как отмечает Феррейрос, «запретив« круговые »и« необоснованные »множества, он [ZFC] включил в себя одну из важнейших мотиваций TT [ теория типов] - принцип типов аргументов ». Этот ZFC 2-го порядка, предпочитаемый Цермело, включая аксиому основания, позволил создать богатую кумулятивную иерархию. Феррейрос пишет, что «« слои »Цермело по сути те же, что и типы в современных версиях простой TT [теории типов], предложенной Геделем и Тарским. Кумулятивную иерархию, в которой Цермело развивал свои модели, можно описать как вселенную совокупности TT, в котором разрешены трансфинитные типы (как только мы приняли импредикативную точку зрения, отказавшись от идеи, что классы конструируются, принятие трансфинитных типов не является неестественным). "по существу о тех же предполагаемых объектах. Основное отличие состоит в том, что TT опирается на сильную логику более высокого порядка, в то время как Цермело использует логику второго порядка, а ZFC также может иметь формулировку первого порядка." Описание "первого порядка кумулятивной иерархии намного слабее, как показывает существование счетных моделей (парадокс Сколема), но она обладает некоторыми важными преимуществами ».

В ZFC для данного набора A можно определить набор B, который состоит именно из наборов в A , которые не являются членами самих себя. B не может быть в A по тем же рассуждениям, что и в парадоксе Рассела. Этот вариант парадокса Рассела показывает, что ни один набор не содержит всего.

Благодаря работе Цермело и других, особенно Джона фон Неймана , структура того, что некоторые считают «естественными» объектами, описанными ZFC, в конечном итоге стала ясной; они являются элементами Вселенной фона Неймана , V , построенной вверх от пустого множества с помощью трансфинитно итерации на множество мощности операции. Таким образом , теперь можно снова о причине множеств в не-аксиоматической моды , не вступая в противоречие парадокс Рассела, а именно путем рассуждений об элементах V . Является ли это уместно думать множеств в этом случае является предметом спора среди конкурирующих точек зрения на философию математики .

Другие решения парадокса Рассела с базовой стратегией, более близкой к теории типов , включают « Новые основы» Куайна и теорию множеств Скотта-Поттера . Еще один подход состоит в том, чтобы определить отношение множественного членства с соответствующим образом модифицированной схемой понимания, как в теории множеств двойного расширения .

История

Рассел открыл парадокс в мае или июне 1901 года. По его собственному отчету в своем « Введении в математическую философию » 1919 года он «попытался обнаружить некоторую ошибку в доказательстве Кантора о том, что не существует величайшего кардинала». В письме 1902 года он объявил Готтлобу Фреге об открытии парадокса в Begriffsschrift Фреге 1879 года и сформулировал проблему с точки зрения как логики, так и теории множеств, и, в частности, с точки зрения определения функции Фреге :

Есть только один момент, в котором я столкнулся с трудностью. Вы утверждаете (стр. 17 [стр. 23 выше]), что функция тоже может действовать как неопределенный элемент. Раньше я в это верил, но теперь эта точка зрения кажется мне сомнительной из-за следующего противоречия. Пусть w будет предикатом: быть предикатом, который не может быть предикатом сам по себе. Можно ж быть предикат себя? Из каждого ответа следует обратное. Следовательно, мы должны заключить, что w не является предикатом. Точно так же не существует класса (как совокупности) тех классов, которые, взятые как совокупность, не принадлежат самим себе. Из этого я прихожу к выводу, что при определенных обстоятельствах определяемая коллекция [Менге] не образует целостности.

Рассел продолжит подробное рассмотрение этого вопроса в своих Основах математики 1903 года , где он повторил свою первую встречу с парадоксом:

Прежде чем отказаться от фундаментальных вопросов, необходимо более подробно изучить уже упомянутое сингулярное противоречие в отношении предикатов, не предсказуемых сами по себе. ... Могу упомянуть, что меня привели к этому, когда я пытался согласовать доказательство Кантора ... "

Рассел написал Фреге о парадоксе, когда Фреге готовил второй том своей Grundgesetze der Arithmetik . Фреге очень быстро ответил Расселу; появилось его письмо от 22 июня 1902 г. с комментарием ван Хейенурта в Heijenoort 1967: 126–127. Затем Фреге написал приложение, признающее парадокс, и предложил решение, которое Рассел поддержал в своих Принципах математики , но позже некоторые сочли его неудовлетворительным. Со своей стороны, Рассел работал в типографии и добавил приложение о доктрине шрифтов .

Эрнст Цермело в своем (1908) новом доказательстве возможности хорошего упорядочения (опубликованном в то же время, когда он опубликовал «первую аксиоматическую теорию множеств») претендовал на предшествующее открытие антиномии в наивной теории множеств Кантора. Он заявляет: «И все же, даже элементарная форма, которую Рассел 9 придал теоретико-множественным антиномиям, могла бы убедить их [Й. Кениг, Журден, Ф. Бернштейн], что решение этих трудностей не следует искать в капитуляции. упорядоченности, но только в подходящем ограничении понятия множества ». В сноске 9 он заявляет о своем требовании:

9 1903 , стр. 366–368. Однако я сам открыл эту антиномию, независимо от Рассела, и передал ее до 1903 года профессору Гильберту среди других .

Фреге послал копию своей « Grundgesetze der Arithmetik» Гильберту; как отмечалось выше, в последнем томе Фреге упоминался парадокс, о котором Рассел сообщил Фреге. Получив последний том Фреге 7 ноября 1903 года, Гильберт написал Фреге письмо, в котором сказал, ссылаясь на парадокс Рассела: «Я полагаю, что доктор Цермело открыл его три или четыре года назад». Письменное изложение фактического аргумента Цермел было обнаружено в Наследстве от Эдмунда Гуссерля .

В 1923 году Людвиг Витгенштейн предложил «избавиться» от парадокса Рассела следующим образом:

Причина, по которой функция не может быть собственным аргументом, заключается в том, что знак функции уже содержит прототип ее аргумента и не может содержать самого себя. Ведь предположим, что функция F (fx) может быть собственным аргументом: в этом случае будет предложение F (F (fx)) , в котором внешняя функция F и внутренняя функция F должны иметь разные значения, поскольку внутренний имеет вид O (fx), а внешний - вид Y (O (fx)) . Только буква «F» является общей для этих двух функций, но сама по себе буква ничего не означает. Это сразу становится ясно, если вместо F (Fu) написать (do): F (Ou). Оу = Фу . Это избавляет от парадокса Рассела. ( Логико-философский трактат, 3.333)

Рассел и Альфред Норт Уайтхед написали свои трехтомные « Основы математики», надеясь достичь того, чего не смог сделать Фреге. Они стремились устранить парадоксы наивной теории множеств , используя для этой цели теорию типов, которую они разработали. Хотя им удалось в какой-то мере обосновать арифметику, совсем не очевидно, что они сделали это чисто логическими средствами. Хотя Principia Mathematica избегает известных парадоксов и позволяет вывести большую часть математики, ее система порождает новые проблемы.

В любом случае Курт Гёдель в 1930–1931 годах доказал, что хотя логика большей части Principia Mathematica , ныне известной как логика первого порядка , является законченной , арифметика Пеано обязательно неполна, если она непротиворечива . Это очень широко, хотя и не повсеместно, рассматривается как доказательство невозможности завершения логицистской программы Фреге.

В 2001 году в Мюнхене прошла столетняя международная конференция, посвященная первой сотне лет парадокса Рассела, и ее труды были опубликованы.

Прикладные версии

Есть несколько версий этого парадокса, которые ближе к реальным ситуациям и могут быть более понятны нелогикам. Например, парадокс парикмахера предполагает, что парикмахер бреет всех мужчин, которые не бреются, и только мужчин, которые не бреются. Когда думаешь о том, должен ли парикмахер бриться или нет, начинает вырисовываться парадокс.

Легкое опровержение «непрофессиональных версий», таких как парадокс парикмахера, похоже, состоит в том, что такого парикмахера не существует или что у парикмахера алопеция, и поэтому он не бреется. Весь смысл парадокса Рассела состоит в том, что ответ «такого множества не существует» означает, что определение понятия множества в рамках данной теории неудовлетворительно. Обратите внимание на разницу между утверждениями «такой набор не существует» и «это пустой набор ». Это похоже на разницу между словами: «Ведра нет» и «Ведро пусто».

Заметным исключением из вышесказанного может быть парадокс Греллинга – Нельсона , в котором слова и значение являются элементами сценария, а не люди и стрижка. Хотя парадокс парикмахера легко опровергнуть, сказав, что такого парикмахера не существует (и не может ) существовать, невозможно сказать что-то подобное о значимом определенном слове.

Приложения и связанные темы

Расселоподобные парадоксы

Как показано выше для парадокса парикмахера, парадокс Рассела нетрудно расширить. Брать:

Сформируйте предложение:

<V> ээээээ <V> - это все (и только те), кто не <V> сам,

Иногда «все» заменяется «все <V> ers».

Примером может быть «краска»:

Краска эр , что краска все , (и только те) , которые не рисуют сами.

или "избрать"

Избранный или ( представитель ), что избранник все , что не выбирают сами.

Парадоксы, которые попадают в эту схему, включают:

  • Парикмахер с «бриться» .
  • Оригинальный парадокс Рассела с «содержать»: контейнер (набор), который содержит все (контейнеры), которые не содержат самих себя.
  • Греллинг-Нельсон парадокс с «описателем»: описатель (слово) , который описывает все слова, которые не описывают себя.
  • Парадокс Ричарда с «обозначать»: обозначение (число), которое обозначает все обозначения (числа), которые не обозначают сами себя. (В этом парадоксе всем описаниям чисел присваивается присвоенный номер. Термин «обозначающий все обозначающие (числа), не обозначающие самих себя» здесь называется Ричардом .)
  • «Я лгу.», А именно лжец парадокс и Эпименид парадокс , чье происхождение древние
  • Парадокс Рассела-Майхилла

Связанные парадоксы

Смотрите также

Примечания

использованная литература

Источники

внешние ссылки