Ordered sets
Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au
Last updates: 07 January 2012
Ordered sets
Let $S$ be a set.

A partial order on $S$
is a relation $\le $ on $S$
such that

If $x,y,z\in S$
and $x\le y$ and
$y\le z$ then
$x\le z$, and

If $x,y\in S$
and $x\le y$ and $y\le x$ then $x=y$.
Stanley adds the axiom: if $x\in S$ then
$x\le x$. Bourbaki adds the axiom:
if $x,y\in S$ and
$x\le y$ then
$x\le x$ and $y\le y$. Bourbaki defines a preorder to be the same excpet without the axiom (b).

Let $S$ be a set. A total order on $S$ is a partial order $\le $ such that

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

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

A totally ordered set is a set
$S$ with a total order $\le $
on $S$.
Let $S$ be a poset and let $x,y\in S$. Write
$$x<y\phantom{\rule{2em}{0ex}}\text{if}\phantom{\rule{2em}{0ex}}x\le y\phantom{\rule{0.5em}{0ex}}\text{and}\phantom{\rule{0.5em}{0ex}}x\ne y.$$
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$.

A lower bound of $E$
is an element $l\in S$ such that if
$y\in E$ then
$l\le y$.

A greatest lower bound of
$E$ is an element $\mathrm{inf}\left(E\right)\in S$ such that
 $\mathrm{inf}\left(E\right)$ is a lower bound of $E$, and
 if $l\in S$ is a lower bound of $E$ then $l\le \mathrm{inf}\left(E\right)$.

A least upper bound of
$E$ is an element $\mathrm{sup}\left(E\right)\in S$ such that
 $\mathrm{sup}\left(E\right)$ is a upper bound of $E$, and
 if $b\in S$ is a upper bound of $E$ then $\mathrm{sup}\left(E\right)\le b$.
 The set $E$ is bounded if
$E$ has both and upper bound and a lower bound in
$S$.
 A minimal element of $E$ is an element
$x\in E$ such that if
$y\in E$ and
$y\le x$ then
$y=x$.
 A maximal element of $E$ is an element
$z\in E$ such that if
$y\in E$ and
$y\ge z$ then
$y=z$.
 A smallest element of $E$ is an element
$a\in E$ such that if $x\in E$ then $a\le x$.
 A largest element of $E$ is an element
$a\in E$ such that if $x\in E$ then $x\le a$.
HW: Show that if $S$ is a poset and $E$ is a
subset of $S$ and a greatest lower bound of $E$
exists then it is unique.
HW: True or false: If $S$ is a poset and $E$ is
a subset of $S$ then a greatest lower bound of $E$
exists.
HW: True or false: If $S$ is a poset and $E$ is
a subset of $S$ and a minimal element of $E$ exists
then it is unique.
HW: True or false: If $S$ is a poset and $E$ is
a subset of $S$ then a minimal element of $E$
exists.
HW: True or false: If $S$ is a poset and $E$ is
a subset of $S$ then a largest element of $E$ exists.
HW: True or false: If $S$ is a poset and $E$ is
a subset of $S$ and a largest element of $E$ exists
then it is unique.
HASSE DIAGRAM NEEDS TO GO IN HERE SOMEWHERE
Let $S$ be a poset.

The poset $S$ is left filtered if $S$ satisfies:
if $x,y\in S$ then
$\{x,y\}$ has a lower bound in
$S$.

The poset $S$ is right filtered if $S$ satisfies:
if $x,y\in S$ then
$\{x,y\}$ has a upper bound in
$S$.

The poset $S$ is a lattice if $S$ satisfies:
if $x,y\in S$ then
$\{x,y\}$ has a greatest lower bound and a least upper bound in $S$.

A poset $S$ is well ordered if $S$
satisfies: every nonempty subset
$E$ of $S$ has a smallest element.
HW: Show that if $S$ is a right filtered poset
and $a$ is a maximal element of $S$ then
$a$ is the largest element of $S$.
HW: Show that every well ordered set is totally ordered.
HW: Show that there exists totally ordered sets that are not well ordered.
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$.

The intervals in $S$ are the sets
$$\begin{array}{lll}[a,b]=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}a\le x\le b\}& \phantom{\mathrm{SPACE}}& (a,b)=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}a<x<b\}\\ [a,b)=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}a\le x<b\}& \phantom{\mathrm{SPACE}}& (a,b]=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}a<x\le b\}\\ (\infty ,b]=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}x\le b\}& \phantom{\mathrm{SPACE}}& [a,\infty )=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}a\le x\}\\ (\infty ,b)=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}x<b\}& \phantom{\mathrm{SPACE}}& (a,\infty )=\{x\in S\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}a<x\}\\ \end{array}$$
for $a,b\in S$.

The
sets $[a,b]$
for $a,b\in S$ are
closed intervals and the
sets $(a,b)$
for $a,b\in S$ are
open intervals.
Let $X$ be a totally ordered set. An open set
is a subset $E\subseteq X$ such that
$$E\phantom{\rule{0.5em}{0ex}}\text{is a union of open intervals.}$$
IS THIS DEFINING A TOPOLOGY OR NOT? SHOULD THIS REALLY BE HERE, OR IN THE EXERCISES?
OR IN TOPOLOGIES?
HW: Show that if $S$ is a lattice then the intersection of
two intervals is an interval.
HW: Give an example of a poset $X$ such that the collection
$\mathcal{T}=\left\{\text{unions of open intervals}\right\}$
is not a topology.
Notes and References
The orders on the number systems $\mathbb{Z},\mathbb{Q},\mathbb{R}$ are indispensible for ordinary daily measurements.
Perhaps surprisingly, there is no partial order on $\u2102$
which makes $\u2102$ an ordered field. A frequently
used partial order which is not a total order is inclusion of sets.
The definitions of left filtered and right filtered are
used in the theory of inverse and direct limits. The definitions and examples
of upper and lower bounds, suprema and infima, maxima and minima, and largest
and smallest element, are a natural way to introduce students to analyses and
proofs of existence and uniqueness.
Fundamental definitions and properties of partially ordered are treated thoroughly
in [Bou, Ens Ch. III]. The exposition of Stanley [St, Ch. 3] has an inspiring modern point of view and a wealth of information on the important subject of posets.
References
[Bou]
N. Bourbaki, Théorie des Ensembles, Chapter III,
Masson, SpringerVerlag, 1970
MR??????
[St]
R. Stanley, Enumerative combinatorics I, Chapter 3,
Cambridge Studies in Advanced Mathematics 49,
Cambridge University Press, 1997.
MR??????
page history