Blue-Eye Paradox: Solution Not Unique

[Demystifier]

What is the deeper message of all this?

After a rather convoluted roundabout argument (which I don't want to reproduce here) I have finally found a way to convince myself that the standard solution is OK, and that my alternative solution is not. I guess it answers some of the most recent questions addressed to me.

But my philosophic mind is not satisfied with this. I want some deeper message to be extracted from this logical riddle. So is there a deeper or more general conclusion that can be inferred from the solution of the blue-eyes puzzle? For instance, has this puzzle been used to illustrate some more general result of mathematical logic? Something like Godel theorems illustrated by the puzzling sentence "This sentence cannot be proved."?

I don't know about any general theorem of that kind, but let me explain what philosophical message I have been extracted from it.

When I see a new conceptual problem, usually my first reaction is to try to solve it intuitively, at once, without using any formal argument. Often such an approach doesn't work.

In the next step I study a more detailed and technical solution of the problem, and after that, in hindsight, I try to modify my intuition to make me see the solution even without the detailed technical procedure. When I succeed in that, then I feel that I learned something deep. Often this approach works for me.

But sometimes even this doesn't work. Sometimes I cannot intuitively comprehend the solution even after I see the formal technical one. For instance, I cannot see intuitively that some simple dynamical equation has chaotic solutions, even after seeing that at a technical formal level.

Well, the blue-eyes puzzle is of that last kind, at least for me. At the intuitive level, I want to see what new message is conveyed by the prophet. But to answer that question, it seems unavoidable to use statements of the form: "I know that you know that he knows that you know ..." And no matter how hard I try, such sentences are intuitively incomprehensible to me. I can find a way to deal with them formally, but my intuition fails. And this is what makes me frustrated. (And what made me doubtful about the standard solution.)

So this is the deeper philosophical message I take from it. The solutions of some problems are too complex for intuitive understanding. In some cases, the only way to understand the solution is by following the formal technical procedure. One has to accept it and live with it. Accepting this makes me less frustrated.

 

[maline]

But to answer that question, it seems unavoidable to use statements of the form: "I know that you know that he knows that you know ..." And no matter how hard I try, such sentences are intuitively incomprehensible to me.

Perhaps this may help:The Kiss
By Coventry Patmore (1823–1896)

‘I SAW you take his kiss!’ ‘’Tis true.’
‘O modesty!’ ‘’Twas strictly kept:
He thought me asleep—at least, I knew
He thought I thought he thought I slept.’

 

[Andreas C]

So this is the deeper philosophical message I take from it. The solutions of some problems are too complex for intuitive understanding. In some cases, the only way to understand the solution is by following the formal technical procedure.

No, you CAN intuitively understand it, it's hard, not complex, its difficulty is based on quantity instead of "quality". With 3 monks/islanders, it's very easy to understand. When you add more persons, you just add more steps. Finding what the 8940198th powers of the 3rd, 1928th, 5904508139th and 99999929893895821st digits of $2^{12345678901234567890}$ without the aid of a computer is hard. Really hard. Is it complex? No. It's just a bunch of arithmetics. Proving Fermat's theorem is extremely hard, because it's actually complex, it's not a bunch of complications one on top of the other.

 

[.Scott]

Well, the blue-eyes puzzle is of that last kind, at least for me. At the intuitive level, I want to see what new message is conveyed by the prophet. But to answer that question, it seems unavoidable to use statements of the form: "I know that you know that he knows that you know ..." And no matter how hard I try, such sentences are intuitively incomprehensible to me. I can find a way to deal with them formally, but my intuition fails.

Those "I know that you know that he knows that you know ..." statements were just distractions. It's more a case of "I might think that someone else might think that someone else might think ...". I thought StevenDaryl's post 144 makes it clear. Also, why bother with those statements when the much simpler sequence of "Day 1 the guru says there is at least 1 blue-eyed. No suicide on day 2 demonstrates to everyone that there are at least 2. No suicide on day 3 ..."? It's like the bird that flies between two oncoming trains: you can solve for it's total flying distance with an infinite series, or you can just calculate how long it will be before the trains collide. Do it the simple way.

This puzzle has modified my "intuition" by making me more careful in describing what might be new information in a public declaration with content that apparently everyone already knows and to be more on the alert to situations that can create "domino" logic.

 

[Demystifier]

No, you CAN intuitively understand it, it's hard, not complex, its difficulty is based on quantity instead of "quality". With 3 monks/islanders, it's very easy to understand. When you add more persons, you just add more steps. Finding what the 8940198th powers of the 3rd, 1928th, 5904508139th and 99999929893895821st digits of $2^{12345678901234567890}$ without the aid of a computer is hard. Really hard. Is it complex? No. It's just a bunch of arithmetics. Proving Fermat's theorem is extremely hard, because it's actually complex, it's not a bunch of complications one on top of the other.

You have the point, the word "complex" is not the best word to describe some kinds of hardness.

 

[Demystifier]

Those "I know that you know that he knows that you know ..." statements were just distractions. It's more a case of "I might think that someone else might think that someone else might think ...". I thought StevenDaryl's post 144 makes it clear. Also, why bother with those statements when the much simpler sequence of "Day 1 the guru says there is at least 1 blue-eyed. No suicide on day 2 demonstrates to everyone that there are at least 2. No suicide on day 3 ..."? It's like the bird that flies between two oncoming trains: you can solve for it's total flying distance with an infinite series, or you can just calculate how long it will be before the trains collide. Do it the simple way.

This puzzle has modified my "intuition" by making me more careful in describing what might be new information in a public declaration with content that apparently everyone already knows and to be more on the alert to situations that can create "domino" logic.

I agree, it's technically simpler not to think about the information content of the prophet's public statement, but to concentrate on the day-by-day analysis. But my point (and my philosophic problem) is that it is not intuitive to ignore the information content.

 

[stevendaryl]

Also, why bother with those statements when the much simpler sequence of "Day 1 the guru says there is at least 1 blue-eyed. No suicide on day 2 demonstrates to everyone that there are at least 2. No suicide on day 3 ..."?

Right. You can prove by induction that "no suicide on day n demonstrates to everyone that there are at least n people with blue eyes". That doesn't seem to involve "Alice knows that Bob knows that Carol knows that ..." But they have to be equivalent, I would think. So I would think that, implicitly, the reasoning about Day n must involve n levels of "knows that".

 

[maline]

Also, why bother with those statements when the much simpler sequence of "Day 1 the guru says there is at least 1 blue-eyed. No suicide on day 2 demonstrates to everyone that there are at least 2. No suicide on day 3 ..."?

That would not clarify the central point: that "demonstrating to everyone" - i.e. common knowledge- is different from "everyone knowing".

 

[andrewkirk]

I believe I may have managed to construct a formal, non-infinitely recursive, statement and proof of the problem, without the use of indeterminate terms like 'perfect logician', or the need for modal logic. I would be very appreciative of any comments anybody can offer. The statement and proof is too long to post here, so instead I have saved it as a pdf where it is accessible on this link. The latex version is saved here, in case anybody wants to use some of that in commenting.

What I have actually proved (E&OE) is that if there are n blues then they all leave/suicide no later than the nth day (which I have numbered as day n-1 because things can be expressed more concisely in symbolic logic if you start counting at 0). I don't think anybody (maybe not even Terence Tao, at least, as far as I can see) has yet proven the other part, which is that nobody leaves/suicides before that day. I think that is a much harder thing to prove, because it effectively involves proving that the proposition 'I am blue' is undecidable in the theories available to the blues prior to day n-1. And we all know how difficult proving undecidability is! I have an idea about how such a proof might go, and will play around with it to see where it goes, but I am not terribly optimistic.

I was surprised to find that, in the end, it was possible to axiomatise the problem without getting into any complex 'A knows that B knows that C knows that ...' jargon, nor was it necessary to invoke the infinitely recursive concept of 'common knowledge'. It seems to be possible to axiomatise it with about a dozen axioms, most of which are obvious, basic arithmetic, common-sense facts about the world, or prescribed rules of the island's society. These axioms are arranged in two series of nested logical theories in an 'object' language L0, with the theories in a sequence corresponding to days on the island. One series is for propositions that all monks know (Public Knowledge, but not necessarily Common Knowledge). The other is for propositions that individual monks know (which consists of all the facts that all monks know, plus any private knowledge). The only difference between corresponding elements of the two series is what a given monk can see on the given day, and can remember seeing from earlier days. Seeing generates private knowledge, since the monks are not allowed to communicate.

Only one axiom asserts anything about what others know. It is:
$$5:\ \ \ numBlue(d)\geq y+1 \wedge seesBlue(m,d)\leq y\to knowsSelfIsBlue(m,d)$$
Informally, it says that if there are at least $y+1$ blues, and monk $m$ - which may be the monk doing the reasoning or another monk - sees fewer blues than that, then monk $m$ will know that he is blue.

I would be grateful for any comments or suggestions.

 

[Buzz Bloom]

You can prove by induction that "no suicide on day n demonstrates to everyone that there are at least n people with blue eyes".

Hi Steven:

It seems to me that this proof requires some omitted prior common knowledge. Specifically, the required prior common knowledge is the "Everyone knows ... etc." that I presented in post #175. Without that prior knowledge, no blue eyed person can logically deduce they have blue eyes from seeing others with blue eyes.

That prior common knowledge is exactly what the guru's statement produces.

ADDITION
Actually, although the guru's announcement does provide the common knowledge I describe in post #175, a more limited common knowledge than that would be sufficient for the proof to be valid.

Let P(X) represent: "Everyone with blue eyes knows X."
Let Y represent: "There is at least one person on the island with blue eyes."
Let P₁ = P(Y)
Let P_k = P(P_k-1)
Then the required common knowledge if there are N persons with blue eyes is:
P₁ & P₂ & . . . & P_N

Regards,
Buzz

 

[.Scott]

Right. You can prove by induction that "no suicide on day n demonstrates to everyone that there are at least n people with blue eyes". That doesn't seem to involve "Alice knows that Bob knows that Carol knows that ..." But they have to be equivalent, I would think. So I would think that, implicitly, the reasoning about Day n must involve n levels of "knows that".

You can't demonstrate it with "Alice knows that Bob knows..." because that is the wrong line. You can demonstrate it with something more like Alice can't be sure that Bob can be sure that Carol can be sure that there are no blue-eyed monks.
But if you want the whole thing you need your post 144 or my post 165.

 

[.Scott]

That would not clarify the central point: that "demonstrating to everyone" - i.e. common knowledge- is different from "everyone knowing".

I'm not sure what the point of the "demonstrating to everyone" vs. "everyone knows" debate is.

The key point is that the guru makes an announcement that eliminates the possibility that no one is blue-eyed ($\overline{T_0}$), that all the blue-eyed monks get this message, and that all the blue-eyed monks know that all the blue-eyed monks got the message. If there are other semantics that do not unambiguously denote the situation as either compliant or non-compliant to those conditions, then don't use those semantics.

 

[.Scott]

I don't think anybody (maybe not even Terence Tao, at least, as far as I can see) has yet proven the other part, which is that nobody leaves/suicides before that day.

Someone may leave/suicide before that day. The issue isn't to prove that it doesn't happen, but to specify the conditions under which it cannot happen.
If we change the problem by stipulating this sequence on day 0, then we can demonstrate that there is no information available to any blue-eyed monk that can lead to him proving that he is not blue-eyed:
1) The memories of all monks are erased.
2) All monks are given the rules.
3) All monks are introduced to each other.
4) All monks are told that all monks have gone through this same induction process.

