рефлексивність
антирефлексивність
транзитивність
(антитранзитивність)
Бінарне відношення (бінарне відношення на множині) — в математиці окремий випадок відношення заданого на множині M, яке встановлюється між двома елементами множини. Іншими словами, це підмножина декартового квадрата M2 = M × M.
Також кажуть, що елементи a, b ∈ M перебувають у бінарному відношенні R (часто записують у вигляді aRb), якщо впорядкована пара (a, b) ∈ R і записують, що R ⊆ M×M.
Взагалі, бінарне відношення між двома множинами A і B — це підмножина A × B. В цьому випадку вживають термін відповідність між множинами. Термін 2-місне відношення або 2-арне відношення є синонімами бінарного відношення.
В деяких системах (аксіом теорії множин), відношення розширюються до класів, які є узагальненнями множин. Таке розширення потрібне, зокрема для того, щоб формалізувати поняття «є елементом» або «є підмножиною» теорії множин і запобіганню таких невідповідностей, як парадокс Расселла.
Приклади
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
Приклади бінарних відношень на множині натуральних чисел :
- R1 — відношення
(«менше або дорівнює»), тоді 4 R1 9 та 5 R1 5.
- R2 — відношення «ділиться на», тоді 4 R2 2, 49 R2 7, m R2 1 для будь-якого натурального m.
- R3 — відношення «є взаємно простими», тоді 15 R3 8, 366 R3 121, 1001 R3 612.
- R4 — відношення «складаються з однакових цифр», тоді 127 R4 721, 230 R4 302, 3231 R4 3213311.
- Шахівниця. Множина
На декартовому добутку
задано відношення
Відношення
задає на шаховій дошці чорні клітини — клітини у яких сума координат буде парним числом.
Види відношень
- Рефлексивне транзитивне відношення називається відношенням квазіпорядку.
- Рефлексивне симетричне транзитивне відношення називається відношенням еквівалентності.
- Рефлексивне антисиметричне транзитивне відношення називається відношенням (часткового) порядку.
- Антирефлексивне антисиметричне транзитивне відношення називається відношенням строгого порядку.
- Повне антисиметричне (для будь-яких x, y виконується xRy або yRx) транзитивне відношення називається відношенням лінійного порядку.
- Антирефлексивне антисиметричне відношення називається відношенням домінування.
Операції з відношеннями
Оскільки відношення на M є також множинами, то над ними дозволені теоретико-множинні операції. Наприклад:
- перетином бінарних відношень «більше або дорівнює» і «менше або дорівнює» є відношення «дорівнює»,
- об'єднанням відношень «менше» і «більше» є відношення «не дорівнює»,
- доповненням відношення «ділиться на» є відношення «не ділиться на» тощо.
Обернене відношення
Відношення R−1 називається оберненим до відношення R, якщо bR−1a тоді і тільки тоді, коли aRb. Очевидно, що (R−1)−1=R.
Наприклад, для відношення «більше або дорівнює» оберненим є відношення «менше або дорівнює», для відношення «ділиться на» — відношення «є дільником».
Композиція
Композицією відношень R1 і R2 на множині M (позначається R1oR2) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент c∈M, для якого виконується aR1c і cR2b.
Наприклад, композицією відношень R1 — «є сином» і R2 — «є братом» на множині чоловіків є відношення R1oR2 — «є небожем».
Властивості
Нехай R — деяке відношення на множині M. Відношення R називається:
- оберненим (відношення, обернене до R), якщо воно складається з пар елементів (у, х), отриманих перестановкою пар елементів (х, у) даного відношення R. Позначається: R−1. Для даного відношення і оберненого до нього виконується рівність: (R−1)−1 = R.
- взаємообернені відношення — відношення, що є оберненими одне до одного. Область значень одного з них служить областю визначення іншого, а область визначення першого — областю значень іншого.
- рефлексивним, якщо для всіх a ∈ M має місце aRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-якого х цієї множини елемент х перебуває у відношенні R до самого себе, тобто для будь-якого елемента х цієї множини має місце xRx. Приклади рефлексивних відношень: рівність, одночасність, подібність.
- корефлексивним, якщо будь-які два елементи
множини
, що перебувають у відношенні
(що записують ще як
), збігаються
.
- антирефлексивним (іррефлексивним), якщо для жодного a ∈ M не виконується aRa. Відзначимо, що так само, як антисиметричність не збігається з несиметричністю, іррефлексівність не збігається з нерефлексивністю. Двомісне відношення R, визначене на деякій множині M і відрізняється тим, що для будь-якого елемента х цієї множини не виконується, що воно перебуває у відношенні R до самого себе (відсутнє xRx), тобто можливий випадок, що елемент множини не перебуває у відношенні R до самого себе. Приклади нерефлексивних відношень: «дбати про», «розважати», «нервувати».
- симетричним, якщо для всіх a, b∈ M таких, що aRb маємо bRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких елементів х і у цієї множини з того, що х перебуває до у відношенні R (xRy), випливає, що й у перебуває в тому ж відношенні до х (yRx). Прикладами симетричних відношень є рівність (=), відношення еквівалентності, подібності, одночасності, деякі відношення споріднення.
- асиметричним, якщо для всіх a, b∈ M таких, що aRb не виконується bRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy слідує заперечення yRx. Приклад: відношення «більше» (>) і «менше» (<).
- антисиметричним, якщо для всіх a, b∈ M таких, що aRb і a
b, маємо що bRa — не виконується. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy і xR — 1y випливає х = у (тобто R і R−1 виконуються одночасно лише для рівних між собою членів).
- транзитивним, якщо зі співвідношень aRb і bRc випливає aRc. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz випливає xRz (xRy &
). Приклади транзитивних відношень: «більше», «менше», «дорівнює», «подібно», «вище», «північніше».
- нетранзитивним, якщо для будь-яких х, у, z із множини, на якій визначено відношення, з xRy і yRz не випливає xRz. Приклад нетранзитивного відношення: «x батько y».
- повним, якщо для будь-яких a, b ∈ M випливає, що aRb або bRa.
- відношенням порядку, якщо воно володіє тільки деякими з трьох властивостей відношення еквівалентності. Зокрема, відношення рефлексивне і транзитивне, але несиметричне (наприклад, «не більше») утворює «нестрогий» порядок. Відношення транзитивне, але нерефлексивне і несиметричне (наприклад, «менше») — «строгий» порядок.
- функцією, якщо кожному значенню x відношення xRy відповідає лише одне — єдине значення y. Приклад: «y батько x». Властивість функціональності відношення R записується у вигляді аксіоми: (xRy і xRz) → (y ≡ z). Оскільки кожному значенню x у виразах xRy і xRz відповідає одне і те ж значення, то y і z збіжаться, виявляться одними і тими ж. Функціональне відношення однозначне, оскільки кожному значенню x відношення xRy відповідає єдине значення y, але не навпаки.
- бієкцією, якщо кожному значенню х відповідає єдине значення у, і кожному значенню у відповідає єдине значення х.
- відношенням зв'язку, якщо для будь-яких двох різних елементів х та у із множини, на якій визначено відношення, одне з них перебуває у відношенні R до іншого (тобто виконано одне з двох співвідношень: xRy або yRx). Приклад: відношення «менше» (<).
Якщо відношення R має будь-яку з перерахованих вище властивостей, то обернене відношення R−1 також має ту саму властивість. Таким чином, операція обернення зберігає всі ці властивості відношень.
Відношення, яке є рефлексивним, симетричним та транзитивним, називається відношенням еквівалентності.
З поняттям відношення еквівалентності тісно пов'язане поняття розбиття.
Теорема 1. Відношення Е є відношенням еквівалентності на множині R тоді й лише тоді, коли воно визначає розбиття ПЕ на множині R.
Доведення.
а) Пряме. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що означає, що належать одній і тій ж підмножині Ri розбиття П. Тоді відношення Е(П) — рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду для кожного симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду то включаємо і пару вигляду, транзитивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду, то включаємо і пару вигляду Таким чином, відношення Е(П) — відношення еквівалентності.
б) Обернене. Нехай задано на R відношення еквівалентності E. Легко побудувати функцію котра елементу ri ставить у відповідність підмножину Тому що відношення Е рефлексивне, то а отже Залишається показати, що будь-які дві підмножини або не перетинаються, або є рівними. Нехай це не так і є загальний елемент але підмножини і не рівні. Але тоді справедливо В силу симетричності відношення E, якщо виконується то виконується За наявності в відношенні E пар в силу транзитивності відношення E в ньому присутня пара З того, що для будь-якого справедливо і, отже, в силу транзитивності справедливо слідує, що Помінявши місцями елементи аналогічно встановлюємо справедливість Але це означає Іншими словами, будь-які підмножини або не перетинаються, або є рівними. З кожної групи таких рівних підмножин залишимо по одній підмножині, отримавши різні підмножини, що задовольняють другому обмеженню на розбиття. Теорема доведена.
Відношення, яке є рефлексивним, антисиметричним та транзитивним, називається відношенням часткового порядку.
Відношення часткового порядку, яке є повним, називається відношенням лінійного порядку (чи лінійним порядком).
Властивості відношень за назвами
Назва | рефлексивність | антирефлексивність | симетричність | асиметричність | антисиметричність | транзитивність | повнота |
---|---|---|---|---|---|---|---|
Перевага | + | ||||||
Подібність (толерантність) | + | + | |||||
Еквівалентність | + | + | + | ||||
Часткова еквівалентність | + | + | |||||
Квазіпорядок | + | + | |||||
Впорядкування | + | + | + | ||||
Частковий порядок | + | + | + | ||||
Лінійний порядок | + | + | + | + | |||
Строгий квазіпорядок | + | + | |||||
Строгий порядок | + | + | (+) | + | |||
Домінування | + | + | (+) | ||||
Строгий частковий порядок | + | + | (+) | + | |||
Строгий лінійний порядок | + | + | (+) | + | + |
Способи задання відношень
Для того, щоб задати відношення (R, Ω), необхідно задати всі пари елементів (x, y)∈Ω×Ω, які включено в множину R. Крім повного переліку всіх пар, існують три способи задання відношень: за допомогою матриці, графу й розрізів. Перші два способи застосовують, щоб задати відношення на скінченних множинах, задання відношення розрізами може бути застосовано й до нескінченних множин.
Задання відношення за допомогою матриці
Нехай множина Ω складається з n елементів, R– подане на цій множині бінарне відношення. Пронумеруємо елементи множини Ω цілими числами від 1 до n. Для того, щоб задати відношення, побудуємо квадратну таблицю розміром n×n. Її i-й рядок відповідає елементу xi множини Ω, j-й стовпчик — елементу xj з множини Ω. На перетині i-го рядка та j-го стовпчика ставимо 1, якщо елемент xi перебуває у відношенні R з елементом xj , і нуль в інших випадках.
Задання відношення за допомогою графу
Для того, щоб задати відношення за допомогою графу, поставимо у взаємно однозначну відповідність елементам скінченної множини Ω, на якій визначено відношення, вершини графу x1,…,xn (за будь-якою нумерацією).
Провести дугу від вершини xi до xj, можна тоді й тільки тоді, коли елемент xi перебуває у відношенні R з елементом xj, коли ж i = j, то дуга (xi,xj) перетворюється на петлю при вершині xi.
Задання відношень за допомогою розрізів
Верхнім розрізом відношення (R,Ω) в елементі x, позначене через R+(x), називається множина елементів y∈Ω, для яких виконано умову: (y, x)∈R, тобто R+(x)={y∈Ω|(y, x)∈R}.
Нижнім розрізом відношення (R,Ω) в елементі x, позначене через R-(x), називається множина елементів y∈Ω, для яких виконано умову: (x, y)∈R, а саме R-(x)={y∈Ω|(x, y)∈R}.
Отже, верхній розріз (множина R+) являє собою множину всіх таких елементів y, що перебувають у відношенні R з фіксованим елементом х(yRx). Нижній розріз (множина R-) — це множина всіх таких елементів у, з якими фіксований елемент х перебуває у відношенні R(xRy).
Таким чином, для того, щоб задати відношення за допомогою розрізів, необхідно описати всі верхні або всі нижні його розрізи. Тобто відношення R буде задано, якщо для кожного елемента x∈Ω задано множину R+(x) або для кожного елемента x∈Ω задано множину R-(x).
Див. також
Джерела
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : , 1937. — 304 с. — .(рос.)
- Fonseca de Oliveira, J. N., & Pereira Cunha Rodrigues, C. D. J. (2004). Transposing Relations: From Maybe Functions to Hash Tables. In Mathematics of Program Construction (p. 337). URL: https://link.springer.com/chapter/10.1007%2F978-3-540-27764-4_18 [ 2018-06-17 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Vlastivosti binarnih vidnoshen a b c X displaystyle forall a b c in X refleksivnist aRa displaystyle aRa antirefleksivnist aRa displaystyle lnot aRa simetrichnist aRb bRa displaystyle aRb Rightarrow bRa asimetrichnist aRb bRa displaystyle aRb Rightarrow lnot bRa antisimetrichnist aRb bRa a b displaystyle aRb wedge bRa Rightarrow a b tranzitivnist aRb bRc aRc displaystyle aRb wedge bRc Rightarrow aRc antitranzitivnist aRb bRc aRc displaystyle aRb wedge bRc Rightarrow lnot aRc povnota aRb bRa displaystyle aRb vee bRa Binarne vidnoshennya binarne vidnoshennya na mnozhini v matematici okremij vipadok vidnoshennya zadanogo na mnozhini M yake vstanovlyuyetsya mizh dvoma elementami mnozhini Inshimi slovami ce pidmnozhina dekartovogo kvadrata M2 M M Takozh kazhut sho elementi a b M perebuvayut u binarnomu vidnoshenni R chasto zapisuyut u viglyadi aRb yaksho vporyadkovana para a b R i zapisuyut sho R M M Vzagali binarne vidnoshennya mizh dvoma mnozhinami A i B ce pidmnozhina A B V comu vipadku vzhivayut termin vidpovidnist mizh mnozhinami Termin 2 misne vidnoshennya abo 2 arne vidnoshennya ye sinonimami binarnogo vidnoshennya V deyakih sistemah aksiom teoriyi mnozhin vidnoshennya rozshiryuyutsya do klasiv yaki ye uzagalnennyami mnozhin Take rozshirennya potribne zokrema dlya togo shob formalizuvati ponyattya ye elementom abo ye pidmnozhinoyu teoriyi mnozhin i zapobigannyu takih nevidpovidnostej yak paradoks Rassella PrikladiShahova doshka 5x5 U chornih klitin suma koordinat parne chislo Prikladi binarnih vidnoshen na mnozhini naturalnih chisel N displaystyle mathbb N R1 vidnoshennya displaystyle leqslant menshe abo dorivnyuye todi 4 R1 9 ta 5 R1 5 R2 vidnoshennya dilitsya na todi 4 R2 2 49 R2 7 m R2 1 dlya bud yakogo naturalnogo m R3 vidnoshennya ye vzayemno prostimi todi 15 R3 8 366 R3 121 1001 R3 612 R4 vidnoshennya skladayutsya z odnakovih cifr todi 127 R4 721 230 R4 302 3231 R4 3213311 Shahivnicya Mnozhina A 1 2 3 4 5 displaystyle A 1 2 3 4 5 Na dekartovomu dobutku A A displaystyle A times A zadano vidnoshennya R a b a b A a b 0 mod2 displaystyle R a b a b in A a b equiv 0 pmod 2 Vidnoshennya R displaystyle R zadaye na shahovij doshci chorni klitini klitini u yakih suma koordinat bude parnim chislom Vidi vidnoshenRefleksivne tranzitivne vidnoshennya nazivayetsya vidnoshennyam kvaziporyadku Refleksivne simetrichne tranzitivne vidnoshennya nazivayetsya vidnoshennyam ekvivalentnosti Refleksivne antisimetrichne tranzitivne vidnoshennya nazivayetsya vidnoshennyam chastkovogo poryadku Antirefleksivne antisimetrichne tranzitivne vidnoshennya nazivayetsya vidnoshennyam strogogo poryadku Povne antisimetrichne dlya bud yakih x y vikonuyetsya xRy abo yRx tranzitivne vidnoshennya nazivayetsya vidnoshennyam linijnogo poryadku Antirefleksivne antisimetrichne vidnoshennya nazivayetsya vidnoshennyam dominuvannya Operaciyi z vidnoshennyamiOskilki vidnoshennya na M ye takozh mnozhinami to nad nimi dozvoleni teoretiko mnozhinni operaciyi Napriklad peretinom binarnih vidnoshen bilshe abo dorivnyuye i menshe abo dorivnyuye ye vidnoshennya dorivnyuye ob yednannyam vidnoshen menshe i bilshe ye vidnoshennya ne dorivnyuye dopovnennyam vidnoshennya dilitsya na ye vidnoshennya ne dilitsya na tosho Obernene vidnoshennyaDokladnishe Obernene vidnoshennya Vidnoshennya R 1 nazivayetsya obernenim do vidnoshennya R yaksho bR 1a todi i tilki todi koli aRb Ochevidno sho R 1 1 R Napriklad dlya vidnoshennya bilshe abo dorivnyuye obernenim ye vidnoshennya menshe abo dorivnyuye dlya vidnoshennya dilitsya na vidnoshennya ye dilnikom KompoziciyaKompoziciyeyu vidnoshen R1 i R2 na mnozhini M poznachayetsya R1oR2 nazivayetsya vidnoshennya R na M take sho aRb todi i tilki todi koli isnuye element c M dlya yakogo vikonuyetsya aR1c i cR2b Napriklad kompoziciyeyu vidnoshen R1 ye sinom i R2 ye bratom na mnozhini cholovikiv ye vidnoshennya R1oR2 ye nebozhem VlastivostiNehaj R deyake vidnoshennya na mnozhini M Vidnoshennya R nazivayetsya obernenim vidnoshennya obernene do R yaksho vono skladayetsya z par elementiv u h otrimanih perestanovkoyu par elementiv h u danogo vidnoshennya R Poznachayetsya R 1 Dlya danogo vidnoshennya i obernenogo do nogo vikonuyetsya rivnist R 1 1 R vzayemooberneni vidnoshennya vidnoshennya sho ye obernenimi odne do odnogo Oblast znachen odnogo z nih sluzhit oblastyu viznachennya inshogo a oblast viznachennya pershogo oblastyu znachen inshogo refleksivnim yaksho dlya vsih a M maye misce aRa Binarne vidnoshennya R viznachene na deyakij mnozhini i vidriznyayetsya tim sho dlya bud yakogo h ciyeyi mnozhini element h perebuvaye u vidnoshenni R do samogo sebe tobto dlya bud yakogo elementa h ciyeyi mnozhini maye misce xRx Prikladi refleksivnih vidnoshen rivnist odnochasnist podibnist korefleksivnim yaksho bud yaki dva elementi a b displaystyle a b mnozhini X displaystyle X sho perebuvayut u vidnoshenni a b R displaystyle a b in R sho zapisuyut she yak aRb displaystyle aRb zbigayutsya a b displaystyle a b antirefleksivnim irrefleksivnim yaksho dlya zhodnogo a M ne vikonuyetsya aRa Vidznachimo sho tak samo yak antisimetrichnist ne zbigayetsya z nesimetrichnistyu irrefleksivnist ne zbigayetsya z nerefleksivnistyu Dvomisne vidnoshennya R viznachene na deyakij mnozhini M i vidriznyayetsya tim sho dlya bud yakogo elementa h ciyeyi mnozhini ne vikonuyetsya sho vono perebuvaye u vidnoshenni R do samogo sebe vidsutnye xRx tobto mozhlivij vipadok sho element mnozhini ne perebuvaye u vidnoshenni R do samogo sebe Prikladi nerefleksivnih vidnoshen dbati pro rozvazhati nervuvati simetrichnim yaksho dlya vsih a b M takih sho aRb mayemo bRa Binarne vidnoshennya R viznachene na deyakij mnozhini i vidriznyayetsya tim sho dlya bud yakih elementiv h i u ciyeyi mnozhini z togo sho h perebuvaye do u vidnoshenni R xRy viplivaye sho j u perebuvaye v tomu zh vidnoshenni do h yRx Prikladami simetrichnih vidnoshen ye rivnist vidnoshennya ekvivalentnosti podibnosti odnochasnosti deyaki vidnoshennya sporidnennya Simetrichne vidnoshennyaasimetrichnim yaksho dlya vsih a b M takih sho aRb ne vikonuyetsya bRa Binarne vidnoshennya R viznachene na deyakij mnozhini i vidriznyayetsya tim sho dlya bud yakih h ta u z xRy sliduye zaperechennya yRx Priklad vidnoshennya bilshe gt i menshe lt antisimetrichnim yaksho dlya vsih a b M takih sho aRb i a displaystyle neq b mayemo sho bRa ne vikonuyetsya Binarne vidnoshennya R viznachene na deyakij mnozhini i vidriznyayetsya tim sho dlya bud yakih h ta u z xRy i xR 1y viplivaye h u tobto R i R 1 vikonuyutsya odnochasno lishe dlya rivnih mizh soboyu chleniv tranzitivnim yaksho zi spivvidnoshen aRb i bRc viplivaye aRc Binarne vidnoshennya R viznachene na deyakij mnozhini i vidriznyayetsya tim sho dlya bud yakih h u z ciyeyi mnozhini z xRy i yRz viplivaye xRz xRy amp yRz xRz displaystyle yRz to xRz Prikladi tranzitivnih vidnoshen bilshe menshe dorivnyuye podibno vishe pivnichnishe netranzitivnim yaksho dlya bud yakih h u z iz mnozhini na yakij viznacheno vidnoshennya z xRy i yRz ne viplivaye xRz Priklad netranzitivnogo vidnoshennya x batko y povnim yaksho dlya bud yakih a b M viplivaye sho aRb abo bRa vidnoshennyam poryadku yaksho vono volodiye tilki deyakimi z troh vlastivostej vidnoshennya ekvivalentnosti Zokrema vidnoshennya refleksivne i tranzitivne ale nesimetrichne napriklad ne bilshe utvoryuye nestrogij poryadok Vidnoshennya tranzitivne ale nerefleksivne i nesimetrichne napriklad menshe strogij poryadok funkciyeyu yaksho kozhnomu znachennyu x vidnoshennya xRy vidpovidaye lishe odne yedine znachennya y Priklad y batko x Vlastivist funkcionalnosti vidnoshennya R zapisuyetsya u viglyadi aksiomi xRy i xRz y z Oskilki kozhnomu znachennyu x u virazah xRy i xRz vidpovidaye odne i te zh znachennya to y i z zbizhatsya viyavlyatsya odnimi i timi zh Funkcionalne vidnoshennya odnoznachne oskilki kozhnomu znachennyu x vidnoshennya xRy vidpovidaye yedine znachennya y ale ne navpaki biyekciyeyu yaksho kozhnomu znachennyu h vidpovidaye yedine znachennya u i kozhnomu znachennyu u vidpovidaye yedine znachennya h vidnoshennyam zv yazku yaksho dlya bud yakih dvoh riznih elementiv h ta u iz mnozhini na yakij viznacheno vidnoshennya odne z nih perebuvaye u vidnoshenni R do inshogo tobto vikonano odne z dvoh spivvidnoshen xRy abo yRx Priklad vidnoshennya menshe lt Yaksho vidnoshennya R maye bud yaku z pererahovanih vishe vlastivostej to obernene vidnoshennya R 1 takozh maye tu samu vlastivist Takim chinom operaciya obernennya zberigaye vsi ci vlastivosti vidnoshen Vidnoshennya yake ye refleksivnim simetrichnim ta tranzitivnim nazivayetsya vidnoshennyam ekvivalentnosti Z ponyattyam vidnoshennya ekvivalentnosti tisno pov yazane ponyattya rozbittya Teorema 1 Vidnoshennya E ye vidnoshennyam ekvivalentnosti na mnozhini R todi j lishe todi koli vono viznachaye rozbittya PE na mnozhini R Dovedennya a Pryame Nehaj zadane rozbittya P Rozglyanemo vidnoshennya E P take sho oznachaye sho nalezhat odnij i tij zh pidmnozhini Ri rozbittya P Todi vidnoshennya E P refleksivne tomu sho za pobudovoyu mi vklyuchayemo v nogo pari viglyadu dlya kozhnogo simetrichne tomu sho za pobudovoyu yaksho mi vklyuchayemo v nogo paru viglyadu to vklyuchayemo i paru viglyadu tranzitivne tomu sho za pobudovoyu yaksho mi vklyuchayemo v nogo pari viglyadu to vklyuchayemo i paru viglyadu Takim chinom vidnoshennya E P vidnoshennya ekvivalentnosti b Obernene Nehaj zadano na R vidnoshennya ekvivalentnosti E Legko pobuduvati funkciyu kotra elementu ri stavit u vidpovidnist pidmnozhinu Tomu sho vidnoshennya E refleksivne to a otzhe Zalishayetsya pokazati sho bud yaki dvi pidmnozhini abo ne peretinayutsya abo ye rivnimi Nehaj ce ne tak i ye zagalnij element ale pidmnozhini i ne rivni Ale todi spravedlivo V silu simetrichnosti vidnoshennya E yaksho vikonuyetsya to vikonuyetsya Za nayavnosti v vidnoshenni E par v silu tranzitivnosti vidnoshennya E v nomu prisutnya para Z togo sho dlya bud yakogo spravedlivo i otzhe v silu tranzitivnosti spravedlivo sliduye sho Pominyavshi miscyami elementi analogichno vstanovlyuyemo spravedlivist Ale ce oznachaye Inshimi slovami bud yaki pidmnozhini abo ne peretinayutsya abo ye rivnimi Z kozhnoyi grupi takih rivnih pidmnozhin zalishimo po odnij pidmnozhini otrimavshi rizni pidmnozhini sho zadovolnyayut drugomu obmezhennyu na rozbittya Teorema dovedena Vidnoshennya yake ye refleksivnim antisimetrichnim ta tranzitivnim nazivayetsya vidnoshennyam chastkovogo poryadku Vidnoshennya chastkovogo poryadku yake ye povnim nazivayetsya vidnoshennyam linijnogo poryadku chi linijnim poryadkom Vlastivosti vidnoshen za nazvami Nazva refleksivnist antirefleksivnist simetrichnist asimetrichnist antisimetrichnist tranzitivnist povnotaPerevaga Podibnist tolerantnist Ekvivalentnist Chastkova ekvivalentnist Kvaziporyadok Vporyadkuvannya Chastkovij poryadok Linijnij poryadok Strogij kvaziporyadok Strogij poryadok Dominuvannya Strogij chastkovij poryadok Strogij linijnij poryadok Sposobi zadannya vidnoshenDlya togo shob zadati vidnoshennya R W neobhidno zadati vsi pari elementiv x y W W yaki vklyucheno v mnozhinu R Krim povnogo pereliku vsih par isnuyut tri sposobi zadannya vidnoshen za dopomogoyu matrici grafu j rozriziv Pershi dva sposobi zastosovuyut shob zadati vidnoshennya na skinchennih mnozhinah zadannya vidnoshennya rozrizami mozhe buti zastosovano j do neskinchennih mnozhin Zadannya vidnoshennya za dopomogoyu matrici Nehaj mnozhina W skladayetsya z n elementiv R podane na cij mnozhini binarne vidnoshennya Pronumeruyemo elementi mnozhini W cilimi chislami vid 1 do n Dlya togo shob zadati vidnoshennya pobuduyemo kvadratnu tablicyu rozmirom n n Yiyi i j ryadok vidpovidaye elementu xi mnozhini W j j stovpchik elementu xj z mnozhini W Na peretini i go ryadka ta j go stovpchika stavimo 1 yaksho element xi perebuvaye u vidnoshenni R z elementom xj i nul v inshih vipadkah Zadannya vidnoshennya za dopomogoyu grafu Dlya togo shob zadati vidnoshennya za dopomogoyu grafu postavimo u vzayemno odnoznachnu vidpovidnist elementam skinchennoyi mnozhini W na yakij viznacheno vidnoshennya vershini grafu x1 xn za bud yakoyu numeraciyeyu Provesti dugu vid vershini xi do xj mozhna todi j tilki todi koli element xi perebuvaye u vidnoshenni R z elementom xj koli zh i j to duga xi xj peretvoryuyetsya na petlyu pri vershini xi Zadannya vidnoshen za dopomogoyu rozriziv Verhnim rozrizom vidnoshennya R W v elementi x poznachene cherez R x nazivayetsya mnozhina elementiv y W dlya yakih vikonano umovu y x R tobto R x y W y x R Nizhnim rozrizom vidnoshennya R W v elementi x poznachene cherez R x nazivayetsya mnozhina elementiv y W dlya yakih vikonano umovu x y R a same R x y W x y R Otzhe verhnij rozriz mnozhina R yavlyaye soboyu mnozhinu vsih takih elementiv y sho perebuvayut u vidnoshenni R z fiksovanim elementom h yRx Nizhnij rozriz mnozhina R ce mnozhina vsih takih elementiv u z yakimi fiksovanij element h perebuvaye u vidnoshenni R xRy Takim chinom dlya togo shob zadati vidnoshennya za dopomogoyu rozriziv neobhidno opisati vsi verhni abo vsi nizhni jogo rozrizi Tobto vidnoshennya R bude zadano yaksho dlya kozhnogo elementa x W zadano mnozhinu R x abo dlya kozhnogo elementa x W zadano mnozhinu R x Div takozhVidnoshennya na mnozhini Vidpovidnist mizh mnozhinami Vidnoshennya poryadku Vidnoshennya ekvivalentnosti Evklidove vidnoshennyaDzherelaKuratovskij 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 Fonseca de Oliveira J N amp Pereira Cunha Rodrigues C D J 2004 Transposing Relations From Maybe Functions to Hash Tables In Mathematics of Program Construction p 337 URL https link springer com chapter 10 1007 2F978 3 540 27764 4 18 2018 06 17 u Wayback Machine