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$.


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

$\blacksquare$