Discrete Math Equivalence Relation

Question

Let $f$ be some function with domain $S$ and range $T$. Define a relation $R$ by $x R y$ to mean $f(x) = f(y)$. Prove that $R$ is an equivalence relation. If $4$ is a member of $S$, what are the members of $[4]$ (the set of all elements equivalent to $4$ under under this equivalence relation)?

I'm not sure what exactly this question is asking...what does "relation $R$ by $x R y$" mean? Thanks in advance

Answer 1

$R$ is a relation, it means that you identify all the members of a set that fulfill a certain condition, in this particular case you are searching all the members in $S$ that goes to the same element in $T$ under the function $f$. And we define an equivalence relation iff the relation is:

• Reflexive: $xRx$ (x is relationed with itself)
• Symmetry: If $xRy$ then $yRx$ (x is relationed with y and so y with x)
• Transitivity: If $xRy$ and $yRz$ then $xRz$ (x relationed with y, y with z then x is relationed with z)

So, getting back to this particular exercise, $xRy$ if $f(x)=f(y)$ with $f$ some function such that: $f:S\to T$, we shall prove this conditions:

• It is reflexive 'cause f(x)=f(x)
• We have that $xRy$ or $f(x)=f(y)$ but that implies that $f(y)=f(x)$ and so $yRx$
• If $xRy$ and $yRz$ then $f(x)=f(y)$ and $f(y)=f(z)$ and again that implies that $f(x)=f(z)$ and so $xRz$.

Therefore $R$ is an equivalence relation.

Answer 2

First for your second question, $[4] = \{x: f(x) = f(4)\}=f^{-1}(f(4))$, and for the first question, we have $f(x) = f(x) \Rightarrow x \sim x \Rightarrow \text{reflexive holds}, f(x) = f(y) \Rightarrow f(y) = f(x) \Rightarrow x \sim y \Rightarrow y \sim x \Rightarrow \text{symmetric holds}, f(x)=f(y), f(y) = f(z) \Rightarrow f(x) = f(z) \Rightarrow x \sim y, y \sim z \Rightarrow x \sim z \Rightarrow \text{ transitivity holds } \Rightarrow \text{R is an equivalence relation}$.

Answer 3

I'm not sure what exactly this question is asking...what does "relation R by x R y" mean?

To rephrase: We define the relation called $R$ to be such that when we write $x \mathop{R} y$ it means that $f(x)=f(y)$.

You are asked to show that this relation $R$ satisfies the definition of an equivalence relation; that is that it is a reflexive, symmetric, and transitive relation.

---

If it is reflexive: $\forall x \in S: x R x$

If it is symmetric: $\forall (x, y) \in S^2: (x R y \to y R x)$

If it is transitive: $\forall (x, y, z) \in S^3: \big((x R y\wedge y R z) \to x R z\big)$

Can you now show that these are so?