Парадокс Скулема

В логике и философии математической парадокс Скулема — кажущееся противоречие, возникающее из нисходящей теоремы Левенхайма-Скулема . Торальф Скулем (1922) был первым, кто обсудил, казалось бы, противоречивые аспекты теоремы и открыл относительность теоретико-множественных понятий, ныне известных как неабсолютность . Хотя это не настоящая антиномия, подобная парадоксу Рассела , результат обычно называется парадоксом и описывается Сколемом (1922: стр. 295) как «парадоксальное положение дел».

Парадокс Скулема заключается в том, что каждая счетная аксиоматизация теории множеств в логике первого порядка , если она непротиворечива , имеет модель счетную . Это кажется противоречивым, поскольку на основе тех же самых аксиом можно доказать предложение, которое интуитивно говорит (или точно говорит в стандартной модели теории), что существуют множества, которые не являются счетными. Таким образом, кажущееся противоречие заключается в том, что модель, которая сама по себе счетна и, следовательно, содержит только счетные множества, удовлетворяет предложению первого порядка, которое интуитивно утверждает, что «существуют несчетные множества».

Математическое объяснение парадокса, показывающее, что он не является противоречием в математике, дал Сколем (1922). Работа Скулема была резко воспринята Эрнстом Цермело , который выступал против ограничений логики первого порядка, но результат быстро был принят математическим сообществом.

Философские последствия парадокса Скулема получили много исследований. Одна из линий исследования ставит под вопрос, правильно ли утверждать, что любое предложение первого порядка на самом деле утверждает, что «существуют неисчислимые множества». Этот ход мыслей можно распространить на вопрос о том, является ли какое-либо множество несчетным в абсолютном смысле. Совсем недавно статья Хилари Патнэм «Модели и реальность» и ответы на нее привели к возобновлению интереса к философским аспектам результата Скулема.

Фон

Одним из самых ранних результатов в теории множеств , опубликованных Георгом Кантором в 1874 году, было существование несчетных множеств, таких как набор степеней натуральных чисел , набор действительных чисел и набор Кантора . Бесконечное множество X счетно, если существует функция, которая дает взаимно однозначное соответствие между X и натуральными числами, и несчетно, если такой функции соответствия нет. Когда Цермело предложил свои аксиомы теории множеств в 1908 году, он доказал на их основе теорему Кантора, чтобы продемонстрировать их силу.

Левенгейм (1915) и Сколем (1920, 1923) доказали теорему Левенгейма–Скулема . Нисходящая форма этой теоремы показывает, что если счетная первого порядка аксиоматизация удовлетворяется любой бесконечной структурой , то тем же аксиомам удовлетворяет некоторая счетная структура. В частности, это означает, что если версии аксиом Цермело теории множеств первого порядка выполнимы, они выполнимы в некоторой счетной модели. То же самое верно для любой последовательной аксиоматизации теории множеств первого порядка.

Парадоксальный результат и его математические последствия

Скулем (1922) указал на кажущееся противоречие между теоремой Левенгейма-Скулема, с одной стороны, из которой следует, что существует счетная модель аксиом Цермело, и теоремой Кантора, с другой стороны, которая утверждает, что существуют несчетные множества, и которая доказуемо на основе аксиом Цермело. «Насколько мне известно, — пишет Скулем, — никто не обратил внимания на это своеобразное и, по-видимому, парадоксальное положение вещей. В силу аксиом мы можем доказать существование высших мощностей... Как же тогда может быть, что вся область B [счетная модель аксиом Цермело] уже может быть пронумерована с помощью конечных положительных целых чисел?» (Сколем 1922, стр. 295, перевод Бауэра-Менгельберга).

Более конкретно, пусть B — счетная модель аксиом Цермело. Тогда существует некоторое множество u в B такое, что B удовлетворяет формуле первого порядка, утверждающей, что u несчетно. Например, u можно рассматривать как набор действительных чисел в B . Теперь, поскольку B счетно, существует только счетное число элементов c таких, что c ∈ u согласно B имеется только счетное количество элементов c в B , потому что изначально . Таким образом, оказывается, что u должно быть счетным. Это парадокс Скулема.

