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
  1. If $x,y,z\in S$ and $x\le y$ and $y\le z$ then $x\le z$, and
  2. 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
  3. 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\text{if}x\le y\text{and}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 $\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)$.
• A least upper bound of $E$ is an element $\sup \left(E\right)\in S$ such that
  1. $\sup \left(E\right)$ is a upper bound of $E$, and
  2. if $b\in S$ is a upper bound of $E$ then $\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|a\le x\le b\}& \phantom{\mathrm{SPACE}}& (a,b)=\{x\in S|a<x<b\}\\ [a,b)=\{x\in S|a\le x<b\}& \phantom{\mathrm{SPACE}}& (a,b]=\{x\in S|a<x\le b\}\\ (-\infty ,b]=\{x\in S|x\le b\}& \phantom{\mathrm{SPACE}}& [a,\infty )=\{x\in S|a\le x\}\\ (-\infty ,b)=\{x\in S|x<b\}& \phantom{\mathrm{SPACE}}& (a,\infty )=\{x\in S|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\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 $𝒯=\left\{\text{unions of open intervals}\right\}$ is not a topology.

Notes and References

The orders on the number systems $\mathbb{Z},\mathbb{Q},ℝ$ are indispensible for ordinary daily measurements. Perhaps surprisingly, there is no partial order on $ℂ$ which makes $ℂ$ 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, Springer-Verlag, 1970 MR??????

[St] R. Stanley, Enumerative combinatorics I, Chapter 3, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, 1997. MR??????

page history