Order relation
From AoPSWiki
An order relation (or a partial order relation) on a set 
is a binary relation 
on which satisfies the following axioms:
- For all
, 
. (Reflexivity)
- For all
, if 
and 
, then 
. (Anti-symmetry)
- For all
, if and 
, then 
. (Transitivity)
We use 
to denote 
.
One example of an ordering is the relation on the natural numbers.
A set with a partial order relation on is also called a partially ordered set (or poset). Note that it under some partial orderings, there can exist elements 
in , such that 
, 
, and 
. For instance, we could define to mean , in which case we can only write or 
if . For a more substantial example, we can let be the power set of another set 
, and define to mean "
is a subset of 
." In this case, and are not related in either direction in many cases (e.g., when and are disjoint).
We say that a partial order on a set which also satisfies the axiom
- For all , or
(Comparability, or trichotomy)
is a total order. For instance, our first example, the relation on the natural numbers, is a total order. A set with a total order is called a totally ordered set.
See Also
This article is a stub. Help us out by expanding it.
