Рефлексивті және транзитивті екілік қатынас

Кіріспе

Рефлексивті және транзитивті бинарлық қатынас, бинарлық қатынастар

Математикада, әсіресе тәртіп теориясында, алдын ала тәртіп немесе квазиреттік – рефлексивті және транзитивті бинарлық қатынас. «Алдын ала тәртіп» атауы алдын ала тәртіптер жартылай тәртіпке ұқсас екенін, бірақ толыққанды емес екенін көрсетеді, себебі олар міндетті түрде антисимметриялық бола бермейді. Алдын ала тәртіпке табиғи мысал – бүтін сандар, полиномдар немесе коммутативті сақина элементтері арасындағы «x, y-ді бөледі» қатынасы. Мысалы, бөлу қатынасы рефлексивті, өйткені әрбір бүтін сан өзін-өзі бөледі. Бірақ бөлу қатынасы антисимметриялық емес, себебі бөледі және бөледі. «Ең үлкен» және «ең төмен» тіркестерінде «ең үлкен ортақ бөлгіш» және «ең төмен ортақ еселік» сөздері осы алдын ала тәртіпке сілтеме жасайды (бірақ бүтін сандар үшін ең үлкен ортақ бөлгіш, бүтін сандардың табиғи тәртібі бойынша да ең үлкен болып табылады). Алдын ала тәртіптер эквиваленттік қатынастармен және (қатаң емес) ішінара тәртіптермен тығыз байланысты. Бұл екеуі де алдын ала тәртіптің ерекше жағдайлары: антисимметриялық алдын ала тәртіп – ішінара тәртіп, ал симметриялық алдын ала тәртіп – эквиваленттік қатынас. Сонымен қатар, жиынның алдын ала тәртібін, эквиваленттік сыныптар жиынындағы ішінара тәртіппен бірге, эквиваленттік қатынас ретінде анықтауға болады. Ішінара тәртіптер мен эквиваленттік қатынастар сияқты, алдын ала тәртіптер (бос емес жиын үшін) ешқашан асимметриялық бола алмайды. Алдын ала тәртіпті бағытталған граф ретінде бейнелеуге болады, онда жиынның элементтері графтың төбелеріне сәйкес келеді, ал элементтер жұбы арасындағы тәртіп қатынасы графтың төбелері арасындағы бағытталған қабырғаларға сәйкес келеді. Керісінше, көптеген бағытталған графтар рефлексивті де, транзитивті де емес. Антисимметриялық алдын ала тәртіпте циклдар болмайды; ол ішінара тәртіп және бағытталған ациклді графқа сәйкес келеді. Симметриялық алдын ала тәртіп – эквиваленттік қатынас; оны графтың қабырғаларындағы бағыт белгілерін жоғалтқан деп есептеуге болады. Жалпы, алдын ала тәртіпке сәйкес бағытталған графта көптеген ажыратылған компоненттер болуы мүмкін. Бинарлық қатынас ретінде, алдын ала тәртіптің b, a-ны жабуы немесе b, a-дан бұрын келуі немесе b, a-ға дейін кемітілуі деп айтуға болады. Кейде ← немесе → белгісі де қолданылады.

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. The name preorder is meant to suggest that preorders are almost partial orders, but not quite, as they are not necessarily antisymmetric. A natural example of a preorder is the divides relation "x divides y" between integers, polynomials, or elements of a commutative ring. For example, the divides relation is reflexive as every integer divides itself. But the divides relation is not antisymmetric, because divides and divides It is to this preorder that "greatest" and "lowest" refer in the phrases "greatest common divisor" and "lowest common multiple" (except that, for integers, the greatest common divisor is also the greatest for the natural order of the integers). Preorders are closely related to equivalence relations and (non strict) partial orders. Both of these are special cases of a preorder: an antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation. Moreover, a preorder on a set can equivalently be defined as an equivalence relation on , together with a partial order on the set of equivalence class. Like partial orders and equivalence relations, preorders (on a nonempty set) are never asymmetric. A preorder can be visualized as a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. The converse is not true: most directed graphs are neither reflexive nor transitive. A preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a directed acyclic graph. A preorder that is symmetric is an equivalence relation; it can be thought of as having lost the direction markers on the edges of the graph. In general, a preorder's corresponding directed graph may have many disconnected components. As a binary relation, a preorder may be denoted or In words, when one may say that b covers a or that a precedes b, or that b reduces to a. Occasionally, the notation ← or → is also used.

Граф теориясы

Кез келген бағытталған графиктегі (мүмкін циклдерді қамтитын) қолжетімділік қатынасы алдын ала тәртіпке әкеледі, онда x, y алдын ала тәртіпте орналасқан, егер және тек егер бағытталған графикте x-тен y-ге дейін жол болса. Керісінше, кез келген алдын ала тәртіп – бағытталған графиктің қолжетімділік қатынасы болып табылады (мысалы, әрбір (x, y) жұбы үшін x-тен y-ге жиегі бар график). Дегенмен, көптеген әртүрлі графиктерде бірдей қолжетімділік алдын ала тәртібі болуы мүмкін. Сол сияқты, бағытталған ациклді графиктердің, яғни циклдары жоқ бағытталған графиктердің қолжетімділігі ішінара реттелген жиынтықтарды тудырады (қосымша антисимметрия қасиетін қанағаттандыратын алдын ала тәртіптер). Графтың кіші графигіне қатысты қатынас та алдын ала тәртіп болып табылады.

Компьютерлік ғылым

Компьютерлік ғылымда келесі алдын ала реттіліктердің мысалдарын кездестіруге болады. Асимптотикалық рет функциялар арасында алдын ала реттілік тудырады. Оған сәйкес келетін эквиваленттік қатынас асимптотикалық эквиваленттік деп аталады. Полиномиялық уақыт, көп-бірлік (бейнелеу) және Тьюринг азайтулары күрделілік сыныптарында алдын ала реттіліктер болып табылады. Подтиптер арасындағы қатынастар көбінесе алдын ала реттіліктер болып келеді. Симуляциялық алдын ала реттіліктер алдын ала реттіліктер болып табылады (сондықтан осылай аталады). Абстрактілі қайта жазу жүйелеріндегі азайту қатынастары. Егер t терминінің ішкі терми s терминінің орнына қойылған түрі болса, терминдер жиынындағы қоршау реті анықталады. Тета-көмектесу, яғни дизъюнктивті бірінші реттік формуланың литералдары, біріншісіне орнын ауыстыру қолданғаннан кейін екіншісіне кіріктірілген кезде.

Алдын ала тапсырыстардың саны

Жоғарыда түсіндірілгендей, алдын ала тапсырыстар мен (бөлу, ішінара реттелу) жұптары арасында 1:1 сәйкестік бар. Осылайша, алдын ала тапсырыстардың саны – әр бөлімдегі ішінара реттелулер санының қосындысына тең. Мысалы: