1. ## Proof about countable sets

I want to prove the following:
the set of all intervals with rational end points is countable

I know rational numbers are countable, so there is a a function f: N x N -> Q x Q.
With this, i could say that since the naturals are also countable N -> N x N, then there is a function g: N -> Q x Q

Is this right? I am sure this is a not a complete proof, so if somebody could provide some help.

Thanks

2. Originally Posted by inthequestofproofs
I want to prove the following:
the set of all intervals with rational end points is countable

I know rational numbers are countable, so there is a a function f: N x N -> Q x Q.
With this, i could say that since the naturals are also countable N -> N x N, then there is a function g: N -> Q x Q

Is this right? I am sure this is a not a complete proof, so if somebody could provide some help.

Thanks
Problem: Let $\displaystyle E=\left\{(p,q)\subseteq\mathbb{R},q\in\mathbb{Q}\right\}$. Prove that $\displaystyle E$ is countable.

Proof: Define $\displaystyle \mathcal{D}:E\mapsto\mathbb{Q}\times\mathbb{Q}$ by $\displaystyle (p,q)\mapsto (p,q)$. This is clearly an injection, for if $\displaystyle \mathcal{D}\left(p,q\right)=\mathcal{D}\left(p',q' \right)$ then we have that $\displaystyle (p,q)=\left(p',q'\right)$ which by the definition of ordered pairs is only true if and only if $\displaystyle p=p',q=q'$.

Now, to prove that $\displaystyle \mathbb{Q}^2$ (more generally $\displaystyle \mathbb{Q}^n,\text{ }n\in\mathbb{N}$) we need a couple facts.

Lemma: $\displaystyle \mathbb{N}^m,\text{ }m\in\mathbb{N}$ is countable.

Proof: It is clear that $\displaystyle f:\mathbb{N}\mapsto\mathbb{N}^m$ given by $\displaystyle n\mapsto(n,\underbrace{1,\cdots,1}_{m-1\text{ times}})$ is an injection. Also, if we define $\displaystyle g:\mathbb{N}^m\mapsto\mathbb{N}$ by $\displaystyle \left(n_1,\cdots,n_m\right)\mapsto p_1^{n_1}\cdots p_m^{n_1}$ where $\displaystyle p_k$ is the $\displaystyle k$th prime we see this is an injection

since if $\displaystyle g\left(\left(n_1,\cdots,n_m\right)\right)=g\left(\ left(n'_1,\cdots,n'_m\right)\right)$ 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 $\displaystyle m$-tuples must be equal. It follows by the Schroder-Bernstein theorem that $\displaystyle \mathbb{N}^m$ is countable $\displaystyle \blacksquare$

Lemma: $\displaystyle \mathbb{Q}^m$ is countable.

Proof: We know that $\displaystyle \mathbb{Q}$ is countable (for example consider the surjection $\displaystyle f:\mathbb{N}^2\mapsto\mathbb{Q}$ given by $\displaystyle (m,n)\mapsto\frac{m+1}{n+1}$) and so we know there exists some function $\displaystyle f:\mathbb{N}\mapsto\mathbb{Q}$ which is a bijection.

Therefore, define $\displaystyle \mathcal{J}:\mathbb{N}^m\mapsto\mathbb{Q}^m$ by $\displaystyle \mathcal{J}\left(\left(n_1,\cdots,n_m\right)\right )=\left(f(n_1),\cdots,f(n_m)\right)$. To see that this is injective we note that if

$\displaystyle \mathcal{J}\left(\left(n_1,\cdots,n_m\right)\right )=\left(f(n_1),\cdots,f(n_m)\right)=\left(f\left(n '_1\right),\cdots,f\left(n'_m\right)\right)=\mathc al{J}\left(\left(n'_1,\cdots,n'_m\right)\right)$ that each of $\displaystyle f(n_k)=f\left(n'_k\right),\text{ }1\leqslant k\leqslant m$ must hold true and since $\displaystyle f$ is an injection it follows that

$\displaystyle n_k=n'_k,\text{ }1\leqslant k\leqslant m$ from where injectivity follows.

To see that it's surjective we must merely note that given any $\displaystyle \left(q_1,\cdots,q_m\right)\in\mathbb{Q}$ there exists, by $\displaystyle f$'s surjectivity, some $\displaystyle n_1,\cdots,n_m$ such that $\displaystyle f(n_1)=q_1,\cdots,f(n_m)=q_m$ from where it follows that

$\displaystyle \mathcal{J}\left(\left(n_1,\cdots,n_m\right)\right )=\left(f(n_1),\cdots,f(n_m)\right)=\left(q_1,\cdo ts,q_m\right)$.

It follows that $\displaystyle \mathcal{J}:\mathbb{N}^m\mapsto\mathbb{Q}^m$ is a bijection, and since $\displaystyle \mathbb{N}^m$ is countable it follows that $\displaystyle \mathbb{Q}^m$ is as welll $\displaystyle \blacksquare$

With our lemma in mind we see that $\displaystyle \mathbb{Q}^2$ is countable and since $\displaystyle \mathcal{D}:F\mapsto\mathbb{Q}^2$ is an injection and $\displaystyle F$ infinite (obvious) it follows that $\displaystyle F$ is countably infinite.