Upward closure in the generic multiverse of a countable model of set theory, RIMS 2015, Kyoto, Japan

Philosophers Walk Kyoto Japan (summer)This will be a talk for the conference Recent Developments in Axiomatic Set Theory at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Japan, September 16-18, 2015.

Abstract. Consider a countable model of set theory amongst its forcing extensions, the ground models of those extensions, the extensions of those models and so on, closing under the operations of forcing extension and ground model.  This collection is known as the generic multiverse of the original model.  I shall present a number of upward-oriented closure results in this context. For example, for a long-known negative result, it is a fun exercise to construct forcing extensions $M[c]$ and $M[d]$ of a given countable model of set theory $M$, each by adding an $M$-generic Cohen real, which cannot be amalgamated, in the sense that there is no common extension model $N$ that contains both $M[c]$ and $M[d]$ and has the same ordinals as $M$. On the positive side, however, any increasing sequence of extensions $M[G_0]\subset M[G_1]\subset M[G_2]\subset\cdots$, by forcing of uniformly bounded size in $M$, has an upper bound in a single forcing extension $M[G]$. (Note that one cannot generally have the sequence $\langle G_n\mid n<\omega\rangle$ in $M[G]$, so a naive approach to this will fail.)  I shall discuss these and related results, many of which appear in the “brief upward glance” section of my recent paper:  G. Fuchs, J. D. Hamkins and J. Reitz, Set-theoretic geology.


The pluralist perspective on the axiom of constructibility, MidWest PhilMath Workshop, Notre Dame, October 2014

University of Notre DameThis will be a featured talk at the Midwest PhilMath Workshop 15, held at Notre Dame University October 18-19, 2014.  W. Hugh Woodin and I will each give one-hour talks in a session on Perspectives on the foundations of set theory, followed by a one-hour discussion of our talks.

Abstract. I shall argue that the commonly held $V\neq L$ via maximize position, which rejects the axiom of constructibility V = L on the basis that it is restrictive, implicitly takes a stand in the pluralist debate in the philosophy of set theory by presuming an absolute background concept of ordinal. The argument appears to lose its force, in contrast, on an upwardly extensible concept of set, in light of the various facts showing that models of set theory generally have extensions to models of V = L inside larger set-theoretic universes.

Set-theorists often argue against the axiom of constructibility V=L on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible. Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory. In this talk, I shall criticize Maddy’s proposal, pointing out that neither the fairly-interpreted-in relation nor the (strongly) maximizes-over relation is transitive, and furthermore, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s account, contrary to what had been desired. Ultimately, I shall argue that the V≠L via maximize position loses its force on a multiverse conception of set theory with an upwardly extensible concept of set, in light of the classical facts that models of set theory can generally be extended to models of V=L. I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Slides

Higher infinity and the foundations of mathematics, plenary General Public Lecture, AAAS, June, 2014

I have been invited to give a plenary General Public Lecture at the 95th annual meeting of the American Association for the Advancement of Science (Pacific Division), which will be held in Riverside, California, June 17-20, 2014.  The talk is sponsored by the BEST conference, which is meeting as a symposium at the larger AAAS conference.

This is truly a rare opportunity to communicate with a much wider community of scholars, to explain some of the central ideas and methods of set theory and the foundations of mathematics to a wider group of nonspecialist but mathematics-interested researchers. I hope to explain a little about the exciting goings-on in the foundations of mathematics.  Frankly, I feel deeply honored for the opportunity to represent my field in this way.

The talk will be aimed at a very general audience, the general public of the AAAS meeting, which is to say, mainly, scientists.  I also expect, however, that there will be a set-theory contingent present of participants from the BEST conference, which is a symposium at the conference — but I shall not take a stand here on whether mathematics is a science; you’ll have to come to my talk for that!

