# Is $X=\left\{(x_n)_{n\in\mathbb{N}}\mid x_n\in\{0,1\},\forall n \wedge x_n=1\text{ for at most finitely many$n$}\right\}$ countable or uncountable?

Consider the set $$X=\left\{(x_n)_{n\in\mathbb{N}}\mid x_n\in\{0,1\},\forall n\in\mathbb{N}\wedge x_n=1\text{ for at most finitely many n}\right\}$$ Then what can we say about the cardinality of $$X$$ (countable or uncountable)?

My try: I've taken an arbitrary $$A=\{s_1,s_2,\ldots,s_n,\ldots\}\subseteq X$$ which is countable.

Arrange the sets \begin{align}Y_0&=\{(s_k)_{k\in\mathbb{N}}\mid s_k\text{ contains no }1's\}\\ Y_1&=\{(s_k)_{k\in\mathbb{N}}\mid s_k\text{ contains exactly one }1's\}\\\vdots \\ Y_m&=\{(s_k)_{k\in\mathbb{N}}\mid s_k\text{ contains exactly m 1's}\}\\\end{align}

This process must stop for some $$m\in\mathbb N$$ because each sequence of $$X$$ contains at most finitely many $$1.$$

Clearly $$A=\bigcup_{i=0}^mY_i$$

So if we consider the set $$S=\{(x_n)_{n\in\mathbb{N}}\mid x_n\in\{0,1\}\;\forall n\in\mathbb N\text{ and x_n=1 for (m+1) values of n} \}$$

Then $$S\not\in A.$$ $$A$$ was an arbitrary countable subset of $$X$$ and we've shown that $$A$$ is a proper subset of $$X$$. Thus any countable subset of $$X$$ is a proper subset of $$X$$.

If $$X$$ is countable then according to the proof, $$X$$ being a countable subset of $$X$$, is a proper subset of $$X$$, a contradiction. Hence $$X$$ must be uncountable.

• The description you gave makes it seem like $X\subset\lbrace 0,1\rbrace$. Since each $x_n\in\lbrace 0,1\rbrace$. Is this what you meant? – Prototank Oct 24 '18 at 14:02
• If $X$ consists of elements that are indexed by the elements of $\mathbb N$, how can we have anything else then $\vert X\vert \leq \vert \mathbb N\vert$? – gebruiker Oct 24 '18 at 14:02
• It looks like a confusion between set and sequence. Although there is no definition of a set, we know it contains non-repeating elements. Sequence can contain repeating elements. E.g. $\{1\}$ is a set, $(x_n)_{n\in\mathbb{N}}, x_n=1, \forall n\in\mathbb{N}$ is a sequence. – rtybase Oct 24 '18 at 14:11
• @ArjunBanerjee then I'd suggest an edit so that $X=\left\{(x_n)_{n\in\mathbb{N}}\mid x_n\in\{0,1\} ...\right\}$ – rtybase Oct 24 '18 at 14:28
• @rtybase Thank you so much for suggesting edits. – Arjun Banerjee Oct 24 '18 at 14:55

## 1 Answer

$$\mathcal{P}_{fin}(\mathbb{N})$$ (i.e. the collection of the finite subsets of $$\mathbb{N}$$) is countable. Clearly $$\mathbb{N},\mathbb{N}^{(2)},\mathbb{N}^{(3)},\ldots$$ are countable, so each element of $$\mathcal{P}_{fin}(\mathbb{N})$$ can be identified with a couple of natural numbers: the first natural number is the number $$k$$ of elements of such subset and the second number is the index of such subset among the elements of $$\mathbb{N}^{(k)}$$. It follows that $$\left|\mathcal{P}_{fin}(\mathbb{N})\right| = \left|\mathbb{N}\times\mathbb{N}\right|=|\mathbb{N}|=\aleph_0.$$

• Could you please explain the flaws in my proof? – Arjun Banerjee Oct 24 '18 at 14:59
• @ArjunBanerjee: simply, your contradiction is not a contradiction. $2\mathbb{N}$ is a proper subset of $\mathbb{N}$ and still both $\mathbb{N}$ and $2\mathbb{N}$ are countable, for instance. – Jack D'Aurizio Oct 24 '18 at 15:03
• I said if all countable subsets of a set are the proper subsets of $X$, then $X$ is uncountable. Please have a look at my post where I've proven it that $X$ can't be countable. – Arjun Banerjee Oct 24 '18 at 15:12
• In your example, $\mathbb N$ is a countable subset of $\mathbb N$ but it is not a proper subset of itself. – Arjun Banerjee Oct 24 '18 at 15:17
• If a set has the same cardinality of a proper subset then such set is infinite, not uncountable. The approach above clearly shows that $\mathcal{P}_{fin}(\mathbb{N})$ has the same cardinality of $\mathbb{N}\times\mathbb{N}$, and I dare you to say that $\mathbb{N}\times\mathbb{N}$ is uncountable! – Jack D'Aurizio Oct 24 '18 at 15:19