И.А. Пушкарев логика

81

Пример 1. Если интерпретации изоморфны, то для каждого элемента

иначе этот самый предикат и различит рассматриваемые интерпретации.

Пример 3. N и Z как интерпретации теории упорядоченных множеств не

являются элементарно эквивалентными: в N есть наименьший элемент

(считаем, что это 0), а в Z такового нет. Покажем, как Н может использовать это различие, чтобы выиграть за два хода.

Первым ходом он помечает 0 из N. В ответ К должен пометить некоторое

число m ÎZ . Вторым ходом Н помечает (m -1)Î Z , и, как бы ни ответил (в N)

К, предикат a2 < a1 ложен, а b2 < b1 – истинен.

Пример 4. Для той же сигнатуры рассмотрим(также неэквивалентные)

интерпретации Z и Q. Различие между ними в том, что вторая интерпретация представляет собой плотный линейный порядок: между любыми двумя числами

a < b есть третье: a < c < b . В этом случае Н выигрывает за три хода.

Первыми двумя ходами он помечает0 и 1 из Z. В ответ К помечает

элементарно эквивалентны, поэтому в соответствующей игре должен выиграть

противопоставить что-то этой стратегии, ни различить получившиеся наборы каким-либо предикатом.

Пример 6. Важным и довольно нетривиальным примером элементарно эквивалентных интерпретаций рассматриваемой сигнатуры является параZ и

Z+Z. Под Z+Z понимается порядковая сумма двух бесконечных цепейZ: их объединение при условии, что любое число из второго экземпляра больше

любого числа из первого экземпляра. Их элементарная эквивалентность нами пока не установлена, поэтому до завершения доказательства теоремы8.3. мы и не будем уверены в их элементарной эквивалентности.

Различие между интерпретациями очевидно: Z любые два числа находятся на конечном расстоянии одно от другого, в то время как Zв+Z

расстояние между числами из двух различных экземпляровZ не может быть конечным. Покажем, как именно К может«скрыть» это различие, пользуясь конечностью количества ходов в игре.

Пусть после очередного хода Н до окончания игры К осталось сделатьs

ходов (а Н – (s -1)). В этот момент он может считать все соседние выбранные

числа в обеих интерпретациях, расстояние между которыми больше, чем 3s ,

бесконечно-удалёнными друг от друга. При этом допущении он может придерживаться примерно той же стратегии, что и в прошлом примере, и даже

придерживаться в течение всей игры.

83

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

«бесконечный» интервал, то одна или обе из этих частей тоже будут

«бесконечны», и К сможет повторить и этот ход, учитывая, что на следующем ходу «бесконечными» считаются интервалы втрое короче , техкоторые считались таковыми на предыдущем ходу. Пусть он так и делает, и инвариант сохранится.

Для доказательства теоремы 8.3. нам потребуется одно новое понятие.

Определение 8.3. Зададим индуктивно на множестве формул новую

(1)если р – атомарная формула, то d (p)= 0 ;

(2)d (Ø p)= d (p);

(3)d (p Ù q)= d (p Ú q)= max{d (p), d (q)};

(4)d (Ex p)= d (Ax p)= d (p)+1.

когда часть игры (k ходов) уже сыграна и доказать построенное таким образом семейство утверждений (одно за другим, по индукции).

Лемма 8.4. показывает, что в случае, когда интерпретации не являются элементарно эквивалентными, Н может, начиная с формулы, различающей эти интерпретации, постоянно поддерживать рассмотренный инвариант и в итоге выиграть.

Теперь покажем, что если интерпретации элементарно эквивалентны, то выигрышная стратегия есть у К. Это делается почти аналогично.

Определение 8.4. Две формулы с одним и тем же набором свободных параметров назовём эквивалентными, если они истинны или ложны одновременно – в любой интерпретации и на любой оценке.

некоторый квантор на фиксированную переменную в двух эквивалентных

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

Теперь покажем, что, основываясь на этом соображении, К всегда сможет ответить на ход Н, восстановив неразличимость наборов.

Итак, пусть наборы a1, a2 , ..., ak и b1, b2 , ..., bk не различаются при помощи формул кванторной глубины не более s. Очередным ходом Н выбрал, не умаляя общности, число ak +1 . Рассмотрим все формулы с k + 1 свободным параметром

86

