Теорема Левенхайма – Скулема

В математической логике теорема Левенхайма-Скулема — теорема о существовании и мощности моделей Торальфа , названная в честь Леопольда Левенхайма и Скулема .

Точная формулировка приведена ниже. Это означает, что если счетная первого порядка теория имеет бесконечную модель , то для каждого бесконечного кардинального числа κ она имеет модель размера κ , и что ни одна теория первого порядка с бесконечной моделью не может иметь единственную модель с точностью до изоморфизма . Как следствие, теории первого порядка не могут контролировать мощность своих бесконечных моделей.

Теорема Левенхайма-Скулема (вниз) является одним из двух ключевых свойств, наряду с теоремой о компактности , которые используются в теореме Линдстрема для характеристики логики первого порядка . В общем, теорема Левенхайма-Скулема не справедлива в более сильных логиках, таких как логика второго порядка .

Теорема

Иллюстрация теоремы Левенхайма – Скулема

В своей общей форме теорема Левенхайма–Скулема утверждает, что для любой сигнатуры σ , каждой бесконечной σ - структуры M и каждого бесконечного кардинального числа $κ \geq | σ |$ , существует σ -структура N такая, что $| Н | = κ$ и такой, что

если $κ < | М |$ тогда N — элементарная подструктура M ;
если $κ \geq | М |$ тогда N является элементарным расширением M .

Теорему часто делят на две части, соответствующие двум вышеприведенным случаям. Часть теоремы, утверждающая, что структура имеет элементарные подструктуры всех меньших бесконечных мощностей, известна как нисходящая теорема Левенгейма – Скулема . ^[1]^{: 160–162} Часть теоремы, утверждающая, что структура имеет элементарные расширения всех больших мощностей, известна как восходящая теорема Левенхайма – Скулема . ^[2]

Обсуждение

Ниже мы подробно остановимся на общей концепции подписей и структур.

Концепции

Подписи

Сигнатура S состоит из набора функциональных символов S _func , набора символов отношения rel _и функции $\operatorname {ar} :S_{\operatorname {func} }\cup S_{\operatorname {rel} }\rightarrow \mathbb {N} _{0}$ представляющие арность символов функций и отношений. (Символ нулевой функции называется постоянным символом.) В контексте логики первого порядка сигнатуру иногда называют языком. Она называется счетной, если множество символов функций и отношений в ней счетно и, вообще говоря, мощность подписи равна мощности множества всех содержащихся в ней символов.

первого порядка Теория состоит из фиксированной сигнатуры и фиксированного набора предложений (формул без свободных переменных) в этой сигнатуре. ^[3]^: 40 Теории часто конкретизируются путем предоставления списка аксиом, которые порождают теорию, или путем определения структуры и рассмотрения теории, состоящей из предложений, которым удовлетворяет эта структура.

Структуры/модели

Учитывая сигнатуру σ , σ - структура M является конкретной интерпретацией символов в σ . Он состоит из базового набора (часто также обозначаемого « M ») вместе с интерпретацией символов функций и отношений σ . Интерпретация постоянного символа σ в M это просто элемент M. — В более общем смысле, интерпретация n -арного функционального символа f — это функция из M ^н к М. Аналогично, интерпретация символа отношения R — это n- арное отношение на M , т.е. подмножество M ^н.

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

Последствия

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

Теория называется категоричной , если она имеет только одну модель с точностью до изоморфизма. Этот термин был введен Вебленом (1904) , и в течение некоторого времени после этого математики надеялись, что смогут поставить математику на прочный фундамент, описав категориальную теорию первого порядка некоторой версии теории множеств. Теорема Левенхайма-Скулема нанесла первый удар по этой надежде, поскольку из нее следует, что теория первого порядка, имеющая бесконечную модель, не может быть категоричной. Позже, в 1931 году, надежды были полностью разбиты теоремой Гёделя о неполноте . ^[1]

Многие следствия теоремы Левенхайма-Скулема казались логикам начала 20 века противоречащими здравому смыслу, поскольку различие между свойствами первого и непервого порядка еще не было понято. Одним из таких последствий является существование бесчисленных моделей истинной арифметики первого порядка , которые удовлетворяют каждой аксиоме индукции , но имеют неиндуктивные подмножества.

