Игра Эренфойхта

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

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

В начале игры Новатор объявляет натуральное число . Далее они ходят по очереди, начиная с Н; каждый из игроков делает

ходов, после чего определяется победитель.

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

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

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

Рассмотрим сигнатуру упорядоченных множеств (предикаты и ) и ее естественные интерпретации в и . Они не являются элементарно эквивалентными, поскольку среди натуральных чисел есть наименьшее, а среди целых — нет. Покажем, что в игре Эренфойхта для данных интерпретаций выигрывает Новатор.

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



Для той же сигнатуры рассмотрим интерпретации в и . Эти интерпретации не элементарно эквивалентны, поскольку порядок на рациональных числах плотен, а на целых — нет. Покажем, что в игре Эренфойхта снова выигрывает Новатор.

Игра будет проходить в три хода. На первых двух ходах Н

помечает числа и из . К

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

помечает любое рациональное число, лежащее строго между и . Так как между и нет натуральных чисел, К не может соблюсти требования игры и проигрывает при любом ходе.



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

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


Таким образом, К стремится поддерживать такой "инвариант" (как сказали бы программисты): соответствующие элементы в и в идут в одном и том же порядке, и расстояния между соответствующими парами соседей одинаковы (при этом все бесконечно большие расстояния считаются одинаковыми). Ясно, что такая стратегия гарантирует ему выигрыш; надо лишь проверить, что поддержать инвариант можно.

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

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

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





85. Кто выигрывает в игре Эренфойхта для упорядоченных множеств (а) и ; (б) и ; (в) и ? Как он должен играть?

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


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

Глубина атомарных формул равна нулю.Глубина формул и равна максимуму глубин формул и .Глубина формулы равна глубине формулы .Глубина формул и на единицу больше глубины формулы .

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

Рассмотрим позицию, которая складывается в игре после

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

элементов. Пусть это будут элементы в одной интерпретации (назовем ее ) и в другой ().

Лемма. Если существует формула глубины с параметрами , отличающая от , то в указанной позиции Н имеет выигрышную стратегию; в противном случае ее имеет К.

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

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

Это и будет выигрывающим ходом Новатора; при любом ответном ходе Консерватора формула

будет ложной. Таким образом, некоторая формула глубины

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




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

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

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

ходов) у К есть выигрышная стратегия.

Лемма доказана. Ее частным случаем является обещанный критерий элементарной эквивалентности:

Теорема 41. Интерпретации и элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Эренфойхта выигрывает Консерватор.

86. Покажите, что условие конечности сигнатуры существенно (без него из элементарной эквивалентности не следует существование выигрышной стратегии для К).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Аксиомы и правила вывода

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

Почти столь же просто понять, что ничего другого такие аксиомы не дадут: если пользоваться лишь схемами аксиом - , разрешая брать в них в качестве , ,

произвольные формулы сигнатуры , а в качестве правила вывода использовать modus ponens, то все выводимые формулы будут частными случаями пропозициональных тавтологий. В самом деле, если какая-то подформула начинается с квантора, то в выводе она может встречаться только как единое целое, то есть такая подформула ведет себя как пропозициональная переменная.

92. Проведите это рассуждение аккуратно.

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

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

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

К сожалению, все не так просто. Например, если формула

имеет вид то подстановка терма вместо даст абсурдное выражение

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

которое хотя и будет формулой, но имеет совсем не тот смысл, который нам нужен.

Конечно, в данном случае по смыслу ясно, что подставлять

надо лишь вместо самого первого вхождения переменной . Но если мы хотим определить формальную систему аксиом и правил вывода, то надо дать формальные определения.

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

любое вхождение переменной в терм или атомарную формулу свободно;свободные вхождения переменной в формулу

являются ее свободными вхождениями в формулу ;свободные вхождения любой переменной в одну из формул

и являются свободными вхождениями в , и ;переменная не имеет свободных вхождений в формулы и ; свободные вхождения остальных переменных в являются свободными вхождениями в эти две формулы.

Сравнивая это определение с индуктивным определением параметров формулы, мы видим, что параметры — это переменные, имеющие свободные вхождения в формулу.



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

Теперь можно внести поправку в сказанное выше и считать, что аксиомами являются формулы где есть результат подстановки

вместо всех свободных вхождений переменной . Однако такой оговорки недостаточно, как показывает следующий пример.

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

дает формулу , в которой

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

93. Приведите пример формулы вида

в которой происходит коллизия переменных и которая не является общезначимой. (Ответ: .)

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

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

Педантичный читатель мог бы попросить доказать, что результат такой подстановки будет формулой. Это проще всего сделать так: дать индуктивное определение корректной подстановки, равносильное исходному.

Сначала определим индуктивно результат подстановки терма

вместо переменной в терм ; этот результат будем обозначать :

есть ; для любой переменной , отличной от , мы полагаем равным .если есть - местный функциональный символ, а — термы, то



Теперь индуктивное определение продолжается для формул:

для атомарных формул: если есть -местный предикатный символ, а — термы, то

и подстановка является корректной;подстановка терма вместо переменной в формулу корректна, если она корректна для формулы , при этом



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

аналогично для формул и ;

наконец, подстановка вместо в формулу корректна в двух случаях:

(1) если не является параметром формулы (это возможно, когда не является параметром или когда совпадает с ); при этом подстановка ничего не меняет в формуле;

(2) переменная является параметром формулы , но переменная не входит в терм и подстановка корректна; при этом

Аналогично определяется корректная подстановка в формулу .



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

После всех этих приготовлений мы можем сформулировать две оставшиеся схемы аксиом исчисления предикатов: формула

(12)

и двойственная ей формула

(13)

будут аксиомами исчисления предикатов, если указанные в них подстановки корректны.

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

Отсюда следует, что формулы

и будут аксиомами исчисления предикатов (для любой формулы и переменной ).

