Set theoretic construction of the natural numbers I'm trying to tie some loose ends here. My lecturer didn't bother to go into details, so I have to work it out myself. I usually hate to be pedantic, but these questions have been bugging me for a while.
First, what's the proper definition of the natural numbers? The one given to me is: "the smallest set such that $\emptyset\in N$ and $x\in N\implies x\cup\lbrace x\rbrace\in N$". This definition does not seem rigorous to me. What does "smallest" mean here? Does it mean that no proper subset have the same property? And how to prove the existence of such set (under ZFC)? Lastly, how to prove this set satisfies Peano's axioms, especially the last axiom (about induction)?
Next, how to prove that the relation $<$ is a total order? The definition is $x<y\Leftrightarrow x\subset y$. I was thinking of changing the definition into "the transitive closure of $\lbrace(n,n')|n\in N\rbrace$" (to avoid the set theory stuffs), but it's still difficult to prove that it's a total order.
Lastly, how to prove the well ordering principle? I suspect this would be easy after proving the previous statement though.
 A: Proper definition of the natural numbers.
Here's one taken (from memory) from Halmos's Naive Set Theory.
Definition. Given a set $x$, we define $x^+$, the successor of $x$, to be the set $x\cup\{x\}$.
If $x$ is a set, $x^+$ is a set: $\{x\}$ is an element of the power set of $X$, so $x^+$ is a subset of $x\cup\mathcal{P}(x)$, hence a set (by the Axiom of Powers, Axiom of Unions, and Axiom of Separation).
Definition. A set $S$ is said to be inductive if and only if $\emptyset\in S$ and for every $x$, if $x\in S$ then $x^+\in S$.
Axiom of Infinity. There exists at least one inductive set.
Now, let $S$ be any inductive set. Let
$$\mathbb{N}_S = \bigcap\{A\subseteq S\mid A\text{ is inductive}\}.$$
This is a set, since the family is a subsets of $\mathcal{P}(S)$, and so its intersection is a set.
Lemma. The intersection of any nonempty collection of inductive sets is inductive.
Proof. Suppose $\{S_i\}$ is a nonempty family of inductive sets, and let $S=\cap S_i$  Then $\emptyset\in S_i$ for each $i$, hence $\emptyset\in S$; and if $x\in S$, then $x\in S_i$, for each $i$; hence (since each $S_i$ is inductive), $x^+\in S_i$ for each $i$, and thus $x^+\in S$. Thus, $S$ is inductive. $\Box$
Corollary. If $S$ is inductive, then $\mathbb{N}_S$ is inductive. Moreover, if $B$ is any inductive subset of $S$, then $\mathbb{N}_S\subseteq B$. 
Theorem. If $S$ and $T$ are two inductive sets, then $\mathbb{N}_S = \mathbb{N}_T$.
Proof. Consider $\mathbb{N}_T\cap S$; this is an inductive subset of $S$, hence $\mathbb{N}_S\subseteq \mathbb{N}_T\cap S\subseteq \mathbb{N}_T$. Symmetrically, since $\mathbb{N}_S\cap T$ is inductive, then $\mathbb{N}_T\subseteq \mathbb{N}_S\cap T\subseteq\mathbb{N}_S$. Thus, $\mathbb{N}_S=\mathbb{N}_T$. $\Box$
Definition. $\mathbb{N}$ is the set $\mathbb{N}_S$, where $S$ is any inductive set.
This set is well defined, since by the theorem above it does not matter what inductive set we start with, we always get the same set $\mathbb{N}$; and there is at least one inductive set by the Axiom of Infinity.
Theorem. If $S$ is any inductive set, then $\mathbb{N}\subseteq S$; that is, $\mathbb{N}$ is the "smallest" inductive set, in the sense of set inclusion.
Proof. If $S$ is any inductive set, then $\mathbb{N}=\mathbb{N}_S\subseteq S$. $\Box$
Now let $0=\emptyset$, and let $s(x) = x^+$ for every $x$.
Theorem. (The Peano Axioms) $\mathbb{N}$ satisfies the following:


*

*$0\in \mathbb{N}$.

*If $n\in \mathbb{N}$, then $s(n)\in\mathbb{N}$.

*For all $n\in\mathbb{N}$, $s(n)\neq 0$.

