Comparing Cardinalities

Cardinal comparison is not a museum piece; it is load-bearing machinery throughout modern mathematics and its applications.

Foundations and logic. The entire classification of infinite sets into countable and uncountable — and further into the hierarchy $\aleph_0, \aleph_1, \dots$ — rests on exactly the definitions given here. The question of whether there is a set strictly between $|\mathbb N|$ and $|\mathbb R|$ (the Continuum Hypothesis) is phrased entirely in the language of $\le$ and $\approx$ developed above, and is a central object of study in modern set theory and independence results (Gödel, Cohen).

Computability theory and complexity. Reductions between decision problems are often literally injections (or computable injections) witnessing that one problem is "no harder" than another; the notion of many-one reducibility is a computable analogue of $|A|\le|B|$, and cardinality-style arguments (diagonalization) prove the existence of undecidable and non-computable sets.

Combinatorics. Injective and bijective proofs — showing two finite structures have equal size by exhibiting an explicit bijection, rather than computing both counts and comparing numerals — are a core proof technique, a finite-world echo of exactly the equinumerosity idea developed here for arbitrary sets.

Measure theory and analysis. The distinction between countable and uncountable sets (a direct descendant of cardinal comparison) determines whether a set can have positive Lebesgue measure, underlies almost-everywhere convergence arguments, and separates "small" exceptional sets from "generic" behavior throughout real analysis.

Cryptography. Injective functions (and their inverses) are the mathematical backbone of encryption schemes: a cipher must act injectively on messages (no two distinct plaintexts may collide to the same ciphertext) precisely so that decryption is well-defined — an applied instance of the injection concept central to this article.

Statistics and data science. Encoding schemes (hashing, feature embeddings) rely on injectivity to guarantee no information is lost when mapping a data domain into another representation space; cardinality comparisons between a sample space and a representation space govern whether lossless encoding is even possible.

Ask the tutor: How does the Schröder–Bernstein theorem actually build a single bijection out of two given injections?

The finite case is the anchor for intuition. Suppose $A = \{\text{♣},\text{♦},\text{♥}\}$ and $B=\{1,2,3,4\}$. To see $|A|\le |B|$, exhibit an injection, say $\text{♣}\mapsto 1,\ \text{♦}\mapsto 2,\ \text{♥}\mapsto 3$: each suit lands on a distinct number, with room to spare (the number $4$ is unused). No injection can go the other way — $B$ has "too many" elements to fit into $A$ without a collision — and this is exactly the content of the Finite Sets and Counting pigeonhole principle. The definition of $\le$ simply extracts the "fits without collision" idea and detaches it from any finite counting process, so it survives unchanged when $A$ and $B$ are infinite. The famous twist is that for infinite sets, a set can be equinumerous with a proper subset of itself — something utterly impossible for finite sets. The natural numbers $\mathbb N=\{0,1,2,3,\dots\}$ and the even naturals $E=\{0,2,4,6,\dots\}$ give a clean picture: $E \subsetneq \mathbb N$, yet the map $n\mapsto 2n$ is a bijection $\mathbb N \to E$. There is no contradiction, because "same size" for infinite sets is defined by the existence of a bijection, not by some prior notion of counting that a proper-subset argument would violate. This is precisely what makes cardinal comparison a genuinely new and useful concept rather than a restatement of finite counting.

Note what is not claimed here: antisymmetry of $\le$, i.e. that $|A|\le|B|$ and $|B|\le|A|$ imply $A\approx B$. That implication is true but is a separate, much deeper theorem — the Schroeder-Bernstein Theorem — requiring a genuinely different construction (building a bijection out of two one-directional injections), and it is not a routine consequence of the preorder properties proved above.

Example 1: $\mathbb{Z}$ and $\mathbb{N}$ are equinumerous. Let $\mathbb N = \{0,1,2,3,\dots\}$ and let $\mathbb Z = \{\dots,-2,-1,0,1,2,\dots\}$. These look structurally different — $\mathbb Z$ has "twice as many" elements in the naive sense, stretching in two directions — yet we claim $\mathbb Z \approx \mathbb N$. Define $f : \mathbb N \to \mathbb Z$ by

