# Well-ordered set

A well-or­dered set is a to­tally or­dered set $$(S, \leq)$$, such that for any nonempty sub­set $$U \subset S$$ there is some $$x \in U$$ such that for ev­ery $$y \in U$$, $$x \leq y$$; that is, ev­ery nonempty sub­set of $$S$$ has a least el­e­ment.

Any finite to­tally or­dered set is well-or­dered. The sim­plest in­finite well-or­dered set is $$\mathbb N$$, also called $$\omega$$ in this con­text.

Every well-or­dered set is iso­mor­phic to a unique or­di­nal num­ber, and thus any two well-or­dered sets are com­pa­rable.

The or­der $$\leq$$ is called a “well-or­der­ing,” de­spite the fact that “well” is usu­ally an ad­verb.

# In­duc­tion on a well-or­dered set

math­e­mat­i­cal in­duc­tion works on any well-or­dered set. On well-or­dered sets longer than $$\mathbb N$$, this is called trans­finite in­duc­tion.

In­duc­tion is a method of prov­ing a state­ment $$P(x)$$ for all el­e­ments $$x$$ of a well-or­dered set $$S$$. In­stead of di­rectly prov­ing $$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 el­e­ments of $$S$$ for which $$P$$ doesn’t hold, and sup­pose $$U$$ is nonempty. Since $$S$$ is well-or­dered, $$U$$ has a least el­e­ment $$x$$. That means $$P(y)$$ is true for all $$y < x$$, which im­plies $$P(x)$$. So $$x \not\in U$$, which is a con­tra­dic­tion. Hence $$U$$ is empty, and $$P$$ holds on all of $$S$$.

Parents:

• Totally ordered set

A set where all the el­e­ments can be com­pared as greater than or less than.

• Is $$\mathbb{N}$$ it­self called $$\omega$$, or just the usual or­der­ing of it?