# Thread: Proving that a relation is an equivalence relation

1. ## Proving that a relation is an equivalence relation

I am having difficulties proving the relation IS an equivalence relation.

Let
$f: X\longrightarrow Y$ be a function from a set $X$ onto a set $Y$. Let $R$ be the subset of $X \times X$ consisting of those pairs $(x, x')$such that $f(x)= f(x')$. Prove that $R$ is an equivalence relation . Let $\pi: X\longrightarrow X/R$ be a projection. Verify that, if $\alpha \in X/R$ is an equivalence class, to define $F(\alpha) = F(a)$, whenever $\alpha = \pi (a)$, establishes a well-defined function $F: X/R \longrightarrow Y$ which is one-to-one and onto.

2. ## Re: Proving that a relation is an equivalence relation

We need to show 3 things:

1. For any $x \in X$ that $(x,x) \in R$ ($R$ is reflexive).

2. If $(x,x') \in R$ then also $(x',x) \in R$ ($R$ is symmetric).

3. If $(x,x')$ AND $(x',x'')$ are in $R$, then so is $(x,x'')$ ($R$ is transitive).

I'll show you (1) and (2), you can try (3).

Suppose $x \in X$. Since $f$ is a function, $f(x)$ is uniquely defined, and $f(x) = f(x)$ hence $(x,x) \in R$. This is so simple it's almost silly.

Now suppose $(x,x') \in R$. By definition, this means $f(x) = f(x')$. But equality is symmetric, so $f(x') = f(x)$, and thus $(x',x) \in R$.

A word about the mapping $\pi:X \to X/R$: what we mean is: $\pi(x) = [x]_R$ (the equivalence class of $x$ in the relation $R$).

Note that we define $F(\alpha) = f(a)$, for this to actually BE a function, we need to be SURE that no matter "which" $a$ we pick out of the equivalence class $\alpha$ to which it belongs, we get the same value.

Specifically, if $a' \in \alpha = [a]_R$, we have to show that $f(a') = f(a)$. However, since this is how we DEFINED $R$, we're OK, all elements of $[a]_R$ all have the same image under $f$.

To show $F$ is onto, for every $y \in Y$ we need to find $\alpha \in X/R$ with $F(\alpha) = y$.

Since $f$ is onto, we have some $x \in X$ with $f(x) = y$, so pick $\alpha = [x]_R = \pi(x)$.

Now suppose $F(\alpha) = F(\beta)$. This means that $f(a) = f(b)$ for some $a \in \alpha$ and $b \in \beta$. But that means that $(a,b) \in R$, so $[a]_R = [b]_R$, that is $\alpha = \beta$, so $F$ is one-to-one.

Let me give a simple example, to show you how this works:

Let $X = \Bbb Z$, the set of integers, and let $Y = \{0,1\}$. Define the function $f: X \to Y$ by:

$f(k) = \dfrac{1^k - (-1)^k}{2}$. Clearly, if $k$ is even, then $f(k) = 0$, and if $k$ is odd, then $f(k) = 1$.

So we have two equivalence classes:

$\{\dots,-4,-2,0,2,4,6,8,\dots\}$

$\{\dots,-5,-3,-1,1,3,5,7,\dots\}$

We can call these $[0]_R$ and $[1]_R$. Our function $F$ is thus:

$F([0]_R) = 0$
$F([1]_R) = 1$, which is clearly a one-to-one correspondence between two two-element sets.