Is Set Theory Reducible to Second-Order Logic?

Set theory and second-order logic are both foundational frameworks in mathematics that offer distinct approaches to organizing and understanding the structure of mathematical objects. While they share common ground, it is a matter of debate whether set theory can be fully reduced to second-order logic. This article will explore the relationship between these two frameworks, focusing on the cumulative hierarchy and the differences in their axiomatic systems.

The Cumulative Hierarchy and Set Theory

The cumulative hierarchy is a fundamental concept in set theory, which describes a process of building sets through a transfinite sequence of stages. Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC) is a common axiomatization of this theory, but it does not explicitly define the cumulative hierarchy. Instead, the hierarchy is a construct defined through a series of axioms that establish the existence and properties of sets.

Second-order logic, on the other hand, allows for the quantification over both individual elements and sets of elements, which can provide a more expressive framework for formalizing mathematical concepts. One can provide categorical second-order axiomatizations of significant portions of the cumulative hierarchy. For example, second-order Peano axioms can be used to characterize the natural numbers, and second-order axioms can ensure that a model contains elements corresponding to all sets of natural numbers.

Second-Order Axiomatizations in the Cumulative Hierarchy

Countable sets of first-order axioms that have a model will only have countable models, which do not include all sets of natural numbers. In contrast, second-order axioms can guarantee the inclusion of all such sets. In fact, second-order axioms can be formulated to assert that the model is Valpha; for some ordinal alpha;, where Valpha; is the sets of rank at most alpha;. If alpha; is a large enough ordinal, Valpha; will include sets representing all typical mathematical objects. This reflects the fact that the cumulative hierarchy contains all ordinals.

Second-order truths of Valpha; for a given ordinal alpha; become first-order truths of Vbeta; when alpha; is a designated constant and beta; is a larger ordinal. The subsets of Valpha; are the same as the sets of rank less than or equal to alpha;, which can be discussed in the context of first-order logic. Extensions of n-ary predicates on Valpha; can be encoded as subsets of Valpha;, provided that alpha; is a limit ordinal.

Consistency and Completeness

It is possible to have complete second-order axioms for the cumulative hierarchy, such as the axioms for Valpha; where alpha; is the first inaccessible cardinal. However, if such an inaccessible cardinal does not exist, these axioms would be axioms for the universe and consistent only in the sense of having a proper-class model. This scenario is not particularly plausible, given the current state of consistency results in set theory.

While it is not immediately clear whether any second-order axioms satisfied by the whole universe would also be satisfied by Valpha; for some ordinals alpha;, there is a reasonable belief that this is possible. Any second-order truth in the universe would need to be true for some ordinal alpha; in the hierarchy. However, if a finite set of second-order axioms were sufficient, this would lead to a contradiction since Valpha; for the smallest such alpha; would have no definable proper class of ordinals that satisfy the same second-order truth, making it different from the universe.

Conclusion

While there are strong connections between set theory and second-order logic, it is not clear whether set theory can be fully reduced to second-order logic. The cumulative hierarchy, which is central to set theory, contains all ordinals, whereas second-order logic might need to rely on the existence of inaccessible cardinals or proper-class models. Although there are second-order axiomatizations that can characterize significant portions of the cumulative hierarchy, the consistency and completeness of these axioms remain open questions.