Different models of set theory with the same subset relation

OkonomiyakiRecently Makoto Kikuchi (Kobe University) asked me the following interesting question, which arises very naturally if one should adopt a mereological perspective in the foundations of mathematics, placing a focus on the parthood relation rather than the element-of relation. In set theory, this perspective would lead one to view the subset or inclusion relation $\subseteq$ as the primary fundamental relation, rather than the membership $\in$ relation.

Question. Can there be two different models of set theory, with the same inclusion relation?

We spent an evening discussing it, over delicious (Rokko-michi-style) okonomiyaki and bi-ru, just like old times, except that we are in Tokyo at the CTFM 2015, and I’d like to explain the answer, which is yes, this always happens in every model of set theory.

Theorem. In any universe of set theory $\langle V,\in\rangle$, there is a definable relation $\in^*$, different from $\in$, such that $\langle V,\in^*\rangle$ is a model of set theory, in fact isomorphic to the original universe $\langle V,\in\rangle$, for which the corresponding inclusion relation $$u\subseteq^* v\iff \forall a\, (a\in^* u\to a\in^* v)$$ is identical to the usual inclusion relation $u\subseteq v$.

Proof. Let $\theta:V\to V$ be any definable non-identity permutation of the universe, and let $\tau:u\mapsto \theta[u]=\{\ \theta(a)\mid a\in u\ \}$ be the function determined by pointwise image under $\theta$. Since $\theta$ is bijective, it follows that $\tau$ is also a bijection of $V$ to $V$, since every set is the $\theta$-image of a unique set. Furthermore, $\tau$ is an automorphism of $\langle V,\subseteq\rangle$, since $$u\subseteq v\iff\theta[u]\subseteq\theta[v]\iff\tau(u) \subseteq\tau(v).$$ I had used this idea a few years ago in my answer to the MathOverflow question, Is the inclusion version of Kunen inconsistency theorem true?, which shows that there are nontrivial $\subseteq$ automorphisms of the universe. Note that since $\tau(\{a\})=\{\theta(a)\}$, it follows that any instance of nontriviality $\theta(a)\neq a$ in $\theta$ leads immediately to an instance of nontriviality in $\tau$.

Using the map $\tau$, define $a\in^* b\iff\tau(a)\in\tau(b)$. By definition, therefore, $\tau$ is an isomorphism of $\langle V,\in^*\rangle\cong\langle V,\in\rangle$. Let us show that $\in^*\neq \in$. Since $\theta$ is nontrivial, there is an $\in$-minimal set $a$ with $\theta(a)\neq a$. By minimality, $\theta[a]=a$ and so $\tau(a)=a$. But as mentioned, $\tau(\{a\})=\{\theta(a)\}\neq\{a\}$. So we have $a\in\{a\}$, but $\tau(a)=a\notin\{\theta(a)\}=\tau(\{a\})$ and hence $a\notin^*\{a\}$. So the two relations are different.

Meanwhile, consider the corresponding subset relation. Specifically, $u\subseteq^* v$ is defined to mean $\forall a\,(a\in^* u\to a\in^* v)$, which holds if and only if $\forall a\, (\tau(a)\in\tau(u)\to \tau(a)\in\tau(v))$; but since $\tau$ is surjective, this holds if and only if $\tau(u)\subseteq \tau(v)$, which as we observed at the beginning of the proof, holds if and only if $u\subseteq v$. So the corresponding subset relations $\subseteq^*$ and $\subseteq$ are identical, as desired.

Another way to express what is going on is that $\tau$ is an isomorphism of the structure $\langle V,{\in^*},{\subseteq}\rangle$ with $\langle V,{\in},{\subseteq}\rangle$, and so $\subseteq$ is in fact that same as the corresponding inclusion relation $\subseteq^*$ that one would define from $\in^*$. QED

Corollary. One cannot define $\in$ from $\subseteq$ in a model of set theory.

Proof. The map $\tau$ is a $\subseteq$-automorphism, and so it preserves every relation definable from $\subseteq$, but it does not preserve $\in$. QED

