Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
“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? –  Matt N. 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$. –  Matt N. Nov 24 '12 at 20:01
show 1 more comment

1 Answer

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.