Скулем объяснил, почему не было противоречия. В контексте конкретной модели теории множеств термин «множество» относится не к произвольному множеству, а только к множеству, которое фактически включено в модель. Определение счетности требует, чтобы существовало определенное взаимно однозначное соответствие, которое само по себе является множеством. Таким образом, можно признать, что определенное множество u счетно, но не счетно в конкретной модели теории множеств, поскольку в модели нет множества, которое бы давало взаимно однозначное соответствие между u и натуральными числами в этой модели. модель. ^[1]

В теории множеств ZFC теорема Кантора представляет собой длинную формулу на формальном языке ZFC . То, что означает эта формула, дается в терминах структуры теории моделей . Если у ZFC есть модель, назовем ее $\mathrm {M}$ и его домен $\mathbb {M}$ . Толкование символа $\in$ , ${\mathcal {I}}(\in )$ , представляет собой набор упорядоченных пар элементов $\mathbb {M}$ - другими словами ${\mathcal {I}}(\in )$ является подмножеством $\mathbb {M} \times \mathbb {M}$ . Поскольку теорема Левенхайма – Скулема гарантирует, что $\mathbb {M}$ счетно, то так и должно быть $\mathbb {M} \times \mathbb {M}$ . Есть два особых элемента $\mathbb {M}$ ; они есть $\mathbb {N}$ и ${\mathcal {P}}(\mathbb {N} )$ . Отсюда следует, что существует просто счётно бесконечное количество упорядоченных пар в ${\mathcal {I}}(\in )$ формы $\langle x,{\mathcal {P}}(\mathbb {N} )\rangle$ , потому что $\mathbb {M} \times \mathbb {M}$ является счетным. Однако в этом нет противоречия с теоремой Кантора, поскольку она просто утверждает, что «нет элемента $\mathbb {M}$ является биективной функцией из $\mathbb {N}$ (элемент $\mathbb {M}$ ) к ${\mathcal {P}}(\mathbb {N} )$ (еще один элемент $\mathbb {M}$ )" ^[2]

Скулем использовал термин «относительный» для описания такого положения дел, когда одно и то же множество включено в две модели теории множеств, является счетным в одной модели и несчетным в другой. Он назвал это «самым важным» результатом в своей статье. Современные теоретики множеств описывают концепции, которые не зависят от выбора транзитивной модели, как абсолютные . С их точки зрения, парадокс Скулема просто показывает, что счетность не является абсолютным свойством в логике первого порядка (Кунен 1980, стр. 141; Эндертон 2001, стр. 152; Берджесс 1977, стр. 406).

Скулем описал свою работу как критику теории множеств (первого порядка), призванную проиллюстрировать ее слабость как основополагающей системы:

«Я считал, что аксиоматизация в терминах множеств не является удовлетворительным окончательным основанием математики настолько очевидно, что математиков по большей части это не очень-то интересует. Но в последнее время я, к своему удивлению, увидел, что так много математиков думают, что эти аксиомы теории множеств обеспечивают идеальную основу математики, поэтому мне показалось, что пришло время для критики». (Эббингауз и ван Дален, 2000, стр. 147)

Прием математического сообщества

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

«Ни книга по антиномии еще не закрыта, ни соглашение о ее значении и возможном решении еще не достигнуто». (ван Дален и Эббингауз, 2000, стр. 147).

В 1925 году фон Нейман представил новую аксиоматизацию теории множеств, которая развилась в теорию множеств NBG . Хорошо зная о статье Скулема 1922 года, фон Нейман подробно исследовал счетные модели своих аксиом. В своих заключительных замечаниях фон Нейман отмечает, что не существует категорической аксиоматизации теории множеств или любой другой теории с бесконечной моделью. Говоря о влиянии парадокса Скулема, он писал:

