# Parallels in universality between the universal algorithm and the universal finite set, Oxford Math Logic Seminar, October 2018

This will be a talk for the Logic Seminar in Oxford at the Mathematics Institute in the Andrew Wiles Building on October 9, 2018, at 4:00 pm, with tea at 3:30.

Abstract. The universal algorithm is a Turing machine program $e$ that can in principle enumerate any finite sequence of numbers, if run in the right model of PA, and furthermore, can always enumerate any desired extension of that sequence in a suitable end-extension of that model. The universal finite set is a set-theoretic analogue, a locally verifiable definition that can in principle define any finite set, in the right model of set theory, and can always define any desired finite extension of that set in a suitable top-extension of that model. Recent work has uncovered a $\Sigma_1$-definable version that works with respect to end-extensions. I shall give an account of all three results, which have a parallel form, and describe applications to the model theory of arithmetic and set theory.

Slides

# Topological models of arithmetic

• A. Enayat, J. D. Hamkins, and B. Wcisło, “Topological models of arithmetic,” ArXiv e-prints, 2018. (under review)
@ARTICLE{EnayatHamkinsWcislo2018:Topological-models-of-arithmetic,
author = {Ali Enayat and Joel David Hamkins and Bartosz Wcisło},
title = {Topological models of arithmetic},
journal = {ArXiv e-prints},
year = {2018},
volume = {},
number = {},
pages = {},
month = {},
note = {under review},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
eprint = {1808.01270},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://wp.me/p5M0LV-1LS},
}


The first author had inquired whether a nonstandard model of arithmetic could be continuously presented on the rational numbers.

Main Question. (Enayat, 2009) Are there continuous functions $\oplus$ and $\otimes$ on the rational numbers $\Q$, such that $\langle\Q,\oplus,\otimes\rangle$ is a nonstandard model of arithmetic?

By a model of arithmetic, what we mean here is a model of the first-order Peano axioms PA, although we also consider various weakenings of this theory. The theory PA asserts of a structure $\langle M,+,\cdot\rangle$ that it is the non-negative part of a discretely ordered ring, plus the induction principle for assertions in the language of arithmetic. The natural numbers $\newcommand\N{\mathbb{N}}\langle \N,+,\cdot\rangle$, for example, form what is known as the standard model of PA, but there are also many nonstandard models, including continuum many non-isomorphic countable models.

We answer the question affirmatively, and indeed, the main theorem shows that every countable model of PA is continuously presented on $\Q$. We define generally that a topological model of arithmetic is a topological space $X$ equipped with continuous functions $\oplus$ and $\otimes$, for which $\langle X,\oplus,\otimes\rangle$ satisfies the desired arithmetic theory. In such a case, we shall say that the underlying space $X$ continuously supports a model of arithmetic and that the model is continuously presented upon the space $X$.

Question. Which topological spaces support a topological model of arithmetic?

In the paper, we prove that the reals $\R$, the reals in any finite dimension $\R^n$, the long line and Cantor space do not support a topological model of arithmetic, and neither does any Suslin line. Meanwhile, there are many other spaces that do support topological models, including many uncountable subspaces of the plane $\R^2$. It remains an open question whether any uncountable Polish space, including the Baire space, can support a topological model of arithmetic.

Let me state the main theorem and briefly sketch the proof.

Main Theorem. Every countable model of PA has a continuous presentation on the rationals $\Q$.

Proof. We shall prove the theorem first for the standard model of arithmetic $\langle\N,+,\cdot\rangle$. Every school child knows that when computing integer sums and products by the usual algorithms, the final digits of the result $x+y$ or $x\cdot y$ are completely determined by the corresponding final digits of the inputs $x$ and $y$. Presented with only final segments of the input, the child can nevertheless proceed to compute the corresponding final segments of the output.

\begin{equation*}\small\begin{array}{rcr}
\end{array}\end{equation*}

This phenomenon amounts exactly to the continuity of addition and multiplication with respect to what we call the final-digits topology on $\N$, which is the topology having basic open sets $U_s$, the set of numbers whose binary representations ends with the digits $s$, for any finite binary string $s$. (One can do a similar thing with any base.) In the $U_s$ notation, we include the number that would arise by deleting initial $0$s from $s$; for example, $6\in U_{00110}$. Addition and multiplication are continuous in this topology, because if $x+y$ or $x\cdot y$ has final digits $s$, then by the school-child’s observation, this is ensured by corresponding final digits in $x$ and $y$, and so $(x,y)$ has an open neighborhood in the final-digits product space, whose image under the sum or product, respectively, is contained in $U_s$.

Let us make several elementary observations about the topology. The sets $U_s$ do indeed form the basis of a topology, because $U_s\cap U_t$ is empty, if $s$ and $t$ disagree on some digit (comparing from the right), or else it is either $U_s$ or $U_t$, depending on which sequence is longer. The topology is Hausdorff, because different numbers are distinguished by sufficiently long segments of final digits. There are no isolated points, because every basic open set $U_s$ has infinitely many elements. Every basic open set $U_s$ is clopen, since the complement of $U_s$ is the union of $U_t$, where $t$ conflicts on some digit with $s$. The topology is actually the same as the metric topology generated by the $2$-adic valuation, which assigns the distance between two numbers as $2^{-k}$, when $k$ is largest such that $2^k$ divides their difference; the set $U_s$ is an open ball in this metric, centered at the number represented by $s$. (One can also see that it is metric by the Urysohn metrization theorem, since it is a Hausdorff space with a countable clopen basis, and therefore regular.) By a theorem of Sierpinski, every countable metric space without isolated points is homeomorphic to the rational line $\Q$, and so we conclude that the final-digits topology on $\N$ is homeomorphic to $\Q$. We’ve therefore proved that the standard model of arithmetic $\N$ has a continuous presentation on $\Q$, as desired.

But let us belabor the argument somewhat, since we find it interesting to notice that the final-digits topology (or equivalently, the $2$-adic metric topology on $\N$) is precisely the order topology of a certain definable order on $\N$, what we call the final-digits order, an endless dense linear order, which is therefore order-isomorphic and thus also homeomorphic to the rational line $\Q$, as desired.

Specifically, the final-digits order on the natural numbers, pictured in figure 1, is the order induced from the lexical order on the finite binary representations, but considering the digits from right-to-left, giving higher priority in the lexical comparison to the low-value final digits of the number. To be precise, the final-digits order $n\triangleleft m$ holds, if at the first point of disagreement (from the right) in their binary representation, $n$ has $0$ and $m$ has $1$; or if there is no disagreement, because one of them is longer, then the longer number is lower, if the next digit is $0$, and higher, if it is $1$ (this is not the same as treating missing initial digits as zero). Thus, the even numbers appear as the left half of the order, since their final digit is $0$, and the odd numbers as the right half, since their final digit is $1$, and $0$ is directly in the middle; indeed, the highly even numbers, whose representations end with a lot of zeros, appear further and further to the left, while the highly odd numbers, which end with many ones, appear further and further to the right. If one does not allow initial $0$s in the binary representation of numbers, then note that zero is represented in binary by the empty sequence. It is evident that the final-digits order is an endless dense linear order on $\N$, just as the corresponding lexical order on finite binary strings is an endless dense linear order.

The basic open set $U_s$ of numbers having final digits $s$ is an open set in this order, since any number ending with $s$ is above a number with binary form $100\cdots0s$ and below a number with binary form $11\cdots 1s$ in the final-digits order; so $U_s$ is a union of intervals in the final-digits order. Conversely, every interval in the final-digits order is open in the final-digits topology, because if $n\triangleleft x\triangleleft m$, then this is determined by some final segment of the digits of $x$ (appending initial $0$s if necessary), and so there is some $U_s$ containing $x$ and contained in the interval between $n$ and $m$. Thus, the final-digits topology is the precisely same as the order topology of the final-digits order, which is a definable endless dense linear order on $\N$. Since this order is isomorphic and hence homeomorphic to the rational line $\Q$, we conclude again that $\langle \N,+,\cdot\rangle$ admits a continuous presentation on $\Q$.

