# Prove that if $|A|=|B|$ and $|B|=|C|$ then $|A|=|C|$

Let $A,B$ and $C$ be sets. Prove that if $|A|=|B|$ and $|B|=|C|$ then $|A|=|C|$. Let $A,B$ and $C$ be sets.

Solution

$|A|=|B|$ means there exists a bijection $f:A\rightarrow B$

and $|B|=|C|$ means there exists a bijection $g:B\rightarrow C$

we need to show that $|A|=|C|$ meaning we have to prove that there also exist a bijection $h:A\rightarrow C$.

In other words we have to show that the function $h$ is injective and surjective

For that we use the existing functions $f:A\rightarrow B$ and $g:B\rightarrow C$.

Now we will consider the element in the domain of $h$ and we define it as $h(a)=f(a)$.

Since we have defined $h$ we will show that it is injective and surjective.

To show surjective consider an element $x$ in the codomain of $h$. It is $c\in C$.

For $x=c$ we use the fact that $g:B\rightarrow C$ is surjective and so there exists some $b\in B$ such that $f(b)=c$. but then by definition of $h$, holds $h(b)=c=x$.

To show that $h$ is injective, suppose that $x,y$ are in the domain of $h$ and that $h(x)=h(y)$. Call this common value $z$.

It is $z=a$ then by definition of $h$, $x=a$ and $y=a'$ and moreover $f(a)=f(a')=b$. But since $f$ is injective it follows that $a=a'$ and so that $x=y$

• Simply set $h:=g\circ f$. The composition of two bijections is again a bijection. Of courss, you need to notice that the range of $f$ is equal to the domain of $g$. – Julien Feb 13 '13 at 0:15

It can be just easier to prove the following two-parts claim first:

Let $A,B,C$ be sets, and $f\colon A\to B$, $g\colon B\to C$ functions. Then:

1. If $f,g$ are injective then $g\circ f$ is injective.
2. If $f,g$ are surjective then $g\circ f$ is surjective.

The proof is really just element chasing. I'll write one of these here:

Suppose that $f,g$ are surjectives, we want to show that $g\circ f\colon A\to C$ is surjective. That is, for every $c\in C$ there is some $a\in A$ such that $(g\circ f)(a)=c$.

Let $c\in C$ be some element, we assumed that $g$ is surjective, therefore there is some $b\in B$ such that $g(b)=c$. We also assumed that $f$ is surjective so there is some $a\in A$ such that $f(a)=b$. Therefore the following holds: $$(g\circ f)(a)=g(f(a))=g(b)=c$$ And so we found $a\in A$ as wanted, and $g\circ f$ is indeed surjective. $\square$

The claim you want to prove now is merely using these two parts. $h=g\circ f$, since both $f,g$ are injective so is $h$, and they are surjective and therefore $h$ is also surjective.

Do note that the definition you write for $h$ is not well written, you first define it to be $h(a)=f(a)$ and then define it to be $h(b)=g(b)$, if $b\in B\setminus A$ then $h$ is not a function whose domain is $A$; and if $b\in A\cap B$ and $g(b)\neq f(b)$ then $h(b)$ is not even well-defined.

• Bingo. This works. – ncmathsadist Feb 13 '13 at 2:47

You wanted $h:A\to C$, but when you say (for $a\in A$) that you're letting $h(a)=f(a)$, you're defining $h:A\to B$. There are other, similar errors, which amount to failing to keep track of your (co)domain(s).

You're quite correct that we can use $f:A\to B$ and $g:B\to C$ to define $h$, though. What can you say about $g\circ f$, given what you know of $f$ and $g$?

Right. So we have $f:A \to B$ is bijective, and $g:B \to C$ is bijective. So just compose these functions to get $g \circ f = h:A \to C$, and it shouldn't be hard to show that $h$ is bijective.