: Let ,q\in\mathbb{Q}\right\}" alt="E=\left\{(p,q)\subseteq\mathbb{R},q\in\mathbb{Q}\right\}" />. Prove that is countable.Problem

Define by . This is clearly an injection, for if then we have that which by the definition of ordered pairs is only true if and only if .Proof:

Now, to prove that (more generally ) we need a couple facts.

Lemma:is countable.

Proof:It is clear that given by is an injection. Also, if we define by where is the th prime we see this is an injection

since if then we have a number represented as two prime factorizations. It follows by the fundamental theorem of arithmetic that the two factorizations must

be equal, in particular their exponents, and thus the -tuples must be equal. It follows by the Schroder-Bernstein theorem that is countable

Lemma:is countable.

Proof: We know that is countable (for example consider the surjection given by ) and so we know there exists some function which is a bijection.

Therefore, define by . To see that this is injective we note that if

that each of must hold true and since is an injection it follows that

from where injectivity follows.

To see that it's surjective we must merely note that given any there exists, by 's surjectivity, some such that from where it follows that

.

It follows that is a bijection, and since is countable it follows that is as welll

With our lemma in mind we see that is countable and since is an injection and infinite (obvious) it follows that is countably infinite.