Orders
As a bonus today, I want to define a few more kinds of relations.
A preorder is a relation on a set which is reflexive and transitive. We often write a general preorder as 
and say that 
precedes 
or that succeeds . A set equipped with a preorder is called a preordered set. If we also have that for any two elements and there is some element 
(possibly the same as or ) that succeeds both of them we call the structure a directed set.
A partial order is a preorder which is also antisymmetric: the only way to have both and 
is for and to be the same element. We call a set with a partial order a partially-ordered set or a “poset”.
Any set gives a partial order on its set of subsets, given by inclusion: if 
and 
are subsets of a set 
, then precedes if is contained in . This has the further nice property that it has a top element, itself, that succeeds every element. It also has a bottom element, the empty subset, that precedes everything. The same sort of construction applies to give the poset of subgroups of any given group. These kinds of partially-ordered sets are very important in logic and set theory, and they’ll come up in more detail later.
Finally, a partial order where for any two elements and we either have or is called a total order. Total orders show up over and over, and they’re nice things to have around. I must admit, though, that as far as I’m concerned they’re pretty boring in and of themselves.
March 11, 2007 -
Posted by John Armstrong |
Fundamentals, Orders
The Unapologetic Mathematician 
[…] A well-ordering on a set is a special kind of total order: one in which every non-empty subset contains a least […]
Pingback by Well-Ordering « The Unapologetic Mathematician | April 2, 2007 |
[…] Lower Bounds and Euclid’s Algorithm One interesting question for any partial order is that of lower or upper bounds. Given a partial order and a subset we say that is a lower […]
Pingback by Greatest Lower Bounds and Euclid's Algorithm « The Unapologetic Mathematician | May 4, 2007 |
[…] A poset which has both least upper bounds and greatest lower bounds is called a lattice. In more detail, […]
Pingback by Lattices « The Unapologetic Mathematician | May 14, 2007 |
[…] containment from to those collections of subsets of which are actually topologies, it defines a partial order on the collection of all topologies on […]
Pingback by Topology « The Unapologetic Mathematician | November 5, 2007 |
[…] numbers for sequences is that they’re “directed”. That is, there’s an order on them. It’s a particularly simple order since it’s total — any two elements are […]
Pingback by Nets, Part I « The Unapologetic Mathematician | November 19, 2007 |
[…] let’s consider the collection of all subspaces of . This is a partially-ordered set, where the order is given by containment of the underlying sets. It’s sort of like the power […]
Pingback by The Sum of Subspaces « The Unapologetic Mathematician | July 21, 2008 |
[…] Complements and the Lattice of Subspaces We know that the poset of subspaces of a vector space is a lattice. Now we can define complementary subspaces in a way […]
Pingback by Orthogonal Complements and the Lattice of Subspaces « The Unapologetic Mathematician | May 7, 2009 |
[…] we want to introduce a partial order on the collection of partitions called the “dominance order”. Given partitions and , […]
Pingback by The Dominance Order on Partitions « The Unapologetic Mathematician | December 17, 2010 |
What does the antisymmetry axiom gain / lose you?
Antisymmetry makes it so that if two elements satisfy
and 
then we actually have 
. This makes life simpler in some situations.
As a more visual example, imagine the preorder as a graph, with an arrow from
to 
if 
(pointing “up” the order). Then the graph of a preorder can have nontrivial loops, with an arrow from 
to 
and another one back. The graph of a partial order will be acyclic; partial orders are “simpler” than preorders in the same way acyclic graphs are simpler than general graphs.
Thanks!