Ordered Sets

Arun Ram
Department of Mathematics
University of Wisconsin, Madison
Madison, WI 53706 USA
ram@math.wisc.edu

and

Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last updates: 15 October 2009

Ordered Sets

Let $S$ be a set. A partial order on $S$ is a relation $\le$ on $S$ such that both of the following conditions are satisfied.

1. If $x,y,z\in S$ and $x\le y$ and $y\le z$ then $x\le z$.
2. If $x,y\in S$ and $x\le y$ and $y\le x$ then $x=y$.

Let $S$ be a set. A total order on $S$ is a partial order $\le$ on $S$ which also satisfies the following condition.

3. If $x,y\in S$ then either $x\le y$ or $y\le x$.

A partially ordered set or poset is a set $S$ with a partial order $\le$ on $S$.

Let $S$ be a poset. A lower order ideal of $S$ is a subset $E$ of $S$ such that if $y\in E$, $x\in S$ and $x\le y$ then $x\in E$.

Let $S$ be a poset and let $E$ be a subset of $S$. An upper bound of $E$ is an element $b\in S$ such that if $y\in E$ then $y\le b$.

Let $S$ be a poset and let $E$ be a subset of $S$. A lower bound of $E$ is an element $l\in S$ such that if $y\in E$ then $l\le y$.

Let $S$ be a poset and let $E$ be a subset of $S$. The [THE? EXISTENCE/UNIQUENESS IS NOT GUARANTEED] greatest lower bound of $E$ is the element $\inf \left(E\right)\in S$ such that

1. $\inf \left(E\right)$ is a lower bound of $E$, and
2. if $l\in S$ is a lower bound of $E$ then $l\le \inf \left(E\right)$.

Let $S$ be a poset and let $E$ be a subset of $S$. The [THE? EXISTENCE/UNIQUENESS IS NOT GUARANTEED] least upper bound of $E$ is the element $\sup \left(E\right)\in S$ such that

1. $\sup \left(E\right)$ is an upper bound of $E$, and
2. if $b\in S$ is a lower bound of $E$ then $\sup \left(E\right)\le b$.

A lattice is a poset $S$ such that every set containing a pair of elements $\left\{x,y\right\}\subseteq S$ has a greatest lower bound and a least upper bound.

Let $S$ be a poset. The intervals in $S$ are the sets $$\begin{array}{rcl}\left[a,b\right]& =& \left\{x\in S|a\le x\le b\right\}\\ \left[a,b\right)& =& \left\{x\in S|a\le x<b\right\}\\ \left(a,b\right]& =& \left\{x\in S|a<x\le b\right\}\\ \left(a,b\right)& =& \left\{x\in S|a<x<b\right\}\\ \left[a,\infty \right)& =& \left\{x\in S|a\le x\right\}\\ \left(a,\infty \right)& =& \left\{x\in S|a<x\right\}\\ \left(-\infty ,b\right]& =& \left\{x\in S|x\le b\right\}\\ \left(-\infty ,b\right)& =& \left\{x\in S|x<b\right\}\end{array}$$ for $a,b\in S$. The sets $\left[a,b\right]$, $a,b\in S$ are closed intervals and the sets $\left(a,b\right)$, $a,b\in S$ are open intervals.

Exercises

	Show that if a greatest lower bound exists, then it is unique.
	Show that if $S$ is a lattice then the intersection of two intervals is an interval.
	A poset $S$ is left filtered if every subset $E$ of $S$ has an upper bound. A poset $S$ is right filtered if every subset $E$ of $S$ has an lower bound. Let $S$ be a poset and let $E$ be a subset of $S$. A minimal element of $E$ is an element $x\in E$ such that if $y\in E$ then $x\le y$. A poset $S$ is well ordered if every subset $E$ of $S$ has a minimal element. Show that every well ordered set is totally ordered.
	Show that there exist totally ordered sets that are not well ordered.

References [PLACEHOLDER]

[BG] A. Braverman and D. Gaitsgory, Crystals via the affine Grassmanian, Duke Math. J. 107 no. 3, (2001), 561-575; arXiv:math/9909077v2, MR1828302 (2002e:20083)