Повышение мощности
Теорема Левенгейма-Сколема позволяла уменьшать мощность интерпретации (она утверждала, что для любой бесконечной интерпретации конечной или счетной сигнатуры существует элементарно эквивалентная ей счетная подструктура). В этом разделе мы рассмотрим обратную задачу — расширение интерпретации до элементарно эквивалентной интерпретации большей мощности. Соответствующее утверждение также называют теоремой Левенгейма-Сколема.
Прежде всего отметим, что без требования нормальности это утверждение бессодержательно: как уже говорилось, мы можем дублировать элементы сигнатуры в произвольном количестве. Поэтому мы предполагаем, что все рассматриваемые интерпретации нормальны (равенство интерпретируется как тождественное совпадение).
Теорема 61 (Левенгейма-Сколема о повышении мощности).
Пусть — бесконечная нормальная интерпретация некоторой сигнатуры с равенством. Тогда существует нормальная интерпретация сколь угодно большой мощности, являющаяся элементарным расширением .
(Это означает, согласно определению, напомним, что интерпретация предикатных и функциональных символов в продолжает их интерпретацию в и что формулы сигнатуры , параметрам которых приданы значения из , одновременно истинны в и в .)
Сформулируем утверждение теоремы в терминах теорий и моделей. Пусть — произвольная нормальная интерпретация сигнатуры . Рассмотрим сигнатуру , которая получается из добавлением констант — по одной для каждого элемента множества . Эта сигнатура имеет естественную нормальную интерпретацию с носителем : значением каждой константы является соответствующий ей элемент. (Возможно, что в изначально было достаточно констант и всякий элемент был значением некоторой константы. Тогда эта процедура лишняя, но и вреда от нее нет.)
Рассмотрим теорию , состоящую из формул сигнатуры , истинных в при указанной интерпретации. Всякое элементарное расширение
интерпретации будет моделью теории . В самом деле, замкнутая формула
сигнатуры получается подстановкой констант вместо параметров из какой-то формулы сигнатуры . (Мы используем не вполне корректные обозначения, в частности, отождествляем элементы множества с константами для них.) Ее истинность в (или в ) равносильна истинности формулы при значениях параметров — формально говоря, следует воспользоваться леммой 2.
Поэтому по определению элементарного расширения все формулы из будут истинны и в .
Верно и обратное: любая нормальная модель теории естественно определяет элементарное расширение интерпретации . В самом деле, пусть дана нормальная модель этой теории с носителем . Тогда каждый элемент множества (точнее, соответствующая этому элементу константа) интерпретируется некоторым элементом множества . Разным элементам множества соответствуют разные элементы в , так как формула , истинная в , должна быть истинной и в . Таким образом, вкладывается в и можно отождествить его с некоторым подмножеством множества . Это отождествление корректно в том смысле, что предикаты и функциональные символы интерпретируются согласованным образом. В самом деле, атомарные формулы вида , а также формулы и , истинные в , истинны и в . Истинные в формулы вида принадлежат и потому истинны и в ; ложные в формулы имеют отрицания в и потому ложны в .
Таким образом, для доказательства теоремы Левенгейма-Сколема о повышении мощности осталось построить нормальную модель теории , имеющую сколь угодно большую мощность. Это можно сделать так: добавим множество новых констант и формулы (для всех ) к теории . Полученная теория будет совместной по теореме компактности для нормальных моделей. (В самом деле, любая конечная часть ее имеет нормальную модель, поскольку содержит конечное число новых констант, и им можно придать различные значения в .) Поэтому и вся теория имеет нормальную модель. Всем константам
соответствуют в этой модели разные элементы (поскольку истинна формула ), поэтому мощность этой модели может быть сколь угодно большой, если использовать достаточно много констант.
Этот же прием будет использован нами при построении нестандартной модели арифметики
Приведенное рассуждение дает оценку мощности снизу. Можно получить и в точности нужную мощность:
Теорема 62. Пусть — бесконечная нормальная интерпретация сигнатуры (с равенством) и пусть — мощность, не меньшая мощностей сигнатуры и интерпретации .
Тогда существует нормальное элементарное расширение мощности .
Мощность сигнатуры есть максимум из мощностей и ; после добавления новых констант в количестве штук получится сигнатура мощности , и согласно теореме 48 найдется модель множества мощности . Преобразование ее в нормальную модель (факторизация) может лишь уменьшить мощность, но различных элементов у нас заведомо есть.
Аналогичный прием (добавление констант) позволяет легко доказать такое утверждение:
Теорема 63. Если теория (в произвольной сигнатуре с равенством) имеет сколь угодно большие конечные нормальные модели, то она имеет и бесконечную нормальную модель.
Добавим к теории бесконечное число новых констант и аксиомы о том, что все они различны. Любой конечный фрагмент расширенной теории имеет нормальную модель (возьмем достаточно большую конечную модель и проинтерпретируем в ней константы). По теорме компактности и вся расширенная теория имеет нормальную модель, которая и будет бесконечной нормальной моделью исходной теории.
Вообще можно задать себе такой естественный вопрос. Пусть есть некоторая теория (или даже просто одна формула). Каковы могут быть мощности ее нормальных моделей? Как мы видели, для теорий с конечной сигнатурой верно одно из двух: либо бесконечных моделей вовсе нет, либо есть бесконечные модели всех мощностей. Это гарантируют теоремы Левенгейма-Сколема об элементарной подмодели (теорема 42) и о повышении мощности (теорема 61).
Что можно сказать про мощности конечных моделей? Для каждой формулы рассмотрим множество всех возможных мощностей ее конечных моделей. Его иногда называют спектром формулы. Это множество может быть устроено довольно сложным образом: например, для формулы, выражающей аксиомы поля, спектр состоит из всех степеней простых чисел.
116. (а) Укажите формулу, спектр которой состоит из всех четных положительных чисел. (б) Укажите формулу, спектр которой состоит из всех нечетных чисел. (в) Укажите формулу, спектр которой состоит из всех составных чисел.
Любопытно, что проблема конечного спектра (приведенная в книге Кейслера и Чэна под номером 1 среди "старых проблем теории моделей"), неожиданно оказалась связана с центральной проблемой теории сложности вычислений — так называемой "проблемой перебора". (Проблема конечного спектра состоит в следующем: верно ли, что дополнение (до ) к спектру любой формулы является спектром некоторой другой формулы?)
В качестве примера использования теоремы о повышении мощности докажем теорему Гильберта о нулях (теорема 40), не проводя элиминацию кванторов. Пусть система уравнений имеет решение в поле , являющемся расширением алгебраически замкнутого поля . Покажем, что она имеет решение и в . Построим элементарное расширение очень большой мощности. Теперь можно вложить в (это вложение строится по трансфинитной рекурсии: добавляя алгебраический элемент, мы пользуемся алгебраической замкнутостью , добавляя трансцендентный элемент, мы пользуемся большой мощностью ). Значит, система имеет решение в . Поскольку было элементарным расширением, то система имеет решение в .
Другое любопытное применение теоремы о повышении мощности таково. Назовем линейно упорядоченное множество
однородным, если для любых двух возрастающих последовательностей и найдется автоморфизм множества , переводящий в (при всех ).
Теорема 64. Для всякой бесконечной мощности найдется однородное линейно упорядоченное множество такой мощности.
Множество рациональных чисел (и вообще любое счетное плотное линейно упорядоченное множество) однородно. В самом деле, соответствие между двумя наборами его элементов постепенно продолжается до автоморфизма (добавляем элементы поочередно с той или другой стороны). Другой способ убедиться в этом — вспомнить о том, что это рациональные числа, и взять кусочно-линейный автоморфизм.
Для каждого фиксируем способ продолжения автоморфизмов с -элементных подмножеств в виде функции с аргументами: означает элемент, в который переходит при автоморфизме, переводящем в . Рассмотрим теперь
как интерпретацию сигнатуры, включающей порядок и все . По теореме о повышении мощности можно найти элементарно эквивалентную интерпретацию любой заданной мощности. Поскольку свойства функций выражаеются формулами, получится однородное линейно упорядоченное множество заданной мощности.
