Real Numbers, Sets and Countability
CSIR NET real analysis: countable and uncountable sets, Cantor's theorem, R as a complete ordered field, Archimedean property, sup and inf, with practice.
- 21 min
On this page · 15 sections
Prerequisites
- Sets, functions, injections, surjections and bijections from a first course. Nothing else.
- This is the first topic of Real Analysis. The completeness axiom proved here drives everything in Sequences, Series, limsup and liminf, and countability comes back as “measure zero” in Riemann, Improper and Lebesgue Integration.
- For how the paper is marked, see the Mathematical Sciences overview.
The Hook: A Hole in the Rationals
Sets, Functions and Cardinality
Two sets \( A \) and \( B \) have the same cardinality, written \( \lvert A \rvert = \lvert B \rvert \), if there is a bijection \( A \to B \). We write \( \lvert A \rvert \le \lvert B \rvert \) if there is an injection \( A \to B \).
- \( A \) is finite if it is empty or in bijection with \( \{1, \dots, n\} \) for some \( n \).
- \( A \) is countably infinite (denumerable) if \( \lvert A \rvert = \lvert \mathbb{N} \rvert \). Its cardinality is written \( \aleph_0 \).
- \( A \) is countable if it is finite or countably infinite. Otherwise it is uncountable.
Two theorems that settle most questions
Schröder–Bernstein theorem. If there are injections \( A \to B \) and \( B \to A \), then \( \lvert A \rvert = \lvert B \rvert \). You never need to build the bijection; two injections suffice.
Cantor’s theorem. For every set \( A \), \( \lvert A \rvert < \lvert \mathcal{P}(A) \rvert \). There is an injection \( a \mapsto \{a\} \), but no surjection \( f : A \to \mathcal{P}(A) \): the set \( D = \{a \in A : a \notin f(a)\} \) is not \( f(a) \) for any \( a \). So there is no largest cardinal.
Countable Sets
The basic toolkit
- Every subset of a countable set is countable.
- The image of a countable set under any function is countable.
- \( \mathbb{N} \times \mathbb{N} \) is countable. The map \( (m, n) \mapsto 2^m 3^n \) is an injection into \( \mathbb{N} \), by unique factorisation.
- A finite product of countable sets is countable.
- A countable union of countable sets is countable. (The standard proof chooses an enumeration of each set; this uses the axiom of countable choice, which all MSc courses assume.)
From these:
| Set | Why countable |
|---|---|
| \( \mathbb{Z} \) | \( 0, 1, -1, 2, -2, \dots \) |
| \( \mathbb{Q} \) | image of \( \mathbb{Z} \times \mathbb{N} \) under \( (p, q) \mapsto p/q \) |
| \( \mathbb{Q}^n \) | finite product |
| Polynomials with integer (or rational) coefficients | union over degree \( n \) of copies of \( \mathbb{Z}^{n+1} \) |
| Algebraic numbers | each polynomial has finitely many roots; countable union of finite sets |
| Finite subsets of \( \mathbb{N} \) | union over \( n \) of the subsets of \( \{1,\dots,n\} \) |
| Finite strings over a countable alphabet | union over length |
| Sequences in \( \mathbb{N} \) that are eventually zero | determined by a finite string |
| Any family of pairwise disjoint open intervals in \( \mathbb{R} \) | pick a rational in each; injection into \( \mathbb{Q} \) |
| Discontinuities of a monotone function | each jump contains its own rational |
The last two rows are favourite Part C ingredients. The rational-in-each-interval argument also proves that every open subset of \( \mathbb{R} \) is a countable union of disjoint open intervals.
Uncountable Sets
Cantor’s diagonal argument
Suppose \( (0,1) \) were listed as \( x_1, x_2, x_3, \dots \), with decimal expansions \( x_n = 0.d_{n1}d_{n2}d_{n3}\dots \) (choose the expansion that does not end in recurring 9s). Define \( y = 0.e_1 e_2 e_3 \dots \) with \( e_n = 5 \) if \( d_{nn} \ne 5 \) and \( e_n = 4 \) if \( d_{nn} = 5 \). Then \( y \) differs from \( x_n \) in the \( n \)-th digit for every \( n \), and \( y \) has a unique expansion, so \( y \ne x_n \) for all \( n \). The list misses \( y \).
The standard uncountable sets
| Set | Cardinality | Reason |
|---|---|---|
| \( \mathbb{R} \), any non-degenerate interval | \( \mathfrak{c} \) | \( \tan \) gives \( (-\pi/2, \pi/2) \to \mathbb{R} \) |
| Irrationals \( \mathbb{R} \setminus \mathbb{Q} \) | \( \mathfrak{c} \) | if countable, \( \mathbb{R} \) would be a union of two countable sets |
| Transcendental numbers | \( \mathfrak{c} \) | complement of the countable algebraic numbers |
| \( \mathcal{P}(\mathbb{N}) \) | \( \mathfrak{c} = 2^{\aleph_0} \) | Cantor’s theorem; binary expansions |
| \( \{0,1\}^{\mathbb{N}} \), all 0-1 sequences | \( \mathfrak{c} \) | indicator functions of subsets of \( \mathbb{N} \) |
| \( \mathbb{N}^{\mathbb{N}} \), all sequences of naturals | \( \mathfrak{c} \) | contains \( \{0,1\}^{\mathbb{N}} \); injects into \( \mathbb{R} \) |
| Infinite subsets of \( \mathbb{N} \) | \( \mathfrak{c} \) | complement in \( \mathcal{P}(\mathbb{N}) \) of a countable set |
| Strictly increasing sequences in \( \mathbb{N} \) | \( \mathfrak{c} \) | bijection with infinite subsets (the range) |
| \( \mathbb{R}^n \), \( \mathbb{C} \) | \( \mathfrak{c} \) | interleave decimal digits; or Schröder–Bernstein |
| Cantor set | \( \mathfrak{c} \) | ternary expansions using only 0 and 2 |
| \( C[0,1] \), continuous real functions | \( \mathfrak{c} \) | a continuous function is fixed by its values on \( \mathbb{Q} \cap [0,1] \) |
| All functions \( \mathbb{R} \to \mathbb{R} \) | \( 2^{\mathfrak{c}} > \mathfrak{c} \) | contains indicator functions of all subsets of \( \mathbb{R} \) |
The Real Numbers as a Complete Ordered Field
\( \mathbb{R} \) is a set with \( + \), \( \cdot \) and \( < \) satisfying three groups of axioms.
- Field axioms. \( (\mathbb{R}, +, \cdot) \) is a field.
- Order axioms. \( < \) is a total order compatible with the operations: \( x < y \Rightarrow x + z < y + z \), and \( x, y > 0 \Rightarrow xy > 0 \).
- Completeness (least upper bound property). Every non-empty subset of \( \mathbb{R} \) that is bounded above has a least upper bound in \( \mathbb{R} \).
\( \mathbb{Q} \) satisfies 1 and 2 but not 3 (the hook). Up to an order-preserving field isomorphism, \( \mathbb{R} \) is the only complete ordered field. It can be built from \( \mathbb{Q} \) by Dedekind cuts (Rudin, Chapter 1) or by equivalence classes of Cauchy sequences.
Consequences of completeness
Archimedean property. For any \( x \in \mathbb{R} \) and \( y > 0 \) there is \( n \in \mathbb{N} \) with \( ny > x \). Proof: if not, \( \{ny : n \in \mathbb{N}\} \) is bounded above by \( x \); let \( s \) be its sup. Then \( s - y \) is not an upper bound, so \( my > s - y \) for some \( m \), giving \( (m+1)y > s \), a contradiction. Equivalent forms: \( \mathbb{N} \) is not bounded above; \( \frac{1}{n} \to 0 \).
Density. Between any two reals \( a < b \) there is a rational (choose \( n \) with \( n(b - a) > 1 \), then an integer \( m \) with \( na < m < nb \)) and an irrational (take a rational between \( a/\sqrt{2} \) and \( b/\sqrt{2} \), non-zero, times \( \sqrt{2} \)). Hence each interval contains infinitely many of both.
Existence of roots. For \( x > 0 \) and \( n \in \mathbb{N} \) there is a unique \( y > 0 \) with \( y^n = x \): \( y = \sup\{t > 0 : t^n < x\} \).
Equivalent forms of completeness. In an Archimedean ordered field the following are equivalent, and each can serve as the completeness axiom:
| Form | Statement |
|---|---|
| Least upper bound property | non-empty, bounded above \( \Rightarrow \) sup exists |
| Monotone convergence | bounded monotone sequences converge |
| Nested intervals | \( [a_n, b_n] \supseteq [a_{n+1}, b_{n+1}] \Rightarrow \bigcap_n [a_n, b_n] \ne \emptyset \) |
| Bolzano–Weierstrass | every bounded sequence has a convergent subsequence |
| Cauchy completeness | every Cauchy sequence converges |
The Archimedean hypothesis matters only for the nested interval and Cauchy forms; the first, second and fourth imply it on their own.
Supremum and Infimum
Let \( A \subseteq \mathbb{R} \) be non-empty and bounded above. \( s = \sup A \) is the number with
- \( a \le s \) for all \( a \in A \) (upper bound), and
- for every \( \varepsilon > 0 \) there is \( a \in A \) with \( a > s - \varepsilon \) (nothing smaller is an upper bound).
The infimum is defined dually, and \( \inf A = -\sup(-A) \). If \( \sup A \in A \) it is the maximum of \( A \). Conventionally \( \sup A = +\infty \) when \( A \) is not bounded above.
Sequential characterisation. \( s = \sup A \) if and only if \( s \) is an upper bound and there is a sequence \( a_n \in A \) with \( a_n \to s \). So \( \sup A \in \overline{A} \) always.
Algebra of sup and inf
For non-empty bounded \( A, B \subseteq \mathbb{R} \) and \( c \in \mathbb{R} \):
| Set | Supremum |
|---|---|
| \( A + B = \{a + b\} \) | \( \sup A + \sup B \) |
| \( A - B = \{a - b\} \) | \( \sup A - \inf B \) |
| \( cA \), \( c > 0 \) | \( c \sup A \) |
| \( cA \), \( c < 0 \) | \( c \inf A \) |
| \( A \subseteq B \) | \( \sup A \le \sup B \), \( \inf A \ge \inf B \) |
| \( AB = \{ab\} \), \( A, B \subseteq (0, \infty) \) | \( \sup A \cdot \sup B \) |
| \( A \cup B \) | \( \max(\sup A, \sup B) \) |
| \( A \cap B \) (if non-empty) | \( \le \min(\sup A, \sup B) \), equality can fail |
For functions on a common domain, \( \sup (f + g) \le \sup f + \sup g \), and the inequality can be strict: \( f(x) = x \), \( g(x) = 1 - x \) on \( [0,1] \) give \( \sup(f+g) = 1 < 2 \). The set identity \( \sup(A+B) = \sup A + \sup B \) holds because \( a \) and \( b \) vary independently; in \( f + g \) they are tied to the same \( x \).
Computing sup and inf
Counter-examples Table
| False claim | Counter-example |
|---|---|
| Every non-empty bounded subset of \( \mathbb{Q} \) has a sup in \( \mathbb{Q} \) | \( \{x \in \mathbb{Q} : x^2 < 2\} \) |
| A bounded set contains its sup | \( (0,1) \); \( \{1 - \frac{1}{n}\} \) |
| An infinite subset of \( \mathbb{R} \) is uncountable | \( \mathbb{Q} \), \( \mathbb{N} \) |
| An uncountable subset of \( \mathbb{R} \) contains an interval | Cantor set; the irrationals |
| A countable set is closed | \( \mathbb{Q} \); \( \{\frac{1}{n} : n \in \mathbb{N}\} \) (misses 0) |
| A dense subset of \( \mathbb{R} \) is uncountable | \( \mathbb{Q} \) |
| \( \sup(AB) = \sup A \cdot \sup B \) for all bounded sets | \( A = B = \{-2, -1\} \): \( \sup AB = 4 \), \( \sup A \sup B = 1 \) |
| \( \sup(A \cap B) = \min(\sup A, \sup B) \) | \( A = \{0, 2\} \), \( B = \{0, 3\} \): \( \sup(A \cap B) = 0 \) |
| A countable union of finite sets is finite | \( \mathbb{N} = \bigcup_n \{n\} \) |
| The set of all subsets of a countable set is countable | \( \mathcal{P}(\mathbb{N}) \) |
| Nested non-empty intervals always meet | \( (0, \frac{1}{n}) \); \( [n, \infty) \) |
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| sup (least upper bound; may lie outside the set) | max (largest element; must lie in the set) | |
| countable (finite or \( \aleph_0 \)) | countably infinite (exactly \( \aleph_0 \)) | |
| \( \mathbb{Q} \) dense (meets every interval) | open (contains an interval around each point); \( \mathbb{Q} \) is not open | |
| measure zero (small in length) | countable (small in cardinality); the Cantor set is the first but not the second | |
| finite subsets of \( \mathbb{N} \) (countable) | all subsets of \( \mathbb{N} \) (uncountable) | |
| eventually zero sequences (countable) | all 0-1 sequences (uncountable) |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- Is the set of all finite subsets of \( \mathbb{N} \) countable?
- Find sup and inf of \( \{1 - \frac{1}{n} : n \in \mathbb{N}\} \). Which is attained?
- State the Archimedean property.
Answers
- Yes. It is \( \bigcup_n \mathcal{P}(\{1, \dots, n\}) \), a countable union of finite sets.
- sup = 1 (not attained), inf = 0 (attained at \( n = 1 \)).
- For every \( x \in \mathbb{R} \) and \( y > 0 \) there is \( n \in \mathbb{N} \) with \( ny > x \). Equivalently, \( \mathbb{N} \) is not bounded above in \( \mathbb{R} \).
Level 2: Part B Style
Practice Q1. Which of the following sets is uncountable?
(a) \( \mathbb{Q} \times \mathbb{Q} \) (b) the set of algebraic numbers (c) the set of all sequences of 0s and 1s (d) the set of polynomials with rational coefficients
Answer: (c)
\( \{0,1\}^{\mathbb{N}} \) is in bijection with \( \mathcal{P}(\mathbb{N}) \), uncountable by Cantor’s theorem. (a) is a finite product of countable sets; (b) is a countable union of finite root sets; (d) is a countable union over degree of copies of \( \mathbb{Q}^{n+1} \).
Practice Q2. Let \( A = \left\{ (-1)^n \left(1 - \frac{1}{n}\right) : n \in \mathbb{N} \right\} \). Then:
(a) \( \sup A = 1 \), \( \inf A = -1 \), neither attained (b) \( \sup A = 1 \) attained, \( \inf A = -1 \) not attained (c) \( \sup A = \frac{1}{2} \), \( \inf A = -1 \) (d) \( \sup A = 1 \), \( \inf A = 0 \)
Answer: (a)
Even \( n \): \( 1 - \frac{1}{n} = \frac{1}{2}, \frac{3}{4}, \frac{5}{6}, \dots \), increasing to 1, never equal. Odd \( n \): \( -(1 - \frac{1}{n}) = 0, -\frac{2}{3}, -\frac{4}{5}, \dots \), decreasing to \( -1 \), never equal. So sup 1 and inf \( -1 \), neither attained. Option (c) mistakes the first even term for the sup.
Practice Q3. Let \( A, B \) be non-empty bounded subsets of \( \mathbb{R} \) and \( A - B = \{a - b : a \in A, b \in B\} \). Then \( \sup(A - B) \) equals:
(a) \( \sup A - \sup B \) (b) \( \sup A - \inf B \) (c) \( \inf A - \sup B \) (d) \( \sup A + \inf B \)
Answer: (b)
\( A - B = A + (-B) \), so \( \sup(A - B) = \sup A + \sup(-B) = \sup A - \inf B \). Check with \( A = B = [0,1] \): \( A - B = [-1, 1] \), sup 1 = \( 1 - 0 \). Option (a) would give 0.
Practice Q4. Let \( S \) be the set of real numbers in \( (0,1) \) whose decimal expansion contains only the digits 3 and 8. Then \( S \) is:
(a) finite (b) countably infinite (c) uncountable (d) dense in \( (0,1) \)
Answer: (c)
Choosing 3 or 8 independently at each place gives a bijection with \( \{0,1\}^{\mathbb{N}} \) (such expansions are unique). So \( S \) is uncountable. It is not dense: no element lies in \( (0.4, 0.8) \), since the first digit must be 3 or 8.
Level 3: Part C Style
Practice Q5. Which of the following sets are countable?
(a) the set of functions \( f : \mathbb{N} \to \{0, 1\} \) with \( f(n) = 0 \) for all but finitely many \( n \) (b) the set of all functions \( f : \{0, 1\} \to \mathbb{N} \) (c) the set of all strictly increasing sequences of natural numbers (d) the set of real roots of all polynomials with integer coefficients
Answer: (a), (b) and (d)
- (a) Countable. Each such \( f \) is the indicator of a finite subset of \( \mathbb{N} \); finite subsets form a countable set.
- (b) Countable. \( f \) is the pair \( (f(0), f(1)) \in \mathbb{N} \times \mathbb{N} \).
- (c) Uncountable. A strictly increasing sequence is determined by its range, an infinite subset of \( \mathbb{N} \), and every infinite subset arises. Infinite subsets of \( \mathbb{N} \) are \( \mathcal{P}(\mathbb{N}) \) minus the countable family of finite subsets, so uncountable.
- (d) Countable. Countably many polynomials, each with finitely many roots.
Practice Q6. Let \( A \subseteq \mathbb{R} \) be non-empty and bounded above, and \( s = \sup A \). Which statements are necessarily true?
(a) For every \( \varepsilon > 0 \) there is \( a \in A \) with \( a > s - \varepsilon \). (b) \( s \) belongs to the closure of \( A \). (c) If \( A \) is open, then \( s \notin A \). (d) If \( A \) is infinite, then \( s \) is a limit point of \( A \).
Answer: (a), (b) and (c)
- (a) True. This is the definition: \( s - \varepsilon \) is not an upper bound.
- (b) True. From (a), pick \( a_n \in A \) with \( s - \frac{1}{n} < a_n \le s \); then \( a_n \to s \).
- (c) True. If \( s \in A \) and \( A \) is open, some \( (s - \delta, s + \delta) \subseteq A \), so \( s + \frac{\delta}{2} \in A \), contradicting that \( s \) is an upper bound.
- (d) False. \( A = \{-\frac{1}{n} : n \in \mathbb{N}\} \cup \{1\} \) is infinite with \( \sup A = 1 \), an isolated point of \( A \). The limit point is 0, not the sup.
Practice Q7. Which of the following statements are true?
(a) Between any two distinct real numbers there are infinitely many irrational numbers. (b) \( \mathbb{Q} \), with its usual order, has the least upper bound property. (c) The set of transcendental numbers is uncountable. (d) Every non-empty subset of \( \mathbb{R} \) that is bounded below has a smallest element.
Answer: (a) and (c)
- (a) True. By density there is an irrational in every interval; apply it repeatedly to sub-intervals.
- (b) False. \( \{x \in \mathbb{Q} : x^2 < 2\} \) has no least upper bound in \( \mathbb{Q} \).
- (c) True. \( \mathbb{R} \) is uncountable and the algebraic numbers are countable, so their complement is uncountable.
- (d) False. \( (0, 1) \) is bounded below with infimum 0, but has no smallest element. Bounded-below sets have an infimum, not necessarily a minimum.
Quick Revision Table
| Idea | Fact |
|---|---|
| Countable | finite or in bijection with \( \mathbb{N} \) |
| Countable sets | \( \mathbb{Z}, \mathbb{Q}, \mathbb{Q}^n \), algebraic numbers, finite subsets of \( \mathbb{N} \), \( \mathbb{Q} \)-polynomials |
| Uncountable sets | \( \mathbb{R} \), intervals, irrationals, transcendentals, \( \mathcal{P}(\mathbb{N}) \), \( \{0,1\}^{\mathbb{N}} \), Cantor set |
| Cantor’s theorem | \( \lvert A \rvert < \lvert \mathcal{P}(A) \rvert \) |
| Schröder–Bernstein | two injections give a bijection |
| Completeness | non-empty, bounded above \( \Rightarrow \) sup exists |
| Archimedean | \( \mathbb{N} \) unbounded; \( \frac{1}{n} \to 0 \) |
| sup criterion | upper bound and \( \forall \varepsilon\ \exists a > s - \varepsilon \) |
| \( \sup(A - B) \) | \( \sup A - \inf B \) |
| \( \sup(cA) \), \( c < 0 \) | \( c \inf A \) |
Key Takeaways
What’s Next
- Sequences, Series, limsup and liminf: completeness turned into convergence theorems.
- Metric Spaces and Several Variables: sup, completeness and Bolzano–Weierstrass in general spaces.
- Real Analysis: Quick Revision.
- Counting and probability at Part A level: Numerical Ability.