A set-theoretic approach to Scott’s Problem

This is a talk at the National University of Singapore Logic Seminar, October 19, 2016.


Every nonstandard model of Peano Arithmetic (${\rm PA}$) has a Boolean algebra of subsets of the natural numbers associated to it, called its standard system. The standard system of a model $M\models{\rm PA}$, denoted ${\rm SSy}(M)$, consists of the intersections of the definable subsets of $M$ with the natural numbers. Standard systems play a very important role in the study of nonstandard models of arithmetic. For instance, they are used to determine when models are isomorphic and when models elementarily embed. Two countable computably saturated models of ${\rm PA}$ are isomorphic precisely when they have the same theory and the same standard system (this folklore result has been variously attributed to Ehrenfeucht and Jensen, Wilmers, etc.). A countable model $M\models{\rm PA}$ $\Sigma_n$-elementarily embeds into another model $N\models{\rm PA}$ precisely when $N$ satisfies the $\Sigma_{n+1}$-theory of $M$ and ${\rm SSy}(M)\subseteq{\rm SSy}(N)$ (this is a variant of the famous Friedman’s Embedding Theorem showing that every model of ${\rm PA}$ has an isomorphic elementary initial segment).

Standard systems are Boolean algebras because the definable sets of any model form a Boolean algebra. Standard systems are closed under relative computability: if $A$ is in a standard system and $B$ is Turing computable with oracle $A$, then $B$ is also in that standard system. Let’s see why this is true. Suppose $M\models{\rm PA}$, $A\in {\rm SSy}(M)$, and $B$ is computed by a Turing machine $m$ with oracle $A$. Let $\bar A$ be a definable subset of $M$ such that $A=\bar A\cap \mathbb N$ and let $\bar B$ be the set computed in $M$ by the Turing machine $m$ with oracle $\bar A$. Since $M$ must see that $m$ computes $B$ on the natural numbers, it follows that $\bar B\cap \mathbb N=B$. Standard systems also have the tree property: if $T$ is an infinite binary tree coded by a set in a standard system (use your favorite coding), then there is another set in that standard system coding an infinite branch through $T$. Let’s see why this is true. Suppose that $M\models{\rm PA}$ and $T\in {\rm SSy}(M)$ codes an infinite binary tree. Let $\bar T$ be a definable subset of $M$ such that $T=\bar T\cap\mathbb N$. Since for every natural number $n$, there is an element in $\bar T$ coding a binary sequence of length $n$ such that all its predecessors are also coded in $\bar T$, this must hold for some nonstandard $c$ as well. So $\bar T$ has some nonstandard binary sequence $s$ of length $c$ as well as all its binary predecessors. Let $\bar B$ the definable set of all binary predecessors of $s$ in $\bar T$. Then $B=\bar B\cap \mathbb N$, the collection of all binary predecessors of $s$ of finite length, is an infinite branch through $T$.

A decade before the notion of a standard system was introduced by Harvey Friedman in 1973 [1], Dana Scott defined that a Scott set is a nonempty Boolean algebra of subsets of the natural numbers that is closed under relative computability and has the tree property [2]. We just argued that every standard system is a Scott set. Scott’s arguments translated into modern terms show a partial converse: every countable Scott set is the standard system of some model of ${\rm PA}$. What about uncountable Scott sets? This is Scott’s Problem, one of the most famous and long-standing open problems in the field. Is every Scott set the standard system of some model of ${\rm PA}$? In 1982, Knight and Nadel showed that every Scott set of size $\omega_1$ is the standard system of a some model of ${\rm PA}$ [3]. Thus, it is consistent, namely, by assuming ${\rm CH}$, that Scott’s Problem has a positive answer. What happens if $2^\omega=\omega_2$ or if continuum is very large? No one knows the answer! Most well-developed techniques in the field of models of ${\rm PA}$ break down for uncountable models. Elegant theorems for countable models are either known to be false or are open problems for uncountable models. Here are two examples. It is easy to see that every nonstandard model of ${\rm PA}$ has order-type $\mathbb N+\mathbb A\cdot \mathbb Z$ for a dense linear order $\mathbb A$ without endpoints. For countable models, obviously, $\mathbb A=\mathbb Q$, but very little is known about the possible order-types of uncountable models (see [4]). The classification theorem for countable computably saturated models is known to fail for uncountable models (there are counterexample $\omega_1$-like models, see [5] Chapter 10).

