Countable and uncountable sets

Problem Statement

• Explain why positive rationals are countable by diagonal listing.
• Use Cantor's diagonal argument to show reals in $[0,1)$ are uncountable.

Hints

Construct a new decimal differing from the $n$th listed decimal at position $n$.

Solutions

Rationals can be arranged in an infinite grid $\frac{p}{q}$ and traversed by diagonals, skipping duplicates after simplification; this yields a sequence listing all positive rationals. For reals in $[0,1)$, assume a list $T_1,T_2,\dots$ exists. Build $x$ so its $n$th digit differs from the $n$th digit of $T_n$. Then $x\neq T_n$ for every $n$, contradicting completeness of the list. Hence uncountable.

Further Readings

• HSC Collections: https://vumaths.com/booklets/hsc-collections/
• HSC Vectors: https://vumaths.com/booklets/hsc-vectors/
• HSC Combinatorics: https://vumaths.com/booklets/hsc-combinatorics/
• HSC Proofs: https://vumaths.com/booklets/hsc-proofs/

Connect with me

• Website - Vu's Maths Hub: https://vumaths.com/
• Instagram: https://www.instagram.com/vuhung16/
• YouTube - HSC Maths Extension 1+2: https://www.youtube.com/playlist?list=PLHSE0sAlTr2w