# Thread: [SOLVED] 1-to-1 Correspondence Proof

1. ## [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?

2. Originally Posted by BSC hiBi
How would I change that proof to prove a correspondence?
One-to-one correspondences are simply bijections.
Show one-to-one and onto.

3. So I would take what I did with the 1-to-1 proof, apply it to my problem? Then do onto?

4. Sorry, in both of those A->B and B->C, then we want to prove A->C

5. Originally Posted by BSC hiBi
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.

6. 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?

7. $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

8. 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.?

9. You need a face-to-face tutorial with a live tutor.

10. 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.

11. Nvm I solved it.

12. Originally Posted by BSC hiBi
there are no discrete mathematics tutors here.
You don't have an instructor for the course?

Originally Posted by BSC hiBi
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.