Proof:≤ is transitive

From CS2800 wiki
If [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] and [math]|B| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |C| [/math] then [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |C| [/math]. In other words, the [math]\href{/cs2800/wiki/index.php/%E2%89%A4}{≤} [/math] relation on cardinalities is transitive.
Proof: (using definitions)
Suppose [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] and [math]|B| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |C| [/math]. Then by definition, there exists injections [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] and [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math].

I claim [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math] is also an injection. To see this, suppose that [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f(x_1) = g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f(x_2) [/math]. We want to show that [math]x_1 = x_2 [/math].

Since [math]g [/math] is injective, we have [math]f(x_1) = f(x_2) [/math]. Since [math]f [/math] is also injective, we have [math]x_1 = x_2 [/math], as desired.

We can use inverses to give an alternate proof:

Proof: (using inverses)
Suppose [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] and [math]|B| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |C| [/math]. Then by definition, there exists injections [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] and [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math].

I claim [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math] is also an injection. To see this, note that [math]f [/math] and [math]g [/math] have left inverses [math]f' : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] and [math]g' : C \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math].

Now, [math]f' \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g' [/math] is a left inverse of [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f [/math], because for any [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math],

[math]\begin{align} (f' \circ g') \circ (g \circ f)(x) &= (f' \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g')(g(f(x))) && \href{/cs2800/wiki/index.php/%5Ccirc}{\text{by definition}} \\ &= f'(g'(g(f(x)))) && \href{/cs2800/wiki/index.php/%5Ccirc}{\text{by definition}} \\ &= f'(f(x)) && \href{/cs2800/wiki/index.php/Left_inverse}{\text{since g' is a left inverse of g; g'(g(y)) = y}} \\ &= x && \text{since f' is a left inverse of f} \end{align} [/math]

as required.

Since [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f [/math] has a left inverse, it is injective, so by definition, we have [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |C| [/math] as required.