| Preorder |
Articles about Preorder |
Information AboutPreorder |
| CATEGORIES ABOUT PREORDER | |
| order theory | |
|
In Mathematics , especially in Order Theory , preorders are certain kinds of Binary Relation s that are closely related to Partially Ordered Set s. The name '''quasiorder''' is also a common expression for preorders. Many order theoretical definitions for partially ordered sets can be generalized to preorders, but the extra effort of generalization is rarely needed. 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 : if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity) A set that is equipped with a preorder is called a preordered set. If a preorder is also Antisymmetric , that is, ''a'' ≤ ''b'' and ''b'' ≤ ''a'' implies ''a'' = ''b'', then it is a Partial Order . A partial order on a set ''T'' can be constructed from any preorder on set ''S'' by associating members of ''T'' with "equivalent" members of ''S''. Formally, one defines an Equivalence Relation ~ over ''S'' such that ''a'' ~ ''b'' Iff ''a'' ≤ ''b'' and ''b'' ≤ ''a''. Now let ''T'' be the quotient set ''S'' / ~, i.e., the set of all Equivalence Class es of ~. ''T'' can easily be ordered by defining ≤ [''y'' iff ''x'' ≤ ''y''. By the construction of ~ this definition is independent from the chosen representatives and the corresponding relation is indeed Well-defined . It is readily verified that this yields a partially ordered set. EXAMPLES OF PREORDERS
SEE ALSO
|
|
|