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 βŠ† as the primary fundamental relation, rather than the membership ∈ 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 βŸ¨π‘‰, ∈⟩, there is a definable relation βˆˆβˆ—, different from ∈, such that βŸ¨π‘‰, βˆˆβˆ—βŸ© is a model of set theory, in fact isomorphic to the original universe βŸ¨π‘‰, ∈⟩, for which the corresponding inclusion relation π‘’βŠ†βˆ—π‘£βŸΊβˆ€π‘Žβ‘(π‘Žβˆˆβˆ—π‘’β†’π‘Žβˆˆβˆ—π‘£) is identical to the usual inclusion relation 𝑒 βŠ†π‘£.

Proof. Let πœƒ :𝑉 →𝑉 be any definable non-identity permutation of the universe, and let 𝜏 :𝑒 β†¦πœƒβ‘[𝑒] ={ πœƒβ‘(π‘Ž) βˆ£π‘Ž βˆˆπ‘’ } be the function determined by pointwise image under πœƒ. Since πœƒ is bijective, it follows that 𝜏 is also a bijection of 𝑉 to 𝑉, since every set is the πœƒ-image of a unique set. Furthermore, 𝜏 is an automorphism of βŸ¨π‘‰, βŠ†βŸ©, since π‘’βŠ†π‘£βŸΊπœƒβ‘[𝑒]βŠ†πœƒβ‘[𝑣]⟺𝜏⁑(𝑒)βŠ†πœβ‘(𝑣). 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 βŠ† automorphisms of the universe. Note that since 𝜏⁑({π‘Ž}) ={πœƒβ‘(π‘Ž)}, it follows that any instance of nontriviality πœƒβ‘(π‘Ž) β‰ π‘Ž in πœƒ leads immediately to an instance of nontriviality in 𝜏.

Using the map 𝜏, define π‘Ž βˆˆβˆ—π‘ ⟺ 𝜏⁑(π‘Ž) ∈𝜏⁑(𝑏). By definition, therefore, 𝜏 is an isomorphism of βŸ¨π‘‰, βˆˆβˆ—βŸ© β‰…βŸ¨π‘‰, ∈⟩. Let us show that βˆˆβˆ— β‰ βˆˆ. Since πœƒ is nontrivial, there is an ∈-minimal set π‘Ž with πœƒβ‘(π‘Ž) β‰ π‘Ž. By minimality, πœƒβ‘[π‘Ž] =π‘Ž and so 𝜏⁑(π‘Ž) =π‘Ž. But as mentioned, 𝜏⁑({π‘Ž}) ={πœƒβ‘(π‘Ž)} β‰ {π‘Ž}. So we have π‘Ž ∈{π‘Ž}, but 𝜏⁑(π‘Ž) =π‘Ž βˆ‰{πœƒβ‘(π‘Ž)} =𝜏⁑({π‘Ž}) and hence π‘Ž βˆ‰βˆ—{π‘Ž}. So the two relations are different.

Meanwhile, consider the corresponding subset relation. Specifically, 𝑒 βŠ†βˆ—π‘£ is defined to mean βˆ€π‘Ž ⁑(π‘Ž βˆˆβˆ—π‘’ β†’π‘Ž βˆˆβˆ—π‘£), which holds if and only if βˆ€π‘Ž ⁑(𝜏⁑(π‘Ž) ∈𝜏⁑(𝑒) β†’πœβ‘(π‘Ž) ∈𝜏⁑(𝑣)); but since 𝜏 is surjective, this holds if and only if 𝜏⁑(𝑒) βŠ†πœβ‘(𝑣), which as we observed at the beginning of the proof, holds if and only if 𝑒 βŠ†π‘£. So the corresponding subset relations βŠ†βˆ— and βŠ† are identical, as desired.

Another way to express what is going on is that 𝜏 is an isomorphism of the structure βŸ¨π‘‰, βˆˆβˆ—, βŠ†βŸ© with βŸ¨π‘‰, ∈, βŠ†βŸ©, and so βŠ† is in fact that same as the corresponding inclusion relation βŠ†βˆ— that one would define from βˆˆβˆ—QED

Corollary. One cannot define ∈ from βŠ† in a model of set theory.

Proof. The map 𝜏 is a βŠ†-automorphism, and so it preserves every relation definable from βŠ†, but it does not preserve ∈. QED

Nevertheless, I claim that the isomorphism type of βŸ¨π‘‰, ∈⟩ is implicit in the inclusion relation βŠ†, in the sense that any other class relation βˆˆβˆ— having that same inclusion relation is isomorphic to the ∈ relation.

