The Unapologetic Mathematician

Yarn Theory

Yeah, it’s a rerun, but this Doonesbury is a classic. It feels very much like going into academics. Yeah, I’m looking forward to the ten-year high school reunion this fall…

March 11, 2007 Posted by | Uncategorized | Leave a comment

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 $x\preceq y$ and say that $x$ precedes $y$ or that $y$ succeeds $x$. A set equipped with a preorder is called a preordered set. If we also have that for any two elements $x$ and $y$ there is some element $z$ (possibly the same as $x$ or $y$) 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 $x\preceq y$ and $y\preceq x$ is for $x$ and $y$ 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 $A$ and $B$ are subsets of a set $X$, then $A$ precedes $B$ if $A$ is contained in $B$. This has the further nice property that it has a top element, $X$ 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 $x$ and $y$ we either have $x\preceq y$ or $y\preceq x$ 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 | Fundamentals, Orders | 8 Comments