Введение

Рефлексивное и транзитивное бинарное отношение
бинарные отношения

В математике, особенно в теории порядка, предзаказ или квазипорядок — это бинарное отношение, которое является рефлексивным и транзитивным. Название «предзаказ» подразумевает, что предзаказы почти являются частичными порядками, но не совсем, поскольку они не обязательно антисимметричны. Естественным примером предзаказа является отношение «x делит y» между целыми числами, многочленами или элементами коммутативного кольца. Например, отношение деления является рефлексивным, поскольку каждое целое число делится само на себя. Но отношение деления не антисимметрично, потому что x делит y и y делит x. Именно к этому предзаказу относятся понятия «наибольший» и «наименьший» в выражениях «наибольший общий делитель» и «наименьшее общее кратное» (за исключением того, что для целых чисел наибольший общий делитель также является наибольшим в естественном порядке целых чисел). Предзаказы тесно связаны с отношениями эквивалентности и (нестрогими) частичными порядками. Оба этих случая являются частными случаями предзаказа: антисимметричный предзаказ является частичным порядком, а симметричный предзаказ является отношением эквивалентности. Более того, предзаказ на множестве M может быть эквивалентно определен как отношение эквивалентности на M, вместе с частичным порядком на множестве классов эквивалентности. Как и частичные порядки и отношения эквивалентности, предзаказы (на непустом множестве) никогда не бывают асимметричными. Предзаказ можно визуализировать как ориентированный граф, где элементам множества соответствуют вершины, а отношению порядка между парами элементов соответствуют ориентированные ребра между вершинами. Обратное неверно: большинство ориентированных графов не являются ни рефлексивными, ни транзитивными. Предзаказ, который является антисимметричным, больше не имеет циклов; это частичный порядок и соответствует ориентированному ациклическому графу. Предзаказ, который является симметричным, является отношением эквивалентности; его можно рассматривать как потерявший указатели направления на ребрах графа. В общем случае, соответствующий ориентированный граф предзаказа может иметь множество несвязных компонент. Как бинарное отношение, предзаказ может быть обозначен ≤ или ≼. В терминах, когда b ≤ a, можно сказать, что b покрывает a, или что a предшествует b, или что b сводится к a. Иногда также используется обозначение ← или →.

Теория графов

Отношение достижимости в любом ориентированном графе (возможно, содержащем циклы) порождает предзаказ, где x предшествует y в предзаказе тогда и только тогда, когда в ориентированном графе существует путь из x в y. Обратно, любой предзаказ является отношением достижимости ориентированного графа (например, графа, имеющего ребро из x в y для каждой пары (x, y) с ). Однако многие различные графы могут иметь один и тот же предзаказ достижимости. Аналогично, достижимость в ориентированных ациклических графах, то есть ориентированных графах без циклов, порождает частично упорядоченные множества (предзаказы, удовлетворяющие дополнительному свойству антисимметричности). Отношение миноров графов также является предзаказом.

Информатика

В информатике можно найти примеры следующих предзаказов. Асимптотический порядок порождает предзаказ над функциями. Соответствующее отношение эквивалентности называется асимптотической эквивалентностью. Полиномиальное время, многие-к-одному (отображение) и редукции Тьюринга являются предзаказами на классах сложности. Отношения подтипирования обычно являются предзаказами. Предзаказы симуляции – это предзаказы (отсюда и название). Отношения редукции в абстрактных системах переписывания. Предзаказ включения на множестве термов, определяемый условием, что если подтерм t является результатом подстановки s. Тета-субсумпция, которая возникает, когда литералы в дизъюнктивной формуле первого порядка содержатся в другой формуле после применения подстановки к первой.

Количество предварительных заказов

Как объяснено выше, существует взаимно однозначное соответствие между предзаказами и парами (разбиение, частичный порядок). Следовательно, количество предзаказов равно сумме количества частичных порядков для каждого разбиения. Например: