# An Exercise in Kunen (A Model for Foundation, Pairing,...)

This is exercise I.4.18 in Kunen's Set Theory.

Derive $\forall y (y \notin y)$ from the Axioms of Comprehension and Foundation. Don't use the Pairing or Extensionality Axioms. Then find a 2 element model for Foundation, Extensionality, Pairing, and Union, plus $\exists y \forall x (x \in y)$ (so of course, $y \in y$).

Hint. If $y \in y$ use Comprehension to form $x := \{y\}$; the fact that there may be more than one $x$ doesn't affect the proof.

My attempt:

Suppose for contradiction $\exists y (y \in y)$. Fix such a $y$. Let $x = \{z \in y \mid z = y\}$ so by Comprehension we have that $x = \{y\}$. But then we see that $y \in x$ and $y \in y$ contradicting the Foundation Axiom which says: $\exists y (y \in x) \implies \exists y (y \in x \wedge \neg\exists z (z \in x \wedge z \in y)$.

That part I didn't have too much trouble with, but I can't for the life of me figure out the second part of the question. Every configuration I make of two elements hasn't worked. I'm sure there is a very simple and obvious answer, so please let me know! This has stumped me for the last couple days!

Thanks!

• A minor gripe: in the first part, $x = \{z \in y \mid z = y\}$ is not a valid definition if you don't assume extensionality. It is, however, valid to take an (not the) $x$ such that its members are exactly the members of $y$ which are equal to $y$. The rest is okay. Jun 27, 2013 at 12:18
• @tomasz Just to clarify: you mean that I can't say $x = \{z \in y \mid z = y \}$ because such an $x$ may not be unique? Instead should I say: Let $x$ be one of the sets $\{z \in y \mid z = y\}$? Or is there a more correct way to say that? And is that why he says in the hint that there may be more than one such $x$? Jun 27, 2013 at 23:28
• I mean that the expression $\{z \in y \mid z = y\}$ is not defined without extensionality. That's kind of like square roots in complex numbers: a complex number certainly does have a square root, but there's no obvious choice of the square root in general, so $\sqrt i$, for instance, is undefined. Of course, in case of square root you can choose a principal value, and you could do the same for this separation instance, assuming some choice in the metatheory (and this is almost the same as picking an $x$ satisfying this "definition", for which you need no choice). Jun 28, 2013 at 1:15
• Ok thanks, I think I understand. So in the metatheory I can say "take an $x$ such that its members are exactly the members of $y$ which are equal to $y$" (as you wrote). But without extensionality it doesn't make sense to talk about the objects in the theory as defined by their members. Is that about right? Jun 28, 2013 at 3:30
• In fact, I think you can say that in theory (because you have the axiom schema of separation), but essentially yes, you're right. Jun 28, 2013 at 9:31

Take the universe to be $\{x,y\}$. Let $\in=\{(x,y),(y,y)\}$. That is $x$ is the "empty set" and $y$ contains everything. Extensionality follows trivially. Foundation follows trivially as well because the only non-empty set contains the empty set. Union is also true since $\bigcup y = y$ and $\bigcup x=x$. Pairing is trivially true because Kunen defines pairing as $\forall x\forall y\exists z(x\in z\land y\in z)$, so the universal set is there to provide the pair of any sets.
Notice however that if the pairing axiom was $\forall x\forall y\exists z(\forall w(w\in z\leftrightarrow w=x\lor w=y))$, then there is no 2 element model that satisfies all these axioms. To see this let $\{x,y\}$ to be the universe and let the universal set be $y$. Then by pairing $\{x\}$ exists and by extensionality it is different from $y$ (since one contains one element while the other contains two). Hence $\{x\}=x$. From this foundation fails, exactly as you showed it in your proof.