Why proof by induction is working. I know how to make proofs by induction, but I don't understand why it prove that the propriety is true. It's in fact logical, but how to prove that proof by induction really prove the assertion.
 A: Let prove the following theorem:

1) $A(0)$ true,
2) For all $n$ we have that $A(n)$ true $\implies A(n+1)$ true.
Then $A(n)$ is true for all $n$.

Let denote $$\mathcal W=\{n\mid A(n)\ \text{ is false}\}.$$
Suppose by contradiction that $A$ is not true, i.e. that $|\mathcal W|\neq\emptyset$. Since $\mathcal W\subset \mathbb N$ and that $\mathbb N$ is well ordered, there is an $\alpha\in \mathcal W$ which is minimal. By 1) we have that $\alpha\neq 0$. Therefore, by minimality of $\alpha$, we have that $A(\alpha-1)$ is true, which is a contradiction with 2). Therefore $A(n)$ is true for all $n$.
A: I'm not sure what you are asking. There are two things involved:


*

*Intuition. You prove that your statement is true for $n=1$, and then from this you show it's true for $n=2$, from that for $n=3$ etc., just you do all these steps in one step.

*Axiom of induction. One of its versions is
$$ \forall P \Bigl( \Bigl(
  \forall n \bigl( \forall m (m<n \implies P(m)) \implies P(n) \bigr)
  \Bigr) \implies \Bigl(
  \forall n (P(n))
  \Bigr) \Bigr), $$
where $P$ is a formula with one variable, and $n$, $m$ are natural numbers. This is a simpler version of the one mentioned in wikipedia, because the first step -- proving that $P(0)$ is true, is an integral part of the statement.
A: $\bf Definition:$ Inductive set.
An inductive set is a set S that satisfies:


*

*$1\in S$.

*$k\in S\implies k+1\in S$.
$\bf Definition: \Bbb N$
$\Bbb N$ is the set that satisfies:


*

*$\Bbb N$ is inductive.

*If $H$ is inductive, then $\Bbb N \subseteq H$.
Consider now, some proposition $P(n)$. Let $T=\{n\in \Bbb N: P(n)\}$ be the set of $n\in \Bbb N$ that make the proposition true..
Now, if we prove that $T$ is inductive, we will have proved that $T=\Bbb N$ (as we have from it's definition that $T\subseteq\Bbb N$): the proposition is true for all natural $n$.
A: A proposition is true when $n=1$.
If it is true when $n=1$, then it is true when $n=2$.
If it is true when $n=2$, then it is true when $n=3$.
If it is true when $n=3$, then it is true when $n=4$.
If it is true when $n=4$, then it is true when $n=5$.
If it is true when $n=5$, then it is true when $n=6$.
and so on${}\,\ldots$
If this sequence can be shown to keep going, then it is true when $n$ is equal to any of $1,2,3,4,\ldots\,{}$.  That is induction.
