# Thread: Formal proof of equivalence relation

1. ## Formal proof of equivalence relation

Hello,

can someone show me how to write a formal proof of equivalence relation?

I have the following problem:

Let us have a set A and a set B. Let $\displaystyle f: A \rightarrow B$. Now let us have relation R and T, where R has a relation on B and T has a relation on A with one condition, $\displaystyle (a,b) \in T$ if and only if $\displaystyle (f(a), f(b)) \in R$.

Proof: If R is an equivalence relation then T is an equivalence relation

Well if I need to prove this, I have no idea where to start. It looks pretty obvious to me that when something $\displaystyle (a,b) \in R$ with R is an equivalence relation, then T is also an equivalence relation?

If not, can someone show me how to start? How to approach this problem?

Thanks!

2. Originally Posted by umbrella
how to write a formal proof of equivalence relation?
Let us have a set A and a set B. Let $\displaystyle f: A \rightarrow B$. Now let us have relation R and T, where R has a relation on B and T has a relation on A with one condition, $\displaystyle (a,b) \in T$ if and only if $\displaystyle (f(a), f(b)) \in R$.
Proof: If R is an equivalence relation then T is an equivalence relation
$\displaystyle \left( {\exists x \in A} \right)\left[ {f(x) \in B} \right]$ therefore
$\displaystyle \left( {f(x),f(x)} \right) \in R$ because $\displaystyle R$ is reflexive.
Does that mean that $\displaystyle (x,x)\in T?$ What does that prove?

Now you have two more to go. Give it a shot!

Answer to your first question: Yes it means that $\displaystyle (x,x) \in T$ by the definition of $\displaystyle T$. (I guess this is the proof for reflexivity right?)

PS: Could you clear up what exactly does T has a relation on a mean? (I am very uncertain about the definition, it's rather vague at my side )

PS: I am trying the other two, please hold =)

4. Proof of symmetric:

$\displaystyle \exists x, y \in A$, so $\displaystyle \exists f(x), f(y) \in B$.
$\displaystyle (f(x), f(y)), (f(y), f(x)) \in R$ (symmetric), so $\displaystyle (x, y), (y, x) \in S$ (because of defintion)

Proof of transivitiy

I am not really sure how to prove this one as it has a "temporary value" because transivity means if there is $\displaystyle a \rightarrow b \wedge b \rightarrow c$ then $\displaystyle a \rightarrow c$ right?

5. Suppose that $\displaystyle (a,b) \in T\,\& \,(b,c) \in T$ we need to show that $\displaystyle (a,c) \in T$, to show transitivity.
But by the very definition of $\displaystyle T$ we know that $\displaystyle (f(a),f(b)) \in R\,\& \,(f(b),f(c)) \in R$.
We know that $\displaystyle R$ is transitive thus $\displaystyle (f(a),f(c)) \in R$.
Again by the definition of $\displaystyle T$ that means that $\displaystyle (a,c)\in T$.

Does that answer your other question about what $\displaystyle T$ is?

6. Ah yes, thank you. So it's actually just by it's definition.