0
$\begingroup$

I was reading an article in wikipedia about math induction: http://en.wikipedia.org/wiki/Mathematical_induction

And there is a sentence:

"Note that the first quantifier in the axiom ranges over predicates rather than over individual numbers."

It is told about the axiom of math induction:

enter image description here

As I understand, first quantifier is P(0), i.e. math induction base.

What does it mean that math induction base ranges over predicates rather than over individual numbers?

  • 0
    Let $S=S_P$ be the **subset** of $\mathbb{N}$ at which $P$ is true. Replace $P(x)$ by $x\in S$. Use of the word predicate is a holdover from the days before set theoretic language became universal.2012-06-08

2 Answers 2

2

No, the first quantifier is the $\forall$ at the very beginning of the expression. It quanitifies $P$, which can be any predicate describing natural numbers. For example, $P(n)$ could be ‘$n$ is even’, or ‘$n$ is prime’, or $\exists p(p\text{ is prime and }p^2\mid n)$.

The second and third quantifiers are the $\forall$’s in $\forall k\in\Bbb N$ and $\forall n\in\Bbb N$: they range over elements of $\Bbb N$, i.e., over natural numbers.

$P(0)$ is simply a sentence saying ‘the number $0$ has the property $P$’; there is no quantifier here at all (unless, of course, the predicate $P$ itself contains quantifiers, as in my third example above).

1

Let $I_P$ be the induction sentence you have written above, without the $(\forall P)$ in the front. Usually, induction is not one axiom. It is an axiom Schema. Induction is $\{I_P\}$ for all formulas $P$ in one free variable. That is, you have an induction axiom for each formula $P$.

  • 1
    It is a "schema" rather than a single axiom only when a quantifier over predicates is not allowed. I think one should be explicit about that point when mentioning that it's a schema rather than a single axiom.2012-06-08