|
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. All equivalence relations and (non-strict) partial orders are preorders, but preorders are more general. The name 'preorder' comes from the idea that preorders (that are not partial orders) are 'almost' (partial) orders, but not quite; they're neither necessarily anti-symmetric nor symmetric. Because a preorder is a binary relation, the symbol ≤ can be used as the notational device for the relation. However, because they are not necessarily anti-symmetric, some of the ordinary intuition associated to the symbol ≤ may not apply. On the other hand, a preorder can be used, in a straightforward fashion, to define a partial order and an equivalence relation. Doing so, however, is not always useful or worthwhile, depending on the problem domain being studied. In words, when ''a'' ≤ ''b'', one may say that ''b'' ''covers'' ''a'' or that ''a'' ''precedes'' ''b'', or that ''b'' ''reduces'' to ''a''. Occasionally, the notation ← or is used instead of ≤. To every preorder, there corresponds 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. In general, the corresponding graphs may contain cycles. 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 may have many disconnected components. ==Formal definition== Consider some set ''P'' and a binary relation ≤ on ''P''. Then ≤ is a preorder, or quasiorder, if it is reflexive and transitive, i.e., for all ''a'', ''b'' and ''c'' in ''P'', we have that: :''a'' ≤ ''a'' (reflexivity) : if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity) A set that is equipped with a preorder is called a preordered set (or proset).〔For "proset", see e.g. .〕 If a preorder is also antisymmetric, that is, ''a'' ≤ ''b'' and ''b'' ≤ ''a'' implies ''a'' = ''b'', then it is a partial order. On the other hand, if it is symmetric, that is, if ''a'' ≤ ''b'' implies ''b'' ≤ ''a'', then it is an equivalence relation. Equivalently, the notion of a preordered set ''P'' can be formulated in a categorical framework as a thin category, i.e. as a category with at most one morphism from an object to another. Here the objects correspond to the elements of ''P'', and there is one morphism for objects which are related, zero otherwise. Alternately, a preordered set can be understood as an enriched category, enriched over the category 2 = (0→1). A preordered class is a class equipped with a preorder. Every set is a class and so every preordered set is a preordered class. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「preorder」の詳細全文を読む スポンサード リンク
|