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

Объединением семейства множеств А! (! Е 1) называется множество !зА, = (х ~существует!', е 1такое, чтох е А ) гна! о Пересечением множеств А и В называется множество ЛОВ = (х ~ х !Е Л и х ~ В). Пересечением семейства множествА. (! Е 1), где 1ми, называет! ся множество !! А, = (х ~ х ЕА. для всех! Е 1).

!на! Разностью множеств А и В называется множество А1В=(х ~ хЕАнхЮВ). Мы предполагаем, что все встречающиеся в задачах этого параграфа множества являются подмножествами некоторого универсального множества 1!. Разность |11А называется дополнением множества А и обозначается через -А. Симметрической разностью множеств А н В называется множество А-В = (А ! В) 1.1(В ! А). из. тин нн множкств 1.

Доказать: (а) А ъ. Л (рефлекснвность); (6) если Л и. В и В 1 С, то А ъ. С (транзитнаность); (в)ЛйВъ,Лъ.АОВ; (г)АйВъ,В( АОВ; (д) Л~ВаЛ. 2. Доказать. что если А есть множеспю корней уравнения «з- 7к + б * О н В «(1, 6), то А В. 3. Доказать, что а и (а). 4. Доказать, что Н1, 2), (2, 3)) и (1, 2, 3).

5. Доказать, что для любого А. (а)аъ.А1 1У; (б)еслиАЯа,тоЛ а;еслииаЛ, оА и; (в)ЛОО Л,Лйи О,АОУ* (Г,АйУ Л. б. Доказать, что существует лишь одно множество, ие имакииее злемйэггов. 7. Существуют ли такие множества А, В н С, что ЛйВ и а, АйС «а, (АйВ)1С «а7 3. Доказать, что множество всех корней миогочлена а(к) = «)У(х) у(х) есть объединение множеств корней многочленов ф(к) и у(х).

Ф. Доказать, что пересечение множеств действительных корней миоозчленов о(х) и )$(к) с действительными козффициентами совпадает с множеством всех действительных корней миогочлена у(х) * а (к) + )9 (х), 1Ф. Доказать„что Л Я В» ЛОВ «В «АйВ = А «А~В = о «(-Л)ОВ = У. 11. Доказать следующие тождества: (а) ЛОА «АйА «А; (б) ЛйВ «ВйЛ; (в) АОВ ВОА; (г) Лй(вйс) (Айв)йс; (д) ЛО(ВОС) «(АОВ)ОС; (е) Лй(ВОС) (АйВ)О(АйС); (ж) ЛО(Вйс) - (ЛОВ) й(АОС); (з) (АЙВ)О(СйР) = (АОС)й(ВОС)й(АОР)й(ВОР). $2.

