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$
  • $\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 '15 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 '15 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 '15 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 '15 at 10:53
  • $\begingroup$ @AsafKaragila - does it look better now? :) $\endgroup$ – user860374 Feb 14 '15 at 11:14
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
    $\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 '15 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.