«В настоящее время мы можем лишь отметить, что у нас есть еще одна причина высказывать сомнения относительно теории множеств и что в настоящее время не известно никакого способа реабилитации этой теории». (Эббингауз и ван Дален, 2000, стр. 148)

Цермело сначала считал парадокс Скулема обманом (van Dalen and EBBinghaus, 2000, стр. 148 и далее) и выступал против него, начиная с 1929 года. Результат Скулема применим только к тому, что сейчас называется логикой первого порядка , но Цермело возражал против финитная метаматематика , лежащая в основе логики первого порядка (Канамори 2004, стр. 519 и сл.). Цермело утверждал, что вместо этого его аксиомы следует изучать в логике второго порядка , в которой результат Скулема неприменим. Цермело опубликовал аксиоматизацию второго порядка в 1930 году и доказал в этом контексте несколько результатов о категоричности. Дальнейшая работа Цермело над основами теории множеств после статьи Скулема привела к открытию им кумулятивной иерархии и формализации бесконечной логики (ван Дален и Эббингауз, 2000, примечание 11).

Френкель и др. (1973, стр. 303–304) объясняют, почему результат Скулема оказался настолько неожиданным для теоретиков множеств 1920-х годов. Теорема Гёделя о полноте и теорема о компактности не были доказаны до 1929 года. Эти теоремы пролили свет на то, как ведет себя логика первого порядка, и установили ее финитную природу, хотя первоначальное доказательство теоремы о полноте, проведенное Гёделем, было сложным. Леоном Хенкиным Альтернативное доказательство теоремы о полноте, которое сейчас является стандартным методом построения счетных моделей непротиворечивой теории первого порядка, было представлено только в 1947 году. Таким образом, в 1922 году конкретные свойства логики первого порядка, позволяющие Парадокс Скулема, через который нужно пройти, еще не был понят. Теперь известно, что парадокс Скулема уникален для логики первого порядка; если теория множеств изучается с использованием логики высшего порядка с полной семантикой, то из-за используемой семантики она не имеет счетных моделей.

Текущее математическое мнение

Современные математические логики не рассматривают парадокс Скулема как фатальный недостаток теории множеств. Клини (1967, стр. 324) описывает результат как «не парадокс в смысле прямого противоречия, а скорее своего рода аномалию». Изучив аргумент Скулема о том, что результат не противоречив, Клини заключает: «не существует абсолютного понятия счетности». Хантер (1971, стр. 208) описывает это противоречие как «едва ли даже парадокс». Френкель и др. (1973, стр. 304) объясняют, что современных математиков беспокоит отсутствие категоричности теорий первого порядка не больше, чем их беспокоит вывод теоремы Гёделя о неполноте , согласно которому не существует непротиворечивого, эффективного и достаточно сильного набора теорий первого порядка. аксиомы полны.

Счетные модели ZF стали обычными инструментами при изучении теории множеств. Форсирование , например, часто объясняется с помощью счетных моделей. Тот факт, что эти счетные модели ZF все еще удовлетворяют теореме о существовании несчетных множеств, не считается патологией; ван Хейеноорт (1967) описывает это как «новую и неожиданную особенность формальных систем» (ван Хейеноорт 1967, стр. 290).

См. также

Парадоксы теории множеств

Ссылки

^ Р.Л. Гудстейн, Значение теорем о неполноте (1963), стр.209. Британский журнал философии науки, Vol. 14. По состоянию на 8 марта 2023 г.
^ Тимоти Бэйс, Математика парадокса Скулема (PDF)

