Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

enter image description here

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

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.