Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 39
Текст из файла (страница 39)
Аналогично доказывается и общая форма критерия Лося – Воота:Теорема 66. Непротиворечивая теория с равенством в конечнойили счётной сигнатуре, не имеющая конечных моделей и категоричная в данной несчётной мощности α, полна. Пусть теория T не полна и к ней можно присоединить безпротиворечия любую из формул ϕ и ¬ϕ. Рассмотрим счётные нормальные модели теорий T ∪ {ϕ} и T ∪ {¬ϕ}. По теореме 62 увеличимих мощности до α и получим противоречие. 118. Условие конечности или счётности сигнатуры в этой теореме можно ослабить. Как это сделать?Вот пример применения теоремы 66. Теория алгебраически замкнутых полей характеристики 0 категорична в любой несчётноймощности. (Это можно доказать, используя базисы трансцендентности: такое поле имеет базис трансцендентности над полем алгебраических чисел, мощность которого равна мощности всего поля, адва поля с равномощными базисами трансцендентности изоморфны).
Следовательно, эта теория полна.Заметим, что это наблюдение согласовано со знаменитой (и трудной!) теоремой Морли; эта теорема утверждает, что теория с равенством, категоричная в одной несчётной мощности, категорична и вовсех несчётных мощностях. (Подробно о теореме Морли можно прочесть, например, в учебнике Кейслера и Чэна [13].)Теорема 67. Конечно аксиоматизируемая полная теория в конечной сигнатуре разрешима. Пусть дана произвольная формула ϕ.
Будем перебирать всевыводы в исчислении предикатов и проверять, не обнаружилась ливыводимость одной из формул ϕ или ¬ϕ из конъюнкции некоторыхаксиом теории T . Рано или поздно одна из них окажется выводимой(поскольку теория полна), и тем самым мы узнаем, какая из формулвыводима в теории. [п. 3]Полные теории177Это доказательство неконструктивно в том смысле, что не даёт никакой оценки на время работы алгоритма. Отметим также, чтоне обязательно требовать конечной аксиоматизируемости теории; достаточно, чтобы она имела разрешимое или перечислимое множествоаксиом (см.
[5]).Проиллюстрируем все эти понятия на нескольких (в основномуже обсуждавшихся нами) примерах.Плотные линейно упорядоченные множестваРассмотрим сигнатуру, содержащую отношения порядка и равенства. Рассмотрим теорию плотных линейно упорядоченных множеств без первого и последнего элемента, которая включает в себяследующие аксиомы:• аксиомы равенства (в том числе сохранение порядка при заменеэлементов на равные);• ∀x (x 6 x) (рефлексивность порядка);• ∀x∀y∀z ((x 6 y) ∧ (y 6 z) → (x 6 z))(транзитивность порядка);• ∀x∀y ((x 6 y) ∧ (y 6 x) → (x = y))(антисимметричность порядка);• ∀x∀y ((x 6 y) ∨ (y 6 x)) (линейность порядка);• ∀x∃y (y > x) (нет максимального элемента; (y > x) можно считать сокращением для ¬(y 6 x) или для (x 6 y) ∧ ¬(x = y) —при наличии остальных аксиом это одно и то же);• аналогичная аксиома про отсутствие минимального элемента;• ∀x∀y ((x < y) → ∃z ((x < z) ∧ (z < y)) (плотность).Рациональные числа образуют счётную модель этой теории, адействительные — несчётную.
Как мы уже упоминали, эта теориякатегорична в счётной мощности, все её счётные нормальные моделиизоморфны. Отсюда по теореме 65 получаем, что она полна. Следовательно, в ней выводятся все истинные в Q (или в любой другоймодели, в частности, в R) формулы её сигнатуры (в самом деле, изформул ϕ и ¬ϕ ровно одна истинна и ровно одна выводима, и выводимая формула должна быть истинной). Наконец, по теореме 67 этатеория разрешима.178Теории и модели[гл.
5]Другое доказательство тех же фактов даёт элиминация кванторов (теорема 30, с. 93). Как мы отмечали в разделе 3.6, для каждойформулы ϕ нашей сигнатуры существует бескванторная формула ϕ0 ,эквивалентная ϕ в любой нормальной интерпретации теории плотных линейно упорядоченных множеств без первого и последнего элементов. Поэтому эквивалентность ϕ ↔ ϕ0 (с кванторами всеобщности) является теоремой этой теории. Если формула ϕ была замкнутой, то формула ϕ0 будет тождественно истинной или тождественноложной. В первом случае в теории выводима формула ϕ, во второмслучае — её отрицание.
Следовательно, теория полна.Сказанное можно интерпретировать и так: мы доказали конечную аксиоматизируемость теории Th(Q, =, <), предъявив список аксиом.119. Покажите, что эта теория не является категоричной в мощностиконтинуум.Отсюда следует (по теореме Морли), что теория плотных линейноупорядоченных множеств без первого и последнего элемента не будеткатегоричной ни в какой несчётной мощности.120. Не используя теоремы Морли, укажите примеры неизоморфныхплотных линейно упорядоченных множеств заданной несчётной мощности.121. Покажите, что теории Th([0, 1], =, <) и Th([0, +∞), =, <) конечноаксиоматизируемы, полны и разрешимы. Будут ли они категоричными вмощности континуум?122.
Рассмотрим теорию плотных линейно упорядоченных множеств(не добавляя аксиом про наименьший и наибольший элемент). Будет лиона категорична в какой-либо мощности? полна? разрешима?Теория Th(Z, =, S, 0)В этом примере мы действуем в обратном порядке, начав с конкретной интерпретации (целые числа с равенством, функцией прибавления единицы и константой 0) и построив явную систему аксиом. Для этого вспомним процедуру элиминации кванторов из раздела 3.6 (теорема 28). Какими свойствами должна обладать нормальная интерпретация языка, чтобы преобразования, использованныепри элиминации кванторов, были эквивалентными? Помимо аксиомравенства, нам нужно, чтобы функция S была биекцией и чтобы длялюбого x все элементы. .
. , S −1 (S −1 (x)), S −1 (x), x, S(x), S(S(x)), . . .[п. 3]Полные теории179были различны. Другими словами, элиминация кванторов даёт формулу, эквивалентную исходной во всех моделях такой теории:• аксиомы равенства;• ∀x∀y ((S(x) = S(y)) → (x = y));• ∀x∃y (S(y) = x);• ∀x ¬(x = S(x));• ∀x ¬(x = S(S(x)));• ∀x ¬(x = S(S(S(x)))) и т. д.Ограничиваясь замкнутыми формулами, мы (как и в предыдущем примере) видим, что Th(Z, =, S, 0) совпадает с множеством всехформул, выводимых из перечисленных аксиом, так что теория с этими аксиомами полна. Она разрешима (как любая полная теория сразрешимым множеством аксиом; кроме того, явный алгоритм даётся элиминацией кванторов).В отличие от предыдущего примера, эта теория не является категоричной в счётной мощности — например, Z + Z является еёмоделью, не изоморфной исходной.123.
Опишите все модели этой теории.124. Покажите, что она категорична в любой несчётной мощности.Покажем в заключение, что эта теория не является конечно аксиоматизируемой. В самом деле, пусть имеется конечное множествоF теорем этой теории, из которой следуют все остальные теоремы.Каждая из теорем множества F выводима из аксиом, и этот выводиспользует конечное число аксиом.
Это означает, что все остальныеаксиомы (не используемые в выводе формул из F ) вообще лишние.А это не так: в конечной модели, составленной из остатков по модулю N , верны все аксиомы, кроме S N (x) 6= x, S 2N (x) 6= x, . . . , поэтомуэти аксиомы не следуют из остальных.125. Докажите, что использованное нами рассуждение носит общийхарактер: если теория бесконечна, но конечно аксиоматизируема, то некоторая её конечная часть равносильна всей теории (имеет те же теоремы).Теория Th(Z, =, <, S, 0)Что изменится, если мы добавим к сигнатуре, помимо прибавления единицы, ещё и отношение порядка? Как мы видели (см.
доказательство теоремы 29 и задачу после него, с. 92), элиминация кванторов по-прежнему возможна. Для придания законности нам нужны180Теории и модели[гл. 5]такие свойства интерпретации (которую мы предполагаем нормальной): она представляет собой линейно упорядоченное множество, вкотором каждый элемент имеет непосредственно следующий (совпадающий с значением функции S) и непосредственно предшествующий. В отличие от предыдущего примера, нам достаточно конечного набора аксиом. Таким образом, теория Th(Z, =, <, S, 0) конечноаксиоматизируема, а также (как и в предыдущем примере) полна,разрешима, но не категорична в счётной мощности.Можно обойтись и без элиминации кванторов, рассуждая иначе.Рассмотрим теорию линейно упорядоченных множеств со следующим и предыдущим элементом и опишем все её модели.
Именно,мы покажем, что любая нормальная модель M этой теории имеетвид Z × A, где A — произвольное линейно упорядоченное множество (порядок на парах таков: сначала сравниваются A-компоненты,а в случае равенства — Z-компоненты.) В самом деле, будем говорить, что элементы x и y лежат «в одной галактике», если междуними конечное число элементов. (Легко проверить, что это действительно отношение эквивалентности, и наше множество разбиваетсяна галактики.) Далее проверяем, что каждая галактика изоморфна Z (как упорядоченное множество) и что на галактиках естественно определяется порядок.Теперь с помощью игры Эренфойхта (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
