22 - Second-Order Logic

Summary

Suppose that, in addition to allowing quantifications over the elements of a domain, as in ordinary first-order logic, we allow also quantification over relations and functions on the domain. The result is called second-order logic. Almost all the major theorems we have established for first-order logic fail spectacularly for second-order logic, as is shown in the present short chapter. This chapter and those to follow generally presuppose the material in section 17.1. (They are also generally independent of each other, and the results of the present chapter will not be presupposed by later ones.)

Let us begin by recalling some of the major results we have established for first-order logic.

The compactness theorem: If every finite subset of a set of sentences has a model, the whole set has a model.

The (downward) Löwenheim—Skolem theorem: If a set of sentences has a model, it has an enumerable model.

The upward Löwenheim—Skolem theorem: If a set of sentences has an infinite model, it has a nonenumerable model.

The (abstract) Gödel completeness theorem: The set of valid sentences is semirecursive.

All of these results fail for second-order logic, which involves an extended notion of sentence, with a corresponding extension of the notion of truth of a sentence in an interpretation. In introducing these extended notions, we stress at the outset that we change neither the definition of language nor the definition of interpretation: a language is still an enumerable set of nonlogical symbols, and an interpretation of a language is still a domain together with an assignment of a denotation to each nonlogical symbol in the language.