So far, no information has been provided to any monk about their own eye color.

Since monks are not allowed to communicate anything about eye color, that source of information is not available.
The lack of suicides/departures dos not communicate anything. This was the exception before. Although the monks were not allowed to communicate anything about eye-color before, the act of suicide or departure was implicitly exempted. If it had not been exempted, then the monks would have acted differently. For example, if they departed/suicide, they would have arranged to conceal this activity - or conversely, in situations where not departing/suiciding would have tipped off other monks, they would have flipped a coin: heads they hide or simulate suicide, tails they continue as usual.

By the rules, only the guru and rules-following monks know the eye color of other monks. If the guru stays silent, there are no other mechanisms for monks to communicate eye-color, so each monk can never discover his own eye-color.

Which brings us back to this (slightly modified to accommodate DH's remarks in post #171):

Try this one:
Suicides opportunities are only at midnights.

Given that all monks:
1) Recognize all other monk on the island that they share with them.
2) Always exercise perfect logic.
3) Will commit suicide if and only if they know they are blue-eyed.
4) Always know when a suicide has taken place on their island and who committed suicide.
5) Know that all other monks are like themselves, always logical, always follow the rules, always recognize all other monks, always know when a suicide has taken place on the island they are on.
6) All monks follow the rules and no monk commits suicide unless he knows that his eyes are blue.

