0005 Bounds
Let $(X,\preceq)$ be a poset and $A\subseteq X$ a nonempty set, and $\alpha\in X$.
If $\forall b\in A$ we have $b\preceq \alpha$ then we call $\alpha$ an upper bound of $A$.
We denote the set of all upper bounds of $A$ by $UB_A$.
If $\alpha\in A\cap UB_A$ then we call $\alpha$ the maximum of $A$ and write $\alpha=\max(A)$.
If $\alpha=\min(UB_A)$ we call $\alpha$ the supremum of $A$ and write $\alpha=\sup(A)$.
Each of these terms define a kind of upper bound for a set. Each has a dual in terms of lower bounds. The dual of the maximum is called the minimum, written $\min(A)$. The dual of the supremum is the infimum, written $\inf(A)$.
Throughout this section, assume that $(X,\preceq)$ is a poset, and $A,B\subseteq X$ are nonempty subsets, and $\alpha\in X$.
For each theorem below, stated in terms of an upper bound, there is a theorem for its dual in terms of a lower bound.
Theorem: Bound uniq. max.
If the maximum of a set exists, it is unique.
Statement and proof.
Suppose $\alpha=\max(A)$ exists. Let $\beta\in X$ be another maximum, $\beta \in A\cap UB_A$.
Then $\alpha\preceq \beta$ because $\alpha\in A$ and $\beta\in UB_A$. But also $\beta\preceq \alpha$ because $\beta\in A$ and $\alpha\in UB_A$.
Therefore by the anti-symmetry of $\preceq$, we have $\alpha=\beta$.
$\Box$
Theorem: Bound max. is sup.
If a set has a maximum then the maximum is the supremum of that set.
Statement and proof.
Statement: Let $A\subseteq X$ be a set with a maximum, $\alpha = \max(A)$. Then $\alpha=\sup(A)$.
Proof:
Theorem: Bound tot. ord. finite set max.
For a total order, every finite set has a maximum.
Statement and proof.
Statement: If $\preceq$ is total and $A$ is finite, then $\max(A)$ exists.
Proof:
Base-case: $|C|=1$.
Suppose that $C\subseteq X$ is a singleton set, and let $C=\{y\}$. Then $y\in UB_C$ by reflexivity, $y\preceq y$.
Therefore $y \in C\cap UB_C$ and so $y = \max(C)$.
Inductive case.
Let $1\le n$ and suppose that every finite set $D\subseteq X$, such that $|D|=n$, the set $D$ has a maximum. Suppose that $C\subseteq X$ is such that $|C| = n+1$.
Then let $y\in C$ and define $C' = C\smallsetminus \{y\}$. By the inductive hypothesis, since $|C'|=n$, then $\alpha = \max(C')$ exists.
If $y\preceq \alpha$ then $\alpha=\max(C)$. If $\alpha\preceq y$ then $y=\max(C)$. Therefore, in all cases, $\max(C)$ exist.
$\Box$
Theorem: Bound inf. left-eq sup.
$\inf(A)\preceq \sup(A)$
Statement and proof.
Statement: Suppose that both $\alpha=\inf(A)$ and $\beta=\sup(A)$ exist. Then
$$ \inf(A)\preceq \sup(A) $$
Proof: Let $y\in A$. Then if $\gamma\in LB_A$ and $\delta\in UB_A$, we must have
$$ \gamma\preceq y \preceq \delta $$
Since $\alpha\in LB_A$ and $\beta\in UB_A$ then we have
$$ \alpha\preceq y\preceq \beta $$
$\Box$
Theorem: Bound subset sup. ineq.
Subsets have left-eq suprema.
Statement and proof.
Statement: Let $A\subseteq B$ and suppose that $\sup(A)$ and $\sup(B)$ both exist.
Then $\sup(A)\preceq \sup(B)$.
Proof: If $y\in A$ then $y\in B$. Therefore $y\preceq\sup(B)$.
So $\sup(B) \in UB_A$. Since $\sup(A)=\min(UB_A)$ we have
$$\sup(A)\preceq\sup(B)$$
$\Box$