Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 40
Текст из файла (страница 40)
раздел 3.9, теорема 37)мы показываем, что все нормальные модели этой теории элементарно эквивалентны. Отсюда заключаем, что теория полна (как вдоказательстве теоремы 65, где мы по существу использовали элементарную эквивалентность моделей, а не их изоморфизм).126. Покажите, что теория Th(Z, =, <, S, 0) не категорична ни в какойнесчётной мощности.127.
Будет ли теория Th(Z, =, <) конечно аксиоматизируемой? разрешимой? категоричной?128. Будет ли теория Th(N, =, <) конечно аксиоматизируемой? разрешимой? категоричной?Теория Th(Q, =, <, +, 0, 1)Эту теорию мы рассматривали в разделе 3.6, с. 96. Мы ограничимся двумя константами 0 и 1, поскольку любую атомарную формулу можно привести к общему знаменателю и получить целые константы, которые можно выразить через 0 и 1.Мы хотим указать явно набор аксиом этой теории, то есть множество формул, из которых выводятся все теоремы этой теории и[п. 3]Полные теории181только они. Как и в предыдущих примерах, это можно сделать, проанализировав процесс элиминации кванторов и выявив все использованные при этом свойства интерпретации.
(Все рассматриваемыенами интерпретации предполагаются нормальными, а аксиомы равенства изначально включаются в строимую нами теорию.)Прежде всего, нам важно, что по сложению мы имеем абелевугруппу (и 0 является её нулём). Это позволяет в равенствах переносить члены с одной стороны в другую. Для операций с неравенствами нам надо знать, что порядок является линейным и что он согласован со сложением (то есть что из x < y следует x + z < y + z).Кроме того, мы умножали равенства и неравенства на рациональные числа.
Чтобы это было законно, мы должны знать, что группаявляется делимой: для всякого a уравнения x + x = a, x + x + x == a, x + x + x + x = a, . . . имеют решения. (В упорядоченной группетакое решение, как легко показать, единственно.) Наконец, нам надознать, что 1 > 0.Кроме этих аксиом (которых счётное число) мы при элиминацииничего не использовали, так что для любой формулы ϕ есть бескванторная формула ϕ0 , которая эквивалентна ϕ в любой делимойупорядоченной группе. Поэтому любая замкнутая формула, истинная в стандартной интерпретации (в Q), истинна в любой делимойупорядоченной группе, и мы получили счётную систему аксиом длятеории Th(Q, =, <, +, 0, 1).129.
Покажите, что эта теория не является конечно аксиоматизируемой. (Указание: делимость любого элемента группы на простое число pне вытекает из делимости на все меньшие простые числа — рассмотримрациональные числа, знаменатель которых взаимно прост с p.)130. Покажите, что эта теория разрешима.131.
Покажите, что эта теория не является категоричной.132. Покажите, что теория Th(Q, =, +, 0) не является категоричной всчётной мощности, но категорична в любой несчётной мощности. (Указание: её модели — векторные пространства над полем рациональных чисел.)Арифметика ПресбургераВ разделе 3.7 мы занимались элиминацией кванторов в теории(Z, =, <, +, 0, 1), которая потребовала добавления бесконечного числа дополнительных предикатов (сравнимость по модулю N для всехцелых N > 1).Проанализировав это рассуждение, можно извлечь из него явную аксиоматизацию для теории (Z, =, <, +, 0, 1) (без дополнительных предикатов). Какие свойства порядка и сложения на целых чис-182Теории и модели[гл.
5]лах мы используем? Нам важно, что целые числа образуют абелевугруппу, что порядок согласован со сложением и что x + 1 есть непосредственно следующий за x элемент (достаточно, впрочем, сказать,что 1 непосредственно следует за 0). В любой группе можно рассмотреть подгруппу делящихся на N элементов (для любой целойконстанты N > 1) и сравнивать элементы по модулю этой подгруппы. Но этого мало: нам нужно ещё иметь возможность делить наN с остатком. Это гарантируется такой аксиомой (при каждом N —своя аксиома): для любого элемента x ровно один из N элементовx, x − 1, x − 2, . .
. , x − N + 1 делится на N .Можно проверить, что все шаги элиминации кванторов сохраняют равносильность в такой ситуации. Проверим, например, чтосравнения можно умножать на целое положительное число. Почему,скажем, a ≡ b (mod 3) равносильно a + a ≡ b + b (mod 6)? По определению первое означает, что a − b = u + u + u для некоторого u, авторое — что (a − b)+(a − b) = v +v +v +v +v +v для некоторого v, идостаточно сослаться на то, что в упорядоченной группе из x + x = 0следует x = 0 (поскольку из x > 0 следует x + x > x > 0).
Наиболеесложный шаг — доказательство представительности набора. Здесьнадо рассмотреть все случаи расположения произвольного y относительно правых частей. В каждом из случаев мы заменяли y напервый элемент из окрестности правых частей, встречающийся придвижении шагами D (как описано на с. 100). Эту процедуру можно понимать как деление расстояния (до ближайшей правой части)на D с остатком; возможность этого гарантируется нашими аксиомами.133.
Покажите, что теория (Z, =, <, +, 0, 1) разрешима.134. Покажите, что эта теория не категорична в счётной мощности.(Указание: Среди её моделей есть модели вида Z × A, где A — делимаяупорядоченная группа.1 )135. Покажите, что эта теория не конечно аксиоматизируема. (Указание: рассмотрите интерпретацию Z × A, когда в A возможно деление напростые числа, меньшие некоторого p, но не на p.)Алгебраически замкнутые поля характеристики 0Теорема 34 устанавливает возможность элиминации кванторовв поле комплексных чисел. Как мы уже отмечали (теорема 38 на1 В первом издании книги ошибочно утверждалось, что все модели этой теорииимеют такой вид.
Авторы благодарны Евгению Петровичу Бондаренко, которыйобнаружил эту ошибку и указал контрпример.[п. 3]Полные теории183с. 114), это преобразование даёт формулу, равносильную во всех алгебраически замкнутых полях характеристики 0. Отсюда следует,как обычно, что теория алгебраически замкнутых полей характеристики 0 полна. (Её аксиомы таковы: аксиомы равенства, аксиомыполя, счётный набор утверждений о том, что любой многочлен степени n > 0 с ненулевым старшим коэффициентом имеет корень, атакже счётный набор утверждений вида 1 + 1 + 1 + . .
. + 1 6= 0.) Этатеория совпадает с элементарной теорией поля комплексных чисел.Другое доказательство полноты этой теории можно получить спомощью критерия Лося – Воота (теорема 66, с. 176) и утвержденияследующей задачи.136. Покажите, что теория алгебраически замкнутых полей характеристики 0 не категорична в счётной мощности, но категорична в любойнесчётной мощности. (Указание: алгебраически замкнутое поле имеет базис трансцендентности над Q; если поле несчётно, то базис равномощенполю.)137. Покажите, что теория алгебраически замкнутых полей даннойхарактеристики p полна.138. Покажите, что если некоторая формула в сигнатуре (=, +, ×) истинна в алгебраически замкнутых полях характеристики 0, то она истиннаи во всех алгебраически замкнутых полях достаточно большой конечнойхарактеристики.Вещественно замкнутые поляБолее сложно сформулировать, какие свойства поля вещественных чисел реально используются при доказательстве теоремы Тарского – Зайденберга (раздел 3.8).
Дело в том, что мы ссылались наразные факты из анализа (понятие производной, теорема Ролля,асимптотика многочленов). Однако на самом деле достаточно некоторых алгебраических свойств поля — как говорят, поле должнобыть «вещественно замкнутым».Поле называется упорядоченным, если на нём задан линейныйпорядок, причём он согласован со сложением (x < y влечёт x + z <y + z) и умножением (x, y > 0 влечёт xy > 0).139. Покажите, что любое упорядоченное поле имеет характеристику 0и что в нём сумма квадратов не может равняться −1.Упорядоченное поле называется вещественно замкнутым, если любой многочлен, имеющий на концах отрезка разные знаки,имеет корень на этом отрезке. (Отметим в скобках, что существуетнесколько эквивалентных определений вещественно замкнутого поля, см.
учебник ван дер Вардена [4]; мы выбрали наиболее удобное184Теории и модели[гл. 5]для наших целей.)Мы не можем записать определение вещественной замкнутостив виде формулы, поскольку степень многочлена может быть любой.Но можно написать много формул — по одной для каждой степенимногочлена. Например, для многочленов степени 2 получится формула(u < v) ∧ (a 6= 0) ∧ ((au2 + bu + c)(av 2 + bv + c) < 0) →→ ∃x ((u < x) ∧ (x < v) ∧ (ax2 + bx + c = 0)).Теория, состоящая из аксиом упорядоченного поля (в том числеаксиом равенства) и этих дополнительных аксиом, называется теорией вещественно замкнутых полей.
Покажем, что в любом вещественно замкнутом поле выполнены основные факты о многочленахи их производных. Прежде всего заметим, что в алгебре естественноопределять производную многочлена не как предел, а чисто формально: (xn )0 = nxn−1 (для любого положительного целого n), далеепо линейности.
Степень производной многочлена на единицу меньшестепени самого многочлена. Выполнены основные правила дифференцирования (линейность, правило дифференцирования произведения, формула Тейлора).Теперь отметим некоторые свойства многочленов, связанные спорядком. Пусть многочлен в какой-то точке равен нулю, а производная его в этой точке больше нуля. Тогда в некоторой окрестностиэтой точки он положителен справа и отрицателен слева. (В самомделе, можно применить формулу Тейлора и оценки, показывающие,что вблизи нуля знак определяется линейной частью.)Справедливо и свойство сохранения знака: если в какой-то точке многочлен положителен, то и в достаточно близких точках онположителен.
Слова «достаточно близких» понимаются в обычномсмысле (∃ε > 0), только теперь ε — не действительное число, а элемент поля.Аналогичным образом можно сформулировать и доказать такоеутверждение: при всех достаточно больших значениях аргументазнак многочлена определяется его старшим коэффициентом (обычные оценки вполне годятся).Более сложно доказывается, что что если производная многочлена P (x) положительна на интервале (a, b), то он неубывает на отрезке [a, b].
Пусть это не так. Добавив к многочлену константу, можно считать, что для каких-то точек c, d этого отрезка имеют место[п. 4]Неполные и неразрешимые теории185неравенства c < d, P (c) > 0, P (d) < 0 и потому P имеет корень наинтервале (c, d) (вещественная замкнутость).Число корней многочлена (в любом поле) конечно, поэтому средикорней многочлена P (x) на интервале (c, d) есть наименьший кореньα. Слева от α многочлен P должен быть положительным (посколькукорень первый), но одновременно вблизи α и отрицательным (таккак P 0 (α) > 0 по предположению).Теперь легко понять, что многочлен с положительной производной на (a, b) строго возрастает на [a, b]: если бы в двух точках онпринимал одинаковые значения, то между ними он был бы константой (чего не может быть для непостоянного многочлена).Следствие: многочлен, производная которого не имеет корней на(a, b), либо строго возрастает, либо строго убывает на [a, b].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
