is either finite or infinite. If is finite then by definition there is a bijection . And there is an injection . Then is an injection and so is at most countable. Thus, it is safe to assume is infinite. Define the sequence and . There are two reasons why such a sequence exists. One, we assumed that is infinite and therefore its elements never get exhausted at any finite stage. Two, the existence of such a function is gaurentted by the Recursion Theorem. Now argue that (argue by contradiction). Also the function is one-to-one by construction. Thus, . And this completes the proof.