Връзката еквивалентна ли е? Двоични релации - MT1102: Линейна алгебра (Въведение в математиката) - Бизнес информатика

Анотация: Описани са много нови концепции, като релацията на еквивалентност, релацията на частичен ред и изоморфни частични множества. Няколко теореми по тази тема са доказани с подробни обяснения, графики и примери. Дадени са голям брой примери за частични поръчки. Описани са няколко конструкции, които позволяват да се конструират подредени набори от други. Лекцията се характеризира с множество задачи за самостоятелно решаване

Отношения на еквивалентност и ред

Нека ви го напомним двоична релациявърху множество се нарича подмножество; вместо често пиша.

Бинарна релация върху множество се нарича отношение на еквивалентност, ако са изпълнени следните свойства:

Следното очевидно, но често използвано твърдение е вярно:

Теорема 11. (a) Ако едно множество е разделено на обединение от несвързани подмножества, тогава отношението „да лежи в едно и също подмножество“ е отношение на еквивалентност.

(б) Всичко отношение на еквивалентностсе получава по описания начин от някакъв дял.

Доказателство. Първото твърдение е съвсем очевидно; Ще дадем доказателство за второто, за да може да се види къде се използват всички точки от определението за еквивалентност. И така, нека е отношение на еквивалентност. Помислете за всеки елемент клас на еквивалентност- множеството от всички, за които е вярно.

Нека докажем, че за две различни такива множества или не се пресичат, или съвпадат. Нека се пресичат, тоест да имат общ елемент. Тогава и , откъдето (симетрия) и (транзитивност), както и (симетрия). Следователно за което и да е от това следва (транзитивност) и обратно.

Остава да се отбележи, че поради рефлексивността всеки елемент принадлежи към класа, който дефинира, т.е. цялото множество наистина е разделено на несвързани класове.

78. Покажете, че изискванията за симетрия и транзитивност могат да бъдат заменени с едно: (като се запази изискването за рефлексивност).

79. Колко различни отношения на еквивалентност съществуват в множеството ?

80. Върху множеството са дадени две отношения на еквивалентност, означени с и , имащи съответно и класове на еквивалентност. Тяхното пресичане ще бъде ли релация на еквивалентност? Колко класа може да има? Какво можете да кажете за обединяване на отношенията?

81. (Теорема на Рамзи) Множеството от всички - елементарни подмножества на безкрайно множество е разделено на класове (, - естествени числа). Докажете, че има безкрайно множество, всички елементарни подмножества на които принадлежат към един и същи клас.

(Това е очевидно: ако безкрайно множествое разделен на краен брой класове, тогава един от класовете е безкраен. Кога и твърдението може да се формулира по следния начин: от безкраен набор от хора човек може да избере или безкрайно много познати по двойки, или безкрайно много непознати по двойки. Окончателната версия на това твърдение - че сред всеки шестима души има или трима по двойки познати, или трима по двойки непознати - е добре известен проблем за учениците.)

Множеството от класове на еквивалентност се нарича фактор - мнмножества чрез отношение на еквивалентност. (Ако релацията е в съответствие с допълнителни структури на , получаваме факторни групи, факторни пръстени и т.н.)

Ще се сблъскаме с отношения на еквивалентност повече от веднъж, но засега основната ни тема са отношенията на ред.

Бинарна релация върху множество се нарича отношение на частичен ред, ако са изпълнени следните свойства:

(Следвайки традицията, ние използваме символ (а не буква) като знак за релация на ред.) Набор с частична релация на ред, даден върху него, се нарича частично поръчан.

Казват, че два елемента частично поръчанкомплекти сравними, ако или . Обърнете внимание, че дефиницията на частичен ред не изисква два елемента от множеството да бъдат сравними. Като добавим това изискване, получаваме определението линеен ред (линейно подредено множество).

