И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 4

Верхней (нижней) гранью подмножества В частично упорядоченного множества А называется любой элемент а из Л такой, что диа (аЯд) для лн)бого дЕВ. Точной верхней [нижней) з 3. СПЕПИАЛЬНЫЕ БИНАРНЫЕ ОТНОШЕНИЯ гранью подмножества ВСА называется наименьшая верхняя (наибольшая нижняя) грань для В. Точная верхняя и точная нижняя грани множества ВЕА обозначаются через анр В и 1п( В соответственно. Линейный порядок ( на множестве А назовем полным, если каждое непустое подмножество множества А имеет наименьший элемент.

В этом случае множество А называется вполне упорядоченным. Пусть А и  — частично упор1щоченные множества иУ вЂ” функция из А в В. г называется монотонным отображением, если из х ~ха следует У(х ) ~У(х ) для любых элементов х, х ЕА, Если У есть взаимно однозначное соответствие между А и В, У и з' — монотонные отображения, тоУ называется изоморфизмом частично упорядоченных множеств А и В, а множества А и В называются изоморфными. Частично упорядоченное множество М называется решеткой или структурой, если для любых двух элементов х, уЕМ существуют точная нижняя грань хйуи точнаяверхняя грань хС)у.

Будем обозначать (...((х,йх )йх )й...йх ) через х, й х й хз й ... й х и (...((х ()х ) Ох ) ()... Е) х„) через х, С) х. С) х ... () х . Наибольший элемент решетки (если он существует) обозначается через 1, а наименьший — через О. Решетка М называется дистрибутивной, если для любых х, у, гЕМ выполнены тождества (х(Зу)йг = (хйг)()(уйг), (хйу)()г = (х0г)й(у(.)г). Дистрибутивная решетка М называется булевой алгеброй, если для любого элемента хЕМ существует дополнение, т.

е. элемент ( — х), удовлетворяющий условиям: для любого элемента уЕМ [х1)(-х) )йу = у, [хй( — х) [Оу = у. Семейство подмножеств 5 данного множества А называется алгеброй подмножеств, если В замкнуто относительно теоретико-множественных операций объединения, пересечения и дополнения, т. е.

х, уы (х(з»ы, (хй»ы, (-х)ы. Фильтром на булевой алгебре М называется непустое подмно- жество РСМ, удовлетворяющее условиям: (1) х, уЕР ~ (хйу)ЕР, (2) хЕР, х<у~ уЕР, (3) хЕР ~ ( — х)ЮР. Фильтр Р на булевой алгебре М называется улыпрафильтром, если он удовлетворяет условию (4) хЕ Р или (-х) Е Р для любого хЕМ. Фильтр Х» иа булевой алгебре М называегсв простым, если он удонветвариет уаювиик длш любил х, у~М (5) (хну)ЯХ» э' АХ» илн у("-Х». Фильтр Х» иа бужвай алгебре М называегсв максимальным, если он не содерзситсв ни в каком друн»м фнлътре на М. $ Доказать, что если атно»иеизюВ Я н Я рефлексивны, то рефотисив з* » г' 2.

Доказать, что если Я' и Я нррефлексивнм, то ир(»ефлексивны и отношении Я (.)Яз, Я (')Яз, Я, . Показать, что произведение Я Я нррефлексивиык отношений может не быть иррефлекснвным. 3. Доказать, что если Я н Я симметричны, то симметричны отно- шеннкЯ ()Яз, Я Г)Я~, Я, Я Я 4. Доказать, что произведение Я, Я симметричныл отношений Я иЯ симметрнчнотогдаитолькотогда, когдаЯ, Я = Я .Я . 5. Доказать, что: (а) если отношении Я и Я антисимметрнчны, то антисиммет- ричны также Я () Я нЯ, '; (б) объединение Я, о Я антиснмметрнчных отношений Я и Я на А аитиснмметричио тогда и только тогда, когда Я .

Я б. Построить бинарное отношение: (а) рефлексивное„симметричное, не транзнтивное; (б) рефлексивное, аитнсимметрнчное, не транзитивиое; (в) рефдексивное, транзитивное, ие симметричное; (г) антнсимметрнчное, транзитивное, не рефлексивное. 7 (а) Построить бинарное отшвиенне, симметричное, траизитввиое, ио ие рефлексивиое. (б) Доказать, что если Я есть транзитнвное и симметричное отношение на миожссгве А и д 0 р = А, то Я есть эквивалентность иа А. й Доказать, что любое отнсвнеиие Я, симыетричное и антисиммегричиае одновременно, вкакетсв траизитивиым.

Ф. Дакии»иь, чю опююеиие Я иа множестве А вивкетск одновременна эквивалезгпюстъю и частичаыы иорш(кам в том и только там свучае, кшда Я = ( . !Ф. На множествах,Х и.Хх Ф' оиреаеаим Я, Д, Б следующим образоьс (а) (а, Ь)(ЕЯ «» (а — Ь) делится на ш (гл>0); (б) ((а, Ь), (с, с())«=-(1 *в а + ( = Ь + с; (в) ((а, Ь), (с, «())(БЯ ч и (((а.«( = Ь.с) и Ь и О и А«»0) или (а = с, Ь = О,й = О) ]. Доказать, что Я, Д и Я являются отношениями эквивалентности. ! !.

Пусть А — множсктзо всех прямых на плоскости. Являются лн эквиваленпюстями следующие отношения: (а) параллельность примых; (б) иерпеидикулярнесгь прянику (2. На миолпктве Ф действителынях чисел определим отношение Я следующим образом: аЯ() «» (а-)У) — рациональное число.

Доказать, что Я есть эквивалентность. (3. Доказать, что есин Я вЂ” эквивалентность, то: (а) хЕ(х)а, (б) (х,у)«=Я «» (х) = (у) . (4. Доказать, что если Я есп эквивалентность, то Я ' есть также эквивалентность. ! 5. Пуси Я Я А~. Доказать,что Я есть эквивалентность «» (Я Я ')Ш = Я. А !6. Доказать, что если Я и Я вЂ” эквивалентности на А, то: ! 3 (2 Я Аз. (б)Я Я =А «»Я Я А. 3 $ (7.

Доказать, что существует взаимно однозначное соответствие между классом всех разбиений множества А на непересекающиеся непустые подмножества и семейством всех отношений эквивалентности на А. (Семейство (А), называется раэоиеиием А, если ( ) А. = А и множества А. попарно не пересекаются.) гЫ ((). Доказать, что Я тогда и только тогда является отношением эквивалентности на множестве А, когда существует система У попарно непересекающихся множеств такая, что Я= О СхС и () С=А.

се У сн.У 26 Ч.1. ТЕОРИЯ МНОЖЕСТВ 19. Пусть/: А-  — произвольная функция. Положим Ц = ((х, у)[/(х) =Ду)]. Доказать, что Ц является эквивалентностью на А и для отображения/существует разложение /= Е !' где е — естесл венное отображение А на А/Д = ([х] [х!ЕА], т, е. 0 г(х) = [х],, / — взаимно однозначное соответствие между А/Д и ДА). 20.

Доказать, что пересечение любой системы эквивалентностей на множестве А есть эквивалентность на А. 2!. Доказать, что объединение Я,!./Я эквивалентностей Я, и Я является эквивалентностью тогда и только тогда, когда Я, С!Я =Я Я. ! 2' 22. Доказать, что произведение Я, Я двух эквивалентностей Я н Я тогда и только тогда является эквивалентностью, когда Я, Я =Я Я. 2 !' 23. Доказать, что если Я и Я вЂ” эквивалентности и Я Я 1 2 1 2 = Я ЯН то Я,+ Я = Я Я, где Я +Я вЂ” наименьшее отношение эквивалентности, включающее Я, ! !Я .

24. Доказать, что для всякого семейства эквивалентностей (Я.) . ! 1Н1 существует эквивалентность Д такая, что С! Я. С Д, и для всякого огни! ношения эквивалентности Я, если !.! Я. С Я, то Ц ~ Я. 1 нят 25. Доказать, что 1=о где р — число эквивалентностей на множестве из и элементов. 26. Доказать, что множесгво всех подмножеств данного множества частично упорядочено отношением включения С. 27. Пусть < и < на множестве Ф'= (О, 1, 2, ...) определяются обычнымобразом. Доказать, что« ° м«; ° «=; < «=„Ф' .

2 28, Доказать, что ! есть частичный порядок на А. $ 3. СПКНИАЛЬНЫЕ БИНАРНЫЕ ОТНОЦ1ЕНИЯ 27 29. Пусть а<Ь ч» а, ЬЕ 4' и а делит Ь. Считаем, что О делит О. Доказать, что < — частичный порядок на 4'. 30. (а) Доказать, что всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента. (б) Доказать, что наибольший (наименьший) элемент частично упорядоченного множества является единственным максимальным (минимальным) элементом. (в) Построить пример частично упорядоченного множества, имеющего точно один минимальный элемент, но не имеющего наименьшего элемента. -1 31. Доказать, что если Я вЂ” частичный порядок, то Я вЂ” частичный порядок.

32. Показать, что если (Я.). — система частичных порядков на ! Ш множестве А, то й Я вЂ” частичный порядок на множестве А. (в Г 33. Доказать, что отношение Я на множестве А есть предпорядок тогда и только тогда, когда Я = (Я Я)Ш . 34. Пусть Я вЂ” отношение предпорядка на А. Положим а — Ь»» (а, Ь)ЕЯ и (Ь, а)1=Я. Доказать, что: (а) — есть отношение эквивалентности на А; (б) если а — а,, Ь вЂ” Ь, (а, Ь)ЕЯ, то(а,, Ь1)ЕЯ; (в) Я есть отношение частичного порядка на А/-, где 1 ([а [, [Ь [)ЕЯ, ч» (а, Ь)ЕЯ.

35. Доказать, что если Я вЂ” частичный (линейный, полный) порядок на Х и АСХ, то ЯГ)А есть частичный (линейный, полный) порядок на А. 36. Пусть < — частичный порядок на А. Доказать, что < иррефлексивно и транзитивно. 37. Доказать, что если некоторое отношение < на А иррсфлексивно и транзитивно, то отношение х<у ч» х<у или х=у есть частичный порядок на А. 38, Показать„что если А и А, — частично упорядоченные множества и ~1 А- А — монотонная функция, осуществляющая взаимно 1 однозначное соответствие между А и А, то) может не быть моно- 1' тонной.