Теорема Лёвенгейма – Сколема - Löwenheim–Skolem theorem

В математической логике , то теорема Löwenheim-Skolem является теоремой о существовании и мощности из моделей , названное в честь Леопольда Löwenheim и Thoralf Сколемого .

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

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

Теорема

В своей общей форме, Löwenheim-Skolem теорема утверждает , что для каждой сигнатуры сг , каждая бесконечная σ - структура М и каждое бесконечное кардинальное число х ≥ | σ | существует такая σ -структура N , что | N | = κ и такой, что

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

Теорема часто делится на две части, соответствующие двум приведенным выше случаям. Часть теоремы, утверждающая, что структура имеет элементарные подструктуры всех меньших бесконечных мощностей, известна как нисходящая теорема Лёвенгейма – Сколема . Часть теоремы, утверждающая, что структура имеет элементарные расширения всех больших мощностей, известна как восходящая теорема Левенгейма – Сколема .

Обсуждение

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

Концепции

Подписи

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

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

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

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

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

Последствия

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

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

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

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

Еще одно последствие, которое считалось особенно тревожным, - это существование счетной модели теории множеств, которая, тем не менее, должна удовлетворять предложению о несчетности действительных чисел. Теорема Кантора утверждает, что некоторые множества несчетны. Эта парадоксальная ситуация стала известна как парадокс Сколема ; это показывает, что понятие счетности не является абсолютным .

Доказательство эскиза

Нижняя часть

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

Семейство функций приводит к оператору preclosure на множестве мощности от${\ displaystyle f _ {\ varphi}}$ ${\ displaystyle F}$${\ displaystyle M}$

${\ Displaystyle F (A) = \ {е _ {\ varphi} (a_ {1}, \ dots, a_ {n}) \ in M ​​\ mid \ varphi \ in \ sigma; \, a_ {1}, \ dots , a_ {n} \ in A \}}$

для ${\ Displaystyle А \ Subteq M \ ,.}$

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

Уловка, использованная в этом доказательстве, в основном принадлежит Сколему, который ввел в язык функциональные символы для функций Сколема . Можно также определить как частичные функции, такие, которые определены тогда и только тогда, когда Единственным важным моментом является то, что это оператор предварительного закрытия, который содержит решение для каждой формулы с параметрами, в которых есть решение, и что ${\ displaystyle f _ {\ varphi}}$${\ displaystyle f _ {\ varphi}}$${\ displaystyle f _ {\ varphi}}$${\ displaystyle M \ models \ существует 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 приговоров с ≠ с « для любых двух различных новых постоянных символов гр и с» . Используя теорему компактности , легко убедиться, что полученная теория непротиворечива. Поскольку ее модели должны иметь мощность не менее κ , нижележащая часть этой теоремы гарантирует существование модели N, имеющей мощность ровно κ . Он содержит изоморфную копию M как элементарную подструктуру.

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

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

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

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

Первый значительный результат в том, что впоследствии модельная теория была теорема Löwenheim в в Leopold Löwenheim «s публикации„Über Möglichkeiten им Relativkalkül“(1915):

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

Источники

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

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

• Löwenheim, Leopold (1915), "Über Möglichkeiten им Relativkalkül" (PDF) , Mathematische Annalen , 76 (4): 447-470, DOI : 10.1007 / BF01458217 , ISSN  0025-5831 , S2CID  116581304
  • Левенхайм, Леопольд (1977), "Возможности в исчислении родственников", От Фреге до Геделя: Справочник по математической логике, 1879-1931 (3-е изд.), Кембридж, Массачусетс: Harvard University Press, стр. 228– 251, ISBN 0-674-32449-8( Интернет-копия , стр. 228, в Google Книгах )
• Мальцев, Анатолий Иванович (1936), "Untersuchungen aus dem Gebiete der Mathematischen Logik" , Математический сборник , Новая серия, 1 (43) (3): 323–336
• Сколем, Thoralf (1920), "Logisch-kombinatorische Untersuchungen über умереть Erfüllbarkeit Одер Beweisbarkeit mathematischer Sätze nebst Айнем Theoreme über Dichte Mengen", Videnskapsselskapet Skrifter, И. 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", Mathematikerkongressen I Helsingfors den 4–7 июля 1922 г., den Femte Skandinaviska Matematikerkongressen, Redogörelse : 217
  • Сколем, Торальф (1977), «Некоторые замечания по аксиоматизированной теории множеств», От Фреге до Гёделя: Справочник по математической логике, 1879-1931 (3-е изд.), Кембридж, Массачусетс: Harvard University Press, стр. 290–301 , ISBN 0-674-32449-8( Интернет-копия , стр. 290, в Google Книгах )
• Сколем, Торальф (1929), "Uber 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 Leila Haaparanta , ed. (2009), Развитие современной логики , Oxford University Press, ISBN 978-0-19-513731-6
• Брэди, Джеральдин (2000), От Пирса до Сколема: забытая глава в истории логики , Elsevier, ISBN 978-0-444-50334-3
• Кроссли, JN ; Эш, CJ; Брикхилл, CJ; Стиллвелл, JC; Уильямс, Н.Х. (1972), Что такое математическая логика? , Лондон / Оксфорд / Нью-Йорк: Oxford University Press , стр. 59–60, ISBN 0-19-888087-1, Zbl  0251,02001
• Доусон, Джон В., младший (1993), «Компактность первого порядка логики: От Геделя к Линдстрем», истории и философии логики , 14 : 15-37, DOI : 10,1080 / 01445349308837208
• Ходжес, Уилфрид (1993), Теория моделей , Кембридж: Cambridge Univ. Пр., ISBN 978-0-521-30442-9
• Poizat, Bruno (2000), Курс теории моделей: Введение в современную математическую логику , Берлин, Нью-Йорк: Springer, ISBN 978-0-387-98655-5

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

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