MissionInnPanoramaBestAbstract. Let me tell you the story of infinity and what is going on in the foundations of mathematics. For over a century, mathematicians have explored the soaring transfinite tower of different infinity concepts. Yet, fundamental questions at the foundation of this tower remain unsettled. Indeed, researchers in set theory and the foundations of mathematics have uncovered a pervasive independence phenomenon, whereby foundational mathematical questions are often in principle neither provable nor refutable. Presented with what may be these inherent limitations on our mathematical reasoning, we now face difficult philosophical questions on the nature of mathematical truth and the meaning of mathematical existence. Does mathematics need new axioms? Some mathematicians point the way the way towards what they describe as an ultimate theory of mathematical truth. Some adopt a scientific attitude, judging new mathematical axioms and theories by their predictions and explanatory power. Others propose a multiverse mathematical foundation with pluralist truth. In this talk, I shall take you from the basic concept of infinity and some simple paradoxes up to the continuum hypothesis and on to the higher infinity of large cardinals and the raging philosophical debates.

Slides | AAAS PD 2014 | Schedule | BEST | My other BEST talk

Satisfaction is not absolute

[bibtex key=HamkinsYang:SatisfactionIsNotAbsolute]$\newcommand\N{\mathbb{N}}\newcommand\satisfies{\models}$

Abstract. We prove that the satisfaction relation $\mathcal{N}\satisfies\varphi[\vec a]$ of first-order logic is not absolute between models of set theory having the structure $\mathcal{N}$ and the formulas $\varphi$ all in common. Two models of set theory can have the same natural numbers, for example, and the same standard model of arithmetic $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$, yet disagree on their theories of arithmetic truth; two models of set theory can have the same natural numbers and the same arithmetic truths, yet disagree on their truths-about-truth, at any desired level of the iterated truth-predicate hierarchy; 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 the same $\langle H_{\omega_2},{\in}\rangle$ or the same rank-initial segment $\langle V_\delta,{\in}\rangle$, yet disagree on which assertions are true in these structures.

On the basis of these mathematical results, we argue that a philosophical commitment to the determinateness of the theory of truth for a structure cannot be seen as a consequence solely of the determinateness of the structure in which that truth resides. The determinate nature of arithmetic truth, for example, is not a consequence of the determinate nature of the arithmetic structure $\N=\{ 0,1,2,\ldots\}$ itself, but rather, we argue, is an additional higher-order commitment requiring its own analysis and justification.

Many mathematicians and philosophers regard the natural numbers $0,1,2,\ldots\,$, along with their usual arithmetic structure, as having a privileged mathematical existence, a Platonic realm in which assertions have definite, absolute truth values, independently of our ability to prove or discover them. Although there are some arithmetic assertions that we can neither prove nor refute—such as the consistency of the background theory in which we undertake our proofs—the view is that nevertheless there is a fact of the matter about whether any such arithmetic statement is true or false in the intended interpretation. The definite nature of arithmetic truth is often seen as a consequence of the definiteness of the structure of arithmetic $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$ itself, for if the natural numbers exist in a clear and distinct totality in a way that is unambiguous and absolute, then (on this view) the first-order theory of truth residing in that structure—arithmetic truth—is similarly clear and distinct.

Feferman provides an instance of this perspective when he writes (Feferman 2013, Comments for EFI Workshop, p. 6-7) :

In my view, the conception [of the bare structure of the natural numbers] is completely clear, and thence all arithmetical statements are definite.

