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$
20
  • $\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$
    – J. Moeller
    Commented Oct 24, 2018 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
    Commented Oct 24, 2018 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
    Commented Oct 24, 2018 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
    Commented Oct 24, 2018 at 14:28
  • 1
    $\begingroup$ @rtybase Thank you so much for suggesting edits. $\endgroup$
    – Jimmy
    Commented Oct 24, 2018 at 14:55

1 Answer 1

3
$\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$
5
  • $\begingroup$ Could you please explain the flaws in my proof? $\endgroup$
    – Jimmy
    Commented Oct 24, 2018 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$ Commented Oct 24, 2018 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$
    – Jimmy
    Commented Oct 24, 2018 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$
    – Jimmy
    Commented Oct 24, 2018 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$ Commented Oct 24, 2018 at 15:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .