Results 1 to 6 of 6

Thread: Formal proof of equivalence relation

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    24

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,776
    Thanks
    2823
    Awards
    1
    Quote Originally Posted by umbrella View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    24
    Thank you for your first reply!

    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 =)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    Posts
    24
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,776
    Thanks
    2823
    Awards
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2009
    Posts
    24
    Ah yes, thank you. So it's actually just by it's definition.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence relation proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 3rd 2011, 05:18 AM
  2. Equivalence relation proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 17th 2011, 04:30 PM
  3. Equivalence Relation Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Mar 25th 2011, 08:32 AM
  4. Equivalence Relation Proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Aug 5th 2009, 12:19 PM
  5. equivalence relation proof
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: Jul 3rd 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum