Key Concepts of Cardinality of Sets

Why This Matters

Cardinality is how mathematicians answer a deceptively simple question: how big is a set? For finite sets, this is straightforward—just count the elements. But for infinite sets, things get wonderfully strange. You're being tested on your ability to rigorously compare set sizes using bijections, distinguish between countable and uncountable infinities, and apply foundational theorems like Cantor's theorem and the Schröder-Bernstein theorem. These concepts form the backbone of modern set theory and appear throughout analysis, topology, and logic.

The key insight is that "infinity" isn't one thing—there's a whole hierarchy of infinities, and cardinality gives us the tools to navigate it. When you encounter cardinality problems on exams, you're demonstrating mastery of formal comparison techniques, proof strategies involving injections and bijections, and the surprising behavior of infinite sets. Don't just memorize that the reals are uncountable—understand why Cantor's diagonal argument works and how bijections serve as the gold standard for comparing set sizes.

---

Foundational Definitions

Before comparing infinities, you need precise language for what "size" means in set theory. Cardinality formalizes intuition about set size through the existence (or non-existence) of certain functions between sets.

Definition of Cardinality

• Cardinality measures the "size" of a set—for finite sets, it's simply the element count; for infinite sets, it's a cardinal number
• Two sets have equal cardinality if and only if there exists a bijection between them—this is the formal definition, not just a test
• Notation varies by context: $|A|$ or $\text{card}(A)$ denotes the cardinality of set $A$

Bijective Functions

• A bijection is both injective (one-to-one) and surjective (onto)—every element in the codomain is hit exactly once
• Bijections are the "measuring stick" for cardinality—if $f: A \to B$ is a bijection, then $|A| = |B|$
• Finding a bijection proves equal size; proving no bijection exists shows different cardinalities

Finite and Infinite Sets

• Finite sets have cardinality equal to some natural number $n$—they can be listed as $\{a_1, a_2, \ldots, a_n\}$
• Infinite sets are not in bijection with any $\{1, 2, \ldots, n\}$—they're characterized by being bijectable with a proper subset of themselves
• Dedekind's definition: a set is infinite if and only if it has the same cardinality as one of its proper subsets

---

Countable vs. Uncountable: The First Great Divide

The distinction between countable and uncountable infinities is one of the most important ideas in mathematics. A set is countable if its elements can be "listed" in a sequence; uncountable sets are too large for any such listing.

Countable Sets and $\aleph_0$

• A set is countably infinite if it bijects with $\mathbb{N}$—the cardinality is denoted $\aleph_0$ (aleph-null), the smallest infinite cardinal
• Countable means "listable"—you can write the elements as a sequence $a_1, a_2, a_3, \ldots$ covering every element exactly once
• $\aleph_0$ is closed under countable unions—a countable union of countable sets remains countable

Cardinality of Rational Numbers

• $\mathbb{Q}$ is countably infinite despite being dense in $\mathbb{R}$—between any two reals, there's a rational, yet $|\mathbb{Q}| = \aleph_0$
• The standard proof uses a diagonal enumeration—arrange rationals in a grid by numerator and denominator, then traverse diagonally
• This is a classic exam example of how intuition fails: "more spread out" doesn't mean larger cardinality

Cardinality of Algebraic Numbers

• Algebraic numbers are roots of polynomials with rational coefficients—includes $\sqrt{2}$, $i$, and all rationals
• The set of algebraic numbers is countable—each polynomial has finitely many roots, and there are countably many polynomials
• Proof strategy: show algebraic numbers are a countable union of finite sets (roots of each polynomial)

---

Uncountable Infinities and the Continuum

Cantor's revolutionary discovery was that some infinities are strictly larger than others. The real numbers cannot be listed, no matter how clever your enumeration scheme.

Cardinality of Real Numbers ($\mathfrak{c}$)

• The continuum $\mathfrak{c} = |\mathbb{R}|$ is uncountably infinite—proved by Cantor's diagonal argument showing no bijection with $\mathbb{N}$ exists
• $\mathfrak{c} = 2^{\aleph_0}$—the cardinality of the reals equals the cardinality of the power set of naturals
• Any interval $(a, b)$ has cardinality $\mathfrak{c}$—use $f(x) = \tan\left(\pi x - \frac{\pi}{2}\right)$ to biject $(0,1)$ with $\mathbb{R}$

Cardinality of Transcendental Numbers

