# Any well-ordered set must be inductive? (Goldrei, Classic Set Theory, Exercise 3.17)

This exercise asks to show that well-ordered set $X$ is inductive ($\varnothing \in X$ and for every $x \in X$, $x^{+} = x \cup \{x\} \in X$). In other words I have to show that $\varnothing \in X$.

But If we take $\Bbb N$ constructed from sets, when $0 = \varnothing$ and for every $n \in \Bbb N$ and the successor of $n$ is $n \cup \{n\}$. We know that this $\Bbb N$ is well-ordered. If we then remove $\varnothing$ from $\Bbb N$, that new $\Bbb N'$ will still be well-ordered (every subset of $\Bbb N'$ has the least element) but no longer inductive ($\varnothing \notin \Bbb N'$). Would not it be a counterexample to the exercise?

Some relevant definitions:  • Are you sure the question did not meant to ask that there is a monotone increasing bijection to an inductive set? (some people treat isomorphic object as if they are the same) – Gina Jul 14 '14 at 4:47
• You are correct, $\mathbb N$ without $\varnothing$ is not inductive. – Git Gud Jul 14 '14 at 4:51

## 2 Answers

The text appears to be "overloading" the notions of $0$ and $x^+$ (and with these the notion of inductive) at this point. While the official definitions were given to be $0 := \varnothing$ and $x^+ := x \cup \{ x \}$, the exercise itself provides new definitions in the context of a well-ordered set. Suppose that $\leq$ is a well-ordering on a set $X$:

• By $0$ we denote the least element of $X$.

• For each $x \in X$ the "successor" $x^+$ of $x$ (according to $\leq$) is the least element of $\{ y \in X : x < y \}$ (if this set is nonempty).

You then appear to be implicitly asked to use these new definitions within the definition of inductive:

A subset $A$ of a well-ordered set $X$ is inductive if $0$ (i.e., the least element of $X$) is in $A$, and if $x^+$ (i.e., the least element of $\{y \in X : x < y \}$) exists and is in $A$ for all $x \in A$.

If $X$ denotes the set obtained after removing $0 = \varnothing$ from $\mathbb{N}$, then while $\varnothing \notin X$ (of course), it still has a least element, namely $\{ \varnothing \}$. $X$ is also well-ordered by $\leq$, and according to the interpretations above, $X$ will be inductive.

You are right, that set would not be, strictly speaking, an inductive set.

But if we take the options that the author might have conflated isomorphic object (which is pretty much what people do everywhere else), then the question become whether there exist a monotone increasing bijection to an inductive set.

Define $Y=\{\{a\in X|a<x\}|x\in X\}$. Define a function $x\rightarrow\{a\in X|a<x\}$.

Now we simply need to prove:

$Y$ is inductive: this follow from condition of $X$.

The function is bijective: this follow from linear ordering.

The function is monotonic increasing: also linear ordering.