1.5 Upper and lower bounds

Definition of bounds

In a partially ordered set (poset), bounds give you a way to describe elements that sit "above" or "below" an entire subset. They're the starting point for some of the most important ideas in order theory, including supremum, infimum, and completeness.

Throughout this section, let $(S, \leq)$ be a partially ordered set and let $A \subseteq S$.

Upper bounds

An upper bound of $A$ is any element $b \in S$ such that every element of $A$ is less than or equal to $b$:

$\forall x \in A,\; x \leq b$

A few things to note:

• An upper bound doesn't have to belong to $A$ itself. It just needs to be in $S$.
• Upper bounds are not necessarily unique. A subset can have many upper bounds, one, or none at all.
• Think of an upper bound as a ceiling: nothing in $A$ exceeds it.

Example: In $S = \{1, 2, 3, 4, 5\}$ with the usual $\leq$, the subset $A = \{1, 2, 3\}$ has upper bounds $3, 4,$ and $5$.

Lower bounds

A lower bound of $A$ is any element $a \in S$ such that $a$ is less than or equal to every element of $A$:

$\forall x \in A,\; a \leq x$

• Like upper bounds, lower bounds need not belong to $A$.
• Multiple lower bounds can exist for a single subset, or none at all.
• A lower bound acts as a floor: it sits at or below every element of $A$.

Example: Using the same $S$ and $A = \{3, 4, 5\}$, the lower bounds of $A$ are $1, 2,$ and $3$.

Properties of bounds

Uniqueness vs. non-uniqueness

Whether a bound is unique depends on the structure of the poset:

• If a subset has a maximum element (an element in the subset that is $\geq$ every other element in the subset), that maximum is an upper bound, but there may still be other upper bounds outside the subset.
• When multiple upper bounds exist, you can ask which one is smallest. That leads to the least upper bound (supremum). Similarly, when multiple lower bounds exist, the largest one is the greatest lower bound (infimum).
• Suprema and infima, when they exist, are always unique. This follows directly from the antisymmetry of the partial order.

Existence conditions

Bounds don't always exist. Their existence depends on the poset's structure:

• A subset $A$ is called bounded above if it has at least one upper bound, and bounded below if it has at least one lower bound. A subset that is both is called bounded.
• In a complete lattice, every subset (including infinite ones) is guaranteed to have both a supremum and an infimum. This is a very strong condition that many posets don't satisfy.
• Some posets have subsets with no upper bound at all. For instance, in $(\mathbb{Z}, \leq)$, the subset of all positive integers has no upper bound.

Least upper bound

The least upper bound captures the idea of the tightest possible ceiling on a subset.

Supremum definition

The supremum (or least upper bound) of a subset $A$ in a poset $(S, \leq)$, denoted $\sup(A)$ or $\bigvee A$, is an element $s \in S$ satisfying two conditions:

1. $s$ is an upper bound of $A$: for all $x \in A$, $x \leq s$.
2. $s$ is the least such bound: for every upper bound $b$ of $A$, $s \leq b$.

The supremum may or may not exist for a given subset. But when it does exist, it's unique (by antisymmetry: if $s_1$ and $s_2$ both satisfy the definition, then $s_1 \leq s_2$ and $s_2 \leq s_1$, so $s_1 = s_2$).

Relationship to maximum

• If $A$ has a maximum element $m$ (meaning $m \in A$ and $x \leq m$ for all $x \in A$), then $m = \sup(A)$. The maximum is always the supremum.
• The converse is false: a supremum can exist without being a maximum. The classic example is the open interval $(0, 1)$ in $\mathbb{R}$. Here $\sup(0,1) = 1$, but $1 \notin (0,1)$, so there's no maximum.
• In finite totally ordered sets, the supremum of a nonempty subset always exists and equals the maximum.

Greatest lower bound

The greatest lower bound is the dual concept: the tightest possible floor on a subset.

Infimum definition

The infimum (or greatest lower bound) of a subset $A$ in a poset $(S, \leq)$, denoted $\inf(A)$ or $\bigwedge A$, is an element $g \in S$ satisfying:

1. $g$ is a lower bound of $A$: for all $x \in A$, $g \leq x$.
2. $g$ is the greatest such bound: for every lower bound $a$ of $A$, $a \leq g$.

