1 Introduction↩︎

By a language of a structure we mean its set of function, relation, and constant symbols. The language of arithmetic is \(\{+,\times\}\).

Let \({\mathbb{N}}\) be the set of natural numbers. All computable and computably enumerable sets of natural numbers are first-orderdefinable¹ in the standard model \(({\mathbb{N}},+,\times)\). 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-orderones, which opened the door to an interpretation of the syntax of first-orderlogic in arithmetic(arithmetization). Under this interpretation, each first-orderarithmeticformula \(\varphi\) is assigned a code, its Gödel number, \(\left\ulcorner\varphi\right\urcorner\). It can be shown that for each natural number\(n\), the set \({\rm 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 [1].

Soon after Gödel results, Skolem’s construction of an elementary extension of the standard model exposed a weakness of first-orderlogic by showing that the standard model of arithmetic is not uniquely determined by its first-ordertheory. Almost at the same time, Tarski proved a general result on formal theories from which it follows that the “full truth" \({\rm Tr}=\bigcup_{n\in {\mathbb{N}}}{\rm 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 structureis 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 structureexplicitly. What is also implicitly given is the set of all first-orderdefinable subsets of all finite Cartesian powers of the domain. To know a structureis 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. First-order 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-orderlogic. The set Tr is the union of countably many definable sets. Moreover, while the quantifier complexity of the sets \({\rm 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-orderlogic does not see.

Truth becomes logically visible in an extension of first-orderlogic known as \(L_{\omega_1,\omega}\). In \(L_{\omega_1,\omega}\), in addition to all first-orderoperations, we can form conjunctions and disjunctions of arbitrary countablesequences of formulas, as long as the free variables of all formulas in the sequence are contained in a finite set. This extends definability to countableintersections and countableunions 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 [2] and Gonzalo Reyes [3].

The Kueker-Reyes theorem is a strengthening of an earlier result of Dana Scott [4]. Scott proved that every relation on the domain of a countablestructure is fixed setwise by every automorphismif and only if has an \(L_{\omega_1,\omega}\) definition without parameters. In particular, in every rigid countablestructure every element of the domain has an \(L_{\omega_1,\omega}\) definition, and it follows form the Kueker-Reyes theorem that in every countable structures with fewer than \(2^{\aleph_0}\)automorphisms, every relation has an \(L_{\omega_1,\omega}\) definition, possibly with parameters.

One direction of Kueker, Reyes, and Scott’s results is obvious. Parametrically definable sets are setwise fixed by automorphismthat fix all parameters in their definitions. This applies not only to first-orderlogic and \(L_{\omega_1,\omega}\), 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 structurehas uncountably many automorphic images, I will call it absolutely undefinable.

Let \(S\) be the successor relation on \({\mathbb{N}}\). In the sequence \(({\mathbb{N}},S)\), \(({\mathbb{N}},<)\), \(({\mathbb{N}},+)\), \(({\mathbb{N}},+,\times)\), \(({\mathbb{N}},+,\times, {\rm Tr})\), each structureis 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 are \(L_{\omega_1,\omega}\)-definable in \(({\mathbb{N}},S)\) by simple formulas that correspond to the first-order recursive definitions. 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 definability of linear orderings in elementary extensions of \(({\mathbb{N}},S)\). This will be followed by a number of absolute undefinability results about expansions of countablemodels of Presburger arithmeticand expansions of countableresplendentmodels of PAto axiomatic fragments of the first-ordertheory of \(({\mathbb{N}},+,\times, {\rm Tr})\).

²

1.1 Resplendence↩︎

For a structure\({\mathfrak A}\), \(\mathop{\mathrm{Th}}({\mathfrak A})\) is the complete first-ordertheory of \({\mathfrak A}\). A structure\({\mathfrak A}\) is resplendent if for all for all tuples \(\bar a\) in the domain of \({\mathfrak A}\) and all sentences \(\varphi(R,\bar a)\) in the language of \({\mathfrak A}\) with an extra relation symbol \(R\), if some model of \(\mathop{\mathrm{Th}}({\mathfrak A},\bar a)\) is expandable to a model of \(\varphi(R,\bar a)\), then already \({\mathfrak A}\) is expandable to model of \(\varphi(R,\bar a)\).

Definition of resplendence does not require any assumptions about the language, but the results that we will discuss do. From now on the will assume that the language (signature) of each structureis finite.

By a theorem proved by Barwise and Schlipf, and independently by Ressayre, a countablestructureis resplendent if and only if it is recursively saturated. Every countablestructurehas a countableresplendent elementary extension. Moreover, countableresplendentmodels can be characterized by the following stronger property: Let \({\mathfrak A}\) be a countableresplendent structure, let \({\mathcal{L}}\) be the language of \({\mathfrak A}\), and let \(T\) be a computably axiomatized theory in a language \({\mathcal{L}}'\supseteq {\mathcal{L}}\cup\{\bar a\}\), for \(\bar a\) in the domain of \({\mathfrak A}\). If some model of \(\mathop{\mathrm{Th}}({\mathfrak A},\bar a)\) is expandable to a model of \(T\), then \({\mathfrak A}\) has an expansion to a resplendentmodel of \(T\). This property is called chronic resplendence.

We will say that an expansion of a structure\({\mathfrak A}\) is (parametrically) definable if all new functions, relations, and constants are (parametrically) definable in \({\mathfrak A}\). If an elementary extensionof a structure\({\mathfrak A}\) has a (parametrically) definable expansion to a model of \(\varphi(R,\bar a)\), then \({\mathfrak A}\) has such an expansion.

For a brief introduction to resplendent models see [5], and for a full discussion of the role of resplendence in models of arithmeticsee [6] and [1]. For us, the following result of Schlipf [7] is crucial.

Suppose that \(T\) is a computably axiomatizable theory in the language of a countableresplendentstructure\({\mathfrak A}\) with an additional relation symbol, \(T\) is consistent with \(\mathop{\mathrm{Th}}({\mathfrak A})\) and \({\mathfrak A}\) has has an expansion to a model of \(T\) that is not parametrically definable. Then, by chronic resplendence, \({\mathfrak A}\) has a resplendentexpansion \(({\mathfrak A},R)\) to a model of \(T\) that is not parametrically definable. It follows from Schlipf’s theorem that each such \(R\) is absolutely undefinable in \({\mathfrak A}\). This shows that absolute undefinability is hard to avoid. If a countableresplendent model has expansions to a model of \(T\) that are not parametrically definable, then among those expansions there have to be absolutely undefinable ones.

A classification of countablemodels of \(\mathop{\mathrm{Th}}({\mathbb{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 \(\varphi(I)\) be the sentence \[[\forall y\lnot S(y,x)\Longrightarrow I(x)]\land [\forall x,y (I(x)\land S(x,y))\Longrightarrow I(y)]\land \exists x\lnot I(x).\] Clearly, \(({\mathbb{N}},S)\) is not expandable to a model of \(\varphi(I)\), but every elementary extensionof \(({\mathbb{N}},S)\) is. This shows that \(({\mathbb{N}},S)\) is not resplendent. Because \(({\mathbb{N}},S)\) satisfies the induction schema, no expansion of a model of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\)to a model of \(\varphi(I)\) can be parametrically definable, but we will see that some such expansions are \(L_{\omega_1,\omega}\)-definable with parameters; hence they are not absolutely undefinable. By Schlipf’s theorem, \(({\mathbb{N}},S)\) has an elementary extensionto a countableresplendentmodel which has an absolutely undefinable expansion to a model of \(\varphi(I)\). We will see that \(\mathop{\mathrm{Th}}({\mathbb{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 countableresplendentmodels of PA. Similar results were obtained independently by Athanassios Tzouvaras [8]. Tzouvaras uses the real/imaginary terminology introduced by Čuda and Vopěnka in the context of Alternative Set Theory [9]. If \({\mathfrak M}\) is a countable resplendentmodel a relation \(R\) on \({\mathfrak 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 countableresplendentmodels of PAare imaginary. This was also shown independently by another proof in [10]. Both proofs are short, but they use nontrivial results about models of PA: Tzouvaras uses Ehrenfeucht’s Lemma, the authors of [10] use Kotlarski’s Moving Gaps Lemma.

2 The successor relation↩︎

There is hardly a simpler structurethan \(({\mathbb{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-orderlogic cannot? Our understanding of \(({\mathbb{N}},S)\) includes the fact that every natural numbercan be reached from 0 by a finite number of successor steps. It is this finiteness that first-ordercannot handle. For each \(n\), the formula \[\varphi_n(x,y)=\exists x_1\exists x_2 \cdots \exists x_n[x_1=x\land S(x_1,x_2)\land \cdots \land x_n=y]\] defines the relation \(x+n=y\) in \(({\mathbb{N}},S)\). However, there is no first-orderformula that defines \(x+z=y\). There is no first-orderway to say “repeat …\(z\)-times." How do we know this? A proof will be given below.

A structureis pointwisedefinable if each element of its domain has a first-orderdefinition. In \(({\mathbb{N}},S)\), the formula \(\sigma_0(x)=\forall y \lnot S(y,x)\) defines 0, and for each \(n>0\), \(\sigma_n(x)=\varphi_n(0,x)\) defines \(n\); hence \(({\mathbb{N}},S)\) is pointwisedefinable, and it follows that every model of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\)has an elementary submodel which is isomorphic to \(({\mathbb{N}},S)\). We will identify this submodel with \(({\mathbb{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 \(({\mathbb{N}},S)\). The formulas \(\varphi_n(x,y)\) and \(\sigma_n(x)\) are fixed for the rest of the article.

Because in \(({\mathbb{N}},S)\) every element other than 0 has a successor and a predecessor, it follows that every nonstandard element \(c\) in an elementary extensionof \(({\mathbb{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 \({\mathbb{Z}}\)-chain of \(c\).

By the compactness theorem, there is a model of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\)with at least two \({\mathbb{Z}}\)-chains. Let \((M,S)\) be such a model. We will use \((M,S)\) to show that no linear ordering is parametrically definablein \(({\mathbb{N}},S)\). Because \(({\mathbb{N}},S)\) is pointwisedefinable, it is enough to consider formulas without parameters. To get a contradiction, suppose \(\varphi(x,y)\) defines a linear ordering of \({\mathbb{N}}\). Then \(\varphi(x,y)\) also defines a linear ordering \(\prec\) in \((M,S)\). Let \([c]\) and \([d]\) be distinct \({\mathbb{Z}}\)-chains in \(M\) with \(c\prec d\), and let \(f(c+n)=d+n\) and \(f(d+n)=c+n\), for all \(n\in {\mathbb{Z}}\), and \(f(x)=x\) for all other \(x\) in \(M\). Then \(f\) is an automorphismof \((M,S)\), and \(f(d)\prec f(c)\), which shows that \(\prec\) cannot be definable in \((M,S)\) giving us a contradiction. In particular, the usual ordering \(<\) is not definable in \(({\mathbb{N}},S)\). Because \(S\) is definable in \(({\mathbb{N}},<)\), it follows that \(({\mathbb{N}},<)\) is a proper expansion of \(({\mathbb{N}},S)\).

In every pointwisedefinable model every relation has a parameter-free \(L_{\omega_1,\omega}\) definition. It is just the elementary diagram of the relation coded by a single \(L_{\omega_1,\omega}\) sentence. For example, the ordering of \({\mathbb{N}}\) is defined by \(\bigvee\{\sigma_m(x)\land\sigma_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 \(\bigvee_{n>0} \varphi_n(x,y)\).

Using Ehrenfeucht-Fraïssé game characterization of first-order elementary equivalence, it can be shown that the extension of \(({\mathbb{N}},S)\) by any number of \({\mathbb{Z}}\)-chains is a model of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\) (see [11]). Any two models with the same number of \({\mathbb{Z}}\)-chains are isomorphic, so up to isomorphism there are exactly \(\aleph_0\) countablemodels of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\). Except for the standard model, none of those models is rigid. Each automorphismof a nonstandard model of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\)is a composition of a permutation of the \({\mathbb{Z}}\)-chains and an automorphismwhich for each chain either fixes it pointwiseor shifts its elements either up or down. It follows that automorphism groups of models with finitely many \({\mathbb{Z}}\)-chains are countable, and the automorphism groupof the model with \(\aleph_0\) chains is of power \(2^{\aleph_0}\). Each model of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\)can be expanded by a linear ordering that is compatible with the successor relation.We can first order the \({\mathbb{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_{\omega_1,\omega}\) definitions with parameters. Such definitions can be obtained by choosing one parameter from each \({\mathbb{Z}}\)-chain, deciding how they are ordered, and then defining the ordering of each \({\mathbb{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 \({\mathbb{Z}}\)-chains, it is not hard to see that each ordering compatible with the successor relation has \(2^{\aleph_0}\)automorphic images; hence it is absolutely undefinable.

Resplendent models of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\) have infinitely many \({\mathbb{Z}}\)-chains. For example, if \((M,S)\) has only one \({\mathbb{Z}}\)-chain, let \(a\) be any element of the chain and consider the following theory \(T\) with a unary relation symbol \(A\): \[\{\exists! x A(x)\land [\forall x [A(x)\Longrightarrow[\lnot \sigma_n(x)\land \lnot \varphi_n(a,x)\land \lnot \varphi_n(x,a)]: n\in {\mathbb{N}}\}.\] By the compactness theorem, \((M,S,a)\) has an elementary extension that is expandable to a model of \(T\). Because \((M,S)\) has no such expansion; hence it is not resplendent. This argument can be generalized to models with finite numbers of \({\mathbb{Z}}\)-chains. Hence, up to isomorphism, there is only one countableresplendentmodel of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\).

3 The ordering and the additive structure↩︎

The discussion from the previous section shows that the nonstandard part of each model \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\)is the union of its \({\mathbb{Z}}\)-chains. The set of \({\mathbb{Z}}\)-chains of a model of \(\mathop{\mathrm{Th}}({\mathbb{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 \(({\mathbb{N}},<)\) and the ordered set of \({\mathbb{Z}}\)-chains which is isomorphic to \((I,<)\) is a model of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\). Because there are \(2^{\aleph_0}\)nonisomorphic countablelinearly ordered sets, it follows that \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\)has \(2^{\aleph_0}\)nonisomorphic countablemodels.

We will now show that addition is not definable in \(({\mathbb{N}},<)\). We will prove a stronger fact: \(({\mathbb{N}},<)\) is minimal, i.e., every subset of \({\mathbb{N}}\) definable in \(({\mathbb{N}},<)\) is either finite or cofinite.³ To get a contradiction suppose that the set defined in \(({\mathbb{N}},<)\) by \(\varphi(x)\) is neither finite nor cofinite. Then⁴ \[({\mathbb{N}},<)\models \forall x \exists y \exists z[x<y\land S(y,z)\land \varphi(y)\land \lnot\varphi(z)].\eqno{(*)}\] Let \((M,<)\) be an elementary extensionof \(({\mathbb{N}},<)\). Then by \((*)\) there must be nonstandard \(c\) and \(d\) such that \[(M,<)\models S(c,d)\land \varphi(c)\land\lnot\varphi(d).\] Let \(f(x)\) be the successor of \(x\) for all \(x\) in the \({\mathbb{Z}}\)-chain \([c]\), and let \(f(x)=x\) for all other \(x\). Then \(f\) is an automorphismof \((M,<)\), and \(f(c)=d\), which contradicts the fact that \((M,<)\models \varphi(c)\land \lnot\varphi(d)\) and finishes the proof.

\(({\mathbb{N}},+)\) is not minimal. For example, the formula \(\exists y [x=y+y]\) defines the set of even numbers. It follows that addition is not definable in \(({\mathbb{N}},<)\). Because the usual ordering of the natural numbers is definable in \(({\mathbb{N}},+)\), it follows that \(({\mathbb{N}},+)\) is a proper expansion of \(({\mathbb{N}},<)\).

We will denote \(\mathop{\mathrm{Th}}({\mathbb{N}},+)\) by Pr(Presburger Arithmetic). In the previous section we saw that every model of \(\mathop{\mathrm{Th}}({\mathbb{N}},S)\)is expandable to a model of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\). Now we will briefly discuss expandability of models of \(\mathop{\mathrm{Th}}({\mathbb{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-ordersentence. Hence, every \({\mathbb{Z}}\)-chain of a model of Prcan 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 Prthere is no smallest and no largest \({\mathbb{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 \({\mathbb{Z}}\)-chains in any countablenonstandard model of Pris isomorphic to the ordered set of rational numbers; hence, up to isomorphism, there is only one countablemodel \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\)which is expandable to a model of Pr. At this point, model theory becomes harder. It can be shown that there are \(2^{\aleph_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 countableresplendentmodel of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\). It is the model whose ordered set of \({\mathbb{Z}}\)-chain is isomorphicto the ordered set of rational numbers, so a countablemodel of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\)is expandable to a model Prif 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^{\aleph_0}\)isomorphismtypes of countablemodels of Pr, it follows that the countableresplendentmodel of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\)can be expanded to a model of Prin \(2^{\aleph_0}\)nonisomorphic ways.

To expand a model \((M,<)\) of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\)to a model of Prwhose addition is compatible with the ordering, we need a function \(f:M^2\longrightarrow M\) such that \((M,f)\models {\sf Pr}\) and \[(M,<,f)\models \forall x,y[(\lnot(x=y)\land \exists z f(x,z)=y))\Longleftrightarrow\;x<y].\] The required property of the expansion is no longer a single sentence, but an infinite theory. By a theorem of Presburger, Pris computably axiomatized; hence resplendence can still be applied. Let \({\mathfrak M}\) be the countableresplendentmodel of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\). It follows from Schlipf’s theorem that \({\mathfrak 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 \({\mathfrak M}\) to a model of Pris absolutely undefinable (unpublished).

While there are no nonstandard rigid models of \(\mathop{\mathrm{Th}}({\mathbb{N}},<)\), there are countablenonstandard rigid models of Pr, but they are rare. For a full discussion see [12].

3.1 Membership and inclusion↩︎

The relationship between the addition and the ordering of models of Pris similar to that of the relations membership and inclusion of models of set theories. In [13] and a follow-up paper [14], Joel David Hamkins and Makoto Kikuchi showed that the membership relation is not definable in inclusion reducts \((M,\subseteq^M)\) of models \((M,\in^M)\) of ZFCand other set theories. Moreover, if \((M,\in^M)\) is a countablemodel of ZFC, then \((M,\subseteq^M)\) is \(\omega\)-saturated—hence it is resplendent—and up to isomorphism there is only one such reduct. Zachiri McKenzie noticed that using the results of Hamkins and Kikuchi one can show that in each inclusion reduct of a countablemodel of ZFC, \(\in^M\) is absolutely undefinable.

4 The multiplicative structure↩︎

A theorem of Ginsburg and Spanier says that the subsets of \({\mathbb{N}}\) which are definable in \(({\mathbb{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\in X\) if and only if \(x+p\in X\) [15]. The set of squares is not ultimately periodic, but it is definable in \(({\mathbb{N}},\times)\); hence multiplication is not definable in \(({\mathbb{N}},+)\). In the other direction, addition is not definable in \(({\mathbb{N}},\times)\). There are many arguments which can be used to show this. A short one uses the fact that \(({\mathbb{N}},\times)\) admits lots and lots of automorphisms. Every permutation \(\alpha\) of the set prime numbers can be extended to an automorphism\(f\) of \(({\mathbb{N}},\times)\) defined for each product of prime numbers by \(f(\Pi_{i<n}p_i^{k_i})=\Pi_{i<n}\alpha(p_i)^{k_i}\). This shows that even the successor relation is not definable in \(({\mathbb{N}},\times)\). Incidentally, this is the only obstacle. Addition is definable in \(({\mathbb{N}},\times, S)\). It is easy to check that the following holds for all \(x\), \(y\), and all \(z\not=0\). \[x+y=z \Longleftrightarrow(zx+1)(zy+1)=z^2(xy+1)+1.\]

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-ordertheories of \(({\mathbb{N}},S)\), \(({\mathbb{N}},<)\), and \(({\mathbb{N}},+)\) are computably axiomatized, and so is \(\mathop{\mathrm{Th}}({\mathbb{N}},\times)\), but this is more difficult to show. An axiomatizations for \(\mathop{\mathrm{Th}}({\mathbb{N}},\times)\) was first given by Patrick Cégielski in 1981.⁵

The first-order theory of \(({\mathbb{N}},+,\times)\) 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 PAas well as to its extensions, most notably to \({\sf PA}^*\), which is Peano axioms in any countablelanguage extending the language of arithmetic.

An important result in model theory of arithmeticis that if \((M,+,\times)\) is a nonstandard model of PA, then \(({\mathfrak M},+)\) is a model of Pr, \((M,\times)\) is a model of \(\mathop{\mathrm{Th}}({\mathbb{N}},\times)\), and both \((M,+)\) and \((M,\times)\) are recursively saturated; hence, if \(M\) is countable, then both resducts are resplendent. Moreover, if \((M,+,\times)\) and \((N,+,\times)\) are countablenonstandard models of PA, then \((M,+)\) and \((N,+)\) are isomorphicif and only if \((M,\times)\) and \((N,\times)\) are. For a discussion of these results and a proof that the equivalence above no longer holds in the uncountablecase see [17].

Every countableresplendentmodel of Prcan be expanded to \(2^{\aleph_0}\)nonisomorphicmodels of PA, including \(2^{\aleph_0}\)rigid models, \(2^{\aleph_0}\)resplendent models, and \(2^{\aleph_0}\)other models, and each of these expansions is absolutely undefinable. All these statements, except the last one follow from the standard results about countableresplendentmodels of Prsummarized in [1]. The last result is due to Alf Dolich and Simon Heller (unpublished). It is based on the fact that every resplendentmodel of Prhas automorphisms which move some elements to their squares. In the special case when \((M,+, \times)\) is a countableresplendentmodel of PA, it follows directly from Schlipf’s theorem that \(\times\) is absolutely undefinable in \((M,+)\), and that \(+\) is absolutely undefinable in \((M,\times)\).

5 Tarski Arithmetic↩︎

We begin this section with a general undefinability result, from which Tarski’s theorem on undefinability of truth follows.

In the corollary below we will take advantage of arithmeticcoding of finite sequences, which allows us to reduce definability with parameters to definability with only one parameter. In the formula below, \(\langle x,y\rangle\) denotes Cantor’s pairing function, and \(\left\ulcorner\varphi(x)\right\urcorner\) is the Gödel number of \(\varphi(x)\).

In the corollary, it does not matter how \(\left\ulcorner\varphi(x)\right\urcorner\) is defined, all we need is that it is an element of \(M\).

It follows from Corollary 5 that \(({\mathbb{N}},+,\times, {\rm Tr})\) is a proper expansion of \(({\mathbb{N}},+,\times)\). Let Tar(Tarski Arithmetic) be \(\mathop{\mathrm{Th}}({\mathbb{N}},+,\times, {\rm Tr})\). A routine argument using the overspill principle shows that if \(({\mathfrak M},T)\) is a nonstandard model of Tar, then \({\mathfrak M}\) is recursively saturated; hence, if \({\mathfrak M}\) is countable, then it is resplendent.

By Gödel’s incompleteness theorem, Taris not axiomatizable. In recent years, much attention was given to the study of axiomatic subtheories of Tar. See [18] 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 [19] for details. Let Sat be a binary relation symbol. We will consider the following theories in the language \({\mathcal{L}}_{\sf ar}({\rm Sat})=\{+,\times, {\rm Sat}\}\).

1. Partial satisfaction class: PA+ all sentences of the form \[\forall y[\varphi(y)\Longleftrightarrow{\rm Sat}(\left\ulcorner\varphi(x)\right\urcorner,y)].\]

2. Partial inductive satisfaction class: (1) + induction for all formulas of \({\mathcal{L}}_{\sf ar}({\rm Sat})\).

3. Full satisfaction class: Arithmetized axioms for satisfaction (but no induction). For example, the axiom of fullness: \[\forall\varphi\forall z [{\rm Form}_{\sf PA}(\varphi)\Longrightarrow({\rm Sat}(\lnot\varphi,z))\Longleftrightarrow\lnot {\rm Sat}(\varphi,z))],\] where \({\rm Form}_{\sf PA}(x)\) is an arithmeticformula representing in PAthe set of Gödel numbers of arithmeticformulas with one free variable.

4. Full inductive satisfaction class: (3) + induction for all formulas of \({\mathcal{L}}_{\sf ar}({\rm Sat})\).

By Corollary 5, no partial satisfaction class is parametrically definable.

It was shown in [20] that all partial inductive partial satisfaction classes in countableresplendentmodels of PAare 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 PAis a class if for every \(a\), \(\{x\in X: x<a\}\) is parametrically definable. It is not difficult to show that \(X\subseteq M\) is a class of a model \({\mathfrak M}\) of PAif and only if \(({\mathfrak M},X)\) is a model of bounded induction \(I\Delta_0(X)\). If \(({\mathfrak M},X)\) is a model of \({\sf PA}^*\), we call \(X\) inductive. All inductive sets are classes. Every countablemodel of PAhas classes which are not inductive, and also has inductive sets which are not parametrically definable. There are uncountablemodels of PAall of whose classes are definable (the rather classless models).

Let \({\mathfrak M}\) be a countableresplendentmodels of PA. For such models, Jim Schmerl proved that all undefinable classes of \({\mathfrak M}\) are absolutely undefinable [21]. This shows that if \(S\) is a partial inductive satisfaction class and \(({\mathfrak M},S)\models I\Delta_0(S)\), then \(S\) is absolutely undefinable. 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, \({\mathfrak M}\) has a full satisfaction class, but by a theorem of Bartosz Wcisło [22], \({\mathfrak M}\) can have a full satisfaction class that is a class only under certain assumptions about \(\mathop{\mathrm{Th}}({\mathfrak M})\). Combining several results one can show that all full satisfaction classes in countableresplendentmodels are absolutely undefinable. A direct proof of this result and a comprehensive discussion are in the recent paper [23].

References↩︎