1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving a set is countable.

  1. Apr 11, 2014 #1
    1. The problem statement, all variables and given/known data
    Let [itex]A=\{f:\mathbb{Z}\to\mathbb{Z}: f(n)\neq 0 \text{for a finite number of n}\}[/itex], prove that [itex]A[/itex] is countable.


    2. Relevant equations
    I'm considering using that it would be equivalent to prove that the set [itex]A'=\{f:\mathbb{N}\to\mathbb{N}: f(n)\neq 0 \text{for a finite number of n}\}[/itex] is countable.


    3. The attempt at a solution

    I'm dividing this solution in two steps, first proving what I stated en (2), this is, that [itex]A[/itex] and [itex]A'[/itex] have the same cardinal. I'm still trying to prove this.
    (...)

    Then prove [itex]A'[/itex] is countable, I define [itex]A'_k = \{f:\mathbb{N}\to\mathbb{N}: f(n)\neq 0 \text{ for k numbers}[/itex], I want to prove that every [itex]A'_k[/itex] is countable. I define now the function [itex]g_k:A'_k\to \underbrace{\mathbb{N}\times\dots\times\mathbb{N}}_{\text{2k}}[/itex] by [itex]g_k(f)=(n_1,\dots,n_k,f(n_1),\dots,f(n_k))[/itex] where [itex]n_1,n_2,\dots[/itex] are the points where [itex]f[/itex] is not zero.
    This function defines (or at least it seems to me) an injection to the set [itex]A'_k[/itex] to a countable set.
    A problem is that only a finite product of countable sets is countable, can I still conclude [itex]A'[/itex] after take the union of the [itex]A'_k[/itex]?.
     
  2. jcsd
  3. Apr 11, 2014 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes. You have shown each ##A^\prime_k## to be countable. The countable union of countable sets is countable, thus
    [tex]\bigcup_k A^\prime_k[/tex]
    is countable.

    Your remark about the product of countable sets makes me think you make the following error: let ##B_n = \mathbb{N}^n## for ##n\in \mathbb{N}##. This is countable. But
    [tex]\mathbb{N}^\mathbb{N} = \bigcup B_n[/tex]
    is uncountable. The flaw here is that the above equality does not hold. That is, we only have
    [tex]\bigcup B_n \subset \mathbb{N}^\mathbb{N}[/tex]
    And this inclusion is strict. Prove this. (Also, I identify here an element ##(k_1,...,k_n)\in B_n## with ##(k_1,...,k_n,0,0,...)\in \mathbb{N}^{\mathbb{N}}##).
     
    Last edited: Apr 11, 2014
  4. Apr 11, 2014 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    A couple of minor points:
    The countable union of countable sets is countable
    "And this subset is strict."
     
  5. Apr 11, 2014 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Thank you very much. I'll correct them!
     
  6. Apr 11, 2014 #5
    Thanks a lot.
    Just for clarification, my worry comes mainly because of the product. I'm trying to deal with an intuitive way to think about the infinity in this case, I thought the problem was how I defined the function [itex]g_k[/itex], because I defined an injection to the set of [itex]\underbrace{\mathbb{N}\times\dots\times\mathbb{N}}_{\text{2k}}[/itex] and [itex]k[/itex] increases to infinity ([itex]A'=\bigcup_{k=1}^{\infty}[/itex]) then I wouldn't be able to do the general step and say the union is countable.

    Regarding to the part above when I said I still was trying to find a way to prove [itex]A[/itex] countable [itex]\iff A'[/itex] countable. The functions I defined in this thread would work as well to prove this part?.
     
    Last edited: Apr 11, 2014
  7. Apr 11, 2014 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    What do you mean? You can show it for any integer ##k## and then just take the union. This works.

    Do you mean you can't do this for ##k=+\infty##? That's true.

    Yes.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted