1. ## countable

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

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

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

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

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

Or is the only way to do it is to say that $A$ is equivalent to $\mathbb{Q}^{\mathbb{N}}$?
How would you show that it is "impossible to construct a sequence $s$ such that $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 $s_N\ne 0$ but that $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 $s$ such that $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 $s_N\ne 0$ but that $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 $E$ of $A$ you can construct a sequence $s$ such that $s \notin E$ right? So the choice of $E$ doesn't really matter. But is it possible to explicitly show that no such $s$ exists in this case?