- Virtual Laboratories
- 0. Foundations
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9

A relation $$ on $S$ that is reflexive, anti-symmetric, and transitive is said to be a partial order on $S$. As the name and notation suggest, a partial order is a type of ordering of the elements of $S$. Partial orders occur naturally in many areas of mathematics, including probability.

A partial order $$ on a set $S$ naturally gives rise to several other relations on $S$: $$, $$, $$, $$, and $$:

- $(x, y)$ if and only if $(y, x)$, so $$ is the inverse of $$.
- $(x, y)$ if and only if $(x, y)$ and $x\neq y$.
- $(x, y)$ if and only if $(y, x)$, so $$ is the inverse of $$.
- $(x, y)$ if and only if $(x, y)$ or $(y, x)$ so that $x$ and $y$ are related in the partial order.
- $(x, y)$ if and only if $\neg (x, y)$ so $x$ and $y$ are unrelated in the partial order. Note that $$ is the complement of $$, as sets of ordered pairs.

Show that the inverse of a partial order is also a partial order.

Show that if $$ is a partial order on $S$ and $A$ is a subset of $S$, then the restriction of $$ to $A$ is a partial order on $A$.

A partial order $$ on $S$ is a total order or linear order if it satisfies the additional property that for every $x\in S$ and $y\in S$, either $(x, y)$ or $(y, x)$. Of course, the ordinary order $$ is a total order on the set of real numbers $\mathbb{R}$.

Suppose that $S$ is a set. Show that the subset relation $$ is a partial order on $(S)$, the power set of $S$.

The following exercise characterizes relations that correspond to strict order.

Let $S$ be a set. Show that $$ is a partial order on $S$ if and only if $$ is transitive and irreflexive.

Suppose that $_{1}$ and $_{2}$ are partial orders on a nonempty set $S$. Then $_{1}$ is an sub-order of $_{2}$, or equivalently $_{2}$ is an extension of $_{1}$ if and only if

$$_{1}(x, y)\implies _{2}(x, y)$$Thus, as sets of ordered pairs, $_{1}$ is a subset of $_{2}$.

Let $$ denote the division relation on the set of positive integers $$. That is, $m | n$ if and only if there exists $k\in $ such that $n=km$. Show that $$ is a partial order on $$, and $$ is a sub-order of the ordinary order $$.

Suppose that $$ is a partial order on a set $S$. For $x\in S$ and $y\in S$, $y$ is said to cover $x$ if $(x, y)$ but no element $z\in S$ satisfies $(x, z, y)$. If $S$ is finite, the covering relation completely determines the partial order. Moreover, the covering graph or Hasse graph is the directed graph with vertes set $S$ and directed edge set $E$, where $\left(\begin{array}{c}x\\ y\end{array}\right)\in E$ if and only if $y$ covers $x$. Thus, $(x, y)$ if and only if there is a directed path in the graph from $x$ to $y$. Hasse graphs are named for the German mathematician Helmut Hasse. The graphs are often drawn with the edges directed upward. In this way, the directions can be inferred without having to actually draw arrows.

Let $S=\{2, 3, 4, 6, 12\}$.

- Sketch the Hasse graph corresponding to the ordinary order $$ on $S$.
- Sketch the Hasse graph corresponding to the division partial order $$ on $S$.

Suppose that $S$ and $T$ are sets with partial orders $_{S}$ and $_{T}$ respectively. Define the relation $$ on $S\times T$ by $(\left(\begin{array}{c}x\\ y\end{array}\right), \left(\begin{array}{c}z\\ w\end{array}\right))$ if and only if $_{S}(x, z)$ and $_{T}(y, w)$

- Show that $$ is a partial order on $S\times T$, called, appropriately enough, the product order.
- Suppose that $\left(\begin{array}{c}S\\ _{S}\end{array}\right)=\left(\begin{array}{c}T\\ _{T}\end{array}\right)$. Show that if $S$ has at least 2 elements, then $$ is not a total order on $S^{2}$.

The picture below shows a point $\left(\begin{array}{c}x\\ y\end{array}\right)\in \mathbb{R}^{2}$. Suppose that $\mathbb{R}^{2}$ is given the product order associated with the ordinary order $$ on $\mathbb{R}$. Then the region shaded red is the set of points larger than $\left(\begin{array}{c}x\\ y\end{array}\right)$ The region shaded blue is the set of points smaller than $\left(\begin{array}{c}x\\ y\end{array}\right)$. The region shaded white is the set of points that are not comparable with $\left(\begin{array}{c}x\\ y\end{array}\right)$.

