13
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ Completeness theorem. $\endgroup$
    – Asaf Karagila
    May 6, 2012 at 13:45

1 Answer 1

16
$\begingroup$

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
$\endgroup$
16
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 21, 2014 at 4:12
  • $\begingroup$ @CarlMummert So if I allow Heniken semantics for second order logic then PA2 wouldn't be categorical any more? $\endgroup$ Oct 1, 2014 at 19:05
  • $\begingroup$ Yes, exactly. The thing that makes it categorical is not so much the theory as the declaration that we will only consider full models - although the theory helps via the induction axiom. The theory PA2 (which often goes by the name $Z_2$) has many nonstandard Henkin models. @Trismegistos $\endgroup$ Oct 1, 2014 at 19:08
  • $\begingroup$ @CarlMummert Are $Z_2$ nonstandard models equally exotic as PA1 models? Are they of different cardinality than natural numbers? $\endgroup$ Oct 1, 2014 at 19:20
  • $\begingroup$ Yes; the usual Lowenheim-Skolem theorem applies. There are models of every infinite cardinality. Actually, there are no countable full models, since the powerset of the integers in a full model will be uncountable. But in fact for any infinite cardinalities $a,b$ with $a \leq b$ there is a Henkin model of $Z_2$ whose numbers have cardinality $a$ and whose collection of sets has cardinality $b$. @Trismegistos $\endgroup$ Oct 1, 2014 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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