Tag Archives: Peano Arithmetic

Pointwise definable and Leibnizian extensions of models of arithmetic and set theory, MOPA seminar CUNY, November 2022

Posted on by
Reply

 This will be an online talk for the MOPA Seminar at CUNY on 22 November 2022 1pm. Contact organizers for Zoom access.

Abstract. I shall introduce a flexible new method showing that every countable model of PA admits a pointwise definable end-extension, one in which every individual is definable without parameters. And similarly for models of set theory, in which one may also achieve the Barwise extension result—every countable model of ZF admits a pointwise definable end-extension to a model of ZFC+V=L, or indeed any theory arising in a suitable inner model. A generalization of the method shows that every model of arithmetic of size at most continuum admits a Leibnizian extension, and similarly in set theory. 

Slides-Pointwise-definable-end-extensions-MOPA-2022

Is the twin prime conjecture independent of Peano Arithmetic?

Posted on by
Reply

[bibtex key=”BerarducciFornasieroHamkins:Is-the-twin-prime-conjecture-independent-of-PA”]

Download the article at arXiv:2110.08640

Abstract. We show that there is an arithmetical formula $\varphi$ such that ZF proves that $\varphi$ is independent of PA and yet, unlike other arithmetical independent statements, the truth value of $\varphi$ cannot at present be established in ZF or in any other trusted metatheory. In fact we can choose an example of such a formula $\varphi$ such that ZF proves that $\varphi$ is equivalent to the twin prime conjecture. We conclude with a discussion of notion of trustworthy theory and a sharper version of the result.

This work grows in part out of an answer I posted on MathOverflow in 2012.

Continuous models of arithmetic, MOPA, November 2020

Posted on by
Reply

This will be a talk for the Models of Peano Arithmetic (MOPA) seminar on 11 November 2020, 12 pm EST (5pm GMT). Kindly note the rescheduled date and time.

Abstract. Ali Enayat had asked whether there is a model of Peano arithmetic (PA) that can be represented as $\newcommand\Q{\mathbb{Q}}\langle\Q,\oplus,\otimes\rangle$, where $\oplus$ and $\otimes$ are continuous functions on the rationals $\Q$. We prove, affirmatively, that indeed every countable model of PA has such a continuous presentation on the rationals. More generally, we investigate the topological spaces that arise as such topological models of arithmetic. The reals $\mathbb{R}$, the reals in any finite dimension $\mathbb{R}^n$, the long line and the Cantor space do not, and neither does any Suslin line; many other spaces do; the status of the Baire space is open.

This is joint work with Ali Enayat, myself and Bartosz Wcisło.

Article: Topological models of arithmetic

[bibtex key=”EnayatHamkinsWcislo2018:Topological-models-of-arithmetic”]

Victoria Gitman

Posted on by
Reply

Victoria Gitman earned her Ph.D. under my supervision at the CUNY Graduate Center in June, 2007.  For her dissertation work, Victoria had chosen a very difficult problem, the 1962 question of Dana Scott to characterize the standard systems of models of Peano Arithmetic, a question in the field of models of arithmetic that had been open for over forty years. Victoria was able to make progress, now published in several papers, by using an inter-disciplinary approach, applying set-theoretic ideas—including a use of the proper forcing axiom PFA—to the problem in the area of models of arithmetic, where such methods hadn’t often yet arisen.  Ultimately, she showed under PFA that every arithmetically closed proper Scott set is the standard system of a model of PA.  This result extends the classical result to a large new family of Scott sets, providing for these sets an affirmative solution to Scott’s problem.  In other dissertation work, Victoria untangled the confusing mass of ideas surrounding various Ramsey-like large cardinal concepts, ultimately separating them into a beautiful hierarchy, a neighborhood of the vast large cardinal hierarchy intensely studied by set theorists.  (Please see the diagram in her dissertation.)  Victoria holds a tenure-track position at the New York City College of Technology of CUNY.

Victoria Gitman

web page | math genealogy | MathSciNet | ar$\chi$iv | google scholar | related posts

Victoria Gitman, “Applications of the Proper Forcing Axiom to Models of Peano Arithmetic,”  Ph.D. dissertation for the Graduate Center of the City University of New York, June 2007.