It is Feferman’s `thence’ to which we call attention.  Martin makes a similar point (Martin, 2012, Completeness or incompleteness of basic mathematical concepts):

What I am suggesting is that the real reason for confidence in first-order completeness is our confidence in the full determinateness of the concept of the natural numbers.

Many mathematicians and philosophers seem to share this perspective. The truth of an arithmetic statement, to be sure, does seem to depend entirely on the structure $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$, with all quantifiers restricted to $\N$ and using only those arithmetic operations and relations, and so if that structure has a definite nature, then it would seem that the truth of the statement should be similarly definite.

Nevertheless, in this article we should like to tease apart these two ontological commitments, arguing that the definiteness of truth for a given mathematical structure, such as the natural numbers, the reals or higher-order structures such as $H_{\omega_2}$ or $V_\delta$, does not follow from the definite nature of the underlying structure in which that truth resides. Rather, we argue that the commitment to a theory of truth for a structure is a higher-order ontological commitment, going strictly beyond the commitment to a definite nature for the underlying structure itself.

We make our argument in part by proving that different models of set theory can have a structure identically in common, even the natural numbers, yet disagree on the theory of truth for that structure.

Theorem.

  • Two models of set theory can have the same structure of arithmetic $$\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_1}=\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_2},$$yet disagree on the theory of arithmetic truth.
  • Two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree about whether it is a well-order.
  • Two models of set theory that have the same natural numbers and the same reals, yet disagree on projective truth.
  • Two models of set theory can have a transitive rank initial segment in common $$\langle V_\delta,{\in}\rangle^{M_1}=\langle V_\delta,{\in}\rangle^{M_2},$$yet disagree about whether it is a model of ZFC.

The proofs use only elementary classical methods, and might be considered to be a part of the folklore of the subject of models of arithmetic. The paper includes many further examples of the phenomenon, and concludes with a philosophical discussion of the issue of definiteness, concerning the question of whether one may deduce definiteness-of-truth from definiteness-of-objects and definiteness-of-structure.

 

Exploring the Frontiers of Incompleteness, Harvard, August 2013

I will be participating in the culminating workshop of the Exploring the Frontiers of Incompleteness conference series at Harvard University, to take place August 31-September 1, 2013.  Rather than conference talks, the program will consist of extended discussion sessions by the participants of the year-long series, with the discussion framed by very brief summary presentations.  Peter Koellner asked me to prepare such a presentation on the multiverse conception, and you can see the slides in The multiverse perspective in set theory (Slides).

My previous EFI talk was The multiverse perspective on determinateness in set theory, based in part on my paper The set-theoretical multiverse.

Pluralism in mathematics: the multiverse view in set theory and the question of whether every mathematical statement has a definite truth value, Rutgers, March 2013

This is a talk for the Rutgers Logic Seminar on March 25th, 2013.  Simon Thomas specifically requested that I give a talk aimed at philosophers.

Abstract.  I shall describe the debate on pluralism in the philosophy of set theory, specifically on the question of whether every mathematical and set-theoretic assertion has a definite truth value. A traditional Platonist view in set theory, which I call the universe view, holds that there is an absolute background concept of set and a corresponding absolute background set-theoretic universe in which every set-theoretic assertion has a final, definitive truth value. I shall try to tease apart two often-blurred aspects of this perspective, namely, to separate the claim that the set-theoretic universe has a real mathematical existence from the claim that it is unique. A competing view, the multiverse view, accepts the former claim and rejects the latter, by holding that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe, and a corresponding pluralism of set-theoretic truths. After framing the dispute, I shall argue that the multiverse position explains our experience with the enormous diversity of set-theoretic possibility, a phenomenon that is one of the central set-theoretic discoveries of the past fifty years and one which challenges the universe view. In particular, I shall argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for.

Some of this material arises in my recent articles:

On the axiom of constructibility and Maddy’s conception of restrictive theories, Logic Workshop, February 2013

This is a talk for the CUNY Logic Workshop on February 15, 2013.

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Set-theorists often argue against the axiom of constructibility $V=L$ on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible.  Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory.

In this talk, I shall criticize Maddy’s specific proposal.  For example, it turns out that the fairly-interpreted-in relation on theories is not transitive, and similarly the maximizes-over and strongly-maximizes-over relations are not transitive.  Further, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s proposal, although this is not what she had desired.

Ultimately, I argue that the $V\neq L$ via maximize position loses its force on a multiverse conception of set theory, in light of the classical facts that models of set theory can generally be extended to (taller) models of $V=L$.  In particular, every countable model of set theory is a transitive set inside a model of $V=L$.  I shall conclude the talk by explaining various senses in which $V=L$ remains compatible with strength in set theory.

Pluralism in set theory: does every mathematical statement have a definite truth value? GC Philosophy Colloquium, 2012

This will be my talk for the CUNY Graduate Center Philosophy Colloquium on November 28, 2012.

I will be speaking on topics from some of my recent articles:

I shall give a summary account of some current issues in the philosophy of set theory, specifically, the debate on pluralism and the question of the determinateness of set-theoretical and mathematical truth.  The traditional Platonist view in set theory, what I call the universe view, holds that there is an absolute background concept of set and a corresponding absolute background set-theoretic universe in which every set-theoretic assertion has a final, definitive truth value.  What I would like to do is to tease apart two often-blurred aspects of this perspective, namely, to separate the claim that the set-theoretic universe has a real mathematical existence from the claim that it is unique.  A competing view, which I call the multiverse view, accepts the former claim and rejects the latter, by holding that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe, and a corresponding pluralism of set-theoretic truths.  After framing the dispute, I shall argue that the multiverse position explains our experience with the enormous diversity of set-theoretic possibility, a phenomenon that is one of the central set-theoretic discoveries of the past fifty years and one which challenges the universe view. In particular, I shall argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for.

Slides

A multiverse perspective on the axiom of constructiblity

[bibtex key=Hamkins2014:MultiverseOnVeqL]

This article expands on an argument that I made during my talk at the Asian Initiative for Infinity: Workshop on Infinity and Truth, held July 25–29, 2011 at the Institute for Mathematical Sciences, National University of Singapore, and will be included in a proceedings volume that is being prepared for that conference.

Abstract. I argue that the commonly held $V\neq L$ via maximize position, which rejects the axiom of constructibility $V=L$ on the basis that it is restrictive, implicitly takes a stand in the pluralist debate in the philosophy of set theory by presuming an absolute background concept of ordinal. The argument appears to lose its force, in contrast, on an upwardly extensible concept of set, in light of the various facts showing that models of set theory generally have extensions to models of $V=L$ inside larger set-theoretic universes.

In section two, I provide a few new criticisms of Maddy’s proposed concept of `restrictive’ theories, pointing out that her concept of fairly interpreted in is not a transitive relation: there is a first theory that is fairly interpreted in a second, which is fairly interpreted in a third, but the first is not fairly interpreted in the third.  The same example (and one can easily construct many similar natural examples) shows that neither the maximizes over relation, nor the properly maximizes over relation, nor the strongly maximizes over relation is transitive.  In addition, the theory ZFC + “there are unboundedly many inaccessible cardinals” comes out as formally restrictive, since it is strongly maximized by the theory ZF + “there is a measurable cardinal, with no worldly cardinals above it.”

