Results 1 to 12 of 12

Math Help - [SOLVED] 1-to-1 Correspondence Proof

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    16

    [SOLVED] 1-to-1 Correspondence Proof

    Let g: A -> and f: B -> both be 1-to-1 correspondences. Prove that f o g : A->C is a 1-to-1 correspondence.

    I'm studying for exam next week and trying to do a proof from sets, correspondences, induction, and an equivalence relation. I understand set proofs, now I'm doing a correspondence proof.

    I was able to solve the same problem but it was proving g o f is 1-to-1. This is the pf for that.

    Pf: Let g: A -> and f: B -> both be 1-to-1. Prove that f o g : A->C is a 1-to-1.

    To show f is 1-to-1, we need to show that if f(x1)=f(x2), then x1=x2. Then g(f(x1))=g(f(x2)) or gf(x1) = gf(x2). This means x1 = x2 because gf is 1-to-1.

    How would I change that proof to prove a correspondence?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by BSC hiBi View Post
    How would I change that proof to prove a correspondence?
    One-to-one correspondences are simply bijections.
    Show one-to-one and onto.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    16
    So I would take what I did with the 1-to-1 proof, apply it to my problem? Then do onto?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    16
    Sorry, in both of those A->B and B->C, then we want to prove A->C
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by BSC hiBi View Post
    So I would take what I did with the 1-to-1 proof, apply it to my problem? Then do onto?
    YES!
    You are given that both mappings are on-to-one and onto.
    So prove that the composition is also.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2009
    Posts
    16
    Instead of using f(x1) and f(x2) for 1-to-1, what should I use for onto? Since I know onto requires if A->B then everything in B must be hit by something in A. But how does this translate to what I'm doing?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    f \circ g(a) = f \circ g(b)\, \Rightarrow \,g(a) = g(b)\, \Rightarrow \,a = b ONE-to-ONE

    r \in C\, \Rightarrow \,\left( {\exists q \in B} \right)\left[ {f(q) = r} \right]\, \Rightarrow \,\left( {\exists p \in A} \right)\left[ {g(p) = q} \right]
    f \circ g(p) = r ONTO
    Last edited by Plato; March 7th 2009 at 02:44 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2009
    Posts
    16
    Is there anyway you could give elaborate briefly on what a lot of those symbols mean? Like where r is coming from? You're using r like I use x? r is an element of ect.?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    You need a face-to-face tutorial with a live tutor.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Mar 2009
    Posts
    16
    Heh, there are no discrete mathematics tutors here. And I'll understand it if anyone explains it to me... If I get an explanation Ill understand it.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Mar 2009
    Posts
    16
    Nvm I solved it.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by BSC hiBi View Post
    there are no discrete mathematics tutors here.
    You don't have an instructor for the course?

    Quote Originally Posted by BSC hiBi View Post
    I'll understand it if anyone explains it to me... If I get an explanation Ill understand it.
    But that is not the function of this site.
    We give help to posters who have a basic understanding.
    We are not here to give tutorials. Sorry.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One-to-one correspondence between set of homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 13th 2012, 03:30 PM
  2. Correspondence Theorem
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: April 5th 2010, 06:37 PM
  3. one to one correspondence
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: October 21st 2009, 02:56 AM
  4. one to one correspondence
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 12th 2009, 11:48 AM

Search Tags


/mathhelpforum @mathhelpforum