4
$\begingroup$

Axiom of Induction

enter image description here

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?

$\endgroup$
0

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ nice and useful $\endgroup$
    – Olórin
    Sep 13, 2014 at 16:22
0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .