My Analysis lecturer defined $\mathbb{N}$ as the smallest set such that $0 \in \mathbb{N}$ and if $n \in \mathbb{N}$ then $n+1 \in \mathbb{N}$. He then proceeded to "prove" the Principle of Mathematical Induction as follows: Let $P(n)$ be a family of propositions indexed on $\mathbb{N}$. Suppose that $P(0)$ is true and that for any $n \geq 0$, if $P(n)$ is true then $P(n+1)$ is true. Let $S$ be the set of natural numbers such that $P(n)$ is true. Then $S$ is a subset of $N$. Since $P(0)$ is true, $0 \in S$, and if $n \in S$ then $P(n)$ is true, so $P(n+1)$ is true, or equivalently $n+1 \in S$. Thus $S$ has the properties $0 \in S$ and if $n \in S$ then $n+1 \in S$; as $N$ is the smallest set with these properties, $N$ is a subset of $S$, but since we already know $S$ is a subset of $N$ it follows that $S=N$, i.e. $P(n)$ is true for all natural numbers.
My question is whether this proof is actually valid. I can't see any obvious flaw in the logic, but at the same time, I always thought that either the Principle of Mathematical Induction or (equivalently) the Well-Ordering Principle had to be taken as an axiom and couldn't be proved itself.
Best Answer
The Well-Ordering Principle states that any non-empty set can be well-ordered. This does not follow from the standard ZF axioms, and it is required to be assumed as its own axiom (conventionally, the Axiom of Choice is used instead, but assuming the rest of ZF, they are equivalent).
However, having well-ordered sets does not require the Well-Ordering Principle. Many sets can be proven to be well-orderable without any Well-Ordering Principle. This includes $\Bbb N$, as defined by your lecturer (assuming he has some sensible formal definition of $0$ and $+1$, and that he has shown that $\Bbb N$ is actually a set).
Similarily, proving that you can induct over $\Bbb N$ does not require the Well-Ordering Principle. However, proving that you can induct over any set does.
New answer: (After realizing I mixed up the Principle and the Theorem.)
You're mixing up the Well-Ordering Principle with the Well-Ordering Theorem. This is an easy thing to do (as witnessed by everything preceeding this paragraph). The Well-Ordering Principle is a theorem in ZF. It does not require any additional axioms, and it states that the standard ordering of $\Bbb N$ is a well-order.
The Well-Ordering Theorem is a statement that is independent of ZF, and states that all non-empty sets can be fitted with a well-order. This is what I described in my previous answering attempt.