Релацијата на множество еквивалентност ги има следните својства. Релација на еквивалентност. Односите на еквивалентност и ред
Прибелешка: Опишани се многу нови концепти, како што се релацијата еквивалентност, односот со парцијален ред и изоморфните парцијални множества. Неколку теореми на оваа тема се докажани со детални објаснувања, графикони и примери. Дадени се голем број примери на делумни нарачки. Опишани се неколку конструкции кои овозможуваат да се конструираат нарачани комплети од други. Предавањето се карактеризира со многу задачи за самостојно решавање
Односите на еквивалентност и ред
Да ве потсетиме дека бинарна врскана множество се нарекува подмножество; наместо 
често пишуваат.
Бинарна релација на множество се нарекува еквивалентност, доколку се исполнети следниве својства:
Следната очигледна, но често користена изјава е вистинита:
Теорема 11. (а) Ако множеството е поделено во заедница од разединети подмножества, тогаш релацијата „да лежи во истото подмножество“ е релација на еквивалентност.
(б) Било што еквивалентностсе добива на опишаниот начин од некоја партиција.
Доказ. Првата изјава е сосема очигледна; Ќе дадеме доказ за второто за да може да се види каде се употребени сите точки од дефиницијата за еквивалентност. Значи, нека биде релација на еквивалентност. За секој елемент, разгледајте го класа на еквивалентност- множеството на сите за кои е точно.
Да докажеме дека за две различни , таквите множества или не се сечат или се совпаѓаат. Нека се сечат, односно имаат заеднички елемент. Потоа и , од каде (симетрија) и (транзитивност), како и (симетрија). Според тоа, за било кој од него следи (транзитивност) и обратно.
Останува да се забележи дека, поради рефлексивноста, секој елемент припаѓа на класата што ја дефинира, односно целото множество е навистина поделено на дисјунктни класи.
78. Покажете дека барањата за симетрија и транзитивност можат да се заменат со едно: (притоа задржувајќи го барањето за рефлексивност).
79. Колку различни релации на еквивалентност постојат на множеството 
?
80. На множеството се дадени две еквивалентни релации, означени со и , имајќи и класи на еквивалентност, соодветно. Дали нивното вкрстување ќе биде еквивалентна релација? Колку часови може да има? Што можете да кажете за обединување на односите?
81. (Ремзиова теорема) Множеството од сите - елементарни подмножества на бесконечно множество се дели на класи (, - природни броеви). Докажете дека постои бесконечно множество, чиишто елементарни подмножества припаѓаат на иста класа.
(Ова е очигледно: ако бесконечно множествосе дели на конечен број класи, тогаш една од класите е бесконечна. Кога и изјавата може да се формулира на следниов начин: од бесконечна група луѓе може да се изберат или бесконечно многу познаници во пар или бесконечно многу странци во пар. Конечната верзија на оваа изјава - дека меѓу кои било шест лица има или три познаници во пар или тројца странци во пар - е добро познат проблем за учениците од училиштата.)
Се нарекува множеството класи на еквивалентност фактор - многумножества по однос на еквивалентност. (Ако релацијата е конзистентна со дополнителни структури на , добиваме факторски групи, факторски прстени итн.)
Релации на еквивалентност ќе се сретнеме повеќе пати, но засега главна тема ни се односите на редот.
Бинарна релација на множество се нарекува однос на делумен ред, доколку се исполнети следниве својства:
(Следејќи ја традицијата, ние користиме симбол (наместо буква) како знак на релација за ред. делумно нарачана.
Велат дека два елементи делумно нарачанамножества споредливи, ако или . Забележете дека дефиницијата за делумен ред не бара кои било два елементи од множеството да бидат споредливи. Со додавање на ова барање, ја добиваме дефиницијата линеарен редослед (линеарно подредено множество).
Еве неколку примери на делумни нарачки:
- Нумерички множества со вообичаена релација за редослед (тука редоследот ќе биде линеарен).
- На множеството од сите парови реални броеви можеме да воведеме делумна нарачка, со оглед на тоа , ако и . Овој ред повеќе нема да биде линеарен: паровите не се споредливи.
- На збир на функции со вистински аргументи и вредности, можете да внесете делумна нарачка, имајќи предвид дека ако
пред сите. Овој редослед нема да биде линеарен. - На множеството позитивни цели броеви, можеме да го одредиме редоследот земајќи го предвид дека , ако дели . Овој редослед исто така нема да биде линеарен.
- Релацијата „било кој прост делител на број е и делител на број“ нема да биде редовна врска на множеството позитивни цели броеви (таа е рефлексна и преодна, но не и антисиметрична).
- Нека биде произволен сет. Потоа, на множеството од сите подмножества од множеството, релацијата за вклучување ќе биде делумен редослед.
- На буквите од руската азбука, традицијата одредува одреден редослед (). Овој редослед е линеарен - за кои било две букви можете да кажете која е прва (ако е потребно, гледајќи во речникот).
- Дефинирано со зборови од руската азбука лексикографскиред (како во речник). Може формално да се дефинира на следниов начин: ако зборот е почеток на зборот, тогаш (на пример, ). Ако ниту еден од зборовите не е почеток на друг, погледнете ја првата буква по редослед по кој се разликуваат зборовите: тогаш зборот каде што оваа буква е помала по азбучен ред ќе биде помал. Овој редослед е исто така линеарен (инаку што би правеле компајлерите на речник?).
- Релацијата за еднаквост () е исто така однос на делумен ред, за кои не се споредливи два различни елементи.
- Сега да дадеме секојдневен пример. Нека има многу картонски кутии. Дозволете ни да воведеме ред на него, имајќи предвид дека ако кутијата се вклопува целосно во кутијата (или ако и е истата кутија). Во зависност од множеството кутии, овој редослед може или не може да биде линеарен.
ВРСКА
Врските се кореспонденции помеѓу елементи од истото множество, односно кореспонденции чии основни множества се совпаѓаат:
x A, y Aстав Г = ((x,y)| P(x,y)), P(x,y)некаков исказ (прирок).
Ако (x,y) Г,тогаш тие велат дека Xсе во врска ГДо на.
На пример, да се има ист остаток (за бројки), да се биде на исто растојание од линија (за точки), семејни односи или односи со соседите (за многу луѓе).
Построга дефиниција:
Бинарна релација е две множества:
1) потпорен сет А,
2) множество од парови Г=((x,y)| x A, y A), што е подмножество од квадратот на потпорното множество.
n-ary релација или n-ary (тројна, кватернарна, ...) релација е потпорно множество Аи множества со тократна димензија n, што е подмножество од множеството А n.
Пример за тројна врска: да се биде дел од „трите играчи“.
Ако релацијата едноставно се разбере како множество од множества (без потпорно множество), тогаш може да се користат сите закони на теоријата на множества. Универзалното множество ќе биде квадратот на потпорното множество, односно множеството од сите можни торки (кога секој елемент е во однос на секој друг елемент).
Релацијата може да се дефинира и како двоместо предикати на објектни променливи x, y, кој ја зема вредноста „точно“ ако (x, y) Ги лажни ако не припаѓа.
Ознаки: (x, y) Г, у = Г(x), у = Гxили едноставно xGu, на пример, односот на еднаквост (x = y), однос на нарачка (Х< у) .
Ако (x, y) Г, Тоа xGuја зема вредноста „точно“, во спротивно - „неточно“.
Ако односите се наведени на дискретно множество, тие можат да бидат напишани во форма на матрица
A i, j = 
Релацијата е посебен случај на кореспонденција; за неа можете да воведете инверзни односи, состав на односи:
Г -1 =((y,x)| (x,y) Г), Г ◦ Δ = ((x,z) | y ((x,y) Г &(y,z Δ))).
Тие го воведуваат концептот на „единичен елемент“ Δ 0 = ((x, x)) - „да се биде во однос на себе“. Во матричното претставување ова ќе биде главната дијагонала).
Својства на бинарни односи
1 Рефлексивност – „да се биде во однос со себе“
xGx - точно(на пример, врски x=x, x≤x, x≥x).
2 Анти-рефлексивност - „да не биде во врска со себе“
xGx - лага(на пример, врски x≠x, x
Ако множеството не е „рефлексивно“, тоа не значи дека е „антирефлексивно“.
3 Симетрија „Независност кој елемент е прв, а кој втор“
хГу – вистина → уГх – вистина(на пример, врски x=y, x≠y).
4 Антисиметрија „да не се надмине“
(xGy – точно) & (yGx – точно) → (x=y) (на пример, релации x≤y, x≥y).
5 Асиметрија (не-симетрија) "надминат"
xGy – точно → yGx – неточно (на пример, врски X<у, х>на).
6. Транзитивност "преносливост"
(xГу – точно) и (yГz – точно) → (хГz – точно)(на пример, врски x=y, x<у, х>y, x≤y, x≥y, став x≠yнема транзитивност).
ПОСЕБНИ БИНАРНИ ОДНОСИ
Да ги разгледаме „односот на еквивалентност“, „релацијата на нестрог ред“, „односот на строг ред“ и „односот на доминација“.
Релација на еквивалентност
Релацијата еквивалентност е рефлексивно(x~x), симетрични ((x~y)=(y~x)), транзитивен ((x~y)&(y~z)→(x~z)) став.
Примери: еднаквост, идентитет, еквивалентност на множества, еквивалентност на логички искази, сличност на геометриски фигури, паралелизам на прави, но нормалноста на правите не е еквивалентна врска.
Се нарекува подмножество елементи што се еквивалентни на еден елемент класа на еквивалентностили поврзана класа.
Секој елемент од класата се нарекува претставник на класа.
Својства.
Сите елементи во класата се еквивалентни еден на друг.
Елементите од различни класи не се еквивалентни.
Еден елемент може да припаѓа само на неговата класа.
Целиот сет може да се претстави како унија на класи.
Така, збир на класи на еквивалентност или целосен систем на класи формираат партиција на придружното множество. Потсетување: партиционирањето на множеството претставува негово претставување како разединети подмножества.
Индекс на партиции– број на еквивалентни класи.
Факторски сетво однос на релацијата еквивалентност, ова е множество од сите класи или претставници на една класа.
Кардиналноста на множеството фактори е еднаква на индексот на поделба.
Нарачајте односи
Релацијата за ред се однесува на два вида бинарни односи.
Став лабав реднаречен рефлексивен (x≥x), антисиметрични ((x≤y)&(y≤x)→ (x=y)), транзитивен ((x≥y)&(y≥z)→(x≥z)) став.
Велат дека комплетот има лабав редослед. Концептите ≤ , ≥ имаат пошироко значење: нема полошо - нема подобро, не порано - не подоцна итн. Во теоријата на множества, пример за нестрог редослед е нестрогото вклучување (што е подмножество на друго множество0.
Став строг реднаречен анти-рефлексивен ((Х
((x>y)&(y
Велат дека комплет има строг ред. Во концепти< , >тие имаат пошироко значење: полошо е подобро, порано е подоцна итн. Во теоријата на множества, пример за строг редослед е строгото вклучување (да се биде подмножество на друго множество без да биде еднакво на него).
Нарачани комплети
Сетот се вика линеарно подредени, ако некој елемент може да се спореди (односно да речеме: поголем од, помал или еднаков на).
Множество од реални или цели броеви: класични примери на подредено множество.
Ако е можно да се воспостави релација поредок на множество, но не за сите парови на елементи, тогаш таквото множество се нарекува делумно нарачана.
Ова е збир на вектори, множество од сложени броеви, множества во теоријата на множества. Во некои случаи може да кажеме „повеќе е помалку“ или „биди супермножество и подмножество“, но не во сите случаи.
Поврзани дефиниции
Множеството од сите класи на еквивалентност се означува со .
Примери на еквивалентни односи
Покомплексен пример, но апсолутно витален:
Кога лекарот ви препишува лек, тој всушност во рецептот ја наведува класата на еквивалентни лекови; тој не може да наведе целосно специфична копија од пакувањето таблети или ампули. Оние. Сите видови на лекови се поделени во класи според еквивалентни односи. Да не беше овој факт, модерната медицина едноставно не би била можна.
Така, сите видови рецепти за салати и коктели, ГОСТ и класификатори, исто така, ги одредуваат виталните односи на еквивалентност. Односите на еквивалентност го исполнуваат целиот наш живот и не се апстрактна забава за математичарите.
Факторизација на мапирањата
Множеството класи на еквивалентност што одговараат на релацијата на еквивалентност се означува со симболот и се нарекува фактор-множестворелативно . Покрај тоа, субјективното мапирање
повикани природен приказ(или канонска проекција) до множеството на фактори.
Нека , се множества, се пресликување, а потоа бинарната релација дефинирана со правилото
е еквивалентна релација на . Во овој случај, мапирањето индуцира мапирање дефинирано со правилото
или, што е истото,
.Во овој случај излегува факторизацијапресликувања на сурјективно пресликување и инективно пресликување.
Факторизацијата на мапирањето е широко користена во хуманистичките науки и во оние области на технологијата каде што не е можно да се користат нумерички вредности. Факторизацијата на мапирањето ви овозможува да правите без формули каде што формулите не можат да се користат. Ајде да дадеме пример кој ќе биде разбирлив за секого и не бара разбирање на сложена математичка симболика.
Училишниот распоред е типичен пример за факторизација. Во овој случај, множеството на сите ученици во училиштата, збирот на сите академски предмети, дистрибуирани по ден во неделата, наведувајќи го времето на часовите. Еквивалентните часови се класи (групи ученици). Приказ – распоред на часови прикажан во ученичките дневници. Приказ - распоред на часови објавен во фоајето на училиштето. Тука има и приказ - списоци на класи. Овој пример многу јасно ги покажува практичните придобивки од факторизацијата: невозможно е да се замисли распоредот на часовите како табела што ги одразува сите ученици од училиштето поединечно. Факторизацијата овозможи да се прикажат информациите што им се потребни на студентите во компактна форма погодна за употреба во ситуации кога формулите не можат да се применат.
Сепак, придобивките од факторизацијата не се ограничени на ова. Факторизацијата овозможи поделба на работата помеѓу учесниците во активноста: раководителот составува распоред, а учениците го запишуваат во своите дневници. Слично на тоа, факторизацијата на рецептите овозможи поделба на работата помеѓу лекарот, кој ја поставува дијагнозата и го пишува рецептот, и фармацевтот, кој обезбедува еквивалентност на препишаните лекови. Апотеозата на факторизацијата е подвижната лента, која ја спроведува максималната поделба на трудот преку стандардизација на деловите.
Но, придобивките од факторизацијата не се ограничени на ова. Факторизацијата овозможи да се обезбеди модуларност на модерната технологија, што и дава невидена флексибилност на функциите. Можете да ја задржите старата SIM-картичка и да купите сосема нов телефон за да ја користите или да вметнете нова видео меморија во вашиот стар компјутер. Сето ова е флексибилност, модуларност, која се заснова на факторизација.
Литература
- A. I. Кострикин, Вовед во алгебра. М.: Наука, 1977, 47-51.
- А.И. Малцев, Алгебарски системи, М.: Наука, 1970, 23-30.
- V. V. Иванов, Математичка анализа. НСУ, 2009 година.
исто така види
- Односот на толеранција е ослабена форма на еквивалентност.
- Еквивалентноста е логична операција.
Фондацијата Викимедија. 2010 година.
- Болничка пневмонија
- Мител
Погледнете што е „однос на еквивалентност“ во другите речници:
еквивалентност- - Теми за телекомуникации, основни поими EN еквивалентна врска... Водич за технички преведувач
Релација тип на еднаквост- однос на еквивалентност, концепт на логика и математика, изразувајќи го фактот за присуство на исти знаци (својства) во различни предмети. Во однос на таквите заеднички карактеристики, овие различни предмети не се разликуваат (идентични, еднакви,... ...
Став на толеранција- Овој термин има други значења, видете Толеранција. Релација на толеранција (или едноставно толеранција) на множество е бинарна релација која ги задоволува својствата на рефлексивноста и симетријата, но не мора... ... Википедија
Сооднос (математика)- Овој термин има други значења, видете Став. Релацијата е математичка структура која формално ги дефинира својствата на различни објекти и нивните односи. Врските обично се класифицираат според бројот на објекти кои се поврзани... Википедија
СТАВ- во логиката, нешто што, за разлика од својството, карактеризира не посебен предмет, туку пар, три итн. предмети. Традиционалната логика не го сметаше О.; во современата логика O. е пропозициска функција од две или повеќе променливи. Бинарни... Филозофска енциклопедија
Преференциска врска- во теоријата на потрошувачите, ова е формален опис на способноста на потрошувачот да споредува (нарачува по желба) различни групи на стоки (потрошувачки комплети). За да се опише односот на претпочитање, не е неопходно да се измери пожелноста... ... Википедија
Став (филозофски)- Став, филозофска категорија која ја изразува природата на распоредот на елементите на одреден систем и нивната меѓузависност; емоционално-волевен став на една личност кон нешто, т.е., израз на неговата позиција; ментална споредба на разни предмети... ... Голема советска енциклопедија
став- ВРСКА е збир од подредени n ok поединци (каде n е 1), т.е. двајца, тројки итн. Бројот n се нарекува „локалитет“ или „аритет“, О. и, соодветно, тие зборуваат за n локално (n арно) О. Така, на пример, двојно О. се нарекува... ... Енциклопедија на епистемологијата и филозофијата на науката
Став- I Став е филозофска категорија која ја изразува природата на распоредот на елементите на одреден систем и нивната меѓузависност; емоционално-волевен став на една личност кон нешто, т.е., израз на неговата позиција; ментална споредба на различни... ... Голема советска енциклопедија
Класа за еквивалентност- Релација на еквивалентност () на множество X е бинарна релација за која се исполнети следните услови: Рефлексивност: за кое било a во X, Симетрија: ако, тогаш, Транзитивност: ако... Википедија
Книги
- Донесување финансиски одлуки во услови на компаративна несигурност: Монографија, Бајук О.А.. Во монографијата е развиена и теоретски поткрепена нова логичка стратегија на одлучување при изборот меѓу неспоредливи објекти, со што се воспоставува посебен однос на предност и...
I. Поделба на паралелки. Релација на еквивалентност
Дефиниција 2.1. Да ги наречеме заменливи оние и само оние објекти од даденото множество M кои го имаат истиот сет на формални карактеристики кои се суштински во дадена ситуација.
Да го означиме со M x множеството од сите објекти кои се заменливи со објектот x. Очигледно е дека x M x и заедницата на сите M x (за сите можни x од M) се совпаѓаат со целосното множество M:
Ајде да се преправаме дека. Ова значи дека има некој елемент z таков што истовремено припаѓа на и и. Значи, x е заменлив со z, а z е заменлив со y. Според тоа, x е заменлив со y, а со тоа и со кој било елемент на. Така. Обратно префрлување е прикажано на ист начин. Така, множествата што се појавуваат во унијата (2.1) или не се сечат или целосно се совпаѓаат.
Дефиниција 2.2. Ќе го наречеме систем од непразни подмножества (M 1, M 2,….) од множество M партиција на ова множество ако
Самите множества се нарекуваат класи на партиции.
Дефиниција 2.3. Релацијата c на множеството M се нарекува еквиваленција (или еквивалентна врска) ако постои партиција (M 1, M 2,...) од множеството M таква што (x, y) важи ако и само ако x и y припаѓаат на некоја општа класа M i на дадена партиција.
Нека (M 1 , M 2 ,….) е партиција на множеството M. Врз основа на оваа партиција ја дефинираме релацијата од c до M: (x, y), ако x и y припаѓаат на некоја општа класа M i на оваа партиција. Очигледно релацијата со е еквивалентност. Да повикаме со еквивалентната релација што одговара на дадената партиција.
Дефиниција 2.4. Ако во секое подмножество M i го избереме елементот x i содржан во него, тогаш овој елемент ќе се нарече стандард за секој елемент y вклучен во истото множество M i. По дефиниција, да претпоставиме дека релацијата c* „да се биде стандард“ (x i, y) е исполнета
Лесно е да се види дека еквивалентноста c што одговара на дадена партиција може да се дефинира на следниов начин: (z, y) ако z и y имаат заеднички стандард (x i, z) и (x i, y).
Пример 2.1: Да се земе како M множеството од ненегативни цели броеви и да се земе неговата поделба во множеството M 0 од парни броеви и множеството M 1 од непарни броеви. Соодветната релација на еквивалентност на множеството цели броеви е означена на следниов начин:
и гласи: n е споредлив со m модуло 2. Природно е да се избере 0 за парни броеви и 1 за непарни броеви како стандарди. Слично, делејќи го истото множество M на k подмножества M 0, M 1,... M k-1, каде што M j се состои од сите броеви кои кога се делат со k даваат остаток j, доаѓаме до еквивалентната релација:
што важи ако n и m имаат ист остаток кога се делат со k.
Природно е да се избере соодветниот остаток j како стандард во секој M j.
II. Факторски сет
Нека е еквивалентна релација. Потоа, според теоремата, постои поделба (M 1, M 2,....) на множеството М на класи на елементи еквивалентни едни на други - таканаречените класи на еквивалентност.
Дефиниција 2.5. Множеството класи на еквивалентност во однос на релација се означува со M/ и се чита како количник множество од множеството M во однос на релација.
Нека μ: M > S е сурјективно пресликување на множеството M на некое множество S.
За кое било μ: M > S - сурјективно пресликување постои еквивалентна врска на множеството M така што M/ и S може да се стават во кореспонденција еден на еден.
III. Еквивалентни својства
Дефиниција 2.6. Релацијата c на множеството М се нарекува еквивалентна врска ако е рефлексна, симетрична и преодна.
Теорема 2.1: Ако врската c на множеството M е рефлексна, симетрична и транзитивна, постои поделба (M 1 , M 2 ,….) од множеството M таква што (x, y) важи ако и само ако x и y припаѓаат на некоја општа класа M i на дадена партиција.
Спротивно на тоа: Ако е дадена партиција (M 1, M 2,...) и бинарната релација c е дадена како „припаѓа на општата класа на партиција“, тогаш c е рефлексивна, симетрична и транзитивна.
Доказ:
Размислете за рефлексивна, симетрична и преодна врска c со M. Нека било кој се состои од сите z за кои (x, z) c
Лема 2.1: За било кој x и y, или или
Од лемата и рефлексивноста на релацијата c произлегува дека множествата на формата формираат партиција на множеството M. (Оваа партиција природно може да се нарече партиција што одговара на оригиналната релација). Нека сега (x, y) в. Ова значи дека y. Но, исто така, x врз основа на (x, x) c. Затоа, двата елементи се вклучени во. Значи, ако (x, y) c, тогаш x и y се вклучени во општата класа на партиции. Спротивно на тоа, нека u и v. Да покажеме дека (u, v) c Навистина, имаме (x, u) c и (x, v) c. Оттука, по симетрија (u, x) в. Според транзитивноста, од (u, x) c и (x, v) c следи (u, v) c. Првиот дел од теоремата е докажан.
Нека е дадена партиција (M 1, M 2,….) од множеството M. унијата на сите класи на партицијата се совпаѓа со M, тогаш секое x е вклучено во некоја класа. Следи дека (x, x) c, т.е. s - рефлексивно. Ако x и y се во некоја класа, тогаш y и x се во иста класа. Тоа значи дека (x, y) c имплицира (y, x) c, т.е. односот е симетричен. Нека сега се (x, y) c и (y, z) c. Ова значи дека x и y се во некоја класа, а y и z се во некоја класа. Класите имаат заеднички елемент y, и затоа се совпаѓаат. Ова значи дека x и z се вклучени во класата, т.е. (x, z) важи и релацијата е преодна. Теоремата е докажана.
IV. Операции на еквиваленции.
Овде дефинираме некои теоретски операции на множества на еквиваленции и ги прикажуваме нивните важни својства без доказ.
Потсетиме дека врската е пар (), каде што М е множеството елементи што влегуваат во релацијата и е множество од парови за кои релацијата е задоволена.
Дефиниција 2.7. Пресекот на односите (c 1, M) и (c 2, M) е релацијата дефинирана со пресекот на соодветните подмножества. (x, y) со 1 со 2 ако и само ако (x, y) со 1 и (x, y) со 2 во исто време.
Теорема 2.2: Пресекот на еквиваленциите со 1 со 2 со 1 со 2 е само по себе еквивалентна релација.
Дефиниција 2.8. Унијата на односи (со 1, M) и (со 2, M) е релација дефинирана со унија на соодветните подмножества. (x, y) со 1 со 2 ако и само ако (x, y) со 1 или (x, y) со 2.
Теорема 2.3: За заедницата на еквиваленции со 1 со 2 да биде еквивалентна релација сама по себе, потребно е и доволно да
од 1 од 2 = од 1 од 2
Дефиниција 2.9. Директниот збир на односите (c 1, M 1) и (c 2, M 2) се нарекува сооднос). Директната сума се означува (c 1, M 1) (c 2, M 2).
Така, ако (c 1, M 1) (c 2, M 2) = (), тогаш M =.
Теорема 2.4: Ако, и односите се еквиваленции, тогаш директниот збир на односите (c 1, M 1) (c 2, M 2) = (), е исто така еквиваленција.
V. Видови односи
Дозволете ни да воведеме неколку поважни типови на односи. Примери ќе бидат дадени во третото поглавје.
Дефиниција 2.10. Релацијата c на множеството М се нарекува толеранција ако е рефлексивна и симетрична.
Дефиниција 2.11. Релацијата c на множеството М се нарекува релација од строг ред ако е антирефлексивна и транзитивна.
Дефиниција 2.12. Релацијата строг ред c се нарекува совршен строг редослед ако за кој било пар елементи x и y од M е точно или (x, y) или (y, x).
Дефиниција 2.13. Релацијата c на множеството М се нарекува релација со нестрог редослед ако може да се претстави во форма:
каде што има строг редослед на М, а Е е дијагонална релација.
Предавање 22. Односите на еквивалентност и редослед на множество
1. Релација на еквивалентност. Врската помеѓу еквивалентната релација и поделбата на множеството во класи.
2. Релација на ред. Релации со строги и нестроги поредоци, односи со линеарен ред. Подредување на комплети.
3. Главни заклучоци
Да го погледнеме множеството дропки X= (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) однос на еднаквост. Овој однос:
Рефлексивно, бидејќи секоја дропка е еднаква на себе;
Симетрично, бидејќи од фактот дека дропката м/nеднаква на дропка стр/q, следува дека дропката стр/qеднаква на дропка м/n;
Преоден, бидејќи од фактот дека дропката м/nеднаква на дропка стр/qи дропка стр/qеднаква на дропка р/с, следува дека дропката м/nеднаква на дропка р/с.
Релацијата на еднаквост на дропките се вели дека е еквивалентност.
Дефиниција. Релацијата R на множеството X се нарекува еквивалентна врска ако истовремено ги има својствата на рефлексивност, симетрија и транзитивност.
Примери за еквивалентни односи се односите на еднаквост на геометриските фигури, односот на паралелизам на правите (под услов да се совпаѓаат правите за паралелни).
Зошто овој тип на врска е издвоен во математиката? Размислете за односот на еднаквост на дропките дефинирани на множеството X= (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) (сл. 106). Гледаме дека множеството е поделено на три подмножества: (1/2, 2/4, 3/6), (1/3, 2/6), (1/4). Овие подмножества не се вкрстуваат, а нивната унија се совпаѓа со множеството X,тие. имаме партиција на множеството Xна часовите. Ова не е случајно.
Воопшто, ако е дадена релација на еквивалентност на множество X, тогаш таа генерира партиција од ова множество во парно разединети подмножества (класи на еквивалентност).
Така, утврдивме дека односот на еднаквост на множество дропки (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) одговара на поделбата на ова множество во класи на еквивалентност , од кои секоја се состои од еднакви дропки меѓу себе.
Вистина е и обратното: ако некоја релација дефинирана на множеството X генерира партиција на ова множество во класи, тогаш тоа е релација на еквивалентност.
Размислете, на пример, на сетот X =(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) односот „да се има ист остаток кога се дели со 3“. Таа генерира партиција од множеството Xво класи: едниот ќе ги вклучи сите броеви кои кога се делат со 3 оставаат остаток од 0 (тоа се броевите 3, 6, 9), вториот - броевите што кога се делат со 3 оставаат остаток од 1 (ова се броевите 1, 4 , 7 , 10), а во третиот - сите броеви, кога се делат со 3, остатокот е 2 (ова се броеви 2, 5, 8). Навистина, добиените подмножества не се сечат и нивната унија се совпаѓа со множеството X.Следствено, релацијата „имаат ист остаток кога се дели со 3“ дефинирана во множеството X,е еквивалентна релација. Забележете дека изјавата за врската помеѓу релацијата на еквивалентност и поделбата на множеството во класи бара доказ. Го спуштаме. Да речеме само дека ако една еквивалентна релација има име, тогаш на класите им се дава соодветното име. На пример, ако релацијата за еднаквост е наведена на множество отсечки (и тоа е еквивалентна врска), тогаш множеството отсечки е поделено на класи на еднакви отсечки (види Сл. 99). Односот на сличност одговара на поделбата на множество триаголници во класи на слични триаголници.
Значи, имајќи релација на еквивалентност на одредено множество, можеме да го поделиме ова множество на класи. Но, можете да го направите и спротивното: прво поделете го множеството на класи, а потоа дефинирајте еквивалентна релација, имајќи предвид дека два елементи се еквивалентни ако и само ако припаѓаат на иста класа на предметната партиција.
Принципот на поделба на множество во класи со користење на некоја еквивалентна релација е важен принцип на математиката. Зошто?
Прво, еквивалентно - ова значи еквивалентно, заменливо. Затоа, елементите од истата класа на еквивалентност се заменливи. Така, дропките кои се во иста класа на еквивалентност (1/2, 2/4, 3/6) не се разликуваат од гледна точка на односот на еднаквост, а дропката 3/6 може да се замени со друга, на пример 1 /2. И оваа замена нема да го промени резултатот од пресметките.
Второ, бидејќи во класата на еквивалентност има елементи кои не се разликуваат од гледна точка на некоја релација, сметаме дека класата на еквивалентност ја одредува некој нејзин претставник, т.е. произволен елемент од оваа класа. Така, секоја класа на еднакви дропки може да се специфицира со наведување на која било дропка што припаѓа на оваа класа. Определувањето класа на еквивалентност од еден претставник овозможува, наместо сите елементи од множеството, да се проучува множество од поединечни претставници од класите на еквивалентност. На пример, еквивалентната релација „да има ист број темиња“, дефинирана на множество многуаголници, генерира поделба на ова множество во класи на триаголници, четириаголници, петаголници итн. Својствата својствени за одредена класа се сметаат за еден од нејзините претставници.
Трето, поделбата на множеството во класи со користење на еквивалентна релација се користи за воведување нови концепти. На пример, концептот на „сноп од линии“ може да се дефинира како оној што е заеднички за паралелните линии.
Општо земено, секој концепт со кој работи едно лице претставува одредена класа на еквивалентност. „Табела“, „куќа“, „книга“ - сите овие концепти се генерализирани идеи за многу специфични предмети кои имаат иста цел.
Друг важен тип на врска е нарачки односи.
Дефиниција. Релацијата R на множеството X се нарекува релација на редот ако истовремено има својства на антисиметрија и транзитивност .
Примерите за релации за ред вклучуваат: релацијата „помалку од“ на множеството природни броеви; релацијата е „пократка“ на множество отсечки, бидејќи тие се антисиметрични и преодни.
Ако релацијата поредок има и својство на поврзаност, тогаш се вели дека е релација линеарен редослед.
На пример, односот „помалку од“ на множеството природни броеви е врска од линеарен ред, бидејќи има својства на антисиметрија, транзитивност и поврзаност.
Дефиниција. Множеството X се нарекува подредено ако има релација за ред.
Така, множеството N од природни броеви може да се подреди со наведување на релацијата „помалку од“ на него.
Ако релација наредба дефинирана на множество X,има својство на поврзаност, тогаш велиме дека тоа линеарно наредуваеден куп X.
На пример, множеството природни броеви може да се подреди со користење и на релацијата „помалку од“ и на релацијата „повеќекратно“ - и двете се релации за ред. Но, релацијата „помалку од“, за разлика од релацијата „повеќе“, има и својство на поврзаност. Ова значи дека релацијата „помалку од“ го подредува множеството природни броеви линеарно.
Не треба да се мисли дека сите односи се поделени на односи на еквивалентност и односи на ред. Има огромен број релации кои не се ниту еквивалентни, ниту релации.