We now complete the proof by considering an arbitrary countable model $M$ of PA. Let $\triangleleft^M$ be the final-digits order as defined inside $M$. Since the reasoning of the above paragraphs can be undertaken in PA, it follows that $M$ can see that its addition and multiplication are continuous with respect to the order topology of its final-digits order. Since $M$ is countable, the final-digits order of $M$ makes it a countable endless dense linear order, which by Cantor’s theorem is therefore order-isomorphic and hence homeomorphic to $\Q$. Thus, $M$ has a continuous presentation on the rational line $\Q$, as desired. $\Box$

The executive summary of the proof is: the arithmetic of the standard model $\N$ is continuous with respect to the final-digits topology, which is the same as the $2$-adic metric topology on $\N$, and this is homeomorphic to the rational line, because it is the order topology of the final-digits order, a definable endless dense linear order; applied in a nonstandard model $M$, this observation means the arithmetic of $M$ is continuous with respect to its rational line $\Q^M$, which for countable models is isomorphic to the actual rational line $\Q$, and so such an $M$ is continuously presentable upon $\Q$.

Let me mention the following order, which it seems many people expect to use instead of the final-digits order as we defined it above. With this order, one in effect takes missing initial digits of a number as $0$, which is of course quite reasonable.

The problem with this order, however, is that the order topology is not actually the final-digits topology. For example, the set of all numbers having final digits $110$ in this order has a least element, the number $6$, and so it is not open in the order topology. Worse, I claim that arithmetic is not continuous with respect to this order. For example, $1+1=2$, and $2$ has an open neighborhood consisting entirely of even numbers, but every open neighborhood of $1$ has both odd and even numbers, whose sums therefore will not all be in the selected neighborhood of $2$. Even the successor function $x\mapsto x+1$ is not continuous with respect to this order.

Finally, let me mention that a version of the main theorem also applies to the integers $\newcommand\Z{\mathbb{Z}}\Z$, using the following order.

Go to the article to read more.

• A. Enayat, J. D. Hamkins, and B. Wcisło, “Topological models of arithmetic,” ArXiv e-prints, 2018. (under review)
@ARTICLE{EnayatHamkinsWcislo2018:Topological-models-of-arithmetic,
author = {Ali Enayat and Joel David Hamkins and Bartosz Wcisło},
title = {Topological models of arithmetic},
journal = {ArXiv e-prints},
year = {2018},
volume = {},
number = {},
pages = {},
month = {},
note = {under review},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
eprint = {1808.01270},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://wp.me/p5M0LV-1LS},
}

# Paul K. Gorbow, PhD 2018, University of Gothenburg

Paul K. Gorbow successfully defended his dissertation, “Self-similarity in the foundations” on June 14, 2018 at the University of Gothenburg in the Department of Philosophy, Linguistics and Theory of Science, under the supervision of Ali Enayat, with Peter LeFanu Lumsdaine and Zachiri McKenzie serving as secondary supervisors.  The defense opponent was Roman Kossak, with a dissertation committee consisting of Jon Henrik Forssell, Joel David Hamkins (myself) and Vera Koponen, chaired by Fredrik Engström. Congratulations!

Paul K. Gorbow, “Self-similarity in the foundations,” PhD dissertation for the University of Gothenburg, Acta Philosophica Gothoburgensia 32, June 2018. (arxiv:1806.11310)

Abstract. This thesis concerns embeddings and self-embeddings of foundational structures in both set theory and category theory.

The first part of the work on models of set theory consists in establishing a refined version of Friedman’s theorem on the existence of embeddings between countable non-standard models of a fragment of ZF, and an analogue of a theorem of Gaifman to the effect that certain countable models of set theory can be elementarily end-extended to a model with many automorphisms whose sets of fixed points equal the original model. The second part of the work on set theory consists in combining these two results into a technical machinery, yielding several results about non-standard models of set theory relating such notions as self-embeddings, their sets of fixed points, strong rank-cuts, and set theories of different strengths.

The work in foundational category theory consists in the formulation of a novel algebraic set theory which is proved to be equiconsistent to New Foundations (NF), and which can be modulated to correspond to intuitionistic or classical NF, with or without atoms. A key axiom of this theory expresses that its structures have an endofunctor with natural properties.

In the Swedish style of dissertation defense, the opponent (in this case Roman Kossak) summarizes the dissertation, placing it in a broader context, and then challenges various parts of it, probing the candidate’s expertise in an extended discussion. What a pleasure it was to see this.  After this, there is a broader discussion, in which the committee is also involved.

# Different set theories are never bi-interpretable

I was fascinated recently to discover something I hadn’t realized about relative interpretability in set theory, and I’d like to share it here. Namely,

Different set theories extending ZF are never bi-interpretable!

For example, ZF and ZFC are not bi-interpretable, and neither are ZFC and ZFC+CH, nor ZFC and ZFC+$\neg$CH, despite the fact that all these theories are equiconsistent. The basic fact is that there are no nontrivial instances of bi-interpretation amongst the models of ZF set theory. This is surprising, and could even be seen as shocking, in light of the philosophical remarks one sometimes hears asserted in the philosophy of set theory that what is going on with the various set-theoretic translations from large cardinals to determinacy to inner model theory, to mention a central example, is that we can interpret between these theories and consequently it doesn’t much matter which context is taken as fundamental, since we can translate from one context to another without loss.

The bi-interpretation result shows that these interpretations do not and cannot rise to the level of bi-interpretations of theories — the most robust form of mutual relative interpretability — and consequently, the translations inevitably must involve a loss of information.

To be sure, set theorists classify the various set-theoretic principles and theories into a hierarchy, often organized by consistency strength or by other notions of interpretative power, using forcing or definable inner models. From any model of ZF, for example, we can construct a model of ZFC, and from any model of ZFC, we can construct models of ZFC+CH or ZFC+$\neg$CH and so on. From models with sufficient large cardinals we can construct models with determinacy or inner-model-theoretic fine structure and vice versa. And while we have relative consistency results and equiconsistencies and even mutual interpretations, we will have no nontrivial bi-interpretations.

(I had proved the theorem a few weeks ago in joint work with Alfredo Roque Freire, who is visiting me in New York this year. We subsequently learned, however, that this was a rediscovery of results that have evidently been proved independently by various authors. Albert Visser proves the case of PA in his paper, “Categories of theories and interpretations,” Logic in Tehran, 284–341, Lect. Notes Log., 26, Assoc. Symbol. Logic, La Jolla, CA, 2006, (pdf, see pp. 52-55). Ali Enayat gave a nice model-theoretic argument for showing specifically that ZF and ZFC are not bi-interpretable, using the fact that ZFC models can have no involutions in their automorphism groups, but ZF models can; and he proved the general version of the theorem, for ZF, second-order arithmetic $Z_2$ and second-order set theory KM in his 2016 article, A. Enayat, “Variations on a Visserian theme,” in Liber Amicorum Alberti : a tribute to Albert Visser / Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten (eds.) Pages, 99-110. ISBN, 978-1848902046. College Publications, London. The ZF version was apparently also observed independently by Harvey Friedman, Visser and Fedor Pakhomov.)

Meanwhile, let me explain our argument. Recall from model theory that one theory $S$ is interpreted in another theory $T$, if in any model of the latter theory $M\models T$, we can define (and uniformly so in any such model) a certain domain $N\subset M^k$ and relations and functions on that domain so as to make $N$ a model of $S$. For example, the theory of algebraically closed fields of characteristic zero is interpreted in the theory of real-closed fields, since in any real-closed field $R$, we can consider pairs $(a,b)$, thinking of them as $a+bi$, and define addition and multiplication on those pairs in such a way so as to construct an algebraically closed field of characteristic zero.

Two theories are thus mutually interpretable, if each of them is interpretable in the other. Such theories are necessarily equiconsistent, since from any model of one of them we can produce a model of the other.

Note that mutual interpretability, however, does not insist that the two translations are inverse to each other, even up to isomorphism. One can start with a model of the first theory $M\models T$ and define the interpreted model $N\models S$ of the second theory, which has a subsequent model of the first theory again $\bar M\models T$ inside it. But the definition does not insist on any particular connection between $M$ and $\bar M$, and these models need not be isomorphic nor even elementarily equivalent in general.

