∫ SJ Maths Mathematics Notes
UP PGT Tracker UP TGT Tracker
Real Analysis

Countability of sets

Countability classifies sets by their cardinality relative to the natural numbers $\mathbb{N}$, distinguishing between finite, countably infinite, and uncountable sets using bijective mappings. This topic covers this topic.

For: UP PGT Mathematics UP TGT Mathematics DSSSB PGT / TGT KVS / NVS PGT LT Grade
📖 Topic progress
○ Mark as complete

Definition and statement

Cantor's Theorem & Countability Criteria
A set $S$ is said to be countable if there exists an injective function $f: S \to \mathbb{N}$ or a surjective function $g: \mathbb{N} \to S$. Furthermore, the power set $\mathcal{P}(S)$ of any set $S$ is never countable; specifically, $|S| < |\mathcal{P}(S)|$.

📐 Geometric Interpretation

Countability allows the elements of a set to be arranged in a discrete, infinite sequence $(x_1, x_2, x_3, \dots)$ without any gaps, whereas uncountability (such as $\mathbb{R}$ on any interval) possesses a continuum cardinality that cannot be exhausted by any sequential enumeration.

⚙️ Algebraic & Structural Meaning

Algebraically, countable sets preserve structural properties under countable unions (e.g., $\mathbb{Q}$ is countable), forming the foundational framework for measure theory, point-set topology, and real analysis.

Conditions and hypotheses

Check each condition and what changes when it is omitted:

Hypothesis / Condition Domain / Interval Necessity What Fails If Condition Dropped
Existence of Bijection / Injection Arbitrary set $S$ mapped to $\mathbb{N}$ Strictly Mandatory If no injective map into $\mathbb{N}$ exists, the set is uncountable (e.g., $\mathbb{R}$, $(0,1)$).
Countable Union Axiom Collection of countable sets $\{A_n\}_{n=1}^\infty$ Requires Axiom of Countable Choice Without countable choice, a countable union of countable sets may fail to be countable in constructive mathematics.
Cartesian Product Domain Product of countable sets $A \times B$ Essential for product theorem If either set is uncountable, the product becomes uncountable (with few degenerate exceptions).

Useful results and shortcuts

Use these identities and results when their conditions apply:

01

Countable Union Rule

$$ \text{If } A_n \text{ is countable } \forall n \in \mathbb{N}, \text{ then } \bigcup_{n=1}^\infty A_n \text{ is countable.} $$

Rule: Any countable collection of countable sets yields a countable union. Instantly mark countable for polynomial sets, rational coefficients, etc.

Application: undefined
02

Finite Cartesian Product Rule

$$ A_1, A_2, \dots, A_k \text{ countable} \implies A_1 \times A_2 \times \dots \times A_k \text{ is countable.} $$

Rule: Finite products of countable sets are countable. However, infinite arbitrary products of sets with size $\ge 2$ are uncountable.

Application: undefined
03

Algebraic vs Transcendental Numbers

$$ \mathbb{A} \text{ (Algebraic Numbers)} \sim \mathbb{N} \implies \mathbb{T} = \mathbb{R} \setminus \mathbb{A} \text{ is uncountable.} $$

Rule: The set of all algebraic numbers is countable. Since $\mathbb{R}$ is uncountable, transcendental numbers form an uncountable set of 'full measure'.

Application: undefined
04

Subsets of Countable Sets

$$ B \subseteq A \text{ and } A \text{ is countable} \implies B \text{ is finite or countable.} $$

Rule: Infinite subsets of countable sets are always countably infinite.

Application: undefined
05

Power Set Cardinality Rule

$$ |S| < |\mathcal{P}(S)| $$

Rule: The power set of any infinite set strictly increases cardinality. $\mathcal{P}(\mathbb{N})$ is equipotent to $\mathbb{R}$.

Application: undefined
06

Set of Sequences of 0s and 1s

$$ \{0, 1\}^{\mathbb{N}} \sim \mathcal{P}(\mathbb{N}) \sim \mathbb{R} \text{ (Uncountable)} $$

Rule: The set of all infinite sequences formed by digits {0, 1} is uncountable by Cantor's diagonal argument.

Application: undefined

Common errors and counterexamples

