Results 1 to 2 of 2

Math Help - 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
    21
    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 ,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 kth 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.
    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: June 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: October 8th 2010, 01:59 PM
  3. Real Analysis: Union of Countable Infinite Sets Proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: September 14th 2010, 05:38 PM
  4. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  5. Proof of countable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: April 16th 2009, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum