2
$\begingroup$

If natural numbers are defined as $\mathbb{N} = \{1\} \cup \{n + 1 \mid n \in \mathbb{N}\}$, and we know that $P(1)$ and $\forall n \in \mathbb N,P(n) \implies P(n+1)$, then $S = \{ n \mid P(n)\} = \{1\} \cup \{n + 1 \mid n \in S\} = \mathbb N$, meaning that $\forall n \in \mathbb{N}, P(n)$.

In this case why do we need induction (or the equivalent well-ordering principle) as an axiom?

$\endgroup$
  • $\begingroup$ I don't think induction is an axiom, - it is a theorem, and I distinctly remember it even having a second (quite odd) form... $\endgroup$ – gt6989b Sep 29 '17 at 2:22
  • $\begingroup$ @gt6989b: Wikipedia calls it an axiom: en.wikipedia.org/wiki/Mathematical_induction#Axiom_of_induction $\endgroup$ – user485573 Sep 29 '17 at 2:23
  • $\begingroup$ It says that "it can be formalized as a 2nd order axiom" -- it does not have to be but can be, so you can choose this definition and it is equivalent to the other one... $\endgroup$ – gt6989b Sep 29 '17 at 2:24
  • $\begingroup$ I don't follow you. What does "why do we need induction as an axiom" have to do with what you said in your first paragraph? Are you saying that induction shouldn't be an axiom, because it's true? So according to you we shouldn't have axioms at all? Or we should only have false axioms like the Axiom of Determinacy? $\endgroup$ – bof Sep 29 '17 at 3:44
2
$\begingroup$

Your definition is circular, you use $\mathbb{N}$ to define $\mathbb{N}$. To construct the set $\mathbb{N}$, use the Peano's Axioms, and the fifth axiom is percisely the Induction Principle: If $S \subseteq \mathbb{N}$ is a set such that $0 \in S$ and $n \in S \Rightarrow n+1 \in S$ then $S=\mathbb{N}$.

The Induction Principle and the Principle of well-ordering are equivalent.

$\endgroup$
  • $\begingroup$ It's not circular, I'm defining $\mathbb{N}$ as the unique set for which that equality is true. But I see what you mean, when I define it that way, I'm implying the axiom of induction $\endgroup$ – user485573 Sep 29 '17 at 2:31
  • 1
    $\begingroup$ @user485573 What is $n+1$? Under a reasonable definition, there are many sets that satisfy your given equation. You need to strengthen your definition to ensure uniqueness. $\endgroup$ – Andrés E. Caicedo Sep 29 '17 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.