кванторной глубины s -1 (точнее – по одной формуле из каждого класса

(так как рассматриваемая формула имеет глубинуs и, следовательно, не может

различать наборы a1, a2 , ..., ak и b1, b2 , ..., bk ), формула ExP(x1, x2 , ..., xk , x)

истинна и для всех оценок, для которых xi = bi . Поэтому найдётся элемент bk +1 ,

§9. Понижение мощности

Вклассической средневековой науке известен принцип, называемый

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

«сущности, не являющиеся необходимыми»). Удивительно это или нет, но этот принцип оказался верен. Мы докажем его для счётных теорий, впрочем,

доказательство без труда переносится и на общий случай.

a1, a2 , ..., an Î M ¢ (количество равно арности функции f) f (a1, a2 , ..., an )Î M ¢.

87

Теорема 9.1. (Теорема Лёвенгейма-Сколема о понижении мощности,

счётный случай). Пусть есть конечная или счётная сигнатура, имеющая

самой подструктурой действительной интерпретации, существование которой утверждается теоремой 9.1.). Однако – априори – могла бы существовать какая-

нибудь совсем другая интерпретация теории плотного линейного порядка, не являющаяся элементарно эквивалентной этим двум. Тот факт, что её не существует, как минимум, любопытен. Покажем, как его можно вывести из теоремы 9.1.

Действительно, согласно упомянутой теореме, у такой интерпретации

должна существовать счётная подструктура, ей элементарно эквивалентная.

Она представляет собой счётное линейно упорядоченное множество без

наибольшего и наименьшего элементов, порядок на котором ещё и плотен

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

Теорема 9.2. Любые две такие (счётные) интерпретации изоморфны.

Доказательство. Сначала заметим, что любые дваn-элементных

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

Рассмотрим две интерпретации X и Y. Так как обе они счётны, элементы соответствующих множеств (обозначим их так же: X и Y) можно занумеровать натуральными числами. Элемент множества X с номером i обозначим xi , i-й

элемент множества Y, соответственно, обозначим yi . Построим изоморфизм q : X ® Y .

элемент либо меньше всехxi , либо больше их всех, либо находится между какими-то двумя соседними из них. Выберем произвольный элемент yn+1

множества Y, ещё не вошедший вYn , и занимающий по отношению к его

элементам точно такое же положение. После этого положимqn+1 (xi )= yi

"i Î[1, ..., n +1]. На чётном шаге поступаем аналогично, но выбираем yn+1 ÎY с

наименьшим возможным номером. В пределе получим биекциюq¥ между частью X и частью Y. Наконец, заметим, что из-за того, что мы на нечётных шагах выбирали элемент множестваX с наименьшим номером, областью определения q¥ является всё множество X. Аналогично, областью значений q¥

является всё множествоY. Поэтому построенное отображениеq¥ есть искомый изоморфизм.

QED

Следствие 9.3. Любые две интерпретации теории плотного линейного порядка элементарно эквивалентны.

Доказательство. Их счётные элементарные подструктуры изоморфны, и,

следовательно, элементарно эквивалентны. Остаётся заметить, что каждая из них является элементарной подструктурой исходной структуры, поэтому они также элементарно эквивалентны по транзитивности.

QED

Доказательство теоремы 9.1. Во-первых, заметим, что требование «быть подструктурой» само по себе выполнить совсем нетрудно, даже в заметно более общем виде.

89

Лемма 9.4. Пусть A Í M – не более чем счётное множество. Тогда существует не более чем счётное функционально замкнутое множествоS (A),

такое, что A Í S (A)Í M .

Доказательство. Добавив к множеству А результаты применения к его

i=1

функционально замкнуто относительно всех сигнатурных функций, то есть построенное множество – искомое.

QED

Замечание. Совершенно ясно, что лемма тривиально обобщается на случай более чем счётногоА и более чем счётного множества сигнатурных функций: множество конечных векторов, составленных из элементов А, всегда равномощно А, если А счётно или более чем счётно, поэтому мощность S (A) в

общем случае равна максимуму мощностей множестваА и множества сигнатурных функций.

Однако интерпретация, предметным множеством которой является S (A),

конечно, не обязана быть элементарной подструктурой: формула вида

Еx1Ex2 ...Exn p(x1, x2 , ..., xn ) может быть истинна на множествеМ и ложна на