Пусть N обозначает натуральные числа, а R — действительные. Из теоремы следует, что теория ( N , +, ×, 0, 1) (теория истинной арифметики первого порядка) имеет бесчисленное количество моделей и что теория ( R , +, ×, 0, 1) (теория реальных замкнутых полей ) имеет счетную модель. Существуют, конечно, аксиоматизации, характеризующие ( N , +, ×, 0, 1) и ( R , +, ×, 0, 1) с точностью до изоморфизма. Теорема Левенхайма – Скулема показывает, что эти аксиоматизации не могут быть первого порядка. Например, в теории действительных чисел полнота линейного порядка, используемого для характеристики R как полного упорядоченного поля, не является свойством не первого порядка . ^[1]^: 161

Другое последствие, которое считалось особенно тревожным, — это существование счетной модели теории множеств, которая, тем не менее, должна удовлетворять предложению о том, что действительные числа неисчислимы. Теорема Кантора утверждает, что некоторые множества несчетны. Эта парадоксальная ситуация стала известна как парадокс Скулема ; это показывает, что понятие счетности не является абсолютным . ^[4]

Эскиз доказательства

Нижняя часть

За каждый первый заказ $\sigma$ -формула $\varphi (y,x_{1},\ldots ,x_{n})$ , из аксиомы выбора следует существование функции

f_{\varphi }:M^{n}\to M

такой, что для всех $a_{1},\ldots ,a_{n}\in M$ , или

M\models \varphi (f_{\varphi }(a_{1},\dots ,a_{n}),a_{1},\dots ,a_{n})

или

M\models \neg \exists y\,\varphi (y,a_{1},\dots ,a_{n})

.

Применяя еще раз аксиому выбора, получаем функцию из формул первого порядка $\varphi$ к таким функциям $f_{\varphi }$ .

Семейство функций $f_{\varphi }$ порождает оператор предварительной блокировки $F$ на силовом наборе $M$

F(A)=\{f_{\varphi }(a_{1},\dots ,a_{n})\in M\mid \varphi \in \sigma ;\,a_{1},\dots ,a_{n}\in A\}

для $A\subseteq M$ .

Итерация $F$ счетное количество раз приводит к оператору замыкания $F^{\omega }$ . Взяв произвольное подмножество $A\subseteq M$ такой, что $\left\vert A\right\vert =\kappa$ , и определив $N=F^{\omega }(A)$ , это тоже видно $\left\vert N\right\vert =\kappa$ . Затем $N$ представляет собой элементарную подструктуру $M$ по критерию Тарского-Вота .

Уловка, использованная в этом доказательстве, по существу принадлежит Сколему, который ввел функциональные символы для скулемовских функций. $f_{\varphi }$ в язык. Можно было бы также определить $f_{\varphi }$ как частичные функции такие, что $f_{\varphi }$ определяется тогда и только тогда, когда $M\models \exists y\,\varphi (y,a_{1},\ldots ,a_{n})$ . Единственный важный момент заключается в том, что $F$ является оператором презамыкания, таким что $F(A)$ содержит решение для каждой формулы с параметрами в $A$ который имеет решение в $M$ и это

\left\vert F(A)\right\vert \leq \left\vert A\right\vert +\left\vert \sigma \right\vert +\aleph _{0}

.

Верхняя часть

Во-первых, подпись расширяется путем добавления нового постоянного символа для каждого элемента $M$ . Полная теория $M$ за расширенную подпись $\sigma '$ называется элементарной диаграммой $M$ . На следующем шаге добавляется $\kappa$ много новых постоянных символов в подписи и добавляет к элементарной диаграмме $M$ предложения $c\neq c'$ для любых двух различных новых постоянных символов $c$ и $c'$ . Используя теорему о компактности , легко убедиться в непротиворечивости полученной теории. Поскольку его модели должны иметь мощность не менее $\kappa$ , нижняя часть этой теоремы гарантирует существование модели $N$ который имеет мощность ровно $\kappa$ . Он содержит изоморфную копию $M$ как элементарная подструктура. ^[5]^[6]^{: 100–102}

В другой логике

Хотя (классическая) теорема Левенхайма – Скулема очень тесно связана с логикой первого порядка, ее варианты справедливы и для других логик. Например, каждая непротиворечивая теория логики второго порядка имеет модель, меньшую, чем первый суперкомпактный кардинал (при условии, что таковой существует). Минимальный размер, при котором (нисходящая) теорема типа Левенгейма – Скулема применяется в логике, известен как число Левенгейма и может использоваться для характеристики силы этой логики. Более того, если мы выйдем за пределы логики первого порядка, мы должны отказаться от одной из трех вещей: счетной компактности, нисходящей теоремы Левенхайма-Скулема или свойств абстрактной логики . ^[7]^: 134

Исторические заметки

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

Первым значительным результатом в том, что позже стало теорией моделей, была теорема Левенхайма в Леопольда Левенхайма публикации «О возможностях в относительном исчислении» (1915):