Барвайз, Джон (1982) [1977]. «Введение в логику первого порядка». В Барвайзе, Джон (ред.). Справочник по математической логике . Исследования по логике и основам математики. Амстердам: Северная Голландия. ISBN 978-0-444-86388-1 .
Бэйс, Тимоти (2000). Размышления о парадоксе Скулема (PDF) (кандидатская диссертация). Философский факультет Калифорнийского университета в Лос-Анджелесе.
Кроссли, JN; Эш, CJ; Брикхилл, CJ; Стиллвелл, Джей Си; Уильямс, Нью-Хэмпшир (1972). Что такое математическая логика? . Лондон-Оксфорд-Нью-Йорк: Издательство Оксфордского университета . ISBN 0-19-888087-1 . Збл 0251.02001 .
ван Дален, Дирк ; Эббингауз, Хайнц-Дитер (июнь 2000 г.). «Цермело и скулемский парадокс» . Бюллетень символической логики . 6 (2): 145–161. CiteSeerX 10.1.1.137.3354 . дои : 10.2307/421203 . hdl : 1874/27769 . JSTOR 421203 . S2CID 8530810 .
Драгалин, А.Г. (2001) [1994], «Парадокс Скулема» , Энциклопедия математики , EMS Press
Эндертон, Герберт Б. (2001). Математическое введение в логику (2-е изд.). Эльзевир. ISBN 978-0-08-049646-7 .
Френкель, Авраам; Бар-Гилель, Иегошуа; Леви, Азриэль; ван Дален, Дирк (1973). Основы теории множеств . Северная Голландия.
Хенкин, Л. (1950). «Полнота в теории типов». Журнал символической логики . 15 (2): 81–91. дои : 10.2307/2266967 . JSTOR 2266967 . S2CID 36309665 .
Канамори, Акихиро (2004), «Цермело и теория множеств» , Бюллетень символической логики , 10 (4): 487–553, doi : 10.2178/bsl/1102083759 , ISSN 1079-8986 , JSTOR 3216738 , MR 2136635 , S2CID 231795240
Стивен Коул Клини (1952, 1971 с поправками, 10-е издание 1991 г.), «Введение в метаматематику» , издательство North-Holland Publishing Company, Амстердам, штат Нью-Йорк. ISBN 0-444-10088-1 . ср. стр. 420-432: § 75. Системы аксиом, парадокс Скулема, последовательность натуральных чисел.
Стивен Коул Клини (1967). Математическая логика .
Кунен, Кеннет (1980). Теория множеств: введение в доказательства независимости . Амстердам: Северная Голландия. ISBN 978-0-444-85401-8 .
Левенхайм, Леопольд (1915). «О возможностях относительного исчисления» (PDF) . Математические летописи . 76 (4): 447–470. дои : 10.1007/BF01458217 . ISSN 0025-5831 . S2CID 116581304 .
Мур, AW (1985). «Теория множеств, парадокс Скулема и Трактат». Анализ . 45 (1): 13–20. дои : 10.2307/3327397 . JSTOR 3327397 .
Патнэм, Хилари (сентябрь 1980 г.). «Модели и реальность» (PDF) . Журнал символической логики . 45 (3): 464–482. дои : 10.2307/2273415 . JSTOR 2273415 . S2CID 18831300 .
Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк : Springer Science + Business Media . дои : 10.1007/978-1-4419-1221-3 . ISBN 978-1-4419-1220-6 .
Сколем, Торальф (1923). «Некоторые замечания об аксиоматическом обосновании теории множеств». Математические конгрессы в Гельсингфорсе, 4—7 июля 1922 г.; Femte Skandinaviska matematikarkongressen redogörelse . Пятый Скандинавский математический конгресс. Хельсинки . стр. 217–232. ОСЛК 23550016 . Английский перевод: Сколем, Торальф (1961) [1922]. «Некоторые замечания по аксиоматизированной теории множеств». В ван Хейеноорте (ред.). От Фреге до Гёделя: Справочник по математической логике, 1879–1931 . Перевод Стефана Бауэра-Менгельберга. стр. 290–301.

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

[1] Р.Л. Гудстейн, Значение теорем о неполноте (1963), стр.209. Британский журнал философии науки, Vol. 14. По состоянию на 8 марта 2023 г.

[2] Тимоти Бэйс, Математика парадокса Скулема (PDF)

[1]

[2]