Question

Show that if |A| = |B| and |B| = |C| , then |A| = |C| .

Short answer

If go f is one-to-one and onto, is one-to-one correspondence from A to C is |A| = |C|

Step-by-step solution

Step 1:

Definition:

The function f is onto if and only if for every element $\mathrm{b}\in \mathrm{B}$there exist an element $a\in A$ such that f (a) = b

The function f is one-to-one if and only if f (a) = f (b) implies that a = b for all a and b in the domain.

f is a one-to-one correspondence if and only if f is one-to-one and onto.

Composition of f and$g:(f\circ g)\left(a\right)=f\left(g\right(a\left)\right)$

Definition (1): |A| = |B| if and only if there is a one-to-one correspondence from A to B.

Step 2:

Given: |A| = |B| and |B| = |C|

To proof: |A| = |C|

By definition : There exists a one-to-one correspondence f from A to B ( since |A| = |B| ).

By definition : There exists a one-to-one correspondence g from B to C (since |B| = |C| ).

We can then define use the composition of g and f :

$g\circ f:A\to C,(g\circ f)\left(a\right)=g\left(f\right(a\left)\right)$

g o f is one-to-one:

Let $(g\circ f)\left(x\right)=(g\circ f)\left(y\right)$, by definition of $g\circ f:g\left(f\right(x\left)\right)=g\left(f\right(y\left)\right)$ which implies f (x) = f (y) since g is a one-to-one correspondence and x = y since f is a one-to-one correspondence.

Thus, we have then shown that g of is one-to-one.

g of is onto: Let $c\in C$. Since, is a one-to-one correspondence, there exists an element $a\in A$such that f (a) = b.

Since, is a one-to-one correspondence, there exists an element such that.

Combining, we then obtain: $(g\circ f)\left(a\right)=g\left(f\right(a\left)\right)=g\left(b\right)=c$and thus is onto.

Since is one-to-one and onto, is one-to-one correspondence from A to C .

By definition : |A| = |C|