To support the main philosophical thesis of the article, I survey a series of mathemtical results,  which reveal various senses in which the axiom of constructibility $V=L$ is compatible with strength in set theory, particularly if one has in mind the possibility of moving from one universe of set theory to a much larger one.  Among them are the following, which I prove or sketch in the article:

Observation. The constructible universe $L$ and $V$ agree on the consistency of any constructible theory. They have models of the same constructible theories.

Theorem. The constructible universe $L$ and $V$ have transitive models of exactly the same constructible theories in the language of set theory.

Corollary. (Levy-Shoenfield absoluteness theorem)  In particular, $L$ and $V$ satisfy the same $\Sigma_1$ sentences, with parameters hereditarily countable in $L$. Indeed, $L_{\omega_1^L}$ and $V$ satisfy the same such sentences.

Theorem. Every countable transitive set is a countable transitive set in the well-founded part of an $\omega$-model of V=L.

Theorem. If there are arbitrarily large $\lambda<\omega_1^L$ with $L_\lambda\models\text{ZFC}$, then every countable transitive set $M$ is a countable transitive set inside a structure $M^+$  that is a pointwise-definable model of ZFC + V=L, and $M^+$ is well founded as high in the countable ordinals as desired.

Theorem. (Barwise)  Every countable model of  ZF has an end-extension to a model of ZFC + V=L.

