# Proving a set is countable.

## Homework Statement

Let $A=\{f:\mathbb{Z}\to\mathbb{Z}: f(n)\neq 0 \text{for a finite number of n}\}$, prove that $A$ is countable.

## Homework 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.

## 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$?.

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$?.

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:
haruspex
Homework Helper
Gold Member
2020 Award
A couple of minor points:
The union of countable sets is countable
The countable union of countable sets is countable
And this union is strict.
"And this subset is strict."

A couple of minor points:

The countable union of countable sets is countable

"And this subset is strict."

Thank you very much. I'll correct them!

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}}##).
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:
Thanks a lot.
I wouldn't be able to do the general step and say the union is countable.

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.

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?.

Yes.