Dominance Relation is Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be cardinals.

Let $S \preccurlyeq T$ denote that $S$ is dominated by $T$.


Let $\mathbb S$ be any set of cardinals.

Then the relational structure $\struct {\mathbb S, \preccurlyeq}$ is an ordered set.


That is, $\preccurlyeq$ is an ordering (at least partial) on $\mathbb S$.


Proof

From the definition, a cardinal is a set, so standard set theoretic results apply.


So, checking in turn each of the criteria for an ordering:


Reflexivity

For any cardinal $S$, the identity mapping $I_S: S \to S$ is an injection.

Thus:

$\forall S \in \mathbb S: S \preccurlyeq S$

So $\preccurlyeq$ is reflexive.

$\Box$


Transitivity

Let $S_1, S_2, S_3 \in \mathbb S$ such that $f: S_1 \to S_2$ and $g: S_2 \to S_3$ be injections.

From Composite of Injections is Injection, $g \circ f$ is an injection and so $S_1 \preccurlyeq S_3$.

So $\preccurlyeq$ is transitive.

$\Box$


Antisymmetry

Suppose $S \preccurlyeq T$ and $T \preccurlyeq S$.

Then from the Cantor-Bernstein-Schröder Theorem, $S \sim T$ and, as $S$ and $T$ are cardinals, $S = T$ by definition.


So $\preccurlyeq$ is antisymmetric on a set of cardinals.

$\Box$

Hence the result.

$\blacksquare$


Sources