Past exam of the mathematics course of the University of Cambridge 2011 ia Paper 4 8E Solution Created 2026-09-24 Updated 2026-10-14
For any function , form the diagonal subsetIf were surjective, some would satisfy . Then would hold exactly when , which is impossible. Thus no set surjects onto its power set, including the empty-set case. This is Cantor's theorem proved by the Cantor diagonal argument.
Use real-number pairing by separated digits for an explicit injection . First map a real number to by , and use its unique binary expansion that is not eventually all ones. If and , defineThis places the two binary digit strings in alternating ternary positions. Such ternary strings, using only digits zero and one, are unique: at a first differing position , the difference exceeds the maximum tail . Thus the output recovers both digit strings and both inputs. The use of base three avoids any endpoint ambiguity caused by interleaving digits in base two.
For a fixed , the affine sections of a planar set are indexed byThere is an injection , for example by applying to each coordinate pair and then once more to those two results. Suppose every subset of were a section of . Define a function from to by assigning to the corresponding section, and assigning the empty set to every real outside . Injectivity of makes this definition unambiguous. It would be a surjection onto , contradicting the first argument. No planar set has every subset of the real line as a section. Allowing different parametrizations of the same line does not evade this obstruction.
For all countable sets, however, such a planar set does exist. To build one, first encode every real sequence by one real number. Let be the canonical binary digits of , and choose the explicit indexingThis is a bijection from positive integer pairs to positive integers. Define the coding of real sequences by ternary digitsThe same first-differing-digit argument proves that is injective; all its values lie in . Now takeFor every nonempty countable set , choose an enumeration of , repeating terms if is finite. On the vertical line with and , the section of is precisely : injective sequence coding means no other sequence can contribute extra values in this column. The empty set is the section on the line , since all code columns have first coordinate at most . This constructs the required universal planar set for countable real sections. No assertion about its other, nonvertical sections is needed.
Use coding of real sequences by ternary digits to give each real sequence a distinct column coordinate . Put every term of that sequence in its column. The vertical affine section of a planar set at is exactly the sequence range. Every nonempty countable set has such an enumeration, with repetitions allowed, while any column outside the code interval gives the empty set. This realizes every countable real subset; the other sections are unrestricted.