Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-3/16g/b/solution
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 3 16G b Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
The map injects into . Cantor's diagonal argument shows that no map is surjective: for , the set differs from every . Hence .
If is surjective, inverse image gives an injectionFor every infinite initial ordinal , transfinite recursion constructs a pairing of with : at each stage fewer than earlier pairs have been used. Thuswithout invoking choice for arbitrary families.
Every ordinal below has cardinal at most and can be coded by a well-ordering relation on a subset of . Sending such a relation to its order type, and all non-well-orders to zero, gives a surjectionUsing the pairing above to code relations as subsets of yieldsAgain, strictness beyond this is independent of the usual axioms.
New to topics? Read the docs here!