Даиазитз еиеиующие тииаеетза: (з) -(А(ЪЗ) *» (-А)О(-З); (6) -(АШУ) - (-А)(Ъ(-В); (и) А Ъ (З()С) (А Ъ З)(Ъ(Л '( С); (т) Л '( (В(ЪС) - (Л ~ В)(З(Л ~ С);- ()О Л Ъ (А'Ъ,В) «А(ЪВ; (е) А ~ З Л ~ (А(ЪВ); (и) А(Ъ(в Ъ С) (А(ЪВ) Ъ (ЛйС) = (Лйв) 1 С; (з)(Л~В)~С-(А~С) ~(В~С); (и) А(.)В АО(В ~ Л)) (и) -(-А) А; (л) ЛО(-А) Р; (и) А(Ъ(-А) «а( (и) (А(ЪВ)(3 [А(Ъ(-В) ) (ЛОВ)(Ъ [А(.)(-в) ) А; (е) ((-Л)ОВ)(ЪА - А(ЪВ; (и) А(Ъ(В Ъ А) "- а; (р) (Л(.)В) '( С (Л ~ С)~)(В ~ С); » (е) А'Ъ(В~С) (А ~ В)О(Л(ЪС); (т)АЪ(ВУС) (А1В) ЪС.

»3 Деиззат~„ите: (а) АШУ ъ, С «А ~ С н В Я С; (б) Л ~ В(ЪС «А С В н Л ~ С; (з) Л(ЪВ )„С «Л [~ ( — В)ОС; (г) АСВ(.)с«ЛЩ-В) ~С; (и)(ЛВ)ив-л«в(-.л;' (е) (Л(ЪВ)(.)с Лй(ВОС) «С ~ Л; (и) А[ З» АОС~ В(.)с; (з) А ~. В:» А(ЪС )„В(ЪС; (и)Л1 В«(А~С)~(В~С); (и) А Я В»' (С Ъ В) ~ (С Ъ А); (и) А ~ В « -З С -Л; (и) Л(.)в = ЛХЪВ «А = В; (и) А -З«А(ЪВ» и нЛОВ = У. 14. Дииазать толщеетза: (з)А-В* З-А; (б) л-'(в-'с) (л-'в)-'с; (з) А(Ъ(З-С) «(Л(ЪВ)-'(Л/Ъс); (т) А-'(А-'В) * З; (и) А()В - Л-'В-*(ЛЛВ); (и) А Ъ В ' Л-(А(ЪВ); (и) А-а:= А; (з) А-Л = а; (н) А-И» — Л," (и) АОЗ (А-З)О(А(ЪЗ). ЧЛ. ТЕОРИЯ МНОЖЕСТВ 1о 15.

Доказать,что: (а) (А ()...ОА )-(В О...()В ) С (А,— В )О...О(Л вЂ” В„); (6) (А ()...Г)А )-'(В ()...()В ) С (А — 'В )().„(.)(А — 'В ). 16. Доказать,что: (а) А — 'В = о «» А = В; (6) А(1В = о ~ А(.)В = А-В. (в) А-'В = С «» В-'С = А «» С-'А = В. 17. Определить операции О, (), ~ через: (а) —, (1; (б) -', (.); (в) 1, —.

18'. Доказать, что нельзя определить: (а) ~ через С) и (.); (6) (.) через (') и ~. 19, Доказать, что множества образуют кольцо без единицы, где— играет роль операции сложения, а й играет роль операции умножения, Что является вычитанием в этом кольце? 20. Найти все подмножества множеств о, (о), (х), (1, 2) . 21. (а) Доказать, что множество из и элементов имеет 2 подмнои жеств. (6) Сколько подмножеств из й элементов имеет множество из и элементов (к «и)? 22. Доказать,что: (а) Р(АОВ) = Р(Л)ПР(В); (6) Р~ ПА.1 = й Р(А.'); 1)н) ! Ва) (в) Р(АОВ) = (Л ~.3В ~ А Е Р(Л) иВ ~=Р(В)); (г) Р( (.) А,~ = ~ () В, ~ В я Р(А.)~.

23. Доказать, что для любых а, Ь, с, и' ((а), (а, ЬЦ = ((с), (с, с()) «» а = с и Ь = с(. 24. Какие из утверждений верны для всех А, В и С? (а) Если А Е В и В Е С, то А Е С. (6) Если А С В и В Е С, то А Е С. (в) Если АйВ С вЂ” С и А(.)С С В, то АПС = и. (г) Если А м В и В «» С, то А м С. (д) Если А С -(В(.)С) и В С -(А (.) С), то В = о. » 1. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ 25.

Доказать, что для любых А, А, ..., А, «' еслиА СА С...СА СА,тоА =А =...=А. 1 2 '" л 1' 1 2 "' л' 26. Для каждого положительного целого числа н указать мно- жество А из и элементов такое, что если х,уЕА, то хЕу нли в и' у Е х, нли х = у. 27. Решить систему уравнений < А! !Х= В, А(.)Х = С, где А, В и С вЂ” данные множества и В С А С С. 28.

Решить систему уравнений А 1Х=В, Х1А=С, где А, В и С вЂ” данные множества и В С А, А! )С = а. 29. Пусть даны системы множеств (А.) . и (В,3.~, где 1 — некото- рое множество. Решить системы уравнений: (а) АРХ = ВР 1' е 1; (б) А,ОХ = В., ! Е 1.

При каких А и В эти системы имеют решения? ! 30. Решить систему уравнений < А '1 Х = В, А(.)Х = С, где А, В и С вЂ” данные множества и В С А С С. 31. Показать, что: (а) А = В «» (А 1 В)(.)(В '1 А) = а; (б) любое уравнение относительно множества Х, в правой части которого стоит а, равносильно уравнению (А()Х)(.) (Вй(-Х) 1 = а, где А и  — некоторые множества, в записи которых не содержится символ Х; (в) система уравнений с А('1Х = а, В()(-Х) = а имеет решение тогда и только тогда, когда В С -А; при этом условии решением системы является любое множество Х такое, что ВСХС; -А; (г) описать метод решения системы уравнений с одним неизвестным.

12 Ч.1, ТЕОРИЯ МНОЖЕСТВ 32. Пользуясь методом задачи 31, решить следующие системы: 1АОХ = В(1Х, (а) 1АТ)Х = СОХ; (б) 6 ~Х1А ~ С1Х; 1АТ)Х = В 1 Х, ~СОХ = Х'1 А. При каких А, В и С эти системы имеют решение? 33. Доказать, что всякое множество есть: (а) обьединение всех своих подмножеств; (б) объединение всех своих конечных подмножеств; (в) объединение всех своих одноэлементных подмножеств. 34. Пусть имеется последовательность множеств Х02Х12Х22" ° 2Х 2 °" Доказать, что пересечение любой бесконечной подпоследовательности этих множеств совпадает с пересечением всей последовательности. 35.

Пусть имеется последовательность множеств Доказать, что объединение любой бесконечной подпоследовательности этих множеств совпадает с объединением всей последовательности. 36. Доказать следующие тождества: (а) О О А„,=О О А„; 2ЕК 1ЕТ 1ЕТ 1ЕК (б) () () А () Т) АН; 1ЕХ 1ЕТ ГЕТ ЙЕК (в) — ~ О Ак~ () ( Аь) (,/сЕХ / 1ЕК (г) — ~ () А21 = () (-А ); (2ЕК / 1ЕК (д)0 А 0 ОВ = 0 (АОВ„); 1ЕК 2ЕК 1ЕК (е) О (ВГИКА)=В(1( ОА 1ЕК 12ЕК (ж)() (ВОА) ВО( ()А 1ЕК 1 ЙЕК (з 5 2.

ОТНОШЕНИЯ И ФУНК((ИИ 37. (а) Доказать, что для любых К, Т, А„ О ЙАи С() ОА Йех !Ит (нт ьиА' (б) Доказать, что в утверждении (а) включение нельзя заменить равенством. 38. Доказать,что: (а) еслиА С. Валя всех (Е Т, то О А С В; !нт (б) еслиВйА для всех ! Е Т,тоВ С йА; !нТ (в) еслиА С; В для всех (Е Т, то О А С О В и () А С () В. !ет !ет !ет !ет 39. Доказать, что: (а) О А, есть наименьшее множество, содержащее все мно- !ЕТ жества А; (б) () А есть наибольшее множество, содержащееся во всех мно!ит жествах А . 40.

Доказать, что если ( Т) А ) () ( () Ви) = !з, то ии и !(0) неХ!(0! А С О (А ()(В !В)), ин 4'~(0) ие 4'Ц5 где ( О А)О( О В)СВ. 41. Доказать, что для любой системы множеств А,, ..., А, ... суп ществует система попарно непересекающихся множеств В,, ..., В, ... и такая,чтоО А =О В и В СА. и и и и не 4' ин+ ф 2. Отношения и Функции Прямым ( декартовым ) произведением множеств А, ..., А на!' ''' и зывается множество А,х...хА =((а,,...,а)~а(ЕА,,...,а„ЕАи). Если А = ... = А = А, то множество А х ... х А называется ! "' и ! "' и прямой степенью множества А и обозначается через А", !4 Ч.С.

ТЕОРИЯ МНОЖЕСТВ Бинарным отношением между элементами множеств А и В называется любое подмножество Я множества А х В, Если А = В, то отношение называется бинарным отношением на А. Вместо (х, у) Е Я часто пишут хЯу. Областью определения бинарного отношения Я называется множество д = (х ~ существует у такое, что (х, у) Е Я) . Областью значений бинарного отношения Я называется множество р = (х ) существует у такое, что (у, х) Е Я).

Для бинарных отношений определены обычным образом теоретико-множественные операции объединения, пересечения и т. д. Дополнением бинарного отношения Я между элементами А и В считается множество -Я = (А х В)1 Я. Обратным отношением для бинарного отношения Я называется множество Я с = ((у х) ЕЯ). Образом множества Х относительно Я называется множество Я(Х) = (у ) существует х Е Х такое, что (х, у) Е Я), прообразом Х относительно Я называется Я (Х).

Произведением отношений Я СА х В и Я СВ х С называется 1 2 отношение Я, Я = ((х, у)) существует гтакое, что(х, г)еЯ, н(г, у)еЯ ). Отношение г называется функцией из А в В (из А на В), если д = А, рг>--В (соответственно р = В) и для всех х, у,, у из (х, у )Е~' и (х, у )Е/ следует у = у . функция у из А в В обозначается У: А- В. Если с — функция, то пишем у = У(х) вместо (х, у)Е( и называем у значением функции < при значении аргументах.

Для любого множества А определяем<: А- А следующим образом: Л' с (х) — х. Функция г' называется 1 — 1-функцией, если для любых х, х, у из !' 2' того, что у = У(хс) и у = г(х ), следует х = х . Говорят, что функция Р. А ~ В осуществляет взаимно од><означное соответствие между А и В если д = А, р = В иУ вЂ” 1-1-функция. Взаимно однозначное соот»' ' ' ветствиеУ: А- А называется подстановкоймножества А. й г. отношкния и еункции 15 Множество всех функций из А в В обозначается через В~. Декартовым произведением семейства множеств А, (гСЛ назы! вается множество ПА,= ~У~ В1- о А, и У(()еА длявсех (е1~. !Е( гав) Назовем и-местиым отнои~ением на множестве А любое подмножество множества А".

Функцию В А" В назовем и-местной функцией из множества А в В и будем писать у =Дх, ..., х ) вместо ) 1 у =у((х,, ..., х )) и называть у значением функции у нри значении аргументов х, ..., х„. 1. Доказать, что существуют А, В и С такие, что: (а) АхВ ы ВхА; (б) Ах(ВхС) ы (АхВ) хС, 2. Найти геометрическую интерпретацию следующим множеств: (а) (а, Ь!х(с, а(, где (а, Ь] и (с, а') — отрезки действительной прямой У; (б) (а, Ь)2; (в) (а, Ь]~; (г) ун. 3. Доказать, что если А, В, С н Р не пусты, то: (а) АСВ и ССР ч» Ах ССВх 0; (6) А=В и С=Р ч АхС=Вх.0.