- Rationals are countable. Map each pair to a unique natural number.
- Reals in are uncountable. Assume, for a contradiction that they are countable. Construct a real whose i’th digit is 0 if the i’th digit of the i’th number is odd and 1 otherwise. Then this number has some index t. The t’th digit of the number gives us a contradiction.
- Finite strings are countable, infinite (even binary) strings are uncountable.
- Diagonalization is the proof technique we used for showing sets are uncountable and languages are undecidable.
- Here’s a different proof of the existence of an undecidable language.
- For a binary string , let . In words, it is the shortest string including the description of a Turing machine and an input on which the TM produces the desired string .
- Claim 1. For every integer , there is a string s.t. .
- Define . , the language of incompressible strings is infinite.
- Theorem. The language is undecidable.
- Proof. Suppose is decidable. Then consider the following TM M:
- On input an integer , M scans through each string of length and outputs the lexicographically first string that belongs to .

- Claim 2. Let be the string output by M on input . Then . But . Contradiction for larger than some constant!
- Therefore, our assumption is false and is undecidable.

Advertisements