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.)

11 thoughts on “Different models of set theory with the same subset relation

  1. Your corollary reminds me of the hole paradox (http://ncatlab.org/nlab/show/hole+argument), which plagued early ideas about representing spacetime by a manifold. In that case, one was trying to think of a point as being ignored by the diffeomorphism of the spacetime manifold and find that lo and behold, the metric at that point is different before and after the diffeomorphism.

    If you wrote your construction as a class isomorphism \theta V,\in \to W,\epsilon, and carried across the subset relation you’d see the analogy with the resolution of the hole paradox. There (i.e. on the nLab page, in the section ‘Discussion’) one uses *two* isomorphisms, where before one had merely the identity map and an automorphism. How would this look for your setup?

    • David, thanks for this comment, which I find very interesting. You ask what it would look like, and I think it would just be that when you have an isomorphism $\varphi:\langle V,\subseteq\rangle\cong \langle W,\subseteq’\rangle$, then since we also have $\in$ on $V$, we can impose the induced $\in’$ on $W$ that corresponds in just that way. That is, we would define $\varphi(x)\in’\varphi(y)$ just in case $x\in y$. This would make $\varphi$ an isomorphism of $\langle V,\in,\subseteq\rangle$ with $\langle W,\in’,\subseteq’\rangle$, and it would mean that $\subseteq’$ is induced from $\in’$ in just exactly the isomorphic way that $\subseteq$ is induced from $\in$. In my application (the first part of the post), we have $V=W$ and $\varphi=\tau$, with $\subseteq’=\subseteq$. So the inclusion relation $\subseteq$ is induced from $\in$ and also from $\in^*$ defined in that way.

      Incidentally, I’ve now added a stronger result to the post, showing that if another class relation $\in^*$ has the same inclusion relation as $\in$, then in fact $\langle V,\in\rangle$ and $\langle V,\in^*\rangle$ are isomorphic. Thus, although the set-membership relation is not definable from inclusion, nevertheless the isomorphism type of it is implicitly definable.

      • Thanks for the updated version, Joel, that’s not unexpected. In a sense the models of set theory are indistinguishable, up to the issue about \in* being a class. What if it has been induced by some class permutation of the usual \in? I don’t know off the top of my head whether the usual \in is a class or not.

        • Most permutations of the universe will not be subset-preserving, but if you modify them to act as I do in the first part of the answer, then you get an isomorphic copy of the universe with respect to \in, which has the same induced \subset relation, which is therefore an automorphism with respect to \subset. The converse is almost true, in the sense that if you have another \in* relation with the same \subset relation, then it is precisely such an isomorphic copy of \in, provided that you can undertake set-theoretic constructions with \in and \in* simultaneously (which is what the class issue is about).

  2. Domo Arigato for bringing up this subject! 🙂

    I still think about the maaning behind your very interesting answer to my MathOverflow question:

    http://mathoverflow.net/questions/144231/is-the-inclusion-version-of-kunen-inconsistency-theorem-true

    In my opinion the corollary stating that one can’t define $\subseteq$ using $\in$ in a model of set theory has a very deep philosophical content related to the following philosophical questions:

    Q1- What is the most “fundamental” mathematical object?

    Q2- What is the most “fundamental” mathematical relation?

    Set theorists usually claim that the answer to the questions 1 and 2 are “set” and “membership” respectively because using these two very simple notions one can build all other mathematical objects and relations.

    But this seems an insufficient reasoning for such a big claim. Maybe we can generate all existing mathematical objects and relations (and even more new things) using another “fundamental” concepts.

    Anyway in order to answer the above questions we first need to clarify what we mean by “fundamental”. Maybe the definability provides a nice ground for defining “fundamentality” in the sense that if an object or relation is definable from another then it is less fundamental.

    Thus the above corollary indicates that “from ZFC’s perspective $\in$ is a more fundamental relation than $\subseteq$ because one can define $\subseteq$ from $\in$ but not vice versa”.

    This may look like strange because $\subseteq$ seems a more “intuitive” and “natural” relation than $\in$ if we notice that in the “real world” we can compare “objects of the same sort” via $\subseteq$ but this is not the case while talking about $\in$.

    For example when we say that the set of students is included in the set of academicians both these “objects” are of the same sort namely being the “set of humans”. But when we say Ali belongs to the set of academicians, Ali and the set of academicians are of two different sorts namely “humans” and “set of humans”.

    It would be an interesting investigation to characterize all fundamental binary relations of mathematics (and other relations) in an approach similar to above argument via “definability strength”, namely determining those relations that could be defined from each other. Specially finding some possible binary relations that are provably different from $\in$ but equi-fundamental with it could be interesting. By equi-fundamental I mean those which can define $\in$.

    It is also interesting that investigating such questions can lead one to very deep questions about rigidity of the structure $\langle V, E\rangle$ under different binary relations and in general to the structure of $Aut(\langle V, E\rangle)$ and $Eem(\langle V, E\rangle)$, the classes of automorphisms and self-elementary embeddings of the universe respectively.

    Finally I think this line of thinking may give us a better intuition about the best formulation for “foundation of mathematics” and in fact finding an answer to the below question:

    Q3- Did we formulate our axioms of mathematics in the best possible way using the most “fundamental” objects and relations or there could be some other interesting and more “intuitive” concepts and formulations?

  3. Pingback: Set-theoretic mereology: the theory of the subset relation is decidable | Joel David Hamkins

  4. Hey Dr. Hamkins! Super interesting result. Question: I’m still a bit confused as to why we can’t just define \in, given \subseteq, by x \in y iff {x} \subseteq y. What exactly is failing given this ‘definition’ of \in ?

    Thanks for your time!
    Tom

    • Thanks for your comment. For your definition, you have used the object $\{x\}$, and not merely $x$ and $y$. So for this definition to succeed in defining $\in$ from $\subseteq$, you need to define the object $\{x\}$ using only $x$ and $y$ and the subset relation. How do you do this? In fact, my result shows that you cannot.

      • Oh ok, I understand now. I’m a bit new to the subject, so I didn’t know (or have forgotten if I read it) that defining ∈ from ⊆ meant you could only use x and y. Thanks!

  5. Let me add that your joint work with Makoto is also mentioned in the following philosophical paper of Gruszczynski and Varzi, “Mereology Then and Now”:

    http://apcz.pl/czasopisma/index.php/LLP/article/view/LLP.2015.024

    [Quoted from paper]

    … The contribution by Joel David Hamkins and Makoto Kikuchi in Part II of the present collection, in which they investigate the consequences of taking set inclusion, $\subseteq$, as the primary fundamental set-theoretic notion in place of set membership, $\in$, is indicative of how much work can still be done in this direction.

  6. Pingback: Set-theoretic mereology | Joel David Hamkins

Leave a Reply

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