# Proving that $\langle \omega, \in \rangle$ models empty set and extensionality

Let (A1) be the axiom of extensionality: $\forall x,y ( x = y \longleftrightarrow \forall z \in x \leftrightarrow z \in y))$ and let (A2) be the empty set axiom $\exists x \forall y (y \notin x)$.

Then my book asks me the following:

(a) Show that $\langle \omega , \in \rangle \models (A1) \land (A2)$.

(b) Show that $\langle \{ \varnothing , \{\{\varnothing\}\}, \{\varnothing, \{\varnothing\}\}\}, \in \rangle \models \lnot (A1) \land (A2)$.

The exercise is classified as "difficult" but my attempt at an answer is easy and hence suspicious and I must be missing something:

(a) $\varnothing \in \omega \implies (A2)$.

If $x,y \in \omega$ and $x=y$ then $z \in x \iff z \in y$ (though this doesn't quite look like a proof, I can't think of anything else to write). Similarly, for the other direction: If $z \in x \iff z \in y$ then $y = x$.

(b) Let $M = \{ \varnothing , \{\{\varnothing\}\}, \{\varnothing, \{\varnothing\}\}\}$. Then $\varnothing \in M \implies (A2)$.

We have $\varnothing \neq \{\{\varnothing\}\}$ but $\forall z ( z \in \varnothing \iff z \in \{\{\varnothing\}\}$ hence $\lnot (A1)$.

What am I missing? Thanks for your help.

-
“Similarly, for the other direction: If $z\in x \Leftrightarrow z\in y$ then $y=x$” needs more justification. This is the only non-trivial part of the question. –  Yury Nov 24 '12 at 19:04
It looks like you're probably supposed to write down exactly what A1 and A2 are when relativized to $\omega$ respectively $M$. Since you're getting the right result in (b), you're probably understanding it correctly, but writing it down explicitly will help with clarity. –  Henning Makholm Nov 24 '12 at 19:15
Dear @HenningMakholm, thank you. What does "relatively to $\omega$ respectively $M$" mean? –  Rudy the Reindeer Nov 24 '12 at 19:32
@Matt: Another way to express it would be, say, "unfold the definition of $\vDash$ in $\langle M,{\in}\rangle\vDash\text{(A1)}$". –  Henning Makholm Nov 24 '12 at 19:38
By now I think I have to translate it into a statement that quantifies over the elements in $\omega$. –  Rudy the Reindeer Nov 24 '12 at 20:01

The $\rightarrow$ part in the axiom of extensionality is tautological. The essential part is the $\leftarrow$ part. To show that extensionality holds, you need to take any two elements $x,y$ of $\omega$ and show that if they have the same elements according to $M$ (that is, that $\{z\in M \vert M\models z\in x\}=\{z\in M \vert M\models z\in y\}$, which you can also write as $\{z\in M \vert z\in^M x\}=\{z\in M\vert z\in^M y\}$), then they are equal, which you didn't do (you assumed that $\{z\vert z\in x\}=\{z\vert z\in y\}$ instead).
I think the easiest way to do it is by contraposition, that is, assuming that $x\neq y$ and showing that then $\{z\in M\vert M\models z\in x\}\neq\{z\in M\vert M\models z\in y\}$, OR by noting that $M$ is transitive (which means that the universe is transitive as a set and that $\in^M$ is a restriction of $\in$ to $M$) and hence $\{z\in M\vert M\models z\in x\}=\{z\vert z\in x\}$ (in general, transitive models are always extensional and well-founded -- in fact, this characterizes them up to isomorphism).
It still doesn't seem to me to be very difficult... In fact, I think anyone learning the theory should do the exercise to see the difference between $\in^M$ and $\in$.
By the way, the way you worded A1 is a bit sloppy. It is a common convention to write something like $\forall x\in X$, but then we usually mean that something is true for all $x$ among elements of a set $X$, that is, it is a shorthand for the more formal expression $\forall x (x\in X\rightarrow (\ldots))$.
If you read it that way, your statement makes no sense, it looks like $$\forall x,y ( x = y \longleftrightarrow (\forall z (z\in x \rightarrow (\leftrightarrow z \in y)))$$ Furthermore, it mixes up the $\in$ as a symbol of the language of the theory with the $\in$ as a symbol of the language of metatheory -- which is also important because that is precisely the mistake you made in your solution. Instead, you should write it as $$\forall x,y ( x = y \longleftrightarrow \forall z(z \in x \leftrightarrow z \in y))$$