Языки и исчисления

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


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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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



Содержание раздела