So what are the promising strategies for making progress on Scott’s Problem? Knight and Nadel’s result can be proved using an unpublished theorem of Ehrenfeucht, which we will call Ehrenfeucht’s Lemma. Ehrenfeucht’s Lemma states that if $\mathscr X$ is a Scott set and $M$ is a countable model of ${\rm PA}$ such that ${\rm SSy}(M)\subseteq \mathscr X$, then for every $A\in \mathscr X$, $M$ has an elementary extension $N$ such that $A\in {\rm SSy}(N)\subseteq \mathscr X$. Knight and Nadel’s result follows nearly immediately by a transfinite application of Ehrenfeucht’s Lemma. Let $\mathscr X=\{A_\xi\mid \xi<\omega_1\}$ be a Scott set. We build the model $M$ with standard system $\mathscr X$ in $\omega_1$-many steps as the union of a continuous elementary chain of models $M_0\prec M_1\prec\cdots\prec M_\xi\prec\cdots\prec M$ such that $A_\xi\in {\rm SSy}(M_\xi)\subseteq \mathscr X$. Does Ehrenfeucht's Lemma hold for uncountable models $M$? Nothing is known here either. So nearly a decade ago in my dissertation, I tried to find some strong requirements on a Scott set $\mathscr X$ of size $\omega_2$ such that Ehrenfeucht's Lemma would hold for it with models of size $\omega_1$. By the elementary chain of models argument, each such Scott set would be the standard system of some model of ${\rm PA}$.

Let’s say that a collection $\mathscr X$ of subsets of $\mathbb N$ is arithmetically closed if it is a Boolean algebra closed under the Turing jump operation. Scott sets are precisely the $\omega$-models of the second-order arithmetic theory ${\rm WKL}_0$ and arithmetically closed families are precisely the $\omega$-models of the theory ${\rm ACA}_0$. Given $M\models{\rm PA}$ and a Scott set $\mathscr X$ such that ${\rm SSy}(M)\subseteq \mathscr X$, there is an ultrapower construction introduced by Kirby and Paris which uses an ultrafilter on $\mathscr X$ and functions $f:\mathbb N\to M$ that are the restrictions of definable functions $F:M\to M$. It turns out that the ultrapower $N$ can be made to satisfy the requirements of Ehrenfeucht’s Lemma (given $A\in\mathscr X$, we have $A\in {\rm SSy}(N)\subseteq \mathscr X$) by including sets satisfying certain properties in the ultrafilter. If the family $\mathscr X$ is arithmetically closed, the desired ultrafilter can be obtained from a generic filter for the partial order $\mathscr X/{\rm fin}$ whose elements are infinite sets in $\mathscr X$ ordered by almost inclusion: $A\subseteq_* B$ if there is $n\in\mathbb N$ such that $A\setminus n\subseteq B$. Indeed, for a model $M$ of size $\omega_1$, the filter $G$ has to meet only $\omega_1$-many dense sets. So if for instance $\mathscr X/{\rm fin}$ is proper and we are in a model with ${\rm PFA}$ (Proper Forcing Axiom) we would have the required filter right there. All this gives that in a model of ${\rm PFA}$ if $\mathscr X$ is an arithmetically closed family such that $\mathscr X/{\rm fin}$ is proper, then Ehrenfeucht’s Lemma holds for models of size $\omega_1$ with standard system contained in $\mathscr X$. It suffices to assume that $\mathscr X/{\rm fin}$ is only piecewise proper: $\mathscr X$ is a chain of arithmetically closed families $\mathscr Y$ of size $\omega_1$ such that $\mathscr Y/{\rm fin}$ is proper [6].