You, a perfectly logical monk, arrive on the island on day 100 and see 12 blue-eyed monks (blues). On day 103, the guru makes his declaration. Then on day 104, six blues commit suicide.

If the guru makes no additional announcements, what if any suicide activity will occur?

 

[maline]

he key point is that the guru makes an announcement that eliminates the possibility that no one is blue-eyed (¯¯¯¯¯T0T0¯\overline{T_0}), that all the blue-eyed monks get this message, and that all the blue-eyed monks know that all the blue-eyed monks got the message

But for "eliminating the possibility that no one is blue-eyed" to be meaningful at all, you need to point out that there is someone who doesn't know that someone knows that someone knows etc. that someone has blue eyes.

 

[.Scott]

But for "eliminating the possibility that no one is blue-eyed" to be meaningful at all, you need to point out that there is someone who doesn't know that someone knows that someone knows etc. that someone has blue eyes.

Someone can't be sure that that others can't be sure .. that others can't be sure that there are no blue-eyed monks. Then "everyone knowing that every has new information on the same day that there is a blue-eyed monk" becomes consequential.

 

[maline]

Someone can't be sure that that others can't be sure .. that others can't be sure that there are no blue-eyed monks. Then "everyone knowing that every has new information on the same day that there is a blue-eyed monk" becomes consequential.

