Prove that a set is not countable

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)?

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.

• 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? – Harry Apr 22 '14 at 17:45
• Why are you ignoring the fact that the set is finite and countable infinite? Or is it just grouped under countable? – Harry Apr 22 '14 at 17:50
• 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. – Mario Carneiro Apr 22 '14 at 17:52
• Sorry - I'm not a mathematician. So I don't understand. Is it possible to explain it in simple terms? Thank you – Harry Apr 22 '14 at 17:53
• @Harry I would recommend my answer or drhab's, which give direct proofs of uncountability, over this one. – Mario Carneiro Apr 22 '14 at 17:56

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.

• 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? – Harry Apr 22 '14 at 18:12
• @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$. – Mario Carneiro Apr 22 '14 at 18:15
• @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). – Mario Carneiro Apr 22 '14 at 18:19

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.