Editing Second-order logic (section)

==Non-reducibility to first-order logic==

One might attempt to reduce the second-order theory of the real numbers, with full second-order semantics, to the first-order theory in the following way. First expand the domain from the set of all real numbers to a two-sorted domain, with the second sort containing all ''sets of'' real numbers. Add a new binary predicate to the language: the membership relation. Then sentences that were second-order become first-order, with the formerly second-order quantifiers ranging over the second sort instead. This reduction can be attempted in a one-sorted theory by adding unary predicates that tell whether an element is a number or a set, and taking the domain to be the union of the set of real numbers and the [[power set]] of the real numbers.

But notice that the domain was asserted to include ''all'' sets of real numbers. That requirement cannot be reduced to a first-order sentence, as the [[Löwenheim–Skolem theorem]] shows. That theorem implies that there is some [[countably infinite]] subset of the real numbers, whose members we will call ''internal numbers'', and some countably infinite collection of sets of internal numbers, whose members we will call "internal sets", such that the domain consisting of internal numbers and internal sets satisfies exactly the same first-order sentences as are satisfied by the domain of real numbers and sets of real numbers. In particular, it satisfies a sort of least-upper-bound axiom that says, in effect:

{{block indent|Every nonempty ''internal'' set that has an ''internal'' upper bound has a least ''internal'' upper bound.}}

Countability of the set of all internal numbers (in conjunction with the fact that those form a densely ordered set) implies that that set does not satisfy the full least-upper-bound axiom. Countability of the set of all ''internal'' sets implies that it is not the set of ''all'' subsets of the set of all ''internal'' numbers (since [[Cantor's theorem]] implies that the set of all subsets of a countably infinite set is an uncountably infinite set). This construction is closely related to [[Skolem's paradox]].

Thus the first-order theory of real numbers and sets of real numbers has many models, some of which are countable. The second-order theory of the real numbers has only one model, however.
This follows from the classical theorem that there is only one [[Archimedean property|Archimedean]] [[real number|complete ordered field]], along with the fact that all the axioms of an Archimedean complete ordered field are expressible in second-order logic. This shows that the second-order theory of the real numbers cannot be reduced to a first-order theory, in the sense that the second-order theory of the real numbers has only one model but the corresponding first-order theory has many models.

There are more extreme examples showing that second-order logic with standard semantics is more expressive than first-order logic. There is a finite second-order theory whose only model is the real numbers if the [[continuum hypothesis]] holds and that has no model if the continuum hypothesis does not hold.{{sfn|Shapiro|2000|p=105}} This theory consists of a finite theory characterizing the real numbers as a complete Archimedean ordered field plus an axiom saying that the domain is of the first uncountable cardinality. This example illustrates that the question of whether a sentence in second-order logic is consistent is extremely subtle.

Additional limitations of second-order logic are described in the next section.