Okay, so we're all saying the same thing.

 

[maline]

Only one axiom asserts anything about what others know. It is:

5: numBlue(d)≥y+1∧seesBlue(m,d)≤y→knowsSelfIsBlue(m,d)5: numBlue(d)≥y+1∧seesBlue(m,d)≤y→knowsSelfIsBlue(m,d)​

5:\ \ \ numBlue(d)\geq y+1 \wedge seesBlue(m,d)\leq y\to knowsSelfIsBlue(m,d)
Informally, it says that if there are at least y+1y+1y+1 blues, and monk mmm - which may be the monk doing the reasoning or another monk - sees fewer blues than that, then monk mmm will know that he is blue.

I don't think this is correct. You need monk m to know that "numBlue(d)≥y+1".

I don't think anybody (maybe not even Terence Tao, at least, as far as I can see) has yet proven the other part, which is that nobody leaves/suicides before that day. I think that is a much harder thing to prove, because it effectively involves proving that the proposition 'I am blue' is undecidable in the theories available to the blues prior to day n-1. And we all know how difficult proving undecidability is!

What is hard about undecidability? All you need to do is demonstrate two "models"- scenarios as to who is in fact blue, and how people react, satisfying all the axioms- one in which monk m is blue, and one in which he is not, while in both, no one leaves up until day n-3. Then on day n-2, monk m will be unable to differentiate between these models, and so cannot conclude he is blue. Similar models exist for each monk, so no one leaves until day n-1.

 

[stevendaryl]

 

[andrewkirk]

I don't think this is correct. You need monk m to know that "numBlue(d)≥y+1".

If the antecedent $numBlue(d)\geq y+1$ is a theorem of the theory we are working in ($T(0,k)$) then all monks know it, including monk m, because that theory represents what all monks know on day $k$.
Alternatively, if it is not a theorem, the entailment is satisfied because the antecedent is denied.

What is hard about undecidability? All you need to do is demonstrate two "models"- scenarios as to who is in fact blue, and how people react, satisfying all the axioms- one in which monk m is blue, and one in which he is not, while in both, no one leaves up until day n-3. Then on day n-2, monk m will be unable to differentiate between these models, and so cannot conclude he is blue. Similar models exist for each monk, so no one leaves until day n-1.

I considered that possibility before posting, and couldn't see a way to make it rigorous - although that could just be because I haven't done much model theory. We need to prove that the monk is unable to differentiate between possible models. To me that sounds equivalent to our proving (within our meta-language L and meta-theory T2) that monk m cannot prove from within $T(1,n-2,m)$ in L0 that $numBlue(n-2)>n-2$, in other words that the proposition $numBlue(n-2)>n-2$ is undecidable in $T(1,n-2,m)$.
Can you think of a rigorous way to prove that the monk is unable to differentiate? It seems blindingly obvious to me that he cannot differentiate. But seeming obvious is one thing and proof is another.

 

[.Scott]

Can you think of a rigorous way to prove that the monk is unable to differentiate? It seems blindingly obvious to me that he cannot differentiate. But seeming obvious is one thing and proof is another.

Didn't I do that at the start of post #188? Do I need to make it more detailed?

 

[maline]

