В математиці, бінарне відношення R на множині X є транзитивним, якщо для будь-яких a, b, та c з X, виконується: коли a відноситься до b і b відноситься до c, то a відноситься до c.
Формально:
Нетранзитивне відношення
- Якщо ця умова дотримується не для всіх трійок a, b, c, то таке відношення називається нетранзитивним. Наприклад, не для всіх трійок
вірно, що
.
- Бінарне відношення R, задане на множині X називається нетранзитивним, якщо
.
Антитранзитивне відношення
- Існує більш «сильна» властивість — антитранзитивність. Під цим терміном розуміється, що для будь-яких трійок a, b, c відсутня транзитивність. Антитранзитивне відношення, наприклад — відношення перемогти в турнірах «на виліт»: якщо A переміг гравця B, а B переміг гравця C, то A не грав з C, отже, не міг його перемогти.
- Бінарне відношення
, задане на множині
називається антитранзитивним, якщо для
.
Особливості
- Якщо відношення
транзитивне, то зворотне відношення
також транзитивне. Нехай
, але за визначенням оберненого відношення
. Так як
транзитивне, то
і
, що й потрібно було довести.
- Якщо відношення
транзитивні, то відношення
транзитивне. Нехай
. З транзитивності
слідує
, але з визначення перетину відносин отримуємо
, що й потрібно було довести.
Приклади транзитивних відношень
- Відношення часткового порядку:
- строга нерівність
- нестрога нерівність
- включення підмножини:
- строга підмножина
- нестрога підмножина
- строга підмножина
- подільність:
- строга нерівність
- Рівність
- Еквівалентність
- Імплікація
- Паралельність
- Відношення подібності геометрических фігур
- Бути предком.
Приклади нетранзитивних відношень
- Харчовий ланцюжок: це відношення не завжди є транзитивним (приклад — вовки їдять оленів, олені їдять траву, але вовки не їдять траву).
- Бути переважніше ніж. Якщо ми хочемо яблуко замість апельсина, а замість яблука ми б хотіли кавун, то це не значить, що ми віддамо перевагу кавуну.
- Бути другом.
- Бути колегою по роботі.
- Бути підлеглим. Наприклад, у часи феодального ладу в Західній Європі була в ходу приказка: «Васал мого васала — не мій васал».
- Бути схожим на іншу людину.
Приклади антитранзитивних відношень
- Бути сином (батьком, бабусею).
- Гра «Камінь, ножиці, папір». Камінь перемагає ножиці, ножиці виграють у паперу, але камінь програє паперові і т. д.
Джерела
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : , 1937. — 304 с. — .(рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, 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 a R a displaystyle aRa antirefleksivnist a R a displaystyle lnot aRa simetrichnist a R b b R a displaystyle aRb Rightarrow bRa asimetrichnist a R b b R a displaystyle aRb Rightarrow lnot bRa antisimetrichnist a R b b R a a b displaystyle aRb wedge bRa Rightarrow a b tranzitivnist a R b b R c a R c displaystyle aRb wedge bRc Rightarrow aRc antitranzitivnist a R b b R c a R c displaystyle aRb wedge bRc Rightarrow lnot aRc povnota a R b b R a displaystyle aRb vee bRa V matematici binarne vidnoshennya R na mnozhini X ye tranzitivnim yaksho dlya bud yakih a b ta c z X vikonuyetsya koli a vidnositsya do b i b vidnositsya do c to a vidnositsya do c Formalno a b c X a R b b R c a R c displaystyle forall a b c in X aRb land bRc Rightarrow aRc Netranzitivne vidnoshennyaYaksho cya umova dotrimuyetsya ne dlya vsih trijok a b c to take vidnoshennya nazivayetsya netranzitivnim Napriklad ne dlya vsih trijok a b c N displaystyle a b c in mathbb N virno sho a b b c a c displaystyle a nmid b land b nmid c Rightarrow a nmid c Binarne vidnoshennya R zadane na mnozhini X nazivayetsya netranzitivnim yaksho a b c X a R b b R c a R c displaystyle exists a b c in X colon aRb land bRc land neg aRc Antitranzitivne vidnoshennyaIsnuye bilsh silna vlastivist antitranzitivnist Pid cim terminom rozumiyetsya sho dlya bud yakih trijok a b c vidsutnya tranzitivnist Antitranzitivne vidnoshennya napriklad vidnoshennya peremogti v turnirah na vilit yaksho A peremig gravcya B a B peremig gravcya C to A ne grav z C otzhe ne mig jogo peremogti Binarne vidnoshennya R displaystyle R zadane na mnozhini X displaystyle X nazivayetsya antitranzitivnim yaksho dlya a b c X a R b b R c a R c displaystyle forall a b c in X colon aRb land bRc Rightarrow neg aRc OsoblivostiYaksho vidnoshennya R displaystyle R tranzitivne to zvorotne vidnoshennya R 1 displaystyle R 1 takozh tranzitivne Nehaj a R 1 b b R 1 c displaystyle aR 1 b bR 1 c ale za viznachennyam obernenogo vidnoshennya c R b b R a displaystyle cRb bRa Tak yak R displaystyle R tranzitivne to c R a displaystyle cRa i a R 1 c displaystyle aR 1 c sho j potribno bulo dovesti Yaksho vidnoshennya R S displaystyle R S tranzitivni to vidnoshennya T R S displaystyle T R cap S tranzitivne Nehaj a T b b T c a R b a S b b R c b S c displaystyle aTb bTc Rightarrow aRb aSb bRc bSc Z tranzitivnosti R S displaystyle R S sliduye a R c a S c displaystyle aRc aSc ale z viznachennya peretinu vidnosin otrimuyemo a T c displaystyle aTc sho j potribno bulo dovesti Prikladi tranzitivnih vidnoshenVidnoshennya chastkovogo poryadku stroga nerivnist a lt b b lt c a lt c displaystyle colon a lt b b lt c Rightarrow a lt c nestroga nerivnist a lt b b lt c a lt c displaystyle colon a lt b b lt c Rightarrow a lt c vklyuchennya pidmnozhini stroga pidmnozhina A B a n d B C A C displaystyle A subset B and B subset C Rightarrow A subset C nestroga pidmnozhina A B a n d B C A C displaystyle A subseteq B and B subseteq C Rightarrow A subseteq C podilnist a b b c a c displaystyle a mid b b mid c Rightarrow a mid c a b b c a c displaystyle a vdots b b vdots c Rightarrow a vdots c Rivnist a b b c a c displaystyle colon a b b c Rightarrow a c Ekvivalentnist a b b c a c displaystyle colon a Leftrightarrow b b Leftrightarrow c Rightarrow a Leftrightarrow c Implikaciya a b b c a c displaystyle colon a Rightarrow b b Rightarrow c Longrightarrow a Rightarrow c Paralelnist a b b c a c displaystyle colon a parallel b b parallel c Rightarrow a parallel c Vidnoshennya podibnosti geometricheskih figur Buti predkom Prikladi netranzitivnih vidnoshenHarchovij lancyuzhok ce vidnoshennya ne zavzhdi ye tranzitivnim priklad vovki yidyat oleniv oleni yidyat travu ale vovki ne yidyat travu Buti perevazhnishe nizh Yaksho mi hochemo yabluko zamist apelsina a zamist yabluka mi b hotili kavun to ce ne znachit sho mi viddamo perevagu kavunu Buti drugom Buti kolegoyu po roboti Buti pidleglim Napriklad u chasi feodalnogo ladu v Zahidnij Yevropi bula v hodu prikazka Vasal mogo vasala ne mij vasal Buti shozhim na inshu lyudinu Prikladi antitranzitivnih vidnoshenButi sinom batkom babuseyu Gra Kamin nozhici papir Kamin peremagaye nozhici nozhici vigrayut u paperu ale kamin prograye paperovi i t d DzherelaKuratovskij 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