1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 20
Текст из файла (страница 20)
Элементы множестваили арности для :Е.R UFFназываются символами операцийназывается отображением местностиµ(q) =qЕ Rп, тоqназывается п-местными п-местным функциональнымО-местный функциональный символ называетсясимволом константы или просто константой.Часто для удобства будемсигнатуру :Е= (R, F, µ)представлять конечнуюили счетнуюв виде:Е = (rj(r1), ...
, r~(rп), ... ; Jj(fi), ... , Jf(Jk),... ; С\' ... 'Ст, ... )или просто~ == (r1, • ··, Тп, • · ·; ft, · · ·, fk, · · ·; Ct, ···,Ст,··.),где ri,fi -тами, Ck -символы отношений и функций, не являющихся констанконстанты сигнатуры :Е. Все сигнатуры в дальнейшем будутобозначаться буквой :Е (возможно, с индексами), множество их символов отношений-черезR,множество символов операций-черезF,94Гл.Истинность на алгебраических системах3.а отображение арностичерез-µ(с соответствующими индексами).Будем говорить, что сигнатура Е содержится в сигнатуре Е 1 (обозначаем Е ~ Е1), еслисигнатуру Е 1R ~ R1, F ~ F1 иµ~ µ1. Если Х ~ R U F, то(R n Х, F n Х, µ 1Х) назовем ограничением сигнату=ры Е на множество Х (обозначаем Е1= Е I Х).Мощность множестваR U F называется мощнdстью сигнатуры Е = (R, F, µ) и обозначаетсячерез IEI.
Если Еп ~ Еп+I п Е w, то через U Еп обозначаем сигнатуруnEw( U Rn, U Fn, U µп).nEwnEwЕслиnEwR U F -/=- 121ито сигнатура Е называетсяF = 125 (R = 125),предикатной (функциональной).ЕслиR UF= 125,то сигнатура Еназывается пустой.Определение. Упорядоченная пара 21раической системойсигнатурыЕ,= (А, v 21 )еслиназывается алгебвыполняются следующиеусловия:а} Анепустое множество;-б} v 21 -отображение множества R U F в множество отношенийи операций на множестве А;в)г)rfЕ RЕ F==}==}vш(f) является µ(r)-местным отношением на А;v 21 - µ(!)-местная операция на А.Множество А называется носителем 21, v 21 - интерпретацией сигнатуры Е в А.
В дальнейшем вместо v 21 (r) будем часто писать простоrш или даже r, если ясно, о какой 21 идет речь.Алгебраические системы в дальнейшем будут обозначаться готическими буквами21,SВ,(возможно, с индексами}, а их носители...соответствующими латинскими буквами А, В,...-(с соответствующимииндексами). Мощностью алгебраической системы21будем называтьмощность ее носителя А. Для краткости будем часто опускать слово<,алгебраическая,> и называть21Определение. Отображениеалгебраической системы21просто системой.f:А-В называется гомоморфизмомсигнатуры Е в систему SВ той же сигнатурыЕ, если выполняются следующие условия:а) еслиqЕRиµ(q) =п, то для всех а1,...
,апЕ А(а1, ... , ап) Е qш ===* (!а1, ... , f ап) Е q'13;б} еслиqЕFиµ(q) =п, то для всех а1,J(q 21 (a1, ... , ап))Еслиf -гомоморфизмгомоморфизмом2121на SВ, а SВ-... ,апЕ А= q<.В (fa1, ... , fап).и SВ и ![А]=В, тоfгомоморфным образомназывается21.§ 3.1.Алгебраические системыИнъективный гомоморфизмI95Q( на SВ, для которого1- 1также-гомоморфизм, называется изоморфизмом Q( на SВ и обозначается черезI:QL::::.SВ. Если существует изоморфизмI:QL::::.SВ, то системыQ(и SВназываются изоморфными и обозначается это так: Q( ~ SВ. Изоморфизм1 системыQ(наQ(называется автоморфизмом системыQL.1Предложение 3.1.1. а). Если I: QL::::.SВ, то 1- : SВ::::.QL.б). Если I: QL::::.Q(1 и g: QL1::::.QL2, то (fg): QL::::.QL2.в). idл: QL::::. QL.До к аз ат ел ь ст в о получается непосредственно из определенияизоморфизма.ООпределение.SВ (обозначаемQ(СистемаQ(называетсяподсистемойсистемы~ SВ), если выполняются следующие условия:а) Q( и SВ имеют одну и ту же сигнатуру;б) А~ В;в) множество А замкнуто относительно операций v'В (!), 1 Е F;г) отношения и операции v 21 (q), q Е R U F, в Q( являются ограничением на А соответствующих отношений и операций v'В(q),q Е RU F, в SВ.Если АЕслиQ(,j:.В, тоQ(~ SВ называется собственной подсистемой SВ.~ SВ, то SВ называется надсистемойQL.Ясно, что в определении подсистемы в) следует из г).
Для удобствассылок мы выписали в) отдельно.Из определения подсистемы следует, что две подсистемыQ( 1, Q( 2системы SВ с одинаковыми носителями совпадают. С другой стороны,если непустое подмножество В1 ~ В замкнуто относительно операцийсистемы SВ, то В1 является носителем некоторой подсистемы SВ 1 ~ SВ.Таким образом, существует инъективное отображение множества непустых замкнутых относительно операций SВ подмножеств носителя Вна множество подсистем SВ. Это отображение можно продолжить навсе непустые подмножества В. А именно, имеет местоПредложениеХ,j:. 125,3.1.2.Если SВ-алгебраическая система, Х ~ В,то существует такая единственная подсистема SВ(Х) ~ SВс носителем В(Х), что Х ~ В(Х) и SВ(Х) ~Q(для любой подсистемы Q( ~ SВ, для которой Х ~ А.До к аз ат ель ст в о.
В качестве В(Х) берем пересечение носителей А всех подсистем Q( ~ SВ, содержащих Х. Так как Х ~ В(Х),то В(Х),j:. 125. Как уже отмечалось выше, В(Х) является носителемединственной подсистемы SВ(Х) ~ SВ.ООпределение. Подсистема SВ(Х) ~ SВ из предложениязываетсяподсистемой,порожденной множествомХв3.1.2SВ.наЕслиГл.96Х3.Истинность на алгебраических системах= {а1, ... , ап}, то SВ(Х) обозначаем также через SВ(а1, ...
, ап)- Если= SВ, то говорим, что система SВ порождается множеством Х.SВ(Х)Множество алгебраических систем {QLiIiЕJ}называется направленным множеством алгебраических систем, еслибыхi, jЕJсуществуетkЕJ,I =/:-IZJ и для людля которого Q(i ~ Q(k и Q(j ~ Q(k· Изопределения следует, что все системы направленного множества системимеют одну сигнатуру.Предложение3.1.3.Если {QLiI i Е J}алгебраических систем сигнатуры~.система Q( такая, что Q(i ~ Q( для всехсистемы SВ, для которой Q(i ~ SВ,Еiнаправленное множество-то существует единственнаяiЕJ и Q( ~ SВ для любойJ.До к аз ат ель ст в о.
Носителем Q( будет множество АПусть { ai, ... , ап} ~ А.Тогда= U Ai.iEIизопределения направленного мно-жества следует, что существует такое i Е J, что { а 1, ... , ап} ~ Ai.Пусть (а1, ... ,ап) принадлежит v 21 (s), s Е RUF, когда (а1, ... ,ап)принадлежит v 21; ( s). Такое определение не зависит от выбора i ЕЕ J, так как если {а1, ... ,ап} ~ Aj, то существует такая Q(k, чтоn{Q(i ~ Q(k и Q(j ~ Q(k· Следовательно, v 21 ,,. (r)(а1, ... , ап) }, r Е R, иv 21 ,,. (!) (а 1 , ..• , ап), f Е F, для т Е { i, j} совпадают с соответствующимиv 21 k(r)n {(а1, ... ,ап)}, rЕ R, иутверждения предложенияQ(i,v 21 k(J)(a1, ...
,an), f Е F. Остальные3.1 Q(очевидны.Система Q( из предложения3.1i Е J, и обозначается так: Q(= U Q(i·Оназывается объединением системiEIОпределение. Алгебраическая система Q( сигнатуры ~ называетсяобогащением системы Q(l сигнатуры ~1. если выполняются следующие условия:а) А= А1;б)~1в) v 211= ~ 1(R1 U F1);= v 21 1(R1 U F1).Если система Q( сигнатуры ~ является обогащением системы Q(lсигнатуры ~1.
то Q(l называется обеднением системы Q( до сигнатуры~ 1 и обозначается через Q(Если ~=1~ 1.(r1, ... , rп, ... ; !1, ... , fk, ... ; с1, ... , Ст, ... ), то алгебраическую систему Q( сигнатуры ~ часто будем обозначать так: Q(=(А, r. 1, ..•· · ·, r.n, ·· ·; f_ 1,. ·., j_k, ...
; ~1, ... , ~m• ... ),где r.n, j_k, ~m обозначают соответственно отношение v 21 (rп), операцию v 21 (fk) и значение константыv 21 (cm) на множестве А.ПримерN =vJ -3.1.4.Алгебраическаясистема 1)1множество натуральных чисел,+и.: -=(N,+,.:;Q,l), гдеоперации сложения97§ 3.1. Алгебраические системыи умножения,Q=О,1=1,называется арифметикой натуральныхчисел или просто арифметикой. Заметим, что 1)1 не имеет подсистемотличных от нее самой. Функциональная сигнатура Е1= (+ 2, -2; О, 1)называется сигнатурой колец с единицей.
Однако не все алгебраические системы сигнатуры Е, будут кольцами. Для этого необходимо,чтобы операции удовлетворяли определенным условиям (аксиомам колец). Арифметика 1)1 не является кольцом, а система 3 = (Z,где Z - множество всех целых чисел (Z{О, 1,, 2, ... ; -1,=операции сложения и умножения,+,: -Заметим, что 1)1 ~Система ~+, : -3.гдеПример3 является1=-2, ... } ),будет кольцом.1,3называется кольцом целых чисел.множество действительных чисел,операции сложения и умножения,кольцом.
СистемаО,R -Система= (R, +, :; Q, 1),Q=+, :; Q, 1),Q=~-О,1=1,также являетсяподсистемой3.1.5. Функциональная сигнатура Е2 = (-2, (- 1 ) 1 ;е) называется групповой. Группой подстановок множества Х называетсясистема (S(X), :, (~); f) сигнатуры Е2, где S(X) обозначает множествовсех биективных отображений непустого множества Х на себя,: -композицию отображений, (~) - обращение отображения, f - тождественное отображение. Вообще, система 21 = (А,:, (~); f) сигнатурыЕ2 называется группой, если для любых а, а1, а2 Е А в21выполняютсяследующие равенства:1) а · (а1 · а2) = (а · а1) · а2,2) а· е = е · а = а,3) а· а- 1 = а- 1 ·а= е, где :(а, а 1 ), (~)(а) записаны более краткокак а· а 1 и а- 1 • Если для любых а, а1 Е А в 21 выполняется ещеравенствотогруппаназывается21абелевой.Часто,чтобыподчеркнуть, чтогруппа 21 абелева, символы ·, (- 1) и е обозначаются через+, (-)и О соответственно.
Примером абелевой группы может служить группацелых чиселводящая m в(Z, +, (=); Q),-m, и Q = О.где+-сложение,(=) -Пример 3.1.6. Если предикатная сигнатура Еоперация, пере= (Q 2)состоит из одного символа двухместного отношенияQ,тосистемы 2121=(А,Q)называется графом. Если Q - частичный (линейный) порядок на А, то21 называется частично (линейно) упорядоченным множеством илипросто частичным (линейным) порядком 1). В этом случае (а, Ь) Е Q1)Это определение не совсем совпадает с определением ч. у. м.
в § 2.2(ч. у. м. в§2.2 -пара, у которой первый член может быть пустым множеством,а носители алгебраических систем всегда непустые).4Ю. Л. Ершов, Е. А. ПалютинГл.98Истинность на алгебраических системах3.обозначается через а ~ 21 Ь или просто через а ~ Ь. Частичный порядокQt называется плотным, если из а ~ Ь и а -1=- Ь следует существованиетакого с Е А, что с -1=- а, с -1=- Ь, а ~ с и с ~ Ь. Будем говорить, чтодва линейных порядка Qt иществование вQ3 имеют одинаковые концы, если суQt наименьшего и наибольшего элемента эквивалентносуществованию соответствующего элемента в!13.Заметим, что подсистема частичного (линейного) порядка будет частичным (линейным)порядком, однако подсистема плотного линейного порядка не обязанабыть плотным линейным порядком.Предложение3.1. 7.Если Qt иQ3 -два счетных плотных линейных порядка с одинаковыми концами, то Qt с:::IпДоказательство. Пусть А= {апРассмотрим множествоG,Е!13.w},IпВ= {Ьпсостоящее из отображенийg:А1Еw}.---.В1,удовлетворяющих следующим условиям:1) А 1 и В 1 - конечные подмножества А и В соответственно;2) g: l.2t(A1)~ SJ3(B1), если А1 -1=- !о;3) если IA1I = 2n > О, то {ао, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
