# Proving a set is countable.

1. Apr 11, 2014

### trash

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

2. Relevant equations
I'm considering using that it would be equivalent to prove that the set $A'=\{f:\mathbb{N}\to\mathbb{N}: f(n)\neq 0 \text{for a finite number of n}\}$ 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 $A$ and $A'$ have the same cardinal. I'm still trying to prove this.
(...)

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

2. Apr 11, 2014

### micromass

Staff Emeritus
Yes. You have shown each $A^\prime_k$ to be countable. The countable union of countable sets is countable, thus
$$\bigcup_k A^\prime_k$$
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
$$\mathbb{N}^\mathbb{N} = \bigcup B_n$$
is uncountable. The flaw here is that the above equality does not hold. That is, we only have
$$\bigcup B_n \subset \mathbb{N}^\mathbb{N}$$
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
3. Apr 11, 2014

### haruspex

A couple of minor points:
The countable union of countable sets is countable
"And this subset is strict."

4. Apr 11, 2014

### micromass

Staff Emeritus
Thank you very much. I'll correct them!

5. Apr 11, 2014

### trash

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 $g_k$, because I defined an injection to the set of $\underbrace{\mathbb{N}\times\dots\times\mathbb{N}}_{\text{2k}}$ and $k$ increases to infinity ($A'=\bigcup_{k=1}^{\infty}$) 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 $A$ countable $\iff A'$ countable. The functions I defined in this thread would work as well to prove this part?.

Last edited: Apr 11, 2014
6. Apr 11, 2014

### micromass

Staff Emeritus
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.