Injection implies Cardinal Inequality

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

Let $f: S \to T$ be an injection.

Let $\card T$ denote the cardinal number of $T$.

Let:

$T \sim \card T$

where $\sim$ denotes set equivalence


Then:

$\card S \le \card T$


Proof

Let $f \sqbrk S$ denote the image of $S$ under $f$.


\(\ds S\) \(\sim\) \(\ds f \sqbrk S\) Set is Equivalent to Image under Injection
\(\ds \) \(\subseteq\) \(\ds T\) Image Preserves Subsets
\(\ds \leadsto \ \ \) \(\ds \card S\) \(=\) \(\ds \card {f \sqbrk S}\) Equivalent Sets have Equal Cardinal Numbers
\(\ds \) \(\le\) \(\ds \card T\) Subset implies Cardinal Inequality

$\blacksquare$