1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Prototank Oct 24 '18 at 14:02
  • $\begingroup$ 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$? $\endgroup$ – gebruiker Oct 24 '18 at 14:02
  • 2
    $\begingroup$ 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. $\endgroup$ – rtybase Oct 24 '18 at 14:11
  • 1
    $\begingroup$ @ArjunBanerjee then I'd suggest an edit so that $X=\left\{(x_n)_{n\in\mathbb{N}}\mid x_n\in\{0,1\} ...\right\}$ $\endgroup$ – rtybase Oct 24 '18 at 14:28
  • 1
    $\begingroup$ @rtybase Thank you so much for suggesting edits. $\endgroup$ – Arjun Banerjee Oct 24 '18 at 14:55
2
$\begingroup$

$\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.$$

$\endgroup$
  • $\begingroup$ Could you please explain the flaws in my proof? $\endgroup$ – Arjun Banerjee Oct 24 '18 at 14:59
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Oct 24 '18 at 15:03
  • $\begingroup$ 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. $\endgroup$ – Arjun Banerjee Oct 24 '18 at 15:12
  • $\begingroup$ In your example, $\mathbb N$ is a countable subset of $\mathbb N$ but it is not a proper subset of itself. $\endgroup$ – Arjun Banerjee Oct 24 '18 at 15:17
  • $\begingroup$ 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! $\endgroup$ – Jack D'Aurizio Oct 24 '18 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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