Nevertheless, I claim that the isomorphism type of $\langle V,\in\rangle$ is implicit in the inclusion relation $\subseteq$, in the sense that any other class relation $\in^*$ having that same inclusion relation is isomorphic to the $\in$ relation.

Theorem. Assume ZFC in the universe $\langle V,\in\rangle$. Suppose that $\in^*$ is a class relation for which $\langle V,\in^*\rangle$ is a model of set theory (a weak set theory suffices), such that the corresponding inclusion relation $$u\subseteq^* v\iff\forall a\,(a\in^* u\to a\in^* v)$$is the same as the usual inclusion relation $u\subseteq v$. Then the two membership relations are isomorphic $$\langle V,\in\rangle\cong\langle V,\in^*\rangle.$$

Proof. Since the singleton set $\{a\}$ has exactly two subsets with respect to the usual $\subseteq$ relation — the empty set and itself — this must also be true with respect to the inclusion relation $\subseteq^*$ defined via $\in^*$, since we have assumed $\subseteq^*=\subseteq$. Thus, the object $\{a\}$ is also a singleton with respect to $\in^*$, and so there is a unique object $\eta(a)$ such that $x\in^* a\iff x=\eta(a)$. By extensionality and since every object has its singleton, it follows that $\eta:V\to V$ is both one-to-one and onto. Let $\theta=\eta^{-1}$ be the inverse permutation.

Observe that $a\in u\iff \{a\}\subseteq u\iff \{a\}\subseteq^* u\iff\eta(a)\in^* u$. Thus, $$b\in^* u\iff \theta(b)\in u.$$

Using $\in$-recursion, define $b^*=\{\ \theta(a^*)\mid a\in b\ \}$. The map $b\mapsto b^*$ is one-to-one by $\in$-recursion, since if there is no violation of this for the elements of $b$, then we may recover $b$ from $b^*$ by applying $\theta^{-1}$ to the elements of $b^*$ and then using the induction assumption to find the unique $a$ from $a^*$ for each $\theta(a^*)\in b^*$, thereby recovering $b$. So $b\mapsto b^*$ is injective.

I claim that this map is also surjective. If $y_0\neq b^*$ for any $b$, then there must be an element of $y_0$ that is not of the form $\theta(b^*)$ for any $b$. Since $\theta$ is surjective, this means there is $\theta(y_1)\in y_0$ with $y_1\neq b^*$ for any $b$. Continuing, there is $y_{n+1}$ with $\theta(y_{n+1})\in y_n$ and $y_{n+1}\neq b^*$ for any $b$. Let $z=\{\ \theta(y_n)\mid n\in\omega\ \}$. Since $x\in^* u\iff \theta(x)\in u$, it follows that the $\in^*$-elements of $z$ are precisely the $y_n$’s. But $\theta(y_{n+1})\in y_n$, and so $y_{n+1}\in^* y_n$. So $z$ has no $\in^*$-minimal element, violating the axiom of foundation for $\in^*$, a contradiction. So the map $b\mapsto b^*$ is a bijection of $V$ with $V$.

Finally, we observe that because $$a\in b\iff\theta(a^*)\in b^*\iff a^*\in^* b^*,$$ it follows that the map $b\mapsto b^*$ is an isomorphism of $\langle V,\in\rangle$ with $\langle V,\in^*\rangle$, as desired. QED

The conclusion is that although $\in$ is not definable from $\subseteq$, nevertheless, the isomorphism type of $\in$ is implicit in $\subseteq$, in the sense that any other class relation $\in^*$ giving rise to the same inclusion relation $\subseteq^*=\subseteq$ is isomorphic to $\in$.

Meanwhile, I do not yet know what the situation is when one drops the assumption that $\in^*$ is a class with respect to the $\langle V,\in\rangle$ universe.

Question. Can there be two models of set theory $\langle M,\in\rangle$ and $\langle M,\in^*\rangle$, not necessarily classes with respect to each other, which have the same inclusion relation $\subseteq=\subseteq^*$, but which are not isomorphic?

(This question is now answered! See my joint paper with Kikuchi at Set-theoretic mereology.)

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

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

