Results 1 to 3 of 3

Math Help - Countability Proof

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    123

    Countability Proof

    Fix n >= 1. Show that if A1,A2, . . . ,An are countable, then A1A2 . . . An is countable.

    Does this require knowledge of the fact that N x N is countably infinite?

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by h2osprey View Post
    Fix n >= 1. Show that if A1,A2, . . . ,An are countable, then A1A2 . . . An is countable.

    Does this require knowledge of the fact that N x N is countably infinite?

    Thanks in advance.
    You can use the fact that \mathbb{N}^n is countable. Which can be done by induction, and you'll have to use the fact that \mathbb{N} \times \mathbb{N} is countable.

    1.
    You know that there exists an injective mapping \phi_2 ~:~ \mathbb{N}^2 \to \mathbb{N}
    Let n \geqslant 2
    Basis : for n=2, it's verified (I assume it's a know fact for you)
    Inductive hypothesis : assume that there exists an injective mapping \phi_n ~:~ \mathbb{N}^n \to \mathbb{N}
    Now, you have to prove that there exists an injective mapping \phi_{n+1} ~:~ \mathbb{N}^{n+1} \to \mathbb{N}
    For this, define \phi_{n+1} this way :
    \phi_{n+1}(x_1,\dots,x_n,x_{n+1})=(\phi_n(x_1,\dot  s,x_n),x_{n+1})
    It is easy to show that it's injective, knowing that \phi_n is injective.


    2.
    Now prove that there exists an injection \psi from A_1 \times \dots \times A_n to \mathbb{N}^n
    Since A_1,\dots,A_n are countable, there exist injections \psi_i ~:~ A_i \to \mathbb{N}
    Define \psi (x_1,\dots,x_n)=(\psi_1(x_1),\dots,\psi_n(x_n))
    Once again, it's easy to show that it's injective.


    3.
    A_1 \times \dots \times A_n \stackrel{\psi}{\longrightarrow} \mathbb{N}^n \stackrel{\phi_n}{\longrightarrow} \mathbb{N}
    We know that \psi, \phi_n are injective.
    Now you just have to prove that the composite of two injective functions is injective, in particular \phi_n \circ \psi.

    And you're done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by h2osprey View Post
    Fix n >= 1. Show that if A1,A2, . . . ,An are countable, then A1A2 . . . An is countable.

    Does this require knowledge of the fact that N x N is countably infinite?

    Thanks in advance.
    If you know that \mathbb{N}\times \mathbb{N} is countable then it is easy to prove this result.

    If |A| = |B|= |\mathbb{N}| then |A\times B| = |\mathbb{N}\times \mathbb{N}| is countable.

    Thus, |A_1\times ... \times A_n| = |\mathbb{N} \times ... \times \mathbb{N}|.
    We established that \mathbb{N}^2 was countable.
    If \mathbb{N}^k, k\geq 2 is countable then \mathbb{N}^{k+1} = \mathbb{N}^k \times \mathbb{N} is countable.
    The rest follows by induction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Interval Countability proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 12th 2011, 05:29 PM
  2. Countability of Subsets proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 10th 2010, 08:19 AM
  3. Countability proof.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 29th 2010, 10:14 AM
  4. Inductive Proof of Countability of Algebraic Numbers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 5th 2009, 10:04 AM
  5. Proof of countability
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: February 15th 2007, 08:35 PM

Search Tags


/mathhelpforum @mathhelpforum