By addressing this, one arrives at a stronger and more robust form of mutual interpretability. Namely, two theories $S$ and $T$ are bi-interpretable, if they are mutually interpretable in such a way that the models can see that the interpretations are inverse. That is, for any model $M$ of the theory $T$, if one defines the interpreted model $N\models S$ inside it, and then defines the interpreted model $\bar M$ of $T$ inside $N$, then $M$ is isomorphic to $\bar M$ by a definable isomorphism in $M$, and uniformly so (and the same with the theories in the other direction). Thus, every model of one of the theories can see exactly how it itself arises definably in the interpreted model of the other theory.

For example, the theory of linear orders $\leq$ is bi-interpretable with the theory of strict linear order $<$, since from any linear order $\leq$ we can define the corresponding strict linear order $<$ on the same domain, and from any strict linear order $<$ we can define the corresponding linear order $\leq$, and doing it twice brings us back again to the same order.

For a richer example, the theory PA is bi-interpretable with the finite set theory $\text{ZF}^{\neg\infty}$, where one drops the infinity axiom from ZF and replaces it with the negation of infinity, and where one has the $\in$-induction scheme in place of the foundation axiom. The interpretation is via the Ackerman encoding of hereditary finite sets in arithmetic, so that $n\mathrel{E} m$ just in case the $n^{th}$ binary digit of $m$ is $1$. If one starts with the standard model $\mathbb{N}$, then the resulting structure $\langle\mathbb{N},E\rangle$ is isomorphic to the set $\langle\text{HF},\in\rangle$ of hereditarily finite sets. More generally, by carrying out the Ackermann encoding in any model of PA, one thereby defines a model of $\text{ZF}^{\neg\infty}$, whose natural numbers are isomorphic to the original model of PA, and these translations make a bi-interpretation.

We are now ready to prove that this bi-interpretation situation does not occur with different set theories extending ZF.

Theorem. Distinct set theories extending ZF are never bi-interpretable. Indeed, there is not a single model-theoretic instance of bi-interpretation occurring with models of different set theories extending ZF.

Proof. I mean “distinct” here in the sense that the two theories are not logically equivalent; they do not have all the same theorems. Suppose that we have a bi-interpretation instance of the theories $S$ and $T$ extending ZF. That is, suppose we have a model $\langle M,\in\rangle\models T$ of the one theory, and inside $M$, we can define an interpreted model of the other theory $\langle N,\in^N\rangle\models S$, so the domain of $N$ is a definable class in $M$ and the membership relation $\in^N$ is a definable relation on that class in $M$; and furthermore, inside $\langle N,\in^N\rangle$, we have a definable structure $\langle\bar M,\in^{\bar M}\rangle$ which is a model of $T$ again and isomorphic to $\langle M,\in^M\rangle$ by an isomorphism that is definable in $\langle M,\in^M\rangle$. So $M$ can define the map $a\mapsto \bar a$ that forms an isomorphism of $\langle M,\in^M\rangle$ with $\langle \bar M,\in^{\bar M}\rangle$. Our argument will work whether we allow parameters in any of these definitions or not.

I claim that $N$ must think the ordinals of $\bar M$ are well-founded, for otherwise it would have some bounded cut $A$ in the ordinals of $\bar M$ with no least upper bound, and this set $A$ when pulled back pointwise by the isomorphism of $M$ with $\bar M$ would mean that $M$ has a cut in its own ordinals with no least upper bound; but this cannot happen in ZF.

If the ordinals of $N$ and $\bar M$ are isomorphic in $N$, then all three models have isomorphic ordinals in $M$, and in this case, $\langle M,\in^M\rangle$ thinks that $\langle N,\in^N\rangle$ is a well-founded extensional relation of rank $\text{Ord}$. Such a relation must be set-like (since there can be no least instance where the predecessors form a proper class), and so $M$ can perform the Mostowski collapse of $\in^N$, thereby realizing $N$ as a transitive class $N\subseteq M$ with $\in^N=\in^M\upharpoonright N$. Similarly, by collapsing we may assume $\bar M\subseteq N$ and $\in^{\bar M}=\in^M\upharpoonright\bar M$. So the situation consists of inner models $\bar M\subseteq N\subseteq M$ and $\langle \bar M,\in^M\rangle$ is isomorphic to $\langle M,\in^M\rangle$ in $M$. This is impossible unless all three models are identical, since a simple $\in^M$-induction shows that $\pi(y)=y$ for all $y$, because if this is true for the elements of $y$, then $\pi(y)=\{\pi(x)\mid x\in y\}=\{x\mid x\in y\}=y$. So $\bar M=N=M$ and so $N$ and $M$ satisfy the same theory, contrary to assumption.

If the ordinals of $\bar M$ are isomorphic to a proper initial segment of the ordinals of $N$, then a similar Mostowski collapse argument would show that $\langle\bar M,\in^{\bar M}\rangle$ is isomorphic in $N$ to a transitive set in $N$. Since this structure in $N$ would have a truth predicate in $N$, we would be able to pull this back via the isomorphism to define (from parameters) a truth predicate for $M$ in $M$, contrary to Tarski’s theorem on the non-definability of truth.

The remaining case occurs when the ordinals of $N$ are isomorphic in $N$ to an initial segment of the ordinals of $\bar M$. But this would mean that from the perspective of $M$, the model $\langle N,\in^N\rangle$ has some ordinal rank height, which would mean by the Mostowski collapse argument that $M$ thinks $\langle N,\in^N\rangle$ is isomorphic to a transitive set. But this contradicts the fact that $M$ has an injection of $M$ into $N$. $\Box$

It follows that although ZF and ZFC are equiconsistent, they are not bi-interpretable. Similarly, ZFC and ZFC+CH and ZFC+$\neg$CH are equiconsistent, but no pair of them is bi-interpretable. And again with all the various equiconsistency results concerning large cardinals.

A similar argument works with PA to show that different extensions of PA are never bi-interpretable.

# Nonstandard models of arithmetic arise in the complex numbers

I’d like to explain that one may find numerous nonstandard models of arithmetic as substructures of the field of complex numbers.

The issue arose yesterday at Hans Schoutens’s talk for the CUNY Logic Workshop. The main focus of the talk was the question, for a given algebraically closed field $k$ of characteristic zero and a given model of arithmetic $\Gamma\models$PA, whether $\Gamma$ and $k$ were jointly realizable as the set of powers (as he defines it) and the set of units of a model $S$ of the generalized theory of polynomial rings over fields. Very interesting stuff.

During the talk, a side question arose, concerning exactly which models of PA arise as substructures of the field of complex numbers.

Question. Which models of PA arise as substructures of the field of complex numbers $\langle\mathbb{C},+,\cdot\rangle$?

Of course the standard model $\mathbb{N}$ arises this way, and some people thought at first it should be difficult to realize nonstandard models of PA as substructures of $\mathbb{C}$. After some back and forth, the question was ultimately answered by Alfred Dolich in the pub after the seminar, and I’d like to give his argument here (but see the Mlček reference below).  This is a case where a problem that was initially confusing becomes completely clear!

Theorem. Every model of PA of size at most continuum arises as a sub-semiring of the field of complex numbers $\langle\mathbb{C},+,\cdot\rangle$.

Proof. Suppose that $M$ is a model of PA of size at most continuum. Inside $M$, we may form $M$’s version of the algebraic numbers $A=\bar{\mathbb{Q}}^M$, the field that $M$ thinks is the algebraic closure of its version of the rationals. So $A$ is an algebraically closed field of characteristic zero, which has an elementary extension to such a field of size continuum. Since the theory of algebraically closed fields of characteristic zero is categorical in all uncountable powers, it follows that $A$ is isomorphic to a submodel of $\mathbb{C}$. Since $M$ itself is isomorphic to a substructure of its rationals $\mathbb{Q}^M$, which sit inside $A$, it follows that $M$ is isomorphic to a substructure of $\mathbb{C}$, as claimed. QED

In particular, every countable model of PA can be found as a substructure of the complex numbers.

