Парадокс Рассела

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

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

${\text{Let }}R=\{x\mid x\not \in x\}{\text{, then }}R\in R\iff R\not \in R$

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

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

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

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

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

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

$\forall x\,\forall y\,(\forall z\,(z\in x\iff z\in y)\implies x=y)$

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

$\exists y\forall x(x\in y\iff \varphi (x))$

для любой формулы $\varphi$ с переменной x как свободной переменной внутри $\varphi$. Заменять $x\notin x$ для $\varphi (x)$ получить

$\exists y\forall x(x\in y\iff x\notin x)$

Затем путем экзистенциальной реализации (повторного использования символа $y$) и универсальная реализация у нас есть

$y\in y\iff y\notin y,$

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

последствия

До парадокса Рассела (и других подобных парадоксов, обнаруженных примерно в то же время, таких как парадокс Бурали-Форти ), общей концепцией идеи множества была «экстенсиональная концепция множества», как рассказали фон Нейман и Моргенштерн:

Множество — это произвольная совокупность объектов, причем на природу и количество этих объектов, элементов рассматриваемого множества, не налагается абсолютно никаких ограничений. Элементы составляют и определяют множество как таковое, без какого-либо упорядочения или каких-либо отношений между ними.

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

-

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

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

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

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

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

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

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

История

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

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

Рассел подробно изложил это в своей книге «Принципы математики» 1903 года , где он повторил свою первую встречу с парадоксом:

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

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

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

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

копию своей книги «Основы арифметики» Фреге отправил Гильберту ; как отмечалось выше, в последнем томе Фреге упоминается парадокс, о котором Рассел сообщил Фреге. Получив последний том Фреге 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, надеясь достичь того, чего не смог сделать Фреге. Они стремились устранить парадоксы наивной теории множеств, используя теорию типов, которую они разработали для этой цели. Хотя им удалось в некотором роде обосновать арифметику, совсем не очевидно, что они сделали это чисто логическими средствами. Хотя Principia Mathematica избежала известных парадоксов и позволила вывести значительную часть математических знаний, ее система породила новые проблемы.

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

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

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

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

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

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

Один из способов драматизировать парадокс заключается в следующем: предположим, что каждая публичная библиотека должна составить каталог всех своих книг. Поскольку каталог сам по себе является одной из книг библиотеки, некоторые библиотекари включают его в каталог для полноты картины; в то время как другие опускают ее, поскольку это одна из библиотечных книг, что само собой разумеется. А теперь представьте, что все эти каталоги отправлены в национальную библиотеку. Некоторые из них включают себя в свои списки, другие — нет. Национальный библиотекарь составляет два генеральных каталога — один из всех каталогов, в которых они указаны, и один из всех тех, в которых нет.

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

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

Рассела

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

• ⟨V⟩ Переходный глагол , который можно применить к его существительной форме.

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

, Тот ⟨V⟩ что ⟨V⟩ — это все (и только те), кто не ⟨V⟩ сами,

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

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

Художник , который рисует, — это все (и только те), кто не рисует себя.

или «избрать»

Избранный — или ( представитель ), который избирает, это все, кто не избирает себя.

В ​​8-го сезона эпизоде «Теории большого взрыва » «Вторжение Скайуокера» Шелдон Купер анализирует песню « Play That Funky Music » и приходит к выводу, что тексты представляют собой музыкальный пример парадокса Рассела.

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

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

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

• Парадокс Бурали -Форти о типе порядка всех хорошо упорядоченных
• Парадокс Клини -Россера , показывающий, что исходное лямбда-исчисление несовместимо, с помощью самоотрицающего утверждения.
• Парадокс Карри (названный в честь Haskell Curry ), не требующий отрицания
• Самый маленький неинтересный целочисленный парадокс
• Парадокс Жирара в теории типов

См. также

• Основной закон V
• Диагональный аргумент Кантора - Доказательство в теории множеств
• Теоремы Гёделя о неполноте - Ограничительные результаты в математической логике
• Первая проблема Гильберта - Предложение математической логики. Страницы с краткими описаниями целей перенаправления.
• « Об обозначении »
• Парадоксы теории множеств
• Парадокс Куайна
• Самоссылка
• Странная петля - циклическая структура, проходящая через несколько уровней иерархической системы.
• Универсальный набор - математический набор, содержащий все объекты.

Источники

• Поттер, Майкл (15 января 2004 г.), Теория множеств и ее философия , Clarendon Press ( Oxford University Press ), ISBN  978-0-19-926973-0
• ван Хейеноорт, Жан (1967), От Фреге до Гёделя: Справочник по математической логике, 1879–1931, (третье издание 1976 г.) , Кембридж, Массачусетс: Издательство Гарвардского университета , ISBN  0-674-32449-8
• Ливио, Марио (6 января 2009 г.), Бог — математик? , Нью-Йорк: Саймон и Шустер , ISBN.  978-0-7432-9405-8

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

• Каплан, Джеффри (2022). «Парадокс Рассела – простое объяснение глубокой проблемы» . Ютуб . Проверено 25 ноября 2023 г.

• «Парадокс Рассела» . Интернет-энциклопедия философии .
• Ирвин, Эндрю Дэвид (2016). «Парадокс Рассела» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• Вайсштейн, Эрик В. «Антиномия Рассела» . Математический мир .
• «Парадокс Рассела» . Разрезать узел . Проверено 25 ноября 2023 г.