Нужны ли нам еще какие-нибудь аксиомы и правила вывода? Конечно, нужны, поскольку уже сформулированные аксиомы не полностью отражают смысл кванторов. (Например, они вполне согласуются с таким пониманием этого смысла: формула всегда ложна, а формула

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

Если переменная не является параметром формулы , то правила Бернайса разрешают такие переходы:


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

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

Используя первое правило Бернайса, легко установить допустимость правила обобщения (если в исчислении предикатов выводима формула сверху от черты, то выводима и формула снизу). В самом деле, возьмем какую-нибудь выводимую формулу без параметров (например, аксиому, в которой вместо , и

подставлены замкнутые формулы). Раз выводима формула , то выводима и формула (поскольку

является тавтологией и даже аксиомой). Теперь по правилу Бернайса выводим и применяем правило MP к этой формуле и к формуле .

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

Второе правило Бернайса также вполне естественно: желая доказать в предположении , мы говорим: пусть такое существует, возьмем его и докажем (то есть докажем

со свободной переменной ).

94. Покажите, что класс выводимых в исчислении предикатов формул не изменится, если мы вместо правил Бернайса добавим туда правило обобщения и две аксиомы и

(в которых требуется, чтобы переменная не была параметром формулы ).

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

Корректность исчисления предикатов

Теорема 43. Всякая выводимая в исчислении предикатов формула является общезначимой.

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

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

Лемма 1. Пусть и — термы, а — переменная. Тогда

для произвольной оценки .

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

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

Аналогичное утверждение для формул таково:

Лемма 2. Пусть — формула, — терм, а — переменная, причем подстановка вместо в формулу корректна. Тогда

для произвольной оценки .

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

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

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

(отсюда следует, что не совпадает с ). По определению корректной подстановки, в этом случае переменная не входит в терм и подстановка корректна. Тогда

Мы воспользовались определением подстановки, определением истинности ( означает конъюнкцию по всем элементам из носителя интерпретации) и предположением индукции для формулы . Теперь надо заметить, что переменная не входит в по предположению корректности, и потому значение терма не изменится, если заменить на . Далее, и

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

что и требовалось. Случай формулы вида

разбирается аналогично, надо только заменить на . Лемма 2 доказана.

Теперь уже ясно, почему формула

будет истинна на любой оценке (если подстановка корректна). В самом деле, если левая часть импликации истинна на , то будет истинна на любой оценке , которая отличается от лишь значением переменной . В частности, будет истинна и на оценке , что по только что доказанной лемме 2 означает, что правая часть импликации истинна на .

Общезначимость формулы

доказывается аналогично.

Нам осталось проверить, что правила вывода сохраняют общезначимость. Для правила MP это очевидно (как и в случае исчисления высказываний). Проверим это для правил Бернайса. Это совсем несложно, так как здесь нет речи ни о каких корректных подстановках.

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

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

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

истинно. Но переменная не является параметром формулы , так что . Следовательно, формула

истинна на оценке , что и требовалось доказать.

Общезначимые формулы

Исчисление высказываний (лекция 3) позволяло выводить все тавтологии из некоторого набора базисных тавтологий (названных аксиомами) с помощью некоторых правил вывода (на самом деле единственного правила modus ponens). Сейчас мы хотим решить аналогичную задачу для формул первого порядка. Соответствующее исчисление называется исчислением предикатов.

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

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

Конечно, бывают и другие общезначимые формулы, не являющиеся частным случаями пропозициональных тавтологий. Например, формула

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

87. Будет ли общезначима формула (а); (б) ?

Многие вопросы можно сформулировать как вопросы об общезначимости некоторых формул. Например, можно записать свойства рефлексивности, транзитивности и антисимметричности в виде формул , и сигнатуры и затем написать формулу

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

88. Напишите формулы и проверьте, что приведенная нами формула не общезначима, хотя истинна во всех конечных интерпретациях.

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

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

Общезначимость любой формулы очевидно равносильна общезначимости ее замыкания — формулы, которая получится, если слева к приписать кванторы всеобщности по всем параметрам.

Двойственное к общезначимости понятие — выполнимость. Формула называется выполнимой, если она истинна в некоторой интерпретации на некоторой оценке. Очевидно, формула

общезначима тогда и только тогда, когда формула

не является выполнимой.

90. Закончите утверждение: выполнимость формулы с параметрами равносильна выполнимости замкнутой формулы, которая получится, если\,

Чтобы проверить, является ли формула тавтологией, достаточно подставить в нее все возможные наборы значений переменных. Хотя этот процесс может быть на практике невыполним (наборов слишком много), теоретически мы имеем простой алгоритм проверки, является ли формула тавтологией. Для общезначимых формул в общем случае такого алгоритма не существует (теорема Черча; ее доказательство можно прочесть в [5]); он есть только для очень ограниченных классов формул. Например, если сигнатура содержит только нульместные предикатные символы, то задача по существу сводится к проверке тавтологичности (в этом случае кванторы фиктивны). Чуть более сложен случай с одноместными предикатами.

91. Пусть сигнатура содержит только одноместные предикаты. Докажите, что всякая выполнимая формула этой сигнатуры, содержащая различных предикатов, выполнима в некоторой конечной интерпретации, содержащей не более элементов. Как использовать этот факт для алгоритмической проверки выполнимости формул такой сигнатуры?

Переименование переменных

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

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

(легко понять, что эти формулы не эквивалентны). Но даже если подстановка корректна, формулы могут не быть эквивалентными, как в случае формул

Как же сформулировать утверждение правильно?

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

Рис. 10.1. 

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

Теорема 52. (переименование связанных переменных)

Подобные формулы доказуемо эквивалентны.

Докажем две простые леммы.

Лемма 1. Если формула не содержит переменной (ни связанно, ни свободно), то формулы

доказуемо эквивалентны.

Доказательство. В самом деле, подстановка корректна, так как в

нет кванторов по . Поэтому выводима формула

Левая часть ее не содержит переменной , поэтому по правилу Бернайса можно вывести

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

или, что то же самое,

является аксиомой. Осталось применить правило Бернайса, заметив, что в левую часть переменная свободно не входит (все свободные вхождения были заменены на ). Лемма 1 доказана.

Аналогичное утверждение для квантора существования доказывается точно так же.

Лемма 2. Замена подформулы на доказуемо эквивалентную дает доказуемо эквивалентную формулу.

Доказательство. Как мы видели, доказуемая эквивалентность сохраняется после навешивания квантора: если , то и (символ здесь обозначает доказуемую эквивалентность). Кроме того, из и

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

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

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

(Использование третьей формулы существенно: мы не можем преобразовать первую формулу сразу во вторую, так как при замене переменных в рамках может не выполняться условие леммы 1.)

Аккуратное обращение со связанными и свободными переменными — традиционная головная боль авторов учебников по логике. Наиболее радикальный подход — вообще изгнать связанные переменные, заменив их квадратиками со связями между ними. Тогда при подстановке можно ни о чем не заботиться. Зато формулы перестают быть последовательностями символов, а становятся объектами со сложной структурой. (Этот подход использован в книге Бурбаки Теория множеств [3].)

Менее радикальный вариант состоит в том, чтобы разделить переменные на два типа — свободные и связанные. Так делается, например, в классической книге Гильберта и Бернайса Основания математики [8]. Тогда можно смело подставлять терм вместо свободной переменной, зато при навешивании квантора надо заменять свободную переменную на связанную.

Еще один вариант — договориться, что при подстановке терма вместо свободной переменных автоматически происходит переименование связанных переменных, создающих коллизии.

Все это, конечно, мелочи — но досадные, особенно если стремиться к краткости, ясности и наглядности. Следы мучительных раздумий на подобные темы видны в примечании книги Клини Математическая логика [16]: " Гильберт и Бернайс и другие авторы используют для обозначения свободных и связанных переменных разные буквы Мы следовали этому правилу в течение десятилетия Сейчас же мы твердо убеждены, что использование единого списка переменных для свободных и замкнутых вхождений дает небольшое, но чувствительное преимущество".

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

Переменные и константы

Отметим еще несколько простых свойств выводимости, которые нам потребуются:

Лемма о свежих константах.

Пусть выводима формула , где — произвольная формула, — переменная, — константа, не входящая в формулу . Тогда выводима и формула .

Интуитивный смысл леммы: если мы доказали что-то про "свежую" константу (не запятнавшую себя участием в формуле ), то фактически мы доказали формулу

для произвольных значений переменной.

Доказательство леммы. По условию существует вывод формулы . Возьмем "свежую" переменную , не встречающуюся в этом выводе, и всюду заменим в нем константу

на эту переменную. При этом вывод останется выводом, так как правила обращения с переменными и константами ничем не отличаются (кванторов по новой переменной в нем нет, так что корректные подстановки останутся корректными и применения правил Бернайса останутся допустимыми). Таким образом, выводима формула .

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

97. Сформулируйте и докажите аналогичную лемму для нескольких констант.

Аналогичное рассуждение позволяет доказать и другое утверждение, которое нам потребуется:

Лемма о добавлении констант.

Пусть формула некоторой сигнатуры выводима в исчислении предикатов расширенной сигнатуры , полученной из

добавлением новых констант. Тогда выводима и в исчислении предикатов сигнатуры .

Доказательство. Пусть формула , не содержащая новых констант, имеет вывод, в котором новые константы встречаются. Как их оттуда удалить? Легко понять, что их можно заменить на свежие переменные, не входящие в вывод, и он останется выводом, но уже без новых констант. Лемма доказана.

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

98. Проведите это рассуждение подробно.

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

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

Полнота исчисления предикатов

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

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

99. Докажите, что теория противоречива тогда и только тогда, когда в ней выводится формула (здесь — произвольная формула сигнатуры).

Непосредственно из определения следует, что всякое подмножество непротиворечивого множества непротиворечиво. Кроме того, если бесконечное множество противоречиво, то некоторое его конечное подмножество тоже противоречиво (поскольку в выводе участвует лишь конечное число формул).

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

Теорема 45 (о корректности; переформулировка).

Любое совместное множество замкнутых формул непротиворечиво.

Пусть все формулы из истинны в некоторой интерпретации . Может ли оказаться, что и для некоторой замкнутой формулы ? Легко понять, что нет. В самом деле, в этом случае теорема 44 показывает, что формулы и должны быть одновременно истинны в , что, очевидно, невозможно.

Для доказательства обратного утверждения (о совместности непротиворечивой теории) нам понадобится понятие полной теории.

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

выводятся из .

Другими словами, теория полна, если из любых двух формул и (соответствующей сигнатуры) ровно одна является теоремой этой теории.

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

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

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

Теперь мы готовы к доказательству основного результата этого раздела.

Теорема 46 (полнота исчисления предикатов, сильная форма).

Любая непротиворечивая теория совместна.

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

Лемма 1. Для всякого непротиворечивого множества замкнутых формул сигнатуры

существует полное непротиворечивое множество замкнутых формул той же сигнатуры, содержащее .

Доказательство повторяет рассуждение раздела "Второе доказательство теоремы о полноте": рассматривая по очереди замкнутые формулы, мы добавляем либо их, либо их отрицания в множество .



Это можно сделать без труда для конечной или счетной сигнатуры (тогда множество всех замкнутых формул этой сигнатуры счетно); для общего случая надо воспользоваться трансфинитной индукцией или леммой Цорна, как объяснялось в разделе "Второе доказательство теоремы о полноте". Лемма 1 доказана.

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

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

выводима из .

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

истинна в построенной интерпретации, а если , то формула ложна.

Однако без дополнительных предположений о множестве

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



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

Если множество полно и экзистенциально полно, то описанная выше конструкция с замкнутыми термами дает его модель. Прежде чем проверять это, покажем, как расширить до полного и экзистенциально полного множества. Ключевую роль здесь играет такая лемма:

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

(Замечание. Здесь и далее, говоря о непротиворечивости и выводимости, мы не уточняем, в какой сигнатуре строятся выводы: все наши сигнатуры будут отличаться лишь набором констант, и лемма о добавлении констант.)

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

100. Докажите такое усиление леммы 2: при добавлении в

формулы (в предположениях леммы) множество выводимых из формул исходной сигнатуры (без константы ) не меняется.

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

Доказательство. Пусть сигнатура конечна или счетна. Тогда замкнутых формул вида , выводимых из , не более чем счетное число. К каждой из них по очереди будем применять лемму 2, вводя новую константу.


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

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

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

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

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

Лемма 3 доказана.

Последним шагом в доказательстве теоремы о полноте (всякое непротиворечивое множество замкнутых формул совместно) является такая лемма:

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



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

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

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

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

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

Пусть теперь формула имеет вид , где — формула с единственным параметром

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



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

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

Если формула не выводима из , то из выводится ее отрицание. Оно, как мы видели, доказуемо эквивалентно формуле . Поэтому в силу экзистенциальной полноты выводима формула для некоторой константы . Эта формула истинна, поэтому ложна при некотором значении переменной , так что формула ложна в .

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

Анализ доказательства позволяет сделать такое наблюдение:

Теорема 47. Непротиворечивое множество замкнутых формул конечной или счетной сигнатуры имеет счетную модель.

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

Аналогичное рассуждение с использованием свойств операций с мощностями (о которых можно прочесть в [6]) устанавливает такой факт:

Теорема 48. Всякое непротиворечивое множество формул сигнатуры

имеет модель мощности (где

обозначает счетную мощность, а — мощность сигнатуры).

Кстати, при доказательстве теорем 47 и 48 можно было бы сослаться на теорему Левенгейма-Сколема об элементарной подмодели (построить модель произвольной мощности, а потом уменьшить, если надо).



Возвратимся теперь к исходной формулировке теоремы о полноте.

Теорема 49 (полнота исчисления предикатов, слабая форма)

Всякая общезначимая формула выводима в исчислении предикатов.

Пусть формула замкнута. Если она невыводима, то множество непротиворечиво и потому совместно. В его модели формула будет ложной, что противоречит предположению.

Что касается незамкнутых формул, то их общезначимость и выводимость равносильна общезначимости и выводимости их замыкания.

Как и в разделе "Второе доказательство теоремы о полноте", из теоремы о полноте можно вывести такое следствие:

Теорема 50. (компактность для исчисления предикатов).

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

В самом деле, по теореме о полноте (и корректности, если быть точным) наличие модели (совместность) равносильно непротиворечивости. А по определению противоречивость затрагивает лишь конечное число формул из .

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

Прямое доказательство теоремы компактности (без использования понятия выводимости) мы дадим в следующей лекции.

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

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

Теорема 51.


Если , то .

Напротив, пусть не выводима из . Тогда теория непротиворечива и (в силу теоремы о полноте) имеет модель. Значит

не следует из .

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

Примеры выводимых формул

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

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

является частным случаем пропозициональной тавтологии (а на самом деле и аксиомой) и дважды применяем правило MP.Другой пример такого же рода: если формула

выводима, то выводима и формула , поскольку импликация

является частным случаем пропозициональной тавтологии.Еще один пример: если выводимы формулы и , то выводима и формула , поскольку формула

является частным случаем пропозициональной тавтологии.Для произвольной формулы выведем формулу

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

Формулы и являются аксиомами. С их помощью выводим формулу . Теперь заметим, что левая часть импликации не имеет параметра , а правая часть не имеет параметра , так что можно применить два правила Бернайса (в любом порядке) и добавить справа квантор , а слева — квантор .Предположим, что формула выводима, а — произвольная переменная. Покажем, что в этом случае выводима формула . В самом деле, формула является аксиомой. Далее выводим (с помощью пропозициональных тавтологий и правила MP) формулу ; остается воспользоваться правилом Бернайса (левая часть не имеет параметра ).Аналогичным образом из выводимости формулы

следует выводимость формулы , только надо начать с аксиомы , затем получить , а потом применить правило Бернайса.

Таким образом, если формулы и доказуемо эквивалентны (это значит, что импликации и выводимы), то формулы

и также доказуемо эквивалентны. (Аналогичное утверждение верно и для формул и .)

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

Выведем третью формулу: . По правилу Бернайса достаточно вывести , что после контрапозиции превращается в аксиому .
Четвертая формула получится, если заменить в третьей
на и применить контрапозицию.

Выводимость из посылок

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

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

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

выводима из , если ее можно вывести, используя наравне с аксиомами формулы из . Как и для исчисления высказываний, мы пишем . Выводимые из формулы называют также теоремами теории .

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

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

до вывода из . Отличие от пропозиционального случая в том, что в выводе могут встречаться правила Бернайса. Например, от выводимости формулы

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

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

формула

и остается вернуть из конъюнкции в посылку.

Сходным образом рассматривается и второе правило Бернайса. Если выводима формула

то в силу пропозициональных тавтологий выводима формула

к которой можно применить правило Бернайса и получить

после чего вернуть назад с помощью пропозициональной тавтологии.
Лемма о дедукции доказана.
Отметим теперь несколько полезных свойств выводимости из посылок.
Если и , то . (Очевидно следует из определения.)Если , то существует конечное множество , для которого . (Вывод конечен и потому может использовать лишь конечное число формул.)
Если конечно и равно , то
равносильно выводимости (без посылок) формулы
В самом деле, если , то многократное применение леммы о дедукции дает и остается воспользоваться надлежащей пропозиональной тавтологией. (В обратную сторону рассуждение также проходит без труда.)
Комбинируя три предыдущих замечания, приходим к такому эквивалентному определению выводимости из посылок: , если найдутся формулы , для которых
Это определение имеет смысл и для формул с параметрами, так что если уж определять выводимость из посылок с параметрами (чего обычно избегают), то именно так.
Понятие выводимости из посылок позволяет переформулировать теорему о корректности исчисления предикатов.
Говорят, что интерпретация сигнатуры
является моделью теории , если все формулы из истинны в .
Теорема 44 (о корректности; переформулировка).
Все теоремы теории истинны в любой модели
теории .
Если формула является теоремой теории (т. е. ), найдутся формулы , для которых По теореме о корректности (в уже известной нам форме) эта формула будет истинна во всех интерпретациях, в частности в . Поскольку истинны в , то и формула истинна в (на любой оценке).
В следующих задачах — и только в них — знак понимается в описанном выше смысле (в посылках допускаются параметры).
95. Пусть — множество произвольных (не обязательно замкнутых) формул. (а) Пусть существует "вывод" некоторой формулы , в котором наравне с аксиомами используются формулы из , при этом все применения правил Бернайса предшествуют появлению формул из . Покажите, что . Покажите, что верно и обратное утверждение. (б) Покажите, если в "выводе" формулы наравне с аксиомами используются формулы из , но правила Бернайса не применяются по переменным, свободным в , то .
96. Покажите, что правила Бернайса можно переписать так: где переменная не является параметром формулы , а также параметром формул из . (В первом правиле мы для симметрии выделили формулу , хотя она ничем не отличается от формул из .)

Предваренная нормальная форма

Говорят, что формула находится в предваренной нормальной форме, если все кванторы в ней вынесены налево, то есть если она имеет вид

где — кванторы всеобщности или существования, — переменные, а — бескванторная формула. Эта формула может иметь параметры (если формула имеет параметры, отличные от ).

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

Говорят, что предваренная формула является - формулой, если ее кванторная приставка содержит групп кванторов, причем первыми стоят кванторы существования. Если первыми стоят кванторы всеобщности, говорят о классе . (Аналогичные обозначения используются в теории алгоритмов для классификации арифметических множеств, см. [5]).

Пример: формула принадлежит классу , формула принадлежит классу , а формула вообще не находится в предваренной нормальной форме.

103. Указать формулу в предваренной нормальной форме, доказуемо эквивалентную последней из перечисленных формул.

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

Всякая формула из класса или доказуемо эквивалентна формуле из класса , а также формуле из класса . В самом деле, если формула

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

Покажем, что конъюнкция двух формул из доказуемо эквивалентна некоторой формуле из . Например, конъюнкция

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

104. Покажите, что можно сэкономить один квантор и использовать формулу .

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

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

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

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

Отметим кстати, что в них уже нельзя сэкономить квантор; например, формула не равносильна формуле . (В одном из выступлений времен начала перестройки М.С.Горбачев сказал, что нужны "преданные делу социализма, но квалифицированные специалисты" — впрочем, в газетной публикации "но" было заменено на нейтральное "и". Так вот, их существование не вытекает из отдельного существования тех и других.)

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





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

а затем формуле




105. Как сэкономить один квантор в этом преобразовании?

Теперь все готово для доказательства упомянутого в начале раздела результата.

Теорема 53 (о предваренной нормальной форме).

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

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

Отметим, что ни формулировка, ни доказательство этой теоремы не предполагают замкнутости формулы.

106. Привести к предваренной нормальной форме формулу .

107. Формулы и принадлежат классу . Найдем формулу в предваренной нормальной форме, выводимо эквивалентную формуле . В каком классе она окажется? (Указание: возможны разные варианты.)

108. Применим описанный метод к общезначимой формуле . Какая предваренная формула получится? (Естественно, она будет общезначимой.)

Сколемовские функции

В этом разделе мы в разных формах используем ровно одну идею: утверждение

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

поскольку в нашем языке нет квантора по функциям и мы писать не имеем права. (Языки, содержащие кванторы по множествам и функциям, называются языками второго порядка и мы их не рассматриваем.)

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

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

Аналогичное преобразование выполнимо и для произвольных предваренных формул. Например, формула

выполнима тогда и только тогда, когда выполнима формула

(здесь — формула, не имеющая параметров, кроме , запись

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

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

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

109. Казалось бы, выбор в приведенном выше примере зависит от , так что следовало бы написать — но мы так не делаем. Почему это допустимо?

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

Теорема 56. Для всякой замкнутой формулы сигнатуры

можно указать формулу класса

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

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

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

общезначима одновременно с формулой . Внося отрицание внутрь и заменяя

на , получаем такое утверждение: формулы

одновременно общезначимы. (Это утверждение чуть менее наглядно, чем двойственное ему утверждение о выполнимости.) В общем виде двойственное к теореме 56 утверждение выглядит так:

Теорема 57. Для всякой замкнутой формулы сигнатуры

можно указать формулу класса

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

Заметим, что к формуле можно применить теорему Эрбрана: она общезначима тогда и только тогда, когда дизъюнкция нескольких подстановок является тавтологией.

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

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

Идея использования функций вместо групп кванторов восходит к Эрбрану и Сколему. Такие функции иногда называют "эрбрановскими" или "сколемовскими", а их добавление — "сколемизацией". Есть также термин "сколемовская нормальная форма", но здесь добавляются не функциональные символы, а предикатные, и получается формула не класса , как в теореме 57, а класса .

Теорема 57 (о сколемовской нормальной форме).

Для всякой замкнутой формулы сигнатуры

можно указать формулу класса

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

Как и раньше, нам будет удобнее говорить о выполнимости и доказывать, что для всякой формулы найдется одновременно с ней выполнимая формула из класса . Построение такой формулы мы объясним на примере. Пусть исходная формула имеет вид

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

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

Такая конструкция применима к любой предваренной форме и дает конъюнкцию -формул (последняя из которых будет даже и -формулой). А мы знаем, что такая конъюнкция эквивалентна -формуле.

110. Дайте синтаксическое доказательство теоремы о сколемовской нормальной форме (показав, что из выводимости формулы следует выводимость ее сколемовской нормальной формы и наоборот). (Указание: это проще, чем для формул с функциональными символами, и не требуется использовать генценовское исчисление.)

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

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

Теорема Эрбрана

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

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

Теорема 54 (выводимость бескванторных формул).

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

Если прототип формулы является тавтологией, то формула является частным случаем пропозициональной тавтологии и потому выводима и общезначима.

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

Что можно сказать про общезначимость формул классов

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

по существу ничем не отличаются от бескванторных.

Вопрос для класса решается следующей теоремой:

Теорема 55 (Эрбрана). Формула (где формула — бескванторная) общезначима тогда и только тогда, когда найдется конечный список подстановок
( вместо переменных подставляются термы нашей сигнатуры), дизъюнкция которых общезначима.

Заметим, что дизъюнкция, о которой идет речь в теореме, является бескванторной формулой. По теореме 54 она общезначима тогда и только тогда, когда является частным случае пропозициональной тавтологии.

Прежде чем доказывать эту теорему, приведем пример. Рассмотрим формулу (в которой и — константы). Она общезначима; соответствующий набор состоит из подстановок и . В самом деле, формула

истинна как при истинном , так и при ложном. Заметим, что в этом примере нам понадобились две подстановки.

Доказательство теоремы Эрбрана. В одну сторону утверждение очевидно: если общезначима дизъюнкция подстановок, то общезначима формула с квантором. (Мы уже использовали это при элиминации кванторов в разделе "Элиминация кванторов" при доказательстве теоремы 28.)

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

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

Заметим, что теорему Эрбрана можно сформулировать чисто синтаксически: если выводима -формула , то можно найти конечное число подстановок, дизъюнкция которых выводима. Можно предложить и доказательство, не использующее понятия общезначимости. Такое доказательство приведено, например, в книге Клини [16] (для генценовского варианта исчисления предикатов) и в книге Шенфилда [31] (для гильбертовского варианта).Синтаксическое доказательство (в отличие от нашего) конструктивно: по выводу -формулы можно алгоритмически указать соответствующие термы.

Если сигнатура не содержит функциональных символов, то теорема Эрбрана позволяет алгоритмически проверить выводимость формул класса , поскольку число возможных подстановок конечно. Это же можно сказать и про формулы класса , так как внешние кванторы всеобщности можно отбросить, не меняя выводимости.

Естественный вопрос: можно ли построить аналогичные алгоритмы для следующих классов? Отрицательный ответ дается в следующем разделе.

Аксиомы равенства

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

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

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

(называемые аксиомами рефлексивности, симметричности и транзитивности). Это еще не все. Для каждого функционального символа мы формулируем аксиому равенства, которая говорит, что его значение не меняется, если аргументы заменить на равные. Например, для двуместного функционального символа

соответствующая аксиома выглядит так:

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

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

Теорема 59 (полноты для нормальных моделей).

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

Прежде всего заметим, что теоремы о корректности и полноте (раздел "Полнота исчисления предикатов") позволяют говорить о совместности вместо непротиворечивости.

В нормальной модели теории аксиомы равенства истинны, так что в одну сторону утверждение теоремы очевидно. Нам осталось показать, что если теория совместна с аксиомами равенства, то она имеет нормальную модель.

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

(его можно назвать фактор-множеством по данному отношению эквивалентности). Класс элемента будем обозначать .

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

и внутри класса. Аналогичным образом аксиомы для предикатных символов позволяют корректно определить предикаты на классах.

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

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

111. Покажите, что из аксиом равенства для сигнатуры

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

112. Покажите, что если теория (не обязательно с равенством) имеет модель мощности , то она имеет и модель любой большей мощности. (Указание: элементы модели можно "клонировать" в произвольном количестве.)

Из теоремы о полноте для нормальных моделей легко следует аналог теоремы о компактности (теорема 50) для нормальных моделей.



Теорема 60 (компактности для нормальных моделей).

Если всякое конечное подмножество теории в сигнатуре с равенством имеет нормальную модель, то и теория

имеет нормальную модель.

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

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

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

115. Пусть — множество замкнутых формул в сигнатуре с равенством. Покажите, что замкнутая формула этой сигнатуры истинна во всех нормальных моделях тогда и только тогда, когда она выводима из и аксиом равенства.

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

Теорема 34 устанавливает возможность элиминации

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

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

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

137. Покажите, что теория алгебраически замкнутых полей данной характеристики полна.

138. Покажите, что если некоторая формула в сигнатуре

истинна в алгебраически замкнутых полях характеристики , то она истинна и во всех алгебраически замкнуты

Арифметика Пресбургера

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

Проанализировав это рассуждение, можно извлечь из него явную аксиоматизацию для теории

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

Можно проверить, что все шаги элиминации кванторов сохраняют равносильность в такой ситуации. Проверим, например, что сравнения можно умножать на целое положительное число. Почему, скажем, равносильно ? По определению первое означает, что для некоторого , а второе — что для некоторого , и достаточно сослаться на то, что в упорядоченной группе из следует

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

133. Покажите, что теория разрешима.

134. Покажите, что эта теория не категорична в счетной мощности и опишите все ее счетные модели. (Указание: они имеют вид , где — делимая упорядоченная группа.)

135. Покажите, что эта теория не конечно аксиоматизируема. (Указание: рассмотрите интерпретацию , когда в возможно деление на простые числа, меньшие некоторого , но не на .)

Плотные линейно упорядоченные множества

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

аксиомы равенства (в том числе сохранение порядка при замене элементов на равные); (рефлексивность порядка); (транзитивность порядка);

(антисимметричность порядка);

(линейность порядка); (нет максимального элемента; можно считать сокращением для

или для — при наличии остальных аксиом это одно и то же);аналогичная аксиома про отсутствие минимального элемента;

(плотность).

Рациональные числа образуют счетную модель этой теории, а действительные — несчетную. Как мы уже упоминали, эта теория категорична в счетной мощности, все ее счетные нормальные модели изоморфны. Отсюда по теореме 65 получаем, что она полна. Следовательно, в ней выводятся все истинные в (или в любой другой модели, в частности, в ) формулы ее сигнатуры (в самом деле, из формул и ровно одна истинна и ровно одна выводима, и выводимая формула должна быть истинной). Наконец, по теореме 67 эта теория разрешима.

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

Сказанное можно интерпретировать и так: мы доказали конечную аксиоматизируемость теории , предъявив список аксиом.

119. Покажите, что эта теория не является категоричной в мощности континуум.

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

120. Не используя теоремы Морли, укажите примеры неизоморфных плотных линейно упорядоченных множеств заданной несчетной мощности.

121. Покажите, что элементарные теории и конечно аксиоматизируемы, полны и разрешимы. Будут ли они категоричными в мощности континуум?

122. Рассмотрим теорию плотных линейно упорядоченных множеств (не добавляя аксиом про наименьший и наибольший элемент). Будет ли она категорична в какой-либо мощности? полна? разрешима?

Полные теории

В этом разделе мы попытаемся систематизировать уже известные нам понятия и факты.

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

Говорят, что замкнутая формула выводима в теории (является теоремой теории ), если формула получается из аксиом исчисления предикатов и формул теории по правилам вывода. (Обозначение: .)

Формула выводима в теории тогда и только тогда, когда в исчислении предикатов выводится некоторая формула вида , где — конъюнкция конечного числа формул из .

Формула семантически следует из , если она истинна в любой модели теории (обозначение: ). Семантическое следование равносильно выводимости (теорема 51). Взяв в качестве

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

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

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

117. Покажите, что добавление к теории любой ее теоремы не меняет множества теорем.

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

Теорема 65 (критерий Лося-Воота). Непротиворечивая теория с равенством в конечной или счетной сигнатуре, не имеющая конечных моделей и категоричная в счетной мощности, полна.

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

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

Теорема 66. Непротиворечивая теория с равенством в конечной или счетной сигнатуре, не имеющая конечных моделей и категоричная в данной несчетной мощности , полна.

Пусть теория не полна и к ней можно присоединить без противоречия любую из формул и . Рассмотрим счетные нормальные модели теорий и . По теореме 62 увеличим их мощности до и получим противоречие.



118. Условие конечности или счетности сигнатуры в этой теореме можно ослабить. Как это сделать?

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

Заметим, что это наблюдение согласовано со знаменитой (и трудной!) теоремой Морли; эта теорема утверждает, что теория с равенством, категоричная в одной несчетной мощности, категорична и во всех несчетных мощностях. (Подробно о теореме Морли можно прочесть, например, в учебнике Кейслера и Чэна [13])

Теорема 67. Конечно аксиоматизируемая полная теория в конечной сигнатуре разрешима.

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

из конъюнкции некоторых аксиом теории . Рано или поздно одна из них окажется выводимой (поскольку теория полна), и тем самым мы узнаем, какая из формул выводима в теории.

Это доказательство неконструктивно в том смысле, что не дает никакой оценки на время работы алгоритма. Отметим также, что не обязательно требовать конечной аксиоматизируемости теории; достаточно, чтобы она имела разрешимое или перечислимое множество аксиом (см. [5]).

Проиллюстрируем все эти понятия на нескольких (в основном уже обсуждавшихся нами) примерах.

Повышение мощности

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

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

Теорема 61 (Левенгейма-Сколема о повышении мощности).

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

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

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

Рассмотрим теорию , состоящую из формул сигнатуры , истинных в при указанной интерпретации. Всякое элементарное расширение

интерпретации будет моделью теории . В самом деле, замкнутая формула

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

Верно и обратное: любая нормальная модель теории естественно определяет элементарное расширение интерпретации . В самом деле, пусть дана нормальная модель этой теории с носителем . Тогда каждый элемент множества (точнее, соответствующая этому элементу константа) интерпретируется некоторым элементом множества . Разным элементам множества соответствуют разные элементы в , так как формула , истинная в , должна быть истинной и в . Таким образом, вкладывается в и можно отождествить его с некоторым подмножеством множества . Это отождествление корректно в том смысле, что предикаты и функциональные символы интерпретируются согласованным образом. В самом деле, атомарные формулы вида , а также формулы и , истинные в , истинны и в . Истинные в формулы вида принадлежат и потому истинны и в ; ложные в формулы имеют отрицания в и потому ложны в .

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

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

Этот же прием будет использован нами при построении нестандартной модели арифметики

Приведенное рассуждение дает оценку мощности снизу. Можно получить и в точности нужную мощность:

Теорема 62. Пусть — бесконечная нормальная интерпретация сигнатуры (с равенством) и пусть — мощность, не меньшая мощностей сигнатуры и интерпретации .


Тогда существует нормальное элементарное расширение мощности .

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

Аналогичный прием (добавление констант) позволяет легко доказать такое утверждение:

Теорема 63. Если теория (в произвольной сигнатуре с равенством) имеет сколь угодно большие конечные нормальные модели, то она имеет и бесконечную нормальную модель.

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

Вообще можно задать себе такой естественный вопрос. Пусть есть некоторая теория (или даже просто одна формула). Каковы могут быть мощности ее нормальных моделей? Как мы видели, для теорий с конечной сигнатурой верно одно из двух: либо бесконечных моделей вовсе нет, либо есть бесконечные модели всех мощностей. Это гарантируют теоремы Левенгейма-Сколема об элементарной подмодели (теорема 42) и о повышении мощности (теорема 61).

Что можно сказать про мощности конечных моделей? Для каждой формулы рассмотрим множество всех возможных мощностей ее конечных моделей. Его иногда называют спектром формулы. Это множество может быть устроено довольно сложным образом: например, для формулы, выражающей аксиомы поля, спектр состоит из всех степеней простых чисел.

116. (а) Укажите формулу, спектр которой состоит из всех четных положительных чисел. (б) Укажите формулу, спектр которой состоит из всех нечетных чисел. (в) Укажите формулу, спектр которой состоит из всех составных чисел.

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



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

Другое любопытное применение теоремы о повышении мощности таково. Назовем линейно упорядоченное множество

однородным, если для любых двух возрастающих последовательностей и найдется автоморфизм множества , переводящий в (при всех ).

Теорема 64. Для всякой бесконечной мощности найдется однородное линейно упорядоченное множество такой мощности.

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

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

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

Теория Th(Q,=,<,+,0,1)

В этом примере мы действуем в обратном порядке, начав с конкретной интерпретации (целые числа с равенством, функцией прибавления единицы и константой ) и построив явную систему аксиом. Для этого вспомним процедуру элиминации кванторов из раздела "Элиминация кванторов" (теорема 28). Какими свойствами должна обладать нормальная интерпретация языка, чтобы преобразования, использованные при элиминации кванторов, были эквивалентными? Помимо аксиом равенства, нам нужно, чтобы функция была биекцией и чтобы для любого все элементы

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

аксиомы равенства;;;;; и т. д.

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

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

123. Опишите все модели этой теории.

124. Покажите, что эта теория категорична в любой несчетной мощности.

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

125. Докажите, что использованное нами рассуждение носит общий характер: если теория бесконечна, но конечно аксиоматизируема, то некоторая ее конечная часть равносильна всей теории (имеет те же теоремы).

Эту теорию мы рассматривали в разделе "Элиминация кванторов". Мы ограничимся двумя константами и , поскольку любую атомарную формулу можно привести к общему знаменателю и получить целые константы, которые можно выразить через и .

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

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

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

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

130. Покажите, что эта теория разрешима.

131. Покажите, что эта теория не является категоричной.

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

Теория Th(Z,=,<,S,0)

Что изменится, если мы добавим к сигнатуре, помимо прибавления единицы, еще и отношение порядка? Как мы видели (см. доказательство теоремы 29 и задачу после него), элиминация кванторов по-прежнему возможна. Для придания законности нам нужны такие свойства интерпретации (которую мы предполагаем нормальной): она представляет собой линейно упорядоченное множество, в котором каждый элемент имеет непосредственно следующий (совпадающий с значением функции ) и непосредственно предшествующий. В отличие от предыдущего примера, нам достаточно конечного набора аксиом. Таким образом, теория конечно аксиоматизируема, а также (как и в предыдущем примере) полна, разрешима, но не категорична в счетной мощности.

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

Теперь с помощью игры Эренфойхта (см. раздел "Элементарная эквивалентность", теорема 37) мы показываем, что все нормальные модели этой теории элементарно эквивалентны. Отсюда заключаем, что теория полна (как в доказательстве теоремы 65, где мы по существу использовали элементарную эквивалентность моделей, а не их изоморфизм).

126. Покажите, что теория не категорична ни в какой несчетной мощности.

127. Будет ли теория конечно аксиоматизируемой? разрешимой? категоричной?

128. Будет ли теория конечно аксиоматизируемой? разрешимой? категоричной?

Вещественно замкнутые поля

Более сложно сформулировать, какие свойства вещественных чисел реально используются при доказательстве теоремы Тарского-Зайденберга (раздел "Теоремы Тарского-Зайденберга"). Дело в том, что мы ссылались на разные факты из анализа (понятие производной, теорема Ролля, асимптотика многочленов). Однако на самом деле достаточно некоторых алгебраических свойств поля — как говорят, поле должно быть "вещественно замкнутым".

Поле называется упорядоченным, если на нем задан линейный порядок, причем он согласован со сложением ( влечет ) и умножением ( влечет ).

139. Покажите, что любое упорядоченное поле имеет характеристику

и что в любом упорядоченном поле сумма квадратов не может равняться .

Упорядоченное поле называется вещественно замкнутым, если любой многочлен, имеющий на концах отрезка разные знаки, имеет корень на этом отрезке. (Отметим в скобках, что существует несколько эквивалентных определений вещественно замкнутого поля, см. учебник ван дер Вардена [4]

мы выбрали наиболее удобное для наших целей.)

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

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

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

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

Справедливо и свойство сохранения знака: если в какой-то точке многочлен положителен, то и в достаточно близких точках он положителен. Слова "достаточно близких" понимаются в обычном смысле (), только теперь — не действительное число, а элемент поля.

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

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

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

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

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

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

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

Диаграммы и расширения

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

Пусть дана нормальная интерпретация

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

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

является бескванторной.)

Теперь мы готовы дать ответ на такой вопрос. Пусть есть нормальная интерпретация сигнатуры и некоторая теория (с равенством) этой сигнатуры. В каком случае существует расширение интерпретации , являющееся нормальной моделью теории ?

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

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

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

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

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

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

Вот еще один хорошо известный пример из алгебры. В каком случае коммутативное кольцо может быть вложено в поле? Теорема 70 требует, чтобы в выполнялись все -теоремы теории полей. Оказывается, что достаточно выполнения единственного -свойства: отсутствия делителей нуля:

В этом случае кольцо может быть вложено в поле.

148. Докажите это утверждение. (Указание. Это поле называют полем частных; его элементами являются формальные дроби вида при естественных определениях равенства и операций.)

Не всегда, однако, можно указать простые критерии вложимости. Мы не зря требовали коммутативности: известный советский алгебраист и логик А.И.Мальцев доказал, что не всякое некоммутативное кольцо без делителей нуля вкладывается в тело и что никакое конечное число -формул не дают критерия вложимости полугруппы в группу (подробнее см. в книге Куроша [14],глава II, параграф 5).

Мы знаем теперь, когда данную интерпретацию можно расширить до модели данной теории. Это позволяет легко ответить и на такой вопрос: когда существует модель данной теории и ее расширение, являющееся моделью другой теории.

Теорема 71. Пусть даны две теории (с равенством) и

некоторой сигнатуры. Тогда следующие свойства равносильны:

(а) существует нормальная модель теории и ее расширение, являющееся нормальной моделью теории ;

(б) объединение со всеми -теоремами теории совместно;

(в) объединение со всеми -теоремами теории совместно.

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

Легко проверить, что симметричные условия (б) и (в) равносильны друг другу, а также такому свойству: не существует - теоремы

теории и отрицающей ее -теоремы теории . Пусть, например, теория несовместна с -следствиями теории . В этом противоречии участвует конечное число -формул, которые можно объединить в одну. Получится -формула, она будет выводима в теории , а ее отрицание — в .

Нам осталось доказать, что любое из свойств (б) и (в) влечет (а). Здесь нам придется нарушить симметрию и использовать именно (б). По условию есть интерпретация , в которой истинны все теоремы теории и все -теоремы теории . Согласно теореме 70 найдется ее расширение , являющееся моделью , что и требовалось доказать.

Можно было бы пытаться рассуждать симметричным образом, начав с модели теории , в которой истинны все -теоремы теории , и пытаться выделить в ней подструктуру, являющуюся моделью теории . Однако этот план не проходит, поскольку аналог теоремы 70 для подструктур неверен.

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

Вот еще одно следствие доказанных в этом разделе результатов. Теорию называют -аксиоматизируемой, если существует множество -формул, из которого выводятся все теоремы теории и только они.

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

Теорема 72 (Лося-Тарского). Теория -аксиоматизируема тогда и только тогда, когда она устойчива относительна перехода к подструктурам, то есть когда любая подструктура любой ее нормальной модели является ее моделью.

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

непротиворечива и по теореме 71 найдется (нормальная) модель теории и ее расширение, являющееся моделью теории , что противоречит предположению.

150. Докажите, что если формула устойчива относительно перехода к подструктурам, то она выводимо эквивалентна -формуле той же сигнатуры.

Симметричное рассуждение доказывает симметричное утверждение про -аксиоматизируемые теории.

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

151. Проведите подробно соответствующее рассуждение (дав необходимые определения).

152. Докажите, что если формула устойчива относительно перехода к расширениям, то она выводимо эквивалентна -формуле той же сигнатуры.

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

не имеет наибольшего элемента, то и объединение не имеет наибольшего элемента (проверьте). Именно это свойство, как мы вскоре увидим, характеризует -формулы.

Пусть дана последовательность

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

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

Поэтому и любая теория, имеющая -аксиоматизацию, устойчива относительно объединения. Обратное утверждение также верно:

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

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

153. Покажите, что если , то есть элементарное расширение .

Лемма Тарского. Объединение цепи элементарных расширений является элементарным расширением каждой из интерпретаций цепи.

Доказательство леммы. Пусть параметрам формулы приданы значения в каком-либо из . Нам надо доказать, что полученная формула одновременно истинна или ложна в и в объединении цепи, которое мы обозначим через . (Условие леммы гарантирует, что формула с указанными значениями параметров одновременно истинна или ложна во всех интерпретациях цепи, начиная с .)

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

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

элементарно эквивалентно .

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

Теперь докажем теорему Чэна-Лося-Сушко. Предположим, что теория устойчива относительно объединения цепей. Обозначим через множество всех -теорем . Нам надо доказать, что любая модель является моделью .

Для этого, начав с любой модели теории , мы построим цепь интерпретаций

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

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

Осталось построить требуемую цепь. Интерпретация уже есть. Будем строить цепь по шагам, продолжая ее на каждом шаге на два звена вперед. Возможность этого обеспечивает такая лемма:

Лемма о расширении.

Если все -следствия теории истинны в интерпретации , то можно построить ее расширения так, чтобы было моделью теории , а было элементарным расширением .

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

истинно в . Проверим его истинность в . Если оно ложно при , то ложно и в , и в (элементарность расширения) и потому не может быть истинным в (поскольку всякое из лежит и в ).

Доказательство леммы о расширении. Что требуется от данного расширения интерпретации , чтобы можно было построить с требуемыми свойствами? Свойства эти состоят в том, что должно быть моделью теории и расширением интерпретации . Как раз про это говорит теорема 70, надо лишь в качестве в этой теореме взять нашу сигнатуру с добавленными константами для (мы обозначали ее ), а в качестве теории из теоремы 70 взять , то есть множество всех истинных в формул с константами из .

Применяя указанный в теореме 70 критерий, можно сформулировать утверждение, которое нам осталось доказать, так: найдется модель теории , которая является расширением и в которой истинны все -формулы сигнатуры , выводимые из . Вспоминая метод диаграмм, можно сказать, что нас интересует совместность теории с и со всеми - следствиями теории в сигнатуре . В данном случае можно и не упоминать явно, так как оно содержится в .

Итак, осталось доказать, что теория совместна со всеми -формулами с константами из , истинными в . Если это не так, из выводится отрицание какой-то из этих формул, то есть некоторая -формула

ложная в . Константы не входят в теорию , поэтому из выводится и формула

которая будет выводимой из формулой класса , ложной в , а таких формул не бывает по условию.

Лемма о расширении (а с ней и теорема Чэна-Лося-Сушко) доказана.

154. Докажите, что если формула устойчива относительно объединения возрастающих цепей, то она выводимо эквивалентна некоторой -формуле той же сигнатуры.

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

Формальная арифметика

Рассмотрим множество натуральных чисел с операциями сложения и умножения и его элементарную теорию , то есть множество всех истинных (в натуральном ряду) формул со сложением и умножением. Это множество, очевидно, полно. Можно доказать ([5]), что оно неразрешимо (и, более того, неарифметично, как говорит теорема Тарского).

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

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

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

с таким свойством: истинна в

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

145. (Продолжение) Покажите, что верно и обратное: элементарная теория натуральных чисел сводится к элементарной теории целых чисел. (Указание. Если бы в целых числах был порядок, это было бы совсем просто. Чтобы его ввести, можно использовать теорему Лагранжа о том, что всякое натуральное число представимо в виде суммы четырех квадратов.)

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

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

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

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

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

Неполные и неразрешимые теории

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

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

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

Среди естественных неполных теорий бывают разрешимые и неразрешимые. Например, теория линейно упорядоченных множеств разрешима, теория абелевых групп разрешима, а теория групп неразрешима. Подробный рассказ об этом далеко выходит за рамки нашей книжки; написанный М.О.Рабином обзор соответствующих результатов можно найти в справочнике по математической логике (часть III, Теория рекурсии [26], глава 4).

Мы же ограничимся тремя примерами (теория равенства, теория полугрупп, формальная арифметика).

Теория полугрупп

Наш второй пример — теория полугрупп. Ее сигнатура состоит из равенства и единственного двуместного функционального символа, называемого умножением; результат умножения и мы будем обозначать .

Теория состоит из аксиом равенства (включая корректность умножения: ; мы опускаем внешние кванторы всеобщности) и аксиомы ассоциативности

Нормальные модели этой теории называются полугруппами.

Теорема 69. Множество теорем теории полугрупп (множество замкнутых формул указанной сигнатуры, истинных во всех полугруппах) неразрешимо.

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

Пусть фиксирован алфавит , а также конечное число пар слов

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

141. Сколько элементов в полугруппе с образующими и и соотношениями , , (через мы обозначаем пустое слово)? (Ответ: ; это группа .)

Известно, что существуют такие образующие и соотношения, при которых проблема равенства слов (выяснить, принадлежат ли два данных слова одному классу эквивалентности) является алгоритмически неразрешимой (подробнее см. в [5]). Мы сейчас покажем, что этот вопрос можно свести к вопросу о выводимости некоторой формулы в теории полугрупп, так что если бы она была разрешимой, то получилось бы противоречие.

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

Напротив, если слово не получается из

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

Таким образом, любой алгоритм, проверяющий истинность формул в классе всех полугрупп, можно было бы использовать для проверки равенства двух слов в полугруппе, заданной образующими и соотношениями. А среди таких полугрупп есть неразрешимые.

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

142. Пусть теория разрешима, а теория той же сигнатуры получается из добавлением конечного числа аксиом. Тогда теория разрешима. (Указание: дополнительные аксиомы соединяем конъюнкциями и помещаем в посылку импликации.)

Добавление аксиом может сделать неразрешимую теорию разрешимой. Например, как мы уже упоминали, это происходит с теорией групп при добавлении аксиомы коммутативности.

Теория равенства

Рассмотрим сигнатуру, содержащую единственный двуместный предикат равенства, и теорию, состоящую из трех аксиом равенства (рефлексивность, симметричность и транзитивность). Эти аксиомы рассматривались в разделе "Аксиомы равенства"; заметим, что у нас нет других предикатных и функциональных символов (и связанных с ними аксиом равенства).

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

Теорема 68.Множество теорем теории равенства является разрешимым.

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

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

Например, формула при истинна во всех моделях, начиная с двухэлементной, а при истинна во всех моделях, начиная с трехэлементной. Можно ожидать, что модели с большим числом элементов неотличимы друг от друга и от бесконечных моделей.

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

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

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

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

Квантор всеобщности рассматривается точно так же (а можно его выразить через квантор существования и вообще не рассматривать). Лемма доказана.

Доказательство леммы конструктивно, то есть указывает способ узнать, будет ли формула истинной, если известно, какие ее параметры равны и какова мощность носителя. В частности, для замкнутых формул получаем способ проверять их истинность для всех значений мощности, то есть выводимость в теории равенства.

140. Рассмотрим теорию, в сигнатуре которой есть равенство и конечное число одноместных предикатных символов, а аксиомами являются аксиомы равенства (включая устойчивость предикатов относительно равенства, как в разделе "Аксиомы равенства"). Покажите, что эта теория разрешима.

Эта задача показывает, что добавление одноместных предикатов в сигнатуру не делает теорию равенства неразрешимой. Отметим, что расширение сигнатуры (без изменения множества аксиом) может превратить разрешимую теорию в неразрешимую: например, добавив конечное число одноместных функциональных символов к теории равенства, получим неразрешимую теорию (как видно из доказательства теоремы Черча с помощью проблемы тождества для полугрупп, см. [5]).Добавление одного двуместного предикатного символа также дает неразрешимую теорию.

Нестандартный анализ

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

Это направление получило название нестандартного анализа. Целей тут две: во-первых, упростить доказательства известных теорем, во-вторых, использовать методы нестандартного анализа для получения новых результатов. Насколько эти цели достигнуты за тридцать с лишним лет, прошедших с возникновения нестандартного анализа?

Простота доказательств — дело вкуса. Конечно, всякий преподаватель курса математического анализа мечтает избавиться от утомительных рассуждений с выбором достаточно малых эпсилонов. Но если вместо этого нужно постоянно переходить от модели к ее элементарному расширению и обратно, лекарство может оказаться страшнее болезни. Во всяком случае, " нестандартные" учебники математического анализа для нематематиков (один из них написан Кейслером [34]) большого распространения не получили.

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

Так или иначе, нестандартный анализ — интересное приложение теории моделей, и мы разберем несколько простых примеров. Более подробно об этом можно прочесть в книгах Дэвиса [11] и Успенского [27], а также в последней главе книги Робинсона [22].

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

Перейдем к формальным определениям. Мы будет рассматривать вещественную прямую как модель очень богатой сигнатуры. Для каждого отношения на (c произвольным числом аргументов) введем свой предикатный символ. Получится

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

в (при всех ) введем свой функциональный символ. Это даст еще символов.

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

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

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

где — множество всех истинных в

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

164. Проведите это рассуждение подробно.

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

будут нестандартными гипердействительными числами. (По нашему предположению таковые существуют.)

Утверждение об элементарной эквивалентности

и называют принципом переноса: он позволяет перенести истинность формулы из в (или наоборот).

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

Аналогично определяется множество гиперцелых чисел и вообще множество для любого множества

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

Принцип переноса гарантирует, что для конечного

нестандартных элементов в не появится. В самом деле, пусть, скажем, в ровно три элемента , и . Тогда формула

в которой — предикат, соответствующий множеству , истинна в . По принципу переноса она истинна и в , так что и состоит из трех элементов, являющихся значениями констант , и

(отождествленных со стандартными действительными числами).

Впоследствии мы увидим, что бесконечное множество

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

Несколько простых следствий принципа переноса:

(применяем принцип переноса к формуле );, (применяем принцип переноса к формуле , где — объединение и );аналогичные утверждения верны и для пересечения и разности множеств.

165. Покажите, что для счетного объединения аналогичное утверждение может не быть верным и

может отличаться от .

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

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

167. Покажите, что для всюду определенной функции два способа ее продолжения (как функции и через график) дают одну и ту же функцию.

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

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

169. Абсолютную величину гипердействительного числа можно определить как при и как при . С другой стороны, можно рассмотреть нестандартный аналог функции . Покажите, что получится одно и то же.

170. Покажите, что поле гипердействительных чисел является вещественно замкнутым.

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

Целью расширения было получить возможность рассматривать бесконечно большие и бесконечно малые числа. Дадим соответствующие определения.

Гипердействительное число , большее всех стандартных чисел, называется положительным бесконечно большим. Аналогично определяются отрицательные бесконечно большие числа.

171. Докажите, что число является отрицательным бесконечно большим тогда и только тогда, когда является положительным бесконечно большим. Докажите, что является положительным бесконечно большим тогда и только тогда, когда является либо положительным, либо отрицательным бесконечно большим.

Гипердействительные числа, не являющиеся бесконечно большими, называют конечными. Другими словами, гипердействительное число называется конечным, если оно лежит в промежутке со стандартными концами и .

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

Сумма и произведение двух конечных чисел конечны. Если

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

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

Два гипердействительных числа называются бесконечно близкими, если их разность бесконечно мала. Обозначение: .

172. Докажите, что если , то для любого гипердействительного , а для любого конечного гипердействительного . Покажите, что условие конечности существенно.

173. Покажите, что два конечных гипердействительных числа бесконечно близки тогда и только тогда, когда между ними нельзя вставить двух разных стандартных чисел.

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

Теорема 78. Всякое конечное гипердействительное число бесконечно близко к некоторому стандартному числу.

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

Пусть — конечное гипердействительное число. Рассмотрим множество множество всех стандартных действительных чисел, меньших или равных , а также множество всех стандартных действительных чисел, больших или равных . Конечность числа гарантирует, что оба этих множества непусты (если бы, скажем, было пусто, то

было бы положительным бесконечно большим). Заметим, что и не пересекаются (если только само не является стандартным, и тогда доказывать нечего) и в объединении дают все .

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

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

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

174. Докажите, что если и конечны, причем , то и .

Теорема 79. Среди гипердействительных чисел есть ненулевые бесконечно малые, а также бесконечно большие числа.

Напомним, что по нашему предположению не совпадает с , то есть существует некоторое нестандартное гипердействительное число . Если

бесконечно, то — искомое ненулевое бесконечно малое число. Если конечно, то — искомое ненулевое бесконечно малое число (а обратное к нему будет бесконечно большим).

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

Теперь обратимся к натуральным и целым числам.

Теорема 80. Существуют нестандартные гипернатуральные числа, при этом все они бесконечно велики.

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

Всякое положительное действительное число есть сумма натурального и числа из . Принцип переноса гарантирует, что всякое положительное гипердействительное число есть сумма гипернатурального и гипердействительного , для которого . Возьмем бесконечно большим, тогда и будет бесконечно большим. Первое утверждение доказано.

Пусть теперь — конечное гипернатуральное число. По определению конечности оно меньше некоторого стандартного числа , скажем, числа . Но в стандартной модели верна формула

По принципу переноса она верна и в , поэтому число совпадает с одним из стандартных чисел .

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

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

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

Таким образом, любая последовательность приобретает — помимо своего желания — бесконечный "хвост".

177. Покажите, что если две последовательности отличаются лишь в конечном числе членов, то их бесконечные хвосты одинаковы.

Сейчас мы используем продолжение последовательностей для доказательства такого факта:

Теорема 81. Нестандартный аналог множества

действительных чисел совпадает с тогда и только тогда, когда множество конечно.

Если конечно, и, скажем, состоит из трех элементов , то можно записать формулу

По принципу переноса эта формула остается истинной в , так что состоит из тех же трех элементов.

Пусть теперь бесконечно. Покажем, что

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

Галактикой гипердействительного числа называют множество всех гипердействительных , для которых разность конечна.

178. Покажите, что множество гипердействительных чисел разбивается на галактики. Определите на галактиках естественное отношение линейного порядка и покажите, что этот порядок плотный и не имеет наибольшего и наимен

179. Каждое действительное число , не являющееся двоично- рациональным, можно единственным образом записать в виде бесконечной двоичной дроби ; другими словами, ему соответствует последовательность нулей и единиц (нас будет интересовать лишь дробная часть после запятой). Фиксируем бесконечное гипернатуральное и рассмотрим те числа , у которых . Покажите, что множество таких чисел переходит в свое дополнение при симметрии относительно любой двоично-рациональной точки (другими словами, для двоично-рациональных ) и потому не может быть измеримым по Лебегу. \end{problem}

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

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

Теорема 82. Пусть . Множество ограничено (в обычном смысле) тогда и только тогда, когда все элементы его гипердействительного аналога конечны.

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

Если все элементы меньше некоторого стандартного

по модулю, то и все элементы меньше того же (принцип переноса), поэтому в одну сторону утверждение очевидно.

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

181. Покажите, что если все элементы множества меньше некоторого гипердействительного , то ограничено.

182. Говорят, что множество гипердействительных чисел является внутренним, если оно есть гипердействительный аналог некоторого множества действительных чисел. Покажите, что множество конечных гипердействительных чисел не является внутренним.

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

Нестандартный анализ позволяет дать естественные определения предельной точки и предела.

Теорема 83. Число является предельной точкой последовательности действительных чисел тогда и только тогда, когда найдется бесконечно далекий член последовательности, бесконечно близкий к .

(Бесконечно далеким членом последовательности мы называем значение при бесконечном гипернатуральном .)

Если является предельной точкой, то для всякого положительного и всякого натурального

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

Напротив, если для некоторого натурального и для некоторого все члены последовательности, начиная с -го, отстоят от более чем на , то по принципу переноса все бесконечно далекие члены последовательности также отстоят от более чем на .

184. Покажите, что число принадлежит замыканию множества тогда и только тогда, когда некоторый элемент множества бесконечно близок к .

185. Как определить в терминах нестандартного анализа понятие предельной точки множества (в любой окрестности которой бесконечно много членов множества)?

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

Теорем 84. Последовательность действительных чисел сходится к числу тогда и только тогда, когда все ее бесконечно далекие члены бесконечно близки к .

Пусть является пределом. Тогда для всякого найдется , начиная с которого все члены последовательности отстоят от менее чем на . В частности, все бесконечно далекие члены таковы и их расстояние до меньше любого стандартного .

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

Приведем теперь нестандартные критерии стандартных топологических понятий.

Теорема 85. Множество открыто тогда и только тогда, когда вместо со всякой точкой оно содержит и всю ее монаду, то есть все гипердействительные точки, бесконечно близкие к .

(Cтрого говоря, следовало бы сказать "его нестандартный аналог " вместо "оно"; напомним также, что и содержат одни и те же стандартные числа.)

Если открыто и содержит вместе с точкой

ее -окрестность, то монада точки по принципу переноса содержится в .

Если же некоторая точка не является внутренней и для всякого действительного

найдется точка вне на расстоянии меньше , применим принцип переноса и возьмем бесконечно малое . Мы получим число, бесконечно близкое к и не лежащее в .

Переходя к дополнениям, получаем, что множество

замкнуто тогда и только тогда, когда любая стандартная точка, бесконечно близкая к некоторой точке из , принадлежит .

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

Теорема 86. Множество компактно тогда и только тогда, когда любой элемент множества бесконечно близок к некоторому (стандартному) элементу множества .

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

186. Используя полученные только что критерии, покажите, что любой отрезок действительной прямой компактен, а любой интервал открыт.

187. Покажите, используя нестандартный критерий открытости, что объединение любого числа открытых множеств открыто. (Напоминание: гипердействительный аналог объединения может не совпадать с объединением гипердействительных аналогов!)

188. Покажите, что пересечение двух (или любого конечного числа) открытых множеств открыто. (Где используется конечность?)

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

190. Докажите, что всякая фундаментальная последовательность сходится, используя приведенный критерий фундаментальности. (Указание. Ограниченность приходится доказывать, исходя из стандартных определений.)

191. Докажите, что если последовательность ограничена и имеет единственную предельную точку, то она сходится (к этой точке).

192. Докажите, что ограниченная возрастающая последовательность имеет предел.

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

Теорема 87. Число есть предел функции в точке тогда и только тогда, когда для всех , бесконечно близких к , но отличных от .

Пусть функция имеет предел согласно - -определению и для всякого

найдется с нужными свойствами. Бесконечно близкое к

число попадает в -окрестность точки при любом стандартном , поэтому попадает в -окрестность точки .

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

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

Для функции, определенной на некотором множестве , критерий непрерывности в точке выглядит так: для всякой точки , бесконечно близкой к .

193. Проверьте это.

Поучительно понять, чем это свойство отличается от равномерной непрерывности.

Теорема 88. Функция равномерно непрерывна на множестве тогда и только тогда, когда для всех выполнено .

Пусть выполнено обычное -- определение непрерывности. Бесконечно близкие точки отличаются менее чем на (стандартное) , а потому их образы отличаются менее чем на . Это верно для любого стандартного , поэтому .

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

Чем это отличается от непрерывности во всех точках множества ? Непрерывность во всех точках

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

принадлежит согласно теореме 86). Тем самым мы получили (почти что тривиальное) нестандартное доказательство классической теоремы: непрерывная на компакте функция равномерно непрерывна.

