# Forcing as a computational process

• J. D. Hamkins, R. Miller, and K. J. Williams, “Forcing as a computational process,” Mathematics arXiv, 2020. (Under review)
@ARTICLE{HamkinsMillerWilliams:Forcing-as-a-computational-process,
author = {Joel David Hamkins and Russell Miller and Kameryn J. Williams},
title = {Forcing as a computational process},
journal = {Mathematics arXiv},
year = {2020},
volume = {},
number = {},
pages = {},
month = {},
note = {Under review},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
url = {http://jdh.hamkins.org/forcing-as-a-computational-process},
eprint = {2007.00418},
archivePrefix = {arXiv},
primaryClass = {math.LO},
}

Abstract. We investigate how set-theoretic forcing can be seen as a computational process on the models of set theory. Given an oracle for information about a model of set theory $\langle M,\in^M\rangle$, we explain senses in which one may compute $M$-generic filters $G\subseteq\mathbb{P}\in M$ and the corresponding forcing extensions $M[G]$. Specifically, from the atomic diagram one may compute $G$, from the $\Delta_0$-diagram one may compute $M[G]$ and its $\Delta_0$-diagram, and from the elementary diagram one may compute the elementary diagram of $M[G]$. We also examine the information necessary to make the process functorial, and conclude that in the general case, no such computational process will be functorial. For any such process, it will always be possible to have different isomorphic presentations of a model of set theory $M$ that lead to different non-isomorphic forcing extensions $M[G]$. Indeed, there is no Borel function providing generic filters that is functorial in this sense.

# Forcing as a computational process, Cambridge, Februrary 2019

This will be a talk for Set Theory in the United Kingdom (STUK 1), to be held in the other place, February 16, 2019.

Abstract. We investigate the senses in which set-theoretic forcing can be seen as a computational process on the models of set theory. Given an oracle for the atomic or elementary diagram of a model of set theory $\langle M,\in^M\rangle$, for example, we explain senses in which one may compute $M$-generic filters $G\subset P\in M$ and the corresponding forcing extensions $M[G]$. Meanwhile, no such computational process is functorial, for there must always be isomorphic alternative presentations of the same model of set theory $M$ that lead by the computational process to non-isomorphic forcing extensions $M[G]\not\cong M[G’]$. Indeed, there is no Borel function providing generic filters that is functorial in this sense.

This is joint work with Russell Miller and Kameryn Williams.

# Computable quotient presentations of models of arithmetic and set theory

• M. T. Godziszewski and J. D. Hamkins, “Computable Quotient Presentations of Models of Arithmetic and Set Theory,” in Logic, Language, Information, and Computation: 24th International Workshop, WoLLIC 2017, London, UK, July 18-21, 2017, Proceedings, J. Kennedy and R. J. G. B. de Queiroz, Eds., Springer, 2017, pp. 140-152.
@Inbook{GodziszewskiHamkins2017:Computable-quotient-presentations-of-models-of-arithmetic-and-set-theory,
author="Godziszewski, Micha{\l} Tomasz and Hamkins, Joel David",
editor="Kennedy, Juliette and de Queiroz, Ruy J.G.B.",
title="Computable Quotient Presentations of Models of Arithmetic and Set Theory",
bookTitle="{Logic, Language, Information, and Computation: 24th International Workshop, WoLLIC 2017, London, UK, July 18-21, 2017, Proceedings}",
year="2017",
publisher="Springer",
pages="140--152",
abstract="We prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No {\$}{\$}{\backslash}Sigma {\_}1{\$}{\$} -sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language {\$}{\$}{\backslash}{\{}+,{\backslash}cdot ,{\backslash}le {\backslash}{\}}{\$}{\$} has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation.",
isbn="978-3-662-55386-2",
doi="10.1007/978-3-662-55386-2_10",
eprint = {1702.08350},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://wp.me/p5M0LV-1tW},
}

Abstract. We prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation.

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.

At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.

Conjecture. (Khoussainov)

1. No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
2. Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.

# Computable quotient presentations of models of arithmetic and set theory, CUNY set theory seminar, March 2017

This will be a talk for the CUNY Set Theory Seminar on March 10, 2017, 10:00 am in room 6417 at the CUNY Graduate Center.

Abstract.  I shall prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. This is joint work with Michał Tomasz Godziszewski.

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.

At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.

In my talk, I shall engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

1. No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
2. Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.