Alternatively, if it is not a theorem of the entailment is satisfied because the antecedent is denied.

No, for the antecedent to be denied you need the negation of the entailment to be a theorem.

In English: The number of blues was n from day zero, but no one left because the statement about the number of blues was not yet a known fact. So your condition needs to be "If 'numBlue(d)≥y+1' is a theorem of T(1,d,m)" (The knowledge of monk m on day d). Of course that forces you to use a language and system that allow such determinations to be made internally, by the monks- they are thinking about what each other are thinking.

 

[maline]

Can you think of a rigorous way to prove that the monk is unable to differentiate? It seems blindingly obvious to me that he cannot differentiate. But seeming obvious is one thing and proof is another.

Again, all you have to do is show that both situations are consistent with the axioms. For any finite n you can just list off what each monk sees and knows. I'm not sure how to do it for the pronumeral case, but it doesn't seem difficult...

 

[andrewkirk]

Didn't I do that at the start of post #188? Do I need to make it more detailed?

It is possible that what you have outlined there may be able to be turned into a proof, but we cannot be certain unless/until that is done. For instance it relies on a concept of 'information', which is not formally defined and about which we have no axioms.

No, for the antecedent to be denied you need the negation of the entailment to be a theorem.

I think you may have something there. I will need to reflect on that. If the objection holds then, as you say it may push us towards having to axiomatise by adding another level of language. When I started drafting the note, my initial idea was to not only have nested theories in sequences indexed by day, but matching nested languages too, with each language able to refer to what is provable in earlier languages. That would allow us to formally define the conditions of each monk on day d reasoning about what other monks know on day d-1, without running into the problem of a circular definition that prompted me to try axiomatising the problem. And fortunately, monks only need to know what the others know on previous days in order to reach the correct conclusions. They don't need to know anything about what the others know today. That sequence of languages would be a bit like the hierarchies of set-like objects that Russell used to avoid his own paradox - before the neater solution of ZF set theory was devised.

I then thought of the axiomatisation in my note and thought that would greatly shortcut the machinery of having to have a nested sequence of languages. But if you are right, it is an illegal shortcut so it'll be back to the nested language sequence to get a non-circular axiomatisation. I could probably manage the axiomatisation but I fear that then even semi-formally proving the result in the new, much larger, system would be beyond what my 21st century concentration span can cope with.

Again, all you have to do is show that both situations are consistent with the axioms.

What I am unsure of here is how we can show that. It seems to me that what we need to prove is relative consistency - ie that, assuming the system is consistent to start with, it remains consistent if we add an axiom that says nobody leaves before day n-1 (relative, because otherwise we would need to start by proving the consistency of arithmetic, which may be an easy task for Gentzen, but not for me). I have been unable to convince myself that going through and showing that all axioms are satisfied by a model with n-1 blues is sufficient. How can I be sure that there won't be some obscure combination of the expanded set of axioms into a deduction that proves a contradiction, which cannot be proved in the original axiom set?

 

[maline]

my initial idea was to not only have nested theories in sequences indexed by day, but matching nested languages too, with each language able to refer to what is provable in earlier languages. That would allow us to formally define the conditions of each monk on day d reasoning about what other monks know on day d-1, without running into the problem of a circular definition that prompted me to try axiomatising the problem. And fortunately, monks only need to know what the others know on previous days in order to reach the correct conclusions. They don't need to know anything about what the others know today.

I like this solution; it is much more elegant than a recursion on the monks, and show clearly how the system is finite and self- contained. Of course, you still need the theories to be indexed by "monk" as well, because the monks have different values for "SeesBlue" depending on their own colors.

I am still curious what a formalization of the full infinitely-recursive idea of "common knowledge" looks like. I do believe it's possible.

I have been unable to convince myself that going through and showing that all axioms are satisfied by a model with n-1 blues is sufficient. How can I be sure that there won't be some obscure combination of the expanded set of axioms into a deduction that proves a contradiction, which cannot be proved in the original axiom set?

I'm not an expert here, but this is how I understand it: You build a model by explicitly defining all the constants, functions etc. of your language using terms from the basic underlying system- Robinson Arithmetic in our case. Then all wff's of your language have a defined truth value. The model consists of all the true wff's in this construction, and it is actually a subtheory of Robinson Arithmetic. Then its consistency is guaranteed by the consistency of the arithmetic (which we assume), so if you can show that the axioms you want are true wff's of the model, you have proven that they are consistent. If another such model includes the negation of one of the axioms, then you have proven that this axiom in independent of the others and undecidable in terms of them.

 

