0
$\begingroup$

Please note I'm new to all this - so can you explain it simply please. Really appreciate it

I'm trying to prove that the set of all finite and countably infinite sequences over {0,1} is not countable (I think).

I have tried using the Diagonalisation technique but i'm a bit confused. I know that the set of all finite length strings is countably infinite and using the Diagonalisation technique to construct a language we can proof by contradiction that it is not countable.

Any suggestions on how to complete it or where to start (if i'm thinking about it in the wrong way)?

Thanks in advance

$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

First, it suffices to show that the set of all countable sequences is not countable. That avoids having to deal with sequences where $x_n$ isn't defined for some $n$. Then we can define a very natural map from that set to $[0,1)$ via $$ f \,:\, \{0,1\}^\mathbb{N} \to [0,1) \,:\, (x_n) \mapsto \sum_{k=1}^\infty x_n2^{-n} $$

If you can show that $f$ is surjective, and already know that $[0,1)$ has the same cardinality as $\mathbb{R}$, then it follows that $\{0,1\}^\mathbb{N}$ also has at least that cardinality.

$\endgroup$
9
  • $\begingroup$ Thanks for your prompt response, but can you take a step back (just a beginner). I'm not sure I understand what you're saying. Is the set of all finite and countably infinite sequences, infinite? If so, why would it be countable? $\endgroup$ Commented Apr 22, 2014 at 17:45
  • $\begingroup$ Why are you ignoring the fact that the set is finite and countable infinite? Or is it just grouped under countable? $\endgroup$ Commented Apr 22, 2014 at 17:50
  • $\begingroup$ This is a circular argument. You just showed that $|\{0,1\}^{\Bbb N}|\ge|\Bbb R|$ and then claim that $|\Bbb R|=|2^{\aleph_0}|$ is known, but $\{0,1\}^{\Bbb N}=2^{\aleph_0}$ is the definition, and nowhere does countability show up in any case. $\endgroup$ Commented Apr 22, 2014 at 17:52
  • $\begingroup$ Sorry - I'm not a mathematician. So I don't understand. Is it possible to explain it in simple terms? Thank you $\endgroup$ Commented Apr 22, 2014 at 17:53
  • $\begingroup$ @Harry I would recommend my answer or drhab's, which give direct proofs of uncountability, over this one. $\endgroup$ Commented Apr 22, 2014 at 17:56
0
$\begingroup$

Let $X=\{0,1\}^{\le\omega}$ be the set of all countable sequences of $\{0,1\}$, and suppose $f:\Bbb N\to X$. Now define

$$g(n)=\begin{cases}1&\mbox{if }n\in\operatorname{dom}f(n)\wedge f(n)(n)=0\\0&\mbox{otherwise}\end{cases}.$$

If $g=f(n)$ for some $n$, then $g(n)=f(n)(n)=0$ implies $g(n)=1$ and $g(n)=1$ implies $g(n)=0$, a contradiction. Thus $g\notin\operatorname{ran} f$ and $f$ is not surjective. If $X$ was countable, there would be a surjection from $\Bbb N$, so it follows that $X$ is uncountable.

$\endgroup$
3
  • $\begingroup$ Thank you, but can you explain yours a bit more. What does 'dom' stand for, i'm not familiar with the notation you used. If you can use the diagonalisation technique for this question, can you explain it using that? $\endgroup$ Commented Apr 22, 2014 at 18:12
  • 1
    $\begingroup$ @Harry A countable sequence is a function from the natural numbers (or a subset) to, in this case, $\{0,1\}$. For example, the sequence $\langle 1,0,1\rangle$ is a function such that $f(1)=1$, $f(2)=0$, and $f(3)=1$. $4$ is not in the domain (that's what 'dom' means) of the function. Thus the function $g$ is only equal to $1$ when the sequence $f(n)$ has an $n$-th term and this term is equal to $0$. $\endgroup$ Commented Apr 22, 2014 at 18:15
  • $\begingroup$ @Harry The reason this is called the "diagonal technique" is because of the $f(n)(n)$ part. That is, we construct a function by drawing all the $0$'s and $1$'s of each function in a big matrix, then drawing a diagonal line on that matrix and make a new function from those terms (but flipped, so we get a contradiction). $\endgroup$ Commented Apr 22, 2014 at 18:19
0
$\begingroup$

Let $F$ be the set of functions $\mathbb{N}\rightarrow\left\{ 0,1\right\} $. Then it corresponds with the set of countably infinite sequences over $\left\{ 0,1\right\} $. Now assume that $F$ is countable. Then it can be well-ordered like $F=\left\{ f_{n}\mid n\in\mathbb{N}\right\} $ where the $f_{n}$ are functions $\mathbb{N}\rightarrow\left\{ 0,1\right\} $. Now define function $g:\mathbb{N}\rightarrow\left\{ 0,1\right\} $ by $n\mapsto0$ if $f_{n}\left(n\right)=1$ and $n\mapsto1$ if $f_{n}\left(n\right)=0$ . Then $g\in F$ but $g\ne f_{n}$ for each $n$ and a contradiction is found. We conclude that $F$ is not countable.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.