Proof about countable sets

**inthequestofproofs** · February 3rd 2010, 06:12 PM

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

**Drexel28** · February 3rd 2010, 06:42 PM

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 $E=\left\{(p,q)\subseteq\mathbb{R}<img src=$ ,q\in\mathbb{Q}\right\}" alt="E=\left\{(p,q)\subseteq\mathbb{R}

,q\in\mathbb{Q}\right\}" />. Prove that $E$ is countable.

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

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

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

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

since if $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 $m$ -tuples must be equal. It follows by the Schroder-Bernstein theorem that $\mathbb{N}^m$ is countable $\blacksquare$

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

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

Therefore, define $\mathcal{J}:\mathbb{N}^m\mapsto\mathbb{Q}^m$ by $\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

$\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 $f(n_k)=f\left(n'_k\right),\text{ }1\leqslant k\leqslant m$ must hold true and since $f$ is an injection it follows that

$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 $\left(q_1,\cdots,q_m\right)\in\mathbb{Q}$ there exists, by $f$ 's surjectivity, some $n_1,\cdots,n_m$ such that $f(n_1)=q_1,\cdots,f(n_m)=q_m$ from where it follows that

$\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 $\mathcal{J}:\mathbb{N}^m\mapsto\mathbb{Q}^m$ is a bijection, and since $\mathbb{N}^m$ is countable it follows that $\mathbb{Q}^m$ is as welll $\blacksquare$

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

Thread: Proof about countable sets

LinkBack

Thread Tools

Display

Proof about countable sets

Similar Math Help Forum Discussions

[SOLVED] Need some guidance for a proof of countable sets

[SOLVED] Countable union of closed sets/countable interesection of open sets

Real Analysis: Union of Countable Infinite Sets Proof

Proof that the intersection of infinitely many countable sets is countable.

Proof of countable sets

Search Tags