[Buzz Bloom]

Again, all you have to do is show that both situations are consistent with the axioms. For any finite n you can just list off what each monk sees and knows.

Hi Maline:

It is unnecessary to consider all monks. It is sufficient to consider only blue eyed monks. If there are N blue eyed monks, then they each of them will see N-1 blue eyed monks. Until the guru tells all of them that there is at least one blue eyed monk, each blue eyed monk, say M, knows that there are two possibilities. M knows that If M has blue eyes, then there are at N blue eyed monks, and that if M's eyes are not blue, then that there are N-1 blue eyed monks. M does not know and cannot deduce that he has blue eyes even after N or more days have passed with no actions taken by the the blue eyed monks that M can see have blue eyes.

After the guru announces to all N blue monks there is at least one blue eyed monk, each blue eyed monk, say M, can deduce that:
If M does not have blue eyes, then all of the N-1 blue eyed monks that M can see will know they all have blue eyes after N-1 days, and that they will all take appropriate action then. If they do not take that appropriate action, M will deduce that he has blue eyes at that point.

Regards,
Buzz

 

[andrewkirk]

I am still curious what a formalization of the full infinitely-recursive idea of "common knowledge" looks like. I do believe it's possible.

Here's my attempt, with latex code here. I'm afraid it's a bit of a monster so I won't post it directly here. The basic idea is to first define a finite recursive knowledge function $FRK$ that takes a finite sequence $l=(l_1,l_2,...,l_r)$ of integers and a proposition $F$ and returns a formula in a suitable language that says something to the effect of

nun $l_1$ can prove that nun $l_2$ can prove that ... nun $r-1$ can prove that nun $r$ can prove $F$

I changed the monks to nuns in the interests of sexual equality.

Then we define common knowledge to mean something a bit like

$F$ is common knowledge iff
$$\forall l\in \mathbb N^*:\ FRK(l,F)$$
There's a bit of fiddling with language conversion that means that last step is not exactly like that, but that's the general idea.

Most of the work is in formally constructing an infinite sequence of languages in which each one can talk about the one below it, and a set of axioms for each nun at each level of the language tower.

I think it's right. But my brain hurts now, so I may have made some silly mistakes and not noticed them.

Comments very welcome.

 

[Buzz Bloom]

Somehow I get the impression from reading through this thread that the basic issue of the "paradox" has become misplaced.
Below is the "paradox" statement from

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

On an island, there are k people who have blue eyes, and the rest of the people have green eyes. At the start of the puzzle, no one on the island ever 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 at dawn; anyone not making such a discovery always sleeps until after dawn. 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.

At some point, an outsider comes to the island, calls together all the people on the island, and makes the following public announcement: "At least one of you has blue eyes". The outsider, furthermore, is known by all to be truthful, and all know that all know this, and so on: it is common knowledge that he is truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes. The problem: assuming all persons on the island are completely logical and that this too is common knowledge, what is the eventual outcome?
​

The paradox is: Why does the statement by the outsider change anything since everyone on the island already knows the truth of what the stranger said before the stranger arrived. That is, everyone knows that: There is at least one blue eyed person on the island.

What the stranger changed is that the following which was not previously known has also become known by everyone from the stranger's statement.

A. IF exactly one person on the island has blue eyes, THEN that person will know the s/he has blue eyes.
​

The following conditional everyone already also previously knew.

B. IF there were exactly k persons on the island with blue eyes, AND on day, say D, they all came to know that they had blue eyes, THEN
IF there were exactly k+1 persons on the island with blue eyes, THEN on day D+1 they will all come to know that they had blue eyes.
​

From these two propositions, and the fact that the behavior of a blue eyed person who know s/he has blue eyes becomes known to others, the following is also known (by induction) by all blue eyed persons.

C. IF there are exactly k persons on the island with blue eyes, THEN on k-1 days after A becomes known, all k of these persons will come to know that they have blue eyes.​

If the stranger did not make A known, then C would also not be known.

Now, there is also a small logical oddity worth mentioning.

A has the form: IF X THEN Y. X and Y are the underlined statements. If it is assumed (everyone knows that) k>1, then X is FALSE. Therefore, (everyone knows that) A is TRUE before the visitor makes his announcement!

Can anyone spot the logical flaw here?

Regards,
Buzz

 

