Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 28
Текст из файла (страница 28)
В самом деле, выберем в них счётные части, элементарно эквивалентные целым множествам. Эти части будут плотными и не будут иметь первого и последнего элементов, таккак эти свойства записываются формулами. Как известно (см., например, [6]), любые два счётных плотных упорядоченных множествабез первого и последнего элемента изоморфны, и потому (теорема 35,с. 112) элементарно эквивалентны. Следовательно, и исходные множества будут элементарно эквивалентны.Прежде всего уточним слова «часть интерпретации». Если сигнатура состоит только из предикатных символов, то проблем нет:взяв произвольное непустое подмножество X произвольной интерпретации, мы можем ограничить предикаты на X и получить новуюинтерпретацию.
Если в сигнатуре есть функциональные символы,мы должны ещё потребовать, чтобы X было замкнуто относительно соответствующих функций (значения функций на элементах подмножества X должны лежать в X). Возникающая при этом интерпретация с носителем X называется подструктурой исходной.Теорема 42 (Левенгейма – Сколема об элементарной подмодели).Пусть имеется конечная или счётная сигнатура σ и некоторая бесконечная интерпретация M этой сигнатуры. Тогда можно указатьсчётное подмножество подмножество M 0 ⊂ M , которое будет подструктурой M (замкнуто относительно сигнатурных функций) и длякоторого M будет элементарным расширением M 0 .
Начнём с первого требования теоремы: M 0 должно быть подструктурой. Само по себе его выполнить легко, как говорит следующая лемма.Лемма 1. Пусть A — произвольное конечное или счётное подмножество множества M . Тогда существует конечное или счётноемножество B ⊂ M , содержащее A, которое является подструктурой(замкнуто относительно сигнатурных функций в M ).Утверждение леммы почти очевидно: надо добавить к A результаты применения всех функций к его элементам, потом результатыприменения всех функций к добавленным элементам и так счётноечисло раз. (Другими словами, надо добавить значения всех термовсигнатуры на оценках, при которых индивидные переменные принимают значения в A.) Ясно, что получится конечное или счётное мно-124Языки первого порядка[гл.
3]жество, так как на каждом шаге расширения добавляется счётноемножество новых элементов и шагов счётное число. (Можно заметить также, что термов счётное число.) Лемма 1 доказана.Замкнутость подмножества A множества M относительно сигнатурных функций позволяет рассматривать интерпретацию с носителем A и с индуцированными из M функциями и предикатами.Однако она, конечно, не обязана быть элементарно эквивалентнойM , как показывает множество очевидных примеров.
(Если, скажем,в сигнатуре нет функций, а одни предикаты, то любое подмножествобудет замкнуто.)Поэтому нам необходимо ещё одно свойство замкнутости. ПустьA — некоторое подмножество M (напомним, что мы рассматриваеминтерпретацию сигнатуры σ с носителем M ). Назовём A экзистенциально замкнутым, если для всякой формулы ϕ(x, x1 , . . . , xn ) сигнатуры σ и для любых элементов a1 , . . .
, an ∈ A выполнено такоеутверждение: если существует m ∈ M , для которого (в M ) истинноϕ(m, a1 , . . . , an ), то элемент m с таким свойством можно выбрать ивнутри A.(Более формально следовало бы сказать, что для всякой формулы ϕ, параметры которой содержатся среди x, x1 , . . . , xn , и длялюбых элементов a1 , . .
. , an ∈ A выполнено такое утверждение: если существует m ∈ M , для которого ϕ истинна в интерпретации Mна оценке (x 7→ m, x1 7→ a1 , . . . , xn 7→ an ), то существует и элементm ∈ A с тем же свойством.)Обратите внимание, что в этом определении (в отличие от формулировки теоремы) не идёт речь об истинности какой бы то ни былоформулы в A — только об истинности в M . В нём говорится примерно вот что: если вообще (во всём M ) найдётся элемент, связанныйнеким формульным отношением с элементами a1 , . . .
, an ∈ A, то такой элемент найдётся и внутри самого A.Лемма 2. Пусть A ⊂ M — конечное или счётное множество. Тогдасуществует конечное или счётное множество B ⊂ M , содержащее Aи являющееся экзистенциально замкнутым.Доказательство леммы 2 аналогично доказательству предыдущей леммы: формул ϕ счётное число и конечных наборов элементов из A тоже счётное число. Поэтому можно посмотреть, в какихслучаях элемент m из определения экзистенциальной замкнутостисуществует, и добавить один из таких элементов (здесь используетсяаксиома выбора).
Один раз так сделать недостаточно, так как добавленные элементы также могут использоваться в качестве a1 , . . . , an[п. 11]Понижение мощности125в определении, поэтому такую процедуру надо повторить счётноечисло раз и взять объединение полученных множеств. Оно уже будет экзистенциально замкнуто (любой набор получается на конечномшаге и на следующем шаге он обслуживается, если нужно). Лемма 2доказана.На самом деле леммы 1 и 2 можно соединить.Лемма 3. Пусть A ⊂ M — конечное или счётное множество. Тогдасуществует конечное или счётное множество B ⊂ M , содержащее A,замкнутое относительно сигнатурных функций и экзистенциальнозамкнутое.В самом деле, чтобы получить такое множество B, достаточночередовать шаги замыкания относительно сигнатурных функций иэкзистенциального замыкания, а потом взять объединение полученной последовательности множеств.
Лемма 3 доказана.Лемма 4. Пусть M 0 ⊂ M замкнуто относительно сигнатурныхфункций и экзистенциально замкнуто. Тогда M является элементарным расширением M 0 .Отсюда уже вытекает утверждение теоремы 42: применим лемму 3 к некоторому счётному подмножеству множества M , а затемвоспользуемся леммой 4.Доказательство леммы 4 также довольно просто.
Напомним определение элементарного расширения: требуется, чтобыM 0 ϕ(a1 , . . . , an )⇔M ϕ(a1 , . . . , an )для любой формулы ϕ(x1 , . . . , xn ) и для любых a1 , . . . , an ∈ M 0 .(Формально следовало бы сказать: для любой формулы с параметрами и любой оценки, при которой все параметры принимаютзначения в M 0 , истинность этой формулы в M 0 на этой оценке равносильна истинности той же формулы в M на той же оценке.)Будем доказывать это индукцией по построению формулы ϕ.
Дляатомарных формул это очевидно: значения термов не зависят от того, проводим ли мы вычисления в M или M 0 , а предикаты на M 0индуцированы из M .Если формула ϕ есть конъюнкция, дизъюнкция, импликация илиотрицание, то её истинность как в M , так и в M 0 определяется истинностью её частей (и можно сослаться на предположение индукции).Единственный нетривиальный случай — если формула ϕ начинается с квантора. Мы можем сократить себе работу и рассматриватьтолько квантор существования, так как ∀ξ можно заменить на ¬∃ξ¬.126Языки первого порядка[гл.
3]Итак, пусть формула ϕ(x1 , . . . , xn ) имеет вид ∃x ψ(x, x1 , . . . , xn ).Если M 0 ϕ(a1 , . . . , an ) для некоторых a1 , . . . , an ∈ M 0 , то найдётсяэлемент m ∈ M 0 , для которого M 0 ψ(m, a1 , . . . , an ). Тогда по предположению индукции (формула ψ короче формулы ϕ) можно перейти к большей интерпретации и заключить, что M ψ(m, a1 , . . . , an ),и потому M ϕ(a1 , . .
. , an ). Обратное рассуждение просто так непроходит, поскольку существующий элемент m существует в M , ане в M 0 , и предположение индукции применить нельзя. Однако ровно для этого у нас есть требование экзистенциальной замкнутости,которое позволяет заменить элемент m на другой элемент из M 0 изавершить доказательство. Вот пример применения теоремы Левенгейма – Сколема в алгебре: существует алгебраически замкнутое счётное подполе поля Cкомплексных чисел. (В самом деле, требование алгебраической замкнутости можно записать в виде счётной последовательности формул — по одной для каждой степени многочлена.
Аксиомы поля также можно записать в виде формул. Значит, счётная элементарнаяподмодель поля C будет также алгебраически замкнутым полем.)Впрочем, алгебраистов такое применение скорее насмешит — онии так знают, что алгебраические элементы поля C (корни многочленов с целыми коэффициентами) образуют счётное алгебраическизамкнутое поле.Любопытный парадокс связан с попытками применить теоремуЛевенгейма – Сколема в теории множеств. Представим себе интерпретацию языка теории множеств (предикаты = и ∈), носителем которой является множество всех множеств. Такого множества, строгоговоря, не бывает, но если про это забыть и применить теорему Левенгейма – Сколема об элементарной подмодели, то можно оставитьлишь счётное число множеств так, чтобы истинность утвержденийтеории множеств не изменилась.
Но среди этих утверждений есть иутверждение о существовании несчётного множества — как же так?Это рассуждение содержит столько пробелов, что указать один изних совсем нетрудно. Тем не менее оно может быть переведено в аксиоматическую теорию множеств и даёт интересные (хотя уже непарадоксальные) результаты.Два дополнительных замечания усиливают теорему Левенгейма – Сколема. Во-первых, легко видеть, что для всякого конечногоили счётного подмножества A ⊂ M найдётся счётная элементарнаяподструктура M 0 ⊂ M , содержащая все элементы A.
(В самом деле, процесс замыкания, использованный при доказательстве, можно[п. 11]Понижение мощности127начинать с множества A.)Во-вторых, можно отказаться от требования счётности сигнатуры и сказать так: для всякого подмножества A ⊂ M найдётся элементарная подструктура M 0 ⊂ M , содержащая A, мощность которой непревосходит максимума из ℵ0 , мощности множества A и мощностисигнатуры. В самом деле, и конструкция замыкания относительносигнатурных операций, и конструкция экзистенциального замыкания, и счётное объединение возрастающей цепи не выводят мощностьза пределы указанного максимума, поскольку и формулы, и термыявляются конечными последовательностями символов сигнатуры исчётного числа других символов (см.
подробнее в [6]); то же самоеможно сказать о числе возможных наборов значений параметров.Мы научились уменьшать мощность структуры, не меняя множества истинных в ней формул. Можно, напротив, увеличивать мощность (соответствующее утверждение иногда называют теоремой Левенгейма – Сколема об элементарном расширении). Но эта конструкция использует теорему компактности для языков первого порядка,которая в свою очередь вытекает из теоремы Гёделя о полноте.
Поэтому мы отложим обсуждение этого утверждения до следующейглавы.4. Исчисление предикатов4.1. Общезначимые формулыИсчисление высказываний (глава 2) позволяло выводить все тавтологии из некоторого набора базисных тавтологий (названных аксиомами) с помощью некоторых правил вывода (на самом деле единственного правила modus ponens). Сейчас мы хотим решить аналогичную задачу для формул первого порядка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
