# If $Y$ not transitive then $\in$ not extensional?

Let $W$ be a binary relation on a set $Y$. The relation $W$ is called extensional if $$\forall x,y \in Y (x \neq y \rightarrow \exists z \in Y (( \langle z,x \rangle \in W \land \langle z,y \rangle \notin W) \lor ( \langle z,x \rangle \notin W \land \langle z,y \rangle \in W )))$$

Consider the $\in$ relation. Let $Y$ be a set that is not transitive. This means that there is $y$ in $Y$ such that $x \in y$ but $x \notin Y$. (Right?) How does this make $\in$ non-extensional?

(As I understand extionsionality means that two sets are equal if and only if they contain the same elements. How is this violated if $\in$ is not transitive?)

Thanks.

Here is a copy of the exercise, page 64, Just/Weese:

-
You are correct that more assumptions are needed to ensure that the $\in$-relation restricted to a non-transitive set is not extensional. Note that the set $Y = \{ \{ \emptyset \} \}$ is not transitive, however the $\in$-relation restricted to $Y$ is extensional. Is this something else from Just-Weese? If so, what precisely do they say? – arjafi Nov 12 '12 at 8:37
@ArthurFischer Yes, let me add a copy. – Rudy the Reindeer Nov 12 '12 at 8:38
Note that the Exercise does not say that all non-transitive sets have non-extensional $\in$-relations. But only that some do (this is the phrase "$\in$ may not be an extensional relation on $Y$" [emphasis mine]). Read Asaf's answer below. – arjafi Nov 12 '12 at 8:43

Consider $Y=\{\varnothing,\{1\}\}$.

From the point of view of $Y$ neither contain any elements, because $1\notin Y$. But these are different sets.

To say that $\langle Y,\in\rangle$ is extensional is to say that the following is true: $$\forall x\in Y\forall y\in Y(x=y\leftrightarrow\forall z\in Y(z\in x\leftrightarrow z\in y))$$

This clearly fails in our case.

-
Bus WiFi is great. – Asaf Karagila Nov 12 '12 at 8:38
: ) But $\{1\} = \{ \{\varnothing \} \}$, I don't understand how $\{1\}$ does not contain an element, it seems to contain $1 = \{\varnothing \}$. Could you elaborate, please? – Rudy the Reindeer Nov 12 '12 at 8:38
In $Y$ it doesn't. As a structure $\langle Y,\in\rangle$ is not extensional. – Asaf Karagila Nov 12 '12 at 8:40
I'm sorry but I honestly don't understand. In $Y$, $1 = \{ \varnothing \} \in \{1\}$, so there is indeed an element in $\{1\}$. – Rudy the Reindeer Nov 12 '12 at 8:42
@Matt: Perhaps using the $\in$ symbol has been confusing you, and perhaps we should avoid it. Given a set $Y$ define a binary relation $\mathord{\triangleleft}$ on $Y$ by $x \triangleleft y$ iff $x \in Y \wedge y \in Y \wedge x \in y$. Now go through Asaf's example and show that $\mathord{\triangleleft}$ is not extensional. – arjafi Nov 12 '12 at 8:55