Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
It means that any predicate P for which P(0) is true and for which P(k) implies P(k+1), holds for all natural numbers. This is not a statement about any particular inductive argument, but ALL of them (so it's not really an axiom per se, but an axiom schema, we get one "instance" of this axiom for each predicate P). –  David Wheeler Jun 8 '12 at 9:00
    
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. –  André Nicolas Jun 8 '12 at 13:34

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer
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. –  Michael Hardy Jun 8 '12 at 11:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.