1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 13
Текст из файла (страница 13)
, АпЕ Ап}и обо-значается через А, х... х Ап. Если Х ~ А, х ... х Ап, то множествоAi, для которых существуют такие а,, ... , ai-1, ai+ 1, ... , ап, что(а,, ... , ai-1, а, ai+,, ... , ап) Е Х, называется проекцией Х и обозначавсех а Еется через1rf Х.б). Если А,=... =Ап= А,то А, х...х Ап называется декартовойп-степенью множества А и обозначается через Ап. Если попределению полагаем А0{0}.= О,то по=в). Подмножества В~ Ап будут называться п-местными отношениями или предикатами на А.
Будем говорить, что В-п-местноеотношение или предикат, если В является n-местным отношениемна А для некоторого множества А.г). Если В{ (а, Ь)-двухместное отношение, то двухместное отношение(Ь, а) Е В} будем называть обратным к В и обозначать через в- 1 •1Гл.62д). Если В, С-2.Теория множествдва двухместных отношения, то двухместноеотношение{ (а, с)1(а, Ь) ЕВ и (Ь, с) Е С для некоторого Ь}будем называть композицией или произведением двухместных отношений В, С и обозначать через (ВС) или В·С.Так как (а) = а, то А 1 = А, поэтому подмножества А будут одноместными предикатами на А.0Заметим, что О-местных предикатов только два:и{0}.Из определения в- 1 сразу следует равенство В= (в- 1 )- 1•Предложение2.1.2.Если В, С иD -двухместные предикаты,тоа)((BC)D)б) (вс)- 1= (B(CD)).= (с- 1 в- 1 ).Доказательство.
а). Пусть (х,у) Еторых и и(и, у) Еv(CD)((BC)D). Тогда для некоЕ D. Таким образом,(B(CD)). Включение B(CD) ~ ((BC)D) докаимеем (х, и) ЕВ, (и,и (х, у) Еv)Е С и(v, у)зывается аналогично. Доказательство б) оставляется читателю.Ассоциативность композиции, доказанная в предложенииволяет обозначать композицию((BC)D)= (B(CD))черезэтой же причине однозначно определена композиция п(В1...
Bn).Отметим, что коммутативность (ВС)=2.1.2,Dпоз(BCD).Попредикатов(СВ) для произведения предикатов не имеет места (приведите пример).Определение. Двухместное отношение И на множестве А называетсяа) диагональю А 2 и обозначается через idA, если И= { (а, а) 1 а ЕЕ А};б) рефлексивным на А, еслив) симметричным, если И=idA ~ И;u- 1;г) транзитивным, если (ИИ) ~ И;д) эквивалентностью на А, если И рефлексивно, симметрично итранзитивно;е) антисимметричным, если Иn u- 1 ~ idA.Например, предикат{ (m, п) 1 m и п - взаимно простые натуральные числа}является симметричным, но не рефлексивным и не транзитным наа предикатw,{ (m, п)1(п - т)но не симметричным и неw,w} является транзитивным нарефлексивным на w.> О, п, тЕ§ 2.1.Если Иn впПредикаты и отображения63n-местное отношение на А и В ~ А, то отношение И-nна множестве В будем называть ограничением отношения И намножество В. Очевидно, что ограничения отношений типов а)-е) изпредыдущего определения на любое В ~ А будут также отношениямисоответствующих типов а)-е).Пример2.1.3.Говорим, чтоU Ai = Амножества А, еслилибоAin Aj= {Ai j iRЕJ}и для любых i,iEJ= 121.
Пусть R = { Ai I i Е J} -является разбиениемЕjIлибоAi= Aj,разбиение множества А.Определим следующее двухместное отношение на А:Ен= {(а, Ь)1а, Ь ЕAiдля некоторогоi Е J}.Очевидно, что Ен будет эквивалентностью на А.Если Е-= {а 1 (а, х)эквивалентность на множестве А, то множества Ех=Е Е} для х Е А будем называть классами эквивалентности по отношению Е.Легко показать, что любую эквивалентность на множестве А можнополучить способом, указанным в примереЕ-эквивалентность на А и Rв=Е получаем х Е Ех, следовательно,2.1.3.В самом деле, пустьI х Е А}.
Из рефлексивностиU Ех = А. Из симметричности{ЕххЕАи транзитивности Е следует, что если (х, у) ЕЕ, то Ех(х, у) ф. Е, то Ехn Еу = 121.= Еу,а еслиТаким образом, множество Rв классовэквивалентности по Е является разбиением А и ЕнЕОпределение. а). Двухместное отношениеf= Е.называется отображением или функцией, если для любых а, Ь, с из (а, Ь) Е1rffи (а, с) Еfследует Ь = с. Если f - отображение, то множествоf называетсяобластью определения f и обозначается domf, а множество 1rШJназывается областью значенийб). Отображениеесли1- 1 такжеfи обозначаетсяrang f.называется инъективным (или разнозначным),является отображением.в). Отображение=А иfназывается отображением А в В, еслиfdomf =rang f~ В.г).
Отображениеfназывается сюръективным отображением Ав В (или отображением А на В), еслид). Отображениеfdomf=Аиrangf =В.называется биективным отображением А в В(или взаимно однозначным отображением А на В), если оно является одновременно инъективным и сюръективным отображением А в В.е). Отображениерацией на А.fмножестваAnв А называется п-местной опе64Гл.2.Теория множествОчевидно, что диагональ idл множества А 2 будет биективной одноместной операцией на А. Диагональ idл множества А 2 в дальнейшембудем называть также тождественной операцией на А.f : А ---t ВЗаписьжение А в В, записьбудет в дальнейшем обозначать, чтоА>-----+ В будет обозначать, чтоf:отображение А в В, а записьf : А--*f -отобраинъективноеf -В будет обозначать, чтоf -сюръективное отображение А в В.Предложение2.1.4.а).
Еслиf:А ---t В иg:В--+ С, то(Jg):А--+--+ С.б). Еслиf: А - В и g: В--* С, то (Jg): А - С.в). Если f -fг). Еслитивно И1- 1 -биективное отображение А в В, тоотображение В в А,и g -f · 1- 1 = idлибиективное1- 1 • f = idв.инъективные отображения, тоf ·gтакже инъек(Jg)- 1 = (g- 1J- 1).До к аз ат ель ст в о этого предложения оставляется читателю в качестве упражнения.f, то Ь называется значением ff(a) или fa.Если f - отображение и А~ domf, то множество {!а I а Е А}называется образом множества А при отображении f и обозначаетсячерез ![А], а отображение f n (Ах rang !) называется ограничениемf на А и обозначается через f ~ А.Ясно, что п-местная операция является ( п + 1)-местным отношением, а О-местная операция f : А 0 --+ А есть { (0, а)} для некоторогоа Е А.
Часто О-местную операцию { (0, а)} на А будем называть конЕслиf -Оотображение и (а, Ь) Ена элементе а и обозначается черезстантой на А и отождествлять с элементом а.Еслиn-местная операция на А, то условие (а1,f -будем записывать так:= Ь,т. е.= Ь,ff(ai, ... , ап) =... , ап, Ь) Е /Ь. Для п = О это будетf() =что согласуется с принятым нами отождествлениемконстанты с ее значением.Пустьf -п-местная операция на А и В ~ А.
Множество В называется замкнутым относительно операцииследует !(а1,... ,ап)f,если из а1,... , апЕ ВЕВ.Упражнения1.ПустьИ-стве А, (а, а)транзитивное двухместное отношение,f.намножеИ для любого а и для любого а Е А существуеттакое Ь, что (а, Ь) Е И. Показать, что А бесконечно.2.3.Доказать предложениеЕслиf:= 1-1.А ---t В,g:2.1.4.В--* А и(gf)= idв,тоfбиективно иg=§ 2.2.§ 2.2.Частично упорядоченные множества65Частично упорядоченные множестваСреди различных типов отношений некоторые имеют фундаментальное значение не только для математической логики, но и для всейматематики.
В предыдущем параграфе мы уже рассматривали одноиз таких отношенийэквивалентность. Определим еще два очень-важных типа отношений.Определение. а). Отношение И на множестве А называется частичным порядком на А, если оно рефлексивно, транзитивно и антисимметрично.б). Частичный порядок И на А называется линейным порядкомна А, если для любых а, Ь Е А выполняется хотя бы одно из следующихдвух условий: (а, Ь) Е И, (Ь, а) Е И.Очевидно, что ограничение частичного (линейного) порядка на Ана любое подмножество В ~ А будет частичным (линейным) порядкомна В.Важным примером частичного порядка на множестве А являетсяотношение{ (а, Ь) \ а, Ь{ (а, Ь) \ а, ЬотношениеЕ А, а ~ Ь}, а примером линейного порядкаЕ Х, а ~ Ь }, где Х--некоторое подмножествомножества действительных чисел.Определение.
а). Если И=-частичный порядок на А, то пару2t=(А, И) назовем частично упорядоченным множеством (сокращенноч. у. м.).б). Если И- линейный порядок на А, то пару 21=(А, И) назовемлинейно упорядоченным множеством.Пусть2t=(А, И)-частично упорядоченное множество.мент ао Е А называется верхней (нижней) гранью в2tЭлеподмножестваАо ~ А, если (Ь, ао) Е И( (ао, Ь) Е И) для всех Ь Е Ао. Верхняя (нижняя)в2tгрань А называется наибольшим (наименьшим) в21элементом.Элемент а Е А называется максимальным (минимальным) в(а, х) Е И (соответственно из (х, а) Е И) следует х= а.2t,если изЯсно, что наибольший (наименьший) элемент является максимальным (минимальным), и если Ив2t-линейный порядок, то максимальный (минимальный)элемент является также наибольшим (наименьшим) вчто если наибольший (наименьший) в2t21.Очевидно,элемент существует, то всемаксимальные (минимальные) элементы равны между собой.Если В-множество верхних граней вА 1 ~ А, то наименьший в (В, Иn В2 )верхней гранью (сокращенно н.
в. г.) вчерез3sup(A1, 21).21=(А, И) множестваэлемент называется наименьшей2tмножества А1 и обозначаетсяЗаменив в предыдущем определении слова <<верх-Ю. Л. Ершов, Е. А. Палютин66Гл.2.Теория множествних,> и <,наименьший,> соответственно на слова <,нижних\) и «наибольший,>, получим определение наибольшей нижней грани (сокращеннон. н. г.) А, виsup(At, !.!)!.!, которую будем обозначать через inf(At, !.!).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
