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'm reading the Stanford Encyclopedia of Philosophy entry on Second-order and Higher-order Logic. In it, I read the following:

[W]e can express the Peano induction postulate by a second-order sentence:

∀X[X0 & ∀y(Xy → XSy) → ∀y Xy]

This sentence expresses the idea that X is true of all natural numbers, if it is true of 0 and its truth at some number y guarantees its truth at the successor of y, no matter what set of numbers X might be true of.

Now, I don't quite see why this sentence has to be second-order to express the Peano induction. That is, what would be missing if it was written in first-order logic, that is, without the "∀X" part?

X0 & ∀y(Xy → XSy) → ∀y Xy

I'd read this in the following way: IF (X is true for zero) and (for every y if X is true for y then it is also true for the successor of y) THEN X is true for all y's. What seems to be missing from my natural language interpretation of the modified sentence compared to the quoted interpretation of the original sentence above is the "no matter what set of numbers X might be true of", but I don't really see what this adds. Is it implied in my first-order sentence that this does not hold for certain sets of X? If so, I really can't see it.

share|improve this question
2  
This might be helpful. –  Asaf Karagila Feb 7 '12 at 12:39

2 Answers 2

up vote 4 down vote accepted

What is X? The second order formulation is about all properties.

If $X$ is a property that can be expressed in FO logic, you can add an axiom saying induction holds for this property. If you do this for ever such property, you get a countable number of axioms, which, together with the other axioms of PA, form first order Peano arithmetic.

But you express only countably many properties this way, since you are using a countable language. But every set of natural numbers defines a property and there are uncountably many such sets, so first order Peano arithmetic doesn't cover all of Peano arithmetic.

share|improve this answer

Just as first-order logic does not have quantifiers over sets (or properties), it does not allow free variables for them. So while $$ X(0) \land (\forall n)(X(n) \to X(n+1)) \to (\forall n)X(n) $$ could be a first-order sentence, the only way for that to happen is if we add $X$ to the signature of the first-order theory as a unary relation symbol. But then each model will pick one particular interpretation for $X$, and so that single induction axiom will only cover induction for a single property.

If you could treat the $X$ as a free variable, this would not really be any different than having a universal quantifier. Many people use the convention that axioms are implicitly universally quantified.

share|improve this answer
    
Actually first order induction means that one adds a schema. So the X is really quantified, but not in the object logic but syntactically on the meta-level. –  j4n bur53 Sep 22 '13 at 14:52

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.