Вот еще несколько "нестандартных" доказательств стандартных (во всех смыслах этого слова) теорем из курса математического анализа.

Теорема 89. Непрерывная на отрезке функция, принимающая значения разных знаков на концах отрезка, имеет нуль на этом отрезке.

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

Теорема 90. Непрерывная во всех точках компакта функция ограничена на нем.

Пусть функция непрерывна на компакте . Следуя нестандартному критерию ограниченности, мы должны показать, что значения функции во всех точках

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

Обратите внимание, что мы пользовались аксиомой полноты (для множества ) только один раз, при доказательстве теоремы 78. Это и не удивительно, поскольку из утверждения этой теоремы следует аксиома полноты.

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

найдется число , являющееся верхней гранью, для которого не будет верхней гранью. Примените принцип переноса, взяв бесконечно малое и рассмотрев стандартную часть соответствующего числа .

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

196. Покажите, что согласно нестандартному определению производной (предыдущая задача).

197. Как использовать нестандартный анализ для определения понятия интеграла?

В наших примерах все рассмотрения были ограничены множеством гипердействительных чисел. Это ограничение кажется существенным — не вполне ясно, каким образом можно применить те же методы к произвольному топологическому пространству (в котором нет бесконечно больших чисел). Тем не менее это возможно, и об этом можно прочесть в книгах Дэвиса [11] или Успенского [27].