Theorem. Assume ZFC in the universe βŸ¨π‘‰, ∈⟩. Suppose that βˆˆβˆ— is a class relation for which βŸ¨π‘‰, βˆˆβˆ—βŸ© is a model of set theory (a weak set theory suffices), such that the corresponding inclusion relation π‘’βŠ†βˆ—π‘£βŸΊβˆ€π‘Žβ‘(π‘Žβˆˆβˆ—π‘’β†’π‘Žβˆˆβˆ—π‘£)is the same as the usual inclusion relation 𝑒 βŠ†π‘£. Then the two membership relations are isomorphic βŸ¨π‘‰,βˆˆβŸ©β‰…βŸ¨π‘‰,βˆˆβˆ—βŸ©.

Proof. Since the singleton set {π‘Ž} has exactly two subsets with respect to the usual βŠ† relation β€” the empty set and itself β€” this must also be true with respect to the inclusion relation βŠ†βˆ— defined via βˆˆβˆ—, since we have assumed βŠ†βˆ— =βŠ†. Thus, the object {π‘Ž} is also a singleton with respect to βˆˆβˆ—, and so there is a unique object πœ‚β‘(π‘Ž) such that π‘₯ βˆˆβˆ—π‘Ž ⟺ π‘₯ =πœ‚β‘(π‘Ž). By extensionality and since every object has its singleton, it follows that πœ‚ :𝑉 →𝑉 is both one-to-one and onto. Let πœƒ =πœ‚βˆ’1 be the inverse permutation.

Observe that π‘Ž βˆˆπ‘’ ⟺ {π‘Ž} βŠ†π‘’ ⟺ {π‘Ž} βŠ†βˆ—π‘’ ⟺ πœ‚β‘(π‘Ž) βˆˆβˆ—π‘’. Thus, π‘βˆˆβˆ—π‘’βŸΊπœƒβ‘(𝑏)βˆˆπ‘’.

Using ∈-recursion, define π‘βˆ— ={ πœƒβ‘(π‘Žβˆ—) βˆ£π‘Ž βˆˆπ‘ }. The map 𝑏 β†¦π‘βˆ— is one-to-one by ∈-recursion, since if there is no violation of this for the elements of 𝑏, then we may recover 𝑏 from π‘βˆ— by applying πœƒβˆ’1 to the elements of π‘βˆ— and then using the induction assumption to find the unique π‘Ž from π‘Žβˆ— for each πœƒβ‘(π‘Žβˆ—) βˆˆπ‘βˆ—, thereby recovering 𝑏. So 𝑏 β†¦π‘βˆ— is injective.

I claim that this map is also surjective. If 𝑦0 β‰ π‘βˆ— for any π‘, then there must be an element of 𝑦0 that is not of the form πœƒβ‘(π‘βˆ—) for any 𝑏. Since πœƒ is surjective, this means there is πœƒβ‘(𝑦1) βˆˆπ‘¦0 with 𝑦1 β‰ π‘βˆ— for any π‘. Continuing, there is 𝑦𝑛+1 with πœƒβ‘(𝑦𝑛+1) βˆˆπ‘¦π‘› and 𝑦𝑛+1 β‰ π‘βˆ— for any 𝑏. Let 𝑧 ={ πœƒβ‘(𝑦𝑛) βˆ£π‘› βˆˆπœ” }. Since π‘₯ βˆˆβˆ—π‘’ ⟺ πœƒβ‘(π‘₯) βˆˆπ‘’, it follows that the βˆˆβˆ—-elements of 𝑧 are precisely the 𝑦𝑛’s. But πœƒβ‘(𝑦𝑛+1) βˆˆπ‘¦π‘›, and so π‘¦π‘›+1 βˆˆβˆ—π‘¦π‘›. So 𝑧 has no βˆˆβˆ—-minimal element, violating the axiom of foundation for βˆˆβˆ—, a contradiction. So the map 𝑏 β†¦π‘βˆ— is a bijection of 𝑉 with 𝑉.

Finally, we observe that because π‘Žβˆˆπ‘βŸΊπœƒβ‘(π‘Žβˆ—)βˆˆπ‘βˆ—βŸΊπ‘Žβˆ—βˆˆβˆ—π‘βˆ—, it follows that the map 𝑏 β†¦π‘βˆ— is an isomorphism of βŸ¨π‘‰, ∈⟩ with βŸ¨π‘‰, βˆˆβˆ—βŸ©, as desired. QED

The conclusion is that although ∈ is not definable from βІ, nevertheless, the isomorphism type of ∈ is implicit in βŠ†, in the sense that any other class relation βˆˆβˆ— giving rise to the same inclusion relation  βŠ†βˆ— =βŠ† is isomorphic to ∈.

Meanwhile, I do not yet know what the situation is when one drops the assumption that βˆˆβˆ— is a class with respect to the βŸ¨π‘‰, ∈⟩ universe.

Question. Can there be two models of set theory βŸ¨π‘€, ∈⟩ and βŸ¨π‘€, βˆˆβˆ—βŸ©, not necessarily classes with respect to each other, which have the same inclusion relation βŠ†= βŠ†βˆ—, but which are not isomorphic?

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