Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 38
Текст из файла (страница 38)
, an ) и f (a1 , . . . , an ) = a, истинные в A, истинны и в B.Истинные в A формулы вида ϕ(a1 , . . . , an ) принадлежат ThA (A) ипотому истинны и в B; ложные в A формулы имеют отрицания вThA (A) и потому ложны в B.Таким образом, для доказательства теоремы Левенгейма – Сколема о повышении мощности осталось построить нормальную модель теории ThA (A), имеющую сколь угодно большую мощность.Это можно сделать так: добавим множество новых констант ci иформулы ci 6= cj (для всех i 6= j) к теории ThA (A). Полученнаятеория будет совместной по теореме компактности для нормальныхмоделей.
(В самом деле, любая конечная часть её имеет нормальную модель, поскольку содержит конечное число новых констант,172Теории и модели[гл. 5]и им можно придать различные значения в A.) Поэтому и вся теория имеет нормальную модель. Всем константам ci соответствуют вэтой модели разные элементы (поскольку истинна формула ci 6= cj ),поэтому мощность этой модели может быть сколь угодно большой,если использовать достаточно много констант.Этот же приём будет использован нами при построении нестандартной модели арифметики (с.
193). Приведённое рассуждение даёт оценку мощности снизу. Можнополучить и в точности нужную мощность:Теорема 62. Пусть A — бесконечная нормальная интерпретациясигнатуры σ (с равенством) и пусть β — мощность, не меньшая мощностей сигнатуры σ и интерпретации A. Тогда существует нормальное элементарное расширение B ⊃ A мощности β. Мощность сигнатуры σA есть максимум из мощностей σ и A;после добавления новых констант в количестве β штук получитсясигнатура мощности β, и согласно теореме 48 (с. 152) найдётся модель множества ThA (A) мощности β. Преобразование её в нормальную модель (факторизация) может лишь уменьшить мощность, ноβ различных элементов у нас заведомо есть. Аналогичный приём (добавление констант) позволяет легко доказать такое утверждение:Теорема 63.
Если теория (в произвольной сигнатуре с равенством)имеет сколь угодно большие конечные нормальные модели, то онаимеет и бесконечную нормальную модель. Добавим к теории бесконечное число новых констант и аксиомы о том, что все они различны. Любой конечный фрагмент расширенной теории имеет нормальную модель (возьмём достаточно большую конечную модель и проинтерпретируем в ней константы). Потеорме компактности и вся расширенная теория имеет нормальнуюмодель, которая и будет бесконечной нормальной моделью исходнойтеории. Вообще можно задать себе такой естественный вопрос.
Пусть естьнекоторая теория (или даже просто одна формула). Каковы могутбыть мощности её нормальных моделей? Как мы видели, для теорийс конечной сигнатурой верно одно из двух: либо бесконечных моделей вовсе нет, либо есть бесконечные модели всех мощностей. Этогарантируют теоремы Левенгейма – Сколема об элементарной подмодели (теорема 42) и о повышении мощности (теорема 61).Что можно сказать про мощности конечных моделей? Для каждой формулы рассмотрим множество всех возможных мощностей её[п. 2]Повышение мощности173конечных моделей.
Его иногда называют спектром формулы. Этомножество может быть устроено довольно сложным образом: например, для формулы, выражающей аксиомы поля, спектр состоит извсех степеней простых чисел.116. (а) Укажите формулу, спектр которой состоит из всех чётныхположительных чисел. (б) Укажите формулу, спектр которой состоит извсех нечётных чисел. (в) Укажите формулу, спектр которой состоит извсех составных чисел.Любопытно, что проблема конечного спектра (стоящая в книгеКейслера и Чэна [13] под номером 1 среди «старых проблем теориимоделей»), неожиданно оказалась связана с центральной проблемойтеории сложности вычислений — так называемой «проблемой перебора».
(Проблема конечного спектра состоит в следующем: верно ли,что дополнение (до N) к спектру любой формулы является спектромнекоторой другой формулы?)В качестве примера использования теоремы о повышении мощности докажем теорему Гильберта о нулях (теорема 40), не проводя элиминацию кванторов. Пусть система уравнений имеет решениев поле k 0 , являющемся расширением алгебраически замкнутого поля k. Покажем, что она имеет решение и в k.
Построим элементарное расширение k 00 ⊃ k очень большой мощности. Теперь k 0 можновложить в k 00 (это вложение строится по трансфинитной рекурсии:добавляя алгебраический элемент, мы пользуемся алгебраическойзамкнутостью k 00 , добавляя трансцендентный элемент, мы пользуемся большой мощностью k 00 ).
Значит, система имеет решение в k 00 .Поскольку k 00 было элементарным расширением, то система имеетрешение в k.Другое любопытное применение теоремы о повышении мощноститаково. Назовём линейно упорядоченное множество M однородным,если для любых двух возрастающих последовательностей x1 < x2 << . . . < xn и y1 < y2 < . . . < yn найдётся автоморфизм множества M ,переводящий xi в yi (при всех i = 1, . . . , n).Теорема 64.
Для всякой бесконечной мощности найдётся однородное линейно упорядоченное множество такой мощности. Множество рациональных чисел (и вообще любое счётное плотное линейно упорядоченное множество) однородно. В самом деле,соответствие между двумя наборами его элементов постепенно продолжается до автоморфизма (добавляем элементы поочерёдно с тойили другой стороны).
Другой способ убедиться в этом — вспомнитьо том, что это рациональные числа, и взять кусочно-линейный авто-174Теории и модели[гл. 5]морфизм.Для каждого n фиксируем способ продолжения автоморфизмовс n-элементных подмножеств в виде функции fn с 2n + 1 аргументами: f (z, x1 , . . . , xn , y1 , . . . , yn ) означает элемент, в который переходитz при автоморфизме, переводящем xi в yi . Рассмотрим теперь Q какинтерпретацию сигнатуры, включающей порядок и все fi .
По теореме о повышении мощности можно найти элементарно эквивалентную интерпретацию любой заданной мощности. Поскольку свойствафункций fn выражаеются формулами, получится однородное линейно упорядоченное множество заданной мощности. 5.3. Полные теорииВ этом разделе мы попытаемся систематизировать уже известныенам понятия и факты.• Начнём с напоминаний. Сигнатурой мы называли набор предикатных и функциональных символов. Среди формул даннойсигнатуры выделяют замкнутые (формулы без параметров).Сигнатура имеет интерпретации, в которых замкнутые формулы этой сигнатуры бывают истинными и ложными. Произвольное множество замкнутых формул данной сигнатуры называется теорией в этой сигнатуре. Моделью теории называется интерпретация, в которой все формулы теории истинны.Теория называется совместной, если она имеет модель.• Теория называется теорией с равенством, если она включает в себя аксиомы равенства (а её сигнатура содержит символ равенства).
Интерпретация теории с равенством называется нормальной, если равенство интерпретируется как совпадение элементов носителя интерпретации. Совместная теория сравенством имеет нормальную модель (получаемую из произвольной модели факторизацией по отношению равенства).• Говорят, что замкнутая формула ϕ выводима в теории T (является теоремой теории T ), если формула ϕ получается изаксиом исчисления предикатов и формул теории T по правилам вывода. (Обозначение: T ` ϕ.)Формула ϕ выводима в теории T тогда и только тогда, когдав исчислении предикатов выводится некоторая формула видаτ → ϕ, где τ — конъюнкция конечного числа формул из T .[п. 3]Полные теории175Формула ϕ семантически следует из T , если она истинна влюбой модели теории T (обозначение: T ϕ). Семантическоеследование равносильно выводимости (теорема 51, с.
154). Взявв качестве ϕ тождественно ложную формулу ⊥ (скажем, отрицание тавтологии), приходим к понятиям противоречивости(T `⊥) и несовместности (T ⊥, T не имеет моделей). В противоречивой теории выводима любая формула (соответствующей сигнатуры).• Непротиворечивая теория T полна (в данной сигнатуре), еслидля любой замкнутой формулы ϕ этой сигнатуры либо формула ϕ, либо её отрицание ¬ϕ выводится из T .• Для произвольной интерпретации M произвольной сигнатуры σ можно рассмотреть элементарную теорию интерпретации M , обозначаемую Th(M ) и состоящую из всех истинныхв M замкнутых формул сигнатуры σ. Очевидно, эта теорияполна (одна из формул ϕ и ¬ϕ ей принадлежит).
Две интерпретации M1 и M2 элементарно эквивалентны, если их элементарные теории совпадают: Th(M1 ) = Th(M2 ).• Теория T называется конечно аксиоматизируемой, если существует конечное множество T 0 теорем теории T , из которыхвыводятся все утверждения из T (другими словами, если существует конечная теория, имеющая то же самое множествотеорем).• Теория с равенством, имеющая конечную или счётную сигнатуру, называется категоричной в счётной мощности, если всееё счётные нормальные модели изоморфны. Категоричность вданной несчётной мощности определяется аналогично.• Теория с конечной сигнатурой называется разрешимой, если существует алгоритм, который по произвольной замкнутой формуле определяет, выводима ли она в этой теории или нет.117.
Покажите, что добавление к теории любой её теоремы не меняетмножества теорем.Прежде чем переходить к примерам, сделаем два простых наблюдения.Теорема 65 (критерий Лося – Воота). Непротиворечивая теория Tс равенством в конечной или счётной сигнатуре, не имеющая конечных моделей и категоричная в счётной мощности, полна.176Теории и модели[гл. 5] Предположим, что ни одна из формул ϕ и ¬ϕ не выводима втеории T .
Тогда обе теории T ∪ {¬ϕ} и T ∪ {ϕ} непротиворечивы.По теореме 47 (с. 152) они имеют счётные модели, которые остаютсясчётными после факторизации (перехода к нормальным моделям),поскольку теория T не имеет конечных моделей. Эти счётные модели должны быть изоморфными (в силу категоричности). С другойстороны, в одной из них истинна формула ¬ϕ, а в другой — формула ϕ, так что они даже не элементарно эквивалентны (мы знаем израздела 3.9, что такого быть не может).