Клас еквівалентності елемента множини за заданим на цій множині відношенням еквівалентності є підмножина множини , що складається з елементів еквівалентних :
Класи еквівалентності між елементами структур часто використовуються для отримання меншої структури, елементами якої є класи. Зв'язок кожного елемента класу поділяється принаймні з одним іншим елементом іншого класу. Клас можна вважати тотожністю одного з оригінальних елементів.
Властивості
- Множина всіх класів еквівалентності множини
називається фактор-множиною і є розбиттям множини
- Кожен елемент x з X є членом класу еквівалентності [x]. Кожні два класи еквівалентності [x] і [y] або дорівнюють, або не перетинаються. Таким чином, множина всіх класів еквівалентності X утворює розбиття множини X: кожен елемент X належить одному і тільки одному класу еквівалентності.
- x ~ y, тоді і тільки тоді, коли x і y належать до одного і того ж самого розділу множини.
З властивостей відношення еквівалентності випливає, що
- x ~ y, тоді і тільки тоді, коли [x] = [y].
Іншими словами, якщо ~ є відношення еквівалентності на множині X, то ці твердження еквівалентні:
.
Позначення і формальне визначення
Відношення еквівалентності є бінарним відношенням, яке має три властивості:
- Для кожного елемента a із X, a ~ a (рефлексивність),
- Для кожних двох елементів a і b з X, якщо a ~ b, то і b ~ a (симетрія)
- Для кожних трьох елементів a, b і c з X, якщо a ~ b і b ~ c, то a ~ c (транзитивність).
Клас еквівалентності елемента a позначається [a] і може визначатися як множина.
Альтернативне позначення [a]R може бути використане для позначення класу еквівалентності елемента зокрема у відношенні R. Це називається R-класу еквівалентність. Множина всіх еквівалентних класів в X даного відношення еквівалентності позначається як X/~ і називається фактор-множина X на ~. Кожне відношення еквівалентності має канонічну проєкцію, сюр'єктивну функцію π з X де X/~ задано π(x) = [x].
Приклади
- Якщо X є множиною всіх автомобілів, і ~ є відношенням еквівалентності «має той же колір», то кожен клас еквівалентності складається з автомобілів однакового кольору. Наприклад, всі зелені автомобілі належать одному класу. Кількість класів X/~ дорівнює числу всіх кольорів автомобілів.
- Розглянемо відношення еквівалентності на множині
цілих чисел: x ~ y, тоді і тільки тоді, коли їх різниця x − y парне число. Це співвідношення призводить до двох класів еквівалентності: один клас, що складається з усіх парних чисел, та другий, який складається з усіх непарних чисел. Клас парних чисел позначається, як [0], непарних як [1]. Згідно з цим співвідношенням [7], [9], та [117] належать одному класу — [1].
- Нехай X множина впорядкованих пар цілих чисел (a,b), де b не дорівнює нулю, і характеризує відношення еквівалентності ~ на X. Відповідно до якого (a,b) ~ (c,d), тоді і тільки тоді, коли ad = bc. Класу еквівалентності пари (a,b) можна поставити у відповідність раціональне число a/b, таким чином, це відношення еквівалентності і його класи еквівалентності можуть бути використані як формальне визначення множини раціональних чисел. Наприклад, еквівалентним парам (1,3), (2,6), (5,15), відповідає рівність дробів
.
- Відношення рівності за модулем (
) на множині цілих чисел
є відношенням еквівалентності. Класи еквівалентності
- Нехай дане число
де
Тоді всяку групу цифр
називають класом. Група цифр
— перший клас (клас одиниць),
— другий клас (клас тисяч) тощо.
- Нехай
є підгрупою групи
У групі
діє закон еквівалентності:
якщо
. Виникає клас суміжності групи
по групі
.
Факторизація відображень
Відображення
називається природним відображенням (або канонічної проєкцією) на фактор-множину
. Нехай
,
— множини,
- відображення, тоді бінарне відношення
визначене правилом
є відношенням еквівалентності на . При цьому відображення
індукує відображення
, яке визначається правилом
або, що те ж саме,
.
При цьому виходить факторизація відображення на сюр'єктивне відображення
і ін'єктивне відображення
.
Див. також
Джерела
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : , 1937. — 304 с. — .(рос.)
- Курош А. Г. Общая алгебра. — М. : Мир, 1970. — 162 с.(рос.)
- Универсальная алгебра. — Москва : Мир, 1968. — 351 с.(рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Klas ekvivalentnosti elementa a displaystyle a mnozhini S displaystyle S za zadanim na cij mnozhini vidnoshennyam ekvivalentnosti ye pidmnozhina mnozhini S displaystyle S sho skladayetsya z elementiv ekvivalentnih a displaystyle a a x S x a displaystyle a x in S x sim a Klasi ekvivalentnosti mizh elementami struktur chasto vikoristovuyutsya dlya otrimannya menshoyi strukturi elementami yakoyi ye klasi Zv yazok kozhnogo elementa klasu podilyayetsya prinajmni z odnim inshim elementom inshogo klasu Klas mozhna vvazhati totozhnistyu odnogo z originalnih elementiv VlastivostiMnozhina vsih klasiv ekvivalentnosti mnozhini S displaystyle S nazivayetsya faktor mnozhinoyu i ye rozbittyam mnozhini S displaystyle S Kozhen element x z X ye chlenom klasu ekvivalentnosti x Kozhni dva klasi ekvivalentnosti x i y abo dorivnyuyut abo ne peretinayutsya Takim chinom mnozhina vsih klasiv ekvivalentnosti X utvoryuye rozbittya mnozhini X kozhen element X nalezhit odnomu i tilki odnomu klasu ekvivalentnosti x y todi i tilki todi koli x i y nalezhat do odnogo i togo zh samogo rozdilu mnozhini Z vlastivostej vidnoshennya ekvivalentnosti viplivaye sho x y todi i tilki todi koli x y dd Inshimi slovami yaksho ye vidnoshennya ekvivalentnosti na mnozhini X to ci tverdzhennya ekvivalentni x y displaystyle x sim y x y displaystyle x y x y displaystyle x cap y neq emptyset Poznachennya i formalne viznachennyaVidnoshennya ekvivalentnosti ye binarnim vidnoshennyam yake maye tri vlastivosti Dlya kozhnogo elementa a iz X a a refleksivnist Dlya kozhnih dvoh elementiv a i b z X yaksho a b to i b a simetriya Dlya kozhnih troh elementiv a b i c z X yaksho a b i b c to a c tranzitivnist Klas ekvivalentnosti elementa a poznachayetsya a i mozhe viznachatisya yak mnozhina a x X a x displaystyle a x in X mid a sim x Alternativne poznachennya a R mozhe buti vikoristane dlya poznachennya klasu ekvivalentnosti elementa zokrema u vidnoshenni R Ce nazivayetsya R klasu ekvivalentnist Mnozhina vsih ekvivalentnih klasiv v X danogo vidnoshennya ekvivalentnosti poznachayetsya yak X i nazivayetsya faktor mnozhina X na Kozhne vidnoshennya ekvivalentnosti maye kanonichnu proyekciyu syur yektivnu funkciyu p z X de X zadano p x x PrikladiYaksho X ye mnozhinoyu vsih avtomobiliv i ye vidnoshennyam ekvivalentnosti maye toj zhe kolir to kozhen klas ekvivalentnosti skladayetsya z avtomobiliv odnakovogo koloru Napriklad vsi zeleni avtomobili nalezhat odnomu klasu Kilkist klasiv X dorivnyuye chislu vsih koloriv avtomobiliv Rozglyanemo vidnoshennya ekvivalentnosti na mnozhini Z displaystyle mathbb Z cilih chisel x y todi i tilki todi koli yih riznicya x y parne chislo Ce spivvidnoshennya prizvodit do dvoh klasiv ekvivalentnosti odin klas sho skladayetsya z usih parnih chisel ta drugij yakij skladayetsya z usih neparnih chisel Klas parnih chisel poznachayetsya yak 0 neparnih yak 1 Zgidno z cim spivvidnoshennyam 7 9 ta 117 nalezhat odnomu klasu 1 Nehaj X mnozhina vporyadkovanih par cilih chisel a b de b ne dorivnyuye nulyu i harakterizuye vidnoshennya ekvivalentnosti na X Vidpovidno do yakogo a b c d todi i tilki todi koli ad bc Klasu ekvivalentnosti pari a b mozhna postaviti u vidpovidnist racionalne chislo a b takim chinom ce vidnoshennya ekvivalentnosti i jogo klasi ekvivalentnosti mozhut buti vikoristani yak formalne viznachennya mnozhini racionalnih chisel Napriklad ekvivalentnim param 1 3 2 6 5 15 vidpovidaye rivnist drobiv 13 26 515 displaystyle frac 1 3 frac 2 6 frac 5 15 Vidnoshennya rivnosti za modulem a b modn a b Z displaystyle a equiv b pmod n a b in mathbb Z na mnozhini cilih chisel Z displaystyle mathbb Z ye vidnoshennyam ekvivalentnosti Klasi ekvivalentnosti a n a a n a 2n a 3n displaystyle overline a n left a a pm n a pm 2n a pm 3n ldots right Nehaj dane chislo anan 1 a3a2a1 displaystyle a n a n 1 cdot cdot cdot a 3 a 2 a 1 de ai 0 1 2 9 displaystyle a i 0 1 2 9 Todi vsyaku grupu cifr ai 2ai 1ai i 1 mod3 displaystyle a i 2 a i 1 a i i equiv 1 pmod 3 nazivayut klasom Grupa cifr a3a2a1 displaystyle a 3 a 2 a 1 pershij klas klas odinic a6a5a4 displaystyle a 6 a 5 a 4 drugij klas klas tisyach tosho Nehaj H displaystyle H ye pidgrupoyu grupi G displaystyle G U grupi G displaystyle G diye zakon ekvivalentnosti x y displaystyle x sim y yaksho xy 1 H displaystyle xy 1 in H Vinikaye klas sumizhnosti grupi G displaystyle G po grupi H displaystyle H Faktorizaciya vidobrazhenVidobrazhennya p x Cx displaystyle p colon x mapsto C x nazivayetsya prirodnim vidobrazhennyam abo kanonichnoyi proyekciyeyu X displaystyle X na faktor mnozhinu X displaystyle X sim Nehaj X displaystyle X Y displaystyle Y mnozhini f X Y displaystyle f colon X to Y vidobrazhennya todi binarne vidnoshennya xRfy displaystyle x R f y viznachene pravilom xRf y f x f y x y X displaystyle x mathop R f y iff f x f y quad x y in X ye vidnoshennyam ekvivalentnosti na X displaystyle X Pri comu vidobrazhennya f displaystyle f indukuye vidobrazhennya f X Rf Y displaystyle overline f colon X R f to Y yake viznachayetsya pravilom f Cx f x displaystyle overline f C x f x abo sho te zh same f p x f x displaystyle overline f circ p x f x Pri comu vihodit faktorizaciya vidobrazhennya f displaystyle f na syur yektivne vidobrazhennya p displaystyle p i in yektivne vidobrazhennya f displaystyle overline f Div takozhFaktor mnozhina Faktor struktura Teoremi pro izomorfizmiDzherelaKuratovskij K Mostovskij A Teoriya mnozhestv Set Theory Teoria mnogosci M Mir 1970 416 s ros Hausdorf F Teoriya mnozhestv Moskva Leningrad 1937 304 s ISBN 978 5 382 00127 2 ros Kurosh A G Obshaya algebra M Mir 1970 162 s ros Universalnaya algebra Moskva Mir 1968 351 s ros