{'fraction_non_alphanumeric': 0.04462796791868499, 'fraction_numerical': 0.005002779321845469, 'mean_word_length': 4.3058773962502634, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Undefinability and Absolute Undefinability in Arithmetic

This is a survey of results on definability and undefinability in models of arithmetic. The goal is to present a stark difference between undefinability results in the standard model and much stronger versions about expansions of nonstandard models. The key role is played by counting the number of automorphic images of subsets of countable resplendent models of Peano Arithmetic.


Introduction
By a language of a structure we mean its set of function, relation, and constant symbols. The language of arithmetic is {+, ×}.
Let N be the set of natural numbers. All computable and computably enumerable sets of natural numbers are first-order definable 1 in the standard model (N, +, ×). Beyond that there is an infinite hierarchy of definable sets whose complexity is measured by the number of alternations of quantifiers in their definitions. First-order logic is strong enough to capture all this complexity. This was first revealed in the proof of Gödel's incompleteness theorems. Gödel showed how recursive definitions can be converted to first-order ones, which opened the door to an interpretation of the syntax of first-order logic in arithmetic (arithmetization). Under this interpretation, each first-order arithmetic formula ϕ is assigned a code, its Gödel number, ϕ . It can be shown that for each natural number n, the set Tr n of Gödel numbers of sentences with at most n quantifiers which are true in the standard model is definable. The defining formulas follow Tarski's definition of truth, but still it takes an effort to write them down explicitly-especially in the case of n = 0, and to show in Peano Arithmetic (PA) that they have the required property. All the gory details are given in [Kay91,Chapter 9].
Soon after Gödel results, Skolem's construction of an elementary extension of the standard model exposed a weakness of first-order logic by showing that the standard model of arithmetic is not uniquely determined by its first-order theory. Almost at the same time, Tarski proved a general result on formal theories from which it follows that the "full truth" Tr = n∈N Tr n is not definable in the standard model. Both results were seminal for later developments in mathematical logic.
The question of definability becomes important in the case of functions and relations that may be regarded as intrinsic to the structure. In model theory, if a structure is given, then what is given are its functions, relations, and constants. It does not matter how they are given; they may be explicitly defined, but still highly complex; they may be given only by existence theorems of set theory, or they may just be assumed to exist. These sets and constants define the structure explicitly. What is also implicitly given is the set of all firstorder definable subsets of all finite Cartesian powers of the domain. To know a structure is to know its definable sets. First-order definitions reveal the complexity of the sets they define. They tell us how the definable sets are built from the basic relations, functions, and constants by means of Boolean operations, Cartesian products, and projections. Firstorder logic gives us what I call logic visibility. We see the geometry of the definable sets through the eyes of logic.
The fact that truth is undefinable is a deficiency of first-order logic. The set Tr is the union of countably many definable sets. Moreover, while the quantifier complexity of the sets Tr n increases with n, the definitions form a well-defined recursive sequence. A number is a Gödel code of a true sentence if and only if it is in one of the sets defined by these formulas, and this is an example of a perfectly clear mathematical definition. In other words, Tr is an example of an intrinsic set which first-order logic does not see.
Truth becomes logically visible in an extension of first-order logic known as L ω 1 ,ω . In L ω 1 ,ω , in addition to all first-order operations, we can form conjunctions and disjunctions of arbitrary countable sequences of formulas, as long as the free variables of all formulas in the sequence are contained in a finite set. This extends definability to countable intersections and countable unions of definable subsets of a fixed Cartesian power of the domain of a structure. The extension is radical. The following theorem was proved independently by David Kueker [Kue67] and Gonzalo Reyes [Rey67].
Theorem 1.1. Let A be a countable structure for a countable language. Then, a relation on A has a L ω 1 ,ω definition with finitely many parameters if and only if it has at most countably many images under automorphisms of A.
The Kueker-Reyes theorem is a strengthening of an earlier result of Dana Scott [Sco65]. Scott proved that every relation on the domain of a countable structure is fixed setwise by every automorphism if and only if has a L ω 1 ,ω definition without parameters. In particular, in every rigid countable structure every element of the domain has a L ω 1 ,ω definition, and it follows form the Kueker-Reyes theorem that in every countable structures with fewer than 2 ℵ 0 automorphisms, every relation has a L ω 1 ,ω definition, possibly with parameters.
One direction of Kueker, Reyes, and Scott's results is obvious. Parametrically definable sets are setwise fixed by automorphism that fix all parameters in their definitions. This applies not only to first-order logic and L ω 1 ,ω , but in fact it is a requisite for all logical formalisms. Logical properties should be preserved by isomorphisms. Thus, if a relation in a countable structure has 2 ℵ 0 automorphic images, I will call it absolutely undefinable.
Let S be the successor relation on N. In the sequence (N, S), (N, <), (N, +), (N, +, ×), (N, +, ×, Tr), each structure is richer than the previous one, for it has a new relation or function that is not definable in the previous one. This is telling us something about logic, but not that much about the nature of those functions and relations, as they all have simple natural definitions in a modest fragment of L ω 1 ,ω . In contrast, absolute undefinability theorems about expansions of nonstandard models, which we are going to discuss, reveal strong independence of the basic arithmetic functions and relations in nonstandard models. First, we will examine in detail an example of absolute undefinability of any linear ordering of an elementary extension of (N, S). This will be followed by a number of absolute undefinability results about expansions of countable models of Presburger arithmetic and expansions of countable resplendent models of PA to axiomatic fragments of the first-order theory of (N, +, ×, Tr).
Ali Enayat, Mateusz Le lyk, and Simon Heller have reviewed the draft of this paper and provided valuable comments. I also want to thank Alfred Dolich, Emil Jeřábek, Simon Heller, and Zachiri McKenzie for their observations included in sections 3 and 4. is expandable to a model of ϕ(R,ā), then already A is expandable to model of ϕ(R,ā).
Definition of resplendence does not require any assumptions about the language, but the results that we will need do. From now on the will assume that the language of each structure is finite.
By a theorem proved by Barwise and Schlipf, and independently by Ressayre, a countable structure is resplendent if and only if it is recursively saturated. Every countable structure has a countable resplendent elementary extension. Moreover, countable resplendent models can be characterized by the following stronger property: Let A be a countable resplendent structure, let L be the language of A, and let T be a computably axiomatized theory in a language L ′ ⊇ L ∪ {ā}, forā in the domain of A. If some model of Th(A) is expandable to a model of T , then A has an expansion to a resplendent model of T . This property is called chronic resplendence.
We will say that an expansion of a structure A is (parametrically) definable if all new functions, relations, and constants are (parametrically) definable in A. It is not difficult to see that if an elementary extension of a structure A has a (parametrically) definable expansion to a model of ϕ(R,ā), then A has such an expansion.
For a brief introduction to resplendent models see [Kos11], and for a full discussion of the role of resplendence in models of arithmetic see [Smo91] and [Kay91,Chapter 15]. For us, the following result of Schlipf is crucial.
Suppose that T is a computably axiomatizable theory in the language of a countable resplendent structure A with an additional relation symbol, T is consistent with Th(A) and A has no parametrically definable expansion to a model of T . Then, by chronic resplendence, A should have a resplendent expansions (A, R) to a model of T , and it follows from the theorem of Schlipf that each such R is absolutely undefinable in A. This shows that absolute undefinability is hard to avoid. If a countable resplendent model has expansions to a model of T , but none is parametrically definable, then among those expansions there have to be absolutely undefinable ones.
A classification of countable models of Th(N, S) is given in the next section. All statements about the following example will be justified there.
Let I be a unary relation symbol, and let ϕ(I) be the sentence Clearly, (N, S) is not expandable to a model of ϕ(I), but every elementary extension of (N, S) is. This shows that (N, S) is not resplendent. Because (N, S) satisfies the induction schema, no expansion of a model of Th(N, S) to a model of ϕ(I) can be parametrically definable. We will see that some such expansions are L ω 1 ,ω -definable with parameters; hence they are not absolutely undefinable. By Schlipf's theorem, (N, S) has an elementary extension to a countable resplendent model which has an absolutely undefinable expansion to a model of ϕ(I). We will see that Th(N, S) has exactly one such model.

1.2.
Real and Imaginary sets. The last section of this paper is devoted to some specific results about intrinsic but absolutely undefinable sets in countable resplendent models of PA. Similar results were obtained independently by Athanassios Tzouvaras [Tzo91]. Tzouvaras uses the real/imaginary terminology introduced byČuda and Vopěnka in the context of Alternative Set Theory [CV79]. If M is a countable resplendent model a relation R on M is real if and only if the set of automorphic images of X is countable. Thus, all imaginary relations are absolutely undefinable. Among many interesting results, Tzouvaras showed that all nontrivial automorphisms of countable resplendent models of PA are imaginary. This was also shown independently by another proof in [KKK91]. Both proofs are short, but they use nontrivial results about models of PA: Tzouvaras uses Ehrenfeucht's Lemma, the authors of [KKK91] use Kotlarski's Moving Gaps Lemma.

The successor relation
There is hardly a simpler structure than (N, S), but despite its simplicity, the addition and multiplication are uniquely determined in it and so is the set Tr. For all numbers m and n, m + 0 = m and m + (n + 1) = (m + n) + 1. It is a definition by recursion. To compute m + n we can start with m and move n successors up. Why is it that we see clearly something that the powerful first-order logic cannot? Our understanding of (N, S) includes the fact that every natural number can be reached from 0 by a finite number of successor steps. It is this finiteness that first-order cannot handle. For each n, the formula defines the relation x + n = y in (N, S). However, there is no first-order formula that defines x + z = y. There is no first-order way to say "repeat . . . z-times." How do we know this? A proof will be given below.
A structure is pointwise definable if each element of its domain has a first-order definition. In (N, S), the formula σ 0 (x) = ∀y¬S(y, x) defines 0, and for each n > 0, σ n (x) = ϕ n (0, x) defines n; hence (N, S) is pointwise definable, and it follows that every model of Th (N, S) has an elementary submodel which is isomorphic to (N, S). We will identify this submodel with (N, S) and call its elements standard; all other elements will be called nonstandard. A model is called nonstandard if it has nonstandard elements. The same terminology will be applied to models of theories of expansions of (N, S). The formulas ϕ n (x, y) and σ n (x) are fixed for the rest of the text.
Because in (N, S) every element other than 0 has a successor and a predecessor, it follows that every nonstandard element c in an elementary extension of (N, S) belongs to a chain which is isomorphic to the successor relation on the set of integers. We will denote such a chain by [c] and call it the Z-chain of c.
By the compactness theorem, there is a model of Th(N, S) with at least two Z-chains. Let (M, S) be such a model. We will use (M, S) to show that no linear ordering is parametrically definable in (N, S). Because (N, S) is pointwise definable, it is enough to consider formulas without parameters. To get a contradiction, suppose ϕ(x, y) defines a linear ordering of N. In every pointwise definable model every relation has a parameter-free L ω 1 ,ω definition. It is just the elementary diagram of the relation coded by a single L ω 1 ,ω sentence. For example, the ordering of N is defined by {σ m (x) ∧ σ n (y) : m < n}. In this case there is also a definition which ties the ordering to the successor relation in a straightforward way: x < y if and only n>0 ϕ n (x, y).
Using Ehrenfeucht-Fraïssé game characterization of elementary equivalence, it can be shown that the extension of (N, S) by any number of Z-chains is a model of Th(N, S) (see [Mar02, Section 2.4]). Any two models with the same number of Z-chains are isomorphic, so up to isomorphism there are exactly ℵ 0 countable models of Th(N, S). Except for the standard model, none of those models is rigid. Each automorphism of a nonstandard model of Th(N, S) is a composition of a permutation of the Z-chains and an automorphism which for each chain either fixes it pointwise or shifts its elements either up or down. It follows that automorphism groups of models with finitely many Z-chains are countable, and the automorphism group of the model with ℵ 0 chains is of power 2 ℵ 0 . Each model of Th(N, S) can be expanded by a linear ordering that is compatible with the successor relation.We can first order the Z-chains, and then order the elements in each chain according to the successor relation. In the case of models with finitely many chains, different orderings of the chains, give us different, but isomorphic expansions; hence, each ordering has finitely many automorphic images, and-by the Kueker-Reyes theorem-they must have L ω 1 ,ω definitions with parameters. Such definitions can be obtained by choosing one parameter from each Z-chain, deciding how they are ordered, and then defining the ordering of each Z-chain by a formula with the chosen parameters similar to the one we gave for the ordering of the standard model.
In the case of models with countably many Z-chains, it is not hard to see that each ordering compatible with the successor relation has 2 ℵ 0 automorphic images,; hence it is absolutely undefinable.
Resplendent models of Th(N, S) must have infinitely many Z-chains. For example, if (M, S) has only one Z-chain, let a be any element of the chain and consider the following theory T with a unary relation symbol A: By the compactness theorem, Th(N, S) has a model which is expandable to a model of T , hence (M, S) is not resplendent. This argument can be generalized to models with finite numbers of Z-chains. Hence, up to isomorphism, there is only one countable resplendent model of Th(N, S).

The ordering and the additive structure
The discussion from the previous section shows that the nonstandard part of each model Th(N, <) is the union of its Z-chains. The set of Z-chains of a model of Th(N, <) is linearly ordered by the ordering inherited from the model. Using Ehrenfeucht-Fraïssé games, it can be shown that for any linearly ordered set (I, <) the union of (N, <) and the ordered set of Z-chains which is isomorphic to (I, <) is a model of Th(N, <). Because there are 2 ℵ 0 nonisomorphic countable linearly ordered sets, it follows that Th(N, <) has 2 ℵ 0 nonisomorphic countable models.
We will now show that addition is not definable in (N, <). We will prove a stronger fact: (N, <) is minimal, i.e., every subset of N definable in (N, <) is either finite or cofinite. (N, +) is not minimal. For example, the formula ∃y[x = y + y] defines the set of even numbers. It follows that addition is not definable in (N, <). Because the usual ordering of the natural numbers is definable in (N, +), it follows that (N, +) is a proper expansion of (N, <).
We will denote Th(N, +) by Pr (Presburger Arithmetic). In the previous section we saw that every model of Th(N, S) is expandable to a model of Th(N, <). Now we will briefly discuss expandability of models of Th(N, <) to models of Pr.
For every natural number n, either n or n + 1 is even, and this can be expressed by a first-order sentence. Hence, every Z-chain of a model of Pr can be presented as [a] for an even a. Let a be nonstandard and even. It is easy to prove that if a = b + b, then b is nonstandard and [b], [a], and [a + a] are disjoint. It follows that in a nonstandard model of Pr there is no smallest and no largest Z-chain. If a and b are even, a < b, [a] and [b] are disjoint, and c + c = a + b, then a < c < b and [a], [c], and [b] are disjoint. This shows that the ordered set of Z-chains in any countable nonstandard model of Pr is isomorphic to the ordered set of rational numbers; hence, up to isomorphism, there is only one countable model Th (N, <) which is expandable to a model of Pr. At this point, model theory becomes harder. It can be shown that there are 2 ℵ 0 isomorphism types of such expansions, but we will not discuss the details here.
Again resplendence enters the picture. Up to isomorphism, there is only one countable resplendent model of Th (N, <). It is the model whose ordered set of Z-chain is isomorphic to the ordered set of rational numbers, so a countable model of Th(N, <) is expandable to a model Pr if an only if it is resplendent. The question now is: How many such expansions are there and are there any that are not absolutely undefinable? Because there are 2 ℵ 0 isomorphism types of countable models of Pr, it follows that the countable resplendent model of Th(N, <) can be expanded to a model of Pr in 2 ℵ 0 nonisomorphic ways.
To expand a model (M, <) of Th(N, <) to a model of Pr whose addition is compatible with the ordering, we need a function f : The required property of the expansion is no longer a single sentence, but an infinite theory. By a theorem of Presburger, Pr is computably axiomatized; hence resplendence can still be applied. Let M be the countable resplendent model of Th(N, <). It follows from the theorems of Barwise and Schlipf that M has an absolutely undefinable expansion to a model of Pr. In a response to my query Emil Jeřábek gave a short argument proving that in fact each expansion of M to a model of Pr is absolutely undefinable (unpublished).
While there are no nonstandard rigid models of Th(N, <), there are countable nonstandard rigid models of Pr, but they are rare. For a full discussion see [Jer19].

The multiplicative structure
A theorem of Ginsburg and Spanier says that the subsets of N which are definable in (N, +) are exactly the ultimately periodic ones, i.e., the sets X for which there is a p such that for sufficiently large x, x ∈ X if and only if x + p ∈ X [GS66]. The set of squares is not ultimately periodic, but it is definable in (N, ×); hence multiplication is not definable in (N, +). In the other direction, addition is not definable in (N, ×). There are many arguments which can be used to show this. A short one uses the fact that (N, ×) admits lots and lots of automorphisms. Every permutation α of the set prime numbers can be extended to an automorphism f of (N, ×) defined for each product of prime numbers by f (Π i<n p k i i ) = Π i<n α(p i ) k i . This shows that even the successor relation is not definable in (N, ×). Incidentally, this is the only obstacle. Addition is definable in (N, ×, S). It is easy to check that the following holds for all x, y, and all z = 0.
Model theory of the natural numbers becomes more difficult when addition and multiplication are joined together. What made the previous discussion easier was the fact that the first-order theories of (N, S), (N, <), and (N, +) are computably axiomatized, and so is Th(N, ×), but this is more difficult to show. A set of axioms was first given by Patrick Cégielski in 1981. 4 The theory of (N, +, ×) is not computably axiomatizable. To be able to apply model theory of resplendent structures, we need to shift to axiomatizable subtheories. We will focus on PA. Most of the results we will mention apply to fragments of PA as well as to its extensions, most notably to PA * , which is Peano axioms in any countable language extending the language of arithmetic.
An For a discussion of these results and a proof that the equivalence above no longer holds in the uncountable case see [KNS89]. Every countable resplendent model of Pr can be expanded to 2 ℵ 0 nonisomorphic models of PA, including 2 ℵ 0 rigid models, 2 ℵ 0 resplendent models, and 2 ℵ 0 other models; each of these expansions is absolutely undefinable. All these statements, except the last one follow from the standard results about countable resplendent models of Pr summarized in [Kay91,Chapter 15]. The last one result I owe to Alf Dolich and Simon Heller (unpublished). It is based on the fact that every resplendent model of Pr has automorphisms which move some elements to their squares. In the special case when (M, +, ×) is a countable resplendent model of PA, it follows directly from Schlipf's theorem that × is absolutely undefinable in (M, +), and that + is absolutely undefinable in (M, ×).

Tarski Arithmetic
We begin this section with a general undefinability result, from which Tarski's theorem on undefinability of truth follows.
Proposition 5.2. No universal set is parametrically definable.
Proof. Suppose that a parametrically definable U ⊆ M 2 is universal. Let D = {a : (a, a) In the corollary below we will take advantage of arithmetic coding of finite sequences, which allows us to reduce definability with parameters to definability with only one parameter. In the formula below x, y denotes Cantor's pairing function. In the corollary it does not matter how ϕ(x) is defined, all we need is that it is an element of M .
It follows from Corollary 5.3 that (N, +, ×, Tr) is a proper expansion of (N, +, ×). Let Tar (Tarski Arithmetic) be Th(N, +, ×, Tr). A routine argument using the overspill principle shows that if (M, T ) is a nonstandard model of Tar, then M is recursively saturated; hence, if M is countable, then it is resplendent.
By Gödel's incompleteness theorem, Tar is not axiomatizable. In recent years, much attention was given to the study of axiomatic subtheories of Tar. See [Cie17] for a comprehensive account. Originally, the results were formulated in terms of satisfaction classes (binary), as we will do below. Recently, the emphasis has shifted to truth predicates (unary). With a modicum of induction in the axiom system, satisfaction classes and truth predicates are definable from one another. In the absence of induction, the situation is more subtle, see [Cie19] for details. Let Sat be a binary relation symbol. We will consider the following theories in the language L ar (Sat) = {+, ×, Sat}.
By Corollary 5.3, no partial satisfaction class is parametrically definable. It was shown in [KK88] that all partial inductive partial satisfaction classes in countable resplendent models of PA are absolutely undefinable.This turned out to be a special case of a much more general result, for which we need a couple of definitions. A subset X of a model of PA is a class if for every a, {x ∈ X : x < a} is parametrically definable. If (M, X) is a model of PA * , we call X inductive. All inductive sets are classes. Every countable model of PA has classes which are not inductive, and inductive sets which are not parametrically definable. There are uncountable models of PA all of whose classes are definable (rather classless models).
For countable resplendent models of PA, Jim Schmerl proved an ultimate result: all undefinable classes are absolutely undefinable [KS06, Theorem 8.2.3]. If X is a class of M, then (M, X) is a model of bounded induction. In the absence of any amount of induction, the case of full satisfaction classes requires a separate treatment. By a theorem of Kotlarski, Krajewski, and Lachlan, M has a full satisfaction class, but by a theorem of Bartosz Wcis lo [WL17], M can have a full satisfaction class that is a class only under certain assumptions about Th(M). Combining several results one can show that all full satisfaction classes in countable resplendent models are absolutely undefinable. A proof and a comprehensive discussion are in the recent paper [Wci22].