Proof:≤ and ≥ are related

Claim (see proof):

[math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] if and only if [math]|B| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |A| [/math]

Proof: (using inverses)

Suppose that [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math]. Then there exists an injection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]. Since [math]f [/math] is injective, it has a left inverse [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math]. Clearly, [math]f [/math] is a right inverse of [math]g [/math] so [math]g [/math] is surjective. Thus [math]|B| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |A| [/math] (by definition). The converse direction is similar.