Like the supremum, the infimum is unique when it exists, and its existence is not guaranteed in an arbitrary poset.

Relationship to minimum

• If $A$ has a minimum element $m$ (meaning $m \in A$ and $m \leq x$ for all $x \in A$), then $m = \inf(A)$.
• The infimum can exist without being a minimum. For the open interval $(0, 1)$ in $\mathbb{R}$, $\inf(0,1) = 0$, but $0 \notin (0,1)$.
• In finite totally ordered sets, the infimum of a nonempty subset always equals the minimum.

Bounds in partial orders

Partial orders allow for incomparable elements, which makes the behavior of bounds more interesting (and sometimes more surprising) than in total orders.

Hasse diagrams

A Hasse diagram is a graphical representation of a finite poset:

• Elements are drawn as vertices.
• If $x < y$ and there's no element strictly between them (i.e., $x < y$ is a covering relation), you draw an edge from $x$ up to $y$.
• Transitivity is implied by the diagram, so you don't draw redundant edges.

Upper bounds of a subset appear above all the subset's elements in the diagram, and lower bounds appear below. Hasse diagrams make it much easier to visually identify bounds, chains, and antichains.

Chains vs. antichains

• A chain is a subset where every pair of elements is comparable (a totally ordered subset). For a finite nonempty chain, the maximum is the supremum and the minimum is the infimum, so bounds always exist within the poset.
• An antichain is a subset where no two distinct elements are comparable. Finding bounds for an antichain can be trickier. An antichain of two elements has a least upper bound only if the poset contains an element above both of them, and that element is minimal among all such elements.

Example: In the poset of subsets of $\{1, 2\}$ ordered by inclusion, the antichain $\{\{1\}, \{2\}\}$ has $\sup = \{1,2\}$ and $\inf = \emptyset$.

Bounds in lattices

A lattice is a poset in which every pair of elements has both a least upper bound and a greatest lower bound. This makes lattices particularly well-behaved for studying bounds.

Completeness property

• A complete lattice is one where every subset (not just every pair) has both a supremum and an infimum. This includes the empty set, which means a complete lattice always has a greatest element ($\top$) and a least element ($\bot$).
• Completeness is a strong property. It provides the foundation for results like Tarski's fixed point theorem, which guarantees that every order-preserving function on a complete lattice has a fixed point.
• Not every lattice is complete. For example, $(\mathbb{Z}, \leq)$ is a lattice but not a complete one, since $\mathbb{Z}$ itself has no supremum or infimum in $\mathbb{Z}$.

Lattice operations

The two fundamental operations in a lattice are:

• Join ($\vee$): $a \vee b = \sup\{a, b\}$, the least upper bound of two elements.
• Meet ($\wedge$): $a \wedge b = \inf\{a, b\}$, the greatest lower bound of two elements.

These operations satisfy several algebraic laws:

• Idempotent: $a \vee a = a$, $a \wedge a = a$
• Commutative: $a \vee b = b \vee a$, $a \wedge b = b \wedge a$
• Associative: $(a \vee b) \vee c = a \vee (b \vee c)$
• Absorption: $a \vee (a \wedge b) = a$ and $a \wedge (a \vee b) = a$

A lattice is called distributive if meet distributes over join (and vice versa): $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$.

Applications of bounds

Optimization problems

Bounds show up constantly in optimization:

• In linear programming, upper and lower bounds define the feasible region. The optimal solution sits at a boundary of this region.
• Branch and bound algorithms solve combinatorial optimization problems by computing bounds on subproblems and pruning branches that can't improve on the best known solution.
• Interval arithmetic uses explicit upper and lower bounds to track rounding errors and guarantee that the true answer lies within a computed interval.

Fixed point theorems

Bounds are central to proving that fixed points exist:

• Tarski's fixed point theorem states that every order-preserving (monotone) function on a complete lattice has a least fixed point and a greatest fixed point. The proof constructs these fixed points using suprema and infima.
• The Knaster-Tarski theorem is essentially the same result, sometimes stated for complete lattices or for the more general setting of directed-complete partial orders.
• These theorems have practical applications in computer science (semantics of programming languages), game theory, and economics.

Bounds in specific structures

Real number line