Для каждой счетной сигнатуры σ каждое σ -предложение выполнимо в счетной модели. выполнимое

Статья Левенхайма на самом деле касалась более общего Пирса – Шредера исчисления родственников ( алгебры отношений с кванторами). ^[1] Он также использовал устаревшие обозначения Эрнста Шредера . Краткое изложение статьи на английском языке и с использованием современных обозначений см. в Brady (2000 , глава 8).

Согласно сложившейся исторической точке зрения, доказательство Левенхайма было ошибочным, поскольку оно неявно использовало лемму Кенига , не доказывая ее, хотя в то время лемма еще не была опубликованным результатом. В ревизионистском отчете Бадеса (2004) считает, что доказательство Левенхайма было полным.

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

Всякая счетная теория, выполнимая в модели M , выполнима и в счетной M. подструктуре

Скулем (1922) также доказал следующую более слабую версию без аксиомы выбора:

Всякая счетная теория, выполнимая в модели, также выполнима в счетной модели.

Сколем (1929) упростил Сколем (1920) . Наконец, Анатолий Иванович Мальцев (Анато́лий Ива́нович Ма́льцев, 1936) доказал теорему Левенгейма–Скулема во всей её общности ( Мальцев 1936 ). Он процитировал заметку Скулема, согласно которой теорема была доказана Альфредом Тарским на семинаре в 1928 году. Поэтому общую теорему иногда называют теоремой Левенгейма-Скулема-Тарского . Но Тарский не помнил своего доказательства, и остаётся загадкой, как он смог это сделать без теоремы о компактности .

Несколько иронично, что имя Скулема связано как с восходящим, так и с нисходящим направлением теоремы:

«Я следую обычаю называть следствие 6.1.4 восходящей теоремой Левенгейма-Скулема. Но на самом деле Скулем даже не верил в это, потому что он не верил в существование несчетных множеств». – Ходжес (1993) .

«Скулем [...] отверг результат как бессмысленный; Тарский [...] весьма разумно ответил, что формалистическая точка зрения Скулема должна считать нисходящую теорему Левенхайма-Скулема бессмысленной, так же как и восходящую». – Ходжес (1993) .

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Нурани, К.Ф., Теория функториальных моделей: новые приложения к алгебраической топологии, описательным множествам и вычислительным категориям топос ( Торонто : Apple Academic Press; Boca Raton : CRC Press , 2014), стр. 160–162 .
^ Шеппард, Б., Логика бесконечности ( Кембридж : Cambridge University Press , 2014), стр. 372 .
^ Хаан, Р. де, Параметризованная сложность в полиномиальной иерархии: распространение теории параметризованной сложности на более высокие уровни иерархии ( Берлин / Гейдельберг : Springer , 2019), стр. 40 .
^ Бэйс, Т., «Парадокс Скулема» , Стэнфордская энциклопедия философии , зима 2014 г.
^ Черч, А. , и Лэнгфорд, CH , ред., Журнал символической логики ( Сторрс, Коннектикут : Ассоциация символической логики , 1981), стр. 529.
^ Лири, К.С., и Кристиансен, Л., Дружеское введение в математическую логику ( Генезео, Нью-Йорк : Библиотека Милна, 2015), стр. 100–102 .
^ Чанг, CC , и Кейслер, HJ , Теория моделей , 3-е изд. ( Минеола и Нью-Йорк : Dover Publications , 1990), с. 134 .

Источники

Теорема Левенхайма-Скулема рассматривается во всех вводных текстах по теории моделей или математической логике .

Исторические публикации

