3
$\begingroup$

If $A \sim B$ and $B \sim C$. Prove that $A \sim C$


What I have:

We know there exists functions $f,g$ such that $f:A\to B$ and $g:B \to C$ where $f$ and $g$ are bijective.

We thus require to show that there exists a function $h:A \to C$ where $h$ is bijective.


Can anyone please give me some hints that might point me in the right direction? I do not want a complete answer, simply a nudge in the right direction.

UPDATE: This is my (very rough) attempt at the proof.

We know there exists functions $f,g$ such that $f:A\to B$ and $g:B \to C$ where $f$ and $g$ are bijective.

We thus require to show that there exists a function $h:A \to C$ where $h$ is bijective.

Assume that $h(x) = g \circ f = g(f(x))$.

We must now show that $h$ is bijective.

$\underline{RTP:}$ If $f$ and $g$ are surjective, then $g \circ f$ is surjective.

$\underline{Proof:}$ We are given that $f$ and $g$ are surjective (since they are bijective). Suppose $c \in C$, then since $g$ is surjective, we know $\exists b \in B$ such that $g(b) = c$. Similarly, since $f$ is surjective, $\exists a \in A$ such that $f(a) = b$.

Thus \begin{align}g \circ f(a) &= g(f(a)) \\ &= g(b) \\ &= c\end{align} Hence we have shown that $h$ is surjective.

We must now show that $h$ is injective.

$\underline{RTP:}$ If $f$ snd $g$ are injective, then $g\circ f$ is also injective.

$\underline{Proof:}$ We are given that $f$ and $g$ are injective (since they are bijective) and suppose $$g \circ f(x_1) = g \circ f(x_2)$$ We thus have that $$g(f(x_1))= g(f(x_2))$$ Since $g$ is injective, we know that this is true if and only if $f(x_1) = f(x_2)$. Similarly, since $f$ is injective, it follows that $$x_1 = x_2$$ Thus $g \circ f$ is injective.

We have thus proven that there exists a function $h(x)= g \circ f : A \to C$ that is bijective.

Hence we can conclude that $A \sim C$.

$\endgroup$
6
  • $\begingroup$ Just try to prove injectivity and surjectivity. Whatever you can prove for $f$ and $g$ independently you can prove for their composition. $\endgroup$
    – Mnifldz
    Feb 14, 2015 at 8:03
  • $\begingroup$ I have posted an update to the question that includes my next attempt at the proof. Can you please check it and give comment/feedback? :) $\endgroup$
    – user860374
    Feb 14, 2015 at 10:47
  • $\begingroup$ The proof of surjectiveness is wrong. What do you have to show? You have to show that given $c\in c$, there is some $a\in A$ such that $h(a)=c$. You just wrote $h(a)=g(b)=c$ for three arbitrary elements, that's just not right. $\endgroup$
    – Asaf Karagila
    Feb 14, 2015 at 10:49
  • $\begingroup$ @AsafKaragila - Thank you for pointing that out. :). I will give it a try and see if I can figure it out :) $\endgroup$
    – user860374
    Feb 14, 2015 at 10:53
  • $\begingroup$ @AsafKaragila - does it look better now? :) $\endgroup$
    – user860374
    Feb 14, 2015 at 11:14

3 Answers 3

2
$\begingroup$

Make a list of everything you know. What does it mean that $f$ and $g$ are bijective? Well, it means that $f$ is injective, and $f$ is surjective, and $g$ is injective, and $g$ is surjective. What do each of those four statements mean?

What do you want to prove? That $g\circ f$ is bijective. What does that mean? That $g\circ f$ is injective, and $g\circ f$ is surjective. Choose one of these two statements to tackle first. What exactly does it require? What tools do you have that look like what you want?

$\endgroup$
1
  • 1
    $\begingroup$ Yes. That's what I tell my, students all the time. Read the question, understand the definitions, write down stuff. $\endgroup$
    – Asaf Karagila
    Feb 14, 2015 at 9:33
1
$\begingroup$

Take $c\in C$ and find $a\in A:g(f(a))=c$.

Take $a_1,a_2\in A$ such that $g(f(a_1))=g(f(a_2))$ and show $a_1=a_2$.

$\endgroup$
1
$\begingroup$

A function $u:X\rightarrow Y$ is bijective iff there is a function $v:Y\rightarrow X$ such that $u\circ v=\rm{id}_Y$ and $v\circ u=\rm{id}_X$. Moreover this function $v$ is unique and denoted as $u^{-1}$. It is the so called inverse of function $u$. It is immediate that $u^{-1}$ is also bijective and that $u$ is its inverse.

It is very handsome to have this lemma in your mathematical handbag. If you want a proof of it, then let me know.

In the context of your question we find easily that $f^{-1}\circ g^{-1}$ serves as inverse of $g\circ f$. Direct conclusion: $g\circ f$ is bijective.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .