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

Концепция математической логики

Торальф Скулем , в честь которого назван парадокс

В математической логике и философии парадокс Скулема — это кажущееся противоречие, что счетная модель теории множеств первого порядка может содержать несчетное множество . Парадокс возникает из части теоремы Лёвенгейма–Скулема ; Торальф Скулем был первым, кто обсудил, казалось бы, противоречивые аспекты теоремы и открыл относительность теоретико-множественных понятий, теперь известную как неабсолютность . Хотя это не является фактической антиномией , как парадокс Рассела , результат обычно называют парадоксом и Скулем описал его как «парадоксальное положение дел». ^[1]

В теории моделей модель соответствует определенной интерпретации формального языка или теории. Она состоит из домена (множества объектов) и интерпретации символов и формул в языке, так что аксиомы теории выполняются в пределах этой структуры. Теорема Лёвенгейма–Скулема показывает, что любая модель теории множеств в логике первого порядка , если она непротиворечива , имеет эквивалентную модель , которая является счетной. Это кажется противоречивым, поскольку Георг Кантор доказал, что существуют множества, которые не являются счетными . Таким образом, кажущееся противоречие заключается в том, что модель, которая сама по себе счетна и которая, следовательно, содержит только счетные множества, удовлетворяет предложению первого порядка, которое интуитивно утверждает «существуют несчетные множества».

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

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

Фон

Одним из самых ранних результатов в теории множеств , опубликованных Кантором в 1874 году, было существование различных размеров или мощностей бесконечных множеств. ^[2] Бесконечное множество называется счетным , если существует функция, которая дает взаимно однозначное соответствие между и натуральными числами , и несчетным, если такой функции соответствия нет. ^{[3] [4]} В 1874 году Кантор доказал, что действительные числа несчетны; в 1891 году он доказал с помощью своего диагонального аргумента более общий результат, известный как теорема Кантора : для любого множества множество мощности не может находиться во взаимно однозначном соответствии с самим собой. ^[5] Когда Цермело предложил свои аксиомы для теории множеств в 1908 году, он доказал теорему Кантора из них, чтобы продемонстрировать их силу. ^[6] ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

В 1915 году Леопольд Лёвенгейм дал первое доказательство того, что Скулем доказал в более общем виде в 1920 и 1922 годах, теоремы Лёвенгейма–Скулема . ^{[7] [8]} Лёвенгейм показал, что любое предложение первого порядка с моделью также имеет модель со счетной областью; Скулем обобщил это на бесконечные множества предложений. Нисходящая форма теоремы Лёвенгейма–Скулема показывает, что если счетный набор аксиом первого порядка удовлетворяется бесконечной структурой , то те же аксиомы удовлетворяются некоторой счетно бесконечной структурой. ^[9] Поскольку версии первого порядка стандартных аксиом теории множеств (таких как теория множеств Цермело–Френкеля ) являются счетным набором аксиом, это означает, что если эти аксиомы выполнимы, то они выполнимы в некоторой счетной модели. ^[4]

Результат и его последствия

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

Однако это лишь кажущийся парадокс. В контексте конкретной модели теории множеств термин «множество» не относится к произвольному множеству, а только к множеству, которое фактически включено в модель. Определение счетности требует, чтобы между множеством и натуральными числами существовало определенное взаимно-однозначное соответствие. Это соответствие само по себе является множеством. Скулем разрешил парадокс, заключив, что такое множество не обязательно существует в счетной модели; то есть счетность «относительна» модели, ^[10] а счетные модели первого порядка являются неполными . ^[11]

