 |
Отношение. Прямое произведение множеств. Примеры
|
|
|
|
Понятие множества. Основные принципы интуитивной теории множеств. Парадокс Рассела
Это из раздела теории множеств. Существует интуитивное и формальное понятие мн-ва. Согласно Кантору, под мн-вом будем понимать любое собрание определенных и различимых м-у собой объектов, мыслимых как единое целое. Сами объекты называются элементами мн-ва. xÎX (элемент принадлежит мн-ву). xÏX (не принадлежит множеству).
Интуитивный принцип объемности. Множества A и B называются равными, если состоят из одних и тех же элементов. (A=B, A¹B). (напр., A={1,2,3,4}, B={1,2,{3,4}}, A¹B). Кантор ввел понятие формы от C. Под формой будем понимать конечную последовательность, состоящую из слов и символа х, такую, что при подстановке вместо х имени какого-нибудь предмета, получается истинное или ложное высказывание. (напр., ²3 делится на х без остатка². При х=3 или 9, истинно. При х=10 или 8, ложно. Форма от х обозначается как R(х).
Интуитивный принцип абстракции. Любая форма R(х) определяет некое мн-во A, а именно мн-во тех и только тех предметов, для которых R(а) - истинное предложение. Для мн-ва A, определяемого формой R(х) принято обозначение A={x|P(x)|}. (напр., {x| x<3}={1,2}. {x|x - четное} - мн-во четных чисел.
Несовершенство интуитивных представлений о мн-вах иллюстрируется парадоксом Б.Рассела: рассмотрим множество A, состоящие из всех таких множеств X, которые не являются элементами самого себя. Тогда, если AÎAè AÏA и обратно AÏA è AÎA.
Операции над множествами. Основные тождества
АÍВ. - отношение включения (каждый элемент из А - есть элемент из В). (А-подмн-во В)
Если AÍB и A¹B, то A - собственное подмножество B, пишется AÌB
А=Æ - пустое множество (нет элементов). Оно подмножество любого множества.
|
|
|
Множество всех подмножеств A - множество-степени, обозначается R(А).
АÈB = {x|xÎA или xÎB} - объединение множеств.
АÇВ = {x | xÎA и xÎB} - пересечение множеств.
Х\А = {x | xÎX, x Ï A} - относительное дополнение A до Х.
(не) A = {x | xÎU, Ï A} – абсолютное дополнение (U – универсальное множество)
А+В = (A\B)È(B\A) - симметрическая разность.
Абсолютное дополнение мн-ва A - множество всех тех элементов х, которые не принадлежат множеству A. = U\X.
A+B= (AUB)\(AÇB); A\B=AÇ(не)B
Для любых подмножеств A, В, C и универсального множества U выполняются след. Тождества (основные тождества алгебры множеств):
1. AÈB=BÈA (коммутативность È); 2. AÈ(BÈC)=(AÈB)ÈC (ассоциативность UÈ); 3. AÈ(BÇC)=(AÈB)Ç(AÈC) (дистрибутивность È относительно Ç); 4. AUA=A; 5. АÈU=U. 6. AÈ(ØA)=U; 7. AÈÆ=A; 8. Ø(AÈB)= (ØA)Ç(ØB) (закон де Моргана); 9. AÈ(AÇB)=A (закон поглощения)
1¢. АÇВ = BÇА; 2¢. АÇ(ВÇС)=(АÇВ)ÇС; 3¢. АÇ(ВÈС)=(АÇВ)È(АÇС); 4¢. AÇA=A; 5’. АÇU=A; 6’. AÇØA=Æ. 7’. AÇÆ=Æ; 8’. Ø(AÇB)= (ØA)È(ØB). 9¢. AÇ(AÈB)=A.
Докажем, к примеру, 3. Сначала покажем, что AÈ(BÇC)Í(AÈB)Ç(AÈC). Действительно, если хÎАÈ(BÇC), то хÎА или хÎВÇС. Если хÎА, то хÎАÈВ и хÎАÈС. Þ х Î(АÈВ)Ç(АÈС). Если хÎВÇС, то хÎВ и хÎС. Отсюда хÎВÈА и хÎСÈА, а значит, хÎ(АÈВ)Ç(АÈС). Теперь покажем, что (АÈВ)Ç(АÈС)ÍАÈ(ВÇС). Если хÎ(АÈВ)Ç(АÈС), то хÎАÈВ и хÎАÈС. Следовательно, хÎА или хÎВ и хÎС, т.е. хÎВÇС. Отсюда хÎАÈ(ВÇС), что и требовалось доказать.
Утверждение 2. Предложения о произвольных множествах A и B попарно эквивалентны:
1) АÍВ. 2) АÇВ=А. 3) АÈВ=В. Докажем, что из первого предложения следует второе. Действительно, т.к. АÇВÍА, то достаточно показать, что в этом случае AÍAÇB. Но если xÎA, то xÎB, т.к. АÍВ, и, следовательно, x Î AÇB. ч.т.д. Доказательство 1à3 аналогично.
|
|
|
Отношение. Прямое произведение множеств. Примеры
Отношением r между элементами множества A и элементами множества B называется произвольное мн-во упорядоченных пар <a,b>, где aÎA, bÎB; иными словами, r есть подмножество прямого произведения АхВ, т.е. rÍAxB. Если <a,b>Îr, то говорят, что элемент, а находится в отношении с элементом b, и пишут arb. Если A=B, то отношение r называется бинарным отношением на множестве А. Напр., r={<1,1>,<1,2>,<2,3>} - бинарное отношение на множестве {1,2,3}. Областью определения отношения называется подмножество D(r) = {x Î A | существует yÎB такое, что <x,y>Îr} множества А. Областью значений отношения r-R(r)={yÎB | существует хÎА такое, что <x,y>Îr}. Отношением, обратным отношению rÍAxB, называется отношение r-1={<y,x>|<x,y>Îr}; при этом r-1ÍBxA. Очевидно, D(r)=R(r-1), R(r)=D(r-1). Композицией отношений rÍAxB и бÍBxC называется отношение б°r = {<x,z> | существует уÎВ такое, что <x,y>Îr и <y,z>Îб}. Очевидно, что б°rÍAxC. Это определение соответствует определению сложной функции: если значения функции y=f(x) принадлежат области определения функции z=g(y), то сложная функция определяется равенством z=g(f(x)). Пусть r - бинарное отношение на множестве А. Тогда говорят, что:
1) r рефлексивно, если хrх для любого хÎА
2) r симметрично, если хrу влечет уrх для любых х, у ÎА
3) r транзитивно, если хrу и уrz влекут хrz для любых... из А.
4) r антисимметрично, если хrу и уrх влекут х=у для любых х,уÎА.
5) Отношением эквивалентности называется рефлексивное, симметричное и транзитивное бинарное отношение.
Прямым произведением множеств Х и У называется совокупность всех упорядоченных пар <x,y> таких, что xÎX, yÎY. Обозначается как X´Y. Прямым произведением множеств X1....Xn называется совокупность всех упорядоченных n-ок <x1.....xn> таких, что xiÎXi, i=1,....,n.
Cв-ва:(AÇB)x(CÇD)=(AxC)Ç(BxD).Если поменять Ç с È то равенство выполняться не будет. Пусть <x,y>Î(AÇB)x(CÇB)ÞxÎ(AÇB), yÎ(CÇD) Þ xÎA и XÎB, yÎC и yÎD => xÎA, yÎC и xÎB, yÎDÞ<x,y>Î(AxC) и <x,y>ÎBxDÞ<x,y>Î(AxC)Ç(BxD).
(AxC)Ç(BxD)=(AÇB)x(CÇD). Д-во аналогично.
|
|
|