Ето няколко примера за частични поръчки:

  • Числови набори с обичайната връзка на реда (тук редът ще бъде линеен).
  • На множеството от всички двойки реални числа, които можем да въведем частичен ред, като се има предвид, че ако и . Този ред вече няма да бъде линеен: двойките не са сравними.
  • Можете да въведете набор от функции с реални аргументи и стойности частичен ред, като се има предвид, че ако пред всички. Този ред няма да бъде линеен.
  • На множеството от положителни числа можем да определим реда, като приемем, че , ако дели . Този ред също няма да бъде линеен.
  • Отношението „всеки прост делител на число е също и делител на число“ няма да бъде отношение на ред върху множеството от положителни цели числа (то е рефлексивно и транзитивно, но не и антисиметрично).
  • Нека е произволен набор. Тогава, върху множеството от всички подмножества на множеството, релацията на включване ще бъде частичен ред.
  • На буквите от руската азбука традицията определя определен ред (). Този ред е линеен - за всеки две букви можете да кажете коя е първа (ако е необходимо, като погледнете в речника).
  • Определено с думи от руската азбука лексикографскиред (както в речника). Формално може да се дефинира по следния начин: ако една дума е началото на думата , то (например ). Ако никоя от думите не е началото на друга, погледнете първата буква в реда, в който думите се различават: тогава думата, където тази буква е по-малка по азбучен ред, ще бъде по-малка. Този ред също е линеен (в противен случай какво биха направили компилаторите на речници?).
  • Отношението на равенство () също е отношение на частичен ред, за които няма два различни елемента, които да са сравними.
  • Нека сега дадем един ежедневен пример. Нека има много картонени кутии. Нека въведем ред върху него, като се има предвид, че ако кутията се побира изцяло вътре в кутията (или ако и е същата кутия). В зависимост от набора от кутии, този ред може или не може да бъде линеен.

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 е диагонална връзка.

ВРЪЗКА

Отношенията са съответствия между елементи от едно и също множество, т.е. съответствия, чиито основни множества съвпадат:

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 поведение.

Казват, че комплектът има строг ред. В концепции< , >те имат по-широко значение: по-лошо е по-добре, по-рано е по-късно и т.н. В теорията на множествата пример за строг ред е строгото включване (да бъдеш подмножество на друго множество, без да си равен на него).

Поръчани комплекти

Комплектът се нарича линейно подредени, ако някой елемент може да бъде сравнен (тоест да кажем: по-голямо от, по-малко от или равно на).

Множество от реални или цели числа: класически примери за подредено множество.

Ако е възможно да се установи връзка на ред върху множество, но не и за всички двойки елементи, тогава такова множество се нарича частично поръчан.

Това е набор от вектори, набор от комплексни числа, множества в теорията на множествата. В някои случаи можем да кажем „повече е по-малко“ или „да бъде надмножество и подмножество“, но не във всички случаи.

Класове еквивалентни елементи и техните свойства

Нека %%R%% — отношение на еквивалентноствърху множеството %%M%% и %%a%% - някакъв елемент от %%M%%. Разгледайте набора от всички елементи от %%M%%, които са във връзка %%R%% с елемент %%a%%.

Клас на еквивалентност%%M_a%%

е множеството от всички елементи %%M%%, които са във връзка %%R%% с елемента %%a%%, т.е.

$$ M_a = \(x \in M: x~R~a\). $$

Пример

Нека %%M%% е множеството от всички жители на Русия и %%R%% е отношението на еквивалентност „да живеем в един и същи град“. Намерете класове от еквивалентни елементи %%M_a%% за %%a \in M%%.

Класът от елементи, еквивалентен на елемента %%a%% има формата: $$ M_a = \(x \in M: x \text( живее в същия град като лицето) a\) $$

В зависимост от елемента %%a%% получаваме няколко класа на еквивалентност. Например класът на еквивалентност на жителите на Москва или Санкт Петербург.

Свойства на класовете на еквивалентност

Нека %%R%% е релация на еквивалентност в множеството %%M%% и %%M_a, M_b, \dotsc, M_z, \dotsc%% са всички класове на еквивалентност за релацията %%R%%. Тогава тези класове имат следните свойства.

Имот 1

За всеки елемент %%a \in M%% условието $$ a \in M_a $$ е изпълнено

