The Land of Green and Blue

https://en.wikipedia.org/wiki/Common_knowledge_(logic)

There is a well known logic probably which beautifully introduces the difference between fact and knowledge.

This is the problem of the green-eyed islanders.

Imagine that there exists an island on which everyone is either green-eyed or blue-eyed. These islanders have a rule. If you know you have blue eyes, you have to leave. However, no one will make you leave, no-one will tell you that you have blue eyes and there are no mirrors. It is not enough to have blue eyes, you have to know.

As a result, there are a number of blue-eyed islanders happily living on the island, blissfully unaware of their condition, even though everyone around them knows they should leave. Let’s call that number k.

One day, you, a famous explorer, arrive on the island to observe this anthropological oddity. You live with the islanders for a few days, observe that the situation is stable, since none of the islanders know the colour of their own eyes, and then leave. Before you leave, however, you make an offhand statement that you think is of no consequence. You say, ‘at least one of you has blue eyes.’

A while later, you return to the island to repeat your observations on the societies stability and discover something incredible. Every one of the blue-eyed islanders has left. Your words destroyed the stability of the society, yet you didn’t introduce any new information, since every islander could observe at least one other blue-eyed islander. How could this be?

The solution to this problem is well-documented and demonstrates proof by induction.

Remember k, the number of islanders with blue eyes? Image your value of k is 1. Now, when you stated that at least one islander has blue eyes, everyone already knows this except the islander with blue eyes. Observing that he only sees green-eyed islanders, the blue-eyed islander deduces that he must have blues and leaves that night.

Imagine, now that k = 2. On the first day after you make your statement, every islander can see at least one blue-eyed islander, so no-one leaves. However, on the second day, we know from above that if there was only one blue-eyed islander, they would have known this and left. Since no-one left, there must be at least 2 blue-eyed islanders, so anyone who can see only one blue-eyed islander must, themselves be blue-eyed and will leave. Therefore, on the second day, both blue-eyed islanders leave.

By induction, we can extrapolate this to any value of k, such that for k blue-eyed islanders, they will all leave on the k’th day.

Simple, right?

Except, since your statement didn’t introduce any new information, then why is k measured from the date of your statement. Surely, if all the islanders already knew that there was at least 1 blue-eyed islander, then k can be measured from any point. Since there is always a point k days previously, the blue-eyed islanders should have left before your arrival. But, since before your statement, no islanders knew the colour of their own eyes, they should have still been there. Paradox?

This is often explained in terms of common knowledge vs individual knowledge. While everyone knew that there was at least one blue-eyed islander, they did not know that everyone else knew.

There’s a far simpler explanation.

The proof is wrong.

When you read through the proof, what did you think when you got to the step about induction? Did you just accept it and move on? If so, you did what 99% of people do when reading the proof. It seems logical. K=1 is true. K=2 is true if K=1 is true. Therefore, since k+1 can be shown to be true if k is true, we can prove for all k, right?

I’ll get back to this. Let me first do what we failed to do in the original proof – imagine k=3.

On the first day, each of the blue-eyed islanders can see 2 blue-eyed islanders. Since 2>1, no one leaves. On the second day, as we’ve shown in the earlier proof, anyone who could only see green-eyed islanders would have left, so since no one left, we know that all of the blue-eyed islanders can see one other islander with blue eyes. So there must be at least two islanders with blue eyes, since we’ve eliminated k=1.

Except, we also know that there was no-one who could only see green-eyed islanders. Nor was there anyone on the island who believed that there might be someone on the island who could see only green-eyed islanders. Everyone on the island can either see 2 or 3 blue-eyed islanders. Which means that everyone on the island knows that everyone else knows that everyone else on the island can either see 1,2 or 3 blue-eyed islanders.

In other words, after the first day, we have neither changed our common knowledge nor our individual knowledge.

By induction, this means we will not change our knowledge on the second day, or the third day or any other day.

In other words, for any k>2, no islanders will leave.

Put simply, the reason the original proof is invalid but convincing is that it fails to specify the method of induction. This is the equivalent to assuming that the next number in the sequence 1,2 must be 3. For a doubling sequence, it could be 4 however. In the case of our islander problem, it’s even more ridiculous – there is no next number. The sequence is precisely of length 2.

This can be proved by going back to the first principles of knowledge rather than fact.

In our original proof, we broke down the islanders into those that can see either k or k-1 blue eyes.

If we recast this as knowledge, we can frame this into two sets of beliefs

1. Green Eyes

– I can see k islanders with blue eyes

– There are either k or k+1 islanders with blue eyes.

– Islanders with blue eyes can see either k-1 or k islanders with blue eyes

– Therefore, islanders with blue eyes either believe that other islanders with blues eyes can see k-1 or k, or k or k+1, islanders with blue eyes

2. Blue eyes

– I can see k-1 islanders with blue eyes

– There are either k-1 or k islanders with blue eyes.

– Islanders with blue eyes can see either k-2 or k-1 islanders with blue eyes

– Therefore, islanders with blue eyes may believe that other islanders with blues eyes can either see k or k-1, or k-1 or k-2, islanders with blue eyes

Now we see why the problem works for k=1 and k=2. In both cases, We have eliminated a possibility: k-2 in the second case, and both k-1 and k-2 in the first case.

For k=1, if we eliminate both k-1 and k-2, then all blue-eyed islanders know two things:

– all islanders with blue eyes believe there to be exactly k islanders with blue eyes.

– they themselves believe there to be k islanders with blue eyes.

– therefore they must have blue eyes

For k=2, we eliminate k-2:

Therefore, eventually, all blue-eyed islanders know two things:

– all islanders with blue eyes believe there to be either k or k-1 islanders with blue eyes.

– they themselves believe there to be either k or k-1 islanders with blue eyes

– therefore they must have blue eyes

However, for k=3 and above, the statement k>=1 only eliminates k-3 and lower. In other words, it has no impact on the beliefs of the islanders.

In fact, from this we can show that the induction is not that the statement ‘there is at least 1 islander with blue eyes’ that will cause the blue islanders to depart for all values of k, but the statement ‘there are at least n islanders with blue eyes’ where n=k or k-1 and n>0.

Oh, and the islanders won’t leave in k days. They’ll leave in k+1-n days.

Leave their beautiful community never to come back. All because of one thoughtless statement.

From you.

Don’t you just love logic.