Хотя Скулем дал свой результат относительно аксиом Цермело, он справедлив для любой стандартной теории множеств первого порядка, ^[12] такой как ZFC . ^[4] Рассмотрим теорему Кантора как длинную формулу на формальном языке ZFC . Если ZFC имеет модель, назовем эту модель и ее область определения . Интерпретация символа элемента , или , является множеством упорядоченных пар элементов — другими словами, является подмножеством . Поскольку теорема Лёвенгейма–Скулема гарантирует, что является счетным, то таким же должно быть . Два специальных элемента модели — натуральные числа и множество степеней натуральных чисел . Существует только счетное бесконечное множество упорядоченных пар в вида , поскольку является счетным. То есть, только счетное множество элементов модели членов несчетного множества . Однако нет противоречия с теоремой Кантора, потому что она просто утверждает, что ни один элемент из не может моделировать биективную функцию от до . ^[13] ${\displaystyle \mathrm {M} }$ ${\displaystyle \mathbb {M} }$ ${\displaystyle \in }$ ${\displaystyle {\mathcal {I}}(\in )}$ ${\displaystyle \mathbb {M} }$ ${\displaystyle {\mathcal {I}}(\in )}$ ${\displaystyle \mathbb {M} \times \mathbb {M} }$ ${\displaystyle \mathbb {M} }$ ${\displaystyle \mathbb {M} \times \mathbb {M} }$ ${\displaystyle \mathbb {M} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle {\mathcal {I}}(\in )}$ ${\displaystyle \langle x,{\mathcal {P}}(\mathbb {N} )\rangle }$ ${\displaystyle \mathbb {M} \times \mathbb {M} }$ ${\displaystyle \mathbb {M} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \mathbb {M} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$

Скулем использовал термин «относительный» для описания ситуации, когда одно и то же множество может быть счетным в одной модели теории множеств и не счетным в другой: относительно одной модели никакая перечисляющая функция не может поставить некоторое множество в соответствие натуральным числам, но относительно другой модели это соответствие может существовать. ^[14] Он описал это как «самый важный» результат в своей статье 1922 года. ^[10] Современные теоретики множеств описывают понятия, которые не зависят от выбора транзитивной модели, как абсолютные . ^[15] С их точки зрения, парадокс Скулема просто показывает, что счетность не является абсолютным свойством в логике первого порядка. ^{[16] [17]}

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

Я считал, что было настолько ясно, что аксиоматизация в терминах множеств не была удовлетворительным конечным основанием математики, что математики, по большей части, не были бы слишком озабочены этим. Но в последнее время я увидел, к своему удивлению, что так много математиков думают, что эти аксиомы теории множеств обеспечивают идеальное основание для математики; поэтому мне показалось, что пришло время для критики. ^[18]

—  Торальф Скулем, Некоторые замечания об аксиоматизированной теории множеств (1922) ^{[примечание 1]}

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

Потребовалось некоторое время, чтобы теория логики первого порядка была достаточно развита для того, чтобы математики поняли причину результата Скулема; ни одно решение парадокса не было широко принято в 1920-х годах. В 1928 году Авраам Френкель все еще описывал результат как антиномию :

Ни книги по антиномии еще не закрыты, ни соглашение о ее значении и возможном решении еще не достигнуто. ^[18]

—  Авраам Френкель, Введение в теорию множеств (1928) ^{[примечание 2]}

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

В настоящее время мы можем лишь отметить, что у нас есть еще одна причина для сомнений относительно теории множеств и что на данный момент не известно ни одного способа реабилитации этой теории. ^[19]

—  Джон фон Нейман, Аксиоматизация теории множеств (1925) ^{[примечание 3]}

Сначала Цермело считал парадокс Скулема мистификацией и в 1931 году выступил против «релятивизма» Скулема. ^[21] Результат Скулема применим только к тому, что сейчас называется логикой первого порядка , но Цермело выступал против финитной метаматематики , лежащей в основе логики первого порядка, ^[22] поскольку Цермело был математическим платоником , выступавшим против интуиционизма и финитизма в математике. ^[23] Цермело верил в своего рода бесконечный платоновский идеал логики и считал, что математика имеет изначально бесконечный характер. ^[24] Цермело утверждал, что его аксиомы вместо этого следует изучать в логике второго порядка , ^[25] в обстановке, в которой результат Скулема неприменим. ^[12] Цермело опубликовал аксиоматизацию второго порядка теории множеств в 1930 году. ^[26] Дальнейшая работа Цермело над основами теории множеств после статьи Скулема привела к открытию им кумулятивной иерархии и формализации бесконечной логики . ^[27]

Удивление, с которым теоретики множеств встретили парадокс Скулема в 1920-х годах, было продуктом их времени. Теорема Гёделя о полноте и теорема о компактности , теоремы, которые проливают свет на то, как ведет себя логика первого порядка, и устанавливают ее финитную природу, были впервые доказаны только в 1929 году . ^[28] Доказательство теоремы о полноте Леона Хенкина , которое теперь является стандартным методом построения счетных моделей непротиворечивой теории первого порядка, было представлено только в 1947 году. ^{[29] [30]} Таким образом, в 1920-х годах особые свойства логики первого порядка, которые допускают парадокс Скулема, еще не были поняты. ^[31] Сейчас известно, что парадокс Скулема уникален для логики первого порядка; если теория множеств изучается с использованием логики высшего порядка с полной семантикой, то она не имеет счетных моделей. ^[12] К тому времени, когда Цермело написал свое окончательное опровержение парадокса в 1937 году, сообщество логиков и теоретиков множеств в основном признало неполноту логики первого порядка. Цермело оставил это опровержение незавершенным. ^[32]

Более поздние мнения

Более поздние математические логики не считали парадокс Скулема фатальным недостатком теории множеств. Стивен Коул Клини описал результат как «не парадокс в смысле прямого противоречия, а скорее своего рода аномалию». ^[33] После обзора аргумента Скулема о том, что результат не является противоречивым, Клини пришел к выводу: «нет абсолютного понятия счетности». ^[33] Джеффри Хантер описал противоречие как «едва ли даже парадокс». ^[34] Френкель и др. утверждали, что современных математиков не больше беспокоит отсутствие категоричности теорий первого порядка, чем их беспокоит вывод теоремы Гёделя о неполноте : что ни один последовательный, эффективный и достаточно сильный набор аксиом первого порядка не является полным. ^[35]

Другие математики, такие как Рубен Гудстейн и Хао Ван, зашли так далеко, что приняли так называемую «скулемитскую» точку зрения: теорема Лёвенгейма-Скулема не только доказывает, что теоретико-множественные понятия счетности относительны к модели, но и что каждое множество счетно с некоторой «абсолютной» точки зрения. ^[36] Л. Э. Дж. Брауэр был еще одним ранним приверженцем идеи абсолютной счетности, утверждая с точки зрения математического интуиционизма , что все множества счетны. ^[37] И скулемитская точка зрения, и интуиционизм Брауэра противостоят математическому платонизму, ^[38] но Карл Пози отрицает идею о том, что позиция Брауэра была реакцией на более ранние теоретико-множественные парадоксы. ^[39] Скулем был еще одним математическим интуиционистом, но он отрицал, что его идеи были вдохновлены Брауэром. ^[40]

Счётные модели теории множеств Цермело–Френкеля стали обычными инструментами в изучении теории множеств. Метод Пола Коэна для расширения теории множеств, форсинг , часто объясняется в терминах счётных моделей и был описан Акихиро Канамори как своего рода расширение парадокса Скулема. ^[41] Тот факт, что эти счётные модели теории множеств Цермело–Френкеля всё ещё удовлетворяют теореме о том, что существуют несчетные множества, не считается патологией ; Жан ван Хейеноорт описал это как «не парадокс...[но] новую и неожиданную особенность формальных систем». ^[42]

Хилари Патнэм считал результат Скулема парадоксом, но парадоксом философии языка, а не теории множеств или формальной логики. ^[43] Он расширил парадокс Скулема, чтобы утверждать, что не только теоретико-множественные понятия членства относительны, но и семантические понятия языка относительны: не существует «абсолютной» модели для терминов и предикатов в языке. ^[44] Тимоти Бэйс утверждал, что аргумент Патнэма неправильно применяет нисходящую теорему Лёвенгейма-Скулема, ^[45] в то время как Тим Баттон утверждал, что утверждение Патнэма остается в силе, несмотря на использование или неправильное использование теоремы Лёвенгейма-Скулема. ^[46] Апелляции к парадоксу Скулема несколько раз делались в философии науки , при этом ученые использовали идею Скулема об относительности модельных структур. ^{[47] [48]}

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

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

Примечания

1. Перевод с немецкого оригинала Einige Bemerkungen zur axiomatischen Begriindung der Mengenlehre
2. Перевод с оригинального немецкого Einleitung in die Mengenlehre.
3. Перевод с немецкого оригинала Eine Axiomatisierung der Mengenlehre.

Ссылки

1. Skolem 1967, стр. 295.
2. Канамори 1996, стр. 3.
3. Кантор 1874. Английский перевод: Эвальд 1996, стр. 839–843.
4. Bays 2007, стр. 2.
5. Канамори 1996, стр. 7.
6. Цермело 1967, стр. 200.
7. ван Хейеноорт 1967, с. 232.
8. Сколем 1967, стр. 290.
9. Нурани 2014, стр. 160–162.
10. Skolem 1967, стр. 300.
11. Гудстейн 1963, стр. 209.
12. Eklund 1996, стр. 153.
13. Бэйс 2007.
14. Резник 1966, стр. 426–427.
15. Кунен 1980, стр. 117–118.
16. Кунен 1980, стр. 141.
17. Нурани 2014, стр. 161.
18. ван Дален и Эббингхаус 2000, стр. 147.
19. ван Дален и Эббингхаус 2000, стр. 148.
20. фон Нейман 1925.
21. ван Дален и Эббингауз 2000, стр. 153.
22. Канамори 2004, стр. 519–520.
23. ван Дален и Эббингхаус 2000, стр. 158–159.
24. ван Дален и Эббингхаус 2000, стр. 149.
25. ван Дален и Эббингауз 2000, стр. 151.
26. Хаапаранта 2009, стр. 352.
27. ван Дален и Эббингхаус 2000, стр. 152.
28. Доусон 1993, стр. 17.
29. Болдуин 2017, стр. 5.
30. Ходжес 1985, стр. 275.
31. Мур 1980, стр. 96.
32. ван Дален и Эббингауз 2000, стр. 145.
33. Kleene 1967, стр. 324.
34. Хантер 1971, стр. 208.
35. Френкель и др. 1973, стр. 304–305.
36. Резник 1966, стр. 425–426.
37. Книл и Книл 1962, стр. 673.
38. Кленк 1976, стр. 475.
39. Пози 1974, стр. 128.
40. Шапиро 1996, стр. 407.
41. Канамори 1996, стр. 40–42.
42. ван Хейеноорт 1967, с. 290.
43. Патнэм 1980, стр. 464.
44. Патнэм 1980, стр. 466.
45. Бэйс 2001, стр. 336.
46. Баттон 2011, стр. 325–327.
47. Ханна 2024, стр. 105–108.
48. Пенчев 2020, стр. 1.

Библиография

• Болдуин, Джон (2017). «Объяснительная сила нового доказательства: доказательство полноты Хенкина» (PDF) . Истина, существование и объяснение: исследования FilMat по философии математики . Springer: 147–162.
• Бэйс, Тимоти (2001). «О Патнэме и его моделях». The Journal of Philosophy . 98 (7). Journal of Philosophy, Inc.: 1–32. JSTOR  2678439.
• Бэйс, Тимоти (2007). «Математика парадокса Скулема» (PDF) . Философия логики . Elsevier. стр. 615–648.
• Баттон, Тим (2011). «Метаматематика модельно-теоретических аргументов Патнэма». Erkenntnis . 74 . Springer: 321–349. JSTOR  41476692.
• Кантор, Георг (1874). «Ueber eine Eigenschaft des Inbegriffes aller reellen алгебраишен Zahlen» (PDF) . Journal für die Reine und Angewandte Mathematik (на немецком языке). 1874 (77): 258–262. дои : 10.1515/crll.1874.77.258. S2CID  199545885. Архивировано (PDF) из оригинала 4 января 2023 г.
• Доусон, Джон В. (1993). «Компактность логики первого порядка: от Гёделя до Линдстрема». История и философия логики . 14 (1). Тейлор и Фрэнсис: 15–37. doi :10.1080/01445349308837208.
• Эклунд, Матти (1996). «О том, как логика стала первопорядковой» (PDF) . Nordic Journal of Philosophical Logic . 1 (2): 147–167.
• Эвальд, Уильям Б., ред. (1996). От Иммануила Канта до Давида Гильберта: Учебник по основам математики . Том 2. Нью-Йорк: Oxford University Press. ISBN 019853471X.
• Френкель, Авраам ; Бар-Хилель, Иегошуа ; Леви, Азриэль; ван Дален, Дирк (1973). Основы теории множеств . Северная Голландия.
• Гудстейн, Р. Л. (1963). «Значение теорем о неполноте». Британский журнал философии науки . 14 (55). Oxford University Press, Британское общество философии науки: 208–220. JSTOR  685241.
• Хаапаранта, Лейла , ред. (2009). Развитие современной логики (PDF) . Oxford University Press. ISBN 978-0-19-513731-6.
• Ханна, Роберт (2024). «Неоорганический подход к теореме Лёвенгейма-Скулема и «парадоксу Скулема»». Наука для людей: разум, жизнь, формальные и естественные науки и новая концепция природы . Springer Nature Switzerland. стр. 105–108. ISBN 978-3-031-61113-1.
• Ходжес, Уилфрид (1985). Building Models by Games (иллюстрированное издание). Cambridge University Press. ISBN 9780521317160.
• Хантер, Джеффри (1971). Металогика. Введение в метатеорию стандартной логики первого порядка . Macmillan Press.
• Канамори, Акихиро (1996). «Математическое развитие теории множеств от Кантора до Коэна». Бюллетень символической логики . 2 (1): 1–71. JSTOR  421046.
• Канамори, Акихиро (2004). «Цермело и теория множеств». Бюллетень символической логики . 10 (4): 487–553. дои : 10.2178/bsl/1102083759. ISSN  1079-8986. JSTOR  3216738. MR  2136635. S2CID  231795240.
• Клини, Стивен Коул (1967). Математическая логика. Wiley. ISBN 9780471490333.
• Кленк, Вирджиния (1976). «Предполагаемые модели и теорема Лёвенгейма-Сколема». Журнал философской логики . 5 (4). Springer: 475–489. JSTOR  30226157. Получено 20 августа 2024 г.
• Нил, Уильям ; Нил, Марта (1962). Развитие логики . Oxford University Press.
• Кунен, Кеннет (1980). Теория множеств: Введение в доказательства независимости . Амстердам: Северная Голландия. ISBN 978-0-444-85401-8.
• Мур, Грегори Х. (1980). «За пределами логики первого порядка: историческое взаимодействие между математической логикой и аксиоматической теорией множеств». История и философия логики . 1 (1–2). Тейлор и Фрэнсис: 95–137. doi :10.1080/01445348008837006.
• Нурани, Сайрус (2014). Теория функториальных моделей: новые приложения к алгебраической топологии, описательным множествам и вычислительным категориям Topos. CRC Press.
• Пенчев, Васил (2020). «Парадокс» Скулема как логика основания: взаимная основа правильных и неправильных интерпретаций». Epistemology eJournal . 13 (19). Elsevier: 1–16.
• Пози, Карл (1974). «Конструктивизм Брауэра». Synthese . 27 (1–2). Kluwer Academic Publishers: 125–159. doi :10.1007/bf00660893. JSTOR  20114910.
• Патнэм, Хилари (сентябрь 1980 г.). «Модели и реальность» (PDF) . Журнал символической логики . 45 (3): 464–482. doi :10.2307/2273415. JSTOR  2273415. S2CID  18831300.
• Резник, Майкл Дэвид (1966). «О парадоксе Скулема». The Journal of Philosophy . 63 (15). Journal of Philosophy, Inc.: 425–438. JSTOR  2024063.
• Шапиро, Стюарт , ред. (1996). Пределы логики: логика высшего порядка и теорема Левенгейма-Сколема . Routledge. ISBN 9781855217317.
• ван Дален, Дирк ; Эббингауз, Хайнц-Дитер (июнь 2000 г.). «Цермело и парадокс Сколема». Бюллетень символической логики . 6 (2): 145–161. CiteSeerX  10.1.1.137.3354 . doi :10.2307/421203. hdl :1874/27769. JSTOR  421203. S2CID  8530810.
• ван Хейеноорт, Жан , ред. (1967). От Фреге до Гёделя: Учебник по математической логике, 1879–1931 . Издательство Гарвардского университета.
  • Левенхайм, Леопольд . «О возможностях исчисления родственников». В ван Хейеноорте (1967), стр. 228–251.
  • Сколем, Торальф . «Некоторые замечания об аксиоматизированной теории множеств». В van Heijenoort (1967), стр. 290–301.
  • Цермело, Эрнст . «Исследования по основам теории множеств I». В van Heijenoort (1967), стр. 199–215.
• фон Нейман, Джон (1925). «Eine Axiomatisierung der Mengenlehre». Journal Fur de Reine und Angewandte Mathematik (на немецком языке). 154 : 219–240.

Дальнейшее чтение

• Бэйс, Тимоти (2000). Размышления о парадоксе Скулема (PDF) (диссертация на степень доктора философии). Философский факультет Калифорнийского университета в Лос-Анджелесе.
• Мур, AW (1985). «Теория множеств, парадокс Скулема и Трактат». Анализ . 45 (1): 13–20. doi :10.2307/3327397. JSTOR  3327397.

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

• Празднование Воана Пратта в честь 120-летия его академического предка Сколема