Which sets of sequence is countable and Uncountable.

Question

Consider the sequences

$$\displaystyle X=\left\{(x_n): x_n \in \left\{0,1\right\},n \in \mathbb{N} \right\}$$ $$and$$ $$\displaystyle Y=\left\{(x_n)\in X:x_n=1 \;\;\text{for at most finitely many n} \right\}$$

I have to choose which is uncountable and which is countable.

Solution i tried- Here $X$ is set of sequence with enteries from $\left\{0,1\right\}$ thus it has number of elements $2^{\aleph_0}$ which is uncountable .

Now The set $Y$ it has all the sequences from the set $X$ but some of its elements of sequences is replaced by the only '$1$' so its Cardinality will be less then $2^{\aleph_0}$ ,but by $\textbf{ continuum hypothesis}$ there is no set having Cardinality in-between the ${\aleph_0}$ and $2^{\aleph_0}$ so the set $Y$ will be countable

I write this proof but i don't even know this is correct or not but i am sure about set $X$ but not sure about $Y$ please help me with set $Y$

Thank you.

Answer 1

We know that the countable union of countable sets is countable.

Which means the countable union of countable unions of countable sets is a countable set.

And $Y$ is the countable union (indexed over how many $1$s the sequences have) of countable unions (indexed over how which positions the finite number of $1$s occupy) of countable sets.

Bear with me:

$V_0=\{(0)=\{0,0,0,0,.....\}\}$ is a set with one element.

$V_1 =\{(x_n)$ where one $x_i=1$ and all the rest are $0\}$ is countable as there is a one to one correspondence between the $(x_n)$ and the possible positions for $x_i = 1$.

$W_{k,1} = \{(x_n): x_{j< k}=0; x_k = 1$ and there is one $x_{i>k}=1$ but all the rest are $0\}$. $\iota: W_{k,1}\leftrightarrow V_1$ via for every $(x_n)\in W_{k,1}$, $\iota((x_n)) = (w_n= x_{n-k})$. That is if $(x_n)$ is the sequence where $x_k=1$ and $x_{i>k} =1$ and all else are $0$, the $\iota((x_n))$ is the sequence where $x_{i-k}=1$ and all else are $0$. This is clearly a bijection.

$V_2=\{(x_n)$ where two $x_i=x_j=1$ and all the rest are $0\}$. $V_2=\cup_{i=1}^{\infty} W_1$ so $V_2$ is countable as it is a countable union of countable sets.

Let $V_m=\{(x_n)$ where there are exactly $m$ $1$s and all the rest are $0\}$.

Let $W_{k,m} = \{(x_n)$ where $x_{j< k}=0;$ and there are $m$ $x_{i>k}=1$ and all the rest are $0\}$.

We can define the bijection $\iota: W_{k,m}\leftrightarrow V_m$ via $(x_n) = (x_{n-k})$.

And $V_{m+1} = \cup_{i=1}^{\infty} W_{i,m}$.

By induction if $V_m$ is countable then so is each $W_{k,m}$ and so $V_{m+1}$ as a union of countable sets.

Now your $Y=\displaystyle Y=\left\{(x_n)\in X:x_n=1 \;\;\text{for at most finitely many n} \right\} = \cup_{i=o}^{\infty} V_i$.

So $Y$ is a countable union of countable sets and thus countable.

Answer 2

$X$ is indeed uncountable and your proof is correct. Your proof for countability of $Y$ is incorrect:

Now the set $Y$ has all the sequences from the set $X$, but some of its elements of sequences are replaced by the only '$1$' so its cardinality will be less then $2^{\aleph_0}$

Even if you assume the continuums hypothesis (which is a strong assumption to make!), you don't know how many elements you really replaced or removed. How do you know that the cardinality became smaller? Did you construct an explicit injection for that failing to be surjective?

Still, $Y$ is countable. I'll explain how. Basically, the only information a sequence $y \in Y$ has is the finite, possibly disconnected, strip of ones it contains -- if any. You can see the zeroes as the default value with no information. Hence, we might posit the following wrong bijection:

$$Y \cong \{0,1\}^* \tag{wrong!}$$

E.g. we would do the following association:

• 1110000.... $\mapsto$ 111
• 1110100.... $\mapsto$ 11101

Certainly, this is injective. But is this surjective? No! We have to consider $\{0,1\}^*$ in such a way that padded zeroes at the right are disregarded. In other words, we have

$$Y \cong \{0,1\}^*/\sim$$

where $\sim$ is some equivalence. If you trust me that such a $\sim$ exists, then we actually don't need to work this out for the countability argument. Namely, since $\{0,1\}^*$ was already countable, so is every quotiened version of it.

Answer 3

Let $A_n=\{1,\cdots,n\}$. For each $f \in \{0,1\}^{A_n}$, define $g_f:\Bbb N \to \{0,1\}$ by $$g_f(x)=\begin{cases}f(x)&\text{if}\;x \in \{1,2,..,n\}\\0&\text{otherwise} \end{cases}$$ Then each $g_f \in Y$. Then $Y$ can be written as $$Y=\cup_{n=1}^\infty Y_n$$ where $Y_n=\left\{g_f: f \in \{0,1\}^{A_n}\right\}$ . Here each $Y_n$ is finite and hence $Y$ is countable!