*If $s(n)=s(m)$, then $n=m$.

*If $S\subseteq \mathbb{N}$ is such that $0\in S$ and if $n\in S$ then $s(n)\in S$, then $S=\mathbb{N}$.


Proof. Since $\mathbb{N}$ is inductive, 1 and 2 are satisfied. 3 is satisfied because by definition, $n\in s(n)$, hence $s(n)\neq\emptyset=0$. 5 is satisfied because the given conditions imply that $S$ is inductive, and therefore $\mathbb{N}\subseteq S$. Since we already have $S\subseteq \mathbb{N}$, then $S=\mathbb{N}$ holds.
The only difficulty is property 4. This requires some auxiliary results:
Lemma 1. If $n\in\mathbb{N}$, and $m\in n$, then $m\subseteq n$. 
Proof. Let $S=\{n\in\mathbb{N}\mid \text{for all }m\in n, m\subseteq n\}$.
Then $0\in S$, since $0=\emptyset$ satisfies the property by vacuity. Assume that $k\in S$, and let $m\in s(k) = k\cup\{k\}$. If $m\in k$, then since $k\in S$ we have $m\subseteq k\subseteq s(k)$. If $m\notin k$, then $m\in\{k\}$, hence $m=k$, and $m=k\subseteq k\cup\{k\}=s(k)$. Thus, $s(k)\in S$. 
We conclude that $S$ is an inductive subset of $\mathbb{N}$, and therefore that $S=\mathbb{N}$. $\Box$
Lemma 2. If $n\in\mathbb{N}$ and $m\in n$, then $n\not\subseteq m$.
Proof.  Let $S=\{n\in\mathbb{N}\mid\text{for all }m\in n, n\not\subseteq m\}$. Then $0\in S$, since it satisfies the condition by vacuity.
Assume that $k\in S$. If $m\in s(k)=k\cup\{k\}$, then either $m\in k$, in which case $k\not\subseteq m$, hence $s(k)\not\subseteq m$ (since $k\subseteq s(k)$); or else $m=k$. But since $k\in S$, then $k\notin k$ (for $k\subseteq k$, so $k\in k$ would contradict that $k\in S$). Since $k\in s(k)$, then $s(k)\not\subseteq k=m$. Thus, if $k\in S$ then $s(k)\in S$. Hence $S$ is an inductive subset of $\mathbb{N}$, so $S=\mathbb{N}$. $\Box$
We are now ready to prove property 4. Assume that $s(n)=s(m)$. Since $m\in s(m)=s(n) = n\cup \{n\}$, then either $m=n$, or $m\in n$. If $m=n$, we are done. So assume that $m\in n$. Since $n\in s(n)=s(m)$, then $n\in m\cup \{m\}$; since $n\neq m$, then $n\in m$. Thus, $n\in m$, hence $n\subseteq m$; but $m\in n$, contradicting Lemma 2. This contradiction arises from assuming that $m\in n$. Therefore, $m\notin n$, so $m=n$, hence $\mathbb{N}$ satisfies the fourth Peano axiom. $\Box$
Proof that $\lt$ is a total order on $\mathbb{N}$.
(I'm more used to the definition $n\lt m\Longleftrightarrow n\in m$, but I'll use your definition with proper inclusion)
We want to prove that if $n,m\in\mathbb{N}$, then either $n=m$, $n\subset m$, or $m\subset n$.
Lemma. Let $n\in \mathbb{N}$. Then either $n=0$, or there exists $k\in\mathbb{N}$ such that $n=s(k)$.
Proof. Let $S=\{n\in\mathbb{N}\mid n=0\text{ or }n=s(k)\text{ for some }k\in\mathbb{N}\}$. 
Then $0\in S$; if $k\in S$, $s(k)\in S$ (since $s(k)$ is a successor). Thus, $S$ is inductive, hence $S=\mathbb{N}$. $\Box$
Lemma. Let $k,n\in\mathbb{N}$. If $k\subset n$, then $s(k)\subseteq n$.
Proof. Let $S=\{n\in\mathbb{N}\mid \text{if }k\subset n\text{ then }s(k)\subseteq n\}$. 
Then $0\in S$ by vacuity. If $n\in S$, let $k\subset s(n)=n\cup\{n\}$. 
If $k\subset n$, then $s(k)\subseteq n\subset s(n)$. If $k=n$, then $s(k)=s(n)$. The only other possibility is that $n\in k$. But since $k$ is a natural number, then $n\in k$ implies $n\subseteq k$. But $n\subseteq k\subset n\cup\{n\}$ is impossible. Hence, $k\subset s(n)$ simplies $s(k)\subseteq s(n)$. This proves $S$ is inductive, hence $S=\mathbb{N}$. 
Finally, fix $m$, and let $S=\{n\in\mathbb{N}\mid m\subseteq n\text{ or }n\subset m\}$. 
Then $0\in S$: if $m=\emptyset$, then $m\subseteq 0$; if $m\neq\emptyset$, then $\emptyset\subset m$. 
Assume that $k\in S$. If $m\subseteq k$, then $m\subseteq s(k)$. If $k\subset m$, then by the Lemma $s(k)\subseteq m$. If $s(k)=m$, then $s(k)\in S$. If $s(k)\subset m$, then $s(k)\in S$. Either way, $S$ is inductive, hence $S=\mathbb{N}$. Therefore, $\lt$ is a trichotomic relation on $S$.
Proof of the Well Ordering Principle
Lemma. If $n\in\mathbb{N}$, then there does not exist $k\in\mathbb{N}$ such that $n\lt k\lt s(n)$.
Proof. It is impossible to have $n\subset k\subset n\cup\{n\}$. $\Box$
Well Ordering Principle. If $A\subseteq\mathbb{N}$ and $A\neq\emptyset$, then $A$ has a smallest element.
Proof. Let $A\neq\emptyset$, $A\subseteq \mathbb{N}$. Let $S=\mathbb{N}-A$. 
Let $S'= \{n\in\mathbb{N}\mid n\in S\text{ and for all }k,\text{ if }k\lt n\text{ then }k\in S\}$. Since $S'\subseteq S\neq\mathbb{N}$, then $S'$ is not inductive. Therefore, either $0\notin S'$, or else there exists $k\in S'$ such that $s(k)\notin S'$.
If $0\notin S'$, then since for all $k\lt 0$, $k\in S$, it follows that $0\notin S$. Therefore, $0\in A$. Since $0$ is the smallest element of $\mathbb{N}$, it is also the smallest element of $A$ and we are done.
Assume then that there exist $k\in \mathbb{N}$ such that $k\in S'$ but $s(k)\notin S'$. Then $k\in S$ and for all $n\in\mathbb{N}$, if $n\lt k$ then $n\in S$. That means that for all $n\in\mathbb{N}$, if $n\lt s(k)$, then $n\in S$ (for $n\lt s(k)$ implies $n\leq k$ by the Lemma, and so either $n=k\in S$ or $n\lt k$ hence $n\in S$ since $k\in S'$). That means that because $s(k)\notin S'$, it must be because $s(k)\notin S$. Thus, $s(k)\in A$. However, as we have already seen, if $n\lt s(k)$, then $n\in S$, hence $n\lt s(k)\Rightarrow n\notin A$. Thus, $n\in A\Rightarrow s(k)\leq n$, which proves that $s(k)$ is the smallest element of $A$. $\Box$
A: If you have two sets such that each of them satisfies the condition $\emptyset\in N$ and $x\in N\Rightarrow x\cup\{x\}\in N$, then the intersection of the two sets satisfies the same property. In fact this holds not just for the intersection between two sets, but for the intersection between any number of sets. So $\mathbb N$ can be defined as the intersection of all sets that staisfy the condition. That there is at least one set that satisfies it is usually an explicit axiom of set theory -- the Axiom of Infinity.
This definition of $\mathbb N$ directly implies that mathematical induction works. Namely, assume that $A$ is a subset of $\mathbb N$ such that $0\in A$ and $\forall n\in A: n+1\in A$. That means exactly that $A$ is one of the sets we intersected to make $\mathbb N$ in the first place. So $A$ is both a subset of $\mathbb N$ and a superset of $\mathbb N$, thus it must be $\mathbb N$ itself.
Then prove that long induction works -- essentially because $a<b+1$ if and only if $a=b$ or $a<b$.
Finally, we can prove well-ordering by long induction on $n$: if some set $B$ of natural numbers contains $n$, then it contains a least element.