The real numbers $(\mathbb{R}, \leq)$ form a complete totally ordered set, and their bound properties are foundational to analysis:

• The completeness axiom (also called the least upper bound property) states: every nonempty subset of $\mathbb{R}$ that is bounded above has a supremum in $\mathbb{R}$. This is what distinguishes $\mathbb{R}$ from $\mathbb{Q}$.
• Dedekind cuts use this idea to construct the reals from the rationals. A Dedekind cut partitions $\mathbb{Q}$ into a lower set and an upper set, and each cut corresponds to a real number.
• Intervals on the real line are defined by their bounds: $[a, b]$ (closed), $(a, b)$ (open), $[a, b)$ and $(a, b]$ (half-open).

Power sets

The power set $\mathcal{P}(X)$ of a set $X$, ordered by inclusion $\subseteq$, forms a complete lattice:

• The join (supremum) of a collection of subsets is their union.
• The meet (infimum) of a collection of subsets is their intersection.
• $\emptyset$ is the least element (global lower bound), and $X$ is the greatest element (global upper bound).
• Power set lattices are always distributive and in fact form Boolean algebras, connecting directly to propositional logic.

Computational aspects

Algorithms for finding bounds

The method you use to find bounds depends on the structure you're working with:

• In a sorted array, binary search finds upper and lower bounds in $O(\log n)$ time.
• In tree-based data structures (like balanced BSTs), bound queries also run in $O(\log n)$.
• For general posets represented as directed acyclic graphs, finding bounds may require traversing significant portions of the graph.
• Iterative methods (like Newton's method) approximate bounds in continuous settings, converging to a supremum or infimum through successive refinement.

Complexity considerations

• For simple structures (sorted lists, balanced trees), bound-finding is efficient: $O(\log n)$.
• In more complex settings (constraint satisfaction, combinatorial optimization), finding optimal bounds can be NP-hard.
• When exact bounds are computationally infeasible, approximation algorithms provide bounds that are provably close to optimal, often with guaranteed error ratios.

Theoretical implications

Completeness of ordered sets

Completeness is one of the most important structural properties in order theory, and it's defined entirely in terms of bounds:

• A poset is Dedekind-complete if every nonempty subset that is bounded above has a supremum. The real numbers satisfy this; the rationals do not (consider $\{q \in \mathbb{Q} : q^2 < 2\}$, which has no supremum in $\mathbb{Q}$).
• Completeness properties determine whether fixed point theorems apply, whether limits exist, and whether certain equations have solutions within the structure.
• In some contexts, order-completeness connects to topological completeness (e.g., the order topology on $\mathbb{R}$ is complete as a metric space).

Dedekind cuts

Dedekind cuts are a construction that uses bounds to build $\mathbb{R}$ from $\mathbb{Q}$:

1. Partition $\mathbb{Q}$ into two nonempty sets $(L, U)$ where every element of $L$ is less than every element of $U$.
2. Require that $L$ has no maximum element.
3. Each such partition defines a real number: the supremum of $L$ (which may or may not be rational).

This construction demonstrates that the completeness of $\mathbb{R}$ isn't just an axiom you accept on faith. You can build a complete ordered field from an incomplete one using the concept of bounds.

Bounds in order theory proofs

Induction techniques

• Mathematical induction proves bound-related properties in well-ordered sets (like $\mathbb{N}$) by establishing a base case and an inductive step.
• Transfinite induction extends this to ordinals beyond $\omega$, handling limit ordinals by taking suprema of previously established results.
• Structural induction applies when the poset or its elements are defined recursively (common in computer science applications).
• Well-founded induction generalizes all of these: it works on any well-founded relation, where every nonempty subset has a minimal element.

Contradiction methods

• To prove a supremum is unique, assume two distinct suprema $s_1$ and $s_2$ exist. By the definition of least upper bound, $s_1 \leq s_2$ and $s_2 \leq s_1$, so $s_1 = s_2$ by antisymmetry. (This is more of a direct proof, but the logic of eliminating alternatives is similar.)
• To prove a bound doesn't exist, assume it does and derive a contradiction, often by constructing an element of the subset that violates the bound condition.
• Contrapositive arguments are also common: for instance, showing that if a poset lacks a certain completeness property, then some specific subset must fail to have a supremum.