Лёвенхайм, Леопольд (1915), «О возможностях относительного исчисления» (PDF) , Mathematical Annals , 76 (4): 447–470, doi : 10.1007/BF01458217 , ISSN 0025-5831 , S2CID 116581304
- Левенхайм, Леопольд (1977), «О возможностях исчисления родственников», От Фреге до Гёделя: Справочник по математической логике, 1879–1931 (3-е изд.), Кембридж, Массачусетс: Издательство Гарвардского университета, стр. 228– 251, ISBN 0-674-32449-8 ( онлайн-копия , стр. 228, в Google Книгах )
Мальцев, Анатолий Иванович (1936), «Исследования из области математической логики» , Математический сборник , Новая серия, 1(43) (3): 323–336
Сколем, Торальф (1920), «Логико-комбинаторные исследования выполнимости или доказуемости математических предложений вместе с теоремой о плотных множествах», Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse , 4 : 1–36
- Сколем, Торальф (1977), «Логико-комбинаторные исследования выполнимости или доказуемости математических утверждений: упрощенное доказательство теоремы Л. Левенхайма и обобщения теоремы», От Фреге до Гёделя: Справочник по математической логике, 1879–1931 (3-е изд.), Кембридж, Массачусетс: Издательство Гарвардского университета, стр. 252–263, ISBN 0-674-32449-8 ( онлайн-копия , стр. 252, в Google Книгах )
Сколем, Торальф (1922), «Некоторые замечания по аксиоматическому обоснованию теории множеств», Математические конгрессы I в Гельсингфорсе, 4–7 июля 1922 г., Femte Skandinaviska Matematikerkongressen, Redogörelse : 217–232
- Сколем, Торальф (1977), «Некоторые замечания по аксиоматизированной теории множеств», От Фреге до Гёделя: Справочник по математической логике, 1879–1931 (3-е изд.), Кембридж, Массачусетс: Издательство Гарвардского университета, стр. 290–301 , ISBN 0-674-32449-8 ( онлайн-копия , стр. 290, в Google Книгах )
Скулем, Торальф (1929), «Über einige Grundlagenfragen der Mathematik», сочинения, опубликованные Норвежской академией наук в Осло, I. Класс математико-естественных наук , 7 : 1–49
Веблен, Освальд (1904), «Система аксиом геометрии», Труды Американского математического общества , 5 (3): 343–384, doi : 10.2307/1986462 , ISSN 0002-9947 , JSTOR 1986462

Вторичные источники

Бадеса, Каликсто (2004), Рождение теории моделей: теорема Левенхайма в рамках теории относительности , Принстон, Нью-Джерси: Princeton University Press, ISBN 978-0-691-05853-5 ; Более краткое изложение содержится в главе 9 книги. Лейла Хаапаранта , изд. (2009), Развитие современной логики , Oxford University Press, ISBN 978-0-19-513731-6
Брэди, Джеральдин (2000), От Пирса до Скулема: забытая глава в истории логики , Elsevier, ISBN 978-0-444-50334-3
Кроссли, JN ; Эш, CJ; Брикхилл, CJ; Стиллвелл, Джей Си; Уильямс, Нью-Хэмпшир (1972), Что такое математическая логика? , Лондон/Оксфорд/Нью-Йорк: Oxford University Press , стр. 59–60, ISBN. 0-19-888087-1 , Збл 0251.02001
Доусон, Джон В. младший (1993), «Компактность логики первого порядка: от Гёделя до Линдстрема», History and Philosophy of Logic , 14 : 15–37, doi : 10.1080/01445349308837208
Ходжес, Уилфрид (1993), Теория моделей , Кембридж: Cambridge Univ. Пр., ISBN 978-0-521-30442-9
Пуаза, Бруно (2000), Курс теории моделей: введение в современную математическую логику , Берлин, Нью-Йорк: Springer, ISBN 978-0-387-98655-5

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

Сахаров, А. ; Вайсштейн, Э.В. «Теорема Левенхайма-Скулема» . Математический мир .
Беррис, Стэнли Н., Вклад логиков, Часть II, От Ричарда Дедекинда до Герхарда Генцена
Беррис, Стэнли Н., Нисходящая теорема Левенхайма – Скулема
Симпсон, Стивен Г. (1998), Теория моделей

[n-1] Jump up to: ^а ^б ^с ^д ^и Нурани, К.Ф., Теория функториальных моделей: новые приложения к алгебраической топологии, описательным множествам и вычислительным категориям топос ( Торонто : Apple Academic Press; Boca Raton : CRC Press , 2014), стр. 160–162 .

[2] Шеппард, Б., Логика бесконечности ( Кембридж : Cambridge University Press , 2014), стр. 372 .

[3] Хаан, Р. де, Параметризованная сложность в полиномиальной иерархии: распространение теории параметризованной сложности на более высокие уровни иерархии ( Берлин / Гейдельберг : Springer , 2019), стр. 40 .

[4] Бэйс, Т., «Парадокс Скулема» , Стэнфордская энциклопедия философии , зима 2014 г.

[5] Черч, А. , и Лэнгфорд, CH , ред., Журнал символической логики ( Сторрс, Коннектикут : Ассоциация символической логики , 1981), стр. 529.

[6] Лири, К.С., и Кристиансен, Л., Дружеское введение в математическую логику ( Генезео, Нью-Йорк : Библиотека Милна, 2015), стр. 100–102 .

[7] Чанг, CC , и Кейслер, HJ , Теория моделей , 3-е изд. ( Минеола и Нью-Йорк : Dover Publications , 1990), с. 134 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]