1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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
    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


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    A couple of minor points:
    The countable union of countable sets is countable
    "And this subset is strict."
  5. Apr 11, 2014 #4
    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
    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.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted