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

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

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

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

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

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

Фон

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

В 1915 году Леопольд Левенхайм дал первое доказательство того, что Скулем доказывал в более общем плане в 1920 и 1922 годах, — теорему Левенхайма-Скулема . Левенхайм показал, что любое первого порядка предложение с моделью также имеет модель со счетной областью определения; Скулем обобщил это на бесконечное множество предложений. Нисходящая форма теоремы Левенхайма-Скулема показывает, что если счетному первого порядка набору аксиом удовлетворяет бесконечная структура , то тем же аксиомам удовлетворяет некоторая счетная бесконечная структура. множеств первого порядка Поскольку версии аксиом Цермело теории представляют собой счетный набор аксиом, это означает, что если версии аксиом Цермело первого порядка выполнимы, они выполнимы в некоторой счетной модели.

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

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

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

Рассмотрим теорему Кантора как длинную формулу на формальном языке 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}$)"

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

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

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

- Торальф Скулем, Некоторые замечания по аксиоматизированной теории множеств (1923)

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

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

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

- Авраам Френкель, Введение в теорию множеств (1928).

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

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

- Джон фон Нейман, Аксиоматизация теории множеств (1925).

Эрнст Цермело сначала считал парадокс Сколема мистификацией и выступал против него, начиная с 1929 года. Результат Скулема применим только к тому, что сейчас называется логикой первого порядка , но Цермело выступал против финитной метаматематики , лежащей в основе логики первого порядка. поскольку Цермело был математическим платоником , выступавшим против интуиционизма и финитизма в математике. Цермело утверждал, что вместо этого его аксиомы следует изучать в логике второго порядка , в которой результат Скулема неприменим. Цермело опубликовал аксиоматизацию второго порядка в 1930 году и доказал в этом контексте несколько результатов о категоричности. Дальнейшая работа Цермело над основами теории множеств после статьи Скулема привела к открытию им кумулятивной иерархии и формализации бесконечной логики .

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

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

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

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

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

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

См. также

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

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

• Болдуин, Джон (2017). «Объясняющая сила нового доказательства: доказательство полноты Хенкина» (PDF) . Истина, существование и объяснение: ФилМатские исследования по философии математики . Спрингер: 147–162.
• Бэйс, Тимоти (2001). «О Патнэме и его моделях» . Журнал философии . 98 (7). Журнал философии, Inc.: 331–350.
• Бэйс, Тимоти (2007). «Математика парадокса Скулема». Философия логики (PDF) . Эльзевир. стр. 615–648.
• Баттон, Тим (2011). «Метаматематика теоретико-модельных аргументов Патнэма». Эркеннтнис . 74 . Спрингер: 321–349.
• Кантор, Джордж (1874). «О свойстве воплощения всех действительных алгебраических чисел» (PDF) . Журнал чистой и прикладной математики . 1874 (77): 258–262. дои : 10.1515/crll.1874.77.258 . S2CID   199545885 . Архивировано (PDF) из оригинала 4 января 2023 г.
• Доусон, Джон В. (1993). «Компактность логики первого порядка: от Гёделя до Линдстрема». История и философия логики . 14 (1). Тейлор и Фрэнсис: 15–37.
• Эклунд, Матти (1996). «О том, как логика стала первоочередной» (PDF) . Северный журнал философской логики . 1 (2): 147–167.
• Эндертон, Герберт Б. (2001). Математическое введение в логику (2-е изд.). Эльзевир. ISBN  978-0-08-049646-7 .
• Эвальд, Уильям Б., изд. (1996). От Иммануила Канта до Давида Гильберта: Справочник по основам математики . Том. 2. Нью-Йорк: Издательство Оксфордского университета. ISBN  019853471X .
• Френкель, Авраам ; Бар-Хилель, Иегошуа ; Леви, Азриэль; ван Дален, Дирк (1973). Основы теории множеств . Северная Голландия.
• Гудштейн, Р.Л. (1963). «Значение теорем о неполноте» . Британский журнал философии науки . 14 (55). Издательство Оксфордского университета, Британское общество философии науки: 208–220.
• Хантер, Джеффри (1971). Металогика. Введение в метатеорию стандартной логики первого порядка . Макмилан Пресс.
• Канамори, Акихиро (2004). «Цермело и теория множеств» . Бюллетень символической логики . 10 (4): 487–553. дои : 10.2178/bsl/1102083759 . ISSN   1079-8986 . JSTOR   3216738 . МР   2136635 . S2CID   231795240 .
• Канамори, Акихиро (2012). «Теория множеств от Кантора до Коэна». Наборы и расширения в двадцатом веке . Эльзевир.
• Клини, Стивен Коул (1967). Математическая логика .
• Кленк, Вирджиния (1976). «Предназначенные модели и теорема Левенхайма-Скулема» . Журнал философской логики . 5 (4). Спрингер: 475–489 . Проверено 20 августа 2024 г.
• Нил, Уильям ; Книл, Марта (1962). Развитие логики . Издательство Оксфордского университета.
• Кунен, Кеннет (1980). Теория множеств: введение в доказательства независимости . Амстердам: Северная Голландия. ISBN  978-0-444-85401-8 .
• Мур, Грегори Х (1980). «За пределами логики первого порядка: историческое взаимодействие между математической логикой и аксиоматической теорией множеств». История и философия логики . 1 (1–2). Тейлор и Фрэнсис: 95–137.
• Пози, Карл (1974). «Конструктивизм Брауэра». Синтезируйте . 27 (1–2). Издательство Kluwer Academic: 125–159. дои : 10.1007/bf00660893 .
• Патнэм, Хилари (сентябрь 1980 г.). «Модели и реальность» (PDF) . Журнал символической логики . 45 (3): 464–482. дои : 10.2307/2273415 . JSTOR   2273415 . S2CID   18831300 .
• Резник, Майкл Дэвид (1966). «О парадоксе Скулема» . Журнал философии . 63 (15). Журнал философии, Inc.: 425–438.
• ван Дален, Дирк ; Эббингауз, Хайнц-Дитер (июнь 2000 г.). «Цермело и скулемский парадокс» . Бюллетень символической логики . 6 (2): 145–161. CiteSeerX   10.1.1.137.3354 . дои : 10.2307/421203 . hdl : 1874/27769 . JSTOR   421203 . S2CID   8530810 .
• ван Хейеноорт, Жан , изд. (1967). От Фреге до Гёделя: Справочник по математической логике, 1879–1931 .
  • Левенхайм, Леопольд . «О возможностях в исчислении родственников». В ван Хейеноорте (1967) , стр. 228–251.
  • Скулем, Торальф . «Некоторые замечания по аксиоматизированной теории множеств». В ван Хейеноорте (1967) , стр. 290–301.
  • Цермело, Эрнст . «Исследования по основам теории множеств I». В ван Хейеноорте (1967) , стр. 199–215.
• фон Нейман, Джон (1925). «Аксиоматизация теории множеств» . Журнал чистой и прикладной математики . 154 : 219-240.

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

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

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

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