There is a really elegant proof for this that requires virtually no math background at all.
All computer programs are a finite sequence of bytes, which is just a number in base 256. So each computer program can be represented as a unique natural number. This statement is elaborated in detail below the divide.
- If a computer program prints its own number, then that program is blue and its number is blue.
- If a program does not print its own number, then that program is red and its number is red.
The set of red numbers is a subset of natural numbers. Now write a program that prints this set. Is that program red or blue?
- Suppose the program is red. Then it must print its own number as part of the set, but this causes it to be a blue program.
- Suppose the program is blue. Then it must print its own number as a blue program, but this causes its output to not be the set of red numbers.
This program is impossible! Therefore, there must exist at least one set which programs can not print.
This is how I learned the Cantor set/subset inequality. I couldn't find a better link, but I got it from a Martin Gardner book.
Let's get into the statement
each computer program can be represented as a unique natural number
This will involve some math, particularly working in binary. We are going to create a Gödel numbering for computer programs.
Assume every program can be represented as a finite string of 0's and 1's. This accurately describes real world programs and the input to a Universal Turing Machine.
So any given program X is x1x2...xN where xi is 0 or 1 for each i.
Let us define
Num(X) as the binary number 1x1x2...xN.
Num(X) of the program X = '0110' would be '10110' in binary, which is 22.
Num(X) gives each program a unique natural number because...
- If two programs have differing length, then the longer program has a greater
Num() than the shorter.
- If two programs have identical length but differ on some bits, then the binary representation is different for that bit, so
Num() will differ between the programs.
- In any other case, the two programs have identical length and identical bits, meaning they are identical programs.
Now we can get on to the set theory part of the proof.
That proof assumed binary, but as long as your program is finitely describable in any language which uses a finite number of characters (like English!) you can similarly map it to a unique natural number. This is interesting because it extends the proof from programs to any describable concept (like genie wishes!).