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$
Can anyone correct me please!!
Best Answer
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$?