Теорема Лёвенгейма–Сколема

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

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

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

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

Теорема

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

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

• если κ < | M |, то N является элементарной подструктурой M ;
• если κ ≥ | 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 , т. е. подмножеством  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]

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

Нисходящая часть

Для каждой формулы первого порядка аксиома выбора подразумевает существование функции ${\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},\ldots ,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}}$.

Восходящая часть

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

В других логиках

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

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

Этот отчет основан в основном на Dawson (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; Бока-Ратон : CRC Press , 2014), стр. 160–162.
2. Шеппард, Б., Логика бесконечности ( Кембридж : Издательство Кембриджского университета , 2014), стр. 372.
3. Хаан, Р. де, Параметризованная сложность в полиномиальной иерархии: расширение теории параметризованной сложности на более высокие уровни иерархии ( Берлин / Гейдельберг : Springer , 2019), стр. 40.
4. Бэйс, Т., «Парадокс Скулема», Стэнфордская энциклопедия философии , зима 2014 г.
5. Чёрч, А. и Лэнгфорд, Ч. Х. , ред., Журнал символической логики ( Сторрс, Коннектикут : Ассоциация символической логики , 1981), стр. 529.
6. Лири, К. К. и Кристиансен, Л., Дружественное введение в математическую логику ( Дженесео, Нью-Йорк : Библиотека Милна, 2015), стр. 100–102.
7. Чанг, CC , и Кейслер, HJ , Теория моделей , 3-е изд. ( Mineola & New York : 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 Books )
• Мальцев, Анатолий Иванович (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 Books )
• Сколем, Торальф (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 Books )
• Скулем, Торальф (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
• Crossley, JN ; Ash, CJ; Brickhill, CJ; Stillwell, JC; Williams, NH (1972), Что такое математическая логика?, Лондон/Оксфорд/Нью-Йорк: Oxford University Press , стр. 59–60, ISBN 0-19-888087-1, ЗБЛ  0251.02001
• Доусон, Джон У. младший (1993), «Компактность логики первого порядка: от Гёделя до Линдстрёма», История и философия логики , 14 : 15–37, doi :10.1080/01445349308837208
• Ходжес, Уилфрид (1993), Теория моделей, Кембридж: Cambridge Univ. Pr., ISBN 978-0-521-30442-9
• Пуаза, Бруно (2000), Курс теории моделей: Введение в современную математическую логику , Берлин, Нью-Йорк: Springer, ISBN 978-0-387-98655-5

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

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