Proving a set is countable.

  • Thread starter trash
  • Start date
  • #1
14
0

Homework Statement


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.


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


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

Answers and Replies

  • #2
22,129
3,297
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]?.

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:
  • #3
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,422
6,952
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."
 
  • #4
22,129
3,297
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!
 
  • #5
14
0
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}}##).
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:
  • #6
22,129
3,297
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 [itex]A[/itex] countable [itex]\iff A'[/itex] countable. The functions I defined in this thread would work as well to prove this part?.

Yes.
 

Related Threads on Proving a set is countable.

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
2
Views
1K
Top