Ультрафильтры и компактность

В этом разделе мы дадим прямое доказательство теоремы о компактности (теорема 50).

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

(пустое множество не является большим);

(пересечение двух больших множеств — снова большое множество); отсюда следует, что пересечение конечного числа больших множеств — большое множество и что любые два больших множества пересекаются; (любое надмножество большого множества является большим); отсюда следует, что все множество является большим.

Дополнения к большим множествам естественно назвать малыми. (Отметим, что множество может не быть ни большим, ни малым; это отличает фильтры от ультрафильтров, которые мы вскоре определим.)

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

156. Переформулируйте определение фильтра в терминах малых множеств.

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

Иными словами, ультрафильтром называется фильтр на с таким свойством: или для любого множества .

Очевидно, любой главный фильтр является ультрафильтром. Фильтры остальных наших примеров не были ультрафильтрами.

157. Докажите, что на конечном множестве любой ультрафильтр является главным.

158. Докажите, что любой неглавный ультрафильтр содержит все коконечные множества.

159. Докажите, что если ультрафильтр не является главным, то вместе с каждым множеством он содержит и все множества , для которых симметрическая разность конечна.

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

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

Теорема 75. Всякий фильтр на множестве можно расширить до ультрафильтра .

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

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

160. Докажите, что на любом бесконечном множестве есть неглавный ультрафильтр. (Указание: расширим фильтр коконечных множеств до ультрафильтра.)

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


