Subset implies Cardinal Inequality

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets such that $S \subseteq T$.

Furthermore, let:

$T \sim \card T$

where $\card T$ denotes the cardinality of $T$.


Then:

$\card S \le \card T$


Proof

For the proof:

the ordering relation $\le$ for ordinals

and

the subset relation $\subseteq$

shall be used interchangeably.


Let $f: T \to \card T$ be a bijection.


It follows that $f \restriction_S : S \to \card T$ is an injection.

The image of $S$ under $f$ is a subset of $\card T$ and thus is a subset of an ordinal.


By Unique Isomorphism between Ordinal Subset and Unique Ordinal, there is a unique mapping $\phi$ and a unique ordinal $x$ such that $\phi: x \to f \sqbrk S$ is an order isomorphism.

It follows that $S \sim x$ by the definition of order isomorphism.


Furthermore, $\phi$ is a strictly increasing mapping from ordinals to ordinals.

\(\ds y\) \(\in\) \(\ds x\)
\(\ds \leadsto \ \ \) \(\ds y\) \(\le\) \(\ds \map \phi y\) Strictly Increasing Ordinal Mapping Inequality
\(\ds \) \(\in\) \(\ds f \sqbrk S\) Definition of $\phi$
\(\ds \) \(\subseteq\) \(\ds \card T\) Image Preserves Subsets
\(\ds \leadsto \ \ \) \(\ds y\) \(\in\) \(\ds \card T\) Cardinal Number is Ordinal


Therefore, $y \in x \implies y \in \card T$ and $x \le \card T$ by the definition of subset.


But $\card S \le x$ by Cardinal Number Less than Ordinal.

So $\card S \le \card T$ by the fact that Subset Relation is Transitive.

$\blacksquare$


Also see


Sources