Skip to content

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 read
  • Updated
On this page · 15 sections
  1. Prerequisites
  2. The Hook: A Hole in the Rationals
  3. Sets, Functions and Cardinality
  4. Countable Sets
  5. Uncountable Sets
  6. The Real Numbers as a Complete Ordered Field
  7. Supremum and Infimum
  8. Counter-examples Table
  9. Memory Tricks
  10. Don’t Confuse
  11. Common Mistakes
  12. Practice
  13. Quick Revision Table
  14. Key Takeaways
  15. What’s Next

Prerequisites

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

  1. Every subset of a countable set is countable.
  2. The image of a countable set under any function is countable.
  3. \( \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.
  4. A finite product of countable sets is countable.
  5. 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:

SetWhy 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) coefficientsunion over degree \( n \) of copies of \( \mathbb{Z}^{n+1} \)
Algebraic numberseach 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 alphabetunion over length
Sequences in \( \mathbb{N} \) that are eventually zerodetermined 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 functioneach 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

SetCardinalityReason
\( \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.

  1. Field axioms. \( (\mathbb{R}, +, \cdot) \) is a field.
  2. Order axioms. \( < \) is a total order compatible with the operations: \( x < y \Rightarrow x + z < y + z \), and \( x, y > 0 \Rightarrow xy > 0 \).
  3. 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:

FormStatement
Least upper bound propertynon-empty, bounded above \( \Rightarrow \) sup exists
Monotone convergencebounded 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–Weierstrassevery bounded sequence has a convergent subsequence
Cauchy completenessevery 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

  1. \( a \le s \) for all \( a \in A \) (upper bound), and
  2. 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} \):

SetSupremum
\( 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 claimCounter-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 intervalCantor 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

ThisvsThat
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

  1. Is the set of all finite subsets of \( \mathbb{N} \) countable?
  2. Find sup and inf of \( \{1 - \frac{1}{n} : n \in \mathbb{N}\} \). Which is attained?
  3. State the Archimedean property.
Answers
  1. Yes. It is \( \bigcup_n \mathcal{P}(\{1, \dots, n\}) \), a countable union of finite sets.
  2. sup = 1 (not attained), inf = 0 (attained at \( n = 1 \)).
  3. 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

IdeaFact
Countablefinite 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–Bernsteintwo injections give a bijection
Completenessnon-empty, bounded above \( \Rightarrow \) sup exists
Archimedean\( \mathbb{N} \) unbounded; \( \frac{1}{n} \to 0 \)
sup criterionupper 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