Subset implies Cardinal Inequality
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
- Set Equivalent to Cardinal, which requires the axiom of choice.
Sources
- 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 10.22$
- Mizar article CARD_1:11