0
$\begingroup$

Apologies if my title is incorrectly formatted. In my preview the MathJax commands don't seem to be working, so I've copied and pasted from other questions on SE.

The body of my problem:

We have two non-empty sets, X and Y, such as that X ⊊ Y. On X we define the equivalence relation xRy if and only if {x,y} ⊂ X or {x,y} ⊂ (Y\X). Prove that the relation is an equivalence relation and find all of its equivalence classes.

Now, I'm familiar with the definition of equivalence relation, however, I'm not sure how to test if the relation is symmetric or transitive in this example. I am also much less confident in my comprehension of equivalence classes, so if someone could explain how to find them in this example, I would be much appreciated.

Thank you SE.

$\endgroup$
  • $\begingroup$ I assume that the equivalence relation is defined on $Y$, not on $X$. A hint: you have two equivalence classes, one formed by the elements of $X$ and one by the elements of $Y\setminus X$. $\endgroup$ – A. Bellmunt Apr 8 '18 at 17:26
  • $\begingroup$ The problem states it is defined on X, but perhaps it is an error? I begin to see what you mean about the equivalence classes, but I still wouldn't know how to define them. Thank you for your answer! $\endgroup$ – Jake Apr 8 '18 at 17:32
  • $\begingroup$ What do you mean when you say you are not sure how to "test" if the relation is symmetric or transitive? $\endgroup$ – theyaoster Apr 8 '18 at 17:33
  • $\begingroup$ xRx if and only if {x} [or would it be {x,x}?] ⊂ X or (Y\X), but I am not sure if yRx would represent the case {y,x} belonging to X or (Y\X), etc... Thank you for your answer. $\endgroup$ – Jake Apr 8 '18 at 17:41
  • $\begingroup$ $\{x\}$ and $\{x,x\}$ are equivalent (by the Axiom of Extensionality), so either one works. Yes, you are correct about $yRx$, since what you said comes directly from the definition of $R$. $\endgroup$ – theyaoster Apr 8 '18 at 17:46
0
$\begingroup$

Hint: To prove symmetry, use the fact that sets are unordered collections, such that $\{x,y\} = \{y,x\}$ (one way to justify this is with the Axiom of Extensionality). To prove transitivity, assume you have $x,y,z$ which satisfy $xRy$ and $yRz$. You wish to show that $xRz$, or in other words, that $x$ and $z$ either both belong to $X$ or both belong to $Y \setminus X$. To accomplish this, try showing that $x$, $y$, and $z$ all belong to $X$ or all belong to $Y \setminus X$.

Once you have proven that $R$ is an equivalence relation, recall that the equivalence class (with respect to equivalence relation $R$) of an element $x \in Y$ is $[x] = \{y \mid xRy\}$. Given $x \in Y$, consider two cases, one where $x \in X$ and another where $x \in Y \setminus X$, and try to find the equivalence class of $x$ in each case.

$\endgroup$
  • $\begingroup$ +1 though I might not have rep for it to be apparent! Thank you for your help! My understanding is broadened. $\endgroup$ – Jake Apr 8 '18 at 18:07
0
$\begingroup$

As you know, equivalence relations require three properties: $$\begin{align} &\mathrm{1. Reflexivity:}\quad x\sim x \\ &\mathrm{2. Symmetry:}\quad x\sim y \Leftrightarrow y\sim x \\ &\mathrm{3. Transativity:}\quad (x\sim y \wedge y\sim z)\Rightarrow x\sim z \end{align}$$

In your case:

  1. Reflexivity holds because $\{x,x\}=\{x\}$

  2. Symmetry holds because $\{x, y\}=\{y, x\}$, hence both $x\sim y$ and $y\sim x$.

  3. Transativity holds because if $\{x, y\}\subset A \hspace{2px}\wedge \{y, z\}\subset A$ then $\{x, y, z\}\subset A \Rightarrow \{x, z\}\subset A$. $A$ can be either of $X$ or $(Y\setminus X)$.

The two equivalence classes are $X$ and $(Y\setminus X)$ because an element can either be in one or the other, and if two elements, $x$ and $y$, are in the same set, the set $\{x, y\}$ is a subset of the set, where $x$ and $y$ are, so they are equal.

$\endgroup$
  • $\begingroup$ +1 though I might not have rep for it to be apparent! Thank you for your help! My understanding is broadened. $\endgroup$ – Jake Apr 8 '18 at 18:07

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.