1
$\begingroup$

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!!

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Julien Feb 13 '13 at 0:15
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Bingo. This works. $\endgroup$ – ncmathsadist Feb 13 '13 at 2:47
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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