Finite, Infinite, Countable and Uncountable Sets
Finite, Infinite, Countable and Uncountable Sets
How do you compare the “sizes” of infinite sets? The integers seem larger than the naturals, the rationals denser than both — yet all three are the same size. The reals, however, are genuinely larger. This post builds the complete theory of cardinality: what it means for two sets to have the same size, which infinite sets are countable, and why $\mathbb{R}$ is fundamentally different from $\mathbb{Q}$.
Finite, Infinite, Countable, Uncountable — Definitions
Two sets $A$ and $B$ are equinumerous ($A \sim B$) if there exists a bijection $f \colon A \to B$. Equinumerosity is the precise way to compare sizes of sets — for infinite sets it replaces naive counting.
Finite: $A$ is finite if $A = \emptyset$ or $A \sim {1,2,\ldots,n}$ for some $n \in \mathbb{N}$. Write $|A| = n$.
Infinite: $A$ is infinite if it is not finite. Equivalently (Dedekind): $A$ is infinite iff it is equinumerous with a proper subset of itself.
Countably infinite (denumerable): $A \sim \mathbb{N}$. Write $|A| = \aleph_0$.
Countable: $A$ is finite or countably infinite.
Uncountable: $A$ is infinite but NOT $\sim \mathbb{N}$.
Finite
$\emptyset$, $\{1,2,3\}$
$|A|=n$
Countably ∞
$\mathbb{N},\mathbb{Z},\mathbb{Q}$
$|A|=\aleph_0$
Uncountable
$\mathbb{R},(0,1)$
$|A|=\mathfrak{c}$
Even larger
$\mathcal{P}(\mathbb{R})$
$|A|=2^{\mathfrak{c}}$
📖 Reference: Rudin, W., Principles of Mathematical Analysis, 3rd ed., Ch. 2, §§2.1–2.14. Also: Apostol, T.M., Mathematical Analysis, 2nd ed., Ch. 1, §§1.14–1.16.
← Sets and Basic Notation — set language, power sets, Cartesian products.
← Functions and Relations — bijections are the core tool for comparing cardinalities.
← Logic and Proof Methods — proof by contradiction drives Cantor’s diagonal argument.
Intuition — Why ℕ, ℤ, ℚ Are the Same Size, but ℝ Is Bigger
The key insight is that size of infinite sets is measured by bijections, not by inclusion or density. Even though $\mathbb{N} \subsetneq \mathbb{Z} \subsetneq \mathbb{Q}$, we can match every integer to a unique natural number and vice versa — so they are the same size. The rationals, despite being dense on the number line, can also be listed one by one.
Suppose you claim to have listed every real number in $(0,1)$: $x_1, x_2, x_3, \ldots$ Cantor’s diagonal trick builds a real number $y$ that differs from $x_1$ in its 1st decimal digit, from $x_2$ in its 2nd, from $x_3$ in its 3rd, and so on. This $y$ is in $(0,1)$ but is not anywhere on your list — contradicting the claim that the list was complete. No matter how cleverly you list reals, there are always more.
Countability results (Rudin, Thm. 2.12–2.13):
- Every infinite subset of a countable set is countable.
- $\mathbb{Z}$ is countably infinite (explicit bijection to $\mathbb{N}$).
- $\mathbb{Q}$ is countably infinite (Cantor's first diagonal enumeration).
- A countable union of countable sets is countable: if each $A_n$ is countable, then $\bigcup_{n=1}^{\infty} A_n$ is countable.
Uncountability (Rudin, Thm. 2.14): $(0,1)$ is uncountable — hence $\mathbb{R}$ is uncountable with $|\mathbb{R}| = \mathfrak{c} > \aleph_0$.
Schroeder–Bernstein Theorem: If injections $f \colon A \to B$ and $g \colon B \to A$ both exist, then a bijection $h \colon A \to B$ exists. So $|A| = |B|$.
Cantor’s Power Set Theorem: For any set $A$, $|A| < |\mathcal{P}(A)|$. In particular $|\mathcal{P}(\mathbb{N})| = \mathfrak{c}$.
दो समुच्चयों का गणनांक (Cardinality) Bijection से मापा जाता है। गणनीय (Countable) समुच्चय वे हैं जिनका $\mathbb{N}$ से Bijection हो: $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ सभी $\aleph_0$ हैं। अगणनीय (Uncountable) समुच्चय: $\mathbb{R}$ की Cardinality $\mathfrak{c} > \aleph_0$ है। Cantor का विकर्ण तर्क (Diagonal Argument) Contradiction द्वारा सिद्ध करता है कि $(0,1)$ अगणनीय है। $\mathbb{R}\setminus\mathbb{Q}$ (अपरिमेय संख्याएँ) भी अगणनीय हैं।
Solved Examples
Define: $f(n) = \begin{cases} 0 & n = 1 \\ n/2 & n \text{ even} \\ -(n-1)/2 & n \text{ odd}, n \geq 3 \end{cases}$
Listing: $f(1),f(2),f(3),f(4),f(5),f(6),\ldots = 0, 1, -1, 2, -2, 3, \ldots$
Injective: Even and odd cases produce distinct non-negative / non-positive outputs; within each case $f$ is strictly monotone. $\checkmark$
Surjective: Every $k \geq 0$ is $f(2k)$ (or $f(1)$ for $k=0$); every $k < 0$ is $f(1-2k)$. $\checkmark$
Hence $f$ is a bijection and $|\mathbb{Z}| = |\mathbb{N}| = \aleph_0$. $\blacksquare$
Note $E \subsetneq \mathbb{N}$, yet we claim they are equinumerous.
Define: $f \colon \mathbb{N} \to E$ by $f(n) = 2n$.
Injective: $f(m)=f(n) \Rightarrow 2m=2n \Rightarrow m=n$. $\checkmark$
Surjective: Every even integer $2k \in E$ equals $f(k)$. $\checkmark$
So $|E| = \aleph_0$. This is the hallmark of infinite sets: a proper subset can have the same cardinality as the whole — this is in fact Dedekind's definition of an infinite set. $\blacksquare$
Define: $f \colon (0,1) \to \mathbb{R}$ by $f(x) = \tan\!\left(\pi\!\left(x - \tfrac{1}{2}\right)\right)$.
Well-defined: For $x \in (0,1)$, the argument $\pi(x-\tfrac{1}{2}) \in (-\tfrac{\pi}{2}, \tfrac{\pi}{2})$, where $\tan$ is defined. $\checkmark$
Injective: $\tan$ is strictly increasing on $(-\frac{\pi}{2}, \frac{\pi}{2})$, so $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$. $\checkmark$
Surjective: As $x \to 0^+$, $f(x) \to -\infty$; as $x \to 1^-$, $f(x) \to +\infty$. By the Intermediate Value Theorem, every $y \in \mathbb{R}$ is attained. $\checkmark$
Hence $|(0,1)| = |\mathbb{R}| = \mathfrak{c}$, showing that a bounded interval and the entire real line have the same cardinality. $\blacksquare$
Part 1 — $\mathbb{Q}$ is countable.
Arrange all positive rationals in an infinite array: entry $(p, q)$ is $p/q$ for $p, q \in \mathbb{N}$. Traverse the array by diagonals:
$\frac{1}{1} \to \frac{1}{2}$ $\frac{2}{1} \to \frac{2}{2}$ $\frac{3}{1} \cdots$
$\searrow$ $\nearrow\searrow$ $\nearrow$
$\frac{1}{2}$ $\frac{2}{2}$ $\frac{3}{2} \cdots$
Reading along diagonals: $\tfrac{1}{1}, \tfrac{1}{2}, \tfrac{2}{1}, \tfrac{1}{3}, \tfrac{2}{2}, \tfrac{3}{1}, \ldots$ — delete duplicates, prepend $0$ and negatives. This gives a surjection $\mathbb{N} \twoheadrightarrow \mathbb{Q}$, hence a bijection (since $\mathbb{Q}$ is infinite). So $|\mathbb{Q}| = \aleph_0$. $\checkmark$
Part 2 — $\mathbb{R} \setminus \mathbb{Q}$ is uncountable.
Suppose for contradiction that $\mathbb{R} \setminus \mathbb{Q}$ is countable. Then $\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q})$ would be a union of two countable sets, hence countable. But $\mathbb{R}$ is uncountable — contradiction. Therefore $\mathbb{R} \setminus \mathbb{Q}$ is uncountable. $\blacksquare$
Quick Revision Cards
📊 A — Cardinalities & Key Facts
- $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=\aleph_0$
- $|\mathbb{R}|=|(0,1)|=\mathfrak{c}>\aleph_0$
- $|\mathcal{P}(\mathbb{N})|=\mathfrak{c}$
- Countable ∪ countable = countable
- $\mathbb{R}\setminus\mathbb{Q}$ uncountable
- $|A|<|\mathcal{P}(A)|$ for all $A$
⚙️ B — Conditions & Edge Cases
- Subset of countable = countable
- $\mathbb{Q}$ dense in $\mathbb{R}$ but still countable
- $(0,1) \subsetneq \mathbb{R}$ yet $|(0,1)|=|\mathbb{R}|$
- Dedekind: infinite ↔ $\sim$ proper subset
- Schroeder–Bernstein: two injections → bijection
- Diagonal argument needs decimal expansions in $(0,1)$
🎯 C — Exam Tips
- 🔵 CSIR NET: To show countable: bijection to $\mathbb{N}$, or subset/union of countables
- 🟢 GATE: To show uncountable: diagonal argument or contains a copy of $(0,1)$
- 🟠 IIT JAM: $\mathbb{R}\setminus\mathbb{Q}$ uncountable — standard proof via contradiction
- 🔴 B.Sc. Raj.: State bijection and verify injective + surjective explicitly
Common Mistakes
❌ Errors to Avoid
Wrong: "ℤ has more elements so $|\mathbb{Z}| > |\mathbb{N}|$." | Correct: The bijection $\mathbb{N} \leftrightarrow \mathbb{Z}$ shows $|\mathbb{N}| = |\mathbb{Z}| = \aleph_0$. For infinite sets, containment does NOT imply strict cardinality.
Wrong: "$\mathbb{Q}$ is dense in $\mathbb{R}$, so it must be uncountable." | Correct: $\mathbb{Q}$ is countable. Density (between any two reals lies a rational) is a topological property, completely independent of cardinality.
Wrong: "$(0,1) \subsetneq \mathbb{R}$ so $|(0,1)| < |\mathbb{R}|$." | Correct: The bijection $x \mapsto \tan(\pi(x-\frac{1}{2}))$ shows $|(0,1)| = |\mathbb{R}| = \mathfrak{c}$.
Wrong: "Using Cantor's diagonal to prove $\mathbb{N}$ is uncountable." | Correct: The diagonal argument constructs a new real from decimal expansions — it produces a number in $(0,1)$, not a natural number. It cannot be applied to $\mathbb{N}$.
Real-World Applications
Computability Theory
Programs are finite strings — countably many. Real-valued functions are uncountably many. Hence most functions are not computable. This is Turing's foundational insight.
Information Theory
A countably infinite alphabet can be encoded in binary (each symbol gets a finite codeword). Uncountable sets cannot be encoded with finite binary strings — the basis for data compression limits.
Measure Theory
Countable sets have Lebesgue measure zero. $\mathbb{Q}$ has measure zero inside $\mathbb{R}$, even though $\mathbb{Q}$ is dense — the foundation of Lebesgue integration and modern probability.
Cryptography — Randomness
True randomness requires sampling from an uncountable set (physical processes modelling $\mathbb{R}$). Pseudo-random generators produce sequences from a countable set and are thus inherently periodic.
Summary Table & Key Result
| Set | Cardinality | How established | Reference |
|---|---|---|---|
| $\mathbb{N}$ | $\aleph_0$ | Definition | Rudin §2.4 |
| $\mathbb{Z}$ | $\aleph_0$ | Explicit bijection $\mathbb{N}\to\mathbb{Z}$ | Rudin §2.12 |
| $\mathbb{Q}$ | $\aleph_0$ | Diagonal enumeration | Rudin §2.13 |
| $(0,1)$, $\mathbb{R}$ | $\mathfrak{c}$ | Cantor's diagonal argument | Rudin §2.14 |
| $\mathcal{P}(\mathbb{N})$ | $\mathfrak{c}$ | Binary representations | Cantor's thm |
| $\mathbb{R}\setminus\mathbb{Q}$ | $\mathfrak{c}$ | Contradiction via countable union | Example 4 |
The Cardinality Hierarchy:
\(0 \;<\; 1 \;<\; 2 \;<\; \cdots \;<\; \aleph_0 \;<\; \mathfrak{c} \;<\; 2^{\mathfrak{c}} \;<\; \cdots\)
$\mathbb{N} \sim \mathbb{Z} \sim \mathbb{Q}$ (all $\aleph_0$) $\qquad\qquad$ $\mathbb{R} \sim (0,1) \sim \mathcal{P}(\mathbb{N})$ (all $\mathfrak{c}$)
Countable union of countable sets is countable.
Cross-References & Related Posts
← Prerequisites: Sets and Basic Notation — set language and power sets | Functions and Relations — bijections | Logic and Proof Methods — proof by contradiction.
→ Next Topic: Algebraic Structures — Fields.
📖 Further Reading: Rudin, Ch. 2, §§2.1–2.14; Apostol, Ch. 1, §§1.14–1.16; Bartle & Sherbert, Ch. 1, §1.3.
How did you find this post?
Tap a reaction — counts are saved permanently on our server.
Found this helpful?
This article is free and will always remain so. If it helped you understand a concept or prepare for your exam, a small token of appreciation keeps this resource going for the next student.
Have a question, doubt, or thought about this post? Choose how you want to join the discussion below.
💬 Comment on Telegram — No account needed