[maline]

Wow, this is truly heroic! Yes, I think this works, although I didn't follow every detail. It can probably be simplified a bit, but not in a significant way. Now we have a general framework for formalizing all problems involving groups of perfect logicians, using nothing but First Order Predicate Logic. As a matter of fact, you have thus defined the term "perfect logicians", answering @Demystifier's original query.

I note a couple of assumptions you did not make:
1. You did not postulate that the axioms available to various nuns at a given level of iteration should be consistent with one another. Thus according to one nun, other nuns can "know" things wrongly, despite their perfection as logicians.
2. There is no axiom that a nun knows what it is that she herself knows one level down. In fact each "level" might as well be a different person! There are some situations in reality that correspond to this: Some people are under the impression that they think the Bible is divine, when in fact they don't really believe that at all...
Not making these assumptions adds generality, but the user will have to make such things explicit in the problem statement.

 

[Buzz Bloom]

Hi maline:

Thank you for your response to my last post.

I am a bit puzzled by your two assumptions.
I think by "axioms" you mean "logical conclusions".
1. Can you give an example of what you have in mind about what might be an axiom/conclusion "available" to one nun that might be inconsistent with an axiom/conclusion "available" to another nun at "a given level of iteration"?
2. Can you give an example of a what a nun might know (or not know) one level down from something she knows at a given level?

Do you h ae any thoughts about the "logical flaw" I mentioned at the end of my previous post?

BTW: I am working on the text for a new puzzle related to the discussion of this thread. I hope to post the puzzle in a new thread in a day or so.

Regards,
Buzz

 

[andrewkirk]

I have completed a moderately formal proof of the proposition that, if there are n blues and nobody leaves in the first n-1 days, all blues will leave on the nth day. It uses the day-indexed sequences of languages and theories discussed above. Here's the proof and here's the latex code.

My earlier proof was flawed, as pointed out by Maline. It turns out we do need to use more than one level of 'knows that...'. We don't need the unlimited number of levels that is implied by the concept of Common Knowledge though. We only need as many levels as there are blue nuns.

On day n-1, the day they all leave, each blue has worked out she is blue because she knows what axioms the other nuns have on previous days, and that on those days they deduced from those everything that is deducible, and she also knows that:

..on day n-2 nobody left and everybody knew that: (
... on day n-3 nobody left and everybody knew that: (
... on day n-4 nobody left and everybody knew that: (
...
... on day 1 nobody left and everybody knew that: (
... on day 0 nobody left and everybody knew that there was at least one blue) ... ) ) )

There are no circular references, because nuns only ever reason about what others knew the previous day, not about what they know today. Each day's logical language is a meta-language of that of the day before, thereby avoiding circularity. We conduct our own reasoning, which includes a proof by mathematical induction, in a language that is meta to all the infinite sequence of languages, and hence can refer to them all.

I won't post the proof here, because it's eleven pages long and the latex would slow down the page rendering here too much. BUt here are the axioms I use:
The axioms of $T0_0$ are the axioms of Robinson Arithmetic and ZF set theory, plus the following scenario-specific axioms:
\begin{align}
&numBlue(0)\geq 1\\&
numLeave(d)=0\to (\forall m:\ \neg leaves(m,d))\\&
knowsSelfIsBlue(m,d)\wedge (\forall d'\leq d-1:\ \neg leaves(m,d'))\leftrightarrow leaves(m,d)\\&
knownMinBlue(d)\geq y+1 \wedge seesBlue(m,d)\leq y\to knowsSelfIsBlue(m,d)\\&
isBlue(0)\vee isBlue(1)\\&
isBlue(m)\wedge seesBlue(m,d)\geq y\to numBlue(d)\geq y+1\\&
numBlue(d+1)= numBlue(d)-numLeave(d)
\end{align}
(where $(\forall x\leq a:\ F)$ is shorthand for $(\forall x:\ x\leq a\to F)$ )
plus the following axiom schema that has one instance for each wff $\theta$ in $L$ with one free variable:

$$(\forall d'\leq d-1:\theta(d'))\wedge \theta(d)\to(\forall d'\leq d:\ \theta(d'))$$

where $\theta(t)$ denotes the formula generated by replacing the free variable by $t$ in $\theta$.

For $d\leq n-2$, the axioms of $T0_{d+1}$ are those of $T0_{d}$, plus two extra axioms
\begin{align}
&d'\leq d\to numLeave(d')=0\\
&\phi(y)\to knownMinBlue(d)\geq y
\end{align}