Enayat and Shelah showed that there is a Borel arithmetically closed family $\mathscr X$ such that $\mathscr X/\text{fin}$ is not proper [7]. I showed that it is consistent to have continuum many arithmetically closed families $\mathscr X$ of size $\omega_1$ such that $\mathscr X/\text{fin}$ is proper and continuum many arithmetically closed families $\mathscr X$ of size $\omega_2$ such that $\mathscr X/{\rm fin}$ is piecewise proper by adding these families by forcing [8]. But to this day I cannot show that there are proper or piecewise Scott sets of size $\omega_2$ in a model of ${\rm PFA}$. A few years ago when I asked a related question on MathOverflow, François Dorais, in response, came up with a completely different way of associating a partial order to an arithmetically closed family $\mathscr X$ such that the generic filter for the forcing also yields a desired ultrafilter on $\mathscr X$. Conditions in Dorais’ forcing are lower semicontinuous submeasures coded in $\mathscr X$. A submeasure is a function $\mu:P(\mathbb N)\to [0,\infty]$ such that $\mu(\emptyset)=0$ and $\mu(X)\leq \mu(X\cup Y)\leq \mu(X)+\mu(Y)$. A submeasure is lower semicontinuous if $\mu(X)=\lim_{n\to\infty}\mu(X\cap n)$. So lower semicontinous measures are determined by their values on finite sets and therefore can be coded in a Scott set. Given a Scott set $\mathscr X$, let $\mathbb P_{\mathscr X}$ be the partial order whose elements are lower semicontinuous measures coded in $\mathscr X$ ordered by $\leq_*$, where $\mu\leq_*\nu$ whenever there is $n\in\mathbb N$ such that $\mu(X)\leq \text{max}(\mu(X),n)$. Using a deep result of Dorais from [9], we can show that, under ${\rm CH}$, there are $\omega_1$-many arithmetically closed families $\mathscr X$ of size $\omega_1$ such that $\mathbb P_\mathscr X$ is proper. But alas the construction breaks at $\omega_1$.

This leaves many fascinating open questions that we should all start thinking about!

Here are the slides.

