7
$\begingroup$

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!

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – tomasz
    Jun 27, 2013 at 12:18
  • $\begingroup$ @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$? $\endgroup$
    – Ryan Sullivant
    Jun 27, 2013 at 23:28
  • 1
    $\begingroup$ 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). $\endgroup$
    – tomasz
    Jun 28, 2013 at 1:15
  • $\begingroup$ 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? $\endgroup$
    – Ryan Sullivant
    Jun 28, 2013 at 3:30
  • $\begingroup$ In fact, I think you can say that in theory (because you have the axiom schema of separation), but essentially yes, you're right. $\endgroup$
    – tomasz
    Jun 28, 2013 at 9:31

1 Answer 1

Reset to default
12
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Well, that makes sense. I've thought of exactly the same example, and I've been about to post that you can't satisfy pairing and extensionality in a two-element set, but I've had a different formulation of pairing in mind... $\endgroup$
    – tomasz
    Jun 27, 2013 at 12:19
  • $\begingroup$ @tomasz: Yes I noticed that if the pair is required to contain exactly the two sets then there is no 2 model that satisfies these axioms. Then I checked Kunen's book to see how he defines the pairing axiom. I have added that as an edit. $\endgroup$
    – Apostolos
    Jun 27, 2013 at 12:23
  • $\begingroup$ Oh great thanks! I think in my mind I was held up on the other definition of Pairing as well, and it seemed like any time I had two sets in a model I would trivially get infinitely many. (Edit: Well at least something else would fail as you pointed out.) Thanks! $\endgroup$
    – Ryan Sullivant
    Jun 27, 2013 at 23:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .