# Why is $\mathbb{N}$ well-ordered?

Define

$$0:= \emptyset$$ $$1:= \{\emptyset\} =\{0\}$$ $$2:= \{\emptyset, \{\emptyset\}\}=\{0,1\}$$ $$\vdots$$ $$n:= \{0,1, \dots, n-1\}$$

And put $$\mathbb{N}:= \{0,1, \dots\}$$.

Questions:

(1) Doesn't this kind of 'recursive' definition give us what we want? It seems like we need $$\mathbb{N}$$ to define a recursion, so this seems circular?

(2) How can I formally show that $$\mathbb{N}$$, partially ordered by the inclusion, is in fact well-ordered?

Attempt:

Let $$\emptyset \neq Y \subseteq \mathbb{N}$$. Fix $$y \in Y$$. If $$y= y_0$$ is a minimum, we are done. If not, there is an element $$y_1< y_0$$ with $$y_1 \in Y$$. If $$y_1$$ is a minimum, we are done. Otherwise, there is $$y_2 < y_1$$ with $$y_2 \in Y$$. If this process does not stop, we obtain infinitely many elements in $$\mathbb{N}$$ smaller than $$y$$, which should be impossible, but I think I'm making circulaar reasonings here as well.

• it is well-ordered by assumption in the case of the Peano axioms, or by the way that the ZF axioms were chosen. That is: that $\Bbb N$ would be well-redered or not depends on the model that we use to define the natural numbers Commented Mar 9, 2020 at 10:12
• @Masacroso: No, actually PA has the induction axiom(s) which prove that $\Bbb N$ is (internally) well-ordered. Commented Mar 9, 2020 at 10:19
• @AsafKaragila this is exactly what i said Commented Mar 9, 2020 at 12:51
• @Masacroso: But the point is that internally speaking, PA cannot detect ill-foundedness, and not because of "assumption". Commented Mar 9, 2020 at 13:30

We are not defining the natural numbers one by one. Instead we give a recursive definition: $$0=\varnothing$$; if $$n$$ was defined, $$n+1=n\cup\{n\}$$; $$\Bbb N$$ is the smallest collection containing $$0$$ and closed under this definition.
As for your second question, show that if $$Y$$ is a non-empty set of natural numbers, then $$\bigcap Y=\min Y$$.