Cтраница 2
Стоит посмотреть, во что переходят дистрибутивные законы для конечных областей при переходе к бескванторным формулам. Законы из задачи 12.8 следуют тогда из коммутативности и ассоциативности конъюнкции и дизъюнкции соответственно. Равносильности в задаче 12.9 не имеют места, так как конъюнкцию и дизъюнкцию, вообще говоря, нельзя переставлять. [16]
Убедитесь, что в самом деле формула у S ( x) не эквивалентна никакой бескванторной формуле этой сигнатуры. [17]
QnXn, где Qi, I i n, - кванторы, а ф - бескванторная формула, находящаяся в ДНФ. [18]
Чтобы не усложнять обозначений, предположим, что ф ( УхЭу) а, где а - бескванторная формула. [19]
Теперь мы можем задать такой рекурсивный предикат, который для любого числа т, являющегося номером какой-либо бескванторной формулы, будет выполняться тогда и только тогда, когда эта формула является результатом какой-нибудь подстановки в некоторую тождественно истинную формулу исчисления высказываний. [20]
Затем, двигаясь изнутри предложения вовне его, последовательно заменяем формулы, получаемые навешиванием квантора существования на бескванторную формулу, коэкстенсивными с ними бескванторными формулами ( в которых не встречаются новые свободные переменные) до тех пор, пока не придем к предложению, не имеющему связанных переменных, т.е. к бескванторному предложению. [21]
Полностью утверждение теоремы звучит так: для всякой формулы сигнатуры, содержащей равенство, порядок и символ S, найдется бескванторная формула той же сигнатуры, которая эквивалентна ей в интерпретации, где носителем является Z, а символы сигнатуры интерпретируются естественным образом. [22]
Итак, мы получили ответ на интересующий нас вопрос: выразимые в арифметике Пресбургера предикаты - это предикаты, выразимые бескванторными формулами, содержащими целые константы, сложение, равенство, отношение порядка и сравнения по любым фиксированным модулям. [23]
Таким образом, чтобы завершить описание процедуры по замене формулы F формулой G, мы должны лишь показать, как найти бескванторную формулу, обладающую тем свойством, что () она коэкстенсивна с данной формулой, полученной навешиванием квантора существования ( по х) из непустой конъюнкции, содержащей не более одного нижнего неравенства s jx ( здесь j 1 и х не входит в s), не более одного верхнего неравенства kx и не более одной конгруэнции вида Dm ( x - i), не содержащей свободных вхождений переменных. [24]
Кроме этих аксиом ( которых счетное число) мы при элиминации ничего не использовали, так что для любой формулы if есть бескванторная формула ip, которая эквивалентна f в любой делимой упорядоченной группе. [25]
Затем, двигаясь изнутри предложения вовне его, последовательно заменяем формулы, получаемые навешиванием квантора существования на бескванторную формулу, коэкстенсивными с ними бескванторными формулами ( в которых не встречаются новые свободные переменные) до тех пор, пока не придем к предложению, не имеющему связанных переменных, т.е. к бескванторному предложению. [26]
WF), те Л, V, где 4я имеет кванторы и находится в виде Qo o Qre-к / гХ, где X - бескванторная формула. Чг / тЧг) ( Чг тЧг /) для того, чтобы утверждать, что XF имеет кванторы. Случай с другим квантором рассматривается совершенно аналогично. [27]
Будем доказывать индукцией по построению ( или, если угодно, по длине) формулы if существование эквивалентной ей в ( Z S, 0) бескванторной формулы. Для удобства ( чтобы рассматривать один случай, а не два) будем считать, что наша формула может содержать только кванторы существования, но не всеобщности. [28]
Мы же, как это обычно делается, будем считать сложение и умножение функциональными символами и тем самым разрешим использовать произвольные многочлены с целыми коэффициентами в бескванторных формулах. [29]
В самом деле, элиминация кванторов преобразует любую формулу ( с параметрами или без) в эквивалентную ей бескванторную, причем эквивалентность имеет место в обоих полях. А для бескванторной формулы ее истинность при оценке со значениями в fci никак не может зависеть от того, внутри какого поля эта истинность вычисляется. [30]