# The Unapologetic Mathematician

## 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.

### Like this:

Posted by John Armstrong | Fundamentals, Orders

## 8 Comments	»

1. [...] 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 | April 2, 2007 | Reply

2. [...] 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 | May 4, 2007 | Reply

3. [...] A poset which has both least upper bounds and greatest lower bounds is called a lattice. In more detail, [...]

Pingback by | May 14, 2007 | Reply

4. [...] 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 | November 5, 2007 | Reply

5. [...] 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 | November 19, 2007 | Reply

6. [...] 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 | July 21, 2008 | Reply

7. [...] 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 | May 7, 2009 | Reply

8. [...] we want to introduce a partial order on the collection of partitions called the “dominance order”. Given partitions and , [...]

Pingback by | December 17, 2010 | Reply

« Previous | Next »

## About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 26, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9462995529174805, "perplexity_flag": "head"}