Comparing cardinal numbers

RULE 2: $    #S &le#le;#T &iff#iff;$ there exists an injection $f: S &rarr#rightarrow;T$.

Loosely speaking, $S$ is smaller or equal in size to $T$ if and only if one can match the elements of $S$ with elements of $T$ so that all elements of $S$ get used (but maybe some elements of $T$ are left over). For example, there is an injection $\{a,b,c\} \rightarrow {\mathbb{N}}$ sending $a$ to $1$, $b$ to $2$, and $c$ to $17$; this proves that $3 \le \aleph_0$. As a special case of Rule 2, if $S \subseteq T$, then $\char93 S \le \char93 T$.

The relations $=$ and $\le$ for cardinals satisfy the same properties as they do for ordinary numbers:

1. $\char93 S =\char93 S$ for any set $S$ (reflexivity).
2. If $\char93 S=\char93 T$, then $\char93 T=\char93 S$ (symmetry).
3. If $\char93 S=\char93 T$ and $\char93 T = \char93 U$, then $\char93 S = \char93 U$ (transitivity).
4. If $\char93 S=\char93 T$, then $\char93 S \le \char93 T$.
5. If $\char93 S \le \char93 T$ and $\char93 T \le \char93 U$, then $\char93 S \le \char93 U$ (transitivity).
6. For any two sets $S$ and $T$, either $\char93 S \le \char93 T$ or $\char93 T \le \char93 S$.
7. If $\char93 S \le \char93 T$ and $\char93 T \le \char93 S$, then $\char93 S=\char93 T$.

The last two are fairly difficult to deduce from the definitions. The last one is called the Schröder-Bernstein Theorem; it says that if there exist injections $S \rightarrow T$ and $T \rightarrow S$, then there exists a bijection $S \rightarrow T$. (This appeared as a problem on one of the monthly contests.)

The other relations like $\ge$, $<$, and $>$ can be defined in terms of $=$ and $\le$. For instance, ``$\char93 S > \char93 T$'' means `` $\char93 T \le \char93 S$ is true and $\char93 S=\char93 T$ is false.''