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

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

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

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

• 1 Теорема
• 2 Обсуждение
  • 2.1 Концепции
    • 2.1.1 Подписи
    • 2.1.2 Структуры / модели
  • 2.2 Последствия
• 3 Контрольный эскиз
  • 3.1 Нижняя часть
  • 3.2 Верхняя часть
• 4 В другой логике
• 5 Исторические заметки
• 6 Ссылки
• 7 Источники
  • 7.1 Исторические публикации
  • 7.2 Вторичные источники
• 8 Внешние ссылки

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

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

• если κ lt;| M | тогда N - элементарная подструктура M ;
• если κ gt; | 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), Теория моделей