Essentially the same argument shows the following.

Theorem. If $k$ is an uncountable algebraically closed field of characteristic zero, then every model of arithmetic $M\models$PA of size at most the cardinality of $k$ embeds into $k$.

I’ve realized that the same collection of ideas shows the following striking way to look upon the complex numbers:

Theorem. The complex numbers $\mathbb{C}$ can be viewed as a nonstandard version of the algebraic numbers $\bar{\mathbb{Q}}^M$ inside a nonstandard model $M$ of PA. Indeed, for every uncountable algebraically closed field $F$ of characteristic zero and every model of arithmetic $M\models$PA of the same cardinality, the field $F$ is isomorphic to the nonstandard algebraic numbers $\bar{\mathbb{Q}}^M$ as $M$ sees them.

Proof. Fix any such field $F$, such as the complex numbers themselves, and consider any nonstandard model of arithmetic $M$ of the same cardinality. The field $\bar{\mathbb{Q}}^M$, which is $M$’s nonstandard version of the algebraic numbers, is an algebraically closed field of characteristic zero and same uncountable size as $F$. By categoricity, these fields are isomorphic. $\Box$

I had suspected that these results were folklore in the model-theoretic community, and it has come to my attention that proper credit for the main observation of this post seems to be due to Jozef Mlček, who proved it in 1973. Thanks to Jerome Tauber for the reference, which he provided in the comments.

# The modal logic of arithmetic potentialism and the universal algorithm

• J. D. Hamkins, “The modal logic of arithmetic potentialism and the universal algorithm,” ArXiv e-prints, pp. 1-35, 2018. (under review)
@ARTICLE{Hamkins:The-modal-logic-of-arithmetic-potentialism,
author = {Joel David Hamkins},
title = {The modal logic of arithmetic potentialism and the universal algorithm},
journal = {ArXiv e-prints},
year = {2018},
volume = {},
number = {},
pages = {1--35},
month = {},
eprint = {1801.04599},
archivePrefix = {arXiv},
primaryClass = {math.LO},
note = {under review},
url = {http://wp.me/p5M0LV-1Dh},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
}

Abstract. Natural potentialist systems arise from the models of arithmetic when they are considered under their various natural extension concepts, such as end-extensions, arbitrary extension, $\Sigma_n$-elementary extensions, conservative extensions and more. For these potentialist systems, I prove, a propositional modal assertion is valid in a model of arithmetic, with respect to assertions in the language of arithmetic with parameters, exactly when it is an assertion of S4. Meanwhile, with respect to sentences, the validities of a model are always between S4 and S5, and these bounds are sharp in that both endpoints are realized. The models validating exactly S5 are the models of the arithmetic maximality principle, which asserts that every possibly necessary statement is already true, and these models are equivalently characterized as those satisfying a maximal $\Sigma_1$ theory. The main proof makes fundamental use of the universal algorithm, of which this article provides a self-contained account.

In this article, I consider the models of arithmetic under various natural extension concepts, including end-extensions, arbitrary extensions, $\Sigma_n$-elementary extensions, conservative extensions and more. Each extension concept gives rise to an arithmetic potentialist system, a Kripke model of possible arithmetic worlds, and the main goal is to discover the modal validities of these systems.

For most of the extension concepts, a modal assertion is valid with respect to assertions in the language of arithmetic, allowing parameters, exactly when it is an assertion of the modal theory S4. For sentences, however, the modal validities form a theory between S4 and S5, with both endpoints being realized. A model of arithmetic validates S5 with respect to sentences just in case it is a model of the arithmetic maximality principle, and these models are equivalently characterized as those realizing a maximal $\Sigma_1$ theory.

The main argument relies fundamentally on the universal algorithm, the theorem due to Woodin that there is a Turing machine program that can enumerate any finite sequence in the right model of arithmetic, and furthermore this model can be end-extended so as to realize any further extension of that sequence available in the model. In the paper, I give a self-contained account of this theorem using my simplified proof.

The paper concludes with philosophical remarks on the nature of potentialism, including a discussion of how the linear inevitability form of potentialism is actually much closer to actualism than the more radical forms of potentialism, which exhibit branching possibility. I also propose to view the philosphy of ultrafinitism in modal terms as a form of potentialism, pushing the issue of branching possibility in ultrafinitism to the surface.

# Self reference in computability theory and the universal algorithm, Ouroboros: Formal Criteria of Self-Reference in Mathematics and Philosophy, Bonn, February 2018

This will be a talk for the conference: Ouroboros: Formal Criteria of Self-Reference in Mathematics and Philosophy, held in Bonn, February 16-18, 2018.

Abstract. I shall give an elementary account of the universal algorithm, due to Woodin, showing how the capacity for self-reference in arithmetic gives rise to a Turing machine program $e$, which provably enumerates a finite set of numbers, but which can in principle enumerate any finite set of numbers, when it is run in a suitable model of arithmetic. Furthermore, the algorithm can successively enumerate any desired extension of the sequence, when run in a suitable top-extension of the universe. Thus, the algorithm sheds some light on the debate between free will and determinism, if one should imagine extending the universe into a nonstandard time scale. An analogous result holds in set theory, where Woodin and I have provided a universal locally definable finite set, which can in principle be any finite set, in the right universe, and which can furthermore be successively extended to become any desired finite superset of that set in a suitable top-extension of that universe.

# The universal finite set

• J. D. Hamkins and H. W. Woodin, “The universal finite set,” ArXiv e-prints, pp. 1-16, 2017. (manuscript under review)
@ARTICLE{HamkinsWoodin:The-universal-finite-set,
author = {Joel David Hamkins and W. Hugh Woodin},
title = {The universal finite set},
journal = {ArXiv e-prints},
year = {2017},
volume = {},
number = {},
pages = {1--16},
month = {},
note = {manuscript under review},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
eprint = {1711.07952},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/the-universal-finite-set},
}

Abstract. We define a certain finite set in set theory $\{x\mid\varphi(x)\}$ and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $\varphi$ has complexity $\Sigma_2$, so that any affirmative instance of it $\varphi(x)$ is verified in any sufficiently large rank-initial segment of the universe $V_\theta$; the set is empty in any transitive model and others; and if $\varphi$ defines the set $y$ in some countable model $M$ of ZFC and $y\subseteq z$ for some finite set $z$ in $M$, then there is a top-extension of $M$ to a model $N$ in which $\varphi$ defines the new set $z$. Thus, the set shows that no model of set theory can realize a maximal $\Sigma_2$ theory with its natural number parameters, although this is possible without parameters. Using the universal finite set, we prove that the validities of top-extensional set-theoretic potentialism, the modal principles valid in the Kripke model of all countable models of set theory, each accessing its top-extensions, are precisely the assertions of S4. Furthermore, if ZFC is consistent, then there are models of ZFC realizing the top-extensional maximality principle.

Woodin had established the universal algorithm phenomenon, showing that there is a Turing machine program with a certain universal top-extension property in models of arithmetic (see also work of Blanck and Enayat 2017 and upcoming paper of mine with Gitman and Kossak; also my post The universal algorithm: a new simple proof of Woodin’s theorem). Namely, the program provably enumerates a finite set of natural numbers, but it is relatively consistent with PA that it enumerates any particular desired finite set of numbers, and furthermore, if $M$ is any model of PA in which the program enumerates the set $s$ and $t$ is any (possibly nonstandard) finite set in $M$ with $s\subseteq t$, then there is a top-extension of $M$ to a model $N$ in which the program enumerates exactly the new set $t$. So it is a universal finite computably enumerable set, which can in principle be any desired finite set of natural numbers in the right arithmetic universe and become any desired larger finite set in a suitable larger arithmetic universe.

I had inquired whether there is a set-theoretic analogue of this phenomenon, using $\Sigma_2$ definitions in set theory in place of computable enumerability (see The universal definition — it can define any mathematical object you like, in the right set-theoretic universe). The idea was that just as a computably enumerable set is one whose elements are gradually revealed as the computation proceeds, a $\Sigma_2$-definable set in set theory is precisely one whose elements become verified at some level $V_\theta$ of the cumulative set-theoretic hierarchy as it grows. In this sense, $\Sigma_2$ definability in set theory is analogous to computable enumerability in arithmetic.