Suppose again that $S$ and $T$ are sets with partial orders $_{S}$ and $_{T}$ respectively. Define the relation $$ on $S\times T$ by $(\left(\begin{array}{c}x\\ y\end{array}\right), \left(\begin{array}{c}z\\ w\end{array}\right))$ if and only if either $_{S}(x, z)$, or $x=z$ and $_{T}(y, w)$

- Show that $$ is a partial order on $S\times T$, called the lexicographic order or dictionary order.
- Show that if $_{S}$ and $_{T}$ are total orders on $S$ and $T$, respectively, then $$ is a total order on $S\times T$.

The picture below shows a point $\left(\begin{array}{c}x\\ y\end{array}\right)\in \mathbb{R}^{2}$. Suppose that $\mathbb{R}^{2}$ is given the lexicographic order associated with the ordinary order $$ on $\mathbb{R}$. Then the region shaded red is the set of points larger than $\left(\begin{array}{c}x\\ y\end{array}\right)$ The region shaded blue is the set of points smaller than $\left(\begin{array}{c}x\\ y\end{array}\right)$.

Lexicographic orders are not as obscure as you might think. Many standard partially ordered sets can be expressed as lexicographic products.

A real number $x\in \mathbb{R}$ can be uniquely expressed in terms of its integer part and remainder:

$$x=n+t$$where $n=\lfloor x\rfloor $ and $t=x-n=x-\lfloor x\rfloor $. In this way, $\mathbb{R}$ can be associated with the product space $\mathbb{Z}\times \left[0 , 1\right)$. Show that $\left(\begin{array}{c}\mathbb{R}\\ \end{array}\right)$ corresponds to the lexicographic product of $\left(\begin{array}{c}\mathbb{Z}\\ \end{array}\right)$ with $\left(\begin{array}{c}\left[0 , 1\right)\\ \end{array}\right)$, where of course $$ is the ordinary order for real numbers.

Partial orders form a natural setting for increasing and decreasing sets and functions. Suppose first that $$ is a partial order on a set $S$ and that $A\subseteq S$. Then

- $A$ is increasing if $x\in A$ and $(x, y)$ imply $y\in A$
- $A$ is decreasing if $y\in A$ and $(x, y)$ imply $x\in A$

Suppose now $S$ is a set with partial order $_{S}$ and that $T$ is another set with partial order $_{T}$. Finally suppose that $(f, S, T)$. Then

- $f$ is increasing if and only if $_{S}(x, y)\implies _{T}(f(x), f(y))$
- $f$ is decreasing if and only if $_{S}(x, y)\implies _{T}(f(x), f(y))$
- $f$ is strictly increasing if and only if $_{S}(x, y)\implies _{T}(f(x), f(y))$
- $f$ is strictly decreasing if and only if $_{S}(x, y)\implies _{T}(f(x), f(y))$

Suppose that $$ is a partial order on a set $S$ and that $A\subseteq S$. Recall the definition of the indicator function $(A)$ associated with $A$. Show that

- $A$ is increasing if and only if $(A)$ is increasing.
- $A$ is decreasing if and only if $(A)$ is decreasing.

In a sense, the subset partial order is universal--every partially ordered set is isomorphic to $\left(\begin{array}{c}S\\ \end{array}\right)$ for some collection of sets $S$

Suppose that $$ is a partial order on a set $S$. For each $x\in S$, let $A(x)=\{u\in S\colon (u, x)\}$, and then let $S=\{A(x)\colon x\in S\}$, so that $S\subseteq (S)$. Show that the function $(A, S, S)$ is one-to-one (and of course onto) and satisfies

$$(x, y)\text{\hspace{0.5em}if and only if\hspace{0.5em}}A(x)\subseteq A(y)$$Suppose again that $$ is a partial order on a set $S$ and that $A\subseteq S$. Various types of extremal elements of $A$ play important roles.

- An element $a\in A$ is the minimum element of $A$ if and only if $(a, x)$ for every $x\in A$.
- An element $a\in A$ is a minimal element of $A$ if and only if no $x\in A$ satisfies $(x, a)$.
- An element $b\in A$ is the maximum element of $A$ if and only if $(b, x)$ for every $x\in A$.
- An element $b\in A$ is a maximal element of $A$ if and only if no $x\in A$ satisfies $(x, b)$.

In general, a set can have several maximal and minimal elements (or none).

