Past exam of the mathematics course of the University of Cambridge 2009 ia Paper 4 8E Solution Created 2026-09-24 Updated 2026-10-14
Suppose all infinite binary sequences could be listed as , where . Define another binary sequence by . It differs from the th listed sequence at its th entry, so it is absent from the list. This contradiction is Cantor's diagonal argument, proving thatTo transfer this result to , map a binary sequence toThis lies in because . If two sequences first differ at index , with and , thenThus is an injection, avoiding the ambiguous expansions that would arise from unrestricted binary digits in base two. An injection from an uncountable set into proves that .
For , a nondecreasing sequence bounded above can take only finitely many integer values, all lying between its first term and an integer upper bound. Every strict increase raises its value by at least one, so only finitely many strict increases occur. It is therefore eventually constant. Every such sequence has the formfor some finite list of integers. The set of finite integer lists is a countable set: at stage , list the tuples of length at most whose entries have absolute value at most , omitting earlier duplicates. Each stage is finite and every finite tuple occurs at some stage. Constant sequences give an injection of into the collection, soThis is the discrete-order phenomenon that bounded nondecreasing integer sequences are eventually constant.
For , use a different encoding, into rational partial sums:Each is a rational number, the sequence is nondecreasing, and . If two binary inputs first differ at , their th partial sums differ by , so their output sequences differ. This defines an injection of the uncountable binary-sequence set into . Thus bounded nondecreasing rational sequences are uncountable. Finally, every such rational sequence is also an admissible real sequence, so inclusion into is injective. ConsequentlyBoundedness and monotonicity force eventual constancy for integer values, but not for rational or real values; countability of the set of possible individual terms does not imply countability of all infinite sequences of those terms.