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

Существование и мощность моделей логических теорий

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

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

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

Теорема

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

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

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

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

Обсуждение

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

Концепции

Подписи

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

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

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

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

Подструктура σ -структуры 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]

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

Нижняя часть

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

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

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

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

или

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

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

Семейство функций порождает оператор презамыкания на множестве степеней ${\displaystyle f_{\varphi }}$ ${\displaystyle F}$ ${\displaystyle M}$

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

для ${\displaystyle A\subseteq M\,.}$

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

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

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

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

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

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

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

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

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

Первым значительным результатом в том, что позже стало теорией моделей, была теорема Левенхайма в публикации Леопольда Левенхайма «Über Möglichkeiten im Relativkalkül» (1915):

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

1. Nourani, CF, Теория функториальных моделей: новые приложения к алгебраической топологии, описательным наборам и вычислительным категориям Topos ( Торонто : 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.

Источники

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

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

• Лёвенхайм, Леопольд (1915), «Über Möglichkeiten im Relativkalkül» (PDF) , Mathematische Annalen , 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), «Untersuchungen aus dem Gebiete der mathematischen Logik», Математический сборник , Новая серия, 1(43) (3): 323–336
• Сколем, Торальф (1920), «Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem теорема über dichte Mengen», Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse , 4 : 1–36
  • Сколем, Торальф (1977), «Логико-комбинаторные исследования выполнимости или доказуемости математических утверждений: упрощенное доказательство теоремы Л. Левенхайма и обобщения теоремы», От Фреге до Гёделя: Справочник по математической логике, 1879–1931 (3-е изд.), Кембридж, Массачусетс: Издательство Гарвардского университета, стр. 252–263, ISBN 0-674-32449-8( онлайн-копия , стр. 252, в Google Книгах )
• Сколем, Торальф (1922), «Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre», Mathematikarkongressen I Helsingfors den 4–7 июля 1922 г., den 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», Skrifter Utgitt av Det Norske Videnskaps-Akademi I Oslo, I. Matematisk-naturvidenskabelig Klasse , 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), Теория моделей