# Prove that if the relation (R) is symmetric and antisymmetric on the set X, there exists a Y subset of X such that R is the = relation on Y.

Prove that for any relation R on a set X that is both symmetric and antisymmetric, there is subset Y \subseteq X for which R is the relation = on Y.

I will tell you what I know. I know that relations are sets and that I can show two relations are equal by showing they are subsets of each other. I also am itching to say that Y is the domain of R. But I have no clue how to start.

Yes, $Y$ is the domain of $R$.

HINT: Show that if $R$ is symmetric and antisymmetric then every pair in $R$ has the form $(a,a)$.

Let me expand a little bit on that hint with a series of steps. Let us denote by $E_A$ the relation $\{(a,a)\mid a\in A\}$. Denote by $Y$ the domain of $R$.

1. Show that if $(x,y)\in R$ then $x=y$, and conclude that $R\subseteq E_Y$.
2. Show that if $x\in Y$, then $(x,x)\in R$.
3. Conclude equality.
• So would you recommend me starting off by saying that Y is the domain of R? Or should I first say "Let R be a relation on a set X that is both symmetric and antisymmetric. Since (x,x) is in R, it is the domain of R." – KawaiiExpert Apr 15 '14 at 14:49
• First show that $R\subseteq\{(x,x)\mid x\in X\}$, then show that $R$ is the identity relation on its domain. – Asaf Karagila Apr 15 '14 at 14:51
• Oh ok. I was told to use E_Y = $\{(x,x) \mid x \in Y \}$ for a given Y. So I would need to show that $E_Y \subseteq R$ and $R \subseteq E_Y$ – KawaiiExpert Apr 15 '14 at 14:56
• That is your ultimate goal. – Asaf Karagila Apr 15 '14 at 14:58
• Let $E_Y = \{ (x,x) \: | \: x \in Y \}$ for a given $Y$. Let $(x,y) \in R$. Since $R$ is symmetric, $(y,x)$ $\in R$. Since $R$ is asymmetric, $x=y$. Also $x \in$ domain of $R$, which is equal to $E_Y$. So $(x,x) \in E_Y$. So $R \subseteq E_Y$. Let $(x,x) \in R$. Then $x \in Y =$ the domain of $R$. So $\exists \: x,y \in X ((x,y) \in R)$. By asymmetry, $x=y$. So $(x,x) \in R$. Hence $E_Y \subseteq R$. – KawaiiExpert Apr 15 '14 at 15:00