Tag Archives: embeddability

Paul K. Gorbow, PhD 2018, University of Gothenburg

Posted on by
Reply

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!

University of Gothenburg profile |  ar$\chi$iv | Research Gate

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.

Universality and embeddability amongst the models of set theory, CTFM 2015, Tokyo, Japan

Posted on by
2

Tokyo Institute of TechnologyThis will be a talk for the Computability Theory and Foundations of Mathematics conference at the Tokyo Institute of Technology, September 7-11, 2015.  The conference is held in celebration of Professor Kazuyuki Tanaka’s 60th birthday.

Abstract. Recent results on the embeddability phenomenon and universality amongst the models of set theory are an appealing blend of ideas from set theory, model theory and computability theory. Central questions remain open.

A surprisingly vigorous embeddability phenomenon has recently been uncovered amongst the countable models of set theory. It turns out, for instance, that among these models embeddability is linear: for any two countable models of set theory, one of them embeds into the other. Indeed, one countable model of set theory $M$ embeds into another $N$ just in case the ordinals of $M$ order-embed into the ordinals of $N$. This leads to many surprising instances of embeddability: every forcing extension of a countable model of set theory, for example, embeds into its ground model, and every countable model of set theory, including every well-founded model, embeds into its own constructible universe.

V to LAlthough the embedding concept here is the usual model-theoretic embedding concept for relational structures, namely, a map $j:M\to N$ for which $x\in^M y$ if and only if $j(x)\in^N j(y)$, it is a weaker embedding concept than is usually considered in set theory, where embeddings are often elementary and typically at least $\Delta_0$-elementary. Indeed, the embeddability result is surprising precisely because we can easily prove that in many of these instances, there can be no $\Delta_0$-elementary embedding.

The proof of the embedding theorem makes use of universality ideas in digraph combinatorics, including an acyclic version of the countable random digraph, the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraïssé limits, leading to the hypnagogic digraph, a universal homogeneous graded acyclic class digraph, closely connected with the surreal numbers. Thus, the methods are a blend of ideas from set theory, model theory and computability theory.

Results from Incomparable $\omega_1$-like models of set theory show that the embedding phenomenon does not generally extend to uncountable models. Current joint work of myself, Aspero, Hayut, Magidor and Woodin is concerned with questions on the extent to which the embeddings arising in the embedding theorem can exist as classes inside the models in question. Since the embeddings of the theorem are constructed externally to the model, by means of a back-and-forth-style construction, there is little reason to expect, for example, that the resulting embedding $j:M\to L^M$ should be a class in $M$. Yet, it has not yet known how to refute in ZFC the existence of a class embedding $j:V\to L$ when $V\neq L$. However, many partial results are known. For example, if the GCH fails at an uncountable cardinal, if $0^\sharp$ exists, or if the universe is a nontrivial forcing extension of some ground model, then there is no embedding $j:V\to L$. Meanwhile, it is consistent that there are non-constructible reals, yet $\langle P(\omega),\in\rangle$ embeds into $\langle P(\omega)^L,\in\rangle$.

CFTM 2015 extended abstract | Article | CFTM | Slides

The hypnagogic digraph, with applications to embeddings of the set-theoretic universe, JMM Special Session on Surreal Numbers, Seattle, January 2016

Posted on by
1

JMM 2016 SeattleThis will be an invited talk for the AMS-ASL special session on Surreal Numbers at the 2016 Joint Mathematics Meetings in Seattle, Washington, January 6-9, 2016.

Abstract. The hypnagogic digraph, a proper-class analogue of the countable random $\mathbb{Q}$-graded digraph, is a surreal-numbers-graded acyclic digraph exhibiting the set-pattern property (a form of existential-closure), making it set-homogeneous and universal for all class acyclic digraphs. A natural copy of this canonical structure arises during the course of the usual construction of the surreal number line, using as vertices the surreal-number numerals $\{\ A \mid B\ \}$.  I shall explain the construction and elementary theory of the hypnagogic digraph and describe recent uses of it in connection with embeddings of the set-theoretic universe, such as in the proof that the countable models of set theory are linearly pre-ordered by embeddability.

Slides | schedule | related article | surreal numbers (Wikipedia)

Embeddings of the universe into the constructible universe, current state of knowledge, CUNY Set Theory Seminar, March 2015

Posted on by
4

This will be a talk for the CUNY Set Theory Seminar, March 6, 2015.

I shall describe the current state of knowledge concerning the question of whether there can be an embedding of the set-theoretic universe into the constructible universe.

V to L

Question.(Hamkins) Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ into the constructible universe $L$, when $V\neq L$?

The notion of embedding here is merely that $$x\in y\iff j(x)\in j(y),$$ and such a map need not be elementary nor even $\Delta_0$-elementary. It is not difficult to see that there can generally be no $\Delta_0$-elementary embedding $j:V\to L$, when $V\neq L$.

Nevertheless, the question arises very naturally in the context of my previous work on the embeddability phenomenon, Every countable model of set theory embeds into its own constructible universe, where the title theorem is the following.

Theorem.(Hamkins) Every countable model of set theory $\langle M,\in^M\rangle$, including every countable transitive model of set theory, has an embedding $j:\langle M,\in^M\rangle\to\langle L^M,\in^M\rangle$ into its own constructible universe.

The methods of proof also established that the countable models of set theory are linearly pre-ordered by embeddability: given any two models, one of them embeds into the other; or equivalently, one of them is isomorphic to a submodel of the other. Indeed, one model $\langle M,\in^M\rangle$ embeds into another $\langle N,\in^N\rangle$ just in case the ordinals of the first $\text{Ord}^M$ order-embed into the ordinals of the second $\text{Ord}^N$. (And this implies the theorem above.)

In the proof of that theorem, the embeddings $j:M\to L^M$ are defined completely externally to $M$, and so it was natural to wonder to what extent such an embedding might be accessible inside $M$. And I realized that I could not generally refute the possibility that such a $j$ might even be a class in $M$.

Currently, the question remains open, but we have some partial progress, and have settled it in a number of cases, including the following, on which I’ll speak:

  • If there is an embedding $j:V\to L$, then for a proper class club of cardinals $\lambda$, we have $(2^\lambda)^V=(\lambda^+)^L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$ and indeed no embedding $j:P(\omega)\to L$.
  • If there is an embedding $j:V\to L$, then the GCH holds above $\aleph_0$.
  • In the forcing extension $V[G]$ obtained by adding $\omega_1$ many Cohen reals (or more), there is no embedding $j:V[G]\to L$, and indeed, no $j:P(\omega)^{V[G]}\to V$. More generally, after adding $\kappa^+$ many Cohen subsets to $\kappa$, for any regular cardinal $\kappa$, then in $V[G]$ there is no $j:P(\kappa)\to V$.
  • If $V$ is a nontrivial set-forcing extension of an inner model $M$, then there is no embedding $j:V\to M$. Indeed, there is no embedding $j:P(\kappa^+)\to M$, if the forcing has size $\kappa$. In particular, if $V$ is a nontrivial forcing extension, then there is no embedding $j:V\to L$.
  • Every countable set $A$ has an embedding $j:A\to L$.

This is joint work of myself, W. Hugh Woodin, Menachem Magidor, with contributions also by David Aspero, Ralf Schindler and Yair Hayut.

See my related MathOverflow question: Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?

Talk Abstract

Incomparable $\omega_1$-like models of set theory

Posted on by
1

[bibtex key=FuchsGitmanHamkins2017:IncomparableOmega1-likeModelsOfSetTheory]

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.