A mathematician’s year in Japan

  • J. D. Hamkins, A Mathematician’s Year in Japan, author-published, via Amazon Kindle Direct Publishing, 2015. (ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2)  
    @BOOK{Hamkins2015:AMathematiciansYearInJapan,
    author = {Joel David Hamkins},
    title = {A {Mathematician's} {Year} in {Japan}},
    publisher = {author-published, via Amazon Kindle Direct Publishing},
    year = {2015},
    month = {March},
    url = {http://www.amazon.com/dp/B00U618LM2},
    note = {ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2},
    }

Years ago, when I was still a junior professor, I had the pleasure to live for a year in Japan, working as a research fellow at Kobe University. During that formative year, I recorded brief moments of my Japanese experience, and every two weeks or so—this was well before the current blogging era—I sent my descriptive missives by email to friends back home. I have now collected together those vignettes of my life in Japan, each a morsel of my experience. The book is now out!


A Mathematician's Year in Japan, by Joel David Hamkins, available on Amazon Kindle BooksA Mathematician’s Year in Japan
Joel David Hamkins

Glimpse into the life of a professor of logic as he fumbles his way through Japan.

A Mathematician’s Year in Japan is a lighthearted, though at times emotional account of how one mathematician finds himself in a place where everything seems unfamiliar, except his beloved research on the nature of infinity, yet even with that he experiences a crisis.

Available on Amazon $4.49.

Please be so kind as to write a review there.
jo eh ru

The set-theoretical multiverse: a natural context for set theory, Japan 2009

  • J. D. Hamkins, “The Set-theoretic Multiverse : A Natural Context for Set Theory,” Annals of the Japan Association for Philosophy of Science, vol. 19, pp. 37-55, 2011.  
    @article{Hamkins2011:TheMultiverse:ANaturalContext,
    author="Joel David Hamkins",
    title="The Set-theoretic Multiverse : A Natural Context for Set Theory",
    journal="Annals of the Japan Association for Philosophy of Science",
    ISSN="0453-0691",
    publisher="the Japan Association for Philosophy of Science",
    year="2011",
    volume="19",
    number="",
    pages="37--55",
    URL="http://ci.nii.ac.jp/naid/110008722567/en/",
    DOI="",
    }

This article is based on a talk I gave at the conference in honor of the retirement of Yuzuru Kakuda in Kobe, Japan, March 7, 2009. I would like to express my gratitude to Kakuda-sensei and the rest of the logic group in Kobe for the opportunities provided to me to participate in logic in Japan. In particular, my time as a JSPS Fellow in the logic group at Kobe University in 1998 was a formative experience. I was part of a vibrant research group in Kobe; I enjoyed Japanese life, learned to speak a little Japanese and made many friends. Mathematically, it was a productive time, and after years away how pleasant it is for me to see that ideas planted at that time, small seedlings then, have grown into tall slender trees.

Set theorists often take their subject as constituting a foundation for the rest of mathematics, in the sense that other abstract mathematical objects can be construed fundamentally as sets. In this way, they regard the set-theoretic universe as the universe of all mathematics. And although many set-theorists affirm the Platonic view that there is just one universe of all sets, nevertheless the most powerful set-theoretic tools developed over the past half century are actually methods of constructing alternative universes. With forcing and other methods, we can now produce diverse models of ZFC set theory having precise, exacting features. The fundamental object of study in set theory has thus become the model of set theory, and the subject consequently begins to exhibit a category-theoretic second-order nature. We have a multiverse of set-theoretic worlds, connected by forcing and large cardinal embeddings like constellations in a dark sky. In this article, I will discuss a few emerging developments illustrating this second-order nature. The work engages pleasantly with various philosophical views on the nature of mathematical existence.

Slides

 

Kobe University, JSPS Fellowship, 1998

An elegant meal in KobeI held a JSPS Fellowship from the Japan Society for the Promotion of Science at the Graduate School of Kobe University, in Kobe, Japan, from January to December, 1998.  I was a part of the Kobe University Logic Group, and Philip Welch served as my official mentor at that time.  Jörg Brendle started in Kobe at very nearly the same time.