5
$\begingroup$

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.

  • 0
    (or $M$, respectively)2012-11-24

1 Answers 1

3

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