Model theory of second order logic

Jouko Väänänen · 2025

Read Model theory of second order logic by Jouko Väänänen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01788.txt.

Introduction

Jouko Vaananen surveys model theory for second order logic in a 2025 paper. Common wisdom says no such model theory exists, and a classic text lists building one as an open problem. First order model theory thrives on what first order logic cannot express, such as finiteness or completeness of an ordering. Second order logic can express those things, so the usual engine of the field is missing.

Famous second order axiom systems for whole and real numbers are given in textbooks, yet progress in number theory did not come from second order methods, Vaananen argues. Any model theory here would be of a different kind. Readers get a conceptual map of why strength in logic can mean weakness in structure theory.

Catalog record

CREATORJouko Väänänen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01788

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Model theory of second order logic Thanks: The author would like to thank the Academy of Finland, grant no: 322795, and funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101020762). Jouko Väänänen Abstract 1 Introduction Identifying the model theory of second order logic may sound like an impossible mission. The common wisdom is that there is no such model theory. Still, the final Open Problem in Chang-Keisler [ 8 ] is: “Develop model theory of second and higher order logic”. It is clear that second order logic does not manifest model theory in the same sense as first order logic does. In fact, much of currently popular first order model theory is based on the ability to eliminate first order quantifiers in certain situations. It is much more difficult, if not impossible, to eliminate second order quantifiers in any situation. Thus, if we are to find any model theory in second order logic, it is going to be model theory of a different kind. It can be argued that first order model theory is totally based on the inability of first order logic to express things such as finiteness, well-foundedness, countability, and completeness of linear order. This inability has led to a rich structure theory which constitutes much of model theory—weakness has been turned into an asset. Second order logic does not “suffer” from such inability, and neither does it have a rich structure theory, at least as far as can be seen today. The most famous examples of second order axiomatizations are Dedekind’s axiomatization of the arithmetic of natural numbers [ 10 ] and Hilbert’s axiomatization of the arithmetic of real numbers [ 14 ] . Both are categorical axiomatizations. Have they led to a better understanding of number theory or analysis? It is typical of textbooks of mathematics to give both axiomatizations as starting points. Arguably it has been beneficial in the development of mathematics to have these axiomatizations, but the actual progress in understanding the natural numbers or the real numbers is not based on methods of second order logic. In contrast, the study of first order axiomatizations of natural numbers have led to insights such as Gödel’s Incompleteness Theorem and the Paris-Harrington Theorem. In both cases the result is directly based on properties of first order logic. What is then the use of second order model theory? As emphasised by Baldwin [ 2 ] , what is interesting is not that there is some categorical axiomatization for a structure 1 1 1 Our structures are the same as in first order model theory. but that a particular natural axiomatization is in some sense categorical. This would seem to suggest that we should study particular theories rather than second order theories in general. A special case is monadic second order logic, by which we mean the fragment of second order logic which allows second order quantification over unary predicates only. This fragment is decidable on monadic structures [ 19 ] , on the successor structure ({\mathbb{N}},s) [ 6 ] , on the full infinite binary tree [ 22 ] , on any countable ordinal (\alpha,<) and on (\omega_{1},<) [ 7 ] (but ZFC cannot decide whether the monadic second order theory of \omega_{2} is decidable [ 12 ] ). In this paper we focus on non-monadic second order logic, even though the monadic case is highly interesting on particular structures. If the structure has something like a pairing-function, the monadic case encodes the non-monadic case and no advantage arises from restricting to it. A well-known phenomenon in second order logic is the dependence on the background set theory in a way that modern model theorists usually find unsavoury. Indeed, the model theory of second order logic can be best described as set-theoretical model theory, that is, an investigation of properties of models and model classes using set-theoretical methods. Questions studied are related to definability, compactness, and cardinality. It is often thought and claimed that if we liberate second order logic from its entanglement with set theory by admitting so-called Henkin models [ 13 ] , we are squarely back in first order logic. The truth is different. Let us see in more detail why Henkin models are compared to first order logic. A Henkin model is a pair (\mathfrak{A},\mathfrak{H}) , where \mathfrak{A} is an ordinary model and \mathfrak{H} is a set of subsets of the domain A of \mathfrak{A} , relations on A and functions on A . The Comprehension Axioms are assumed to be satisfied by (\mathfrak{A},\mathfrak{H}) , meaning that at least all (second order) definable (with parameters) subsets, relations and functions are in \mathfrak{H} . In such definitions \mathfrak{H} is used as the range of second order variables. We can interpret a Henkin model (\mathfrak{A},\mathfrak{H}) as a two-sorted structure \mathfrak{B} as follows. Let us assume, for the sake of simplicity, that \mathfrak{H} consists only of (some) subsets of A . We can make (\mathfrak{A},\mathfrak{H}) a two-sorted structure in which sort 1 is reserved for elements of A and sort 2 is reserved for the subsets in \mathfrak{H} . To create appropriate connection between the two sorts, a new binary relation E is added such that aEX holds exactly when a\in A , X\in\mathfrak{H} , and a\in X . Now, indeed, second order logic over (\mathfrak{A},\mathfrak{H}) , i.e. second order logic over \mathfrak{A} with second order variables ranging over \mathfrak{H} , can be reduced to first order logic over \mathfrak{B} . But \mathfrak{B} is not just any first order structure. It has the binary predicate E which codes a lot of combinatorial data. For example, \mathfrak{H} necessarily contains all finite subsets of \mathfrak{A} because they are all definable (with parameters). Thus, if \mathfrak{A} is infinite, \mathfrak{B} is necessarily unstable. In fact, second order logic with Henkin models has a high degree of instability and is best compared to Peano arithmetic and ZFC set theory, rather than first order logic. In the light of this it should not come as a surprise that the model theory of second order logic looks at times like the model theory of set theory. Suppose a model or a model class is definable in set theory. What more do we know about it if we know that it is definable in second order logic? The most dramatic difference concerns the structure (\omega,+,\times) : Assuming large cardinals, the second order theory of (\omega,+,\times) is forcing absolute i.e. cannot be changed by forcing [ 36 ] , something that is certainly not true of set theoretic definability over this structure. Questions of first order model theory that have, at least in the light of current knowledge, no relevance in second order logic, are: • Is the theory of a given model, e.g. ({\mathbb{Q}},<) , ({\mathbb{R}},+,\times,e^{x}) or ({\mathbb{C}},+,\times) decidable? (The second order theory of a structure is (rather trivially) decidable if and only if the structure is finite.) • Is a given theory, such as dense linear order or algebraically closed fields, decidable? (A second order theory is (rather trivially) decidable if and only if there is a natural number n such that the theory has only models of size \leq n

Read the complete text