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.

What is the advantage of using first-order logic over second-order logic? Second-order logic is more expressive and there is also a way to overcome Russell's paradox...

So what makes first-order logic standard for set theory?

Thanks.

share|improve this question
4  
Completeness theorem. –  Asaf Karagila May 6 '12 at 13:45

1 Answer 1

up vote 12 down vote accepted

First order logic has the completeness theorem (and the compactness theorem), while second-order logic does not have such theorems.

This makes first-order logic pretty nice to work with. Set theory is used to transform other sort of mathematical theories into first-order.

Let us take as an example the natural numbers with the Peano Axioms. The second-order theory (replace the induction schema by a second-order axiom) proves that there is only one model, while the first-order theory has models of every cardinality and so on. Given a universe of set theory (e.g. ZFC), we can define a set which is a model of the second-order theory but everything we want to say about it is actually a first-order sentence in set theory, because quantifying over sets is a first-order quantification in set theory.

This makes set theory a sort of interpreter, it takes a second-order theory and says "Okay, I will be a first-order theory and I can prove this second-order theory." and if we have that the set theory is consistent then by completeness it has a model and all the higher-order theories it can prove are also consistent.

To read more:

  1. what is the relationship between ZFC and first-order logic?
  2. First-Order Logic vs. Second-Order Logic
share|improve this answer
    
I think some parts of this answer might be slightly misleading. It's only true that second order logic with full semantics lacks a compactness theorem. / It doesn't make sense to say "the second order theory proves that there is only one model". Of course we can prove in the metatheory that there's only one full model of PA2, but that can't even be stated in the second-order theory of $\mathbb{N}$, much less proved. Moreover, it isn't the second order induction axiom that causes categoricity, it's the restriction in the metatheory to only look at full models. –  Carl Mummert Feb 21 at 4:12

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.