Аксиомы фильтра тогда звучат так: решение, против которого все, принято быть не может; если каждое из двух решений принимается, то они принимаются и в совокупности; наконец, принятое решение не может быть отвергнуто, если некоторые из голосовавших против него передумали.

Свойство ультрафильтра также имеет ясный смысл: по любому вопросу можно принять решение (одно из двух противоположных мнений набирает большинство). Главные ультрафильтры соответствуют диктатуре (существенно мнение лишь одного голосующего); задача 150 показывает, что для конечного числа голосующих любые другие способы не позволяют принять решения по некоторым вопросам.

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

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

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

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


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

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

161. Проведите это рассуждение подробно.

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

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

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

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



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

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

162. Что можно сказать про фильтрованное произведение по главному фильтру?

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

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



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

Мы сейчас докажем это свойство по индукции. Как обычно, надо предварительно распространить его на формулы с параметрами.

Теорема 77 (Лося об ультрапроизведениях).

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

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

Следствие. Ультрапроизведение семейства моделей некоторой теории является моделью той же теории.

Докажем теорему Лося индукцией по построению формулы. Для атомарных формул оно непосредственно следует из определения истинности предикатов.

Пусть формула является конъюнкцией двух других формул , для которых утверждение уже верно. Тогда множество тех индексов, для которых истинно, является пересечение множеств тех индексов, где истинны

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



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

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

Импликация сводится к уже рассмотренным случаям (

эквивалентна ); можно также сразу заменить формулу на эквивалентную без импликации.

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

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

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

истинна в . Но тогда для этих индексов и формула

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

Теорема Лося доказана.

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



Теорема Лося позволяет дать прямое доказательство теоремы компактности (теорема 50). Она утверждает, что если всякое конечное подмножество данного множества замкнутых формул совместно (имеет модель), то и все множество совместно.

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

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

Поучительно проследить до конца, что дает такого рода построение для какого-нибудь конкретного примера. Вспомним построение нестандартного натурального ряда. Оно использовало теорему компактности. Сочетая его с приведенным только что доказательством теоремы компактности (и кое-что упростив), получаем такую конструкцию.

Рассмотрим натуральные числа как интерпретацию сигнатуры . Рассмотрим ультрапроизведение счетного числа таких интерпретаций по модулю какого-либо неглавного ультрафильтра. Теорема Лося говорит, что в этой интерпретации будут истинны те же формулы, что в натуральном ряду, то есть что элементарно эквивалентна стандартной интерпретации .

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

не является стандартной.

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

---

---