Main Question. Is there a universal $\Sigma_2$ definition in set theory, one which can define any desired particular set in some model of \ZFC\ and always any desired further set in a suitable top-extension?

I had noticed in my earlier post that one can do this using a $\Pi_3$ definition, or with a $\Sigma_2$ definition, if one restricts to models of a certain theory, such as $V\neq\text{HOD}$ or the eventual GCH, or if one allows $\{x\mid\varphi(x)\}$ sometimes to be a proper class.

Here, we provide a fully general affirmative answer with the following theorem.

Main Theorem. There is a formula $\varphi(x)$ of complexity $\Sigma_2$ in the language of set theory, provided in the proof, with the following properties:

1. ZFC proves that $\{x\mid \varphi(x)\}$ is a finite set.
2. In any transitive model of \ZFC\ and others, this set is empty.
3. If $M$ is a countable model of ZFC in which $\varphi$ defines the set $y$ and $z\in M$ is any finite set in $M$ with $y\subseteq z$, then there is a top-extension of $M$ to a model $N$ in which $\varphi$ defines exactly $z$.

By taking the union of the set defined by $\varphi$, an arbitrary set can be achieved; so the finite-set result as stated in the main theorem implies the arbitrary set case as in the main question. One can also easily deduce a version of the theorem to give a universal countable set or a universal set of some other size (for example, just take the union of the countable elements of the universal set). One can equivalently formulate the main theorem in terms of finite sequences, rather than sets, so that the sequence is extended as desired in the top-extension. The sets $y$ and $z$ in statement (3) may be nonstandard finite, if $M$ if $\omega$-nonstandard.

We use this theorem to establish the fundamental validities of top-extensional set-theoretic potentialism. Specifically, in the potentialist system consisting of the countable models of ZFC, with each accessing its top extensions, the modal validities with respect to substitution instances in the language of set theory, with parameters, are exactly the assertions of S4. When only sentences are considered, the validities are between S4 and S5, with both endpoints realized.

In particular, we prove that if ZFC is consistent, then there is a model $M$ of ZFC with the top-extensional maximality principle: any sentence $\sigma$ in the language of set theory which is true in some top extension $M^+$ and all further top extensions of $M^+$, is already true in $M$.

This principle is true is any model of set theory with a maximal $\Sigma_2$ theory, but it is never true when $\sigma$ is allowed to have natural-number parameters, and in particular, it is never true in any $\omega$-standard model of set theory.

Click through to the arXiv for more, the full article in pdf.

• J. D. Hamkins and H. W. Woodin, “The universal finite set,” ArXiv e-prints, pp. 1-16, 2017. (manuscript under review)
@ARTICLE{HamkinsWoodin:The-universal-finite-set,
author = {Joel David Hamkins and W. Hugh Woodin},
title = {The universal finite set},
journal = {ArXiv e-prints},
year = {2017},
volume = {},
number = {},
pages = {1--16},
month = {},
note = {manuscript under review},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
eprint = {1711.07952},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/the-universal-finite-set},
}

# A program that accepts exactly any desired finite set, in the right universe

Last year I made a post about the universal program, a Turing machine program $p$ that can in principle compute any desired function, if it is only run inside a suitable model of set theory or arithmetic.  Specifically, there is a program $p$, such that for any function $f:\newcommand\N{\mathbb{N}}\N\to\N$, there is a model $M\models\text{PA}$ — or of $\text{ZFC}$, whatever theory you like — inside of which program $p$ on input $n$ gives output $f(n)$.

This theorem is related to a very interesting theorem of W. Hugh Woodin’s, which says that there is a program $e$ such that $\newcommand\PA{\text{PA}}\PA$ proves $e$ accepts only finitely many inputs, but such that for any finite set $A\subset\N$, there is a model of $\PA$ inside of which program $e$ accepts exactly the elements of $A$. Actually, Woodin’s theorem is a bit stronger than this in a way that I shall explain.

Victoria Gitman gave a very nice talk today on both of these theorems at the special session on Computability theory: Pushing the Boundaries at the AMS sectional meeting here in New York, which happens to be meeting right here in my east midtown neighborhood, a few blocks from my home.

What I realized this morning, while walking over to Vika’s talk, is that there is a very simple proof of the version of Woodin’s theorem stated above.  The idea is closely related to an idea of Vadim Kosoy mentioned in my post last year. In hindsight, I see now that this idea is also essentially present in Woodin’s proof of his theorem, and indeed, I find it probable that Woodin had actually begun with this idea and then modified it in order to get the stronger version of his result that I shall discuss below.

But in the meantime, let me present the simple argument, since I find it to be very clear and the result still very surprising.

Theorem. There is a Turing machine program $e$, such that

1. $\PA$ proves that $e$ accepts only finitely many inputs.
2. For any particular finite set $A\subset\N$, there is a model $M\models\PA$ such that inside $M$, the program $e$ accepts all and only the elements of $A$.
3. Indeed, for any set $A\subset\N$, including infinite sets, there is a model $M\models\PA$ such that inside $M$, program $e$ accepts $n$ if and only if $n\in A$.

Proof.  The program $e$ simply performs the following task:  on any input $n$, search for a proof from $\PA$ of a statement of the form “program $e$ does not accept exactly the elements of $\{n_1,n_2,\ldots,n_k\}$.” Accept nothing until such a proof is found. For the first such proof that is found, accept $n$ if and only if $n$ is one of those $n_i$’s.

In short, the program $e$ searches for a proof that $e$ doesn’t accept exactly a certain finite set, and when such a proof is found, it accepts exactly the elements of this set anyway.

Clearly, $\PA$ proves that program $e$ accepts only a finite set, since either no such proof is ever found, in which case $e$ accepts nothing (and the empty set is finite), or else such a proof is found, in which case $e$ accepts only that particular finite set. So $\PA$ proves that $e$ accepts only finitely many inputs.

But meanwhile, assuming $\PA$ is consistent, then you cannot refute the assertion that program $e$ accepts exactly the elements of some particular finite set $A$, since if you could prove that from $\PA$, then program $e$ actually would accept exactly that set (for the shortest such proof), in which case this would also be provable, contradicting the consistency of $\PA$.

Since you cannot refute any particular finite set as the accepting set for $e$, it follows that it is consistent with $\PA$ that $e$ accepts any particular finite set $A$ that you like. So there is a model of $\PA$ in which $e$ accepts exactly the elements of $A$. This establishes statement (2).

Statement (3) now follows by a simple compactness argument. Namely, for any $A\subset\N$, let $T$ be the theory of $\PA$ together with the assertions that program $e$ accepts $n$, for any particular $n\in A$, and the assertions that program $e$ does not accept $n$, for $n\notin A$. Any finite subtheory of this theory is consistent, by statement (2), and so the whole theory is consistent. Any model of this theory realizes statement (3). QED

One uses the Kleene recursion theorem to show the existence of the program $e$, which makes reference to $e$ in the description of what it does. Although this may look circular, it is a standard technique to use the recursion theorem to eliminate the circularity.

This theorem immediately implies the classical result of Mostowski and Kripke that there is an independent family of $\Pi^0_1$ assertions, since the assertions $n\notin W_e$ are exactly such a family.

The theorem also implies a strengthening of the universal program theorem that I proved last year. Indeed, the two theorems can be realized with the same program!

Theorem. There is a Turing machine program $e$ with the following properties:

1. $\PA$ proves that $e$ computes a finite function;
2. For any particular finite partial function $f$ on $\N$, there is a model $M\models\PA$ inside of which program $e$ computes exactly $f$.
3. For any partial function $f:\N\to\N$, finite or infinite, there is a model $M\models\PA$ inside of which program $e$ on input $n$ computes exactly $f(n)$, meaning that $e$ halts on $n$ if and only if $f(n)\downarrow$ and in this case $\varphi_e(n)=f(n)$.

