Вернемся от алгебры к логике и сформулируем
Критерий будет сформулирован в терминах некоторой игры, называемой игрой Эренфойхта. В ней участвуют два игрока, называемые Новатором ( Н ) и Консерватором ( К ). Игра определяется выбранной парой интерпретаций; как мы докажем, интерпретации элементарно эквивалентны тогда и только тогда, когда К имеет выигрышную стратегию в этой игре.
В начале игры Новатор объявляет натуральное число $$k$$. Далее они ходят по очереди, начиная с Н ; каждый из игроков делает $$k$$ ходов, после чего определяется победитель.
На $$i$$ -м ходу Н выбирает элемент в одной из интерпретаций (в любой из двух, причем выбор может зависеть от номера хода) и помечает его числом $$i$$. В ответ К выбирает некоторый элемент из другой интерпретации и также помечает его числом $$i$$. После $$k$$ ходов игра заканчивается. При этом в каждой интерпретации $$k$$ элементов оказываются помеченными числами от $$1$$ до $$k$$ (мы не учитываем, кто именно из игроков их пометил). Обозначим эти элементы $$a_1,a_2,\ldots,a_k$$ (для первой интерпретации; элемент $$a_i$$ имеет пометку $$i$$ ) и $$b_1,b_2,\ldots,b_k$$ (для второй). Элементы $$a_i$$ и $$b_i$$ (с одним и тем же $$i$$ ) будем называть соответствующими друг другу. Посмотрим, найдется ли предикат сигнатуры, который различает помеченные элементы первой и второй интерпретации (то есть истинен на некотором наборе помеченных элементов в одной интерпретации, но ложен на соответствующих элементах другой). Если такой предикат найдется, то выигрывает Новатор, в противном случае — Консерватор.
Прежде чем доказывать, что эта игра дает критерий элементарной эквивалентности, рассмотрим несколько простых примеров.
Рассмотрим сигнатуру упорядоченных
Н объявляет, что игра будет проведена в два хода и на первом ходу помечает число $$0$$ из интерпретации $$\mathbb N$$. В ответ К вынужден пометить некоторое число $$m$$ из $$\mathbb Z$$. На втором ходу Н помечает в $$\mathbb Z$$ некоторое число, меньшее $$m$$ (например, $$m-1$$ ). Теперь К проигрывает при любом ответном ходе, поскольку пометить число, меньшее нуля, он не может.
Для той же сигнатуры рассмотрим интерпретации в $$\mathbb Z$$ и $$\mathbb Q$$. Эти интерпретации не элементарно эквивалентны, поскольку порядок на рациональных числах плотен, а на целых — нет. Покажем, что в игре Эренфойхта снова выигрывает Новатор.
Игра будет проходить в три хода. На первых двух ходах Н помечает числа $$0$$ и $$1$$ из $$\mathbb{Z}$$. К должен пометить некоторые элементы $$b_1$$ и $$b_2$$ из $$\mathbb Q$$. При этом должно быть $$b_1<b_2$$ (иначе Н заведомо выиграет). Тогда на третьем ходу Н помечает любое рациональное число, лежащее строго между $$b_1$$ и $$b_2$$. Так как между $$0$$ и $$1$$ нет натуральных чисел, К не может соблюсти требования игры и проигрывает при любом ходе.
Рассмотрим теперь упорядоченные множества $$\mathbb Z$$ и $$\mathbb Z+\mathbb Z$$. Как мы видели, они элементарно эквивалентны, и потому должна существовать выигрышная стратегия для Консерватора. Как же он должен играть? Кажется разумным поддерживать одинаковые расстояния между соответствующими элементами в $$\mathbb Z$$ и $$\mathbb Z+\mathbb Z$$. Проблема в том, что в $$\mathbb Z+\mathbb Z$$ некоторые расстояния бесконечны (между элементами разных слагаемых). Что же делать Консерватору, если Новатор пометил два таких элемента?
К счастью для К, он знает заранее, сколько ходов осталось до конца игры. Ясно, что если игра скоро кончится, то Н не удастся отличить бесконечное расстояние от достаточно большого. Более точно, если до конца игры остается $$s$$ ходов, то К может считать все расстояния, большие или равные $$2^s$$, бесконечно большими. В конце (при $$s=0$$ ) это означает, что все ненулевые расстояния отождествляются (что правильно, так как в конце важен лишь порядок). Таким образом, К стремится поддерживать такой "инвариант" (как сказали бы программисты): соответствующие элементы в $$A$$ и в $$B$$ идут в одном и том же порядке, и расстояния между соответствующими парами соседей одинаковы (при этом все бесконечно большие расстояния считаются одинаковыми). Ясно, что такая стратегия гарантирует ему выигрыш; надо лишь проверить, что поддержать инвариант можно.
При очередном ходе Н возможны несколько случаев. Н мог разбить "конечный" (меньший $$2^s$$, где $$s$$ — число оставшихся ходов) промежуток на две части. В этом случае соответствующий промежуток в другом множестве также "конечен" и имеет ту же длину, так что К должен лишь выбрать элемент на том же расстоянии от концов. Пусть Н разбил "бесконечный" (длины $$2^s$$ или больше) промежуток на две части. Тогда хотя бы одна из частей будет иметь длину $$2^{s-1}$$ или больше, то есть на следующем шаге будет считаться "бесконечной". Если обе части "бесконечны" (с точки зрения следующего шага), то К должен разбить "бесконечный" (длины $$2^s$$ или более) промежуток другого множества на две "бесконечные" (длины $$2^{s-1}$$ или более) части; это, очевидно, возможно. Если одна часть " бесконечна", а другая "конечна", то надо отложить то же "конечное" расстояние в другом множестве. Наконец, обе части не могут быть "конечными" (если каждая меньше $$2^{s-1}$$, то в сумме будет меньше $$2^s$$ ).
Наконец, новый элемент мог быть больше (или меньше) всех уже отмеченных элементов интерпретации; в этом случае К должен отметить элемент другой интерпретации, находящийся на том же расстоянии от наибольшего (наименьшего) отмеченного элемента (или на "бесконечном" расстоянии, если такова была ситуация с выбранным Н элементом).
85. Кто выигрывает в игре Эренфойхта для упорядоченных множеств (а) $$\mathbb Z$$ и $$\mathbb R$$ ; (б) $$\mathbb R$$ и $$\mathbb Q$$ ; (в) $$\mathbb N$$ и $$\mathbb N+\mathbb Z$$? Как он должен играть?
Приведенные примеры делают правдоподобной связь между наличием
формулы, различающей интерпретации, и выигрышной стратегии для Н. При этом число ходов, которое понадобится Новатору,
соответствует кванторной глубине различающей интерпретации формулы.
Кванторная
Другими словами,
Рассмотрим позицию, которая складывается в игре после $$k$$ ходов Н и К (перед очередным ходом Н ) и за $$l$$ ходов до конца игры (таким образом, общая длина игры есть $$k+l$$ ). В этот момент в каждой из интерпретаций совместными усилиями Н и К выбрано по $$k$$ элементов. Пусть это будут элементы $$a_1,\dots,a_k$$ в одной интерпретации (назовем ее $$A$$ ) и $$b_1,\dots,b_k$$ в другой ( $$B$$ ).
Лемма. Если существует формула глубины $$l$$ с параметрами $$x_1,\dots,x_k$$, отличающая $$a_1,\dots,a_k$$ от $$b_1,\dots,b_k$$, то в указанной позиции Н имеет выигрышную стратегию; в противном случае ее имеет К.
Поясним смысл условия леммы. Пусть $$\varphi$$ — формула глубины $$l$$, все параметры которой содержатся в списке $$x_1,\dots,x_k$$. Тогда имеет смысл ставить вопрос о ее истинности в интерпретации $$A$$ при значениях параметров $$a_1,\dots,a_k$$, а также в интерпретации $$B$$ при значениях параметров $$b_1,\dots,b_k$$. Если окажется, что в одном случае формула $$\varphi$$ истинна, а в другом ложна, то мы говорим, что $$\varphi$$ отличает $$a_1,\dots,a_k$$ от $$b_1,\dots,b_k$$.
Пусть такая формула $$\varphi$$ существует. Она представляет собой
логическую (бескванторную) комбинацию некоторых формул вида $$\forall \xi \,\psi$$ и $$\exists\xi \psi$$, где $$\psi$$ — формула
глубины $$l-1$$. Хотя бы одна из формул, входящих в эту
комбинацию, должна также отличать $$a_1,\dots,a_k$$ от $$b_1,\dots,b_k$$.
Переходя к отрицанию, можно считать, что эта формула начинается
с
Обратное рассуждение (если наборы не отличимы никакой формулой глубины $$l$$, то К имеет выигрышную стратегию в оставшейся $$l$$ -ходовой игре) аналогично, но чуть более сложно. Здесь важно, что по существу есть лишь конечное число различных формул глубины $$k$$.
Точнее говоря, будем называть две формулы (с параметрами) эквивалентными, если они одновременно истинны или ложны в любой интерпретации на любой оценке. Поскольку сигнатура конечна, существует лишь конечное число атомарных формул, все параметры которых содержатся среди $$u_1,\dots,u_s$$. Существует лишь конечное число булевых функций с данным набором аргументов, поэтому существует лишь конечное число неэквивалентных бескванторных формул, все параметры которых содержатся среди $$u_1,\dots,u_s$$. Отсюда следует, что существует лишь конечное число неэквивалентных формул вида$$\exists u_s\, \psi(u_1,\dots,u_{s}),$$ и потому лишь конечное число неэквивалентных формул глубины $$1$$, параметры которых содержатся среди $$u_1,\dots,u_{s-1}$$. (Здесь мы снова используем утверждение о конечности числа булевых функций с данным конечным списком аргументов, а также возможность переименовывать переменную под квантором, благодаря которой мы можем считать, что эта переменная есть $$u_s$$.) Продолжая эти рассуждения, мы заключаем, что для любого $$l$$ и для любого набора переменных $$u_1,\dots,u_n$$ существует лишь конечное число неэквивалентных формул глубины $$l$$, все параметры которых содержатся среди $$u_1,\dots,u_n$$. (Здесь мы существенно используем конечность сигнатуры.)
Теперь можно закончить рассуждения про игру Эренфойхта. Пусть
элементы $$a_1,\dots,a_k$$ нельзя отличить от
элементов $$b_1,\dots,b_k$$ с помощью
формул глубины $$l$$. Опишем выигрышную стратегию для К. Пусть Н выбрал произвольный элемент в одной из
интерпретаций, скажем, $$a_{k+1}$$. Рассмотрим все формулы глубины $$l-1$$ с $$k+1$$ параметрами (с точностью до
эквивалентности их конечное число); некоторые из них будут истинны на $$a_1,\dots,a_{k+1}$$, а некоторые ложны. Тогда формула, утверждающая
существование $$a_{k+1}$$ с ровно такими свойствами (после квантора
существования идет конъюнкция всех
Лемма доказана. Ее частным случаем является обещанный критерий элементарной эквивалентности:
Теорема 41. Интерпретации $$A$$ и $$B$$ элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Эренфойхта выигрывает Консерватор.
86. Покажите, что условие конечности сигнатуры существенно (без него из элементарной эквивалентности не следует существование выигрышной стратегии для К ).
Заметим, что в некоторых случаях (например, для $$\mathbb Z$$ и $$\mathbb Z+\mathbb Z$$ ) игра Эренфойхта дает нам новый способ доказательства элементарной эквивалентности.
В этом разделе мы опишем прием, позволяющей в интерпретации большой мощности выделять часть, которая будет элементарно эквивалентна исходной (и, более того, исходная будет ее элементарным расширением в смысле определения). Например, во всяком бесконечном упорядоченном множестве этот прием позволит найти счетное подмножество, элементарно эквивалентное исходному как интерпретация сигнатуры $$({=},{<})$$.
С помощью этой конструкции (составляющей содержание теоремы Левенгейма-Сколема об элементарной подмодели) легко дать обещанное другое доказательство того, что любые два плотно упорядоченных множества без первого и последнего элемента элементарно эквивалентны. В самом деле, выберем в них счетные части, элементарно эквивалентные целым множествам. Эти части будут плотными и не будут иметь первого и последнего элементов, так как эти свойства записываются формулами. Как известно (см., например, [6]), любые два счетных плотных упорядоченных множества без первого и последнего элемента изоморфны, и потому (теорема 35) элементарно эквивалентны. Следовательно, и исходные множества будут элементарно эквивалентны.
Прежде всего уточним слова "часть интерпретации". Если сигнатура состоит только из предикатных символов, то проблем нет: взяв произвольное непустое подмножество $$X$$ произвольной интерпретации, мы можем ограничить предикаты на $$X$$ и получить новую интерпретацию. Если в сигнатуре есть функциональные символы, мы должны еще потребовать, чтобы $$X$$ было замкнуто относительно соответствующих функций (значения функций на элементах подмножества $$X$$ должны лежать в $$X$$ ). Возникающая при этом интерпретация с носителем $$X$$ называется подструктурой исходной.
Теорема 42 (Левенгейма-Сколема об элементарной подмодели). Пусть имеется конечная или счетная сигнатура $$\sigma$$ и некоторая бесконечная интерпретация $$M$$ этой сигнатуры. Тогда можно указать счетное подмножество подмножество $$M'\subset M$$, которое будет подструктурой $$M$$ (замкнуто относительно сигнатурных функций) и для которого $$M$$ будет элементарным расширением $$M'$$.
Начнем с первого требования теоремы: $$M'$$ должно быть подструктурой. Само по себе его выполнить легко, как говорит следующая лемма.
Лемма 1. Пусть $$A\subset M$$ — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество $$B\subset M$$, содержащее $$A$$, которое является подструктурой (замкнуто относительно сигнатурных функций в $$M$$ ).
Утверждение леммы почти очевидно: надо добавить к $$A$$ результаты применения всех функций к его элементам, потом результаты применения всех функций к добавленным элементам и так счетное число раз. (Другими словами, надо добавить значения всех термов сигнатуры на оценках, при которых индивидные переменные принимают значения в $$A$$.) Ясно, что получится конечное или счетное множество, так как на каждом шаге расширения добавляется счетное множество новых элементов и шагов счетное число. (Можно заметить также, что термов счетное число.) Лемма 1 доказана.
Замкнутость подмножества $$A$$ множества $$M$$ относительно сигнатурных функций позволяет рассматривать интерпретацию с носителем $$A$$ и с индуцированными из $$M$$ функциями и предикатами. Однако она, конечно, не обязана быть элементарно эквивалентной $$M$$, как показывает множество очевидных примеров. (Если, скажем, в сигнатуре нет функций, а одни предикаты, то любое подмножество будет замкнуто.)
Поэтому нам необходимо еще одно свойство замкнутости. Пусть $$A$$ — некоторое подмножество $$M$$ (напомним, что мы рассматриваем интерпретацию сигнатуры $$\sigma$$ с носителем $$M$$ ). Множество $$A$$ назовем экзистенциально замкнутым, если для всякой формулы $$\varphi(x,x_1,\dots,x_n)$$ сигнатуры $$\sigma$$ и для любых элементов $$a_1,\dots,a_n\in A$$ выполнено такое утверждение: если существует $$m\in M$$, для которого (в $$M$$ ) истинно $$\varphi(m,a_1,\dots,a_n)$$, то элемент $$m$$ с таким свойством можно выбрать и внутри $$A$$.
(Более формально следовало бы сказать, что для всякой формулы $$\varphi$$, параметры которой содержатся среди $$x,x_1,\dots,x_n$$, и для любых элементов $$a_1,\dots,a_n\hm\in A$$ выполнено такое утверждение: если существует $$m\hm\in M$$, для которого $$\varphi$$ истинна в интерпретации $$M$$ на оценке $$(x\hm\mapsto m,x_1\hm\mapsto a_1,\dots,x_n\hm\mapsto a_n)$$, то существует и элемент $$m\hm\in A$$ с тем же свойством.)
Обратите внимание, что в этом определении (в отличие от формулировки теоремы) не идет речь об истинности какой бы то ни было формулы в $$A$$ — только об истинности в $$M$$. В нем говорится примерно вот что: если вообще (во всем $$M$$ ) найдется элемент, связанный неким формульным отношением с элементами $$a_1,\dots,a_n\in A$$, то такой элемент найдется и внутри самого $$A$$.
Лемма 2. Пусть $$A\subset M$$ — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество $$B\subset M$$, содержащее $$A$$, являющееся экзистенциально замкнутым.
Доказательство леммы 2 аналогично доказательству предыдущей леммы: формул $$\varphi$$ счетное число и конечных наборов элементов из $$A$$ тоже счетное число. Поэтому можно посмотреть, в каких случаях элемент $$m$$ из определения экзистенциальной замкнутости существует, и добавить один из таких элементов (здесь используется аксиома выбора). Один раз так сделать недостаточно, так как добавленные элементы также могут использоваться в качестве $$a_1,\dots,a_n$$ в определении, поэтому такую процедуру надо повторить счетное число раз и взять объединение полученных множеств. Оно уже будет экзистенциально замкнуто (любой набор получается на конечном шаге и на следующем шаге он обслуживается, если нужно). Лемма 2 доказана.
На самом деле леммы 1 и 2 можно соединить.
Лемма 3. Пусть $$A\subset M$$ — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество $$B\subset M$$, содержащее $$A$$, замкнутое относительно сигнатурных функций и экзистенциально замкнутое.
В самом деле, чтобы получить такое множество $$B$$, достаточно чередовать шаги замыкания относительно сигнатурных функций и экзистенциального замыкания, а потом взять объединение полученной последовательности множеств. Лемма 3 доказана.
Лемма 4. Пусть $$M'\subset M$$ замкнуто относительно сигнатурных функций и экзистенциально замкнуто. Тогда $$M$$ является элементарным расширением $$M'$$.
Отсюда уже вытекает утверждение теоремы 42: применим лемму 3 к некоторому счетному подмножеству множества $$M$$, а затем воспользуемся леммой 4.
Доказательство леммы 4 также довольно просто. Напомним определение элементарного расширения: требуется, чтобы$$M'\vDash \varphi(a_1,\dots,a_n) \quad \Leftrightarrow \quad M \vDash \varphi(a_1,\dots,a_n)$$ для любой формулы $$\varphi(x_1,\dots,x_n)$$ и для любых элементов $$a_1,\dots,a_n\hm\in M'$$.
(Формально следовало бы сказать: для любой формулы с параметрами и любой оценки, при которой все параметры принимают значения в $$M'$$, истинность этой формулы в $$M'$$ на этой оценке равносильна истинности той же формулы в $$M$$ на той же оценке.)
Будем доказывать это индукцией по построению формулы $$\varphi$$. Для атомарных формул это очевидно: значения термов не зависят от того, проводим ли мы вычисления в $$M$$ или $$M'$$, а предикаты на $$M'$$ индуцированы из $$M$$.
Если формула $$\varphi$$ есть конъюнкция, дизъюнкция, импликация или отрицание, то ее истинность как в $$M$$, так и в $$M'$$ определяется истинностью ее частей (и можно сослаться на предположение индукции).
Единственный нетривиальный случай — если формула $$\varphi$$
начинается с квантора. Мы можем сократить себе работу и
рассматривать только
Вот пример применения теоремы Левенгейма-Сколема в алгебре: существует алгебраически замкнутое счетное подполе поля $$\mathbb C$$ комплексных чисел. (В самом деле, требование алгебраической замкнутости можно записать в виде счетной последовательности формул — по одной для каждой степени многочлена. Аксиомы поля также можно записать в виде формул. Значит, счетная элементарная подмодель поля $$\mathbb C$$ будет также алгебраически замкнутым полем.)
Впрочем, алгебраистов такое применение скорее насмешит — они и так знают, что алгебраические элементы поля $$\mathbb C$$ (корни многочленов с целыми коэффициентами) образуют счетное алгебраически замкнутое поле.
Любопытный парадокс связан с попытками применить теорему
Левенгейма-Сколема в теории множеств. Представим себе
интерпретацию языка теории
Два дополнительных замечания усиливают теорему Левенгейма-Сколема. Во-первых, легко видеть, что для всякого конечного или счетного подмножества $$A\hm\subset M$$ найдется счетная элементарная подструктура $$M'\hm\subset M$$, содержащая все элементы $$A$$. (В самом деле, процесс замыкания, использованный при доказательстве, можно начинать с множества $$A$$.)
Во-вторых, можно отказаться от требования счетности сигнатуры и сказать так: для всякого подмножества $$A\subset M$$ найдется элементарная подструктура $$M'\subset M$$, содержащая $$A$$, мощность которой не превосходит максимума из $$\aleph_0$$, мощности множества $$A$$ и мощности сигнатуры. В самом деле, и конструкция замыкания относительно сигнатурных операций, и конструкция экзистенциального замыкания, и счетное объединение возрастающей цепи не выводят мощность за пределы указанного максимума, поскольку и формулы, и термы являются конечными последовательностями символов сигнатуры и счетного числа других символов (см. подробнее в [6]); то же самое можно сказать о числе возможных наборов значений параметров.
Мы научились уменьшать мощность структуры, не меняя множества истинных в ней формул. Можно, напротив, увеличивать мощность (соответствующее утверждение иногда называют теоремой Левенгейма-Сколема об элементарном расширении). Но эта конструкция использует теорему компактности для языков первого порядка, которая в свою очередь вытекает из теоремы Геделя о полноте. Поэтому мы отложим обсуждение этого утверждения до следующей лекции.
Вернемся от алгебры к логике и сформулируем
Критерий будет сформулирован в терминах некоторой игры, называемой игрой Эренфойхта. В ней участвуют два игрока, называемые Новатором ( Н ) и Консерватором ( К ). Игра определяется выбранной парой интерпретаций; как мы докажем, интерпретации элементарно эквивалентны тогда и только тогда, когда К имеет выигрышную стратегию в этой игре.
В начале игры Новатор объявляет натуральное число $$k$$. Далее они ходят по очереди, начиная с Н ; каждый из игроков делает $$k$$ ходов, после чего определяется победитель.
На $$i$$ -м ходу Н выбирает элемент в одной из интерпретаций (в любой из двух, причем выбор может зависеть от номера хода) и помечает его числом $$i$$. В ответ К выбирает некоторый элемент из другой интерпретации и также помечает его числом $$i$$. После $$k$$ ходов игра заканчивается. При этом в каждой интерпретации $$k$$ элементов оказываются помеченными числами от $$1$$ до $$k$$ (мы не учитываем, кто именно из игроков их пометил). Обозначим эти элементы $$a_1,a_2,\ldots,a_k$$ (для первой интерпретации; элемент $$a_i$$ имеет пометку $$i$$ ) и $$b_1,b_2,\ldots,b_k$$ (для второй). Элементы $$a_i$$ и $$b_i$$ (с одним и тем же $$i$$ ) будем называть соответствующими друг другу. Посмотрим, найдется ли предикат сигнатуры, который различает помеченные элементы первой и второй интерпретации (то есть истинен на некотором наборе помеченных элементов в одной интерпретации, но ложен на соответствующих элементах другой). Если такой предикат найдется, то выигрывает Новатор, в противном случае — Консерватор.
Прежде чем доказывать, что эта игра дает критерий элементарной эквивалентности, рассмотрим несколько простых примеров.
Рассмотрим сигнатуру упорядоченных
Н объявляет, что игра будет проведена в два хода и на первом ходу помечает число $$0$$ из интерпретации $$\mathbb N$$. В ответ К вынужден пометить некоторое число $$m$$ из $$\mathbb Z$$. На втором ходу Н помечает в $$\mathbb Z$$ некоторое число, меньшее $$m$$ (например, $$m-1$$ ). Теперь К проигрывает при любом ответном ходе, поскольку пометить число, меньшее нуля, он не может.
Для той же сигнатуры рассмотрим интерпретации в $$\mathbb Z$$ и $$\mathbb Q$$. Эти интерпретации не элементарно эквивалентны, поскольку порядок на рациональных числах плотен, а на целых — нет. Покажем, что в игре Эренфойхта снова выигрывает Новатор.
Игра будет проходить в три хода. На первых двух ходах Н помечает числа $$0$$ и $$1$$ из $$\mathbb{Z}$$. К должен пометить некоторые элементы $$b_1$$ и $$b_2$$ из $$\mathbb Q$$. При этом должно быть $$b_1<b_2$$ (иначе Н заведомо выиграет). Тогда на третьем ходу Н помечает любое рациональное число, лежащее строго между $$b_1$$ и $$b_2$$. Так как между $$0$$ и $$1$$ нет натуральных чисел, К не может соблюсти требования игры и проигрывает при любом ходе.
Рассмотрим теперь упорядоченные множества $$\mathbb Z$$ и $$\mathbb Z+\mathbb Z$$. Как мы видели, они элементарно эквивалентны, и потому должна существовать выигрышная стратегия для Консерватора. Как же он должен играть? Кажется разумным поддерживать одинаковые расстояния между соответствующими элементами в $$\mathbb Z$$ и $$\mathbb Z+\mathbb Z$$. Проблема в том, что в $$\mathbb Z+\mathbb Z$$ некоторые расстояния бесконечны (между элементами разных слагаемых). Что же делать Консерватору, если Новатор пометил два таких элемента?
К счастью для К, он знает заранее, сколько ходов осталось до конца игры. Ясно, что если игра скоро кончится, то Н не удастся отличить бесконечное расстояние от достаточно большого. Более точно, если до конца игры остается $$s$$ ходов, то К может считать все расстояния, большие или равные $$2^s$$, бесконечно большими. В конце (при $$s=0$$ ) это означает, что все ненулевые расстояния отождествляются (что правильно, так как в конце важен лишь порядок). Таким образом, К стремится поддерживать такой "инвариант" (как сказали бы программисты): соответствующие элементы в $$A$$ и в $$B$$ идут в одном и том же порядке, и расстояния между соответствующими парами соседей одинаковы (при этом все бесконечно большие расстояния считаются одинаковыми). Ясно, что такая стратегия гарантирует ему выигрыш; надо лишь проверить, что поддержать инвариант можно.
При очередном ходе Н возможны несколько случаев. Н мог разбить "конечный" (меньший $$2^s$$, где $$s$$ — число оставшихся ходов) промежуток на две части. В этом случае соответствующий промежуток в другом множестве также "конечен" и имеет ту же длину, так что К должен лишь выбрать элемент на том же расстоянии от концов. Пусть Н разбил "бесконечный" (длины $$2^s$$ или больше) промежуток на две части. Тогда хотя бы одна из частей будет иметь длину $$2^{s-1}$$ или больше, то есть на следующем шаге будет считаться "бесконечной". Если обе части "бесконечны" (с точки зрения следующего шага), то К должен разбить "бесконечный" (длины $$2^s$$ или более) промежуток другого множества на две "бесконечные" (длины $$2^{s-1}$$ или более) части; это, очевидно, возможно. Если одна часть " бесконечна", а другая "конечна", то надо отложить то же "конечное" расстояние в другом множестве. Наконец, обе части не могут быть "конечными" (если каждая меньше $$2^{s-1}$$, то в сумме будет меньше $$2^s$$ ).
Наконец, новый элемент мог быть больше (или меньше) всех уже отмеченных элементов интерпретации; в этом случае К должен отметить элемент другой интерпретации, находящийся на том же расстоянии от наибольшего (наименьшего) отмеченного элемента (или на "бесконечном" расстоянии, если такова была ситуация с выбранным Н элементом).
85. Кто выигрывает в игре Эренфойхта для упорядоченных множеств (а) $$\mathbb Z$$ и $$\mathbb R$$ ; (б) $$\mathbb R$$ и $$\mathbb Q$$ ; (в) $$\mathbb N$$ и $$\mathbb N+\mathbb Z$$? Как он должен играть?
Приведенные примеры делают правдоподобной связь между наличием
формулы, различающей интерпретации, и выигрышной стратегии для Н. При этом число ходов, которое понадобится Новатору,
соответствует кванторной глубине различающей интерпретации формулы.
Кванторная
Другими словами,
Рассмотрим позицию, которая складывается в игре после $$k$$ ходов Н и К (перед очередным ходом Н ) и за $$l$$ ходов до конца игры (таким образом, общая длина игры есть $$k+l$$ ). В этот момент в каждой из интерпретаций совместными усилиями Н и К выбрано по $$k$$ элементов. Пусть это будут элементы $$a_1,\dots,a_k$$ в одной интерпретации (назовем ее $$A$$ ) и $$b_1,\dots,b_k$$ в другой ( $$B$$ ).
Лемма. Если существует формула глубины $$l$$ с параметрами $$x_1,\dots,x_k$$, отличающая $$a_1,\dots,a_k$$ от $$b_1,\dots,b_k$$, то в указанной позиции Н имеет выигрышную стратегию; в противном случае ее имеет К.
Поясним смысл условия леммы. Пусть $$\varphi$$ — формула глубины $$l$$, все параметры которой содержатся в списке $$x_1,\dots,x_k$$. Тогда имеет смысл ставить вопрос о ее истинности в интерпретации $$A$$ при значениях параметров $$a_1,\dots,a_k$$, а также в интерпретации $$B$$ при значениях параметров $$b_1,\dots,b_k$$. Если окажется, что в одном случае формула $$\varphi$$ истинна, а в другом ложна, то мы говорим, что $$\varphi$$ отличает $$a_1,\dots,a_k$$ от $$b_1,\dots,b_k$$.
Пусть такая формула $$\varphi$$ существует. Она представляет собой
логическую (бескванторную) комбинацию некоторых формул вида $$\forall \xi \,\psi$$ и $$\exists\xi \psi$$, где $$\psi$$ — формула
глубины $$l-1$$. Хотя бы одна из формул, входящих в эту
комбинацию, должна также отличать $$a_1,\dots,a_k$$ от $$b_1,\dots,b_k$$.
Переходя к отрицанию, можно считать, что эта формула начинается
с
Обратное рассуждение (если наборы не отличимы никакой формулой глубины $$l$$, то К имеет выигрышную стратегию в оставшейся $$l$$ -ходовой игре) аналогично, но чуть более сложно. Здесь важно, что по существу есть лишь конечное число различных формул глубины $$k$$.
Точнее говоря, будем называть две формулы (с параметрами) эквивалентными, если они одновременно истинны или ложны в любой интерпретации на любой оценке. Поскольку сигнатура конечна, существует лишь конечное число атомарных формул, все параметры которых содержатся среди $$u_1,\dots,u_s$$. Существует лишь конечное число булевых функций с данным набором аргументов, поэтому существует лишь конечное число неэквивалентных бескванторных формул, все параметры которых содержатся среди $$u_1,\dots,u_s$$. Отсюда следует, что существует лишь конечное число неэквивалентных формул вида$$\exists u_s\, \psi(u_1,\dots,u_{s}),$$ и потому лишь конечное число неэквивалентных формул глубины $$1$$, параметры которых содержатся среди $$u_1,\dots,u_{s-1}$$. (Здесь мы снова используем утверждение о конечности числа булевых функций с данным конечным списком аргументов, а также возможность переименовывать переменную под квантором, благодаря которой мы можем считать, что эта переменная есть $$u_s$$.) Продолжая эти рассуждения, мы заключаем, что для любого $$l$$ и для любого набора переменных $$u_1,\dots,u_n$$ существует лишь конечное число неэквивалентных формул глубины $$l$$, все параметры которых содержатся среди $$u_1,\dots,u_n$$. (Здесь мы существенно используем конечность сигнатуры.)
Теперь можно закончить рассуждения про игру Эренфойхта. Пусть
элементы $$a_1,\dots,a_k$$ нельзя отличить от
элементов $$b_1,\dots,b_k$$ с помощью
формул глубины $$l$$. Опишем выигрышную стратегию для К. Пусть Н выбрал произвольный элемент в одной из
интерпретаций, скажем, $$a_{k+1}$$. Рассмотрим все формулы глубины $$l-1$$ с $$k+1$$ параметрами (с точностью до
эквивалентности их конечное число); некоторые из них будут истинны на $$a_1,\dots,a_{k+1}$$, а некоторые ложны. Тогда формула, утверждающая
существование $$a_{k+1}$$ с ровно такими свойствами (после квантора
существования идет конъюнкция всех
Лемма доказана. Ее частным случаем является обещанный критерий элементарной эквивалентности:
Теорема 41. Интерпретации $$A$$ и $$B$$ элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Эренфойхта выигрывает Консерватор.
86. Покажите, что условие конечности сигнатуры существенно (без него из элементарной эквивалентности не следует существование выигрышной стратегии для К ).
Заметим, что в некоторых случаях (например, для $$\mathbb Z$$ и $$\mathbb Z+\mathbb Z$$ ) игра Эренфойхта дает нам новый способ доказательства элементарной эквивалентности.
В этом разделе мы опишем прием, позволяющей в интерпретации большой мощности выделять часть, которая будет элементарно эквивалентна исходной (и, более того, исходная будет ее элементарным расширением в смысле определения). Например, во всяком бесконечном упорядоченном множестве этот прием позволит найти счетное подмножество, элементарно эквивалентное исходному как интерпретация сигнатуры $$({=},{<})$$.
С помощью этой конструкции (составляющей содержание теоремы Левенгейма-Сколема об элементарной подмодели) легко дать обещанное другое доказательство того, что любые два плотно упорядоченных множества без первого и последнего элемента элементарно эквивалентны. В самом деле, выберем в них счетные части, элементарно эквивалентные целым множествам. Эти части будут плотными и не будут иметь первого и последнего элементов, так как эти свойства записываются формулами. Как известно (см., например, [6]), любые два счетных плотных упорядоченных множества без первого и последнего элемента изоморфны, и потому (теорема 35) элементарно эквивалентны. Следовательно, и исходные множества будут элементарно эквивалентны.
Прежде всего уточним слова "часть интерпретации". Если сигнатура состоит только из предикатных символов, то проблем нет: взяв произвольное непустое подмножество $$X$$ произвольной интерпретации, мы можем ограничить предикаты на $$X$$ и получить новую интерпретацию. Если в сигнатуре есть функциональные символы, мы должны еще потребовать, чтобы $$X$$ было замкнуто относительно соответствующих функций (значения функций на элементах подмножества $$X$$ должны лежать в $$X$$ ). Возникающая при этом интерпретация с носителем $$X$$ называется подструктурой исходной.
Теорема 42 (Левенгейма-Сколема об элементарной подмодели). Пусть имеется конечная или счетная сигнатура $$\sigma$$ и некоторая бесконечная интерпретация $$M$$ этой сигнатуры. Тогда можно указать счетное подмножество подмножество $$M'\subset M$$, которое будет подструктурой $$M$$ (замкнуто относительно сигнатурных функций) и для которого $$M$$ будет элементарным расширением $$M'$$.
Начнем с первого требования теоремы: $$M'$$ должно быть подструктурой. Само по себе его выполнить легко, как говорит следующая лемма.
Лемма 1. Пусть $$A\subset M$$ — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество $$B\subset M$$, содержащее $$A$$, которое является подструктурой (замкнуто относительно сигнатурных функций в $$M$$ ).
Утверждение леммы почти очевидно: надо добавить к $$A$$ результаты применения всех функций к его элементам, потом результаты применения всех функций к добавленным элементам и так счетное число раз. (Другими словами, надо добавить значения всех термов сигнатуры на оценках, при которых индивидные переменные принимают значения в $$A$$.) Ясно, что получится конечное или счетное множество, так как на каждом шаге расширения добавляется счетное множество новых элементов и шагов счетное число. (Можно заметить также, что термов счетное число.) Лемма 1 доказана.
Замкнутость подмножества $$A$$ множества $$M$$ относительно сигнатурных функций позволяет рассматривать интерпретацию с носителем $$A$$ и с индуцированными из $$M$$ функциями и предикатами. Однако она, конечно, не обязана быть элементарно эквивалентной $$M$$, как показывает множество очевидных примеров. (Если, скажем, в сигнатуре нет функций, а одни предикаты, то любое подмножество будет замкнуто.)
Поэтому нам необходимо еще одно свойство замкнутости. Пусть $$A$$ — некоторое подмножество $$M$$ (напомним, что мы рассматриваем интерпретацию сигнатуры $$\sigma$$ с носителем $$M$$ ). Множество $$A$$ назовем экзистенциально замкнутым, если для всякой формулы $$\varphi(x,x_1,\dots,x_n)$$ сигнатуры $$\sigma$$ и для любых элементов $$a_1,\dots,a_n\in A$$ выполнено такое утверждение: если существует $$m\in M$$, для которого (в $$M$$ ) истинно $$\varphi(m,a_1,\dots,a_n)$$, то элемент $$m$$ с таким свойством можно выбрать и внутри $$A$$.
(Более формально следовало бы сказать, что для всякой формулы $$\varphi$$, параметры которой содержатся среди $$x,x_1,\dots,x_n$$, и для любых элементов $$a_1,\dots,a_n\hm\in A$$ выполнено такое утверждение: если существует $$m\hm\in M$$, для которого $$\varphi$$ истинна в интерпретации $$M$$ на оценке $$(x\hm\mapsto m,x_1\hm\mapsto a_1,\dots,x_n\hm\mapsto a_n)$$, то существует и элемент $$m\hm\in A$$ с тем же свойством.)
Обратите внимание, что в этом определении (в отличие от формулировки теоремы) не идет речь об истинности какой бы то ни было формулы в $$A$$ — только об истинности в $$M$$. В нем говорится примерно вот что: если вообще (во всем $$M$$ ) найдется элемент, связанный неким формульным отношением с элементами $$a_1,\dots,a_n\in A$$, то такой элемент найдется и внутри самого $$A$$.
Лемма 2. Пусть $$A\subset M$$ — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество $$B\subset M$$, содержащее $$A$$, являющееся экзистенциально замкнутым.
Доказательство леммы 2 аналогично доказательству предыдущей леммы: формул $$\varphi$$ счетное число и конечных наборов элементов из $$A$$ тоже счетное число. Поэтому можно посмотреть, в каких случаях элемент $$m$$ из определения экзистенциальной замкнутости существует, и добавить один из таких элементов (здесь используется аксиома выбора). Один раз так сделать недостаточно, так как добавленные элементы также могут использоваться в качестве $$a_1,\dots,a_n$$ в определении, поэтому такую процедуру надо повторить счетное число раз и взять объединение полученных множеств. Оно уже будет экзистенциально замкнуто (любой набор получается на конечном шаге и на следующем шаге он обслуживается, если нужно). Лемма 2 доказана.
На самом деле леммы 1 и 2 можно соединить.
Лемма 3. Пусть $$A\subset M$$ — произвольное конечное или счетное множество. Тогда существует конечное или счетное множество $$B\subset M$$, содержащее $$A$$, замкнутое относительно сигнатурных функций и экзистенциально замкнутое.
В самом деле, чтобы получить такое множество $$B$$, достаточно чередовать шаги замыкания относительно сигнатурных функций и экзистенциального замыкания, а потом взять объединение полученной последовательности множеств. Лемма 3 доказана.
Лемма 4. Пусть $$M'\subset M$$ замкнуто относительно сигнатурных функций и экзистенциально замкнуто. Тогда $$M$$ является элементарным расширением $$M'$$.
Отсюда уже вытекает утверждение теоремы 42: применим лемму 3 к некоторому счетному подмножеству множества $$M$$, а затем воспользуемся леммой 4.
Доказательство леммы 4 также довольно просто. Напомним определение элементарного расширения: требуется, чтобы$$M'\vDash \varphi(a_1,\dots,a_n) \quad \Leftrightarrow \quad M \vDash \varphi(a_1,\dots,a_n)$$ для любой формулы $$\varphi(x_1,\dots,x_n)$$ и для любых элементов $$a_1,\dots,a_n\hm\in M'$$.
(Формально следовало бы сказать: для любой формулы с параметрами и любой оценки, при которой все параметры принимают значения в $$M'$$, истинность этой формулы в $$M'$$ на этой оценке равносильна истинности той же формулы в $$M$$ на той же оценке.)
Будем доказывать это индукцией по построению формулы $$\varphi$$. Для атомарных формул это очевидно: значения термов не зависят от того, проводим ли мы вычисления в $$M$$ или $$M'$$, а предикаты на $$M'$$ индуцированы из $$M$$.
Если формула $$\varphi$$ есть конъюнкция, дизъюнкция, импликация или отрицание, то ее истинность как в $$M$$, так и в $$M'$$ определяется истинностью ее частей (и можно сослаться на предположение индукции).
Единственный нетривиальный случай — если формула $$\varphi$$
начинается с квантора. Мы можем сократить себе работу и
рассматривать только
Вот пример применения теоремы Левенгейма-Сколема в алгебре: существует алгебраически замкнутое счетное подполе поля $$\mathbb C$$ комплексных чисел. (В самом деле, требование алгебраической замкнутости можно записать в виде счетной последовательности формул — по одной для каждой степени многочлена. Аксиомы поля также можно записать в виде формул. Значит, счетная элементарная подмодель поля $$\mathbb C$$ будет также алгебраически замкнутым полем.)
Впрочем, алгебраистов такое применение скорее насмешит — они и так знают, что алгебраические элементы поля $$\mathbb C$$ (корни многочленов с целыми коэффициентами) образуют счетное алгебраически замкнутое поле.
Любопытный парадокс связан с попытками применить теорему
Левенгейма-Сколема в теории множеств. Представим себе
интерпретацию языка теории
Два дополнительных замечания усиливают теорему Левенгейма-Сколема. Во-первых, легко видеть, что для всякого конечного или счетного подмножества $$A\hm\subset M$$ найдется счетная элементарная подструктура $$M'\hm\subset M$$, содержащая все элементы $$A$$. (В самом деле, процесс замыкания, использованный при доказательстве, можно начинать с множества $$A$$.)
Во-вторых, можно отказаться от требования счетности сигнатуры и сказать так: для всякого подмножества $$A\subset M$$ найдется элементарная подструктура $$M'\subset M$$, содержащая $$A$$, мощность которой не превосходит максимума из $$\aleph_0$$, мощности множества $$A$$ и мощности сигнатуры. В самом деле, и конструкция замыкания относительно сигнатурных операций, и конструкция экзистенциального замыкания, и счетное объединение возрастающей цепи не выводят мощность за пределы указанного максимума, поскольку и формулы, и термы являются конечными последовательностями символов сигнатуры и счетного числа других символов (см. подробнее в [6]); то же самое можно сказать о числе возможных наборов значений параметров.
Мы научились уменьшать мощность структуры, не меняя множества истинных в ней формул. Можно, напротив, увеличивать мощность (соответствующее утверждение иногда называют теоремой Левенгейма-Сколема об элементарном расширении). Но эта конструкция использует теорему компактности для языков первого порядка, которая в свою очередь вытекает из теоремы Геделя о полноте. Поэтому мы отложим обсуждение этого утверждения до следующей лекции.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.