These examples show how a conclusion can fail when a condition is missing:

⚠️ COMMON ERROR #01

Infinite Cartesian Product Confusion

Common Pitfall: Assuming infinite cartesian products of countable sets remain countable.

Counterexample: $$ \prod_{n=1}^\infty \{0, 1\} \text{ is uncountable (equipotent to } \mathbb{R}) $$

Why it fails: Cantor's diagonal argument proves that infinite sequences from a 2-element set form an uncountable continuum.

🛡️ Exam Defense: Finite product of countable sets is countable; infinite product of sets with size $>1$ is uncountable.
⚠️ COMMON ERROR #02

Rational vs Real Interval Equivalence

Common Pitfall: Confusing the countability of $\mathbb{Q} \cap [0,1]$ with $[0,1]$.

Counterexample: $Q \cap [0,1]$ is countable, whereas $[0,1]$ is uncountable.

Why it fails: Density of rationals does not imply countability of the continuum.

🛡️ Exam Defense: Any interval of real numbers $[a, b]$ with $a < b$ is always uncountable.

Comparison

Concept / TheoremHypotheses / AssumptionsKey Formula / OutcomeGeometric MeaningExam Identification Clue
Set of Integers $\mathbb{Z}$ / Rationals $\mathbb{Q}$Mapped via zig-zag enumerationCountably infinite ($\aleph_0$)Discrete countable pointsContains only algebraic fractions or integers
Real Interval $(0,1)$Cantor's Diagonal ArgumentUncountable ($c$ or $2^{\aleph_0}$)Continuous unbroken line segmentContains all decimal expansions
Set of Polynomials with $\mathbb{Z}$ coefficientsCountable union of finite degree polynomialsCountably infiniteDiscrete algebraic curvesCoefficients restricted to $\mathbb{Z}$ or $\mathbb{Q}$
Power Set of $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$Set of all subsets of $\mathbb{N}$Uncountable ($2^{\aleph_0}$)Collection of all subsetsPhrased as 'set of all subsets'

Solved examples

Each problem includes a full solution and a shorter method:

CANONICAL PROBLEM 01 Dual-Method Breakdown

Which of the following sets is uncountable?

(A) The set of all prime numbers(B) The set of all rational numbers $\mathbb{Q}$(C) The set of all functions from $\mathbb{N}$ to \{0, 1\}(D) The set of all finite subsets of $\mathbb{N}$
✓ Correct Answer: (C)
📚 Method A: Formal Textbook Derivation
Step 1: Primes, $\mathbb{Q}$, and finite subsets of $\mathbb{N}$ are countable. Step 2: The set of functions from $\mathbb{N}$ to \{0, 1\} corresponds to $\mathcal{P}(\mathbb{N})$, which is uncountable by Cantor's theorem.
⚡ Method B: 25-Second Exam Shortcut
Functions from a countable set to a set of size $\ge 2$ yield an uncountable set.
💡 Tip: Look for mapping spaces or power sets to instantly spot uncountability.
CANONICAL PROBLEM 02 Dual-Method Breakdown

Let $S$ be the set of all sequences of integers. Then $S$ is:

(A) Finite(B) Countably infinite(C) Uncountable(D) Empty
✓ Correct Answer: (C)
📚 Method A: Formal Textbook Derivation
The set of sequences of integers $\mathbb{Z}^{\mathbb{N}}$ contains $\{0,1\}^{\mathbb{N}}$ as a subset. Since $\{0,1\}^{\mathbb{N}}$ is uncountable, $\mathbb{Z}^{\mathbb{N}}$ must be uncountable.
⚡ Method B: 25-Second Exam Shortcut
Infinite product of sets of size $\ge 2$ is uncountable.
💡 Tip: Sequence spaces over infinite sets are always uncountable.

Practice questions

Choose an answer to check it and see the solution:

Q1
MCQ 1: The set of all algebraic numbers $\mathbb{A}$ is:
A Finite
B Countably infinite
C Uncountable
D None of these
Derivation & Analysis:

Since each polynomial has a finite number of roots and polynomials with rational coefficients form a countable set, their roots form a countable union of finite sets, hence countably infinite.

