# 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 $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, $(a,b) \in T$ if and only if $(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 $(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 $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, $(a,b) \in T$ if and only if $(f(a), f(b)) \in R$.
Proof: If R is an equivalence relation then T is an equivalence relation
$\left( {\exists x \in A} \right)\left[ {f(x) \in B} \right]$ therefore
$\left( {f(x),f(x)} \right) \in R$ because $R$ is reflexive.
Does that mean that $(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 $(x,x) \in T$ by the definition of $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:

$\exists x, y \in A$, so $\exists f(x), f(y) \in B$.
$(f(x), f(y)), (f(y), f(x)) \in R$ (symmetric), so $(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 $a \rightarrow b \wedge b \rightarrow c$ then $a \rightarrow c$ right?

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

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

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