which of the following sets are countable

Question

are the following sets countable?

1. set of all sequences of non-negative integers.

2. The set of all sequences of non-negative integers with only a finite number of non zero terms

could any one tell me how to solve this?

Answer 1

HINTS:

For (1): Consider just the sequences of zeroes and ones. Each such sequence corresponds to a set of natural numbers: if $\langle b_0,b_1,\dots\rangle$ is such a sequence, it corresponds to the set $\{k\in\Bbb N:b_k=1\}$. Thus, there are at least as many sequences of natural numbers as there are subsets of $\Bbb N$. Is this a countable collection?

For (2): How many sequences have $0$ non-zero terms? How many have $1$ non-zero term? How many have $2$ non-zero terms? In general, how many have $n$ non-zero terms for a fixed $n>0$? And how big is a countable union of countable sets?

Answer 2

1. No.
2. Yes.

How to solve this. Depends on your level.

1. Let $S = \mathbb{N}^{\mathbb{N}}$ the set of all sequences, clearly $\{0,1\}^{\mathbb{N}}$ can be seen as subset. But any function on $\mathbb{N}$ that takes only values $0$ and $1$ is uniquely described by it's preimage under $0$, so corresponds to an element of $\mathcal{P}(\mathbb{N})$, an uncountable set. You can think of choosing an element of $\mathbb{N}$ to be in a subset if its value under the sequence is $1$ and not be in it if its value is $0$.

2. This set is a countable union of a finite product of countable sets and therefore countable. You can imagine it to be $S_0 = \mathbb{N}^{(\mathbb{N})} = \bigcup_{k \in \mathbb{N}} \mathbb{N}^k$, where $k$ is the "word"-length of such a sequence, before it becomes constantly zero, and $\mathbb{N}^k$ to capture the first $k$ entries in this sequence.

Answer 3

1. $\mathbb{N}^{\mathbb{N}} \geq 2^{\mathbb{N}}=\mathcal{P}(\mathbb{N})$, so $\mathbb{N}^{\mathbb{N}}$ is uncountable.

2. If $E$ is the set of non-negative integers with only a finite number of non zero terms, there is a surjection from $\cup_{n \in \mathbb{N}} \mathbb{N}^n$ onto $E$. So $E \leq\cup_{n \in \mathbb{N}} \mathbb{N}^n$. This is a countable union of countable sets, so it is countable.