Proof. The proof of statements (1) and (2) is just as in the earlier theorem. It is clear that $e$ computes a finite function, since either it computes the empty function, if no proof is found, or else it computes the finite function mentioned in the proof. And you cannot refute any particular finite function for $e$, since if you could, it would have exactly that behavior anyway, contradicting $\text{Con}(\PA)$. So statement (2) holds. But meanwhile, we can get statement (3) by a simple compactness argument. Namely, fix $f$ and let $T$ be the theory asserting $\PA$ plus all the assertions either that $\varphi_e(n)\uparrow$, if $n$ is not the domain of $f$, and $\varphi_e(n)=k$, if $f(n)=k$.  Every finite subtheory of this theory is consistent, by statement (2), and so the whole theory is consistent. But any model of this theory exactly fulfills statement (3). QED

Woodin’s proof is more difficult than the arguments I have presented, but I realize now that this extra difficulty is because he is proving an extremely interesting and stronger form of the theorem, as follows.

Theorem. (Woodin) There is a Turing machine program $e$ such that $\PA$ proves $e$ accepts at most a finite set, and for any finite set $A\subset\N$ there is a model $M\models\PA$ inside of which $e$ accepts exactly $A$. And furthermore, in any such $M$ and any finite $B\supset A$, there is an end-extension $M\subset_{end} N\models\PA$, such that in $N$, the program $e$ accepts exactly the elements of $B$.

This is a much more subtle claim, as well as philosophically interesting for the reasons that he dwells on.

The program I described above definitely does not achieve this stronger property, since my program $e$, once it finds the proof that $e$ does not accept exactly $A$, will accept exactly $A$, and this will continue to be true in all further end-extensions of the model, since that proof will continue to be the first one that is found.

# Same structure, different truths, Stanford University CSLI, May 2016

This will be a talk for the Workshop on Logic, Rationality, and Intelligent Interaction at the CSLI, Stanford University, May 27-28, 2016.

Abstract. To what extent does a structure determine its theory of truth? I shall discuss several surprising mathematical results illustrating senses in which it does not, for the satisfaction relation of first-order logic is less absolute than one might have expected. Two models of set theory, for example, can have exactly the same natural numbers and the same arithmetic structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, yet disagree on what is true in this structure; they have the same arithmetic, but different theories of arithmetic truth; two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree on whether it is a well-order; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have a rank initial segment of the universe $\langle V_\delta,{\in}\rangle$ in common, yet disagree about whether it is a model of ZFC. These theorems and others can be proved with elementary classical model-theoretic methods, which I shall explain. On the basis of these observations, Ruizhi Yang (Fudan University, Shanghai) and I argue that the definiteness of the theory of truth for a structure, even in the case of arithmetic, cannot be seen as arising solely from the definiteness of the structure itself in which that truth resides, but rather is a higher-order ontological commitment.

Slides | Main article: Satisfaction is not absolute | CLSI 2016 | Abstract at CLSI

# Every function can be computable!

I’d like to share a simple proof I’ve discovered recently of a surprising fact:  there is a universal algorithm, capable of computing any given function!

Wait, what? What on earth do I mean? Can’t we prove that some functions are not computable?  Yes, of course.

What I mean is that there is a universal algorithm, a Turing machine program capable of computing any desired function, if only one should run the program in the right universe. There is a Turing machine program $p$ with the property that for any function $f:\newcommand\N{\mathbb{N}}\N\to\N$ on the natural numbers, including non-computable functions, there is a model of arithmetic or set theory inside of which the function computed by $p$ agrees exactly with $f$ on all standard finite input. You have to run the program in a different universe in order that it will compute your desired function $f$.
Theorem There is a Turing machine program $p$, carrying out the specific algorithm described in the proof, such that for any function $f:\N\to\N$, there is a model of arithmetic $M\models\PA$, or indeed a model of set theory $M\models\ZFC$ or more (if consistent), such that the function computed by program $p$ inside $M$ agrees exactly with $f$ on all standard finite input.

The proof is elementary, relying essentially only on the ideas of the classical proof of the Gödel-Rosser theorem. To briefly review, for any computably axiomatized theory $T$ extending $\PA$, there is a corresponding sentence $\rho$, called the Rosser sentence, which asserts, “for any proof of $\rho$ in $T$, there is a smaller proof of $\neg\rho$.” That is, by smaller, I mean that the Gödel-code of the proof is smaller. One constructs the sentence $\rho$ by a simple application of the Gödel fixed-point lemma, just as one constructs the usual Gödel sentence that asserts its own non-provability. The basic classical facts concerning the Rosser sentence include the following:

• If $T$ is consistent, then so are both $T+\rho$ and $T+\neg\rho$
• $\PA+\Con(T)$ proves $\rho$.
• The theories $T$, $T+\rho$ and $T+\neg\rho$ are equiconsistent.
• If $T$ is consistent, then $T+\rho$ does not prove $\Con(T)$.

The first statement is the essential assertion of the Gödel-Rosser theorem, and it is easy to prove: if $T$ is consistent and $T\proves\rho$, then the proof would be finite in the meta-theory, and so since $T$ would have to prove that there is a smaller proof of $\neg\rho$, that proof would also be finite in the meta-theory and hence an actual proof, contradicting the consistency of $T$. Similarly, if $T\proves\neg\rho$, then the proof would be finite in the meta-theory, and so $T$ would be able to verify that $\rho$ is true, and so $T\proves\rho$, again contradicting consistency. By internalizing the previous arguments to PA, we see that $\PA+\Con(T)$ will prove that neither $\rho$ nor $\neg\rho$ are provable in $T$, making $\rho$ vacuously true in this case and also establishing $\Con(T+\rho)$ and $\Con(T+\neg\rho)$, for the second and third statements. In particular, $T+\Con(T)\proves\Con(T+\rho)$, which implies that $T+\rho$ does not prove $\Con(T)$ by the incompleteness theorem applied to the theory $T+\rho$, for the fourth statement.

Let’s now proceed to the proof of the theorem. To begin, we construct what I call the Rosser tree over a c.e. theory $T$. Namely, we recursively define theories $R_s$ for each finite binary string $s\in 2^{{<}\omega}$, placing the initial theory $R_{\emptyset}=T$ at the root, and then recursively adding either the Rosser sentence $\rho_s$ for the theory $R_s$ or its negation $\neg\rho_s$ at each stage to form the theories at the next level of the tree.
$$R_{s\concat 1}=R_s+\rho_s$$
$$R_{s\concat 0}=R_s+\neg\rho_s$$
Each theory $R_s$ is therefore a finite extension of $T$ by successively adding the appropriate Rosser sentences or their negations in the pattern described by $s$. If the initial theory $T$ is consistent, then it follows by induction using the Gödel-Rosser theorem that all the theories $R_s$ in the Rosser tree are consistent. Extending our notation to the branches through the tree, if $f\in{}^\omega 2$ is an infinite binary sequence, we let $R_f=\bigcup_n R_{f\upharpoonright n}$ be the union of the theories arising along that branch of the Rosser tree. In this way, we have constructed a perfect set of continuum many distinct consistent theories.

I shall now describe a universal algorithm for the case of computing binary functions. Consider the Rosser tree over the theory $T=\PA+\neg\Con(\PA)$. This is a consistent theory that happens to prove its own inconsistency. By considering the Gödel-codes in order, the algorithm should begin by searching for a proof of the Rosser sentence $\rho_{\emptyset}$ or its negation in the initial theory $R_{\emptyset}$. If such a proof is ever found, then the algorithm outputs $0$ or $1$ on input $0$, respectively, depending on whether it was the Rosser sentence or its negation that was found first, and moves to the next theory in the Rosser tree by adding the opposite statement to the current theory. Then, it starts searching for a proof of the Rosser sentence of that theory or its negation. At each stage in the algorithm, there is a current theory $R_s$, depending on which prior proofs have been found, and the algorithm searches for a proof of $\rho_s$ or $\neg\rho_s$. If found, it outputs $0$ or $1$ accordingly (on input $n=|s|$), and moves to the next theory in the Rosser tree by adding the opposite statement to the current theory.