Q2
MCQ 2: Which of the following is a countable set?
A The set of all irrational numbers
B The set of all subsets of $\mathbb{N}$
C The set of all polynomials of degree $\le n$ with integer coefficients
D The set of all real numbers in $[0,1]$
Derivation & Analysis:

Polynomials of degree $\le n$ with integer coefficients form a finite Cartesian product of countable sets $\mathbb{Z}^{n+1}$, which is countable.

Q3
MCQ 3: The set of all rational numbers $\mathbb{Q}$ is:
A Finite
B Countably infinite
C Uncountable
D None
Derivation & Analysis:

Can be enumerated using Cantor's diagonal zig-zag pairing method, proving $\mathbb{Q} \sim \mathbb{N}$.

Q4
MCQ 4: Let $A = \{f : \mathbb{N} \to \{0, 1, 2\}\}$. The cardinality of $A$ is equal to:
A $\aleph_0$
B $2^{\aleph_0}$
C $\aleph_0 \cdot \aleph_0$
D Finite
Derivation & Analysis:

The set of functions from $\mathbb{N}$ to a 3-element set has cardinality $3^{\aleph_0} = 2^{\aleph_0}$, which is the cardinality of the continuum.

Q5
MCQ 5: The union of a countable collection of countable sets is:
A Always finite
B Always countable
C Always uncountable
D Can be anything
Derivation & Analysis:

By the Countable Union Theorem, a countable union of countable sets is always countable.

Q6
MCQ 6: The open interval $(0, 1)$ is equipotent to:
A $\mathbb{N}$
B $\mathbb{Z}$
C $\mathbb{R}$
D None of these
Derivation & Analysis:

Intervals like $(0,1)$ can be mapped bijectively to $\mathbb{R}$ via functions like $f(x) = \tan(\pi(x - 1/2))$, so it has cardinality $c = |\mathbb{R}|$.

Q7
MCQ 7: Which of the following sets is uncountable?
A Set of prime numbers
B Set of even integers
C Set of all subsets of $\mathbb{Z}$
D Set of rational numbers
Derivation & Analysis:

The set of all subsets of $\mathbb{Z}$ is $\mathcal{P}(\mathbb{Z})$, which has cardinality $2^{\aleph_0}$, making it uncountable.

Q8
MCQ 8: Assertion (A): The set of transcendental numbers is uncountable. Reason (R): $\mathbb{R}$ is uncountable and $\mathbb{A}$ (algebraic numbers) is countable.
A Both (A) and (R) are true and (R) is the correct explanation of (A)
B Both (A) and (R) are true but (R) is not the correct explanation
C (A) is true, (R) is false
D (A) is false, (R) is true
Derivation & Analysis:

Since $\mathbb{R} = \mathbb{A} \cup \mathbb{T}$ (disjoint union) and $\mathbb{R}$ is uncountable while $\mathbb{A}$ is countable, $\mathbb{T}$ must be uncountable.

Q9
MCQ 9: The set of all finite subsets of the set of natural numbers $\mathbb{N}$ is:
A Finite
B Countably infinite
C Uncountable
D None of these
Derivation & Analysis:

Let $F_n$ be the set of subsets of $\mathbb{N}$ of size $n$. Each $F_n$ is countable, and the set of all finite subsets is $\bigcup_{n=1}^\infty F_n$, a countable union of countable sets.

Q10
MCQ 10: If $A$ is an infinite set and $B$ is a countable set, then $A \cup B$ is:
A Always countable
B Always uncountable
C Equipotent to $A$
D Finite
Derivation & Analysis:

The union of an infinite set with a countable set has the same cardinality as the infinite set $A$.

Common questions

Rationals can be arranged in a systematic 2D grid and enumerated in a zig-zag sequence (Cantor's pairing). Reals cannot be listed in any sequence because Cantor's diagonal argument constructs a real number not present in any purported countable list.

Confusing finite products with infinite products, or forgetting that the power set of any infinite set strictly increases cardinality.

Memorize standard results: $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{A}$, and finite subsets are countable; $\mathbb{R}$, intervals, power sets, and infinite sequence spaces over non-trivial sets are uncountable.

← Previous Topic
Bolzano-Weierstrass theorem
Next Topic →
Left-hand and right-hand limits