Results 1 to 2 of 2

Thread: Proof about countable sets

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    35

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by inthequestofproofs View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Need some guidance for a proof of countable sets
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: Jun 22nd 2011, 12:30 AM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Oct 8th 2010, 01:59 PM
  3. Real Analysis: Union of Countable Infinite Sets Proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: Sep 14th 2010, 05:38 PM
  4. Replies: 1
    Last Post: Feb 9th 2010, 01:51 PM
  5. Proof of countable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Apr 16th 2009, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum