1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 21
Текст из файла (страница 21)
,ап-1} с;:_: А1 и {Ьо, ... ,Ьп-1} с;:_: В1;4) если IA11 = 2n + 1, то {ао, ... , ап} с;:_: А1 и при п > О выполняется{Ьо,5)... , Ьп-1}если а Е А1с;:_: В1;-наименьший (наибольший) элемент Qt, тонаименьший (наибольший) элементТак как-1=- !о. Пусть g: А1 ---. В1 принадлежит G3) получаем, что можно выбрать а Е А\ А1,для которого { ао, ... , ап} с;:_: А1 U { а}. Возьмем такой элемент Ь ЕВ\ В1,иIA11 = 2n.что Ь ~ gc!о ЕG,тоga -!13.GИз условияа ~ с для всех с Е А1 и Ь-наименьший (наибольший)элемент в Q3 тогда и только тогда, когда а-наименьший (наибольший){==}элемент в Qt. Такой элемент существует в силу плотности2), 5) для g.
Ясно, что g U { (а, Ь)} Е G. Если IA11местами Qt икоторой gгде с;:_: -вG!13,Q3= 2n + 1,точно так же можно найти паруи условийто, поменяв(а, Ь)(j g,дляU { (а, Ь)} Е G. Следовательно, в частичном порядке (G, с;:_:),отношение включения, нет максимальных элементов. Тогдасуществует бесконечная цепь Х с;:_:G.Из условий2)-4)что объединение элементов Х будет изоморфизмом Qt на!13.следует,ОУпражнения1.Показать,натурычто любая алгебраическая система Qt счетной сигI; имеет счетную или конечную подсистему Q3 с;:_: Qt(Указание. Определим не более чем счетные множества Вп, п ЕЕw, следующим образом: Во={а}, где а Е А, Вп+l= Вп U {Ь I Ьявляется значением операции системы Qt на элементах множе-99§ 3.2.
Формулы сигнатуры ~ства Вп}. Тогда в качестве носителя Q3 можно взять множествоВ=UВп.)nEw2.Пусть сигнатура Е системы 2( содержит хотя бы один символконстанты, иS(2t) обозначает множество подсистем системы 2t.(S(2t); ~). где (Q3,, Q3z) Е ~ ~ Q3, ~ Q3z, являрешеткой (см. § 2.2).Тогда системается3.Пусть система 2( имеет собственную изоморфную себе подсистему. Тогда 2( имеет собственную изоморфную себе надсистему.4.Показать, что системаа система5.(N;:..) -Показать, что еслиимеет счетное число подсистем,(N; +)несчетное.IEI < w, то для любого п Е w существует такоеконечное множество Х систем сигнатуры Е, что любая системасигнатуры Е, имеющая мощность п, изоморфна одной из системмножества Х.6.Чему равна минимальная мощность множества Х из упражнения7.5,если Е содержит лишьkЕ w одноместных предикатов?Показать, что биективный гомоморфизм:h:А_,.
В системы2tнасистему Q3 функциональной сигнатуры Е является изоморфизмом2( на Q3. Построить пример, показывающий, что условиеR = 0на сигнатуру Е в этом утверждении опустить нельзя.§ 3.2.Формулы сигнатуры 'ЕЗафиксируем некоторое счетное множествоV = {viIiЕw},элементы которого будем называть символами переменных или простопеременными и обозначать буквами х, у иz,возможно, с индексами.Если в тексте встречается последовательность хо,то всегда предполагается, что Xii:-Xj дляi... , Хппеременных,#- j.Определение.
Множество Т(Е) термов сигнатуры Е= (R, F, µ)определяется по индукции:1)2)переменные х ЕVявляются термами сигнатуры Е;еслиt,, ... , tn - термы сигнатуры. . . , tn) - терм сигнатуры Е.Напомним, что запись 0(т1,ности, из2)... , тп)Е,fпри пЕ=Fиµ(!)= п, тоО обозначает0;f(t,, ...в частполучаем, что символ с константы сигнатуры Е являетсятермом сигнатуры Е.Таким образом, термы- это слова (конечно, не все слова) алфаV U F U {(, )} U {, }.
Множество переменных, входящих в терм t,обозначаем через FV(t). Если FV(t) = 0, то терм t называется конвитастантным или замкнутым. Если4*t -терм сигнатуры Е, то записьГл.1003.Истинность на алгебраических системахбудет обозначать, чтоt(x1, ... ,xn)также будем называть термомОпределение.
ПустьОтображениеVв21при интерпретацииl) если t2) если tЯсно,... ,хп}-Эту записьв А называется интерпретациейпеременных множества Х в А. Если:Е, то индукцией по длине~ {х1,алгебраическая система сигнатуры :Е.21 -множества Х ~IFV(t)1).FV(t)~ Х для термаtсигнатурыопределяем значение t 21 [,] Е А термаtt1:= х, х Е Х, то t 21 [,] = 1 х;= f(t1, ... , tп), f Е F, то t 21 [1 ] = v 21 (f)(tr[,], ... , t~[1 ]).- две интерпретаFV(t) = ,2 ~ FV(t), тоt 21 [,1] = t 21 [,2]. Часто для краткости вместо t 21 (x1, ...
, хп)[,], мы будем писать t 21 (a1, ... , ап), где а1 = 1 (х1 ), ... , ап = 1 (хп). Если в тексте встречается запись t(x1, ... , хп), то следующая за этим записьt 21 (a1, ... , ап) будет обозначать t 21 (x1, ... , хп)[,], где I определяется так:,xi = ai, i = 1, ... , n.ции,tчтоесли,1: Х1 ---+ А, ,2: Х2FV(t) ~ Х1 n Х2 и ,1Е Т(:Е),Предложение3.2.l.а). Если---+ А~алгебраическая система сигна21 -туры :Е, Х ~ А, Х ,f. 0, то носитель А(Х) подсистемы ЩХ) равенмножеству {t21 [1 ] 1 t Е Т(:Е), ,: FV(t)---+ Х}.6).Еслигомоморфизм алгебраической системыh-:Ев систему SВ, t(x1, ...
,xn) Е Т(:Е) и а1,... , ап)) = t'В(ha1, ... , hап)-21сигнатуры... ,ап Е А, то h(t 21 (aI,···До каз а тел ь ст во. а). Пусть У={t21 [,] 1 t Е Т(:Е), 1 : FV(t)---+получаем, что если t(x1, ...... ,хп) Е Т(:Е) и а1, ... ,ап Е Х, то t 21 (a1, ... ,an) ЕВ для любой под---+ Х}.Индукцией по длине термасистемы SВ ~21,tдля которой Х ~ В. Поэтому достаточно показать,что У замкнуто относительно операций системы21.Пустьµ(!) = т, t1, ...
, tm Е Т(:Е) и ,: (FV(t1) U ... U FV(tm))v 21 (f)(tr[,], ... , t~[,]) .= tl[,] Е У, где to = f(t1, ... , tп).6). Легко доказывается индукцией по длине t.Определение. МножествоF(:E)---+формул сигнатуры :ЕfЕF,Х. ТогдаО= (R, F, µ)определяется по индукции.О). Логическая константаl).ЕслиrЕR, µ(r) = nJиявляется формулой.t1,,.,,tnЕ Т(:Е), то словоr(t1, .. ,,tn)является формулой сигнатуры :Е.2).Еслиt1, t2Е Т(:Е), то словоt1~t2является формулой сигнатуры :Е.1)Эта запись, конечно, как и буква t, не является термом, а представляетсобой обозначение («имя~) терма.§ 3.2.Если Ф,3).-101\J! - формулы сигнатуры Е, то (Ф /\ Ф), (Ф V Ф), (Ф - формулы сигнатуры Е.Ф) и ~ФЕсли Ф4).Формулы сигнатуры Е-формула сигнатуры Е, х ЕV,то \iхФ и :3хФ-формулысигнатуры Е.Таким образом,множествоиз некоторых слов алфавитаформулF(E)сигнатурыV U R U F U {J, /\, V, -, ~,U {(,)} U {,}.
Например, еслиµ(!) = 1, µ(с)= 0, ТО СЛОВОr ЕR,f,g,c ЕF,Е состоит:::о}=µ(r)U {\i, :3} Uµ(g) = 2,(\iv1:Jv2r(v2, J(vз)) V ~V4 :=:о g(v1, с))является формулой сигнатуры Е, в то время как словаформулами сигнатуры Е не являются (почему?). При этом последнееслово является формулой, только другой сигнатуры.Последовательность Ф некоторых символов будем называть простоформулой, если она является формулой некоторой сигнатуры. ЕслиФформула, то через Е(Ф) будем обозначать сигнатуру, все символы-которой входят в Ф, и Ф является формулой сигнатуры Е(Ф).
Ясно, чтоЕ( Ф) определяется по Ф однозначно.Подслово формулы Ф, которое само является формулой, называетсяподформулой формулы Ф. Формулы видаr -предикатный символ,t1, t2, ... -J, r(t1, ... , tn)и t1 :::о t2, гдетермы, называются атомарными. Атомарные формулы, содержащие не более одного сигнатурногосимвола, называются атомными. Таким образом, атомная формуласигнатуры Е имеет один из следующих видов:J,где с-vi::::oVj, c:=:ovi, vi:=:oc, vj:=:of(vio,···,viJ,константа,f -функциональный символ, аr -предикатный символ сигнатуры Е.
Символ :::о называется символом равенстваили просто равенством. Символы \i и:3называются соответственнокванторами всеобщности и существования. Запись \ix (запись :3х)читается «для всех Х•> ( «существует Х•>). Формулу, не содержащуюкванторов, будем называть бескванторной.Доказательство следующих трех предложений является по существу повторением доказательств предложений1.2.31.2.1, 1.2.4и следствиясоответственно. (Рассмотрение случаев, когда формула начинается с кванторов, не отличается по существу от рассмотрения в указанных предложениях случая, когда формула начинается с отрицания.)Гл.102Предложение3.Истинность на алгебраических системах3.2.2.Всякая неатомарная формула сигнатуры I;представuма в одном и только одном следующих видов:(\J! /\ Х),(ФV Х),(Ф ---t Х),для однозначно определенных формулПредложение3.2.3.Если Фвхождения в Ф подформул\J1-\J1\ix\J!, :Jx\J!,~i:r,и Х сигнатурыОI:.формула сигнатуры I; а 'Г/ и0 -и Х соответственно, то либо 'Г/ и0не имеют общих вхождений символов, либо одно из них целикомсодержится в другом.Предложениетуры I; символовО3.2.4.
С каждым вхождением в формулу Ф сигна~, \i или :3, а также символа (, не входящего ватомарную подформулу, однозначно связано некоторое вхождениеподформулы формулы Ф, первым символом которого является рассматриваемое вхождение соответствующего символа.Определение. Подформула формулы Ф сигнатурыпредложению3.2с вхождением квантораVI:,(квантораобластью действия этого вхождения квантора\iОсвязанная по:3),называется(квантора:3).Мы будем в дальнейшем пользоваться соглашением об опусканиивнешних скобок, принятом в§ 1.2гл.1.Заметим, что формулу исчисления высказываний можно рассматривать как формулу некоторойсигнатуры, если считать, что символы пропозициональных переменныхявляются нульместными предикатными символами.Определение. Для каждой формулы Ф сигнатуры I; определиммножество FV(Ф) свободных переменных формулы Ф следующимобразом:1). Если Ф -атомарная формула вида J,r, r(t,, ...
,tn) или t, ~t2, то множество FV(Ф) равно 0, 0, FV(ti), U ... U FV(tn) илиFV (t,) U FV (t2) соответственно.2). Если Ф = ~i:r,, то FV(Ф) = FV(\J!).3). Если Ф = Ф1тФ2, где т Е {/\, V,---+}, то FV(Ф) = FV(Ф1) UU FV(Ф2).4). Если Ф = Qx\J!, где Q Е {V, :3}, то FV(Ф) = FV(\J!) \ {х}.~Ясно, что для любой формулы Ф через конечное число шагов можнонайти все элементы FV(Ф). Вхождение 'Г/ переменной х в формулуФ сигнатуры I; будем называть связанным, если 'Г/ лежит в областидействия некоторого вхождения квантораVили:3,за которым сразуследует символ х.
Если вхождение 'Г/ переменной х в формулу Ф неявляется связанным, то будем его называть свободным. Если формулаФ содержит свободные (связанные) вхождения переменной х, будемговорить, что х входит свободно (связанно) в формулу Ф.§ 3.2.Предложение3.2.5.Формулы сигнатуры ЕЕсли Ф-103формула сигнатурыменная х тогда и только тогда принадлежитFV (Ф ).I:,то перекогда существует свободное вхождение х в Ф.До к аз ат ель ст в о легко проводится индукцией по длине Ф, и мыоставляем его читателю.Если Ф-Dформула, то запись Ф(х1,... , хп)значать формулу Ф, а также то, что FV(Ф)в дальнейшем будет обо<;;; {х1, ... ,хп}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