Note that, since $L_d\subset L_{d+1}$ and $T0_d\subset T0_{d+1}$, any wff of $L_d$ that is a theorem of $T0_d$ will also be a wff of $L_{d+1}$ and a theorem of $T0_{d+1}$. We can write this in the meta-meta-language $L^\ddagger$ as:
$$(T0_d\vdash_{L_d} \theta)\to (T0_{d+1}\vdash_{L_{d+1}} \theta)$$

Finally, we also use a private knowledge axiom in $T1_d^m$, which states the number of blues that nun $m$ sees at 1pm on day $d$.

Comments, suggestions, questions and criticisms are very welcome.

 

[bahamagreen]

I think there is a problem with the puzzle right here:

"...each person knows every other person's eye color...and there is no discussion of eye color."

Each person's individual knowledge of other's eye color is based on never having been allowed to discuss eye color, so all they know is that they have observed two eye colors and any individual they observe may be classed as one or the other.

They know the rule is that those of one of these eye colors must leave the island when they discover that particular color is their own, but this has never happened... nobody with that particular eye color subject to the rule has ever left the island to indicate to the others which color it is that must leave.

So there is a perfectly good reason why nobody has left the island - not only do individuals not know which color their own eyes are, they don't even know which of the two colors of eyes they see around them is the color that is subject to the rule!

The oracle's canonical statement is not sufficient to initiate the logic process... her referral to the eye color subject to the rule does not distinguish and indicate to which of the two eye colors the islanders see around them. It does not matter if objectively the number of blue eyed people is 0, 1, 2, 3..., without knowing which eye color is the one subject to the rule to which she refers, they have nothing with which to begin figuring it out.

In order for things to change, the role of the oracle must be to finally indicate or demonstrate which of the two colors is the one subject to the rule... THAT is the necessary information turning point (starting clock) from which the islander's subsequent calculations and actions depend.

 

[tzimie]

I think there is a problem with the puzzle right here:

"...each person knows every other person's eye color...and there is no discussion of eye color."

Each person's individual knowledge of other's eye color is based on never having been allowed to discuss eye color, so all they know is that they have observed two eye colors and any individual they observe may be classed as one or the other.

Not true.
They could have mass suicides in the past, so they have developed a "taboo" on such discussions no matter if they see blue eyes or not.

 

[bahamagreen]

What is not true?

Your second sentence is unclear... I can't determine what it is you are disputing.

 

[tzimie]

What is not true?

Your second sentence is unclear... I can't what it is you are disputing.

There are 2 possible reasons why people on that island don't discuss eye color:
1. They see others with blue eyes, but they don't want to provoke mass suicides, so they don't discuss eye color.
2. There were similar events (mass suicides) in the history of the island, and assuming that blue eyes could be a recessive gene and new babies could be born with blue eyes people don't discuss eye color to prevent suicides in the future, even they don't see any people with blue eyes NOW in the current population.
3 both

So from "people avoid discussions about eye color" you can't deduce "there are some people with blue eyes".

So the following quote is not true:
Each person's individual knowledge of other's eye color is based on never having been allowed to discuss eye color, so all they know is that they have observed two eye colors and any individual they observe may be classed as one or the other

 

[Buzz Bloom]

I have completed a moderately formal proof of the proposition that, if there are n blues and nobody leaves in the first n-1 days, all blues will leave on the nth day.

Comments, suggestions, questions and criticisms are very welcome.

Hi andrewkirk:

I have some interest in commenting on your "proof", but I am unable to digest the meaning of your notational expressions. There seem to be possible ambiguities. For example:

numBlue(0) ≥ 1​

What does the "0" represent?
Does the notation mean that
(a) there are more than one blue eyed person on the island, OR
(b) the guru sees that there are more than one blue eyed person on the island, OR
(c) everyone knows that at there are more than one blue eyed person on the island?

I suggest that for each formal statement you supply the English meaning you intend.

I note that your proof seems to involve statements about the knowledge of individuals. It may be possible to make a proof from that perspective, but I am pretty sure it is unnecessary to consider the knowledge of any individual. That is, a formal proof can be made based on what everyone (as a member of a class) who have a particular eye color sees and knows, and when they know it. Also, I am pretty sure it is sufficient to consider only what the (members of the class of) blue eyed "nuns" see and know.

Regards,
Buzz