1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
0
$\begingroup$

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.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – KawaiiExpert Apr 15 '14 at 14:49
  • $\begingroup$ First show that $R\subseteq\{(x,x)\mid x\in X\}$, then show that $R$ is the identity relation on its domain. $\endgroup$ – Asaf Karagila♦ Apr 15 '14 at 14:51
  • $\begingroup$ 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$ $\endgroup$ – KawaiiExpert Apr 15 '14 at 14:56
  • $\begingroup$ That is your ultimate goal. $\endgroup$ – Asaf Karagila♦ Apr 15 '14 at 14:58
  • $\begingroup$ 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$. $\endgroup$ – KawaiiExpert Apr 15 '14 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.