If $f:\N\to 2=\{0,1\}$ is any binary function on the natural numbers, then let $R_f$ be the theory arising from the corresponding path through the Rosser tree, and let $M\models R_f$ be a model of this theory. I claim that the universal algorithm I just described will compute exactly $f(n)$ on input $n$ inside this model. The thing to notice is that because $\neg\Con(\PA)$ was part of the initial theory, the model $M$ will think that all the theories in the Rosser tree are inconsistent. So the model will have plenty of proofs of every statement and its negation for any theory in the Rosser tree, and so in particular, the function computed by $p$ in $M$ will be a total function. The question is which proofs will come first at each stage, affecting the values of the function. Let $s=f\restrict n$ and notice that $R_s$ is true in $M$. Suppose inductively that the function computed by $p$ has worked correctly below $n$ in $M$, and consider stage $n$ of the procedure. By induction, the current theory will be exactly $R_s$, and the algorithm will be searching for a proof of $\rho_s$ or its negation in $R_s$. Notice that $f(n)=1$ just in case $\rho_s$ is true in $M$, and because of what $\rho_s$ asserts and the fact that $M$ thinks it is provable in $R_s$, it must be that there is a smaller proof of $\neg\rho_s$. So in this case, the algorithm will find the proof of $\neg\rho_s$ first, and therefore, according to the precise instructions of the algorithm, it will output $1$ on input $n$ and add $\rho_s$ (the opposite statement) to the current theory, moving to the theory $R_{s\concat 1}$ in the Rosser tree. Similarly, if $f(n)=0$, then $\neg\rho_s$ will be true in $M$, and the algorithm will therefore first find a proof of $\rho_s$, give output $0$ and add $\neg\rho_s$ to the current theory, moving to $R_{s\concat 0}$. In this way, the algorithm finds the proofs in exactly the right way so as to have $R_{f\restrict n}$ as the current theory at stage $n$ and thereby compute exactly the function $f$, as desired.

Basically, the theory $R_f$ asserts exactly that the proofs will be found in the right order in such a way that program $p$ will exactly compute $f$ on all standard finite input. So every binary function $f$ is computed by the algorithm in any model of the theory $R_f$.

Let me now explain how to extend the result to handle all functions $g:\N\to\N$, rather than only the binary functions as above. The idea is simply to modify the binary universal algorithm in a simple way. Any function $g:\N\to \N$ can be coded with a binary function $f:\N\to 2$ in a canonical way, for example, by having successive blocks of $1$s in $f$, separated by $0$s, with the $n^{\rm th}$ block of size $g(n)$. Let $q$ be the algorithm that runs the binary universal algorithm described above, thereby computing a binary sequence, and then extract from that binary sequence a corresponding function from $\N$ to $\N$ (this may fail, if for example, the binary sequence is finite or if it has only finitely many $0$s). Nevertheless, for any function $g:\N\to \N$ there is a binary function $f:\N\to 2$ coding it in the way we have described, and in any model $M\models R_f$, the binary universal algorithm will compute $f$, causing this adapted algorithm to compute exactly $g$ on all standard finite input, as desired.

Finally, let me describe how to extend the result to work with models of set theory, rather than models of arithmetic. Suppose that $\ZFC^+$ is a consistent c.e. extension of ZFC; perhaps it is ZFC itself, or ZFC plus some large cardinal axioms. Let $T=\ZFC^++\neg\Con(\ZFC^+)$ be a slightly stronger theory, which is also consistent, by the incompleteness theorem. Since $T$ interprets arithmetic, the theory of Rosser sentences applies, and so we may build the corresponding Rosser tree over $T$, and also we may undertake the binary universal algorithm using $T$ as the initial theory. If $f:\N\to 2$ is any binary function, then let $R_f$ be the theory arising on the corresponding branch through the Rosser tree, and suppose $M\models R_f$. This is a model of $\ZFC^+$, which also thinks that $\ZFC^+$ is inconsistent. So again, the universal algorithm will find plenty of proofs in this model, and as before, it will find the proofs in just the right order that the binary universal algorithm will compute exactly the function $f$. From this binary universal algorithm, one may again design an algorithm universal for all functions $g:\N\to\N$, as desired.

One can also get another kind of universality. Namely, there is a program $r$, such that for any finite $s\subset\N$, there is a model $M$ of $\PA$ (or $\ZFC$, etc.) such that inside the model $M$, the program $r$ will enumerate the set $s$ and nothing more. One can obtain such a program $r$ from the program $p$ of the theorem: just let $r$ run the universal binary program $p$ until a double $0$ is produced, and then interprets the finite binary string up to that point as the set $s$ to output.

Let me now also discuss another form of universality.

Corollary
There is a program $p$, such that for any model $M\models\PA+\Con(\PA)$ and any function $f:M\to M$ that is definable in $M$, there is an end-extension of $M$ to a taller model $N\models\PA$ such that in $N$, the function computed by program $p$ agrees exactly with $f$ on input in $M$.

Proof
We simply apply the main theorem inside $M$. The point is that if $M$ thinks $\Con(\PA)$, then it can build what it thinks is the tree of Rosser extensions, and it will think that each step maintains consistency. So the theory $T_f$ that it constructs will be consistent in $M$ and therefore have a model (the Henkin model) definable in $M$, which will therefore be an end-extension of $M$.
QED

This last application has a clear affinity with a theorem of Woodin’s, recently extended by Rasmus Blanck and Ali Enayat. See Victoria Gitman’s posts about her seminar talk on those theorems: Computable processes can produce arbitrary outputs in nonstandard models, continuation.

Alternative proof.  Here is an alternative elegant proof of the theorem based on the comments below of Vadim Kosoy. Let $T$ be any consistent computably axiomatizable theory interpreting PA, such as PA itself or ZFC or what have you. For any Turing machine program $e$, let $q(e)$ be a program carrying out the following procedure: on input $n$, search systematically for a finite function $h:X\to\mathbb{N}$, with $X$ finite and $n\in X$, and for a proof of the statement “program $p$ does not agree with $h$ on all inputs in $X$,” using the function $h$ simply as a list of values for this assertion. For the first such function and proof that is found, if any, give as output the value $h(n)$.

Since the function $e\mapsto q(e)$ is computable, there is by Kleene’s recursion theorem a program $p$ for which $p$ and $f(p)$ compute the same function, and furthermore, $T$ proves this.  So the program $p$ is searching for proofs that $p$ itself does not behave in a certain way, and then it is behaving in that way when such a proof is found.

I claim that the theory $T$ does not actually prove any of those statements, “program $p$ does not agree with $h$ on inputs in $X$,” for any particular finite function $h:X\to\mathbb{N}$. If it did prove such a statement, then for the smallest such function and proof, the output of $p$ would indeed be $h$ on all inputs in $X$, by design. Thus, there would also be a proof that the program did agree with this particular $h$, and so $T$ would prove a contradiction, contrary to our assumption that it was consistent. So $T$ actually proves none of those statements. In particular, the program $p$ computes the empty function in the standard model of arithmetic. But also, for any particular finite function $h:X\to\mathbb{N}$, we may consistently add the assertion “program $p$ agrees with $h$ on inputs in $X$” to $T$, since $T$ did not refute this assertion.

For any function $f:\mathbb{N}\to\mathbb{N}$, let $T_f$ be the theory $T$ together with all assertions of the form “program $p$ halts on input $n$ with value $k$”, for the particular value $k=f(n)$.  I claim that this theory is consistent, for if it is not, then by compactness there would be finitely many of the assertions that enable the inconsistency, and so there would be a finite function $h:X\to\mathbb{N}$, with $h=f\upharpoonright X$, such that $T$ proved the program $p$ does not agree with $h$ on inputs in $X$. But in the previous paragraph, we proved that this doesn’t happen. And so the theory $T_f$ is consistent.

Finally, note that in any model of $T_f$, the program $p$ computes the function $f$ on standard input, because these assertions are exactly made in the theory. QED

# Incomparable $\omega_1$-like models of set theory

