Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 41
Текст из файла (страница 41)
В самомделе, свойство вещественной замкнутости можно применить и к производной, следовательно она либо всюду положительна, либо всюдуотрицательна. В частности, справедлива теорема Ролля (многочленс равными значениями на концах отрезка имеет нуль производной).После такой тренировки наши рассуждения про знаки многочленов диаграммы легко провести для произвольного поля. Легкопонять также, что деление с остатком (точнее, операция модифицированного остатка) имеет смысл для любого поля, и что целыечисла (которые были коэффициентами многочленов) содержатся влюбом поле.Итак, элиминация кванторов даёт формулу, равносильную исходной в любом вещественно замкнутом поле. Отсюда, как обычно,следует, что теория вещественно замкнутых полей совпадает с элементарной теорией упорядоченного поля вещественных чисел и потому полна, а также разрешима, и что все вещественно замкнутыеупорядоченные поля элементарно эквивалентны.5.4.
Неполные и неразрешимые теорииПредыдущий раздел мог создать впечатление, что наугад взятаятеория скорее всего окажется полной, разрешимой, а возможно, иконечно аксиоматизируемой. Это совсем не так.Откуда вообще берутся в математике аксиоматические теории?Иногда мы пытаемся построить аксиоматически теорию какой-токонкретной структуры (скажем, теорию действительных чисел сосложением и умножением). В других случаях мы стараемся выделить общие свойства различных структур.
Например, аксиомы груп-186Теории и модели[гл. 5]пы фиксируют общие свойства различных групп, и с самого началаясно, что такая теория не должна и не может быть полной. То жесамое можно сказать и про теорию линейно упорядоченных множеств — полнота такой теории означала бы, что все линейно упорядоченные множества (или группы) элементарно эквивалентны, тоесть обладают одними и теми же свойствами, выражаемыми формулами.
Это, конечно, не так.Что касается конкретных структур, то и для них естественныетеории не всегда оказываются полными. Классический пример —натуральные числа со сложением и умножением. Для них имеетсяестественная формальная теория (называемая формальной арифметикой). Её аксиомы включают в себя обычные свойства сложения иумножения, а также аксиомы индукции. Опыт показывает, что любое рассуждение теории чисел, в котором речь идёт только о конечных объектах, может быть формально записано в виде вывода из аксиом этой теории. Более того, многие доказательства, использующиебесконечные объекты (скажем, важнейшую в теории чисел ζ-функцию Римана), могут быть модифицированы и погружены в эту формальную теорию.
Тем не менее эта теория неполна (и не может бытьполна, как мы увидим в этом разделе).Среди естественных неполных теорий бывают разрешимые и неразрешимые. Например, теория линейно упорядоченных множествразрешима, теория абелевых групп разрешима, а теория групп неразрешима. Подробный рассказ об этом далеко выходит за рамкинашей книжки; написанный М. О. Рабином обзор соответствующихрезультатов можно найти в справочнике по математической логике(часть III, Теория рекурсии [26], глава 4).Мы же ограничимся тремя примерами (теория равенства, теорияполугрупп, формальная арифметика).Теория равенстваРассмотрим сигнатуру, содержащую единственный двуместныйпредикат равенства, и теорию, состоящую из трёх аксиом равенства(рефлексивность, симметричность и транзитивность).
Эти аксиомырассматривались в разделе 5.1; заметим, что у нас нет других предикатных и функциональных символов (и связанных с ними аксиомравенства).Моделями этой теории являются всевозможные множества с отношениями эквивалентности. Нормальными моделями этой теорииявляются множества различной мощности; поскольку никакой до-[п. 4]Неполные и неразрешимые теории187полнительной структуры нет, такая модель определяется мощностью(с точностью до изоморфизма). Теоремами этой теории будут формулы с равенством, истинные в множествах любой мощности.Теорема 68. Множество теорем теории равенства является разрешимым.
Заметим, что истинность формулы в нормальной модели можетзависеть от её мощности. Например, формула ∃x∃y¬(x = y) ложна в одноэлементной модели и истинна во всех остальных. Поэтомупроцедура элиминации кванторов в чистом виде (без расширениясигнатуры) здесь неприменима.Но идея остаётся той же. От чего зависит истинность формулы этой сигнатуры (с параметрами)? Во-первых, от значений параметров (важно, какие параметры равны друг другу, а какие нет).Во-вторых, от числа элементов модели. (Если бы этой зависимостине было, то можно было бы написать бескванторную формулу, эквивалентную данной во всех моделях теории.)Например, формула ∃z (¬(z = x) ∧ ¬(z = y)) при x = y истиннаво всех моделях, начиная с двухэлементной, а при x 6= y истиннаво всех моделях, начиная с трёхэлементной.
Можно ожидать, чтомодели с большим числом элементов неотличимы друг от друга и отбесконечных моделей.Лемма. Истинность формулы языка с равенством, содержащей kпараметров и имеющей кванторную глубину l, определяется тем, какие из параметров равны друг другу, а также мощностью носителя,при этом все мощности, большие k + l, одинаковы.Докажем лемму с помощью индукции по построению формулы.Для атомарной (и вообще для любой бескванторной) формулы мощность вообще не играет роли. Если утверждение леммы верно дляформул ϕ и ψ, то оно очевидным образом верно и для ϕ ∧ ψ, ϕ ∨ ψ,ϕ → ψ и ¬ϕ.
При этом используется такой факт: кванторная глубина(число вложенных кванторов) и число параметров у части формулыне больше, чем у всей формулы.Содержательный случай — когда формула начинается с квантора. Когда, скажем, формула∃xϕ(x, x1 , . . . , xk )с параметрами x1 , . . . , xk будет истинной (в данной интерпретациипри данных значениях параметров)? Достаточно попробовать в качестве x значения x1 , . . . , xk а также какой-нибудь элемент, отлич-188Теории и модели[гл. 5]ный от всех этих значений. (Все такие элементы ничем не отличаются.) Истинность формулы ϕ(x, x1 , .
. . , xk ) при x = xi определяется соотношениями между параметрами и мощностью модели (попредположению индукции; заметим, что число параметров увеличилось на 1, а кванторная глубина уменьшилась на 1, так что суммаосталась прежней). Существование элемента, отличного от всех xi ,определяется мощностью модели и числом различных элементов среди x1 , .
. . , xk (то есть в конечном счёте равенствами вида xi = xj ).При этом модели всех мощностей, начиная с k + 1, ведут себя одинаково. Кроме того, истинность формулы ϕ(x, x1 , . . . , xk ) при x ∈/∈/ {x1 , . . . , xk } по предположению индукции также определяется равенствами вида xi = xj и мощностью модели.Квантор всеобщности рассматривается точно так же (а можно еговыразить через квантор существования и вообще не рассматривать).Лемма доказана.Доказательство леммы конструктивно, то есть указывает способузнать, будет ли формула истинной, если известно, какие её параметры равны и какова мощность носителя. В частности, для замкнутыхформул получаем способ проверять их истинность для всех значениймощности, то есть выводимость в теории равенства.
140. Рассмотрим теорию, в сигнатуре которой есть равенство и конечное число одноместных предикатных символов, а аксиомами являютсяаксиомы равенства (включая устойчивость предикатов относительно равенства, как в разделе 5.1). Покажите, что эта теория разрешима.(Указание. Можно провести элиминацию кванторов, добавив к сигнатуре счётное число нульместных предикатных символов помимо уже имеющихся одноместных предикатных символов P1 , .
. . , Pn . А именно, длякаждого n-битового слова z и для каждого натурального k мы добавляем утверждение о том, что существует ровно k элементов x, для которых(P1 (x), . . . , Pn (x)) равно z.)Эта задача показывает, что добавление одноместных предикатовв сигнатуру не делает теорию равенства неразрешимой. Отметим,что расширение сигнатуры (без изменения множества аксиом) может превратить разрешимую теорию в неразрешимую: например,добавив конечное число одноместных функциональных символов ктеории равенства, получим неразрешимую теорию (как мы вскореувидим, доказывая теорему Чёрча с помощью проблемы тождествадля полугрупп, с. 191). Добавление одного двуместного предикатного символа также даёт неразрешимую теорию.[п.
4]Неполные и неразрешимые теории189Теория полугруппНаш второй пример — теория полугрупп. Её сигнатура состоитиз равенства и единственного двуместного функционального символа, называемого умножением; результат умножения x и y мы будемобозначать (xy).Теория состоит из аксиом равенства (в них входит корректностьумножения: (x1 = x2 ) ∧ (y1 = y2 ) → (x1 y1 = x2 y2 ); мы опускаемвнешние кванторы всеобщности) и аксиомы ассоциативности∀x∀y∀z ((xy)z = x(yz)).Нормальные модели этой теории называются полугруппами.Теорема 69.
Множество теорем теории полугрупп (то есть множество замкнутых формул указанной сигнатуры, истинных во всехполугруппах) неразрешимо. Нам понадобится конкретный способ задания полугрупп с помощью образующих и соотношений. Пусть фиксировано некотороеконечное множество, называемое алфавитом. Элементы его называют буквами, а конечные последовательности букв — словами (данного алфавита). На словах определена операция соединения (приписывания), относительно которой они образуют полугруппу, котораяназывается свободной полугруппой.
Эта полугруппа имеет нейтральный элемент — пустое слово, приписывание которого к любому словуне меняет последнего.Пусть фиксирован алфавит A, а также конечное число пар слов(X1 , Y1 ), . . . , (Xn , Yn ) этого алфавита. Два слова алфавита A назовёмэквивалентными, если одно можно превратить в другое, многократно делая замены подслов вида Xi ↔ Yi . Легко проверить, что получается отношение эквивалентности и что операция приписываниякорректно определена на классах эквивалентности и ассоциативна.Получается полугруппа. Её называют полугруппой с образующимииз A и соотношениями Xi = Yi .141.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
