1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 22
Текст из файла (страница 22)
Определимглавное понятие этой главы.Определение. Для алгебраической системыпретации переменных ,у: ХFV(Ф)2tсигнатурыА и формулы Ф Е---.<;;; Х, определим отношение 2t1= Ф[,]F(I:),(читается <<вI:,интердля которой2tистиннаформула Ф при интерпретации,•>) индукцией по длине Ф.О). Если Ф= J,1). Если Ф= r, r Е R, µ(r)1= Ф[,J не имеет места.= О, то 2t 1= Ф[,J эквивалентно z;'-21(r) -=f. fZ5.то отношение2t2). Если Ф = r(t1, ... , tn), r Е R, µ(r) = n, t1,, ...
, tn Е T(I:), то2t 1= Ф[,] эквивалентно (t?[,J, ... , t~[,J) Е v 21 (r). 1)3). Если Ф равна t1 ~ t2, t1, t2 Е T(I:), то 2t1=Ф[,J эквивалентноt?[,J = t~[,J.4). Если Фчто2t7).8).9).~i:r,, то2t1= Ф[,]тогда и только тогда, когда неверно,2t 1= Ф[,] {с=} (2t 1= Ф1 [,] и 2t 1= Ф2[,]).Если Ф = (Ф1 V Ф2), то 2t 1= Ф[,] {с=} (2t 1= Ф1 [1 ] или 2t 1= Ф2[,]).Если Ф = (Ф1 ---.
Ф2), то 2t 1= Ф[,J {с=}(если имеет место2t 1= Ф1 [,], то имеет место и 2t 1= Ф2[,]).Если Ф = :JхФ, то 2t 1= Ф[,] имеет место тогда и только тогда,когда существует такая интерпретация ,1: Х1 ---. А для которойх Е Х1, 1 1 1FV(Ф)= 1 1 FV(Ф) и 2t 1= Ф[,1].Если Ф = \ix\J!, то 2t 1= Ф[,J имеет место тогда только тогда, когда5). Если Ф6).=1= Ф[,].=(Ф1 Л Ф2), тодля любой интерпретации1FV(Ф) = 1 1FV(Ф),,1,1: Х1 ---.
А, для которой х Е Х1, и2t 1= Ф[, 1 ].имеет местоЕсли формула Ф не является истинной в алгебраической системепри интерпретацииической системе2t1,2tто говорим, что формула Ф ложна в алгебрапри интерпретации1.В частности, формулаJложна в любой алгебраической системе при любой интерпретации.1)Конечно, 2) включает 1), так как мы договорились считать r(t 1 ,равнымrпри п=О. Мы здесь включилинульместных предикатов.1),••• ,tn)чтобы подчеркнуть спецификуГл.1043.Истинность на алгебраических системахИз этого определения видно, что при установлении истинности формулы Ф сигнатуры Е свободные и связанные вхождения переменныхв формулу Ф играют совершенно различные роли. А именно, свободнымвхождениям переменной х <<приписывается» постоянное значение 1'(х ),втоныевремякаксвязанным вхождениямзначения не<<приписываются»,апеременных никакиерассматриваютсяпостоянвсевозможныеих значения.Предложениетуры Е и Ф Е3.2.6.Пусть Qt -тации, для которых FV(Ф) ~ Х1то Q(F Ф[1'1]алгебраическая система сигнаF(E).
Если 1'1: Х1 ---. А, 1'2: Х2 ---. А - две интерпре~ QtF Ф[1'2].n Х2и1'1 1FV(Ф)= 1'2 1FV(Ф),До к аз ат ел ь ст в о легко проводится индукцией по длине Ф.Мычасто будемиспользовать вместо QtFFФ(х1,D... , хп)[1']бо-лее удобную запись QtФ(а1, ...
,ап), где а1 = 1'(х1), ... ,ап = 1'(хп)А именно, если в тексте встречается запись Ф(х1, ... , хп), то следуюFщая за этим запись QtФ( а1, ... , ап), а1, ... , ап Е А, будет обозначать,QtФ(х1, ... ,хп)[1'], где 1' определяется так: ,'Xi = ai, i = 1, ... ,п.FВ силу предложения3.2.6такое сокращение возможно.Определение. Если Ф -формула сигнатуры Е и FV(Ф)= 0,то Фназывается замкнутой формулой или предложением.Если Ф-предложение сигнатуры Е, Qt -то отношение QtFсистема сигнатуры Е,Ф[1'] не зависит от интерпретации 1', и мы егобудем обозначать просто QtФ.
Ясно также, что если для формулы Ф,Fсистемы Qt и интерпретацииQtF Ф[,']равносильно Qt1'определено отношение QtI Е(Ф) F Ф[,,J.FФ[1'], тоОпределение. Формула Ф называется тождественно истиннойили общезначимой, если QtF Ф[1']для любой системы Qt сигнатурыЕ(Ф) и любой интерпретации т FV(Ф)---.А. Ясно, что сигнатуруЕ(Ф) в этом определении можно заменить на любую Ежество формул У ~натуры Е, если существует такая интерпретация тF:2Е(Ф). МноF(E) называется выполнимым в системе Qt сигUFV(Ф)---.А,ФЕУчто QtФ[1'] для всех Ф Е У.
Формула Ф называется выполнимойв системе Qt, если множество { Ф} выполнимо в Qt.Понятие истинности формулы в системе наряду с понятием выводимости принадлежит к основным понятиям математической логики.Важность этого понятия объясняется тем, что многие теоремы математики можно выразить как утверждения об истинности некоторыхформул в алгебраических системах из некоторого класса. В отличиеот свойств «быть формулой» и <<быть тождественно истинной формулой§ 3.2.Формулы сигнатуры ~105ИВ,>, в общем случае не существует эффективного способа, позволяющего для предложения Ф за конечное число шагов установить, верноли Qt1=Ф. Это связано с тем, что при бесконечном А пунктыи 9) требуют проверки бесконечного числа условий8)Пункты 2) и 3)1).в общем случае также не «эффективны», так как предикаты и функциибесконечной системыQt могут быть заданы не <<эффективно,>.Установим теперь достаточно простой, но важный факт.Предложениетуры3.2.
7.f -Пустьизоморфизм системыQt сигна... , xn) - формула сигнатуры I:,то для любых а 1, .•. , an Е А свойство Qt 1= Ф ( а 1 , ... , an) равносильносвойству SВ 1= Ф(fai, ... , fап)- В частности, если Ф - предложение,то QtI:на систему SВ. Если Ф(х1,1= Ф равносильно SВ 1= Ф.До к аз ат ель ст в о легко проводится индукцией по длине термаи формулы длине Ф. Если Фtатомарная формула, то утверждение-следует из определения изоморфизма и предложенияб). Индук3.2.1ционный шаг оставляется читателю в качестве упражнения.DВ отличие от бесконечных систем, проверку истинности формулы Фна конечной системе Qt сигнатуры I:(Ф) можно осуществить за конечное число шагов.
Это легко показать индукцией по длине Ф.Определение.Пусть п Е (;.),п-общезначимым, если Qt1= Фn>О.Предложение Фназываетсядля любой алгебраической системы Qtмощности п и сигнатуры I:(Ф).Предложение3.2.8.Существует эффективная процедура (алгоритм), позволяющая для любого п Е (;.),n >О, и любого предложения Ф за конечное число шагов установить, является ли Фn-общезначимым или нет.До к аз ат ел ь ст в о. Очевидно, что для конечного множества Хмножества Р(Х) и хп, п Е (;.), конечны. Поэтому для любой конечной сигнатурыI:имеется лишь конечное число систем сигнатурыI:с конечным носителем Х.
Тогда процедура проверки n-общезначимостисведется к выписыванию всех систем сигнатуры I:(Ф) с носителем{ 1, 2, ... , п} и проверке истинности Ф на каждой из выписанных систем. Такая проверка, как отмечалось выше, осуществляется за конечное число шагов.DМожно определить аналогично n-общезначимости, О< п < (;.),понятие х-общезначимости формулы Ф для бесконечного кардинала х. Какбудет показано в1)5.1,эти понятия для всех бесконечных кардиналов хВ главе 7 будет показано, что эту трудность нельзя обойти.Гл.1063.Истинность на алгебраических системахсовпадают.
Какие еще зависимости существуют между этими поня~тиями? Как будет показано в следующем параграфе, если предложение Ф бесконечно общезначимо, то существует такое число по Е (.с), чтоФ является k-общезначимым для любого>kпо. Из n-общезначимостипредложения Ф для любого п Е (.с), п -=/= О, в общем случае не следует(упражнение4)общезначимость Ф. Отметим простой факт.ПредложениеДля любого п Е (.с), п ~3.2.9.существует та1,=(.0, .0, .0)),~Фпявляетсякое предложение Фп пустой сигнатуры :Ео (т. е.
:ЕодлякоторогоФпявляетсяk-общезначимым для любогоп-общезначuмым,-=/= п,kk~а1.До к аз ат ель ст в о. В качестве Фп можно взять предложение3v1 ... 3vп(Cv1:=:оv2Л Гv1 :=:о Vз Л(...ЛФормула\iv1 \iv2 (Р( vi)Л:=:о~Vn-1\ivo(vo:=:оVn) ... ))Лvi V ( ... V vo :=:о vn) ... )).О-+ Р( v2)) не содержит символов равенстваи функций, является 1-общезначимой и не является n-общезначимойдля п> 1.Легко строятся (упражнениеравенства и функций,>и не являющаяся m-общезначимой для тФп из предложениятакже формула Фп, без3)являющаяся k-общезначимой для О3.2.9< k :,;; nп.
Построить формулубез равенства и функций нельзя в силуследующего факта (упражнение5):если предложение Ф не содержитсимволов равенства и функций, то из n-общезначимости Ф следуетk-общезначимость Ф для любогоk :,;; п, k-=/= О.Упражнения1.Показать,чтодлялюбойконечнойсигнатуры:Есуществуетпроцедура, позволяющая по любой конечной последовательностисимволов определить, является ли она формулой сигнатуры :Е илинет.2.Пустьh-гомоморфизм системы Qt сигнатуры :Ев систему SВ.
Тогда для любой атомарной формулы Ф(х1,а1,3.... , апЕ А имеем Q(1= Ф(а1, ... , ап)... , хп)==}SВЕF(:E) и любых1= Ф(hа1, ... , hап)-Показать, что следующая формула Фп является k-общезначимойтогда и только тогда, когда1 :,;:; k :,;; n:3v2 ... 3vn+l \ivo(\iv1 (r( v2, vi)-+r( vo, v1) )VV ( ... V\iv1(r(vп+1,v1)-+ r(vo,v1)) ... )).4. Показать, что следующая формула является n-общезначимой длялюбого п Е (.с), п -=/= О, и не является общезначимой:3vo\iv1 ~f(v1):=:оvo-+ 3vo3v1 (f(vo):=:оf(v1)Л~vo:=:оv1).Теорема компактности§ 3.3.5.<k <Пусть Оп<LtJ,107предложение Ф n-общезначимо, не содержит симвQлов равенства и функций. Тогда Ф k-общезначимо.(Указание.
Пусть Qtс носителемF ~Ф,{ 1, 2, ... , k}.где Qt -система сигнатуры :Е(Ф)Строим системуопределяя на множестве В= {1, 2, ... , п}113 2 Qtмощности п,предикатыrсигнатуры:Е(Ф) следующим образом:(it, ... , im) Е z/B(r)где~в=ij8F ~Ф.)если8 ,§ 3.3.i8~{=}=k, j 8k(j1, ...в,jm) Е v2t(r),противном случае.ТогдаТеорема компактностиТеорема компактности была доказана А. И. Мальцевым в1936г.Он же впервые показал ее важное значение как нового метода длядоказательства не только теорем математической логики, но и теоремалгебры. Мы дадим доказательство этой теоремы с помощью ультрапроизведений, введенных Е.
Лосем в1955 г.S = {XiIiПусть дано семейство множествпроизведением семействаI-prodXiSЕI}.Декартовымназывается множество= {f: I---+UXi I fi Е Xi }·iEIДляjЕIэлементуотображение множестваэлементff(j),I-prod XiвXj,сопоставляющееназывается проекцией декартова произведеj, т. е.
f(j) = j(f).I-prodXi отношениения на j-ю координату и обозначается той же буквойПусть наIзадан фильтрОпределим наD."' D следующим образом:frvDgЛемма{=}3.3.1. Отношение "'{ilfi=gi}ED.Dявляется эквивалентностью наI-prodXi.До к аз ат ель ст в о. Рефлексивность и симметричность "' D очевидна. Пусть f "' D g и g "' D h. Тогда множество У = {i I fi = hi}содержит пересечение множествщихся элементамичаем У ЕD.{i I f i = gi} и {i I gi = hi}, являю2) и 3) определения фильтра полуDИз условийD.Отображение, сопоставляющее элементуfЕI-prod Xiкласс эквивалентности по отношению "'D, содержащий f, будем обозначать тойже буквойD,что и фильтр. МножествоD-prodXi= {Df I fЕI-prodXi}называется фильтрованным произведением множествфильтруD.Xi, iЕI,поГл.1083.Истинность на алгебраических системахОпределение. Фильтрованным произведением по фильтруD се{Qti I i Е J} сигнатуры Е называется алгебраическая система Q( = D-prodQti, сигнатуры Е с носителемА = D-prod Ai, и следующей интерпретацией v 21 сигнатуры Е в Qt.1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