Show that the minimum and maximum elements of $A$, if they exist, are unique. They are denoted $\mathrm{min}(A)$ and $\mathrm{max}(A)$, respectively.

Minimal, maximal, minimum, and maximum elements of a set must belong to that set. The following definitions relate to upper and lower bounds of a set, which do not have to belong to the set.

- An element $u\in S$ is a lower bound for $A$ if and only if $(u, x)$ for every $x\in A$.
- An element $v\in S$ is an upper bound for $A$ if and only if $(v, x)$ for every $x\in A$.
- The greatest lower bound or infimum of $A$, if it exists, is the maximum of the set of lower bounds of $A$.
- The least upper bound or supremum of $A$, if it exists, is the minimum of the set of upper bounds of $A$.

By the Exercise 10, the greatest lower bound of $A$ is unique, if it exists. It is denoted $\mathrm{glb}(A)$ or $\mathrm{inf}(A)$. Similarly, the least upper bound of $A$ is unique, if it exists, and is denoted $\mathrm{lub}(A)$ or $\mathrm{sup}(A)$.

Consider the ordinary order ≤ on the set of real numbers $\mathbb{R}$, and let $A=\left[a , b\right)$ where $a< b$. Find each of the following that exist:

- The set of minimal elements of $A$
- The set of maximal elements of $A$
- $\mathrm{min}(A)$
- $\mathrm{max}(A)$
- The set of lower bounds of $A$
- The set of upper bounds of $A$
- $\mathrm{inf}(A)$
- $\mathrm{sup}(A)$

Consider the division partial order $$ on the set of positive integers $$ and let $A$ be a non-empty subset of $$.

- Show that if $A$ is infnite then $\mathrm{sup}(A)$ does not exist. If $A$ is finite then $\mathrm{sup}(A)$ is the least common multiple of $A$, usually denoted $\mathrm{lcm}(A)$ in this context.
- Show that $\mathrm{inf}(A)$ is the greatest common divisor of $A$, usually denoted $\mathrm{gcd}(A)$ in this context.

Again consider the division partial order $$ on the set of positive integers $$ and let $A=\{2, 3, 4, 6, 12\}$. Find each of the following that exist:

- The set of minimal elements of $A$
- The set of maximal elements of $A$
- $\mathrm{min}(A)$
- $\mathrm{max}(A)$
- The set of lower bounds of $A$
- The set of upper bounds of $A$
- $\mathrm{inf}(A)$
- $\mathrm{sup}(A)$

Let $S$ be a set and consider the subset partial order $$ on $(S)$, the power set of $S$. Let $A$ be a non-empty subset of $(S)$, that is, a non-empty collection of subsets of $S$. Show that

- $\mathrm{inf}(A)=A$
- $\mathrm{sup}(A)=A$

Suppose that $S$ is a set and that $(f, S, S)$. An element $z\in S$ is said to be a fixed point of $f$ if $f(z)=z$. The following exercise explores a basic fixed point theorem for a partially ordered set. The theorem is important in the study of cardinality.

Suppose that $$ is a partial order on a set $S$ with the property that $\mathrm{sup}(A)$ exists for every $A\subseteq S$. If $f$ is an increasing function from $S$ into $S$, then $f$ has a fixed point. The following steps outline the proof:

- Let $A=\{x\in S\colon (x, f(x))\}$ and let $z=\mathrm{sup}(A)$
- If $x\in A$ then $(x, z)$ so $(x, f(x), f(z))$,
- From (b), $f(z)$ is an upper bound of $A$ so $(z, f(z))$
- But then $(f(z), f(f(z)))$ so $f(z)\in A$
- Hence $(f(z), z)$
- Finally conclude that $f(z)=z$

Suppose that $\left(\begin{array}{c}a_{1}\\ a_{2}\\ \end{array}\right)$ is a sequence of real numbers.

Show that $(a_{n}, a_{n+1}, )$ is increasing in $n$

The limit of the sequence in the last exercise is the limit inferior of the original sequence:

$$(n, , a_{n})=\lim_{n\to \infty}(a_{n}, a_{n+1}, )$$Show that $(a_{n}, a_{n+1}, )$ is decreasing in $n$

The limit of the sequence in the last exercise is the limit superior of the original sequence:

$$(n, , a_{n})=\lim_{n\to \infty}(a_{n}, a_{n+1}, )$$Note that $(n, , a_{n})\le (n, , a_{n})$ and equality holds if and only if $\lim_{n\to \infty}a_{n}$ exists (and is the common value).