Cтраница 2
Доказательство, ( ii) следует непосредственно из ( i) и теоремы Левенгейма - Скулема о понижении мощности. [16]
Это доказательство геделевской теоремы о полноте заодно дает нам и новое доказательство теоремы Левенгейма о том, что всякая выполнимая формула выполнима в области натуральных чисел. Действительно, из неопровержимости формулы 5 мы сделали вывод не только о ее выполнимости вообще, но и о выполнимости в области натуральных чисел; с другой стороны, из выполнимости формулы, как мы знаем, вытекает ее неопровержимость. [17]
Однако если эта формула выполнима на некоторой области, то в силу теоремы Левенгейма она выполнима и на некоторой конечной или счетной области. Из этого следует, что посредством аксиом рассматриваемого типа невозможно отличить несчетную область от счетной или конечной. Оказывается, однако, что аксиомы, содержащие символы переменных предикатов, могут характеризовать несчетные множества и даже множества заданной несчетной мощности в том смысле, что все удовлетворяющие им области несчетны и имеют в точности данную мощность. [18]
Тем замечательнее то, что, как следует, с одной стороны, из теоремы Левенгейма - Скулема о существовании моделей произвольной мощности для непротиворечивых систем аксиом ( см. [143, 144]), а с другой - из теоремы Геделя о неполноте аксиоматической арифметики ( см., например, [9, 10, 174]), категоричность является не правилом, а лишь исключением, и притом не слишком интересным: она возможна лишь для систем с конечными моделями. Дальнейшее обсуждение этого интересного, но весьма тонкого и сложного вопроса увело бы нас. [19]
Докажите, что всякая интерпретация I имеет элементарную подин-терпретацию J со счетной областью; выведите из этого утверждения аналог теоремы Левенгейма - Сколема, доказанной в тексте. [20]
Таким образом, мы доказали утверждение, что если формула ( 1) выполнима на некоторой области, то она выполнима на ее конечной или счетной части, что и составляет теорему Левенгейма. [21]
Его доказательство особенно важно в теории моделей потому, что в нем вводится метод построения моделей из индивидных констант. Теорема Левенгейма - Скулема - Тарского была впервые доказана даже раньше, чем теорема о полноте; случай а со доказан Левенгеймом [1915] и Скулемом [1920], а общий случай - Тарским. Первые же применения теоремы о полноте Генкиным, Мальцевым, Робинсоном и Тарским дали большой толчок развитию теории моделей. [22]
Если предикатная формула F выполнима в некоторой непустой) области, то F выполнима в области натуральных чисел. Теорема Левенгейма [1915], называемая также теоремой Левенгейма - Ско-лема. [23]
Разрешим интерпретациям приписывать значения несчетному множеству одноместных предикатных символов. Покажите, что теорема Левенгейма - Сколема, как мы ее формулировали, оказывается в этом случае ложной. [24]
Приведенное доказательство теоремы Морли значительно проще, чем первоначальное доказательство Морли, и принадлежит Балдуину и Лахлану. Две основные леммы, а именно теорема Левенгейма - Скулема - Тарского о двух кардиналах и лемма 7.1.13, не были известны Морли, с другой стороны, первоначальное доказательство Морли дает большее количество дополнительной информации о ( о-стабильных теориях, которая представляет самостоятельный интерес. Одно из замечаний Морли, которое нетрудно доказывается, касается понятия неразличимости в стабильных теориях. [25]
Если предикатная формула F выполнима в некоторой непустой) области, то F выполнима в области натуральных чисел. Теорема Левенгейма [1915], называемая также теоремой Левенгейма - Ско-лема. [26]
Теорема Левенгейма ( 1915 г.), сформулированная пятью абзацами выше, отвечает на этот вопрос отрицательно. В 1919 г. Сколем существенно обобщил результат Левенгейма, доказав теорему, из которой непосредственно следует не только теорема Левенгейма, но и доказанное в гл. Теорема Сколема ( 1919 г.) гласит, что всякая интерпретация1 обладает элементарно эквивалентной ей подинтерпретацией со счетной областью. [27]
Теоретико-доказательственным двойником этой теоремы является утверждение о том, что всякая формула исчисления предикатов в отношении выводимости равносильна некоторой бинарной формуле. Для доказательства этой теоремы можно, как это и сделал Эрбран, преобразовать с помощью критериев опровержимости доказательство теоремы Левенгейма в финитное доказательство соответствующей теоремы теории доказательств. [28]
До начала 50 - х годов ее не выделяли отчетливо в качестве самостоятельной области математических исследований. Однако ее исторические корни уходят в такие более старые предметы, как логика, универсальная алгебра и теория множеств, а некоторые из более ранних работ, например теорему Левенгейма, ныне относят к теории моделей. Теория моделей многим обязана общим методам, первоначально развитым в более старых разделах математики. В нашей книге-мы не раз столкнемся с такой ситуацией; сейчас для примера достаточно упомянуть хотя бы важное понятие насыщенной модели ( гл. [29]
Так, теорема Левенгейма показывает, что никакое непротиворечивое предложение не может заключать в себе требования несчетности модели. Теорема Морли показывает, что логика предикатов первого порядка в том, что касается категоричности, не позволяет отличить одну несчетную мощность от другой. С помощью же теоремы компактности было показано, что многие интересные свойства моделей нельзя выразить, используя только множества предложений логики первого порядка - например, не существует множества предложений, моделями которого были бы в точности все конечные модели. [30]