# $Y \notin X$ if $Y = \{u \in X \mid u \notin u\}$

The textbook I am reading mentioned this proposition:

Let $X$ be a set and let $Y = \{u \in X \mid u \notin u\}$. Then $Y \notin X$.

How would you prove that?

-
It depends on your axioms. In ZF you can prove that $Y=X$ and that $\forall x(x\notin x)$. – Brian M. Scott Mar 9 '13 at 21:48
Would you mind posting the proof? I am just wondering... – Husain Mar 9 '13 at 21:51
I was making it too hard: Jasper Loy’s argument below works fine without any specific formal axiom system. – Brian M. Scott Mar 9 '13 at 21:55

Suppose $Y\in X$. If $Y\not\in Y$, then $Y\in Y$ (by definition of $Y$). If $Y\in Y$, then $Y\not\in Y$ (by definition of $Y$ again). Since this leads to a contradiction, we have $Y\not\in X$.

-
I still do not see why that has to do with $X$ though. – Husain Mar 9 '13 at 22:28
@Husain: $X$ appears explicitly both the definition of $Y$ and the supposition.... – Hurkyl Mar 9 '13 at 22:30
Now it makes so much sense. Thanks! – Husain Mar 9 '13 at 22:32

This is Russell's paradox in a nutshell. Russell's paradox showed that there cannot be a set of all the sets which do not contain themselves. This version is a "localized" version where we only care about elements from $X$, and it shows that there is always a collection which is not an element of $X$.

If $Y\in X$ ask yourself is $Y\in Y$? If it is, then $Y\notin Y$, by the defining property of $Y$; if $Y\notin Y$ then $Y\in X$ and $Y\notin Y$ so again by the definition of $Y$ we have that $Y\in Y$.

Either way we have a contradiction so it must be that $Y\notin X$.

In set theory like ZFC where $\in$ is well-founded and $\forall x.x\notin x$, we actually have that $Y=X$.

-