Языки и исчисления

Понижение мощности


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

С помощью этой конструкции (составляющей содержание теоремы Левенгейма-Сколема об элементарной подмодели) легко дать обещанное другое доказательство того, что любые два плотно упорядоченных множества без первого и последнего элемента элементарно эквивалентны. В самом деле, выберем в них счетные части, элементарно эквивалентные целым множествам. Эти части будут плотными и не будут иметь первого и последнего элементов, так как эти свойства записываются формулами. Как известно (см., например, [6]), любые два счетных плотных упорядоченных множества без первого и последнего элемента изоморфны, и потому (теорема 35) элементарно эквивалентны. Следовательно, и исходные множества будут элементарно эквивалентны.

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

Теорема 42 (Левенгейма-Сколема об элементарной подмодели).

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

Начнем с первого требования теоремы: должно быть подструктурой. Само по себе его выполнить легко, как говорит следующая лемма.

Лемма 1. Пусть — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество , содержащее , которое является подструктурой (замкнуто относительно сигнатурных функций в ).

Утверждение леммы почти очевидно: надо добавить к результаты применения всех функций к его элементам, потом результаты применения всех функций к добавленным элементам и так счетное число раз. (Другими словами, надо добавить значения всех термов сигнатуры на оценках, при которых индивидные переменные принимают значения в .) Ясно, что получится конечное или счетное множество, так как на каждом шаге расширения добавляется счетное множество новых элементов и шагов счетное число. (Можно заметить также, что термов счетное число.) Лемма 1 доказана.

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

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

с таким свойством можно выбрать и внутри .

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

истинна в интерпретации на оценке , то существует и элемент с тем же свойством.)

Обратите внимание, что в этом определении (в отличие от формулировки теоремы) не идет речь об истинности какой бы то ни было формулы в — только об истинности в . В нем говорится примерно вот что: если вообще (во всем ) найдется элемент, связанный неким формульным отношением с элементами , то такой элемент найдется и внутри самого .

Лемма 2. Пусть — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество , содержащее , являющееся экзистенциально замкнутым.

Доказательство леммы 2 аналогично доказательству предыдущей леммы: формул счетное число и конечных наборов элементов из тоже счетное число. Поэтому можно посмотреть, в каких случаях элемент из определения экзистенциальной замкнутости существует, и добавить один из таких элементов (здесь используется аксиома выбора). Один раз так сделать недостаточно, так как добавленные элементы также могут использоваться в качестве в определении, поэтому такую процедуру надо повторить счетное число раз и взять объединение полученных множеств. Оно уже будет экзистенциально замкнуто (любой набор получается на конечном шаге и на следующем шаге он обслуживается, если нужно). Лемма 2 доказана.

На самом деле леммы 1 и 2 можно соединить.

Лемма 3. Пусть — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество , содержащее , замкнутое относительно сигнатурных функций и экзистенциально замкнутое.

В самом деле, чтобы получить такое множество , достаточно чередовать шаги замыкания относительно сигнатурных функций и экзистенциального замыкания, а потом взять объединение полученной последовательности множеств. Лемма 3 доказана.

Лемма 4. Пусть замкнуто относительно сигнатурных функций и экзистенциально замкнуто. Тогда

является элементарным расширением .

Отсюда уже вытекает утверждение теоремы 42: применим лемму 3 к некоторому счетному подмножеству множества , а затем воспользуемся леммой 4.

Доказательство леммы 4 также довольно просто. Напомним определение элементарного расширения: требуется, чтобы

для любой формулы и для любых элементов .

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

Будем доказывать это индукцией по построению формулы . Для атомарных формул это очевидно: значения термов не зависят от того, проводим ли мы вычисления в или , а предикаты на индуцированы из .

Если формула есть конъюнкция, дизъюнкция, импликация или отрицание, то ее истинность как в , так и в

определяется истинностью ее частей (и можно сослаться на предположение индукции).

Единственный нетривиальный случай — если формула

начинается с квантора. Мы можем сократить себе работу и рассматривать только квантор существования, так как

можно заменить на . Итак, пусть имеет вид

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

Вот пример применения теоремы Левенгейма-Сколема в алгебре: существует алгебраически замкнутое счетное подполе поля

комплексных чисел. (В самом деле, требование алгебраической замкнутости можно записать в виде счетной последовательности формул — по одной для каждой степени многочлена. Аксиомы поля также можно записать в виде формул. Значит, счетная элементарная подмодель поля будет также алгебраически замкнутым полем.)

Впрочем, алгебраистов такое применение скорее насмешит — они и так знают, что алгебраические элементы поля (корни многочленов с целыми коэффициентами) образуют счетное алгебраически замкнутое поле.

Любопытный парадокс связан с попытками применить теорему Левенгейма-Сколема в теории множеств. Представим себе интерпретацию языка теории множеств (предикаты и ), носителем которой является множество всех множеств. Такого множества, строго говоря, не бывает, но если про это забыть и применить теорему Левенгейма-Сколема об элементарной подмодели, то можно оставить лишь счетное число множеств так, чтобы истинность утверждений теории множеств не изменилась. Но среди этих утверждений есть и утверждение о существовании несчетного множества — как же так? Это рассуждение содержит столько пробелов, что указать один из них совсем нетрудно. Тем не менее оно может быть переведено в аксиоматическую теорию множеств и дает интересные (хотя уже не парадоксальные) результаты.

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

Во-вторых, можно отказаться от требования счетности сигнатуры и сказать так: для всякого подмножества найдется элементарная подструктура , содержащая , мощность которой не превосходит максимума из , мощности множества и мощности сигнатуры. В самом деле, и конструкция замыкания относительно сигнатурных операций, и конструкция экзистенциального замыкания, и счетное объединение возрастающей цепи не выводят мощность за пределы указанного максимума, поскольку и формулы, и термы являются конечными последовательностями символов сигнатуры и счетного числа других символов (см. подробнее в [6]); то же самое можно сказать о числе возможных наборов значений параметров.

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


Содержание раздела