Отношението на еквивалентност на множество има следните свойства. Отношение на еквивалентност. Отношения на еквивалентност и ред
Анотация: Описани са много нови концепции, като релацията на еквивалентност, релацията на частичен ред и изоморфни частични множества. Няколко теореми по тази тема са доказани с подробни обяснения, графики и примери. Дадени са голям брой примери за частични поръчки. Описани са няколко конструкции, които позволяват да се конструират подредени набори от други. Лекцията се характеризира с множество задачи за самостоятелно решаване
Отношения на еквивалентност и ред
Нека ви го напомним двоична релациявърху множество се нарича подмножество; вместо 
често пиша.
Бинарна релация върху множество се нарича отношение на еквивалентност, ако са изпълнени следните свойства:
Следното очевидно, но често използвано твърдение е вярно:
Теорема 11. (a) Ако едно множество е разделено на обединение от несвързани подмножества, тогава отношението „да лежи в едно и също подмножество“ е отношение на еквивалентност.
(б) Всичко отношение на еквивалентностсе получава по описания начин от някакъв дял.
Доказателство. Първото твърдение е съвсем очевидно; Ще дадем доказателство за второто, за да може да се види къде се използват всички точки от определението за еквивалентност. И така, нека е отношение на еквивалентност. Помислете за всеки елемент клас на еквивалентност- множеството от всички, за които е вярно.
Нека докажем, че за две различни такива множества или не се пресичат, или съвпадат. Нека се пресичат, тоест да имат общ елемент. Тогава и , откъдето (симетрия) и (транзитивност), както и (симетрия). Следователно за което и да е от това следва (транзитивност) и обратно.
Остава да се отбележи, че поради рефлексивността всеки елемент принадлежи към класа, който дефинира, т.е. цялото множество наистина е разделено на несвързани класове.
78. Покажете, че изискванията за симетрия и транзитивност могат да бъдат заменени с едно: (като се запази изискването за рефлексивност).
79. Колко различни отношения на еквивалентност съществуват в множеството 
?
80. Върху множеството са дадени две отношения на еквивалентност, означени с и , имащи съответно и класове на еквивалентност. Тяхното пресичане ще бъде ли релация на еквивалентност? Колко класа може да има? Какво можете да кажете за обединяване на отношенията?
81. (Теорема на Рамзи) Множеството от всички - елементарни подмножества на безкрайно множество е разделено на класове (, - естествени числа). Докажете, че има безкрайно множество, всички елементарни подмножества на които принадлежат към един и същи клас.
(Това е очевидно: ако безкрайно множествое разделен на краен брой класове, тогава един от класовете е безкраен. Кога и твърдението може да се формулира по следния начин: от безкраен набор от хора човек може да избере или безкрайно много познати по двойки, или безкрайно много непознати по двойки. Окончателната версия на това твърдение - че сред всеки шестима души има или трима по двойки познати, или трима по двойки непознати - е добре известен проблем за учениците.)
Множеството от класове на еквивалентност се нарича фактор - мнмножества чрез отношение на еквивалентност. (Ако релацията е в съответствие с допълнителни структури на , получаваме факторни групи, факторни пръстени и т.н.)
Ще се сблъскаме с отношения на еквивалентност повече от веднъж, но засега основната ни тема са отношенията на ред.
Бинарна релация върху множество се нарича отношение на частичен ред, ако са изпълнени следните свойства:
(Следвайки традицията, ние използваме символ (а не буква) като знак за релация на ред.) Набор с частична релация на ред, даден върху него, се нарича частично поръчан.
Казват, че два елемента частично поръчанкомплекти сравними, ако или . Обърнете внимание, че дефиницията на частичен ред не изисква два елемента от множеството да бъдат сравними. Като добавим това изискване, получаваме определението линеен ред (линейно подредено множество).
Ето няколко примера за частични поръчки:
- Числови набори с обичайната връзка на реда (тук редът ще бъде линеен).
- На множеството от всички двойки реални числа, които можем да въведем частичен ред, като се има предвид, че ако и . Този ред вече няма да бъде линеен: двойките не са сравними.
- Можете да въведете набор от функции с реални аргументи и стойности частичен ред, като се има предвид, че ако
пред всички. Този ред няма да бъде линеен. - На множеството от положителни числа можем да определим реда, като приемем, че , ако дели . Този ред също няма да бъде линеен.
- Отношението „всеки прост делител на число е също и делител на число“ няма да бъде отношение на ред върху множеството от положителни цели числа (то е рефлексивно и транзитивно, но не и антисиметрично).
- Нека е произволен набор. Тогава, върху множеството от всички подмножества на множеството, релацията на включване ще бъде частичен ред.
- На буквите от руската азбука традицията определя определен ред (). Този ред е линеен - за всеки две букви можете да кажете коя е първа (ако е необходимо, като погледнете в речника).
- Определено с думи от руската азбука лексикографскиред (както в речника). Формално може да се дефинира по следния начин: ако една дума е началото на думата , то (например ). Ако никоя от думите не е началото на друга, погледнете първата буква в реда, в който думите се различават: тогава думата, където тази буква е по-малка по азбучен ред, ще бъде по-малка. Този ред също е линеен (в противен случай какво биха направили компилаторите на речници?).
- Отношението на равенство () също е отношение на частичен ред, за които няма два различни елемента, които да са сравними.
- Нека сега дадем един ежедневен пример. Нека има много картонени кутии. Нека въведем ред върху него, като се има предвид, че ако кутията се побира изцяло вътре в кутията (или ако и е същата кутия). В зависимост от набора от кутии, този ред може или не може да бъде линеен.
ВРЪЗКА
Отношенията са съответствия между елементи от едно и също множество, т.е. съответствия, чиито основни множества съвпадат:
x A, y Aповедение Г = ((x,y)| P(x,y)), P(x,y)някакво твърдение (предикат).
Ако (x,y) Г,тогава те казват това химат връзка ЖДа се при.
Например да има еднакъв остатък (за числа), да е на същото разстояние от линия (за точки), семейни отношения или съседски отношения (за много хора).
По-строга дефиниция:
Двоичната релация е две групи:
1) поддържащ комплект A,
2) множество от двойки Г=((x,y)| x A, y A), което е подмножество на квадрата на опорното множество.
n-арна връзка или n-арна (троична, четвъртична, ...) връзка е поддържащ набор Аи набори от измерение на кортежи н, което е подмножество на множеството A n.
Пример за троична връзка: да бъдеш част от „тримата играчи“.
Ако едно отношение се разбира просто като набор от кортежи (без поддържащо множество), тогава могат да се използват всички закони на теорията на множествата. Универсалното множество ще бъде квадратът на опорното множество, т.е. множеството от всички възможни кортежи (когато всеки елемент е във връзка с всеки друг елемент).
Връзката може да се дефинира и като двуместен предикат на обектни променливи x, y, което приема стойността „истина“, ако (x, y) Gи невярно, ако не принадлежи.
Обозначения: (x, y) Г, у = Г(х), у = Гxили просто xGu, например отношението на равенство (x = y), отношение на поръчката (Х< у) .
Ако (x, y) G, Че xGuприема стойността "true", в противен случай - "false".
Ако отношенията са зададени на дискретно множество, те могат да бъдат записани под формата на матрица
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 – невярно (например отношения х<у, х>при).
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
Казват, че комплектът има строг ред. В концепции< , >те имат по-широко значение: по-лошо е по-добре, по-рано е по-късно и т.н. В теорията на множествата пример за строг ред е строгото включване (да бъдеш подмножество на друго множество, без да си равен на него).
Поръчани комплекти
Комплектът се нарича линейно подредени, ако някой елемент може да бъде сравнен (тоест да кажем: по-голямо от, по-малко от или равно на).
Множество от реални или цели числа: класически примери за подредено множество.
Ако е възможно да се установи връзка на ред върху множество, но не и за всички двойки елементи, тогава такова множество се нарича частично поръчан.
Това е набор от вектори, набор от комплексни числа, множества в теорията на множествата. В някои случаи можем да кажем „повече е по-малко“ или „да бъде надмножество и подмножество“, но не във всички случаи.
Свързани определения
Множеството от всички класове на еквивалентност се означава с .
Примери за отношения на еквивалентност
По-сложен пример, но абсолютно жизненоважен:
Когато лекарят ви предписва лекарство, той всъщност посочва в рецептата класа на еквивалентните лекарства, не може да посочи напълно конкретно копие от опаковката на таблетки или ампули. Тези. Всички видове лекарства се разделят на класове чрез отношения на еквивалентност. Ако не беше този факт, съвременната медицина просто не би била възможна.
По този начин всички видове рецепти за салати и коктейли, GOSTs и класификатори също определят жизненоважни отношения на еквивалентност. Релациите на еквивалентност изпълват целия ни живот и не са абстрактно забавление за математиците.
Факторизиране на преобразувания
Множеството от класове на еквивалентност, съответстващи на отношението на еквивалентност, се означава със символа и се нарича фактор-наборотносително . Освен това, сюрективното картографиране
Наречен естествен дисплей(или канонична проекция) към набора от фактори.
Нека , са множества, са преобразуване, тогава двоичната релация, дефинирана от правилото
е отношение на еквивалентност на . В този случай преобразуването индуцира преобразуване, дефинирано от правилото
или, което е същото,
.В този случай се оказва факторизацияпреобразувания към сюрективно и инжективно преобразуване.
Картографирането на фактори се използва широко в хуманитарните науки и в онези области на технологиите, където не е възможно да се използват числени стойности. Картографирането на фактори ви позволява да правите без формули, когато формулите не могат да се използват. Нека дадем пример, който ще бъде разбираем за всеки и не изисква разбиране на сложна математическа символика.
Училищният график е типичен пример за факторизация. В този случай наборът от всички ученици, наборът от всички учебни предмети, разпределени по дни от седмицата, като се уточнява времето на занятията. Еквивалентните класове са класове (групи от ученици). Дисплей – графикът на класовете се показва в дневниците на ученика. Дисплей - разписание на часовете, поставено във фоайето на училището. Тук има и дисплей - списъци с класове. Този пример много ясно демонстрира практическите ползи от факторизацията: невъзможно е да си представим графика на класа като таблица, която отразява всички ученици в училището поотделно. Факторизацията направи възможно показването на информацията, от която се нуждаят учениците, в компактна форма, удобна за използване в ситуации, в които не могат да се прилагат формули.
Ползите от факторизацията обаче не се ограничават до това. Факторизацията позволява разпределение на труда между участниците в дейността: директорът съставя график, а учениците го записват в дневниците си. По същия начин факторизирането на предписанията позволява разделяне на труда между лекаря, който поставя диагнозата и пише рецептата, и фармацевта, който гарантира еквивалентността на предписаните лекарства. Апотеозът на факторизацията е конвейерната лента, която осъществява максималното разделение на труда чрез стандартизиране на частите.
Но ползите от факторизирането не се ограничават до това. Факторизацията направи възможно да се осигури модулността на съвременната технология, което й дава безпрецедентна гъвкавост на функциите. Можете да запазите старата SIM карта и да си купите изцяло нов телефон, който да върви с нея, или да поставите нова видео памет в стария си компютър. Всичко това е гъвкавост, модулност, която се базира на факторизация.
Литература
- А. И. Кострикин, Въведение в алгебрата. М.: Наука, 1977, 47-51.
- А. И. Малцев, Алгебрични системи, М.: Наука, 1970, 23-30.
- В. В. Иванов, Математически анализ. НГУ, 2009 г.
Вижте също
- Отношението на толерантност е отслабена форма на еквивалентност.
- Еквивалентността е логическа операция.
Фондация Уикимедия. 2010 г.
- Болнична пневмония
- Мител
Вижте какво е „отношение на еквивалентност“ в други речници:
отношение на еквивалентност- - Телекомуникационни теми, основни понятия EN релация на еквивалентност... Ръководство за технически преводач
Отношение тип равенство- отношение на еквивалентност, концепция на логиката и математиката, изразяваща факта на наличието на едни и същи признаци (свойства) в различни обекти. По отношение на такива общи характеристики тези различни обекти са неразличими (идентични, равни,... ...
Отношение на толерантност- Този термин има и други значения, вижте Толерантност. Отношението на толерантност (или просто толерантност) върху набор е двоично отношение, което удовлетворява свойствата на рефлексивност и симетрия, но не непременно... ... Wikipedia
Съотношение (математика)- Този термин има и други значения, вижте Отношение. Връзката е математическа структура, която формално дефинира свойствата на различни обекти и техните взаимоотношения. Връзките обикновено се класифицират според броя на обектите, които се свързват... Уикипедия
ПОВЕДЕНИЕ- в логиката нещо, което за разлика от свойство характеризира не отделен предмет, а двойка, тройка и т.н. елементи. Традиционната логика не разглежда О.; в съвременната логика О. е пропозиционална функция на две или повече променливи. двоичен... Философска енциклопедия
Отношение на предпочитанията- в теорията на потребителите това е формално описание на способността на потребителя да сравнява (подрежда по желание) различни набори от стоки (потребителски комплекти). За да се опише връзка на предпочитанията, не е необходимо да се измерва желателността... ... Wikipedia
Отношение (философско)- Отношение, философска категория, която изразява характера на подреждането на елементите на определена система и тяхната взаимозависимост; емоционално-волево отношение на човек към нещо, т.е. израз на неговата позиция; мислено сравнение на различни обекти... ... Велика съветска енциклопедия
поведение- ВРЪЗКА е набор от подредени n ок индивиди (където n е 1), т.е. двойки, тройки и т.н. Числото n се нарича "местност" или "арност", О. и съответно се говори за n местно (n арно) О. Така например двойно О. се нарича... ... Енциклопедия на епистемологията и философията на науката
Поведение- I Отношението е философска категория, която изразява характера на подреждането на елементите на определена система и тяхната взаимозависимост; емоционално-волево отношение на човек към нещо, т.е. израз на неговата позиция; мислено сравнение на различни... ... Велика съветска енциклопедия
Клас на еквивалентност- Отношение на еквивалентност () върху множество X е двоично отношение, за което са изпълнени следните условия: Рефлексивност: за всяко a в X, Симетрия: ако, тогава, Транзитивност: ако... Wikipedia
Книги
- Вземане на финансови решения в условия на сравнителна несигурност: Монография, Bayuk O.A.. В монографията е разработена и теоретично обоснована нова логическа стратегия за вземане на решения при избор между несравними обекти, установяваща специална връзка на предпочитание и...
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,....) на множеството M на класове от елементи, еквивалентни един на друг - така наречените класове на еквивалентност.
Определение 2.5. Множеството от класове на еквивалентност по отношение на релация се означава с M/ и се чете като частно множество на множеството M по отношение на релация.
Нека μ: M > S е сюръективно преобразуване на множеството M върху някакво множество S.
За всяко μ: M > S - сюръективно преобразуване има релация на еквивалентност в множеството M, така че M/ и S могат да бъдат поставени в съответствие едно към едно.
III. Еквивалентни свойства
Определение 2.6. Връзка c върху множество M се нарича релация на еквивалентност, ако е рефлексивна, симетрична и транзитивна.
Теорема 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) c. Това означава, че y. Но също и x по силата на (x, x) c. Следователно и двата елемента са включени в. Така че, ако (x, y) c, тогава x и y са включени в общия клас на дялове. Обратно, нека u и v. Нека покажем, че (u, v) c. Наистина имаме (x, u) c и (x, v) c. Следователно, чрез симетрия (u, x) c. По транзитивност от (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. Операции върху еквивалентности.
Тук дефинираме някои теоретико-множествени операции върху еквивалентности и представяме техните важни свойства без доказателство.
Спомнете си, че релацията е двойка (), където M е множеството от елементи, влизащи в релацията, и е множеството от двойки, за които релацията е изпълнена.
Определение 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 върху множество M се нарича толерантност, ако е рефлексивно и симетрично.
Определение 2.11. Релация c върху множество M се нарича релация от строг ред, ако е антирефлексивна и транзитивна.
Определение 2.12. Отношение на строг ред c се нарича перфектен строг ред, ако за всяка двойка елементи x и y от M или (x, y), или (y, x) е вярно.
Определение 2.13. Отношение c върху множество M се нарича отношение от нестрог ред, ако може да бъде представено във формата:
където има строг ред на M, а E е диагонална връзка.
Лекция 22. Отношения на еквивалентност и ред върху множество
1. Отношение на еквивалентност. Връзката между релацията на еквивалентност и разделянето на множество на класове.
2. Отношение на поръчката. Строги и нестроги отношения на ред, линейни отношения на ред. Поръчване на комплекти.
3. Основни изводи
Нека да разгледаме множеството от дроби х= (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) отношение на равенство. Тази връзка:
Рефлексивно, тъй като всяка дроб е равна на себе си;
Симетрично, тъй като от факта, че фракцията м/нравен на дроб стр/р, следва, че фракцията стр/рравен на дроб м/н;
Преходен, тъй като от факта, че фракцията м/нравен на дроб стр/ри фракция стр/рравен на дроб r/с, следва, че фракцията м/нравен на дроб r/с.
Отношението на равенство на дробите се нарича отношение на еквивалентност.
Определение. Връзка R върху множество 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, тогава тя генерира разделяне на това множество на двойки несвързани подмножества (класове на еквивалентност).
По този начин установихме, че отношението на равенство върху набор от дроби (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“. Той генерира дял на множеството хна класове: единият ще включва всички числа, които при деление на 3 оставят остатък 0 (това са числата 3, 6, 9), вторият - числа, които при деление на 3 оставят остатък 1 (това са числата 1, 4) , 7 , 10), а в третата - всички числа, като при деление на 3 остатъкът е 2 (това са числата 2, 5, 8). Наистина, получените подмножества не се пресичат и обединението им съвпада с множеството Х.Следователно отношението „имат същия остатък, когато се дели на 3“, дефинирано в множеството Х,е отношение на еквивалентност. Имайте предвид, че твърдението за връзката между релацията на еквивалентност и разделянето на множество на класове се нуждае от доказателство. Слагаме го. Нека просто кажем, че ако връзката на еквивалентност има име, тогава съответното име се дава на класовете. Например, ако отношение на равенство е определено за набор от сегменти (и това е отношение на еквивалентност), тогава множеството от сегменти се разделя на класове от равни сегменти (вижте Фиг. 99). Отношението на подобие съответства на разделянето на набор от триъгълници на класове от подобни триъгълници.
Така че, имайки отношение на еквивалентност на определено множество, можем да разделим това множество на класове. Но можете да направите и обратното: първо да разделите множеството на класове и след това да дефинирате релация на еквивалентност, като се има предвид, че два елемента са еквивалентни, ако и само ако принадлежат към един и същ клас на въпросното разделение.
Принципът за разделяне на набор на класове, използвайки някакво отношение на еквивалентност, е важен принцип на математиката. Защо?
Първо, еквивалентен - това означава равностоен, взаимозаменяем. Следователно елементите от един и същ клас на еквивалентност са взаимозаменяеми. Така дроби, които са в един и същ клас на еквивалентност (1/2, 2/4, 3/6), са неразличими от гледна точка на отношението на равенство и дробта 3/6 може да бъде заменена с друга, например 1 /2. И тази замяна няма да промени резултата от изчисленията.
Второ, тъй като в класа на еквивалентност има елементи, които са неразличими от гледна точка на някакво отношение, смятаме, че класът на еквивалентност се определя от всеки негов представител, т.е. произволен елемент от този клас. По този начин всеки клас от равни дроби може да бъде специфициран чрез посочване на всяка дроб, принадлежаща към този клас. Определянето на клас на еквивалентност по един представител позволява вместо всички елементи на множеството да се изследва набор от отделни представители от класовете на еквивалентност. Например релацията на еквивалентност „да имаш еднакъв брой върхове“, дефинирана върху набор от многоъгълници, генерира разделяне на този набор на класове от триъгълници, четириъгълници, петоъгълници и т.н. Свойствата, присъщи на определен клас, се разглеждат на един от неговите представители.
трето, разделянето на набор на класове с помощта на релация на еквивалентност се използва за въвеждане на нови концепции. Например понятието „пакет от линии“ може да се дефинира като това, което е общо за успоредните линии.
Като цяло всяка концепция, с която човек оперира, представлява определен клас еквивалентност. „Маса“, „къща“, „книга“ - всички тези понятия са обобщени идеи за много конкретни предмети, които имат една и съща цел.
Друг важен тип връзка е отношения на реда.
Определение. Отношение R върху множество X се нарича отношение на ред, ако едновременно притежава свойствата на антисиметрия и транзитивност .
Примерите за порядъчни отношения включват: релацията „по-малко от“ върху множеството от естествени числа; релацията е „по-къса“ на набор от сегменти, тъй като те са антисиметрични и транзитивни.
Ако една релация на ред също има свойството на свързаност, тогава се казва, че е релация линеен ред.
Например отношението „по-малко от“ върху множеството от естествени числа е отношение от линеен ред, тъй като има свойствата на антисиметрия, транзитивност и свързаност.
Определение. Множество X се нарича подредено, ако има отношение на ред.
По този начин множеството N от естествени числа може да бъде подредено чрез определяне на връзката „по-малко от“ върху него.
Ако релация на ред, дефинирана върху множество Х,има свойството на свързаност, тогава казваме това той линейно нарежданяколко Х.
Например, множеството от естествени числа може да бъде подредено, като се използва както връзката "по-малко от", така и връзката "кратно" - и двете са отношения на ред. Но отношението „по-малко от“, за разлика от отношението „множество“, също има свойството на свързаност. Това означава, че връзката „по-малко от“ подрежда набора от естествени числа линейно.
Не трябва да се мисли, че всички отношения се делят на отношения на еквивалентност и отношения на ред. Има огромен брой отношения, които не са нито отношения на еквивалентност, нито отношения на ред.
