Löwenheim -cole теореор

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

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

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

Теорема

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

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

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

Дискуссия

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

Концепции

Подписи

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

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

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

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

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

Последствия

Утверждение, данное во введении, следует непосредственно из того, что 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$ Тестом Тарски -века .

Уловка, используемая в этом доказательстве, по сути, связана с Сколем, который представил символы функций для функций Skolem $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 ]} Он также использовал нынешние устойчивые обозначения Эрнста Шредодера . Краткое описание статьи на английском языке и использование современных обозначений см. В Брэди (2000 , глава 8).

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

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

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

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

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

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

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

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

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

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

Ссылки

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

Источники

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

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

Löwenheim, Leopold (1915), «О возможностях в относительной извести» (PDF) , математические летопись , 76 (4): 447–470, doi : 10.1007/bf01458217 , ISSN 0025-5831 , S2CID 116581304
- Löwenheim, Leopold (1977), «О возможностях в исчислении родственников», от Frege до Gödel: книга источника по математической логике, 1879-1931 (3-е изд.), Кембридж, Массачусетс: издательство Гарвардского университета, с. 228– 251, ISBN 0-674-32449-8 ( онлайн-копия , стр. 228, в Google Книгах )
Maltsev, Anatoly Ivanovich (1936), "Untersuchungen aus dem Gebiete der mathematischen Logik" , Matematicheskii Sbornik , Novaya Seriya, 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
Veblen, Oswald (1904), «Система аксиомов для геометрии», транзакции Американского математического общества , 5 (3): 343–384, doi : 10.2307/1986462 , ISSN 0002-9947 , JSTOR 1986462

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

Badesa, Calixto (2004), «Рождение теории модели: теорема Лёвенгейма» в рамках теории родственников , Принстон, Нью -Джерси: издательство Принстонского университета, 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; Brickhill, CJ; Стиллвелл, JC; Williams, NH (1972), что такое математическая логика? , Лондон/Оксфорд/Нью -Йорк: издательство Оксфордского университета , с. 59–60, ISBN 0-19-888087-1 , LDL 0251.02001
Доусон, Джон В. младший (1993), «Компактность логики первого порядка: от Геделя до Линдстрёма», «История и философия логики» , 14 : 15–37, doi : 10.1080/01445349308337208
Ходжес, Уилфрид (1993), Теория модели , Кембридж: Кембриджский университет. Pr., Isbn 978-0-521-30442-9
Poizat, Bruno (2000), курс по теории моделей: введение в современную математическую логику , Берлин, Нью -Йорк: Springer, ISBN 978-0-387-98655-5

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

Сахарав, а .; Weeptelee, EW "Одуванчики Sklem Теорема" . МАТЕРДЛОРД .
Беррис, Стэнли Н., Вклад логиков, часть II, от Ричарда Дедекинда до Герхарда Дженцена
Беррис, Стэнли Н., вниз по теореме Лёвенгейм -Сколем
Симпсон, Стивен Г. (1998), Теория модели

[n-1] Перейти обратно: ^а ^б ^с ^д ^и Нурани, К. Ф., Теория функториальных моделей: новые приложения к алгебраической топологии, описательным множествам и вычислительным категориям топос ( Торонто : 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 ]