2.3 Ordering & Bounding

2.3.1 Orders

Definition 2.10.

A partially ordered set is an ordered pair $(X,\leq)$ , where $X$ is a set and $\leq$ is a binary relation which forms a partial order on $X$ . For any two elements $x,y\in X$ we have either $x\leq y$ , or $x\not{\leq}y$ .

Example 2.1.

Let $S$ be a set, then let $P(S)$ be the set of subsets of $S$ . Then $(P(S),\subseteq)$ is a partially ordered set. For any two elements $A,B\in P(S)$ we have either $A\subseteq B$ or $A\not{\subseteq}B$ .

Definition 2.11.

A totally ordered set is an ordered pair $(X,\leq)$ , where $X$ is a set and $\leq$ is a binary relation which forms a total order on $X$ . So for any two elements $x,y\in X$ we have $x\leq y$ , or $y\leq x$ , or both (never neither)²² 2 This is known as the trichotomy law. It is possible for a subset of a partially ordered set to be totally ordered (under the same relation).

Example 2.2.

$(\mathbb{N},\leq)$ — the set of natural numbers with the greater than or equal to relation — forms a totally ordered set. For any $m,n\in\mathbb{N}$ we have $m\leq n$ , or $n\leq m$ , or both ( $m=n$ ). Any subset of $\mathbb{N}$ is also totally ordered under $\leq$ .

The key difference between partial orders and total orders is that partial orders are only useful for comparing some elements with each other whereas total orders can compare all elements with each other.

2.3.2 Bounds

There are several different ways we can create definitions for different kinds of ‘extreme’ elements in a set, all with subtle differences between them. We will go through some of these now.

Definition 2.12.

Let $(P,\leq)$ be a partially ordered set and let $S\subseteq P$ .

•

An element $g\in S$ is the greatest element of $S$ if $\forall s\in S,\,s\leq g$ . If a greatest element exists, clearly it is unique (due to the trichotomy law). In other words, a greatest element is an element that is greater than all other elements. However, note that greatest elements may not necessarily exist.
•

An element $m\in S$ is a maximal element of $S$ if there does not exist any $s\in S$ with $(s\neq m)$ such that $m\leq s$ . A set may have multiple maximal elements, and they may exist without there being a greatest element. Maximal elements also may not necessarily exist. In simple terms, a maximal element is one that is not smaller than any other element. Notice how this definition is subtly different to the definition of the greatest element.
•

An element $u\in P$ is an upper bound for $S$ in $P$ $\iff\forall s\in S,\,s\leq u$ . Note that if $P=S$ , then the definition of a greatest element of $S$ becomes equivalent to the definition of an upper bound of $S$ in $S$ , therefore an element $g\in S$ is the greatest element of $S$ if and only if $g$ is an upper bound for $S$ and $g\in S$ . It is also plausible that $S$ may not have a greatest element while also having an upper bound in $P$ (that’s a tricky one to get your head around).
•

Let $T$ be a totally ordered subset of $P$ . Then the greatest element of $T$ and the maximal element of $T$ are the same, in which case this element is called the maximum of $T$ .
•

Let $U(S)\subseteq P$ be the set of all upper bounds for $S$ in $P$ . Then $l\in U(S)$ is the supremum (or least upper bound) of $S$ if $\forall u\in U(S),\,l\leq u$ . Basically the supremum of $S$ is the least element of $U(S)$ . Thus if suprema exist, they are unique. If a greatest element or maximum exists, then it is the supremum, and this is the only case where the supremum of a set will lie in the set itself.
•

If we switch the elements around the $\leq$ sign in all the above definitions, we obtain the definitions for the dual notions of all those just defined: the least element, minimal element, lower bound, minimum, and infimum (or greatest lower bound).