# Well-ordered set

A well-ordered set is a totally ordered set $$(S, \leq)$$, such that for any nonempty subset $$U \subset S$$ there is some $$x \in U$$ such that for every $$y \in U$$, $$x \leq y$$; that is, every nonempty subset of $$S$$ has a least element.

Any finite totally ordered set is well-ordered. The simplest infinite well-ordered set is $$\mathbb N$$, also called $$\omega$$ in this context.

Every well-ordered set is isomorphic to a unique ordinal number, and thus any two well-ordered sets are comparable.

The order $$\leq$$ is called a “well-ordering,” despite the fact that “well” is usually an adverb.

# Induction on a well-ordered set

mathematical induction works on any well-ordered set. On well-ordered sets longer than $$\mathbb N$$, this is called transfinite induction.

Induction is a method of proving a statement $$P(x)$$ for all elements $$x$$ of a well-ordered set $$S$$. Instead of directly proving $$P(x)$$, you prove that if $$P(y)$$ holds for all $$y < x$$, then $$P(x)$$ is true. This suffices to prove $$P(x)$$ for all $$x \in S$$.

Let $$U = \{x \in S \mid \neg P(x) \}$$ be the set of elements of $$S$$ for which $$P$$ doesn’t hold, and suppose $$U$$ is nonempty. Since $$S$$ is well-ordered, $$U$$ has a least element $$x$$. That means $$P(y)$$ is true for all $$y < x$$, which implies $$P(x)$$. So $$x \not\in U$$, which is a contradiction. Hence $$U$$ is empty, and $$P$$ holds on all of $$S$$.

Parents:

• Is $$\mathbb{N}$$ itself called $$\omega$$, or just the usual ordering of it?