1. ## countable

Show that the subset $\displaystyle A$ of terminating sequences is countable (e.g. $\displaystyle a_n = 0$ for $\displaystyle n >N$).

So suppose $\displaystyle E$ is a countable subset of $\displaystyle A$. Then $\displaystyle E = \{s_1, s_2, \cdots, s_n \}$ where $\displaystyle s_k$ ($\displaystyle k=1 \ldots n$) are terminating sequences. Is it possible to just say that is is impossible to construct a sequence $\displaystyle s$ such that $\displaystyle s \notin E$. Thus not every subset $\displaystyle E$ of $\displaystyle A$ is proper. Hence $\displaystyle A$ is countable.

Or is the only way to do it is to say that $\displaystyle A$ is equivalent to $\displaystyle \mathbb{Q}^{\mathbb{N}}$?

2. Originally Posted by manjohn12
Show that the subset $\displaystyle A$ of terminating sequences is countable (e.g. $\displaystyle a_n = 0$ for $\displaystyle n >N$).

So suppose $\displaystyle E$ is a countable subset of $\displaystyle A$. Then $\displaystyle E = \{s_1, s_2, \cdots, s_n \}$ where $\displaystyle s_k$ ($\displaystyle k=1 \ldots n$) are terminating sequences. Is it possible to just say that is is impossible to construct a sequence $\displaystyle s$ such that $\displaystyle s \notin E$. Thus not every subset $\displaystyle E$ of $\displaystyle A$ is proper. Hence $\displaystyle A$ is countable.

Or is the only way to do it is to say that $\displaystyle A$ is equivalent to $\displaystyle \mathbb{Q}^{\mathbb{N}}$?
How would you show that it is "impossible to construct a sequence $\displaystyle s$ such that $\displaystyle s \notin E$? Wouldn't that depend on exactly what E was?

I would do this: let [tex]E_N[tex] be the set of all sequences such that $\displaystyle s_N\ne 0$ but that $\displaystyle s_n= 0$ for all n> N. It should be easy to show that [tex]E_N[tex] is countable. And E is the union of all [tex]E_N[tex] for all positive integers, N. That is, E is the countable union of countable sets.

3. Originally Posted by HallsofIvy
How would you show that it is "impossible to construct a sequence $\displaystyle s$ such that $\displaystyle s \notin E$? Wouldn't that depend on exactly what E was?

I would do this: let EN be the set of all sequences such that $\displaystyle s_N\ne 0$ but that $\displaystyle s_n= 0$ for all n> N. It should be easy to show that EN is countable. And E is the union of all EN for all positive integers, N. That is, E is the countable union of countable sets.
Well that is the traditional way of doing it. But to show a set is uncountable, for any countable set $\displaystyle E$ of $\displaystyle A$ you can construct a sequence $\displaystyle s$ such that $\displaystyle s \notin E$ right? So the choice of $\displaystyle E$ doesn't really matter. But is it possible to explicitly show that no such $\displaystyle s$ exists in this case?