16. Uncountability

Mar 1, 2022

Uncountable sets

Will prove there is a language $L$ which is not accepted by any TM.

Technique: TMs are countable, languages are uncountable (more languages than TMs)

Powerset is uncountable

Theorem: If $S$ is an infinite countable set, then the powerset $2^S$ of $S$ is uncountable.

Powerset $2^S$ contains all possible subsets of $S$, e.g. let $S=\{a,b\}$ then $2^S=\{\mathrm{\varnothing },\{a\},\{b\},\{a,b\}\}$.

Proof.

Since $S$ is countable, we can list its elements in same order: $S=\{s_1,s_2,s_3,\dots \}$.

Elements of the powerset have the form: $\mathrm{\varnothing }$, $\{s_1,s_3\}$, $\{s_5,s_7,s_9,s_{10}\}$, $\dots$, they are subsets of $S$. We can represent these subsets of $S$ in binary encoding:

Subset of $S$	$s_1$	$s_2$	$s_3$	$s_4$	$\dots$
$\{s_1\}$	1	0	0	0	$\dots$
$\{s_2,s_3\}$	0	1	1	0	$\dots$
$\{s_1,s_3,s_4\}$	1	0	1	1	$\dots$

where 0/1 denote absence/inclusion in subset.

Assume (for contradiction) that powerset $2^S$ is countable. Then we can list the elements of the powerset in some order, this ordering must exist if powerset is countable:

Powerset    Binary 
element     encoding
t1          1  0  0  0  ...
t2          1  1  0  0  ...
t3          1  1  0  1  ...
t4          1  1  0  0  ...
...         ...

Now let $t$ be the binary string whose bits are the complement of the diagonal: $t=0011\dots$ Also: $t\in 2^S$ since it is one of the subsets of $2^S$.

Is $t$ equal to any of: $t_1,t_2,t_3,t_4$ => no, it cannot be.

Thus $t\ne t_i$ for every $i$ since they differ on the $i^{th}$ bit.

However, $t\in 2^S$ means $t=t_i$ for some $i$     => contradiction.

Therefore powerset $2^S$ is uncountable.

Non-recognizable languages

Consider a finite alphabet $A=\{a,b\}$.

The set of strings $S=A^{\ast }=\{a,b{\}}^{\ast }=\{ϵ,a,b,aa,ab,ba,bb,aaa,aab,\dots \}$, which is infinite and countable, because we can enumerate the strings in proper order.

Any language $L$ is a subset of $S$ and the powerset $S$ contains all languages:

$2^S=\{\mathrm{\varnothing },\{a\},\{b\},\{a,b\},\{aa,b\},\dots ,\{aa,ab,aab\},\dots \}$, which is uncountable.

Recall: TMs are countable => each TM recognizes some language => languages accepted by TMs are countable.

Let $X$ be the languages accepted by TMs (countable) and $2^S$ is all possible languages (uncountable), therefore $X\ne 2^S$, and we get $X\subset 2^S$ (strict subset). Therefore there exists some language that is not TM-acceptable.