The diagonal lemma

Figure 1: Diagonalization (where a code for a function is
fed into the function itself)

The diagonal lemma (or fixed point theorem) is an essential part of several notable mathematical proofs including Gödel's incompleteness theorems and Tarski's undefinability theorem.

The term diagonal is used because it bears some resemblance to Cantor's famous diagonal argument.

Intuitively, the diagonal lemma says that for any property A, there is a self-referential statement B saying that it has property A.[1] The lemma is expressed as a logical equivalence:

\[\boldsymbol{B \Leftrightarrow A(\#B)}\]

A can be any property about numbers such as isPrime or isEven. This means that statement B must be translatable to a number, which is indicated by the # in the lemma above. The translation is achieved by Gödel-numbering which assigns a unique natural number to every possible statement.

A simple way to implement Gödel-numbering is by converting the statement to its ASCII representation. So the statement "isEven(2)" translates to the number 69734576656e283229 in hexadecimal (which can be translated with a text to hex converter). That number is also translatable back to the original statement again. Thus there is a one-to-one mapping between a statement and its Gödel number.

Figure 2: Substitution along the diagonal

We can also represent statements containing free variables. For example, the statement "isEven(x)" translates to the Gödel number 69734576656e287829.[2] Now consider the table in Figure 2 where the rows (j) represent the Gödel numbers of statements and the columns (k) represent the possible values for x (themselves natural numbers). We can define the function sub(j, k) to translate Gödel number j as a statement, then substitute number k in place of x and, finally, translate that statement to a Gödel number. For example, sub(69734576656e287829, 8) will translate Gödel number 69734576656e287829 as "isEven(x)" then substitute 8 for x, producing the evaluable statement "isEven(8)" and finally translate that statement to the Gödel number 69734576656e283829.

Since k can be any natural number, we can also substitute the Gödel number of the statement itself. That is, sub(69734576656e287829, 69734576656e287829) will translate Gödel number 69734576656e287829 as "isEven(x)" then substitute 69734576656e287829 for x, producing the evaluable statement "isEven(69734576656e287829)" and finally translate it to Gödel number 69734576656e2836393733343537363635366532383738323929. This particular kind of substitution (where j = k) is called diagonalization because it shows up on the diagonal (i.e., the blue squares) of the table in Figure 2. This self-referential process is key to what follows.

To simplify, the diagonalization can be defined by a function with one free variable x:

\[\boldsymbol{diag(x) = sub(x, x)}\]

I will now declare one further function, C(x), as logically equivalent to the property A applied to diag(x):

\[\boldsymbol{C(x) \Leftrightarrow A(diag(x))}\]

Function C will also have a Gödel number which I'll call m. So m is the Gödel number of the function C which, on input x, is logically equivalent to interpreting x as a function, running x on itself, and then running A on the result (partially illustrated by Figure 1). For example, suppose input x is the Gödel number of "isEven(x)" and A is the property isPrime, then we would have: [3]

\[\boldsymbol{C(\#''isEven(x)'') \Leftrightarrow ~''isPrime(diag(\#''isEven(x)''))''}\]

As noted earlier, # indicates the Gödel number of the subsequent statement. Now suppose that m (the Gödel number of function C) is itself the input to function C. This will result in:

\[\boldsymbol{C(m) \Leftrightarrow A(diag(m))}\]

The diag function interprets m as a function (i.e., C(x)) and substitutes m for x (i.e., C(m)). So:

\[\boldsymbol{C(m) \Leftrightarrow A(\#C(m))}\]

Now let B = C(m) and the result is the diagonal lemma:

\[\boldsymbol{B \Leftrightarrow A(\#B)}\]

When expanded out, B is A(diag(#"A(diag(x))")) which is logically equivalent to the right-hand-side of A(#'A(diag(#"A(diag(x))"))'). For example, suppose that A is the property isEven. Statement B is then 'isEven(diag(#"isEven(diag(x))"))'. That is, B says that the diagonalization of the inner statement is an even number. But the diagonalization of the inner statement just is B's Gödel number. So, in effect, B says of itself that its Gödel number is even. Further saying that the Gödel number of B is even is, therefore, logically equivalent to what B already says of itself.[4]

The diagonal lemma can also be used to construct the famous Gödel statement where A is the property of being unprovable. That is:

\[\boldsymbol{B \Leftrightarrow isNotProvable(\#B)}\]

If B is true, then B is, as it says, not provable. Whereas if B is false, then it is false that it is not provable. That is, it is provable. Thus either statement B is true and not provable, and so the system is incomplete. Or else statement B is false and provable, and so the system is inconsistent (since it can prove a false statement). That is Gödel's first incompleteness theorem.

The diagonal lemma can also be used to construct the liar sentence where A is the property of not being true. That is:

\[\boldsymbol{B \Leftrightarrow isFalse(\#B)}\]

If B is true, then B is false. Whereas if B is false, then B truthfully asserts that. Either way, the result is a contradiction. The conclusion of Tarski's undefinability theorem is that the truth predicate is not definable in the object language, so the liar sentence cannot be constructed.

Useful references:

• Proof of Diagonalization Lemma - p181 - Professor Anita Wasilewska
• Gödel’s First Incompleteness Theorem explained - A Trivial Knot blog (also the source of Figure 2)
• "Diagonal fixed points are constructed with a weird trick where you feed a code for a function into that function itself. Given a function f, if you can construct a function g, which on input x, interprets x as a function, runs x on itself, and then runs f on the result (i.e. g(x) := f(x(x)).), then g(g) is a fixed point of f because g(g) = f(g(g))." - Fixed Point Discussion - Less Wrong
• Gödel numbering and diagonalization - Greg Restall
• Diagonalization & The Fixed Point Lemma - Brendan Cordy
• Fixed point (mathematics) - Wikipedia

--

[1] Strictly-speaking, that the numeric representation of statement B has property A. This is indicated by the # which translates from the statement to a natural number (termed its Gödel number).

[2] In this post, the term statement indicates both formulas with free variables (e.g., "IsEven(x)", where x can be any natural number) and formulas without free variables (e.g., "isEven(2)" or "isEven(3)" which are sentences that evaluate as true or false).

[3] The right-hand-side statement resolves to "isPrime(69734576656e2836393733343537363635366532383738323929)". You can use the hex to text converter to decode the Gödel number.

[4] To step through the final substitution in detail:

The inner statement says, "isEven(diag(x))", i.e., "the diagonalization of x is even". To diagonalize that statement is to substitute its Gödel number for x. That is:

    'isEven(diag(  #"isEven(diag(x))"  ))'

Which is to say, 'the diagonalization of #"the diagonalization of x is even" is even'. While the final statement just is the diagonalization of the inner statement, it also asserts a property of the diagonalization of the inner statement, namely, that it is even. Thus, in effect, the statement is asserting a property of its own Gödel number (that it is even).

The liar paradox (Part 2)

In my previous post I discussed the liar paradox and argued that it should not be considered either true or false because it is cyclic. That is, it never ends up successfully asserting anything about the world.

Interestingly, the Stanford Encyclopedia of Philosophy (SEP) entry for the Liar Paradox outlines an argument that the liar sentence implies a contradiction. The argument uses two inference rules, as follows:

• Capture: A implies "A" is true
• Release: "A" is true implies A

Taking these two rules together, the terms A and "A" is true are intersubstitutable [1]. The SEP argument, reproduced in plain English [2], is:

Let L be the sentence, "This sentence is not true".

    1. "L" is true or "L" is not true [Law of Excluded Middle]
    2. Case One:
         a. "L" is true
         b. L [2a: release]
         c. "L" is not true [2b: definition of L]
         d. "L" is true and "L" is not true [2a, 2c: conjunction introduction]
    3. Case Two:
         a. "L" is not true
         b. L [3a: definition of L]
         c. "L" is true [3b: capture]
         d. "L" is true and "L" is not true [3a, 3c: conjunction introduction]
    4. "L" is true and "L" is not true [1-3: disjunction elimination]

Line 1 assumes that the liar sentence conforms to the Law of Excluded Middle. That is, it assumes that the liar sentence is either true or not true and not some other value. Lines 2 and 3 analyze each disjunct as separate cases. In each case a contradiction is reached which is then inferred in 4.

The conclusion that the liar sentence implies a contradiction depends on the first premise being truth-apt. However, as argued previously, the liar sentence is not truth-apt and so therefore the first premise can't be either. Consequently logical inference rules and truth evaluation aren't applicable to it. A contradiction is only reached via a false assumption of truth-aptness.

The rule of thumb would be that a sentence is only truth-apt if it is grounded in a state of the world either directly or else indirectly via other sentences. Note that this condition fails for both the simple liar (where not true means false) and the strengthened liar (where not true means false or not truth-apt).

--

[1] This is Alfred Tarski's T-Schema: 'S' is true if and only if S (e.g., 'snow is white' is true if and only if snow is white).

[2] For example, I've replaced the corner symbols that indicate quasi-quotation with ordinary quotes.

The liar paradox

Consider our friend Pinocchio who says, "I am lying". Is his statement a lie? Or does he speak truly? It seems that if he is telling the truth, then he must be lying, just as he says. In which case he is not telling the truth. But if he is not telling the truth, then he is indeed lying. Just as he truly says!

This is known as the liar paradox. It seems that there is no satisfactory answer for whether Pinocchio is lying or speaking the truth. There are many variations of this paradox. For example, "Epimenides was a Cretan who made one immortal statement: 'All Cretans are liars.'". Another is the sentence, "This sentence is false."

In this post I will offer an explanation for the why the paradox occurs that builds on Gilbert Ryle's analysis [1].

The first thing that is usually noticed is that the statement, "This sentence is false." refers to itself. So perhaps self-reference is the problem. But we use self-reference all the time. For example, "I have a blue shirt on" is a perfectly valid statement. As is, "This sentence has five words".

So perhaps the problem is the way that the statement refers to itself. To evaluate whether the sentence is false first requires evaluating the truth value of the referring expression, namely 'This sentence'. That referring expression is just the original sentence. So that sentence, in turn, first requires evaluating the truth value of its referring expression, namely 'This sentence'. We can see that this is a recursive expression that never terminates in an evaluable statement. So it is not truth-apt [2].

But this raise the question as to why the statement, "This sentence has five words" doesn't have the same unending recursion. This statement expands as, "'This sentence has five words' has five words". We naturally stop at this point and just count the words in the inner sentence. But what is the rule for why we should stop? Shouldn't it expand indefinitely as well? One answer is that this sentence is grounded [3]. That is, the recursive expansion terminates in a sentence that doesn't mention truth.

However one can then go on to create strengthened liars such as, "This sentence is false or not truth-apt". If it is true, then it is false or not truth-apt, so it is not true. If it is false, then it is true, so it is not false. If it is neither true nor false then it is not truth-apt. Which is what the sentence says, so it is true! So it seems there is no satisfactory answer to the strengthened liar. However one approach here is to say that since the sentence is demonstrably not truth-apt, then it should not be subsequently read as making a truth-apt claim. It is a kind of illusion - it appears to be truth-apt but it is not.

A shortcoming of the above approach is that that there doesn't seem to be a principled rule to apply to determine whether a liar-style sentence is truth-apt. One just plugs in values and tries to find a custom solution. If a solution is found, then a new strengthened liar is constructed to foil it (these are also aptly called revenge liars!) And we don't seem closer to understanding what it is that makes liar-style sentences defective.

The approach I take instead involves distinguishing between use and mention. My claim (on ordinary use grounds) is that only the use of statements can be truth-apt whereas mentions of statements are not truth-apt (and treating them as if they were is a category mistake). When we mean to mention a statement rather than use it, we enclose the statement in quotation-marks. Consider the sentence, "This sentence has five words". This expands as "'This sentence has five words' has five words". The inner sentence is mentioned and thus (per my claim) is not truth-apt. This isn't an issue here since a truth predicate is not being used and the sentence is readily evaluable with the predicate it does have.

But what about a statement like "'Snow is white' is true"? Since that statement does evaluate as true, it seems that a mention of a statement can be true after all. My claim is that this is not the case. Instead, in ordinary use, a truth-predicate has a disquotation function [4]. That is, it removes the quotation marks and uses the statement. Thus, the statement ""Snow is white' is true" is transformed to "Snow is white" which (when used) is a truth-apt statement. More generally, "'p is q' is true" becomes "p is q" and "'p is q' is false" becomes "Not (p is q)". I will term this the disquotation rule.

Now consider the liar sentence, "This sentence is false". This expands as, "'This sentence is false' is false". Note that the inner sentence is mentioned, not used, so it is not truth-apt. However, since a truth predicate is specified, the disquotation rule can be applied. So applying this rule to the liar sentence, we get:

1. This sentence is false
2. "This sentence is false" is false [mention]
3. Not ("This sentence is false" is true)
4. Not (This sentence is false) [disquotation]
5. Not ("This sentence is false" is false) [mention]
6. "This sentence is false" is true
7. This sentence is false [disquotation]

What emerges is that the liar sentence is cyclic (line 7 is identical to line 1). We can also apply this rule to the truth-teller sentence:

1. This sentence is true
2. "This sentence is true" is true
3. This sentence is true

Thus the truth-teller is also cyclic. We can also test this approach with a conventional self-referring sentence:

1. This sentence has five words
2. "This sentence has five words" has five words
3. True

So the sentence is indeed truth-apt. The nice thing about applying the disquotation rule is that there is no need to plug in values and test each one. We can just follow the logic of the statement and note whether it terminates in a truth-apt value or, else, cycles.

Now consider the strengthened liar:

Let L be the sentence, "This sentence is false or not truth-apt".

1. L
2. "L" is false or not truth-apt
3. "L" is false or "L" is not truth-apt
4. Not ("L" is true) or ("L" is not true and "L" is not false)
5. Not (L) or (not "L" is true and "L" is true)
6. Not L or (not L and L)
7. Not L or false
8. Not L
9. Not (not L) [substituting 8 into 1]
10. L

Thus the strengthened liar is cyclic and so is not truth-apt. But isn't this just what the strengthened liar says? Since it has been demonstrated that it is cyclic, its apparent truth-aptness is an illusion. Just as a straight stick can appear bent when partially submerged in water, so to a cyclic statement can appear truth-apt when it is actually not.

In conclusion, the reason why the liar sentence (and any strengthened liar) is not truth-apt is because the self-reference is cyclic. Conventional (non-cycling) self-reference is fine. [5]

For more paradoxical fun, see Part 2.

--

[1] From "Heterologicality", Gilbert Ryle, 1951:

"The same inattention to grammar is the source of such paradoxes as 'the Liar ', 'the Class of Classes ...' and 'Impredicability'. When we ordinarily say 'That statement is false ', what we say promises a namely-rider, e.g. '... namely that to-day is Tuesday'. When we say 'The current statement is false' we are pretending either that no namely-rider is to be asked for or that the namely-rider is '... namely that the present statement is false'. If no namely-rider is to be asked for, then 'The current statement' does not refer to any statement. It is like saying 'He is asthmatic' while disallowing the question 'Who?' If, alternatively, it is pretended that there is indeed the namely-rider, '... namely that the current statement is false', the promise is met by an echo of that promise. If unpacked, our pretended assertion would run 'The current statement {namely, that the current statement [namely that the current statement (namely that the current statement ...'. The brackets are never closed; no verb is ever reached; no statement of which we can even ask whether it is true or false is ever adduced.

Many of the Paradoxes have to do with such things as statements about statements and epithets of epithets. So quotation-marks have to be employed. But the mishandling which generates the apparent antinomies consists not in mishandling quotation-marks but in treating referring expressions as fillings of their own namely-riders."

[2] For a sentence to be truth-apt means that it is either true or false. Sentences like "Hello!" or "Twas brillig, and the slithy toves" are not truth-apt. A cyclic sentence like the liar sentence is also not truth-apt. (Note: an alternative view, called dialetheism, regards the liar sentence as both true and false.)

[3] Saul Kripke, 1975, “Outline of a theory of truth”.

[4] Disquotation is the reversal of the process of quotation. It transforms a quoted statement into an actual statement. That is, it uses the mentioned statement. For example "'Snow is white' is true" just means "Snow is white".

[5] Two more interesting sentences are worked out below:

Let L be the sentence, "This sentence is truth-apt".

1. L
2. "L" is truth-apt
3. "L" is true or "L" is false
4. "L" is true or not "L" is true
5. L or not L
6. True [Law of excluded middle]

Let L be the sentence, "This sentence is not truth-apt".

1. L
2. "L" is not truth-apt
3. "L" is not true and "L" is not false
4. Not "L" is true and "L" is true
5. Not L and L
6. False [Law of non-contradiction]

The moral law

In my last post I discussed the solution to the Euthyphro Dilemma. It so happens that a parallel dilemma can be constructed for ourselves. Do we approve of an action because it is good or is an action good because we approve of it?

For morality to be objective it must be based on something other than subjective opinion. In the case of humans, that something is human nature [1]. What distinguishes us from the rest of the animal kingdom is our capability for rational thought. Unlike other animals, which automatically act on instinct to survive, we face a choice - to live or to die. To live (and flourish) is the value that bridges the gap from the "is" of human nature to the "ought" of morality. [2]

An analogy may be helpful here. Medicine is a normative science based on physiology which presupposes the value of health. Ignoring facts about physiology leads to poor health. Similarly, morality is based on human nature and presupposes the value of life and well-being. Ignoring facts about human nature leads to misery for ourselves and society.

Normative terms such as "moral", "virtuous", "good", "bad", "evil" and so on derive their meaning from the choices we make in ordinary, everyday contexts (with well-being as the standard of value). There is substantial agreement across cultures about the content of morality, as evidenced by the widespread injunctions against murder, violence, theft and so on, and in commonly found maxims such as the Golden Rule. [3] Differences that we do find can be recognized as one of degree rather than as being moralities of a radically different kind. [4]

--

[1] For theists, human nature is usually understood to reflect God's nature which allows the moral law to be discoverable. Otherwise, as C.S.Lewis says, "If we once admit that what God means by "goodness" is sheerly different from what we judge to be good, there is no difference left between pure religion and devil worship." (From the "The Poison of Subjectivism" in "Christian Reflections".)

[2] In Aristotelian terms, humans are rational animals and human flourishing (eudaimonia) is the final cause (telos) that grounds moral actions. We can see precursors to value, purpose and choice in an animal's survival instinct. But value, purpose and choice are intentional terms that derive their literal meaning from their use in everyday human contexts.

[3] See the appendix of "The Abolition of Man" where C.S.Lewis presents textual evidence of a universal moral law across modern and ancient cultures.

[4] C.S.Lewis discusses this point in "The Poison of Subjectivism". He notes that the Nietzschean ethic is innovative not because it grounds a different kind of morality but because it rejects objective morality altogether. That is, Nietzsche accepts the subjective horn of the dilemma.

Euthyphro's Dilemma

In "The Poison of Subjectivism", C.S.Lewis asks, "But how is the relation between God and the moral law to be represented? To say that the moral law is God's law is no final solution. Are these things right because God commands them or does God command them because they are right?" [1]

This is the modern version of the dilemma first posed by Socrates in Plato's "Euthyphro". Lewis explains why he is unable to accept either horn of the dilemma.

"If the first, if good is to be defined as what God commands, then the goodness of God Himself is emptied of meaning and the commands of an omnipotent fiend would have the same claim on us as those of the "righteous Lord." If the second, then we seem to be admitting a cosmic dyarchy, or even making God himself the mere executor of a law somehow external and antecedent to His own being. Both views are intolerable."

Be that as it may, rejecting the dilemma is not a valid option here. In essence, the question posed is whether God's morality is subjective or objective and there is no middle ground between these two alternatives. [2] However, Lewis' concern with the "objective" horn of the dilemma turns out to be unfounded. An objective law need not be external and antecedent to the being that follows it.

To see this, consider the economic law of supply and demand. The truth of this law depends on the actual interactions between people. The law did not precede the existence of people since it depends on what people do. But neither did anyone create the law. Instead it is a discovered generalization of people's behavior. That is, the law of supply and demand describes what people do or, to phrase it differently, people act according to the law of supply and demand. [3] The law is objective rather than subjective because it exists independently of anyone's opinions about it albeit, in this case, not independently of people's behavior.

Similarly the existence of the moral law for God is conditional on God's nature and therefore not antecedent or external to it. Given God's nature, it prescribes what God should and should not do. That is, God is subject to the moral law which he did not create but which nonetheless depends on his existence. Adding the premise that "God is (always) good", the moral law also describes what God does and does not do. As Lewis says elsewhere, "... the Divine Will is the obedient servant to the Divine Reason." [4]

Note: The solution to the dilemma involves other philosophical issues which I haven't explored here but which I take a generally Aristotelian approach to. These include the problem of universals (what does it mean for abstractions, such as the moral law, to exist?), the is-ought problem (how does the moral law derive from a being's nature?) and the argument from morality (does the moral law require God?).

--

[1] "The Poison of Subjectivism" from "Christian Reflections" by C.S.Lewis.

[2] Lewis is aware that he doesn't have a satisfactory solution to the dilemma. He says, "But it is probably just here that our categories betray us. It would be idle, with our merely mortal resources, to attempt a positive correction of our categories - ambulavi in mirabilibus supra me." (Translation: I do exercise myself in great matters, in things too high for me.) However, despite his rejection of the dilemma in this instance, Lewis' general tenor in this essay and other writings is toward the "objective" horn.

[3] The law of supply and command is usually thought of as being true all else being equal. So, for example, when demand increases for a fixed supply of oil, government regulation could prevent the price from rising.

[4] Letter from C.S.Lewis to John Beversluis a few months before his death in 1963. From "C.S.Lewis and the Search for Rational Religion", p295, John Beversluis.

The Blue Eyes Puzzle (Part 2)

This follow-up post gives the solution to the Blue Eyes puzzle described here.

The answer is that the 100 blue-eyed people will leave the island on the 100th day.

The way to understand this answer is to first work through a much simpler version of the problem where there is only one-blue eyed person and one brown-eyed person on the island. Let's first try to solve it before the outsider arrives. The blue-eyed person doesn't see anyone with blue eyes, while the brown-eyed person sees one person with blue eyes. Since the blue-eyed person doesn't know whether there are any blue-eyed people on the island, he doesn't know whether he himself has blue eyes. So he will not leave the island.

However once the outsider informs the people that there is at least one blue-eyed person, the single blue-eyed person immediately knows that it must be him. Thus he leaves the island that night. Conversely, when the outsider makes her statement, the brown-eyed person doesn't yet know the color of his own eyes because he can already see someone with blue eyes. But he knows that if he does have brown eyes, then the other person will deduce their own blue eyes and leave the island that night. Or if he himself has blue eyes, then the other person will similarly not yet know the color of his eyes and will stay on the island. Once he observes the blue-eyed person leave the island that night, he then immediately knows that he himself has brown eyes.

So in this simple case, at least, the outsider's statement conveyed crucial information to the blue-eyed person that he didn't previously know and that made the difference to whether he left the island or not. Also, on observing the blue-eyed person leave the island, the brown-eyed person deduces that he himself has brown eyes.

Now consider the next simplest case where there are only two blue-eyed people and two brown-eyed people. Again, let's try to solve it before the outsider arrives. Each blue-eyed person can see one other blue-eyed person, while the brown-eyed people can see two people with blue eyes. Therefore everyone knows that there is at least one blue-eyed person on the island.

The first blue-eyed person realizes that if he himself has brown eyes then his scenario is identical to the single blue-eyed person scenario that we just analyzed. However, without the outsider's information, the other blue-eyed person cannot deduce that he has blue eyes and will therefore stay on the island. He similarly realizes that if he has blue eyes, he has no way of knowing this, so will stay on the island.

However when the outsider states that there is at least one blue-eyed person, the first blue-eyed person will now reason differently. He again realizes that if he has brown eyes then his scenario is identical to the single blue-eyed person scenario that we just analyzed. But he now knows that the other blue-eyed person would deduce that he himself has blue eyes and leave the island on the first night. So the first blue-eyed person now just has to wait until that night to see if the other blue-eyed person leaves the island. If he does, then he can deduce that he himself has brown eyes. If he does not leave, then he can deduce that he himself has blue eyes, and will leave on the second night. The other blue-eyed person reasons in the same way and also leaves on the second night. The brown-eyed person also reasons in a similar way. However, because he can see two blue-eyed people, he will wait until the second night to see what happens. When he observes the blue-eyed people leave the island on the second night, he then immediately knows that he himself has brown eyes.

So the outsider's statement, which only seemed crucial in the one blue-eyed person scenario was also crucial in the two blue-eyed people scenario. That's because it allowed each blue-eyed person to rule out the one-blue-eyed person scenario by observing what happened after the first night. It also allowed each brown-eyed person to confirm the two blue-eyed people scenario after the second night.

The same line of reasoning applies to the three blue-eyed people scenario. Without the outsider's statement, no-one will leave the island. With the outsider's statement the three blue-eyed people can rule out the two blue-eyed people scenario after the second night, deduce that they themselves have blue eyes and leave on the third night.

How do they conclude this? All three blue-eyed people hypothesize that if they themselves have brown eyes, then there are only two blue-eyed people on the island who, in turn, hypothesize that if they themselves have brown eyes, then there is only one blue-eyed person on the island. That hypothesized single blue-eyed person will deduce that he has blue eyes and leave on the first night as a result of the outsider's statement. But if no-one leaves on the first night, then that falsifies the hypothesized two blue-eyed people's hypothesis, so they would leave on the second night. But if no-one leaves on the second night, that falsifies the hypothesis of the three blue-eyed people, so they will all leave on the third night.

Conversely, the brown-eyed people will observe the three blue-eyed people leave on the third night and deduce that they themselves have brown eyes. The same style of reasoning applies to the 100 blue-eyed people scenario, with the blue-eyed people leaving on the 100th night and the remaining islanders deducing that they themselves have brown eyes.

So the outsider's statement did enable everyone to deduce their eye colors. But what new and useful information did it convey? In the single blue-eyed person scenario, it informed the blue-eyed person that someone had blue eyes. In the two blue-eyed people scenario, it informed the two blue-eyed people that the other blue-eyed person knew that someone had blue eyes. In the three blue-eyed people scenario, it informed the three blue-eyed people that the other blue-eyed people knew that the other blue-eyed people knew that someone had blue eyes. And so on.

In other words, the information that at least one person had blue eyes had become common knowledge. This meant that they all knew it, they all knew that they knew it, they all knew that they all knew that they knew it, and so on ad infinitum.

Another way to think about this puzzle is that the blue-eyed people know that they are either in a 99 or a 100 blue-eyed people scenario, but they don't know which one. Whereas the brown-eyed people know that they are either in a 100 or a 101 blue-eyed people scenario, but they also don't know which one. So the blue-eyed people will wait to see if the other blue-eyed people leave the island on the 99th night. If they do not leave, then the blue-eyed people deduce that they are in the 100 blue-eyed people scenario, and leave on the 100th night. The brown-eyed people observe the blue-eyed people leave the island on the 100th night, deduce that they are in the 100 blue-eyed people scenario, and thus know that they themselves have brown eyes. But remember that no-one will leave the island without the outsider's statement since her statement is necessary to falsify or confirm each persons' deeply-nested hypothetical about what the others know.

The key to solving this puzzle is to recognize that it has a recursive structure, observe the pattern that emerges with the simpler scenarios, and then apply that pattern to the more complex 100 blue-eyed people scenario. It's like the pattern that emerges when solving the factorial of four (or 4!). 4! = 4 * 3!, 3! = 3 * 2!, 2! = 2 * 1!, 1! = 1. Once the base case of 1! is solved, and the factorial pattern is understood, it's then easy to solve for higher-numbered factorials.

For some other expositions of the blue eyes puzzle, see xkcd and Terence Tao.

[Added Sep 24]
Bonus question: In a different version of the puzzle, the outsider comes back the day after making her public announcement, calls together all the people on the island, and makes a new public announcement:

"I'm terribly sorry, but I retract my statement from yesterday. I had a migraine that caused me to not see colors correctly so I don't actually know that I saw someone with blue eyes."

What effect (if any) will the outsider's new statement have?

The Blue Eyes Puzzle (Part 1)

I came across a fascinating logic puzzle that goes like this:

On an island, there are 100 people who have blue eyes and 100 people who have brown eyes. No-one on the island knows their own eye color. By rule, if a person on the island ever discovers they have blue eyes, that person must leave the island that night. On the island, each person knows every other person's eye color, there are no reflective surfaces, and there is no discussion of eye color. Also it is public knowledge that the islanders are perfect logicians - if a conclusion can be deduced then they will immediately do so.

One day, an outsider comes to the island, calls together all the people on the island, and makes the following public announcement:

"I can see someone with blue eyes."

Who leaves the island and on what night do they leave?

If you haven't seen this puzzle before, I encourage you to think about it before continuing.

...

All done?

Is your answer that no-one will leave the island? If so then I'm sorry to say that you are incorrect! Despite the fact that all the islanders can see many blue-eyed people, the outsider's statement does convey new information to the islanders and that information enables them to determine the color of their own eyes.

I will give the actual answer and explanation in a few days time. In the meantime, here is a suggestion to help you find the correct solution.

First try to solve a much simpler version of the puzzle. The simplest version is the scenario where there is one blue-eyed person and one brown-eyed person. Consider what the islanders can deduce before the outsider arrives. Then consider what they can deduce after the outsider makes his statement.

Now solve the next simplest version where there are two blue-eyed people and two brown-eyed people. Again consider what the islanders can deduce both before and after the outsider makes his statement. This will help you notice what the islanders learned from the outsider's statement and how it is necessary for solving the subsequent versions with three blue-eyed people and so on.

[Added Sep 22: The Blue Eyes Puzzle solution]