Find the cardinal of the set of all infinite sequences of $0,1,-1$ such that each sequence contains each digit at least once - Check my answer

Question

As the title says, we are asked to find the cardinal of the set of all infinite sequences made from the digits $0,1,-1$ such that each sequence contains each digit at least once.

My answer

I solved this with a somewhat combinatorical approach. We know each sequence contains every digit at least once, so at first let's choose a place in the sequence where there is $0$, we have $\aleph_0$ options for that, then we choose a place for $1$, we have $\aleph_0-1=\aleph_0$ options for that, and then we choose a place where $-1$ fits, we have $\aleph_0$ options for that as well. This sequence now contains every digit once.

For the rest of the numbers in the sequence, we can fit in whatever we want, so we have $\aleph_0$ "free" spaces, and in each space we can put either $0,1,-1$, so overall that $3^{\aleph_0}=c$ options (Where $c$ is the cardinal of the continuum)

So we have $\aleph_0^3*c=\aleph_0*c=c$, and that set we are looking for is uncountable.

Is this correct?

Answer 1

Actually, there's slight problem with your proof which Tobias Kildetoft did not catch. The problem is that you've overcounted. Consider, for example, the element of the set in question,

$1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \ldots$

You've counted this element more than once! You've in fact counted it $\aleph_0$ times -- one time for each of the $0$s. The problem is that you're distinguishing the initial mandatory $0$ from the later $0$s, when in fact all $0$s are indistinguishable. In other words, when you say

"We know each sequence contains every digit at least once, so at first let's choose a place in the sequence where there is 0, we have $\aleph_0$ options for that"

there could easily be more than one place in the sequence where there is a $0$, in which case you are overcounting by counting all of the places and not just one of them.

(I hope this makes sense; ask me if you need clarification.)

Since you've overcounted, your proof shows that the cardinality is at most the continuum, and not that it is equal to the continuum.

---

Generally speaking, if you have a set $S$ and want to prove its cardinality is $\alpha$, it's easiest to prove first $|S| \ge \alpha$, and second $|S| \le \alpha$. That way you don't have to close all the loopholes like the one above.

Therefore, to fix your proof, I recommend showing the set has cardinality at least $c$ and at most $c$. One method of doing so is discussed in the comments to your question.