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

4. Доказать„что: (а) (А()В) х (С()Р) = (Ахе)()(ВхР); (б) () А. х () В. = () (А. х В ). 1Б1 (ЕУ (Е) 5. Доказать, что (АхВ)О(СхР)С(АОС) х(ВОР), При каких А, В, С и Р получается равенство? 6. Доказать, что: (а) (АОВ)хС = (Ахе)О(ВхС); (б) А х (ВОС) = (А х В) О(А х С); (в) (АОВ)х(СОР) = (АхС)О(ВхС)О(АхР)О(ВхР); (г) (А~В)хс = (Ахс)ЦВхс); (д) Ах(В~С) = (АхВ)цАхС); (е) АхВ = (АхР)()(схв), где АСС и ВСР; (ж) и~)(АхВ) = ((и~А)х() )О(((х(и)В) 1; Сз)ил хов= о (л хв); йод ~ос «злила СМОЛ,хОВ,= О СА хв,).

зад унт Ф.фн смт 7. Пусть А, В н и н (Ахв)О(вхл) = (Сх.О). Дакззать, что 3. Нанти д .р М, М-М„М.М, М -М длн сзедующвк атнаивзиис $М М = Кк„уй л, у 4=.4 и л делит у); Ю М = ((к,уН.к,у~ 4" ву делвтл)," Св) М = Кк. уЦК. у ЕУ и к+у ~ 0)„" Ст) М = (~т. уЦ з„у ЕФ и 2з ~. Зу); СМ М = ~фс, ф л, у Е ~ — 2, Я в у > зйа «». Ф. Днкзззть, еак Ь~а =в .М=н р„=н; ййдд — )=р „р — з= 6„„- СМйд =М,'ф ой„); Вт ' 1 "2 Сттр =Мф~ Од ) 9 3 ° з ! $. Дюаззать„анк СМесзввэсв, тол =А; СВ) есин Л и и. торл „и = В- 4 $.

