6

Wikipedia on [2nd order-logic] states:

Predicate logic was primarily introduced to the mathematical community by C. S. Peirce, who coined the term second-order logic and whose notation is most similar to the modern form.

However, today most students of logic are more familiar with the works of Frege...

Frege used different variables to distinguish quantification over objects from quantification over properties and sets; but he did not see himself as doing two different kinds of logic.

After the discovery of Russell's paradox it was realized that something was wrong with his system. Eventually logicians found that restricting Frege's logic in various ways—to what is now called first-order logic—eliminated this problem: sets and properties cannot be quantified over in first-order-logic alone...

It was found that set theory could be formulated as an axiomatized system within the apparatus of first-order logic (at the cost of several kinds of completeness, but nothing so bad as Russell's paradox), and this was done (see Zermelo-Fraenkel set theory).

What were these notions of completeness that had to be abandoned in order to fit ZFC within the framework of first-order logic?

2

Frege's logic was really second-order logic (and more ...).

The restriction needed to avoid Paradoxes (Russell's one) is not to avoid 2nd-order and adopt 1st-order, but to the axioms you want to use. The culprits are :

"naive" Comprehension - Cantor

Basic Law V - Frege

Restrictions are necessary both if you formulate e.g. ZFC in first- or in second-order logic (other aspects are relevant also ..).

First-order is "simpler" and has some nice properties, like completeness of the standard deductive calculus (or proof systems) : see Godel Completeness Theorem. This is not longer true in second-order logic.

This applies also to ZFC.

But all formalized theory sufficently "strong" (and this concept of strong is precise and formal, and it is very ... weak) in term of expressive power are subject to Godel Incompletenss Theorem, that applies to Peano Arithmetic and ZFC as well, both to their version with first- and second-order logic.

  • I don't understand how this answers the question, namely, which "several kinds of completeness" are meant in the WP-entry (i.e. beside deductive completeness)? – DBK Feb 6 '14 at 12:50
  • I'm not the author of Wikepedia article; so I'm not responsible of the statement cited by the OP. I think that he may refer to the "dissatisfying" carachteristic of f-o logic, like Lowenheim-Skolem theorem and the so called Skolem's paradox and the absence of categoricity of several importannt f-o theory. I think that the "historical phantasy" about Peirce and Frege is mistaken and that the rstriction imposed to set theory in order to avoid paradoxes are not connected with f-o or second-order. Those, for me, are enough errors to address in a single post. – Mauro ALLEGRANZA Feb 6 '14 at 13:16
  • It may be the author of the article may be referring to completeness in a general manner. It would have been nice had been a little more specific. – Mozibur Ullah Feb 17 '14 at 15:00
1

What were these notions of completeness that had to be abandoned in order to fit ZFC within the framework of first-order logic?

Second-order logic (SOL) quantifies over predicates or relations including functions. SOL cannot be reduced to FOL, according to current set theory, because FOL addresses at most a countably infinite set. By the theorem of Skolem there is a countable model that satisfies precisely the same first-order sentences about real numbers and sets of real numbers as the real set R of real numbers. In the countable model there cannot be all uncountably many subsets of N or R and the least upper bound property cannot be satisfied for every bounded subset of R. So, if the real numbers are uncountable, then there must be many FOL models of R. In SOL, however, there is merely one model (up to isomorphism).

SOL has a main disadvantage however. According to a result of Gödel's SOL does not admit a complete proof theory. So SOL is not logic, properly speaking. Quine calls it "set theory in sheep's clothing".

  • Note that the claims of this post are only true relative to "full semantics", which insists on a certain compatibility between set-theoretic notions and how the notions of higher order logic are interpreted. – Hurkyl Jul 23 '17 at 17:32

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.