Наистина, по дефиниция, класът %%M_a = \(x \in M: x~R~a\)%%. Тогава за елемента %%a%% условието %%a \in M_a \leftrightarrow a~R~a%% трябва да бъде изпълнено, което е изпълнено поради факта, че релацията %%R%% е рефлексивна по дефиницията на отношение на еквивалентност. Следователно, %%a \in M_a%%.

СледователноТова свойство ни позволява да кажем, че всеки клас %%M_a%% е непразно множество.

Имот 2

Нека %%M_a%% и %%M_b%% са класове на еквивалентност за релацията %%R%%. Класовете %%M_a%% и %%M_b%% са равни тогава и само ако елементът %%a%% е в релацията %%R%% към елемента %%b%%. $$ M_a = M_b \leftrightarrow a~R~b. $$

Имот 3

Нека %%M_a%% и %%M_b%% са класове на еквивалентност за релацията %%R%%. Тогава класовете %%M_a%% и %%M_b%% нямат общи елементи. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing $$

Имот 4

Обединението на всички класове на еквивалентност на множеството %%M%% е равно на множеството %%M%%. $$ \bigcup_(a\in M)(M_a) = M. $$

Разделяне на комплект

Колекцията от подмножества %%M_i%%, където %%i \in I%% (към множеството от индекси), на множеството %%M%% се нарича разделянезадайте %%M%%, ако са изпълнени следните условия:

  1. Всяко от подмножествата %%M_i%% не е празно.
  2. Обединението на всички подмножества %%M_i%% е равно на множеството %%M%%.
  3. Две различни подгрупи %%M_i%% и %%M_j%%, където %%i \neq j%%, нямат общи елементи.

Теорема.Нека %%R%% е релация на еквивалентност в множеството %%M%%. Тогава наборът от класове на еквивалентност на набора %%M%% образува неговото разделение.

Наистина, ако приемем класовете на еквивалентност %%M_a%% като подмножества на %%M_i%%, тогава и трите условия са изпълнени:

  1. Всеки клас на еквивалентност е непразно множество, съгл собственост 1.
  2. Обединението на всички класове на еквивалентност е множеството %%M%%, според собственост 4.
  3. Два различни класа на еквивалентност нямат общи елементи, според собственост 3.

Всички условия за дефиниране на дял са изпълнени. Следователно класовете на еквивалентност са дял на множеството %%M%%.

Примери

Нека е дадено множеството %%M = \(1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \)%%, тогава следните колекции от множества могат да бъдат дял на това множество:

  1. %%A_1 = \(1, 2, 3\), A_2 = \(4, 5, 6, 7\), A_3 = \(8, 9, 0\)%%.
  2. %%B_1 = \(0, 7, 2\), B_2 = \(1, 3, 5\), B_3 = \(4, 6, 8, 9\)%%.

Но следните агрегати не са дялове:

  1. %%C_1 = \(1, 2, 3\), C_2 = \(4, 5, 6, 7\), C_3 = \(8, 9, 0, 3\)%%.
  2. %%D_1 = \(0, 7, 2\), D_2 = \(1, 3, 5\), D_3 = \(4, 6, 8, 9\), D_4 = \varnothing%%.
  3. %%E_1 = \(0, 1, 2\), E_2 = \(3, 4, 5\), E_3 = \(6, 7, 8\)%%.

Наборът %%C_i%% не е дял, защото не отговаря на условие 3 за разделящи множества: множествата %%C_1%% и %%C_3%% имат общ елемент %%3%%.

Наборът %%D_i%% не е дял, защото не отговаря на условие 1 за разделяне на набори: наборът %%D_4%% е празен.

Наборът %%E_i%% не е дял, защото не отговаря на условие 2 за разделящи множества: обединението на множествата %%E_1, E_2%% и %%E_3%% не образува множеството %%M%%.

Отношение на еквивалентност е отношение, което има свойствата на рефлексивност, симетрия и транзитивност.Обозначава се със знака ~, записване А ~ V означава, че А еквивалентен V .

Според дефиницията отношението на еквивалентност има следните свойства:

Примери за отношения на еквивалентност – равенство, подобие на триъгълници.

