Кіріспе

Бинарлық қатынастың түрі

Математикада, егер X жиынындағы кез келген a, b, c элементтері үшін R қатынасы a-ны b-ға және b-ны c-ға қатыстырса, онда R қатынасы a-ны c-ға да қатыстырады. Бұл қатынас транзитивті деп аталады.

Кез келген ішінара реттеу және кез келген эквиваленттік қатынас транзитивті болады. Мысалы, нақты сандар арасындағы теңсіздік және теңдік екеуі де транзитивті: егер a < b және b < c болса, онда a < c; ал егер a = b және b = c болса, онда a = c.

Жабылу қасиеттері

Транзитивті қатынастың керісі (инверсі) әрқашан транзитивті болады. Мысалы, "кіші жиын" қатынасы транзитивті екенін, ал "үлкен жиын" қатынасы оның керісі екенін білгенде, соңғысы да транзитивті деп қорытынды жасауға болады. Екі транзитивті қатынастың қиылысы әрқашан транзитивті болады. Мысалы, "бұрын туған" және "аты бір" қатынастары транзитивті болса, "бұрын туған және аты бір" қатынасы да транзитивті деп қорытынды жасауға болады. Екі транзитивті қатынастың бірігуі транзитивті болуы міндетті емес. Мысалы, "бұрын туған немесе аты бір" қатынасы транзитивті емес, себебі мысалы, Герберт Гувер Франклин Д. Рузвельтпен байланысты, ал ол өз кезегінде Франклин Пирспен байланысты, бірақ Гувер Франклин Пирспен байланысты емес. Транзитивті қатынастың толықтыруы транзитивті болуы міндетті емес. Мысалы, "тең" қатынасы транзитивті болса, "тең емес" қатынасы тек ең көп дегенде бір элементі бар жиынтарда ғана транзитивті болады.

Транзитивті кеңейтулер мен транзитивті жабулар

R жиынындағы X екілік қатынас болсын. R-дің R1 деп белгіленетін транзитивті кеңейтімі – X жиынындағы ең кіші екілік қатынас болып табылады, егер R1, R-ді қамтитын болса, және егер (a, b) ∈ R және (b, c) ∈ R болса, онда (a, c) ∈ R1. Мысалы, X – кейбір қалалар жиыны болсын, олардың кейбіреулері жолдармен байланысқан. R – қалалар арасындағы қатынас болсын, егер A және B қалаларын тікелей байланыстыратын жол болса, онда (A, B) ∈ R. Бұл қатынас міндетті түрде транзитивті болуы керек емес. Осы қатынастың транзитивті кеңейтімі (A, C) ∈ R1 арқылы анықталады, егер A және C қалалары арасында ең көп дегенде екі жол арқылы саяхаттауға болады. Егер қатынас транзитивті болса, онда оның транзитивті кеңейтімі өзі болады, яғни егер R транзитивті қатынас болса, онда R1 = R. R1 транзитивті кеңейтімі R2 деп белгіленеді, және осылай жалғаса береді, жалпы алғанда, Ri транзитивті кеңейтімі Ri+1 болады. R-дің транзитивті жабылуы R* немесе R^(∞) деп белгіленеді және R, R1, R2 жиындарының бірігуіне тең болады. Қатынастың транзитивті жабылуы – транзитивті қатынас болып табылады. Дегенмен, бір мезгілде рефлексивті, симметриялық және транзитивті қатынастардың санын табуға арналған формула бар – яғни, эквиваленттік қатынастар, симметриялық және транзитивті қатынастар, симметриялық, транзитивті және антисимметриялық қатынастар, сондай-ақ толық, транзитивті және антисимметриялық қатынастар. Пфайффер осы бағытта белгілі бір прогреске қол жеткізді, бұл қасиеттерді бірін-бірімен байланыстырып, оларды комбинациялар түрінде көрсетті, бірақ кез келгенін есептеу әлі де қиын. Сондай-ақ, Brinkmann және McKay (2005) еңбегіне қараңыз. Кез келген транзитивті қатынастың рефлексификациясы алдын ала тәртіп болғандықтан, n элементтен тұратын жиындағы транзитивті қатынастардың саны алдын ала тәртіптер санынан екі есе көп, демек, Клейтман мен Ротшильдтің нәтижелері бойынша асимптотикалық түрде өседі.