Cool proofs

When I was in university, our course had a forum that we maintained ourselves in which we posted anything which would be of help to each other or which we found worth sharing. At the time of writing this, the forum will soon be closed down and all of the information in it will be probably lost. I shall post here my geekiest post ever which was titled "Cool proofs" in which I posted 3 mathematical proofs used in computer science which I literally found cool. ^^

Power set of an infinite set is uncountable

By uncountable we mean that you cannot have a one to one mapping from a countable infinite set, usually the natural numbers to the uncountable one.

For example the set of all integers is countable because there exists a bijective mapping from the natural numbers to the integers, for example:
0 -> 0
1 -> -1
2 -> 1
3 -> -2
4 -> 2
...
That is, even numbers point to positive integers and odd numbers point to negatives. So for every integer there exists a natural number which points to it and every natural number points to an integer. So even though there appears to be more integers than natural numbers, in reality they are equal because they are both countable infinite sets.

Now in order to show that the power set of an infinite set is uncountable we need to show that there exists at least one element of the power set which cannot be pointed by a natural number. Consider this random relation of natural numbers pointing to elements of the power set of all natural numbers:
0 -> {}
1 -> {1}
2 -> {0, 1, 2}
3 -> {1, 3}
4 -> {3, 5}
5 -> {1, 2, 3, 4}
6 -> {100, 1000, 10000}
...
Notice that some natural numbers are pointing to sets which contain themselves and others do not. Lets call the numbers which point to themselves Selfish and the others Non-Selfish. For example 1, 2 and 3 are selfish whilst 0, 4, 5 and 6 are not. Given that the power set of all natural numbers contains every possible subset of natural numbers, it stands to reason that one of the subsets should happen to be the set of all Non-Selfish numbers in our relation. Let's call the natural number which points to the set of all Non-Selfish numbers 'd' and the set of all Non-Selfish numbers S. Since every natural number must either be a Selfish number or a Non-Selfish number, we can safely say that d itself is either a Selfish number or a Non-Selfish number. So what is it?

If d is a Selfish number then it is an element of S. But only Non-Selfish numbers are elements of S.
If d is a Non-Selfish number then it is not an element of S. But S contains all Non-Selfish numbers.
Therefore we have reached a contradiction, because we have found an element which cannot be mapped by a natural number. Therefore it is impossible to make a bijective relation between the natural numbers and the power set of all natural numbers. Therefore the power set of an infinite set is uncountable.

QED

Set of all infinite length binary strings is uncountable

Enumerate the infinite length binary strings in a table in some order. For example:
0011111000110011...
1011100101100100...
1010101010010101...
0000000000000000...
...
Now we can refer to a particular string by referring to its corresponding row number. We can also refer to a particular bit in the string by referring to a particular column number. Let B(r,c) be the bit in column c of the string in row r.

If this set was countable, we can create a bijective mapping from the natural numbers to each and every binary string. But it is impossible to enumerate each and every infinite length binary string because no matter what order we use and no matter how many strings we include, it is always possible to find a string which is not included. Here's how:
Consider the diagonal bits in the table, that is, consider B(i,i) for every natural number i. Construct a string, s, which is made of the diagonal bits, inverted. That is, s[i] = !B(i,i). Now for every string, there is at least one bit which is different from s, because the diagonal includes one bit from every string and s has that bit inverted. Given the previous table, s would be 1101...

So no matter how many strings you enumerate (infinity included) there are always strings which are not included in the enumeration. Or conversely, no matter how you construct a relation of natural numbers pointing to the strings, there are always strings which are left out. Therefore the set of all infinite length binary strings is uncountable.

QED

Notice that for any power set, its elements can be encoded into binary strings, where each bit represents whether a particular element in the original set is in that subset. For example the power set of {1,2} is {{}, {1}, {2}, {1,2}} which can be represented as {00, 10, 01, 11} where the first bit says if 1 is in the set and the second says if 2 is in the set. Therefore if the set of all infinite length binary string was countable, the power set of an infinite set was also countable.

The halting problem

The halting problem proves that it is impossible to construct an algorithm (program which always terminates) which will analyze any program and correctly answer if, given a particular input, will terminate. Here's how.

Assume that such a program exists and can be used by simply calling the function Halt(p,i) which will return whether program p will terminate given input i. What we shall do is construct a program which will use Halt on itself and do the opposite. If this is possible than we have just found a case where Halt will fail, no matter what the implementation.

Construct program D which is defined as:
D(p) = if Halt(p,p) then infinite_loop else terminate
Program D will take a program p, check if it halts when given itself as input and enter into an infinite loop if so or terminate otherwise. If this self input confuses you, think of the input to be a copy of the original program. So if I have written a compression program which takes other files and compresses them, I can copy the program and compress the copy, essentially giving the program itself as input.

The reason we constructed such a funny program is that if we give D itself as input, the following will happen:
D(D) = if Halt(D,D) then infinite_loop else terminate
and as you can see, Halt will essentially check if D(D) will terminate, therefore checking if the whole program will terminate. But what does the program mean? The program will either terminate with itself as input or not, but if it terminates then Halt will return true, causing the program to enter an infinite loop, whilst if it does not terminate then Halt will return false, causing the program to terminate.

So if we now call Halt on this program, by calling Halt(D,D), Halt will not be able to come up with a correct answer because D will check what the output will be and do the opposite. Notice that we will receive an answer, it is the same as that given in the if-condition, but it will obviously be the opposite of what will happen. Remember that Halt will call D(p) and pass D as input (instead of p) and that D as a program and D as an input are two separate 'files' which are copies of each other. Self reference can be detected by for example changing a global variable to know how many times a function has been called but
a) A semantically equivalent function can be rewritten which avoids such tricks, yet results in the same problem.
b) This means that some program-input pairs will not be accepted, which means that you have not constructed the required function. After all, what do you think Halt(D,D) should output?

Therefore we have proven that it is always possible to construct a program which will cause Halt to give a wrong output. Similarly, you cannot construct an algorithm which will tell you if a particular action will be carried out in a program given an input because you can construct a program similar to D which will cause it to give the wrong output. Namely D(p) = if ActionPerfomed(p,p) then avoid_action else perform_action.

QED