[1] H. Friedman, “Countable models of set theories,” in Cambridge Summer School in Mathematical Logic (Cambridge, 1971), Berlin: Springer, 1973, p. 539–573. Lecture Notes in Math., Vol. 337.
@incollection {friedman:countableModelsOfSetTheory,
AUTHOR = {Friedman, Harvey},
TITLE = {Countable models of set theories},
BOOKTITLE = {Cambridge {S}ummer {S}chool in {M}athematical {L}ogic
({C}ambridge, 1971)},
PAGES = {539--573. Lecture Notes in Math., Vol. 337},
PUBLISHER = {Springer},
ADDRESS = {Berlin},
YEAR = {1973},
MRCLASS = {02K15 (02H20)},
MRNUMBER = {0347599 (50 \#102)},
MRREVIEWER = {Nigel J. Cutland},
[2] D. Scott, “Algebras of sets binumerable in complete extensions of arithmetic,” in Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117-121.
@incollection {scott:ScottSets,
AUTHOR = {Scott, Dana},
TITLE = {Algebras of sets binumerable in complete extensions of
BOOKTITLE = {Proc. {S}ympos. {P}ure {M}ath., {V}ol. {V}},
PAGES = {117--121},
PUBLISHER = {American Mathematical Society, Providence, R.I.},
YEAR = {1962},
MRCLASS = {02.72},
MRNUMBER = {0141595},
MRREVIEWER = {H. Ribeiro},
[3] [doi] J. Knight and M. Nadel, “Models of arithmetic and closed ideals,” J. symbolic logic, vol. 47, iss. 4, p. 833–840 (1983), 1982.
@article {KnightNadel:ScottSets,
AUTHOR = {Knight, Julia and Nadel, Mark},
TITLE = {Models of arithmetic and closed ideals},
JOURNAL = {J. Symbolic Logic},
FJOURNAL = {The Journal of Symbolic Logic},
VOLUME = {47},
YEAR = {1982},
NUMBER = {4},
PAGES = {833--840 (1983)},
ISSN = {0022-4812},
MRCLASS = {03C62 (03C50 03D30)},
MRNUMBER = {683158},
MRREVIEWER = {S. S. Goncharov},
DOI = {10.2307/2273102},
URL = {http://dx.doi.org/10.2307/2273102},
[4] [doi] A. Bovykin and R. Kaye, “Order-types of models of Peano arithmetic,” in Logic and algebra, Amer. Math. Soc., Providence, RI, 2002, vol. 302, pp. 275-285.
@incollection {BovykinKaye:orderTypesModelsPA,
AUTHOR = {Bovykin, Andrey and Kaye, Richard},
TITLE = {Order-types of models of {P}eano arithmetic},
BOOKTITLE = {Logic and algebra},
SERIES = {Contemp. Math.},
VOLUME = {302},
PAGES = {275--285},
PUBLISHER = {Amer. Math. Soc., Providence, RI},
YEAR = {2002},
MRCLASS = {03H15},
MRNUMBER = {1928396},
DOI = {10.1090/conm/302/05055},
URL = {http://dx.doi.org/10.1090/conm/302/05055},
[5] [doi] R. Kossak and J. H. Schmerl, The structure of models of Peano arithmetic, The Clarendon Press, Oxford University Press, Oxford, 2006, vol. 50.
@book {kossakschmerl:modelsofpa,
AUTHOR = {Kossak, Roman and Schmerl, James H.},
TITLE = {The structure of models of {P}eano arithmetic},
SERIES = {Oxford Logic Guides},
VOLUME = {50},
NOTE = {Oxford Science Publications},
PUBLISHER = {The Clarendon Press, Oxford University Press, Oxford},
YEAR = {2006},
PAGES = {xiv+311},
ISBN = {978-0-19-856827-8; 0-19-856827-4},
MRCLASS = {03-02 (03C62 03F30 03H15)},
MRNUMBER = {2250469 (2008b:03001)},
MRREVIEWER = {Constantine Dimitracopoulos},
DOI = {10.1093/acprof:oso/9780198568278.001.0001},
URL = {http://dx.doi.org.ezproxy.gc.cuny.edu/10.1093/acprof:oso/9780198568278.001.0001},
[6] [pdf] [doi] V. Gitman, “Proper and piecewise proper families of reals,” Mlq math. log. q., vol. 55, iss. 5, pp. 542-550, 2009.
@article {gitman:scott,
AUTHOR = {Gitman, Victoria},
TITLE = {Proper and piecewise proper families of reals},
JOURNAL = {MLQ Math. Log. Q.},
FJOURNAL = {MLQ. Mathematical Logic Quarterly},
VOLUME = {55},
YEAR = {2009},
NUMBER = {5},
PAGES = {542--550},
ISSN = {0942-5616},
MRCLASS = {03E35 (03E40 03H15)},
MRNUMBER = {2568765},
MRREVIEWER = {Renling Jin},
DOI = {10.1002/malq.200810015},
URL = {http://dx.doi.org/10.1002/malq.200810015},
EPRINT ={0801.4364},
[7] [doi] A. Enayat and S. Shelah, “An improper arithmetically closed Borel subalgebra of $\scr P(\omega)\bmod\mathsf{FIN}$,” Topology appl., vol. 158, iss. 18, pp. 2495-2502, 2011.
@article {EnayatShelahImproperFamily,
AUTHOR = {Enayat, Ali and Shelah, Saharon},
TITLE = {An improper arithmetically closed {B}orel subalgebra of {$\scr
JOURNAL = {Topology Appl.},
FJOURNAL = {Topology and its Applications},
VOLUME = {158},
YEAR = {2011},
NUMBER = {18},
PAGES = {2495--2502},
ISSN = {0166-8641},
MRCLASS = {03E15 (03C55 28A05 54H05)},
MRNUMBER = {2847322},
DOI = {10.1016/j.topol.2011.08.006},
URL = {http://dx.doi.org/10.1016/j.topol.2011.08.006},
[8] [pdf] [doi] V. Gitman, “Proper and piecewise proper families of reals,” Mathematical logic quarterly, vol. 55, iss. 5, pp. 542-550, 2009.
@ARTICLE {gitman:proper,
AUTHOR = {Victoria Gitman},
TITLE = {Proper and Piecewise Proper Families of Reals},
JOURNAL = {Mathematical Logic Quarterly},
VOLUME = {55},
YEAR = {2009},
NUMBER = {5},
PAGES = {542-550},
EPRINT ={0801.4368},
ISSN = {0942-5616},
MRCLASS = {03E35 (03E40 03H15)},
MRNUMBER = {2568765 (2011c:03109)},
MRREVIEWER = {Renling Jin},
DOI = {10.1002/malq.200810015},
URL = {http://dx.doi.org/10.1002/malq.200810015},
[9] [doi] F. G. Dorais, “A variant of Mathias forcing that preserves $\mathsf{ACA}_0$,” Arch. math. logic, vol. 51, iss. 7-8, pp. 751-780, 2012.
@article {dorais:MathiasForcing,
AUTHOR = {Dorais, Fran{\c{c}}ois G.},
TITLE = {A variant of {M}athias forcing that preserves {$\mathsf{ACA}_0$}},
JOURNAL = {Arch. Math. Logic},
FJOURNAL = {Archive for Mathematical Logic},
VOLUME = {51},
YEAR = {2012},
NUMBER = {7-8},
PAGES = {751--780},
ISSN = {0933-5846},
MRCLASS = {03B30 (03E40 03F35)},
MRNUMBER = {2975428},
MRREVIEWER = {Wei Wang},
DOI = {10.1007/s00153-012-0297-4},
URL = {http://dx.doi.org/10.1007/s00153-012-0297-4},
This entry was posted in talks and tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *