Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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?

share|improve this answer
  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.

share|improve this answer
  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.