Second-order and Higher-order Logic

First published Thu Aug 1, 2019

Second-order logic has a subtle role in the philosophy of mathematics. It is stronger than first order logic in that it incorporates “for all properties” into the syntax, while first order logic can only say “for all elements”. At the same time it is arguably weaker than set theory in that its quantifiers range over one limited domain at a time, while set theory has the universalist approach in that its quantifiers range over all possible domains. This stronger-than-first-order-logic/weaker-than-set-theory duality is the source of lively debate, not least because set theory is usually construed as based on first order logic. How can second-order logic be at the same time stronger and weaker? To make the situation even more complex, it was suggested early on that in order that the strength of second-order logic can be exploited to its full extent and in order that “for all properties” can be given an exact interpretation, a first order set-theoretical background has to be assumed. This seemed to undermine the claimed strength of second-order logic as well as its role as the primary foundation of mathematics. It also seemed to attach second-order logic to aspects of set theory which second-order logic might have wanted to bypass: the higher infinite, the independence results, and the difficulties in finding new convincing axioms. Setting aside philosophical questions, it is undeniable and manifested by a continued stream of interesting results, that second-order logic is part and parcel of a logician’s toolbox.

• 1. Introduction

• 2. The Syntax of Second-Order Logic

• 3. The Semantics of Second-Order Logic

  • 3.1 The Ehrenfeucht-Fraïssé game of second-order logic

• 4. Properties of Second-Order Formulas

• 5. The Infamous Power of Second-Order Logic

  • 5.1 Putting distance between second- and first- order logic

  • 5.2 The collapse of the Completeness Theorem

  • 5.3 “Set theory in sheep’s clothing”

  • 5.4 Does second-order logic depend on the Axiom of Choice?

• 6. Non-Absoluteness of Truth in Second-Order Logic

• 7. Model Theory of Second-Order Logic

  • 7.1 Second-order characterizable structures

  • 7.2 Second-order logic and large cardinals

  • 7.3 The model theory of general and Henkin models

• 8. Decidability Results

• 9. Axioms of Second-Order Logic

  • 9.1 General models and Henkin models

  • 9.2 Axioms of infinity

• 10. Categoricity

• 11. Logics Between First and Second Order

• 12. Higher Order Logic vis-à-vis Type Theory

• 13. Foundations of Mathematics

• 14. Second-Order Arithmetic

• 15. Second-Order Set Theory

• 16. Finite Model Theory

• Bibliography

• Academic Tools

• Other Internet Resources

• Related Entries