Solution

ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2009/b/5/i/solution

The Cantor-Schröder-Bernstein theorem states that injections and imply the existence of a bijection . Here is a direct proof, avoiding any appeal to a fixed-point theorem. Let , , and . Define
The second case is defined because . On , is a bijection onto . For , injectivity of and the construction of give if and only if : cannot be in , so membership in means membership in some . Hence bijects onto . The two pieces have disjoint domains and images and together cover , proving bijective. This proof itself uses no choice.
Write . We use the standard infinite-cardinal identities , for positive finite and infinite , and , under the permitted axiom of choice. The map bijects with . Therefore

New to topics? Read the docs here!