Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-3/16g/b/solution

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 injection
For every infinite initial ordinal , transfinite recursion constructs a pairing of with : at each stage fewer than earlier pairs have been used. Thus
without 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 surjection
Using the pairing above to code relations as subsets of yields
Again, strictness beyond this is independent of the usual axioms.

New to topics? Read the docs here!