С помощта на релацията на еквивалентност е възможно да се раздели набор на класове на еквивалентност.

Клас на еквивалентност , генериран от елемента – съвкупността от всички елементи от , започвайки от във връзка с еквивалентността.Класът на еквивалентност се определя, както следва:

, За
избрани са елементи
, които са в съответствие с елемента х .

Отношението на еквивалентност има голямо практическо приложение, позволявайки множествата да бъдат разделени на класове на еквивалентност. Класът на еквивалентност може да бъде получен, ако за избрания елемент х от много х можете да изберете елементи
, находящ се с х в един клас на еквивалентност

Факторни множества комплекти по отношение на еквивалентностφ – множеството от всички различни класове на еквивалентност, означA/φ .

Индекс на дяла , генерирани от релациятаφ е мощността на набора от фактори A/φ .

Пример2 .11.

а) Отношение на равенство
на всяко множество е релация на еквивалентност.

Равенството е отношение на минимална еквивалентност в смисъл, че при премахване на която и да е двойка от
(тоест всяка единица по диагонала на матрицата
) то престава да бъде рефлексивно и следователно вече не е еквивалентност.

б)Изявления на формуляра
или
, състоящи се от формули, свързани със знак за равенство, дефинират двоична релация върху набор от формули, описващи суперпозиции на елементарни функции. Това отношение обикновено се нарича отношение на еквивалентност и се дефинира по следния начин: формулите са еквивалентни, ако дефинират една и съща функция. Еквивалентността, въпреки че се обозначава със знака =, е различна от отношението на равенство
, тъй като може да се извърши за различни формули. Поведение
за формулите това е съвпадението на формулите по правопис. Нарича се графично равенство .

V)Нека разгледаме набор от триъгълници в равнина, като приемем, че триъгълник е даден, ако са дадени координатите на неговите върхове. Два триъгълника се наричатконгруентни (равен ) , ако те съвпадат, когато се наслагват, тоест могат да се превърнат един в друг чрез някакво движение. Конгруентността е връзка на еквивалентност върху набор от триъгълници.

G)Поведение " имат същия остатък, когато са разделени на 9" е еквивалентно на
. Тази връзка е в сила за двойки (12, 21), (17, 36) и не е в сила за двойки (11, 13), (19, 29).

Нека на снимачната площадка дадено отношение на еквивалентност . Нека извършим следната конструкция. Нека изберем елемент
и образуват клас (подмножество ), състояща се от ; след това изберете елемента
и образуват клас , състояща се от и всички елементи еквивалентни и т.н. Резултатът е класова система
(възможно безкрайно), така че всеки елемент от е включено в поне един клас, т.е
. Тази класова система има следните свойства:

    то формира преграда, тоест класове по двойки не се пресичат;

    всеки два елемента от един и същи клас еквивалентен;

    всеки два елемента от различни класове не са еквивалентни.

Всички тези свойства произтичат от рефлексивност, симетрия и транзитивност . Наистина, ако класове, напр И , пресечени, тогава те биха имали общ елемент , еквивалентен И , но след това поради преходност би се
, което противоречи на конструкцията . Другите две свойства се доказват по подобен начин.

Изграденото разделение, тоест класовата система, се нарича система класове на еквивалентноствъв връзка с . Мощността на тази система се нарича индекс на дяла. От друга страна, всеки дял класове дефинира определено отношение на еквивалентност, а именно отношението „ принадлежат към същия клас на даден дял».

Пример. 2.12.

а)Всички класове на еквивалентност по отношение на отношението на равенство
се състои от един елемент.

б)Формулите, описващи една и съща елементарна функция, са в един и същ клас на еквивалентност по отношение на релацията на еквивалентност. В този пример самият набор от формули, наборът от класове на еквивалентност (т.е. индексът на дял) и всеки клас на еквивалентност са преброими.

в) Преграда
във връзка с " има общ остатък, когато се раздели на 7" има краен индекс 7 и се състои от 7 изброими класа: 0, 7, 14, ...; 2, 9, 16, …; ...; 6, 13, 20, …



Подобни статии