PDF of Prof. Santosh’s handwritten notes is here.

- 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.

**Godel’s Incompleteness Theorem**

Any ‘sufficiently powerful’ axiomatic system is either:

1. Inconsistent: a statement that is provable and so is its negation

2. Incomplete: a true statement that is not provable within the system

An axiomatic system is ‘sufficiently powerful’ if it can encode Turing Machines.

**Proof**

Any candidate proof of a statement can be checked within the system.

We assume that the statement which stands for “TM M halts on input x” can be expressed in the system.

Assumptions:

- If halts on , there is a proof of
- If does not halt on , there is a proof of

Consider the following TM :

TM on input

- While(True)
- Enumerate every proof of length (there are finitely many):
- If is a proof of : ACCEPT
- If is a proof of : REJECT

- Enumerate every proof of length (there are finitely many):

The TM will always halt since there is either a proof of or a proof of and the TM will find it in finite steps. Thus, the TM decides the language . From previous lectures, we know that is undecidable. This leads to a contradiction.

If we assume our system is consistent, at least one of our assumptions is incorrect. If either assumption is incorrect, we have a true statement that is unprovable in the system.

**Alternative proof via Kolmogorov complexity**

Recall that the Kolmogorov complexity for a string is defined as:

M on input y produces x

Also, we proved the following theorem: is undecidable

Take any axiomatic system where the statement “” can be expressed. Also, assume that it is possible to verify if a string is a proof of a statement in the system.

**Theorem**: there exists true statements that are unprovable within any consistent system. More concretely, , , , the statement is true but cannot be proved.

**Proof**:

Suppose if is true, it has a proof in the system. We also assumed that any candidate proof of a statement can be verified in the system. This gives us the ability to find incompressible strings.

Define TM on input :

- enumerate pairs of integers
- for each pair , enumerate strings of length and proofs of length
- If is a proof of the statement :
- Output and halt

If exist for , the TM will output for which , where denotes the size of .

Thus, s.t. , the statement has no proof!

This is particularly striking since it is easy to produce strings for which . If we pick a random string of length , then with probability , .