Can someone please explain the axiom of induction in lay term?

Question

Axiom of Induction

To me, it says, for all P such that P(0) AND for all k is an element of natural numbers P(k) implies P(K+1) implies for all n is am element in the natural numbers of P(n)

But this is a bit incoherent, can someone please explain the meaning of [] and why is this axiom only holds for natural numbers?

ALso, why do people call this a second order logic? What does a first order logic look like?

Answer 1

The square brackets are just so you can correctly parse the expression, just like parenthesis in plain old arithmetic $2\times 3 + 4$ is ambiguous yet $(2\times 3) +4$ or $2\times (3+ 4)$ is not.

You should interpret $P$ as a property of numbers, e.g. is prime, is even, has a unique prime factorisation, is a counter-example for the Goldback conjecture.

With this in mind, the axiom says that if $P$ is property, that holds of $0$, and if the property holds of $n$ then it holds of $n+1$, then the property holds of all natural numbers.

To see why this is true, suppose $P$ does not hold of $n$, because the natural numbers are well-ordered, if there is a counter-example to $P$ then there is a smallest counterexample. Let $n$ be the smallest. It can't be 0 because we know that $P$ is true of $0$. Therefore $n=m+1$ for some natural number $m$. As $n$ is the smallest counterexample for $P$ then $P$ must be true of $m$. But we supposed that if $P$ is true of a number, it is true of that number $+1$ hence $P$ is true of $m+1= n$, a contradiction. Therefore no counter examples exist.

Induction holds in any structure which has a well-founded order relation, not just in $\mathbb{N}$.

Finally, the axiom you write down is second-order because it quantifies over properties of objects, not the objects themselves. In first order logic, you can only quantify over elements of your domain, not properties of those elements.

Answer 2

I like to think of it this way:

We first show that if $P$ holds for some natural number $n$, then it also holds for $n+1$, i.e. it always works for the next natural number.

Now since we also show that it holds for $n=0$, then it works for $n=1$ (because it always works for the next natural number). And since it works for $n=1$, it must again work for $n=2$, and so on. Therefore, it works for all $n$.