• Feb 3rd 2010, 06:12 PM
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
• Feb 3rd 2010, 06:42 PM
Drexel28
Quote:

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}:p,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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://mathhelpforum.com/differential-geometry/127061-proof-about-countable-sets-print.html", "fetch_time": 1529669097000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2018-26/segments/1529267864391.61/warc/CC-MAIN-20180622104200-20180622124200-00611.warc.gz", "warc_record_offset": 201940280, "warc_record_length": 3769, "token_count": 1473, "char_count": 4511, "score": 3.703125, "int_score": 4, "crawl": "CC-MAIN-2018-26", "snapshot_type": "latest", "language": "en", "language_score": 0.8215781450271606, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00008-of-00064.parquet"}