Theorem. (Hamkins, see here)  Every countable model of set theory $\langle M,{\in^M}\rangle$, including every transitive model, 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$, which is elementary for quantifier-free assertions.

Another way to say this is that every countable model of set theory is a submodel of a model isomorphic to $L^M$. If we lived inside $M$, then by adding new sets and elements, our universe could be transformed into a copy of the constructible universe $L^M$.

(Plus, the article contains some nice diagrams.)

Related Singapore links:

Every countable model of set theory is isomorphic to a submodel of its own constructible universe, Barcelona, December, 2012

This will be a talk for a set theory workshop at the University of Barcelona on December 15, 2012, organized by Joan Bagaria.

Vestíbul Universitat de Barcelona

Abstract. Every countable model of set theory $M$, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding $j:M\to L^M$ that is elementary for quantifier-free assertions. 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 to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected with the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other.  Indeed, the bi-embeddability classes form a well-ordered chain of length $\omega_1+1$.  Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory $M$ is universal for all countable well-founded binary relations of rank at most $\text{Ord}^M$; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if $M$ is any nonstandard model of PA, then every countable model of set theory—in particular, every model of ZFC—is isomorphic to a submodel of the hereditarily finite sets $HF^M$ of $M$. Indeed, $HF^M$ is universal for all countable acyclic binary relations.

Article | Barcelona research group in set theory

A question for the mathematics oracle

At the Workshop on Infinity and Truth in Singapore last year, we had a special session in which the speakers were asked to imagine that they had been granted an audience with an all-knowing mathematical oracle, given the opportunity to ask a single yes-or-no question, to be truthfully answered.  These questions will be gathered together and published in the conference volume.  Here is my account.

 

A question for the mathematics oracle

Joel David Hamkins, The City University of New York

 

Granted an audience with an all-knowing mathematics oracle, we may ask a single yes-or-no question, to be truthfully answered……

