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

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

• Just try to prove injectivity and surjectivity. Whatever you can prove for $f$ and $g$ independently you can prove for their composition. Feb 14, 2015 at 8:03
• 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? :) Feb 14, 2015 at 10:47
• 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. Feb 14, 2015 at 10:49
• @AsafKaragila - Thank you for pointing that out. :). I will give it a try and see if I can figure it out :) Feb 14, 2015 at 10:53
• @AsafKaragila - does it look better now? :) Feb 14, 2015 at 11:14

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?

• Yes. That's what I tell my, students all the time. Read the question, understand the definitions, write down stuff. Feb 14, 2015 at 9:33

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

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.