• G. Fuchs, V. Gitman, and J. D. Hamkins, “Incomparable $\omega_1$-like models of set theory,” Math.~Logic Q., pp. 1-11, 2017.
@article {FuchsGitmanHamkins2017:IncomparableOmega1-likeModelsOfSetTheory,
author = {Fuchs, Gunter and Gitman, Victoria and Hamkins, Joel David},
title = {Incomparable $\omega_1$-like models of set theory},
journal = {Math.~Logic Q.},
issn = {1521-3870},
doi = {10.1002/malq.201500002},
pages = {1--11},
year = {2017},
month = {March},
eprint = {1501.01022},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/incomparable-omega-one-like-models-of-set-theory},
}

This is joint work with Gunter Fuchs and Victoria Gitman.

Abstract. We show that the analogues of the Hamkins embedding theorems, proved for the countable models of set theory, do not hold when extended to the uncountable realm of $\omega_1$-like models of set theory. Specifically, under the $\diamondsuit$ hypothesis and suitable consistency assumptions, we show that there is a family of $2^{\omega_1}$ many $\omega_1$-like models of $\text{ZFC}$, all with the same ordinals, that are pairwise incomparable under embeddability; there can be a transitive $\omega_1$-like model of ZFC that does not embed into its own constructible universe; and there can be an $\omega_1$-like model of PA whose structure of hereditarily finite sets is not universal for the $\omega_1$-like models of set theory.

In this article, we consider the question of whether the embedding theorems of my article, Every countable model of set theory embeds into its own constructible universe, which concern the countable models of set theory, might extend to the realm of uncountable models. Specifically, in that paper I had proved that (1) any two countable models of set theory are comparable by embeddability; indeed, (2) one countable model of set theory embeds into another just in case the ordinals of the first order-embed into the ordinals of the second; consequently, (3) every countable model of set theory embeds into its own constructible universe; and furthermore, (4) every countable model of set theory embeds into the hereditarily finite sets $\langle\text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. The question we consider here is, do the analogous results hold for uncountable models? Our answer is that they do not. Indeed, we shall prove that the corresponding statements do not hold even in the special case of $\omega_1$-like models of set theory, which otherwise among uncountable models often exhibit a special affinity with the countable models. Specifically, we shall construct large families of pairwise incomparable $\omega_1$-like models of set theory, even though they all have the same ordinals; we shall construct $\omega_1$-like models of set theory that do not embed into their own $L$; and we shall construct $\omega_1$-like models of \PA\ that are not universal for all $\omega_1$-like models of set theory.

The embedding theorems are expressed collectively in the theorem below. An embedding of one model $\langle M,{\in^M}\rangle$ of set theory into another $\langle N,{\in^N}\rangle$ is simply a function $j:M\to N$ for which $x\in^My\longleftrightarrow j(x)\in^Nj(y)$, for all $x,y\in M$, and in this case we say that $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$; note by extensionality that every embedding is injective. Thus, an embedding is simply an isomorphism of $\langle M,{\in^M}\rangle$ with its range, which is a submodel of $\langle N,{\in^N}\rangle$. Although this is the usual model-theoretic embedding concept for relational structures, the reader should note that it is a considerably weaker embedding concept than commonly encountered in set theory, because this kind of embedding need not be elementary nor even $\Delta_0$-elementary, although clearly every embedding as just defined is elementary at least for quantifier-free assertions. So we caution the reader not to assume a greater degree of elementarity beyond quantifier-free elementarity for the embeddings appearing in this paper.

Theorem.

1. For any two countable models of set theory $\langle M,\in^M\rangle$ and $\langle N,\in^N\rangle$, one of them embeds into the other.

2. Indeed, such an $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$ if and only if the ordinals of $M$ order-embed into the ordinals of $N$.

3. Consequently, every countable model $\langle M,\in^M\rangle$ of set theory embeds into its own constructible universe $\langle L^M,\in^M\rangle$.

4. Furthermore, every countable model of set theory embeds into the hereditary finite sets $\langle \text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. Indeed, $\text{HF}^M$ is universal for all countable acyclic binary relations.

One can begin to get an appreciation for the difference in embedding concepts by observing that ZFC proves that there is a nontrivial embedding $j:V\to V$, namely, the embedding recursively defined as follows $$j(y)=\bigl\{\ j(x)\ \mid\ x\in y\ \bigr\}\cup\bigl\{\{\emptyset,y\}\bigr\}.$$

We leave it as a fun exercise to verify that $x\in y\longleftrightarrow j(x)\in j(y)$ for the embedding $j$ defined by this recursion. (See my paper Every countable model of set theory embeds into its own constructible universe; but to give a hint here for the impatient, note that every $j(y)$ is nonempty and also $\emptyset\notin j(y)$; it follows that inside $j(y)$ we may identify the pair $\{\emptyset,y\}\in j(y)$; it follows that $j$ is injective and furthermore, the only way to have $j(x)\in j(y)$ is from $x\in y$.} Contrast this situation with the well-known Kunen inconsistency, which asserts that there can be no nontrivial $\Sigma_1$-elementary embedding $j:V\to V$. Similarly, the same recursive definition applied in $L$ leads to nontrivial embeddings $j:L\to L$, regardless of whether $0^\sharp$ exists. But again, the point is that embeddings are not necessarily even $\Delta_0$-elementary, and the familiar equivalence of the existence of $0^\sharp$ with a nontrivial “embedding” $j:L\to L$ actually requires a $\Delta_0$-elementary embedding.)

We find it interesting to note in contrast to the theorem above that there is no such embedding phenomenon in the the context of the countable models of Peano arithmetic (where an embedding of models of arithmetic is a function preserving all atomic formulas in the language of arithmetic). Perhaps the main reason for this is that embeddings between models of PA are automatically $\Delta_0$-elementary, as a consequence of the MRDP theorem, whereas this is not true for models of set theory, as the example above of the recursively defined embedding $j:V\to V$ shows, since this is an embedding, but it is not $\Delta_0$-elementary, in light of $j(\emptyset)\neq\emptyset$. For countable models of arithmetic $M,N\models\text{PA}$, one can show that there is an embedding $j:M\to N$ if and only if $N$ satisfies the $\Sigma_1$-theory of $M$ and the standard system of $M$ is contained in the standard system of $N$. It follows that there are many instances of incomparability. Meanwhile, it is a consequence of statement (4) that the embedding phenomenon recurs with the countable models of finite set theory $\text{ZFC}^{\neg\infty}$, that is, with $\langle\text{HF},{\in}\rangle^M$ for $M\models\text{PA}$, since all nonstandard such models are universal for all countable acyclic binary relations, and so in the context of countable models of $\text{ZFC}^{\neg\infty}$ there are precisely two bi-embeddability classes, namely, the standard model, which is initial, and the nonstandard countable models, which are universal.

Our main theorems are as follows.

Theorem.

1. If $\diamondsuit$ holds and ZFC is consistent, then there is a family $\mathcal C$ of $2^{\omega_1}$ many pairwise incomparable $\omega_1$-like models of ZFC, meaning that there is no embedding between any two distinct models in $\mathcal C$.

2. The models in statement (1) can be constructed so that their ordinals order-embed into each other and indeed, so that the ordinals of each model is a universal $\omega_1$-like linear order. If ZFC has an $\omega$-model, then the models of statement (1) can be constructed so as to have precisely the same ordinals.

3. If $\diamondsuit$ holds and ZFC is consistent, then there is an $\omega_1$-like model $M\models\text{ZFC}$ and an $\omega_1$-like model $N\models\text{PA}$ such that $M$ does not embed into $\langle\text{HF},{\in}\rangle^N$.

4. If there is a Mahlo cardinal, then in a forcing extension of $L$, there is a transitive $\omega_1$-like model $M\models\text{ZFC}$ that does not embed into its own constructible universe $L^M$.

Note that the size of the family $\mathcal C$ in statement (1) is as large as it could possibly be, given that any two elements in a pairwise incomparable family of structures must be non-isomorphic and there are at most $2^{\omega_1}$ many isomorphism types of $\omega_1$-like models of set theory or indeed of structures of size $\omega_1$ in any first-order finite language. Statement (2) shows that the models of the family $\mathcal C$ serve as $\omega_1$-like counterexamples to the assertion that one model of set theory embeds into another whenever the ordinals of the first order-embed into the ordinals of the second.