Cardinal Number Plus One Less than Cardinal Product

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x$ be an ordinal such that $x > 1$.


Then:

$\left|{ x + 1 }\right| \le \left|{ x \times x }\right|$

Where $\times$ denotes the Cartesian product.


Proof

Since $x > 1$, then $0 < x$ and $1 < x$.

Define the function $f : x + 1 \to x \times x$ as follows:

$f\left({y}\right) = \begin{cases} \left({ y , 0 }\right) &: y < x \\ \left({ 0 , 1 }\right) &: y = x \end{cases}$


If $f\left({y}\right) = f\left({z}\right)$, then $y = z$ by cases.


Case 1: $y = x$

If $y = x$, then $f\left({y}\right) = \left({ 0,1 }\right)$ by the definition of $f$.

So if $z < x$, then $f\left({y}\right) \ne f\left({z}\right)$.

This contradicts the hypothesis, so $z = x$ and therefore $z = y$.


Case 2: $y < x$

If $y < x$, then $f\left({y}\right) = \left({ y,0 }\right)$ by the definition of $f$.

$z = x$ yields the contradictory statement $\left({ y,0 }\right) = \left({ 0,1 }\right)$.


Therefore, $z < x$ and $\left({ y,0 }\right) = \left({ z,0 }\right)$.

By Equality of Ordered Pairs, it follows that $y = z$.


It follows that $f$ is an injection.

By Injection iff Cardinal Inequality, it follows that $\left|{ x + 1 }\right| \le \left|{ x \times x }\right|$.

$\blacksquare$


Sources