Abstract. In Chapter 1, new results are presented on Scott’s Problem in the subject of models of Peano Arithmetic. Some forty years ago, Dana Scott showed that countable Scott sets are exactly the countable standard systems of models of PA, and two decades later, Knight and Nadel extended his result to Scott sets of size $\omega_1$. Here it is shown that assuming the Proper Forcing Axiom, every arithmetically closed proper Scott set is the standard system of a model of PA. In Chapter 2, new large cardinal axioms, based on Ramsey-like embedding properties, are introduced and placed within the large cardinal hierarchy. These notions generalize the seldom encountered embedding characterization of Ramsey cardinals. I also show how these large cardinals can be used to obtain indestructibility results for Ramsey cardinals.

Every countable model of set theory embeds into its own constructible universe

Posted on by
19

[bibtex key=Hamkins2013:EveryCountableModelOfSetTheoryEmbedsIntoItsOwnL]

In this article, I prove that every countable model of set theory $\langle M,{\in^M}\rangle$, including every well-founded model, is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$. Another way to say this is that there is an embedding
$$j:\langle M,{\in^M}\rangle\to \langle L^M,{\in^M}\rangle$$
that is elementary for quantifier-free assertions in the language of set theory.

Main Theorem 1. Every countable model of set theory $\langle M,{\in^M}\rangle$ is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$.

The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading eventually to what I call the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, which is closely connected with the surreal numbers. The proof shows that $\langle L^M,{\in^M}\rangle$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$, and so in fact this model is universal for all countable acyclic binary relations of this rank. When $M$ is ill-founded, this includes all acyclic binary relations. The method of proof also establishes the following, thereby answering a question posed by Ewan Delanoy.

Main Theorem 2. The countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory $\langle M,{\in^M}\rangle$ and $\langle N,{\in^N}\rangle$, either $M$ is isomorphic to a submodel of $N$ or conversely. Indeed, the countable models of set theory are pre-well-ordered by embeddability in order type exactly $\omega_1+1$.

The proof shows that the embeddability relation on the models of set theory conforms with their ordinal heights, in that any two models with the same ordinals are bi-embeddable; any shorter model embeds into any taller model; and the ill-founded models are all bi-embeddable and universal.

The proof method arises most easily in finite set theory, showing that the nonstandard hereditarily finite sets $\text{HF}^M$ coded in any nonstandard model $M$ of PA or even of $I\Delta_0$ are similarly universal for all acyclic binary relations. This strengthens a classical theorem of Ressayre, while simplifying the proof, replacing a partial saturation and resplendency argument with a soft appeal to graph universality.

Main Theorem 3. If $M$ is any nonstandard model of PA, then every countable model of set theory is isomorphic to a submodel of the hereditarily finite sets $\langle \text{HF}^M,{\in^M}\rangle$ of $M$. Indeed, $\langle\text{HF}^M,{\in^M}\rangle$ is universal for all countable acyclic binary relations.

In particular, every countable model of ZFC and even of ZFC plus large cardinals arises as a submodel of $\langle\text{HF}^M,{\in^M}\rangle$. Thus, inside any nonstandard model of finite set theory, we may cast out some of the finite sets and thereby arrive at a copy of any desired model of infinite set theory, having infinite sets, uncountable sets or even large cardinals of whatever type we like.

The proof, in brief:  for every countable acyclic digraph, consider the partial order induced by the edge relation, and extend this order to a total order, which may be embedded in the rational order $\mathbb{Q}$.  Thus, every countable acyclic digraph admits a $\mathbb{Q}$-grading, an assignmment of rational numbers to nodes such that all edges point upwards. Next, one can build a countable homogeneous, universal, existentially closed $\mathbb{Q}$-graded digraph, simply by starting with nothing, and then adding finitely many nodes at each stage, so as to realize the finite pattern property. The result is a computable presentation of what I call the countable random $\mathbb{Q}$-graded digraph $\Gamma$.  If $M$ is any nonstandard model of finite set theory, then we may run this computable construction inside $M$ for a nonstandard number of steps.  The standard part of this nonstandard finite graph includes a copy of $\Gamma$.  Furthermore, since $M$ thinks it is finite and acyclic, it can perform a modified Mostowski collapse to realize the graph in the hereditary finite sets of $M$.  By looking at the sets corresponding to the nodes in the copy of $\Gamma$, we find a submodel of $M$ that is isomorphic to $\Gamma$, which is universal for all countable acyclic binary relations. So every model of ZFC isomorphic to a submodel of $M$.