Пусть М вЂ” бинарное опннвеиве вз А Дакзззть, нто М = г тотда и тнзъзо пази, зззза М-М = М М = М дзз либато отноюелнз М нзл. 3 2. Докзззъь„чзн дзз лззназ 6ввзрнзск отнеиизвззс (М МСЗМ = МОМ= М; (б)(М ') '=М; (М(ЦОМз) '=М, 'ОМ,'; мСм,о») '=м,'ом,'; Ж-М '=(-М) ', <е) ОМ = ОМ.'; 13. Длв каких бинарных опиииений Я справедливо Я = — Я? 14. Пусть А и  — конечные мгигжества, састоищне из т н л элементов соответственно. (а) Сколько суи(ествует бинарных отноа1ений между элементами множеств А и Я? (б) Ск е Фу ннг Авв? (в) Сколько нмеегев 1-1-функций нз А в В? (г) При каких юе и л суюествует взаимно однозначное соответствие между А и В? 15.

Доказать, что длв любых бгпварнмх отноииеннй: (а) Я).(ЯЗ.Яз) =(Я(.Я2).Яз' (б) (Я, Я ) ~= И. ~.Я, (в) 1 () Я,1-а= О (Я„.-а); ( (О) / ИГ1 (г) Д.( (1 Я,) = (.1 Я.Я,). (Е1 (Е1 16. Доказать, гпк (а) О ~ г) Я.') с () ((У.Я.); (,(Н1 '! (сг (б) () )(, .ас ()(Я,.()); (в) в утверждеиивх (а) и (б) включении иевьзх заменить ровенст- вами. 17.

Образуют ли бинарные отиеигеиии грунну относительна операций н ? 1и Докати, о, нЯ, СЯ, (а) О Я, С (У . Я; (б) Я„(.( с Я;О; (в) Я, ' С Я, '. 19. Доказатъ„пк (а) если Я м а, то ~ВА м н.„ (б) З'~ С Р(А х 11). 26. Устзаианть взаимно ааиазь ирн1= 11„.. и). ЧЛ. ТЕОРИЯ МНОЖЕСТВ !з ,УУ 21. Используя определение, описать множество У' ), где У— множество действительных чисел.

22. Доказать, что если У есть функция из А в В и я есть функция из В в С,тоТ яестьфункцияизАв С. 23. Пусть/и я — функции. При каких условиях: (а) Т' является функцией; (о) У В является 1 — 1-функцией? 24. Пусть А, В, А,  — такие множества, что А находится во !' ! взаимно однозначном соответствии с А), а  — с В .

Показать, что можно установить взаимно однозначное соответствие: (а) междуАхВ иА,хВ,; В В (б) между А иА !; ! (в) междуАОВиА,ОВ,, если А!"!В = а иА,Г\В, = в. 25. Доказать, что можно установить взаимно однозначное соответствие между множествами (а) АхВ и ВхА; (6) Ах(ВхС) = (Ах В) хС; (в) (АхВ) и А хВс; ( )( ~В)С АВхС.

(д) А иА хА, еслиВ!)С =а; (е) П А.и П А, гдето> — подстановка множества Д ~!. ! х!. Р(!Т (н) (н! (ж) ПА.и П П А,где О Т„=!ивсеТ попарнонепересе(н! Внк ),~нт,~ ьнк каются; (з) А и П А !, где О Т = Т и все Т попарно не пересекаются. 26. Пусть р А- А — подстановка множества А. Доказать, что — ! р — подстановка множества А. 27. Доказать, что множество подстановок множества А образует группу. 28. Пусть р: А -~  — взаимно однозначное соответствие. Доказать, что: (а) р ' — взаимно однозначное соответствие между В и А; (б) У' = !В! 5 2.

ОТНОШЕНИЯ И ФУНКЦИИ га (в) Ю Ю 29. Доказать, что для того, чтобы отношение ЛСАхВ было взаимно однозначным соответствием между А и В, необходимо и достаточно,чтобыВ.В =1 ИВ ' В=( . А в' 30. Доказать, что объединение (пересечение) двух функций/, н/2 из А в В является функцией из А в В тогда и только тогда, когда 1' =1. 1 2' 31. Доказать, что для любой функции 1"' (а) /(А(/В) =1(А)(.)1(В); (б) У( (/А.~ = (//(А,). ((Е1 / НЗ1 32. Доказать, что для любой функции 1' (а) 1(А()В) С /(А) Г)1(В); (б) у( () А.) С (') у(А,), ( (Е1 / (Е1 и эти включения нельзя заменить равенствами.

33. Доказать, что /' удовлетворяет условию /(А()В) = у(А)ГЯВ) для любых А и В тогда и только тогда, когда 1" есть 1-1-функция. 34. Доказать, что/(А) ~/(В) С /(А~В) для любой функции /'. 35. Доказать, что если в предыдущем примере/ есть 1 — 1-функция, то выполняется равенство.

36. Доказать, что если А С В, то 1(А) С 1(В) для любой функции1. 37. Доказать, что для любой функции 1 /(А) = н сэАйд = а. 38. Доказать следующие тождества для любой функции 1: (а) / (А(/В) = 1 (А)(/1 (В); (6)1 ~ О А.~ = (/,/ (А.); (ГЕ1 / (Е1 (в) /' (А()В) = У (А)()/' (В); (г) /' ~ (') А.~ = () /' (А,); 1(Е1 / (Е1 (д)/ '(А')В) =/ '(А)1У '(В). ЧЛ. ТЕОРИЯ МНОЖЕСТВ 39.

Доказать, что если А С В, то справедливо~ 1(А) С ~ (В) для любой функции У. 40. Доказать, что для любой функции у' у' (А) = а ~» Айр = а. 41. Доказать, что если А С д.и В С р ., то: (а) А Су-1(у(А)); (б) У(~ '(В)) = В; (в) ДА)Г1В =/(А11У (В)); (г) 1(А)ПВ = а с АГь! (В) = а; (д) ДА) С В»»А СУ (В). 42. Пусть Р А- В. Определим У: Р(А)- Р(В), 'У' Р(В)- Р(А) такие, что.г'(Х) = Ях) ~ х1-"Х) и'у(у) = (х~ у(х)яу).

При каких условиях у у„= 1 7 При каких условияху' ."г"= 1 43. В обозначениях предыдущей задачи доказать, что: (а) У'(х1 1У) = У" (х)1 1У" (У); (б) (( з)'(Х) = У"(в"(Х)). 44. Пусть У вЂ” не~устое множество. Для любого подмножества А множества У обозначим черезХ следующую функцию (характеи ристическую Функцию множества А): 11 ~0, если хЕА, "А (1, если хЕ11'1А. Определим функцию В Р(11)- (О, Ц следующим условием: 1(А) = Х для любого АЕР(0). Доказать, что,1 есть взаимно однознач- ное соответствие между Р(11) и (О, Ц . й' 45. Доказать, что введенная в предыдущей задаче функция Х удовлетворяет следующим условиям: (а) Х~~х) =0; ' (б) Ха(х) = 1; (в) Хгд (х) = 1 — ХА(х); (г) ХАЕВ(х) =Х 1(х) ° Х (х); (д) Хлг1л(х) = ХА(х) + Хл(х) — Х 1(х) Хл(х); г! а 2.

ОтнОшения и Функнии (е) х„~л(х) = 1 — хл(х) + хл„л(х); (ж) если А = О А., то)( (х) = [п[пт. (х); [аву уну ! (з) если А = ("[ А,, то;( (х) = и[ах)(~(х). !' А .еу А 46. Доказать свойсгва полной дистрибутионости: (а)О ЙА =() ОА, иау уну (б) у) ОА. = О ()А.... ИВУ уИУ уну[ !НЕТ 47. Доказать, что А = ПА., гдеА. = А для всех !~У. у т-т [ ! [нх 48. Пусть А С Х. Доказать, что." (а) П а, = () П А, где Ай=Ар Аг=х. прн ! и у; [иву ' [ИЕУуну О (б) Пх, [ПА = О ПВ( гдеВЯ = хлАЕ В..= х. при! му.

иву [аву [иву уну 49. Доказать, что: (а) () П ~Н = П у) А,; у[ек !БТ уиТ Енк (б) еслиА [)А =апри( м(,томожноустановитьвзанмноодно! г' ! ('!у А1 значное соответствие между В \от ) и П ВА[; унт (в) можно установить взаимно однозначное соответствие между 50. Доказать„что если А м я[ для всех унт, то П А и я[ (одна из [ет формулировок аксиомы выбора) . [[х ° . * - [П~,«[(П!).(П [) гет уцт [ !Бт ! ! ! 2 2 установить взаимно однозначное соответствие, если Т ОТ = Т и Т ()Т = я[. ! 2 22 Ч.!.

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

Классом эквивалентности (смежным классом) элемента х по эквивалентности Я называется множество [х [ = х!Я = (у[ (х, у)ЕЯ). Множество классов эквивалентности элементов множества Л по эквивалентности Я называется фактормножеством А по Я и обозначается через А/Я. Бинарное отношение на множестве А называется предпорядком на А, если оно рефлексивно и транзитивно. Рефлексивное, транзитивное и антисимметричное отношение на множестве А называется частичным порядком на Л.Частичный порядок часто обозначается символом — 1 <. Порядок < называется двойсп|венным к < и обозначается символом >. Будем писать хсу, если х<у и хыу.

Частичный порядок < на множестве А называется линейным, если любые два элемента из А сравнимы по <, т. е. х<у или у<х для любых х, уЕЛ. Множество Л с заданным на нем частичным [линейным) порядком < называется частично |линейно) упорядоченным. Подмножество В множества А, частично упорядоченного отношением <, называется целью в Л, если оно линейно упорядочено отношением < Г)В2. Элемент а частично упорядоченного множества Л называется максимальным [мипимальным), если из того, что а<х (х<а), следует а=х. Элемент а из Л называется наибольшим [наименьшим), если .г<а (а<х) для всех хЕА.