Concretely: $f(0)=0,\ f(1)=-1,\ f(2)=1,\ f(3)=-2,\ f(4)=2,\ f(5)=-3,\dots$ — the map zig-zags outward from $0$, alternately hitting nonnegative and negative integers. Injectivity. Suppose $f(n_1) = f(n_2) = k$. If $k \ge 0$: the only way $f(n)=k\ge 0$ is via the even branch (the odd branch always outputs a strictly negative integer, since $\frac{n+1}{2}\ge 1$ for odd $n\ge 1$), so $n_1, n_2$ are both even with $n_1/2 = n_2/2 = k$, giving $n_1 = n_2 = 2k$. If $k<0$: only the odd branch can produce a negative value, so $n_1,n_2$ are odd with $-(n_1+1)/2 = -(n_2+1)/2 = k$, giving $n_1 = n_2 = -2k-1$. Either way $n_1 = n_2$. Surjectivity. Given $k \in \mathbb Z$: if $k \ge 0$, take $n = 2k$ (even), and $f(n) = k$. If $k < 0$, take $n = -2k - 1$ (odd, since $-2k-1$ is odd for any integer $k$), and $f(n) = -\frac{(-2k-1)+1}{2} = -\frac{-2k}{2} = k$. So $f$ is a bijection, hence $\mathbb Z \approx \mathbb N$, i.e. $|\mathbb Z| = |\mathbb N|$. This is our first hint that "$\mathbb N$-sized" infinity (later called countable, see Countable Sets) can absorb sets that look larger.

Example 2: $|\mathbb{N}| \le |\mathbb{Q}^+|$ and $|\mathbb Q^+| \le |\mathbb N \times \mathbb N|$, via explicit injections (asymmetric, non-bijective witnesses). Here we illustrate the inequality notion with maps that are injective but deliberately not surjective, to show $\le$ does not require a bijection. Let $\mathbb Q^+$ denote the positive rationals. First, $|\mathbb N| \le |\mathbb Q^+|$: define $g:\mathbb N \to \mathbb Q^+$ by $g(n) = n+1$ (viewing each natural number $n+1$ as the rational $\frac{n+1}{1}$). This is injective (if $n_1 + 1 = n_2+1$ then $n_1=n_2$) but wildly non-surjective — it misses every non-integer rational such as $\frac{1}{2}$ or $\frac{7}{3}$. That is fine: $\le$ only demands an injection, not a bijection. Second, exhibit an injection $h : \mathbb Q^+ \to \mathbb N \times \mathbb N$. Every positive rational has a unique representation as $\frac{p}{q}$ with $p,q \in \mathbb N_{\ge 1}$ and $\gcd(p,q)=1$ (lowest terms). Define

Injectivity. If $h(r_1) = h(r_2) = (p,q)$, then by definition both $r_1$ and $r_2$ equal the lowest-terms fraction $p/q$, so $r_1 = r_2$. This $h$ is again far from surjective: e.g. $(2,4)\in\mathbb N\times\mathbb N$ is never hit, since $2/4$ is not in lowest terms (it reduces to $1/2$, whose lowest-terms pair is $(1,2)$). By transitivity of $\le$ (part 4 of the theorem, using the composite $h \circ g'$ for any fixed injection $g':\mathbb N\to\mathbb Q^+$ composed appropriately — here directly $h$ itself already lands in $\mathbb N\times\mathbb N$), we get $|\mathbb N| \le |\mathbb Q^+| \le |\mathbb N\times\mathbb N|$. Combined with the standard Cantor pairing bijection $\mathbb N \times \mathbb N \approx \mathbb N$ (constructed elsewhere), one obtains a chain of inequalities that — once Schröder–Bernstein is available — collapses to $|\mathbb Q^+| = |\mathbb N|$. At the present stage, without invoking that theorem, we have rigorously shown only the one-directional inequalities above; this is exactly the kind of gap Schröder–Bernstein is built to close, and it is worth seeing that gap concretely before filling it.