The article closes with a number of questions, which I record here (and which I have also asked on mathoverflow:  Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?) Although the main theorem shows that every countable model of set theory embeds into its own constructible universe  $$j:M\to L^M,$$ this embedding $j$ is constructed completely externally to $M$ and there is little reason to expect that $j$ could be a class in $M$ or otherwise amenable to $M$.  To what extent can we prove or refute the possibility that $j$ is a class in $M$? This amounts to considering the matter internally as a question about $V$. Surely it would seem strange to have a class embedding $j:V\to L$ when $V\neq L$, even if it is elementary only for quantifier-free assertions, since such an embedding is totally unlike the sorts of embeddings that one usually encounters in set theory. Nevertheless, I am at a loss to refute the hypothesis, and the possibility that there might be such an embedding is intriguing, if not tantalizing, for one imagines all kinds of constructions that pull structure from $L$ back into $V$.

Question 1.  Can there be an embedding $j:V\to L$ when $V\neq L$?

By embedding, I mean an isomorphism from $\langle V,{\in}\rangle$ to its range in $\langle L,{\in}\rangle$, which is the same as a quantifier-free-elementary map $j:V\to L$. The question is most naturally formalized in Gödel-Bernays set theory, asking whether there can be a GB-class $j$ forming such an embedding.  If one wants $j:V\to L$ to be a definable class, then this of course implies $V=\text{HOD}$, since the definable $L$-order can be pulled back to $V$, via $x\leq y\iff j(s)\leq_L j(y)$. More generally, if $j$ is merely a class in Gödel-Bernays set theory, then the existence of an embedding $j:V\to L$ implies global choice, since from the class $j$ we can pull back the $L$-order. For these reasons, we cannot expect every model of ZFC or of GB to have such embeddings. Can they be added generically? Do they have some large cardinal strength? Are they outright refutable?

It they are not outright refutable, then it would seem natural that these questions might involve large cardinals; perhaps $0^\sharp$ is relevant. But I am unsure which way the answers will go. The existence of large cardinals provides extra strength, but may at the same time make it harder to have the embedding, since it pushes $V$ further away from $L$. For example, it is conceivable that the existence of $0^\sharp$ will enable one to construct the embedding, using the Silver indiscernibles to find a universal submodel of $L$; but it is also conceivable that the non-existence of $0^\sharp$, because of covering and the corresponding essential closeness of $V$ to $L$, may make it easier for such a $j$ to exist. Or perhaps it is simply refutable in any case. The first-order analogue of the question is:

Question 2.  Does every set $A$ admit an embedding $j:\langle A,{\in}\rangle \to \langle L,{\in}\rangle$?  If not, which sets do admit such embeddings?

The main theorem shows that every countable set $A$ embeds into $L$. What about uncountable sets? Let us make the question extremely concrete:

Question 3. Does $\langle V_{\omega+1},{\in}\rangle$ embed into $\langle L,{\in}\rangle$? How about $\langle P(\omega),{\in}\rangle$ or $\langle\text{HC},{\in}\rangle$?

It is also natural to inquire about the nature of $j:M\to L^M$ even when it is not a class in $M$. For example, can one find such an embedding for which $j(\alpha)$ is an ordinal whenever $\alpha$ is an ordinal?  The embedding arising in the proof of the main theorem definitely does not have this feature.

Question 4. Does every countable model $\langle M,{\in^M}\rangle$ of set theory admit an embedding $j:M\to L^M$ that takes ordinals to ordinals?

Probably one can arrange this simply by being a bit more careful with the modified Mostowski procedure in the proof of the main theorem.  And if this is correct, then numerous further questions immediately come to mind, concerning the extent to which we ensure more attractive features for the embeddings $j$ that arise in the main theorems. This will be particularly interesting in the case of well-founded models, as well as in the case of $j:V\to L$, as in question , if that should be possible.

Question 5. Can there be a nontrivial embedding $j:V\to L$ that takes ordinals to ordinals?

Finally, I inquire about the extent to which the main theorems of the article can be extended from the countable models of set theory to the $\omega_1$-like models:

Question 6. Does every $\omega_1$-like model of set theory $\langle M,{\in^M}\rangle$ admit an embedding $j:M\to L^M$ into its own constructible universe? Are the $\omega_1$-like models of set theory linearly pre-ordered by embeddability?

The countable models of ZFC, up to isomorphism, are linearly pre-ordered by the submodel relation; indeed, every countable model of ZFC, including every transitive model, is isomorphic to a submodel of its own $L$, New York, 2012

