Question

Show that if A, B and C are sets such that $\left|\mathit{A}\right|\le \left|\mathit{B}\right|\text{and}\left|\mathit{B}\right|\le \left|\mathit{C}\right|\text{, then}\left|\mathit{A}\right|\le \left|\mathit{C}\right|$.

Short answer

$\mathbf{\left|}\mathit{A}\right|\le \left|\mathit{C}\right|$

Step-by-step solution

Step 1:

DEFINITION (1):

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

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

DEFINITION (2): $\left|A\right|\le \left|B\right|$if and only if there is a one-to-one function from A to B.

Step 2:

Given: $\left|A\right|\le \left|B\right|\mathrm{and}\left|\mathrm{B}\right|\le \left|\mathrm{C}\right|$.

To proof: $\left|A\right|\le \left|C\right|$.

PROOF:

By definition (2): There exists a one-to-one function f from A to B (since$\left|A\right|\le \left|B\right|$ ).

By definition (2): There exists a one-to-one function g from B to C (since $\left|B\right|\le \left|C\right|$).

We can then 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\circ f$is one-to-one: Let $(g\circ f)\left(x\right)=(g\circ f)\left(y\right)$, by definition of $\mathrm{g}\circ \mathrm{f}:\mathrm{g}\left(\mathrm{f}\right(\mathrm{x}\left)\right)=\mathrm{g}\left(\mathrm{f}\right(\mathrm{y}\left)\right)$which implies f (x) = f (y) since is a one-to-one function and x = y since f is a one-to-one function. Thus we have then shown that is one-to-one.

By definition (2): $\left|A\right|\le \left|C\right|$.