В математической логике , то теорема Löwenheim-Skolem является теоремой о существовании и мощности из моделей , названное в честь Леопольда Löwenheim и Thoralf Сколемого .
Точная формулировка приведена ниже. Это означает, что если счетная теория первого порядка имеет бесконечную модель , то для каждого бесконечного кардинального числа κ она имеет модель размера κ, и что никакая теория первого порядка с бесконечной моделью не может иметь уникальную модель с точностью до изоморфизма . Как следствие, теории первого порядка не могут контролировать мощность своих бесконечных моделей.
Теорема Левенгейма – Сколема (направленная вниз) является одним из двух ключевых свойств, наряду с теоремой компактности , которые используются в теореме Линдстрема для характеристики логики первого порядка . В общем, теорема Левенгейма – Сколема не верна в более сильных логиках, таких как логика второго порядка .
Теорема
В своей общей форме, Löwenheim-Skolem теорема утверждает , что для каждой сигнатуры сг , каждая бесконечная σ - структура М и каждое бесконечное кардинальное число х ≥ | σ | существует σ-структура N такая, что | N | = κ и такой, что
- если κ <| M | тогда N - элементарная подструктура M ;
- если κ > | M | то N является элементарным расширением М .
Теорема часто делится на две части, соответствующие двум пунктам выше. Часть теоремы, утверждающая, что структура имеет элементарные подструктуры всех меньших бесконечных мощностей, известна как нисходящая теорема Лёвенгейма – Сколема . [1] Часть теоремы, утверждающая, что структура имеет элементарные расширения всех больших мощностей, известна как восходящая теорема Левенгейма – Сколема . [2]
Обсуждение
Ниже мы более подробно остановимся на общей концепции подписей и структур.
Концепции
Подписи
Подпись состоит из множества функциональных символов S FUNC , набора символов отношений S отн и функцийпредставляющие арность символов функций и отношений. (Нулевой функциональный символ называется постоянным символом.) В контексте логики первого порядка подпись иногда называют языком. Он называется счетным, если набор символов функций и отношений в нем счетный, и в общем случае мощность сигнатуры - это мощность множества всех содержащихся в ней символов.
Теория первого порядка состоит из фиксированной сигнатуры и фиксированного набора предложений (формул без свободных переменных) в этой сигнатуре. Теории часто задаются путем предоставления списка аксиом, которые порождают теорию, или путем предоставления структуры и принятия теории как состоящей из предложений, которым удовлетворяет структура.
Структуры / Модели
Для сигнатуры σ σ- структура M является конкретной интерпретацией символов в σ. Он состоит из базового набора (часто также обозначаемого « M ») вместе с интерпретацией символов функций и отношений σ. Интерпретация постоянной символ о в М является просто элементом М . В более общем смысле , интерпретация из п -ичного символа функции F является функцией от М н к М . Точно так же интерпретация символа отношения R является n -арным отношением на M , то есть подмножеством M n .
Подструктура σ-структуры M получается путем взятия подмножества N из M, которое замкнуто относительно интерпретаций всех функциональных символов в σ (следовательно, включает интерпретации всех постоянных символов в σ), а затем ограничения интерпретаций символы отношений к N . Элементарная подструктура является весьма частным случаем этого; в частности, элементарная подструктура удовлетворяет в точности тем же предложениям первого порядка, что и исходная структура (ее элементарное расширение).
Последствия
Утверждение, данное во введении, следует сразу же, если взять M за бесконечную модель теории. Доказательство верхней части теоремы также показывает, что теория с произвольно большими конечными моделями должна иметь бесконечную модель; иногда это считается частью теоремы.
Теория называется категоричной, если она имеет только одну модель, с точностью до изоморфизма. Этот термин был введен Вебленом (1904) , и некоторое время после этого математики надеялись, что смогут положить математику на прочный фундамент, описав категориальную теорию первого порядка некоторой версии теории множеств. Теорема Левенгейма – Сколема нанесла первый удар по этой надежде, поскольку из нее следует, что теория первого порядка, имеющая бесконечную модель, не может быть категоричной. Позже, в 1931 году, эта надежда была полностью разбита теоремой Гёделя о неполноте .
Многие следствия теоремы Левенгейма – Сколема казались логикам в начале 20 века нелогичными, поскольку различие между свойствами первого и не первого порядка еще не было понято. Одним из таких следствий является существование бесчисленных моделей истинной арифметики , которые удовлетворяют каждой аксиоме индукции первого порядка, но имеют неиндуктивные подмножества.
Пусть N обозначает натуральные числа, а R - вещественные числа. Из теоремы следует, что теория ( N , +, ×, 0, 1) (теория истинной арифметики первого порядка) имеет бесчисленное количество моделей и что теория ( R , +, ×, 0, 1) (теория вещественных замкнутых полей ) имеет счетную модель. Конечно, существуют аксиоматизации, характеризующие ( N , +, ×, 0, 1) и ( R , +, ×, 0, 1) с точностью до изоморфизма. Теорема Левенгейма – Сколема показывает, что эти аксиоматизации не могут быть первого порядка. Например, в теории действительных чисел полнота линейного порядка, используемого для характеристики R как полного упорядоченного поля, не является свойством первого порядка .
Еще одно последствие, которое считалось особенно тревожным, - это существование счетной модели теории множеств, которая, тем не менее, должна удовлетворять предложению о несчетности действительных чисел. Эта парадоксальная ситуация стала известна как парадокс Сколема ; это показывает, что понятие счетности не является абсолютным .
Доказательство эскиза
Нижняя часть
Для каждого первого порядка -формула из выбранной аксиомы следует существование функции
такое, что для всех , либо
или же
Снова применяя аксиому выбора, мы получаем функцию из формул первого порядка к таким функциям
Семейство функций дает начало оператору предварительного закрытия на множестве мощности от
для
Итерация счетное количество раз приводит к оператору закрытия Взяв произвольное подмножество такой, что , и определив можно увидеть, что также потом элементарная подструктура в тесте Тарского Воота .
Уловка, использованная в этом доказательстве, в основном принадлежит Сколему, который ввел функциональные символы для функций Сколема. на язык. Можно также определитькак частичные функции, такие что определено тогда и только тогда, когда Единственный важный момент - это то, что является оператором предварительного раскрытия такой, что содержит решение для каждой формулы с параметрами в который имеет решение в и это
Восходящая часть
Во- первых, расширяет подпись путем добавления нового символа постоянной для каждого элемента М . Полная теория M для расширенной сигнатуры»называется элементарная схема из М . На следующем шаге к сигнатуре добавляется много новых постоянных символов, а к элементарной диаграмме M добавляются предложения c ≠ c ' для любых двух различных новых постоянных символов c и c' . Используя теорему компактности , легко убедиться, что полученная теория непротиворечива. Поскольку ее модели должны иметь мощность не менее κ, нижележащая часть этой теоремы гарантирует существование модели N, которая имеет мощность ровно κ. Он содержит изоморфную копию M как элементарную подструктуру. [3] [4] : 100–102
В другой логике
Хотя (классическая) теорема Левенгейма – Сколема очень тесно связана с логикой первого порядка, варианты верны и для других логик. Например, каждая непротиворечивая теория в логике второго порядка имеет модель меньшую, чем первый суперкомпактный кардинал (при условии, что таковая существует). Минимальный размер, при котором (нисходящая) теорема типа Левенхайма – Сколема применяется в логике, называется числом Левенхайма и может использоваться для характеристики силы этой логики. Более того, если мы выходим за рамки логики первого порядка, мы должны отказаться от одной из трех вещей: счетной компактности, нисходящей теоремы Левенгейма – Сколема или свойств абстрактной логики. [5] : 134
Исторические заметки
Этот отчет основан в основном на Доусоне (1993) . Чтобы понять раннюю историю теории моделей, необходимо различать синтаксическую непротиворечивость (никакое противоречие не может быть получено с помощью правил дедукции для логики первого порядка) и выполнимость (модель существует). Несколько удивительно, но даже до того, как теорема о полноте сделала различие ненужным, термин согласованный использовался иногда в одном смысле, а иногда в другом.
Первый значительный результат в том, что впоследствии модельная теория была теорема Löwenheim в в Leopold Löwenheim «s публикации„Über Möglichkeiten им Relativkalkül“(1915):
- Для любой счетной сигнатуры σ каждое выполнимое σ-предложение выполнимо в счетной модели.
Статья Левенхайма фактически была посвящена более общему исчислению Пирса – Шредера ( алгебра отношений с кванторами). [1] Он также использовал устаревшие обозначения Эрнста Шредера . Краткое изложение статьи на английском языке с использованием современных обозначений см. В Brady (2000 , глава 8).
Согласно полученной исторической точке зрения, доказательство Левенхайма было ошибочным, поскольку оно неявно использовало лемму Кёнига, не доказывая ее, хотя в то время эта лемма еще не была опубликована. В своем ревизионистском отчете Бадеса (2004) считает, что доказательство Левенхайма было полным.
Сколем (1920) дал (правильное) доказательство, используя формулы в том, что позже будет называться нормальной формой Сколема, и опираясь на аксиому выбора:
- Каждая счетная теория , которая выполнима в модели M , выполнима в счетной подструктуре М .
Сколем (1922) также доказал следующую более слабую версию без аксиомы выбора:
- Каждая счетная теория, выполнимая в модели, также выполнима в счетной модели.
Сколем (1929) упростил Сколем (1920) . Наконец, Анатолий Иванович Мальцев (Анато́лий Ива́нович Ма́льцев, 1936) доказал теорему Левенгейма – Сколема в ее полной общности ( Мальцев, 1936 ). Он процитировал заметку Сколема, согласно которой теорема была доказана Альфредом Тарским на семинаре в 1928 году. Поэтому общую теорему иногда называют теоремой Левенгейма – Сколема – Тарского . Но Тарский не помнил своего доказательства, и остается загадкой, как он мог сделать это без теоремы компактности .
Несколько иронично то, что имя Сколема связано как с восходящим, так и с нисходящим направлением теоремы:
- «Я следую обычаю называть следствие 6.1.4 восходящей теоремой Левенхайма-Сколема. Но на самом деле Сколем даже не верил в это, потому что не верил в существование несчетных множеств». - Ходжес (1993) .
- «Сколем [...] отверг результат как бессмысленный; Тарский [...] очень разумно ответил, что формалистическая точка зрения Сколема должна считать нисходящую теорему Лёвенгейма-Сколема бессмысленной, как и восходящую». - Ходжес (1993) .
- «Легенда гласит, что Торальф Сколем до конца своей жизни был возмущен ассоциацией его имени с результатом этого типа, который он считал абсурдом, поскольку бесчисленные множества были для него фикцией, не существующей на самом деле». - Поазат (2000) .
Рекомендации
- ^ a b Нурани, К.Ф., Теория функциональных моделей: новые приложения к алгебраической топологии, описательным множествам и вычислительным категориям Topos ( Торонто : Apple Academic Press, 2014), стр . 160–161 .
- ^ Шеппард, Б., Логика бесконечности ( Кембридж : Издательство Кембриджского университета , 2014), стр. 372 .
- ^ Черч, A. , & Лэнгфорд, CH , ред., Журнал символической логики ( Сторрс, Коннектикут : Ассоциация символической логики , 1981), стр. 529.
- Перейти ↑ Leary, CC, & Kristiansen, L., A Friendly Introduction to Mathematical Logic ( Geneseo, NY : Milne Library, 2015), pp. 100–102 .
- ↑ Chang, CC , & Keisler, HJ , Model Theory , 3-е изд. ( Минеола и Нью-Йорк : Dover Publications , 1990), стр. 134 .
Источники
Теорема Левенгейма – Сколема рассматривается во всех вводных текстах по теории моделей или математической логике .
Исторические публикации
- 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 книги. Лейла Хаапаранта , изд. (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 CS1 maint: обескураженный параметр ( ссылка )
- Доусон, Джон В., младший (1993), «Компактность первого порядка логики: От Геделя к Линдстрем», истории и философии логики , 14 : 15-37, DOI : 10,1080 / 01445349308837208 CS1 maint: обескураженный параметр ( ссылка )
- Ходжес, Уилфрид (1993), Теория моделей , Кембридж: Cambridge Univ. Пр., ISBN 978-0-521-30442-9
- Poizat, Bruno (2000), Курс теории моделей: Введение в современную математическую логику , Берлин, Нью-Йорк: Springer, ISBN 978-0-387-98655-5
Внешние ссылки
- Сахаров, А .; Weisstein, EW "Теорема Левенхайма-Сколема" . MathWorld .
- Беррис, Стэнли Н., Вклад логиков, Часть II, От Ричарда Дедекинда до Герхарда Гентцена
- Беррис, Стэнли Н., Нисходящая теорема Левенхайма – Сколема
- Симпсон, Стивен Г. (1998), Теория моделей