Well-Foundedness

Minimal Elements

Definition

Let $\prec$ be a relation on $A$. An element $m \in S \subseteq A$ is minimal in $S$ if:

$\neg\exists x \in S. x \prec m$

No element of $S$ is strictly below $m$.

Distinction: Minimal vs Least

• Minimal: No element is below $m$ (local property)
• Least: $m$ is below every element of $S$

A set can have multiple minimal elements but at most one least element.

Example

On $\{1, 2, 3\}$ with partial order given by divisibility:

• Minimal elements of $\{2, 3, 4, 6\}$ are $2$ and $3$
• No least element

Well-Founded Relations

Definition

A relation $\prec$ on $A$ is well-founded if every non-empty subset $S \subseteq A$ has a minimal element.

$\forall S \subseteq A. (S \neq \emptyset \Rightarrow \exists m \in S. \neg\exists x \in S. x \prec m)$

Equivalent Characterisation

$\prec$ is well-founded iff there is no infinite descending chain:

$a_0 \succ a_1 \succ a_2 \succ \cdots$

Proof:

$(\Rightarrow)$: If such a chain exists, the set $\{a_0, a_1, a_2, \ldots\}$ has no minimal element.

$(\Leftarrow)$: If some $S$ has no minimal element, we can build a descending chain by repeatedly choosing smaller elements.

Examples

Well-Founded

• $<$ on $\mathbb{N}$: Every non-empty subset has a least element (well-order)
• $<$ on $\mathbb{Z}$ restricted to $\{n : n \geq k\}$ for any $k$
• The “proper subterm” relation on finite trees

Not Well-Founded

• $<$ on $\mathbb{Z}$: $\{\ldots, -2, -1, 0\}$ has no minimal element
• $<$ on $\mathbb{Q} \cap (0, 1)$: $\{1/n : n \geq 1\}$ has no minimal element
• $<$ on $\mathbb{R}$: any unbounded-below subset

Well-Orders

Definition

A well-order is a well-founded total order.

Every non-empty subset has a unique least element.

Examples

• $(\mathbb{N}, \leq)$ is a well-order
• $(\mathbb{Z}, \leq)$ is NOT a well-order
• Any finite totally ordered set is a well-order

Properties

If $\prec$ is a well-order, then:

1. Every non-empty subset has a unique least element
2. For each $a$, the set $\{x : x \prec a\}$ is well-ordered
3. Principle of induction applies (see next section)

The Axiom of Foundation

In ZF set theory, the Axiom of Foundation states that $\in$ is well-founded on any set.

This prohibits infinite descending $\in$-chains: $\cdots \in x_2 \in x_1 \in x_0$

---

Summary

• $m$ is minimal in $S$ if no element of $S$ is below $m$
• $\prec$ is well-founded if every non-empty subset has a minimal element
• Equivalent: no infinite descending chains
• $<$ on $\mathbb{N}$ is well-founded; $<$ on $\mathbb{Z}$ or $\mathbb{Q}$ is not
• A well-order is a well-founded total order