• Transcendental numbers are not algebraic—they satisfy no polynomial equation with rational coefficients (e.g., $\pi$, $e$)
• The transcendentals are uncountable since $\mathbb{R} = \text{algebraic} \cup \text{transcendental}$ and algebraic numbers are countable
• "Almost all" real numbers are transcendental—despite being harder to construct, they vastly outnumber algebraic numbers

---

Comparing Cardinalities: Tools and Theorems

How do you prove two sets have the same cardinality when constructing an explicit bijection is difficult? The Schröder-Bernstein theorem provides a powerful shortcut.

Schröder-Bernstein Theorem

• If injections exist in both directions, a bijection exists—formally, if $f: A \hookrightarrow B$ and $g: B \hookrightarrow A$, then $|A| = |B|$
• This avoids constructing an explicit bijection—you only need two one-to-one functions, not a single perfect correspondence
• Essential proof technique: when direct bijection is hard, find injections both ways and invoke Schröder-Bernstein

Comparison of Set Cardinalities

• $|A| \leq |B|$ means an injection $A \hookrightarrow B$ exists—$A$ is "no larger than" $B$
• $|A| < |B|$ means an injection exists but no bijection—$A$ is strictly smaller than $B$
• Cantor's theorem guarantees $|A| < |\mathcal{P}(A)|$ for every set $A$—there's no largest cardinality

---

Power Sets and Cantor's Theorem

Cantor's theorem is the engine that generates the infinite hierarchy of infinities. No set can surject onto its power set, which forces power sets to be strictly larger.

Power Set and Its Cardinality

• The power set $\mathcal{P}(S)$ contains all subsets of $S$—for finite $|S| = n$, we have $|\mathcal{P}(S)| = 2^n$
• For infinite sets, $|\mathcal{P}(S)| = 2^{|S|}$—this is cardinal exponentiation, not ordinary arithmetic
• $\mathcal{P}(\mathbb{N})$ bijects with $\mathbb{R}$—each subset corresponds to a binary sequence (characteristic function), hence $2^{\aleph_0} = \mathfrak{c}$

Cantor's Theorem

• For any set $S$, $|S| < |\mathcal{P}(S)|$—the power set is always strictly larger, even for infinite sets
• Proof uses diagonalization: assume $f: S \to \mathcal{P}(S)$ is surjective, then $D = \{x \in S : x \notin f(x)\}$ cannot be in the range
• Implies no largest cardinal—apply Cantor's theorem repeatedly: $\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots$

---

Cardinal Arithmetic and Open Questions

Cardinal arithmetic behaves very differently from ordinary arithmetic, especially at infinite scales. Adding or multiplying infinite cardinals often doesn't increase size.

Cardinal Arithmetic

• $\aleph_0 + \aleph_0 = \aleph_0$ and $\aleph_0 \cdot \aleph_0 = \aleph_0$—infinite cardinals "absorb" additions and multiplications of equal or smaller size
• $\kappa + \lambda = \kappa \cdot \lambda = \max(\kappa, \lambda)$ for infinite cardinals—the larger one dominates
• Exponentiation is where growth happens: $2^{\aleph_0} = \mathfrak{c} > \aleph_0$, and $2^\kappa > \kappa$ for all $\kappa$

Continuum Hypothesis

• CH states there's no cardinal strictly between $\aleph_0$ and $\mathfrak{c}$—equivalently, $\mathfrak{c} = \aleph_1$
• Proved independent of ZFC by Gödel and Cohen—it can neither be proved nor disproved from standard axioms
• Illustrates limits of formal systems—some natural mathematical questions have no definitive answer within our axioms

---

Quick Reference Table

---

Self-Check Questions

1. Both $\mathbb{Q}$ and the algebraic numbers are countably infinite, yet one is a proper subset of the other. Explain why proper containment doesn't imply smaller cardinality for infinite sets, and describe what would prove different cardinalities.

2. You need to prove $|(0,1)| = |\mathbb{R}|$. Would you use a direct bijection or Schröder-Bernstein? Construct the proof using your chosen method.

3. Compare and contrast Cantor's diagonal argument (proving $\mathbb{R}$ is uncountable) with the proof of Cantor's theorem ($|S| < |\mathcal{P}(S)|$). What structural similarity do they share?

4. Why is $\aleph_0 \cdot \aleph_0 = \aleph_0$ true, but $2^{\aleph_0} > \aleph_0$? What does this tell you about which operations "create" larger infinities?

5. If an FRQ asks you to determine whether a given set is countable or uncountable, outline a general strategy. What's your first move if the set is defined as a union? As a subset of $\mathbb{R}$?