I might mischievously ask the question my six-year-old daughter Hypatia often puts to our visitors:  “Answer yes or no.  Will you answer `no’?” They stammer, caught in the liar paradox, as she giggles. But my actual question is:

Are we correct in thinking we have an absolute concept of the finite?

An absolute concept of the finite underlies many mathematician’s understanding of the nature of mathematical truth. Most mathematicians, for example, believe that we have an absolute concept of the finite, which determines the natural numbers as a unique mathematical structure—$0,1,2,$ and so on—in which arithmetic assertions have definitive truth values. We can prove after all that the second-order Peano axioms characterize $\langle\mathbb{N},S,0\rangle$ as the unique inductive structure, determined up to isomorphism by the fact that $0$ is not a successor, the successor function $S$ is one-to-one and every set containing $0$ and closed under $S$ is the whole of $\mathbb{N}$. And to be finite means simply to be equinumerous with a proper initial segment of this structure. Doesn’t this categoricity proof therefore settle the matter?

I don’t think so. The categoricity proof, which takes place in set theory, seems to my way of thinking merely to push the absoluteness question for finiteness off to the absoluteness question for sets instead. And surely this is a murkier realm, where already mathematicians do not universally agree that we have a single absolute background concept of set. We know by forcing and other means how to construct alternative set concepts, which seem fully as legitimate and set-theoretic as the set concepts from which they are derived. Thus, we have a plurality of set concepts, and our confidence in a unique absolute set-theoretic background is weakened. How then can we sensibly base our confidence in an absolute concept of the finite on set theory? Perhaps this absoluteness is altogether illusory.

My worries are put to rest if the oracle should answer positively. A negative answer, meanwhile, would raise alarms. A negative answer could indicate, on the one hand, that our understanding of the finite is simply incoherent, a catastrophe, where our cherished mathematical theories are all inconsistent. But, more likely in my view, a negative answer could also mean that there is an undiscovered plurality of concepts of the finite. I imagine technical developments arising that would provide us with tools to modify the arithmetic of a model of set theory, for example, with the same power and flexibility that forcing currently allows us to modify higher-order features, while not providing us with any reason to prefer one arithmetic to another (unlike our current methods with non-standard models). The discovery of such tools would be an amazing development in mathematics and lead to radical changes in our conception of mathematical truth.

Let’s have some fun—please post your question for the oracle in the comment fields below.

A question for the math oracle (pdf) | My talk at the Workshop

Recent progress on the modal logic of forcing and grounds, CUNY Logic Workshop, September 2012

This will be a talk for the CUNY Logic Workshop on September 7, 2012.

Abstract. The modal logic of forcing arises when one considers a model of set theory in the context of all its forcing extensions, with “true in all forcing extensions” and“true in some forcing extension” as the accompanying modal operators. In this modal language one may easily express sweeping general forcing principles, such asthe assertion that every possibly necessary statement is necessarily possible, which is valid for forcing, orthe assertion that every possibly necessary statement is true, which is the maximality principle, a forcing axiom independent of but equiconsistent with ZFC.  Similarly, the dual modal logic of grounds concerns the modalities “true in all ground models” and “true in some ground model”.  In this talk, I shall survey the recent progress on the modal logic of forcing and the modal logic of grounds. This is joint work with Benedikt Loewe and George Leibman.

 

Moving up and down in the generic multiverse

[bibtex key=HamkinsLoewe2013:MovingUpAndDownInTheGenericMultiverse]

In this extended abstract we investigate the modal logic of the generic multiverse, which is a bimodal logic with operators corresponding to the relations “is a forcing extension of”‘ and “is a ground model of”. The fragment of the first relation is the modal logic of forcing and was studied by us in earlier work. The fragment of the second relation is the modal logic of grounds and will be studied here for the first time. In addition, we discuss which combinations of modal logics are possible for the two fragments.

The main theorems are as follows:

Theorem.  If  ZFC is consistent, then there is a model of  ZFC  whose modal logic of forcing and modal logic of grounds are both S4.2.

Theorem.  If  the theory “$L_\delta\prec L+\delta$ is inaccessible” is consistent, then there is a model of set theory whose modal logic of forcing is S4.2 and whose modal logic of grounds is S5.

Theorem.  If  the theory “$L_\delta\prec L+\delta$ is inaccessible” is consistent, then there is a model of set theory whose modal logic of forcing is S5 and whose modal logic of grounds is S4.2.

Theorem. There is no model of set theory such that both its modal logic of forcing and its modal logic of grounds are S5.

The current article is a brief extended abstract (10 pages).  A fuller account with more detailed proofs and further information will be provided in a subsequent articl

eprints:  ar$\chi$iv | NI12059-SAS | Hamburg #450

Every countable model of set theory embeds into its own constructible universe, Fields Institute, Toronto, August 2012

This will be a talk for the  Toronto set theory seminar at the Fields Institute, University of Toronto, on August 24, 2012.

Abstract.  Every countable model of set theory $M$, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding $j:M\to L^M$ that is elementary for quantifier-free assertions. 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 to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected Image: Igougo.comwith the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other.  Indeed, the bi-embeddability classes form a well-ordered chain of length $\omega_1+1$.  Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory $M$ is universal for all countable well-founded binary relations of rank at most $\text{Ord}^M$; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if $M$ is any nonstandard model of PA, then every countable model of set theory—in particular, every model of ZFC—is isomorphic to a submodel of the hereditarily finite sets $HF^M$ of $M$. Indeed, $HF^M$ is universal for all countable acyclic binary relations.

Article | my profile at set theory talks | Toronto Set Theory Seminar post