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

Question

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

Answer 1

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?

Answer 2

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

Answer 3

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.