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 = \{ \emptyset, \{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: \(\emptyset\), \(\{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:
1 2 3 4 5 6 7 | |
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 \neq 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^* = \{a, b\}^* = \{\epsilon, 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 = \{\emptyset, \{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 \neq 2^S\), and we get \(X \subset 2^S\) (strict subset). Therefore there exists some language that is not TM-acceptable.