Posted on by
4

This will be a talk on May 18, 2012 for the CUNY Logic Workshop on some extremely new work. The proof uses finitary digraph combinatorics, including the countable random digraph and higher analogues involving uncountable Fraisse limits, the surreal numbers and the hypnagogic digraph.

The story begins with Ressayre’s remarkable 1983 result that if $M$ is any nonstandard model of PA, with $\langle\text{HF}^M,{\in^M}\rangle$ the corresponding nonstandard hereditary finite sets of $M$, then for any consistent computably axiomatized theory $T$ in the language of set theory, with $T\supset ZF$, there is a submodel $N\subset\langle\text{HF}^M,{\in^M}\rangle$ such that $N\models T$. In particular, one may find models of ZFC or even ZFC + large cardinals as submodels of $\text{HF}^M$, a land where everything is thought to be finite. Incredible! Ressayre’s proof uses partial saturation and resplendency to prove that one can find the submodel of the desired theory $T$.

My new theorem strengthens Ressayre’s theorem, while simplifying the proof, by removing the theory $T$. We need not assume $T$ is computable, and we don’t just get one model of $T$, but rather all models—the fact is that the nonstandard models of set theory are universal for all countable acyclic binary relations. So every model of set theory is a submodel of $\langle\text{HF}^M,{\in^M}\rangle$.

Theorem.(JDH) Every countable model of set theory is isomorphic to a submodel of any nonstandard model of finite set theory. Indeed, every nonstandard model of finite set theory is universal for all countable acyclic binary relations.

The proof involves the construction of what I call the countable random $\mathbb{Q}$-graded digraph, a countable homogeneous acyclic digraph that is universal for all countable acyclic digraphs, and proving that it is realized as a submodel of the nonstandard model $\langle M,\in^M\rangle$. Having then realized a universal object as a submodel, it follows that every countable structure with an acyclic binary relation, including every countable model of ZFC, is realized as a submodel of $M$.

The proof, in brief:  for every countable acyclic digraph, consider the partial order induced by the edge relation, and extend this order to a total order, which may be embedded in the rational order $\mathbb{Q}$.  Thus, every countable acyclic digraph admits a $\mathbb{Q}$-grading, an assignmment of rational numbers to nodes such that all edges point upwards. Next, one can build a countable homogeneous, universal, existentially closed $\mathbb{Q}$-graded digraph, simply by starting with nothing, and then adding finitely many nodes at each stage, so as to realize the finite pattern property. The result is a computable presentation of what I call the countable random $\mathbb{Q}$-graded digraph $\Gamma$.  If $M$ is any nonstandard model of finite set theory, then we may run this computable construction inside $M$ for a nonstandard number of steps.  The standard part of this nonstandard finite graph includes a copy of $\Gamma$.  Furthermore, since $M$ thinks it is finite and acyclic, it can perform a modified Mostowski collapse to realize the graph in the hereditary finite sets of $M$.  By looking at the sets corresponding to the nodes in the copy of $\Gamma$, we find a submodel of $M$ that is isomorphic to $\Gamma$, which is universal for all countable acyclic binary relations. So every model of ZFC isomorphic to a submodel of $M$.

The proof idea adapts, with complications, to the case of well-founded models, via the countable random $\lambda$-graded digraph, as well as the internal construction of what I call the hypnagogic digraph, a proper class homogeneous surreal-numbers-graded digraph, which is universal for all class acyclic digraphs.

Theorem.(JDH) Every countable model $\langle M,\in^M\rangle$ of ZFC, including the transitive models, is isomorphic to a submodel of its own constructible universe $\langle L^M,\in^M\rangle$. In other words, there is an embedding $j:M\to L^M$ that is quantifier-free-elementary.

The proof is guided by the idea of finding a universal submodel inside $L^M$. The embedding $j$ is constructed completely externally to $M$.

Corollary.(JDH) The countable models of ZFC are linearly ordered and even well-ordered, up to isomorphism, by the submodel relation. Namely, any two countable models of ZFC with the same well-founded height are bi-embeddable as submodels of each other, and all models embed into any nonstandard model.

The work opens up numerous questions on the extent to which we may expect in ZFC that $V$ might be isomorphic to a subclass of $L$. To what extent can we expect to have or to refute embeddings $j:V\to L$, elementary for quantifier-free assertions?

Article | CUNY Logic Workshop