Talk:Common knowledge (logic)

The blue eyes people on the island example

While whole proof seems very logical it ignores time of information arrival . At k=1 we assume that blue eyed person knows that there is at least one blue eyed. But this information is available only at time N>1(N is the number of blue eyed people). We allow our "perfect" recursive algoritm to imply knowledge from the present while we are backtesting it in the past. In mathematics this is called information filtration and proof simply ignores filtration. — Preceding unsigned comment added by 12.20.30.133 (talk) 16:00, 14 February 2013 (UTC)

The "textbook example" is largely an opportunity for showing off: it does not actually illuminate what is meant by common knowledge. The evolution of what is considered "common knowledge" within a society is not approached yet. Why are no vehicles of "common knowledge" mentioned? Is there no relation to proverbs for instance? A few links to the rest of Wikipedia might make this exercise appear less self-indulgent. --Wetman 22:11, 24 Jan 2005 (UTC)

The "textbook example" is not self-indulgence. That example is the one example I had to demonstrate why common knowledge is different from "general knowledge" to n-ply, with arbitrarily large n. I'm not a logician, nor an expert on this matter, and I bring forth what little knowledge I have in the hopes of contributing as best I can.

This article was intended as one on the precise "common knowledge" of modal logic (and possibly its applications to real human systems) not the informally defined "common knowledge" of proverbs, oral traditions, etc. EventHorizon talk 23:03, 24 Jan 2005 (UTC)

Where's the article defining "Common knowledge", that is, the stuff that most people know? I.E. "IT is common knowledge that the U.S. Declaration of Independence was signed in 1776." --Locarno 16:10, 3 March 2006 (UTC)

Perhaps this paper should have been called the logic of common knowledge. Pierre de Lyon 02:42, 21 March 2006 (UTC)

Moved to "Common knowledge (logic)". -- Beland 05:28, 7 May 2006 (UTC)

Is the example even correct for K>3? Isn't it common knowledge from the start that there are at least K-2 people with blue eyes? 124.176.51.232 (talk) 09:31, 3 February 2008 (UTC)

Each new day that no-one leaves adds to the knowledge of the number of blue eyed people. After day 1, everyone knows that there are at least 2 blue-eyed people. After day 2, everyone knows that there are at least 3 blue-eyed people. 216.17.5.44 (talk) 21:04, 12 February 2008 (UTC)

I know nothing of the concept of "common knowledge" that is being explained here, but to me at least, the example is flawed. For n>1, there is no knowledge introduced by the outsider's pronouncement of the existence of blue eyes. That only adds something for the trivial case of n=1 - it is simply a device to assist the induction proof. For n>1, there is the new knowledge introduced by the passing of each day. The blue-eyed people would leave n days *after they got there*. 216.17.5.44 (talk) 21:39, 12 February 2008 (UTC)

I don't think the validity of the example is in dispute. It's a well-known puzzle. But as a response to your statement, an announcement is absolutely required in this problem. When the islanders arrived, for the n=1 case the blue-eyed person would have no evidence as to the existence of blue-eyed people, and would not leave. For the n=2 case, each blue-eyed islander would not expect a single blue-eyed islander to know that blue-eyed islanders existed, and would therefore not deduce his own eye color, etc. This puzzle is tricky to think about correctly, which is why it's interesting. But its trickiness does not make it incorrect. —Preceding unsigned comment added by 58.91.12.178 (talk) 20:21, 16 February 2008 (UTC)

Most of the puzzle's "trickiness" comes from a pointless and baffling redefinition of what it means to be human. For values of n above 3 or perhaps 4, no one will leave the island unless they are extraordinarily good at logic, as evidenced by the fact that laypeople who hear this puzzle never think it's reasonable for anyone to ever leave the island. Replace the people in the puzzle with robots programmed to flawlessly follow all their knowledge to all of its logical conclusions, and you have a good puzzle (and quite correct as outlined in the article). However, as long as we postulate people instead of robots, it's simply wrong. People don't and generally can't act like robots, and it's patently unfair to present a logic puzzle in which the reader has to pretend they do. It makes the puzzle harder, but for the same reasons that describing it in 5th century Japanese would make it harder. Therefore, I say we change the presentation of the puzzle in the article to be about robots, accordingly. If no one disagrees I'll do it in a couple of days. --Ecksemmess (talk) 23:19, 16 February 2008 (UTC)

I believe the puzzle is difficult to understand because it would not seem that the visitor's statement, that there are people on the island with blue eyes, would have any effect when everyone already knows that there are such people for any case n>2. Populations of hyperrational people are very commonly used in problems of this sort, and it doesn't seem that using them here presents any special difficulty. Accepting the existence of hyperrational people would seem to be the easiest part of this puzzle. In any case, the puzzle still has its meaning if you use something other than the everyday hyperrational Joe, like hyperrational aliens, hyperrational robots, or hyperrational professors of logic. So if you feel strongly about the subject of the puzzle, change away. But a more useful task might be a clear explanation of how a statement of something which is already known adds new information to the island. This is not at all easy, but would add quite a bit to the article if someone could find a way to do it.24.57.194.211 (talk) 13:37, 19 February 2008 (UTC)

To be sure, the puzzle is difficult to understand for quite a few reasons. Whether we talk about robots or humans, you're right that the difficulty in seeing what new information the visitor brings is going to throw a lot of people off the mark. I'm working on a good way to elucidate this factor; probably the best explanation involves admitting that the visitor does bring new information, though the new information is specifically that everyone believes that everyone believes that everyone believes (...to the hundredth) that someone has blue eyes. The recursive aspect of this knowledge is the key, and is clearly new with the visitor's proclamation, assuming no one grants the possibility of a lie and assuming the visitor gathers everyone together, of course. However, I still think that for the layperson (rather than the logician or veteran of these puzzles), something should replace the hypothetical "hyper-rational human", which I'm afraid is just too counter-intuitive an entity for even many quite intelligent people to contemplate. (What's worse, the article as is doesn't even mention that the people are hyper-rational, which obviously totally invalidates everything.) I know how annoying it is when someone like me complains and complains instead of going and making improvements, so I'm sorry about that. I'll do what I can.

No. The original poster, way up at the top, is correct. The "solution" to this problem is incorrect.

I had written a long explanation here, but I've trimmed it down because I can explain it more simply. Obviously as explained in the given "solution", the case n = 1 would be trivial, and the case of n = 2 would be resolved after the first deadline passed and nobody left the island.

But there is a problem. To illustrate: what if we STARTED with n >= 3? The third inhabitant adds another variable, which is different logic from n = 1 and n = 2. Imagine 3 inhabitants looking at each other, and try to solve the problem. I'll leave it as an exercise. Suffice it to say that if you START with 3 or more, the logic no longer works because you have more variables than you have knowns to solve for them. That is WHY the solution that is given to us proceeds serially starting with n = 1 and n = 2, and adds one more at a time.

Why is all this relevant? Because n = 1 and n = 2 are prohibited by the given conditions! Unless there are only 1 or 2 inhabitants on the whole island.

It occurred to me that if the island's population n is >= 3, which is inevitable unless k = 1, the logic of the given solution for n = 1 and n = 2 is invalid because they never happen. Even if two inhabitants are isolated in a corner of the island, and can only see each other, that doesn't matter because there are other inhabitants, elsewhere, any of which could be the one with blue eyes. The deductions given in the "solution" for n = 1 and n = 2 will never arise, for the simple reason that n is never equal to 1 or 2. The chain of logic we are supposed to accept is broken because there is no way to make the initial deductions. The contrived construction of a 'serial' solution is the only way it CAN work, but the given conditions do not allow the series of deductions to begin.

So unless there are only 1 or 2 people on the entire island, the logic for n = 1 and n = 2 is irrelevant. There are always more than 2 inhabitants who must be accounted for. There is always someone else, present or not, who represents another variable, and who could have blue eyes. So unless the population of the entire island is 2 or fewer, n is never 1 or 2. And as explained above n >= 3 has no solution. -- Jane Q. Public (talk) 08:59, 25 April 2016 (UTC)

Oh, and I don't see any trolls here, Pierre de Lyon. --Ecksemmess (talk) 10:12, 22 February 2008 (UTC)

The fact that visitor does bring new info is completely counter-intuitive. Leaving that fact from an article does not help, put it back as a comment/notice or mention that they never thought about that before visitor came to an island. --83.237.2.228 (talk) 22:31, 26 January 2010 (UTC)

"Please do not feed the troll" Pierre de Lyon (talk) 22:03, 19 February 2008 (UTC)

The example is missing some statements which we must assume in order to arrive at the "correct" conclusion. This is misleading because the solution requires that we understand exactly what the islanders themselves can and can't assume.

• "Everyone's adherence to the rules is common knowledge." The solution relies on the islanders all acting logically, and knowing that the others all act logically, etc.
• "...they must leave the island at dawn the next day, otherwise they must stay." If a blue-eyed person can leave the island early, it can lead to the other blue-eyed people not deducing their eye color with certainty. — Preceding unsigned comment added by 209.89.239.183 (talk) 17:21, 20 February 2012 (UTC)

First order logic

Beware of the use first order logic which has a precise meaning in logic. As second order logic and higher order logic, see section Comparison with other logics in article first order logic for a classification. Pierre de Lyon (talk) 21:54, 19 February 2008 (UTC)

New knowledge

For k>1, how would the outsider's statement add anything not already known? 75.118.170.35 (talk) 16:17, 12 August 2009 (UTC)

This puzzle is bogus

This puzzle and its proof are completely bogus.

As no new knowledge was introduced, and everybody could easily infer what was said, it cannot possibly have any effects. Everybody could logically tell that everybody knows that some people have blue eyes, and everybody could already logically tell than everybody knows that everybody knows, and so ad infinitum. This fact is already common knowledge. Taw (talk) 02:38, 22 September 2009 (UTC)

Wrong. If k=2 then not everyone knows that everyone knows that there is a blue eyed.Scineram (talk) 19:49, 13 November 2009 (UTC)

Why not? Can everyone see color? Does everyone look at each other eyes? If people do these things then indeed everyone knows there are blue eyed people and everyone knows they know and so on. If not, then the k=2 case is bogus. When no one leaves, a blue eyed person simply assumes that the other blue eyed person must be colorblind or unobservant and therefore under the impression that there are a bunch of blue eyed people those people have not yet figured out they must go. Thus no one leaves on day 2, or any day for that matter. — Preceding unsigned comment added by 69.242.116.124 (talk) 14:54, 28 December 2011 (UTC)

For purposes of the problem, it is already common knowledge that all of the islanders have correct color vision, pay attention, always count the right numbers of other colors, and always make perfect deductions. If we grant all of these, then it must work for any number. For example, suppose you agree that it works with two, but not three. Then we see that:

• If a (male) islander sees exactly two pairs of blue eyes, then he will know that the total number of blues is either two or three (a simple induction)
• If the total number is exactly two, then the two blues he sees will leave on Day 2 (it doesn't matter what color "our" islander's eyes are, so long as they are not blue; it also makes no difference that we are "in" the problem, since the same event should be observed the same way from all perspectives)
• If no one leaves on Day 2, then the total number must not be exactly two
• Somehow, not one of the blue-eyed people will deduce that the total is three (and thus, that he himself has blue eyes)

The last premise is, of course, flawed. 71.162.46.164 (talk) 17:48, 11 February 2012 (UTC)

See my analysis further up the page. The "solution" is invalid, and this "puzzle" should be removed. -- Jane Q. Public (talk) 07:30, 25 April 2016 (UTC)

The example is correct

Those who are arguing that the example is incorrect are confusing our common knowledge (as observers) and the common knowledge of the participants.

Bot observers and participants know that:

• On an island, there are k people who have blue eyes, and the rest of the people have green eyes.
• If a person ever knows herself to have blue eyes, she must leave the island at dawn the next day.
• Each person can see every other person's eye color, there are no mirrors, and there is no discussion of eye color.

However, we as observers also know:

• There is at least one blue-eyed person on the island (k ≥ 1).

This means that the participants do not know whether , as a logical necessity, there are any blue eyed people on the island. In their common knowledge k could in principle be zero. Now this might seem splitting hairs, but there is a difference between an observation that there are blue eyed people, and a logical requirement that blue eyed people must necessarily exist.

In the case where the number of people on the island is 1, this islander does not know that k ≥ 1, and therefore still holds onto the the possibility that k = 0. In this case, the islander cannot conclude anything. When the external person arrives, the statement k ≥ 1 cvhanges things, and the islander must then leave.

In the case where the number of people on the island is 2, we as observers know that the number of blue eyed people is either 1 or 2. However, for participants, this number could be 0, 1 or 2. The participants will therefore reason as follows:

Suppose A has blue eyes, B has green eyes.

• A sees B, and notes that B has green eyes. Since A does not know whether there are any blue eyed people on the island, A concludes that k is either zero or 1.
• B sees A, and notes that A has blue eyes. Since B does not initially have information about the value of k (the number of blue eyed people), B concludes that k is either 1 or 2.

Now since the islanders cannot discuss this with one another, although they collectively have enough information to resolve the problem, the shared information (common knowledge) is insufficient to resolve the issue. When the external person arrives, and declares that k ≥ 1, this changes matters. A now knows that k cannot be zero, and must therefore leave.

Suppose A and B both have blue eyes

• Both islanders conclude from observation that k is either 1 or 2. This appears to provide the same information as the outsider introduces. However, this information does not entail any logical necessity. We can see this if we follow A's reasoning (B could reason identically: "Suppose I have green eyes, then B would see a green eyed person. In this case, B would conclude that k is either 0 or 1." Now, in this scenario, A has concluded that k = 1 or 2, and also has concluded that B will conclude that k = 0 or 1, in other words, k = 1. Therefore, under this scenario, B should appear to conclude that he has blue eyes and leave. However B cannot do this, as (a) by transplanting the problem into a hypothetical scenario, the initial observation now has no force, and (b) in any case, B does not not have access to A's initial observation that k ≥ 1. This means that although B concludes (in this hypothetical case) that k = 0 or 1, this is as far as B can go. (Even if B now were to think "suppose I have green eyes", this does not help, as this simply means that B now replicates A's reasoning ans ends up in the same stalemate position.)

However, when the external person arrives and declares k ≥ 1, in A's hypothetical scenario, B could now justifiably conclude that k = 1, and that he has blue eyes, and would leave the following day. As B has not done this the day after the external arrived, A must at that point conclude that k cannot be 1 and leave on the second morning after the external arrives.

The cases where the number of islanders is 3 or more follows the same reasoning.

--91.109.11.90 (talk) 09:32, 8 July 2010 (UTC)

• Each person can see every other person's eye color, there are no mirrors, and there is no discussion of eye color.

This assumes the existence of blue eyed people is common knowledge because it is known that each person can see every other person's eye color, if one person on the island sees someone with blue eyes, it is known that everyone but that person knows of the existence of blue eyed people. Thus if there are 2 blue eyed people everyone knows there are blue eyed people. — Preceding unsigned comment added by 69.242.116.124 (talk) 14:58, 28 December 2011 (UTC)

All of this is irrelevant. In the given problem, n is never equal to 1 or 2, unless there are only 1 or 2 people on the entire island. Unless the population n <= 2, the situations of n = 1 and n = 2 will never arise. Even if there are only 2 inhabitants in each others' presence at any given time, if n > 2 there are other inhabitant(s) in other parts of the island, invalidating the logic for n = 1 or n = 2, because the one with blue eyes could be one of those "third parties". Therefore, again, the logic fails for n >= 3, because the conditions for n = 1 and n = 2 are not possible, and n >= 3 by itself has no solution. So the proposed "serial solution" to this puzzle could never arise.

The "puzzle" is only solvable in a contrived serial fashion which cannot occur under the given conditions unless the population n <= 2. No matter what k is. If n >= 3, the "logic" for n = 1 and n = 2 no longer works, because there are "third parties", each of which represents another variable. It isn't a "serial" situation any more than Zeno's paradox of Achilles and the tortoise was a serial situation. Rather, for n > 2, it is a set of simultaneous equations with no solution. -- Jane Q. Public (talk) 07:55, 25 April 2016 (UTC)

Your reasoning is incorrect. Consider an island with four blue eyed people A,B,C,D

A Knows B,C,D are blue and that A may be blue

A Knows that B Knows that C and D are blue, may know A is Blue and knows B may be blue

A Knows that B knows that C knows that D is blue, may know that A and/or B are blue and knows C may be blue

A knows that B knows that C knows that D may know that A,B and/or C are blue and knows D may be blue

So at this fourth order level The D in C's model in B's model from A's perspective could have potential n's from 0/1, 1/2, 2/3, 3/4. The guru's speech rules out the 0 option in all models first night rules out the 1 option in all models. so after 2 nights the models are

A Knows B,C,D are blue and that A may be blue

A Knows that B Knows that C and D are blue, may know A is Blue or knows B is be blue

A Knows that B knows that C knows that D is blue, and that two of A,B and C are blue

A knows that B knows that C knows that D knows three of A,B,C,D are blue.

Each of them thinks the other three may leave that night and if they don't it confirms their eyes are blue. The "serial solution" so called works, and is the true logical answer. SPACKlick (talk) 09:12, 26 April 2016 (UTC)

No, it doesn't, and it isn't. You are still inappropriately applying logic for n = 2 to an n = 4 situation. Invalid. Where you err is that there are no "potential" Ns. There is only n, and it is 4.

Repeat. A serial solution does not work because you never have the opportunity to start the chain.

Specifically, in your 6th line above, you erroneously say "the first night rules out the 1 option". It does not, because that deduction ONLY applies WHEN n = 2. You're applying the n = 2 logic but you're not showing how it applies to n = 4. It doesn't. You call it "fourth order" but you're failing to show how your second-order logic applies to your fourth-order problem. You seem to just assume it.

Because n is never 2, the body of knowledge does not actually increase after the first night, as you claimed it does.

Consider instead that A has brown eyes, B, C and D blue eyes. But it could be other combinations. Even yours.

A looks at B, C, and D, and reasons that the condition is already met. At least one person has blue eyes. Therefore, there is insufficient IMMEDIATE information available to deduce A's own eye color.

B looks at A, C and D, and reasons the same. A's eyes may be brown, but C and D are both blue. B doesn't have enough information to deduce B's own color.

C and D reason similarly. As they should.

Now, here's the kicker: in the n = 2 case, only the information that the first person DIDN'T leave gives inhabitant number 2 the information necessary for the deduction of 2's own color. That deduction REQUIRES that n = 2. Not 1, not 3, but 2. Any other value for n and that deduction fails.

But in our case here, n is not 2. Each sees at least two others with blue eyes. Obviously nobody leaves, because they all suffer from a lack of sufficient information. So far that is the same as with n = 2.

So is there new information now? No. It is not possible to reason that any of the others stayed because they saw or did not see a pair of blue eyes. Each knows that each of the others sees at least two others with blue eyes.

The n = 2 deduction after the first night, therefore, is no longer possible to make. The chain of deductions never starts. There is no way to start a similar chain after 2 or 3 ... n - 1 nights either, because the failure of n = 2 ensures that no additional information is ever added.

Just to drive it home: new information is possible to deduce after the first night IF AND ONLY IF n = 2. Not any other number.

It is not possible to reason this away with mental exercises about "potential Ns". There is only one n, and n does not equal 2 at any point in the process. As a result the first night yields no additional information. Therefore neither does the second, or third, and on down the line. I strongly suggest that if you want to refute that, you will have to resort to truth tables, because what you wrote above contains invalid assumptions. -- Jane Q. Public (talk) 09:56, 9 May 2016 (UTC)

Ofcourse people are reasoning about potential n's, the whole point is that you see x blue eyed people and you know n= x or x+1. Further you know all the blue eyed people you see know it is either (x or x+1) or (x-1 or x) depening on whether your eyes are blue or brown respectively. You also know that that blue eyed person knows about another blue eyed person that either n is ((x or x+1) or (x or x-1)) or ((x or x-1) or (x-1, x-2)) depending on your eye colour and their eye colour.

As you go along the chain of what A knows that B knows that C knows that D knows... you add uncertainty every step. Because A is unsure about their own eyes, A knows B is unsure about B's eyes, A knows that B knows that C is unsure about C's eyes and so on. These chains terminate at a person n deep who may, be considered by one potential person to see every number of blue eyes between 0 and n. SPACKlick (talk) 11:20, 9 May 2016 (UTC)

As I mentioned before, you again fail to explain how new information is added after the first night, or any set of nights. You say your "chain" terminates in a new deduction, but you leave out the absolutely necessary step of explaining how that deduction is actually arrived at. Apparently you expect us to assume that it is true but such an assumption is not warranted. From your incomplete explanation, it appears to me that you're just assuming it yourself.

In order for your "chain" to work, new information must be added every day, until a sufficient amount of information is obtained. But you don't explain how that new information is obtained when n is not 2. Imagining a hypothetical "this is what would happen *IF* n = 2" after the first night is not sufficient, because n is not 2. Your actual situation contains a completely different set of variables and information than when n = 2, so your "what happens if n = 2" logic no longer holds.

As a result, you haven't refuted what I stated at all. You've simply re-asserted your own claim without explaining how your deductions are actually made at any point in time with the information at hand.

If you could SHOW us how new information is added after the first night (or any set of nights) when n = 3, using formal logic or actual math, I'd be happy to agree and put this to rest. But until then I don't accept your very informal and incomplete explanation. You must explain the actual deductive reasoning after the first night (or X nights) for your value of n if you want to show that what you say is true. You don't get to just extrapolate it from the n = 2 scenario BECAUSE n = 2 never actually happens.

OK for N = 3 A, B, C are our blue eyed islanders. D is a brown eyed islander for ease of reference

Before Announcement

• A has the following possible mental models of the island. A1 A,B&C have blue eyes, A2 B&C have blue eyes
• A has the following mental models of B's mental models. A1B1 A,B&C have blue eyes, A1B2 A&C have blue eyes, A2B1 B&C have blue, A2B2 C has blue eyes
• A has the following models of B's models of C's models. A1B1C1 A,B&C have blue eyes, A1B1C2 A&B have blue eyes, A1B2C1 A&C have blue eyes, A1B2C2 A has blue eyes, A2B1C1 B&C have blue eyes, A2B1C2 B has blue eyes, A2B2C1 C has blue eyes, A2B2C2 Nobody has blue eyes
• A has the following models of B's of C's of D's models. A1B1C1D1 A,B,C&D have blue eyes, A1B1C1D2 A,B&C have blue eyes, A1B1C2D1 A,B&D have blue eyes, A1B1C2D2 A&B have blue eyes, A1B2C1D1 A,C&D have blue eyes, A1B2C1D2 A&C has blue eyes, A1B2C2D1 have blue eyes A&D have blue eyes, A1B2C2D2 A has blue eyes, A2B1C1D1 B,C&D have blue eyes, A2B1C1D2 B&C have blue eyes, A2B1C2D1 B&D have blue eyes, A2B1C2D2 B has blue eyes, A2B2C1D1 C&D have blue eyes, A2B2C1D2 C has blue eyes, A2B2C2D1 D has blue eyes, A2B2C2D2 Nobody has blue eyes

After Announcement (This rules out all models where nobody has blue eyes as it has become common knowledge that there are blue eyes)

• A has the following possible mental models of the island. A1 A,B&C have blue eyes, A2 B&C have blue eyes
• A has the following mental models of B's mental models. A1B1 A,B&C have blue eyes, A1B2 A&C have blue eyes, A2B1 B&C have blue, A2B2 C has blue eyes
• A has the following models of B's models of C's models. A1B1C1 A,B&C have blue eyes, A1B1C2 A&B have blue eyes, A1B2C1 A&C have blue eyes, A1B2C2 A has blue eyes, A2B1C1 B&C have blue eyes, A2B1C2 B has blue eyes, A2B2C1 C has blue eyes
• A has the following models of B's of C's of D's models. A1B1C1D1 A,B,C&D have blue eyes, A1B1C1D2 A,B&C have blue eyes, A1B1C2D1 A,B&D have blue eyes, A1B1C2D2 A&B have blue eyes, A1B2C1D1 A,C&D have blue eyes, A1B2C1D2 A&C has blue eyes, A1B2C2D1 have blue eyes A&D have blue eyes, A1B2C2D2 A has blue eyes, A2B1C1D1 B,C&D have blue eyes, A2B1C1D2 B&C have blue eyes, A2B1C2D1 B&D have blue eyes, A2B1C2D2 B has blue eyes, A2B2C1D1 C&D have blue eyes, A2B2C1D2 C has blue eyes, A2B2C2D1 D has blue eyes

After Night 1 (This rules out all models where only one person has blue eyes as nobody left)

• A has the following possible mental models of the island. A1 A,B&C have blue eyes, A2 B&C have blue eyes
• A has the following mental models of B's mental models. A1B1 A,B&C have blue eyes, A1B2 A&C have blue eyes, A2B1 B&C have blue
• A has the following models of B's models of C's models. A1B1C1 A,B&C have blue eyes, A1B1C2 A&B have blue eyes, A1B2C1 A&C have blue eyes, A2B1C1 B&C have blue eyes
• A has the following models of B's of C's of D's models. A1B1C1D1 A,B,C&D have blue eyes, A1B1C1D2 A,B&C have blue eyes, A1B1C2D1 A,B&D have blue eyes, A1B1C2D2 A&B have blue eyes, A1B2C1D1 A,C&D have blue eyes, A1B2C1D2 A&C has blue eyes, A2B1C1D1 B,C&D have blue eyes, A2B1C1D2 B&C have blue eyes

After Night 2 (This rules out all models where only two people have blue eyes as nobody left)

• A has the following possible mental models of the island. A1 A,B&C have blue eyes
• A has the following mental models of B's mental models. A1B1 A,B&C have blue eyes
• A has the following models of B's models of C's models. A1B1C1 A,B&C have blue eyes
• A has the following models of B's of C's of D's models. A1B1C1D1 A,B,C&D have blue eyes, A1B1C1D2 A,B&C have blue eyes
• As A now only has one model of the world and they have blue eyes in it they know their eye colour and will leave tonight

It's n deep in the chain of what A knows that B knows that C knows that D knows that you have a termination because nobody can have a model where anyone sees fewer than 0 sets of blue eyes. Once the announcement is made, nobody can have a model where there are fewer than 1 set of blue eyes. Each night more and more models within models are ruled out until only one model remains in the heads of the blue eyes islanders, they correct one. Two models exist in the heads of the brown eyed islanders, the correct one and the one where they themselves have blue eyes.

Was that detailed enough? SPACKlick (talk) 17:35, 9 May 2016 (UTC)

No, because the problem was not a lack of detailed map of mental states. It was the LOGIC of collapsing one state to the next after dawn, and which you have completely omitted again. That is to say, not the steady states during the day, but how the information is applied to go from state X to state Y. You simply assert it, you do not show it.

In other words, you show the states after each event (more on that in a moment), but not how the logic applies to get from one state to the next. In particular, using your descriptions, what causes the the states to shift from "after announcement" to the state of "after Night 1"? What is A's reasoning that causes A's "models of B's models of C's models" to reduce from 7 possibilities to only 4?

Please read further before hastening to reply, because the answer isn't what you seem to think.

I see that part of the misunderstanding was terminology. The situation you describe here is "k = 3", not "n = 3". n is the number of inhabitants. So in your scenario (as in mine earlier), k = 3, n = 4. I asked for an explanation of n = 3. But so be it. We have what we have. In this version of the puzzle I see that when k = 2 (not n = 2), it all works. I used n because I am more familiar with a different version of this puzzle. So the misunderstanding was probably my fault. Regardless, n was meant to represent population. It is not k.

The crux of the matter is that it is not sufficient to simply assert a state transition from "after announcement" to "after Night 1" for the reason "because nobody left". You have to show how the fact that nobody left that night APPLIES to the reasoning of the individuals WHEN n = 4 and k = 3, to cause them to enter the knowledge state you give for "after Night 1". Without that step you aren't really demonstrating anything. It must be shown.

BUT, there is no way to show it because (referencing "k" now so we are on the same channel), when n = 4 and k = 3, it is not possible to make any new deduction from the fact that nobody left on that first night. Because they all, without exception, ALREADY KNOW, before that first night, that there are 2 or more people with blue eyes. EACH can observe that directly. It is already common knowledge. Even more: each knows that the others can all see k >= 2, regardless of the color of their own eyes.

And that changes everything.

This is what I meant when I stated that the reasoning for n = 2 (but in this version k = 2), which you have assumed to be valid, is not in this specific case. It is a given, it is not reasoning. And everything else in the solution depends on that link in the chain.

To wit: your map of A's mental model of the mental models of the others "after the announcement" is incorrect. All of them already know there are at least 2 people with blue eyes after the announcement and before that first night. None of them will consider cases of less than 2 people with blue eyes because they can all SEE at least 2 people with blue eyes. None of them will reason that the others will consider cases of k < 2 because each knows that all know k >= 2.

Hence there is no new information available at dawn after night 1. The logic chain is broken. After the second night they do not have sufficient information to reason about k >= 3, because k >= 2 was not a reasoned deduction. It was a given initial condition. The DEDUCTION that k >= 2 is no longer possible.

And once that deduction is removed, everything else collapses. It is not possible to extrapolate further, because reasoning the next day that k >= 3 is an inductive (or recursive, if you prefer) chain of logic that critically depends on the initial k >= 2 deduction.

In a computer algorithm, the resolving case would be k = 2 (after one night), and all other cases of higher K would call the recursive function with K - 1, until it arrived at the resolving case. (This is simply a restatement of the inductive logic in different terms.) But we would never get there, because the resolving value for k is 2, and in our scenario k = 3 is the lower bound.

It only takes one counterexample to disprove a general solution. So far it has not been shown (including by you) that there are any flaws in my reasoning for n = 4 and k = 3. (I believe that generalizes to just k > 2, but obviously that does not matter here. Only one counterexample is necessary.)

Again, if you can SHOW logically how the inhabitants GET FROM the state of "after announcement" (which you will have to revise because what you showed is incorrect) TO knowing that k >= 3 "after Night 2", via reasoning, I will retract my claim to have refuted the general "solution". Or show that new information is actually available after Night 1. But let's be clear: it is not relevant to show that after night 1 they know k >= 2, because that is an observation, already known, and not a deduction. And it is not sufficient to show what the knowledge states are. It is necessary to describe the information available, and the reasoning required, to get from one of those states to the next.

-- Jane Q. Public (talk) 07:37, 10 May 2016 (UTC)

Ok, Two things you said stood out there. None of them will consider cases of less than 2 people with blue eyes because they can all SEE at least 2 people with blue eyes. This is true but they don't all know everyone can see 2 people with blue eyes, and they don't all know that everyone know everyone can see 2 people with blue eyes. That there are two people with blue eyes is bnot common knowledge.

As for the logic of scenarios being ruled out, Consider specifically A2B2C2DX The scenario where A's model of B's model of C's model of D's model see no blue eyes and considers the possibility they may or may not have blue eyes themselves. When the announcement is made it becomes common knowledge there are blue eyes. A can reason that B can reason that C can reason that D would reason that if they didn't see any blue eyes they would have to have blue eyes themselves. A2B2C2D2 is inconsistent with the gurus statement. Since everyones model [of everyne's model...etc.] now contains "The guru ses at least one blue eyed person" those which contradict it are discarded.

Considering specifically A's of B's of C's across night 1 A1B1C1 A1B1C2 A1B2C1 A1B2C2 A2B1C1 A2B1C2 A2B2C1 A2B2C1. In A's models of B's models of the island A2B2 was B thinking only C had blue eyes. If this model had been true C would have left the island (as everyone knew someone had blue eyes and so if C could see nobody with blue eyes they would leave) When A sees B see C on day 2 they all know that they all know that the model A2B2 cannot be true So all models within A2B2 cease to be possible. This leaves A1B1C1 A1B1C2 A1B2C1 A1B2C2 A2B1C1 A2B1C2. A1B2C2 and A2B1C2 can both be ruled out for the same reason as they are models where C considers only one blue eyes person on the island, but as above if that were the case a lone blue eyes person would know they were the blue eyed person and have left. As nobody left, these models now contain a contradiction and A knows B knows C would no longer be considering them.

This chain of logic, ruling out minimal numbers of blue eyed people in models goes from night 1 to night k. The new information each night is that "at least x+1 people have blue eyes is common knowledge" SPACKlick (talk) 10:31, 10 May 2016 (UTC)

Re: This is true but they don't all know everyone can see 2 people with blue eyes. You are correct. I see now that A might reason that if his own eyes were non-blue, then C or D might see only one pair of blue eyes.

BUT while that was a genuine error, it makes absolutely no difference. We just change conditions to n = 5, k = 4. Then it WOULD indisputably be common knowledge that each can see at least 2 pairs of blue eyes.

Re: "Consider specifically A2B2C2DX The scenario where A's model of B's model of C's model of D's model see no blue eyes and considers the possibility they may or may not have blue eyes themselves. When the announcement is made it becomes common knowledge there are blue eyes. A can reason that B can reason that C can reason that D would reason that if they didn't see any blue eyes they would have to have blue eyes themselves. A2B2C2D2 is inconsistent with the gurus statement. Since everyones model [of everyne's model...etc.] now contains "The guru ses at least one blue eyed person" those which contradict it are discarded."

You're absolutely fixated on mental models of mental models, while ignoring what is actually observed. You remind me of some climate scientists I've conversed with.

No. First, if n = 5 and k = 4, it is ALREADY common knowledge, even among those with non-blue eyes, that each islander can see 2 or more pairs of blue eyes. Even before the announcement, which yields no new information.

This is another critical point: the announcement is necessarily to a complete solution, because it gives a starting point for k = 1. If there is only one blue-eyed person, now this person knows it and can leave.

But if it is already common knowledge (it is) that k > 1, the announcement imparts nothing new. Its entire purpose is to cover the k = 1 case.

Above 2 the specific numbers don't matter very much. We can choose what we please. 4 and 3 might not have supported my logic, but 5 and 4 do. ANY counterexample disproves the general solution. In my example here, as I have stated, EVERYONE now knows (already knew) that there are k >= 2 people with blue eyes. From observation.

And for that reason, the first night does not yield the new information it would *IF* k = 2 and n = 2. More on that presently.

"The new information each night is that "at least x+1 people have blue eyes is common knowledge."

No. The puzzle uses an inductive chain of logic that critically relies on the deduction that occurs when n = k = 2 after the first night. It is a unique circumstance. Else induction would not be necessary to the "solution".

But if n = 5, k = 4 it is already common knowledge that k >= 2. The deduction that COULD take place if k really equalled 2 does not occur. Consider: no matter the mental state of the islanders, they already know k >= 2 so nobody leaves. In the ACTUAL k = 2 deduction, they don't already know that the other doesn't know, until the night is over. It is information that becomes available only AFTER nobody leaves. But with n = 5 k = 4 they DO know that everybody knows k >= 2. So the first night yields no new information,

And the same kind of deduction is not possible on the 2nd night. Try it and see. You don't get to use "IF k = 2" in your reasoning because it's a hypothetical circumstance we KNOW does not exist. It's like saying "IF my car had wings, and got 1000 mpg, I could go more places." True reasoning perhaps, but not relevant to your real world. "IF k = 2" is just wishful thinking with no basis in reality.

This is the downfall of this puzzle's logic. The reasoning for "if k = 2" isn't valid for the simple reason that at no time is k actually 2. The logic doesn't apply to the situation. The SPECIFIC case the logic works with is when k really equals 2. When n = 5 and k = 4, k is never 2 and the new information that deduction brings is not forthcoming. Nor does it appear on the 2nd, or 3rd, or 4th nights, because those are dependent on what happens on the 1st.

They can reason all they like about hypotheticals but the solution that uniquely applies when k = 2 and one night does NOT apply to k = 4 when one night has passed. Nor does an analogous situation apply when 2, 3, more nights have passed. They might as well reason hypothetically about angels and pinheads, for all the real-world good it does. You don't solve a 3 or 4 or 5 variable equation with only 2 knowns.

I will repeat what has been my whole point, all along: the "solution" insists on applying logic based on the unique condition "n = 2, k = 2 after the first night". But that logic doesn't apply UNLESS k actually equals 2 and a night has passed. At no time, in this example, are there ever just 2 people on the island, or just 2 people with blue eyes.

A, B, C, D, and E can validly reason all they like about what would happen *IF* k = 2, but it doesn't matter to their situation because k doesn't equal 2. And because it doesn't, the fact that nobody leaves after the first night has zero significance. No new information is generated. They can just as easily (and validly) reason that the unique deduction which arrives at k = 2, after one night has passed, is not possible when n = 5 and it was already commonly known that k >= 2.

When nobody leaves the first night, no new information is imparted. Everybody knows it's obvious they didn't leave because they don't have the information needed to solve the equation. And without the extra bit of information from that first night, "if and only if k = 2", there is no chain of induction.

In fact that's a better way to state it. The given "solution" says "consider the case if k = 2...", but if they worded it properly: "Consider what happens if AND ONLY IF k = 2..." then this puzzle wouldn't be on this page.

Reworded again as a recursive algorithm. You have a resolving case of k = 2 after one night. (So far that is the only known resolving condition.) For any input K > 2, the function subtracts one night, then calls itself with K - 1. Eventually it gets to k = 2, everything resolves, and your answer appears.

However, in our real world situation, the function never resolves because (in this latest example) I have already stipulated that k IS NOT ALLOWED TO BE LESS THAN 4. It is an initial condition. The hypothetical k = 2 is meaningless. The real world doesn't allow any subtraction from k, below 4. The only way that could happen would be if the islanders killed each other off one by one until k = 2.

-- Jane Q. Public (talk) 09:10, 13 May 2016 (UTC)

you say at k=4 "it was already commonly known that k >= 2" but this just isn't true. The knowledge chain just needs to be one deeper. A doesn't know that b knows that c knows that n>2. With common knowledge you can have infinite A knows that B knows....etc and it's still true. That isn't the case for any k before the announcement. After the announcement it's true for k>=1 I've shown you the full chain of logic here. It's about what people know that other people know.

When nobody leaves the first night, no new information is imparted. Everybody knows it's obvious they didn't leave because they don't have the information needed to solve the equation. Everybody knows nobody will leave, that's not the information they gain, they gain the information that other people know other people know...that nobody left, which reduces the number of possible models of the island in others heads until the only possibility is that others see your own eyes as blue or everyone you can see with blue eyes leaves.

Nobody ever actually considers k=2, they consider whether A knows k>=2, and whether A knows B knows K>=2, and whether A knows B knows C knows K>=2 etc. each person the chain passes through adds uncertainty about 1 set of eyes, and if you have a chain of consideration of A knows...K knows then there is uncertainty about every pair of blue eyes in that model so there is a model with no blue eyes, whatever the size of k. The recursive solution then follows as models with 0 blue eyes can be ruled out by everybody at any depth in the models, and then models with k=1 can be ruled out and so on until the day where all models of k<k are ruled out for everyone at every depth in the chain.SPACKlick (talk) 12:13, 13 May 2016 (UTC)

Nesting may be getting too deep; quotes are no longer working as they should. A new section should probably be started.

SPACKlick: "you say at k=4 it was already commonly known that k >= 2 but this just isn't true." Yes it is. I'll repeat what I wrote before: you're fixated on mental models of mental models, to the exclusion of simple observation. You're trying to make things much more complicated than they really are.

When k = 4, everybody on the island not only knows that k >= 2, they know that everybody else knows that. Because THEY CAN SEE IT WITH THEIR OWN EYES. They don't need additional "depth of knowledge". No tortuous mental exercise is necessary.

If I'm on the island, k = 4, and I have non-blue eyes, I CAN SEE, directly, that there are 4 people on the island with blue eyes. That is, I can SEE with my eyes that k >= 4 (therefore k >= 2).

If I'm one of the blue-eyed people, I CAN SEE that there are 3 other people with blue eyes. k >= 3, by direct observation. (Therefore k >= 2.)

And again, if I'm one of the people with blue eyes, and I can see three people with blue eyes, I know that any other person with blue eyes will also see AT LEAST 2 other people with blue eyes. So *I* know that *they* each know k >= 2.

So everybody on the island can SEE, from the outset that k is at least 2, and knows that everyone else knows k >= 2. Q.E.D. It's directly observable by everybody, so it is common knowledge.

"Everybody knows nobody will leave, that's not the information they gain, they gain the information that other people know other people know." No, they don't gain that knowledge, because as I have just explained (as I did before), it was already common knowledge from direct observation. So no new information is imparted after the first night.

I will repeat one more time: I will give this a rest, and agree that I have not refuted the "solution" to this puzzle, *IF* you can show, formally, that new information about k is actually available after the first night, or for that matter after k - 1 nights.

I have just explained, thoroughly and in plain English, why no new knowledge is gained after the first night. And again, the k = 2 deduction after the first night is critical to the original inductive solution. So my claim is that the logic chain has failed, and I have given good reasons why.

If you want to prove me wrong, you have to actually show it. You keep just asserting it, and that's not good enough. You can keep repeating it as often as you like, but that won't show us HOW any new information is gained as the nights pass. So SHOW us, using actual reasoning. Not just your mental models of mental models, which I have shown at least twice now to be incorrect.

Trying to just reduce the problem to the k = 2 logic again doesn't work, because our example here has n = 5, k = 4. That is, at all times k = 4, and it is common knowledge that k >= 2. So at no time is it possible to DEDUCE that k = 2, or that k >= 2. Reasoning about *if* k were 2 is useless. We can "consider that possibility" all we like, but it doesn't apply to the case at hand.

After that first night, they do indeed know that k >= 2, because they already knew it. Now what? In what way is new information gained, after any given night? Before you can show that "the chain continues", you have to show how it starts. Because after the first night, it hasn't yet.

04:46, 17 May 2016 (UTC)

Here is where you make a mistake "So everybody on the island can SEE, from the outset that k is at least 2, and knows that everyone else knows k >= 2. Q.E.D. It's directly observable by everybody, so it is common knowledge."

It's not common knowledge. Blue eyed you sees three blue eyed people so you know they each see at least two blue eyed people. So at first order you know k={3 or 4}. At second order you know another blue eyed person knows K={2,3 or 4}. But when you think about what that blue eyed person knows about others at third order k={1,2,3 or 4} because you don't know your eye colour and you know they don't know their eye color and yo know that they know that the third person being considered doesn't know their own eye color, so only one set of eyes being blue is common knowledge to all three of you. Common knowledge doesn't mean "Everyone knows". Common knowledge means "everyone knows that everyone knows that everyone knows that everyone knows that..." ad infinitum. That there exist blue eyes isn't common knowledge at the outset because it is not the case for (K+1)*(everyone knows that).

Set of orders of knowledge

So on day 0 before announcement (blue eyes) 1st order K={3,4} 2nd order K={2,3,4} 3rd order K={1,2,3,4} 4th order K={0,1,2,3,4} (brown eyes) 1st order K={4,5} 2nd order K={3,4,5} 3rd order K={2,3,4,5} 4th order K={1,2,3,4,5} 5th order K={0,1,2,3,4,5} After announcement (blue eyes) 1st order K={3,4} 2nd order K={2,3,4} 3rd order K={1,2,3,4} 4th order K={1,2,3,4} (brown eyes) 1st order K={4,5} 2nd order K={3,4,5} 3rd order K={2,3,4,5} 4th order K={1,2,3,4,5} 5th order K={1,2,3,4,5} After Night 1 (blue eyes) 1st order K={3,4} 2nd order K={2,3,4} 3rd order K={2,3,4} 4th order K={2,3,4} (brown eyes) 1st order K={4,5} 2nd order K={3,4,5} 3rd order K={2,3,4,5} 4th order K={2,3,4,5} 5th order K={2,3,4,5} After Night 2 (blue eyes) 1st order K={3,4} 2nd order K={3,4} 3rd order K={3,4} 4th order K={3,4} (brown eyes) 1st order K={4,5} 2nd order K={3,4,5} 3rd order K={3,4,5} 4th order K={3,4,5} 5th order K={3,4,5} After Night 3 (blue eyes) 1st order K={4} 2nd order K={4} 3rd order K={4} 4th order K={4} (brown eyes) 1st order K={4,5} 2nd order K={4,5} 3rd order K={4,5} 4th order K={4,5} 5th order K={4,5}

The announcmement provides the information that it is common knowledge k>=1, that knowledge doesn't exist at the beginning as I have already shown. Refusing to think beyond second order knowledge doesn't solve the problem, it merely ignores it. Consider the following questions. You are on the island, you see A,B,C and D with blue eyes 1) How many blue eyed people are you sure A sees? 2) How many blue eyed people is A sure B sees? 3) How many blue eyed people is A sure B is sure C sees? 4) How many blue eyed people is A sure B is sure C is sure D sees? 5) How many blue eyed people is A sure B is sure C is sure D is sure that you see? The solution really is correct SPACKlick (talk) 09:15, 17 May 2016 (UTC)

This is ludicrous, on several levels. I haven't failed to think on "higher orders". On the contrary, in your obsession with thinking in nested levels, you've completely failed to recognize first-order information that is clearly available to all.

In my example, we, as observers, already know that in fact each can SEE k >= 3, since we know that k = 4.

But they have to reason about what others think. Fine. It is quite obvious that someone observing k >= 3 will also know that even if they do not personally have blue eyes, others who do have blue eyes SEE that k >= 2. When k = 4, EVERYBODY can SEE directly k is at least 3, and can reason that if they also have blue eyes, k > 3. Their reasoning when they see k = 3 is: any of those 3 can SEE k = 2 and may suspect k > 2. NOBODY will reason that anyone else will reason k < 2 !!! Each can personally see k >= 3. To repeat: even if they have blue eyes, they can each SEE 3 other pairs of blue eyes, and they can reason that even if their own eyes were not blue, everyone who does have blue eyes can themselves see that k is AT LEAST 2.

This simple logic does show that in those circumstances it is already COMMON KNOWLEDGE that k >= 2. Therefore the announcement that k >= 1 imparts no new information. Further, after the first night, the fact that k >= 2 is, again, already common knowledge and imparts no new information.

If you're concerned that the results after the first night may be the same because they don't all know that k is specifically GREATER THAN 2, you can simply up this logic to the situation where k = 5, and eliminate that possibility too.

So to repeat (third time now): this isn't a failure of not thinking in higher orders. I've shown several times that you're trying to think in higher orders to the exclusion of first- and second-order information that is already common knowledge.

And please stop your sloppy editing. You stomped on my signature again. -- Jane Q. Public (talk) 20:52, 6 July 2016 (UTC)

Once again, it really is a failure of higher orders. To quote you Example text and you stop there. As I showed comprehensively above, it is the consideration of what I know about what A knows about what B knows about what C knows about what D knows about... that makes the knowledge not common. To see that, answer the questions I asked.

You are on the island, you see A,B,C and D with blue eyes

1) How many blue eyed people are you sure A sees?

2) How many blue eyed people is A sure B sees?

3) How many blue eyed people is A sure B is sure C sees?

4) How many blue eyed people is A sure B is sure C is sure D sees?

5) How many blue eyed people is A sure B is sure C is sure D is sure that you see?

SPACKlick (talk) 21:52, 6 July 2016 (UTC)

And once again, no it is not. When k = 4, EVERY person can SEE at least 3 pairs of blue eyes. Do you deny this?

Not all of them know that k = 4, because some of them are members of that 4. Yes?

But they know that they can see k = 3 and reason that it could be 4 if their own eyes are blue: k >= 3.

(As an aside, a person whose eyes are not blue does not know k = 4, he only knows k >= 4.)

Since EACH of them can SEE k is at least 3, EACH of them can reason thus:

"I know k >= 3. And I know that everyone who does not have blue eyes can see the same 3 blue-eyed people I do."

"Further, I know that each of the 3 blue-eyed people I see can SEE at least 2 others with blue eyes."

"Therefore EVERYONE can SEE at least 2 people with blue eyes."

By the simplest of logic, they all know k is at least 2, AND that all the others know it too.

It is COMMON KNOWLEDGE.

And since it is COMMON KNOWLEDGE that k >= 2, no new information is imparted by the initial announcement that k >= 1.

That is the part you keep arguing about, and what I am explaining. So what about this do you not understand?

I'm not trying to prove the entire thing here.

But I have just shown that the announcement yields no new information if k = 4. Because you keep saying it does.

However, I have just shown -- quite properly -- that "k >= 2" was already common knowledge.

There is no misunderstanding or failure on my part. This logic is rock solid.

You keep asserting your own answers but you have been unable or unwilling to point out any mistake in this.

-- Jane Q. Public (talk) 08:03, 11 July 2016 (UTC)

Ah, I see the problem in your logic. You are mistaken as to what common knowledge is. Common knowledge is not "Everybody knows x" or even "Everybody knows that everybody knows x" it is when you can add infinite "everybody knows that" and it is always true. This is why the logic above isn't true. The new information is yielded at the Kth level of "everybody knows that" where without the announcement you can reach people who aren't sure K>0. Please in whatever response you put, answer the questions I asked. It's key we get on the same page about the basic facts before any further discussion can be productive. SPACKlick (talk) 08:05, 11 July 2016 (UTC)

You are mistaken.

THERE IS NO LEVEL AT WHICH PEOPLE AREN'T SURE K > 0 BECAUSE THEY CAN ALL **SEE** THAT K >= 2.

That has been my point all along. And which you have failed to understand, all along.

-- Jane Q. Public (talk) 08:17, 11 July 2016 (UTC)

And you have not shown that point. I have in fact shown the reverse. Answer the 5 simple questions above and you will see you are wrong.

I see 4 sets of blue eyes (ABCD). I know A sees 3 sets (BCD) and possibly (I). I know A knows B sees 2 sets (CD) and possibly (AI). I know A knows B knows C sees 1 set (D) and possibly (ABI). I know that A knows that B knows that C knows that D possibly sees 4 sets (ABCI) but I know none for sure. K levels down we lose certainty of what people see including the possibility that A has a model where B has a model where C has a model where D sees no blue eyes and so doesn't know the fact as announced by the guru. SPACKlick (talk) 08:27, 11 July 2016 (UTC)

I have shown that point. The logic I show just above is perfectly valid.

When k = 4, the fact that k >= 2 is already common knowledge.

Because they can see that K >= 3 with their own eyes, and deduce (in one step) that everyone else can see K >= 2.

Therefore, the announcement that k >= 1 imparts no new knowledge.

If you disagree, then show exactly where my logic is incorrect. Otherwise, it's all hot air.

-- Jane Q. Public (talk) 23:39, 12 July 2016 (UTC)

Since nobody has sought to try to challenge my logic for the last year and a half, do we agreee it is valid?

I would be willing to listen to anyone who can actually challenge the logic, rather than simply declaring "you are wrong" and pointing out things I had already refuted. -- Jane Q. Public (talk) 06:20, 20 January 2018 (UTC)

Well I did challenge your logic, but you deleted the comment in your edit. The logic is fine until you call it common knowledge. Everybody knows that everybody knows that k>=2 but it is not true that everybody knows that everybody knows that everybody knows that k>=2. For common knowledge it must be true for all level of everybody knows that. Consider for a second that your opinion may be wrong and answer the 5 questions I asked. Even if it doesn't change your mind humour me. 02:19, 13 July 2016

You've not acknowledged where you've been shown to be incorrect despite it being pointed out repeatedly. While it is true for k=4 that everybody knows k>=3. And while it is true for k=4 that everybody knows that everybody knows that k>=2. And while it is true for k=4 that everybody knows that everybody knows that everybody knows that k>=1. It is not true for k=4 that everybody knows that everybody knows that everybody knows that everybody knows that k>=1. When the oracle speaks it becomes true that everybody knows that everybody knows that everybody knows that everybody knows that k>=1 and that everybody knows that everybody knows that everybody knows that everybody knows that everybody knows that k>=1. And so on.

For something to be common knowledge you must be able to write "Everybody knows that" any number of times before the statement and have it still be true. In the case of a k=4 island "There exists blue eyed people" is not common knowledge because there is some number of "Everybody knows that" you can compose before "there are blue eyed people" such that it is no longer true. For k=4 that is four levels of "Everybody knows that".

As explained in detail above, assuming the K individuals are A, B, C & D.

• A knows that there are at least 3 blue eyed people
• A knows that B knows that there are at least 2 blue eyed people
• A knows that B knows that C knows that there is at least 1 blue eyed person
• A knows that B knows that C knows that D knows that there are at least 0 blue eyed people.
• A does not know that B knows that C knows that D knows there are at least 1 blue eyed people.

So despite the fact that everyone knows, that everyone knows, that everyone knows that there are blue eyed people on the island, it is not common knowledge because if you add one or more more "everyone knows that" to the statement it becomes false.

If anything in this comment is wrong, please feel free to point it out. Preferably backed up with sources. SPACKlick (talk) 21:46, 20 January 2018 (UTC)

Hi. In the hopes that it might be useful, I'd like to share what I think is an intuitive explanation for why this example is correct. I shared Jane's reaction to the example initially until I worked it out this way:

In the k=4 scenario, everyone knows that everyone can see that k>=2. However, before the announcement, there is a plausible explanation as to why no one has left the island. Let's say I'm A. I don't know my eye color and thus cannot know what B knows about my eye color yet. I know that B doesn't know that B has blue eyes because B hasn't left. I know that B knows that C and D have blue eyes BUT B has no reason to believe that C or D can discover their own eye color on a logical basis before the announcement because (from my understanding of B's perspective) B could plausibly believe that C and D are in the pre-announcement k=2 scenario. That is, if I have green eyes.

I can imagine that C and D have a perspective identical to B's.

The announcement is made. One night passes and no one leaves. If k=2, C and D will both see that A and B have green eyes but that the blue-eyed person has not left. Thus C and D will simultaneously reason that their eyes are also blue and leave on the second night.

But C and D don't leave. I know that when B sees this, being perfectly logical, B will leave on the third night because B has figured out that the reason that C and D have not left is because there is another person with blue eyes on the island. And since - fingers crossed - my eyes are green, I will be the only one left.

Night three passes. And yet, no one has left. I finally realize that, since everyone has made the same calculation up to this point but the k=3 scenario has played out without anyone leaving, that I myself was a piece of everyone else's k=3 scenario because I have blue eyes too. We all come to the same conclusion and all leave on the fourth night.

The key is not that everyone knows that everyone knows k>=2, it's that everyone thinks that everyone else's k>=2 is based on a different pair. The chain starts when everyone can see that everyone else's pair knows that k>2. ConvergedPerceptron (talk) 20:30, 27 January 2019 (UTC)

Common versus Mutual Knowledge

I think there is an important mistake in the Steven Pinker reference from Stuff of Thought. It currently states "...the notion of common knowledge (dubbing it mutual knowledge, as it is often done in the linguistics literature)". In fact, Pinker and linguists specifically differentiate mutual knowledge - that which we all know - from common knowledge - that which we all know that we all know (and we all know that we all know that we all know, ad infinitum). Unless I'm misunderstanding it, I'd like to change it. Dashing Leech (talk) 19:39, 18 December 2010 (UTC) — Preceding unsigned comment added by Dashing Leech (talk • contribs) 19:34, 18 December 2010 (UTC)

No. The problem specifically distinguishes between what everyone knows, and what an individual knows. If that were not so, it would not be a puzzle. -- Jane Q. Public (talk) 06:24, 20 January 2018 (UTC)

Clarification for non base cases

The example does not adequately explain the problem. It covers limited base cases, but never reaches a level of academic interest where the information provided already exists in the system, but the event, merely by being a unique event synchronously experienced by individuals interested in pursuing a logical solution causes the system to solve itself.

Before stepping in this direction, lets say that we can describe this puzzle as p(b,g) where b is the number of people with blue eyes and g is the number of people with green eyes. Blue eyed people will be referred to in capitals. Green eyed people will be referred to in lower case letters. We have disallowed p(0,n). p(1,0) is a base case where A is told they have blue eyes and promptly leave. In p(1,1) A realizes b doesn't have blue eyes and therefore A must have blue eyes. There is 100% certainty that A must have blue eyes, so A leaves. In p(2,0) A sees that B has blue eyes, and doesn't leave on the first night. B sees that A has blue eyes and doesn't leave on the first night. On the second night, they see they both didn't leave and realize that someone else with blue eyes was there to satisfy the first requirement. Since there are only two people, the other person MUST be them, so they both leave. This is still a base case.

We can show quickly for p(2,1) that this still works

• A and B see 1 person with blue eyes meaning there are 1 or 2 people with blue eyes. c sees two people with blue eyes, meaning there are 2 or 3 people with blue eyes. Since neither A or B leaves on the first night, it indicates that both A and B see at least one other person with blue eyes. This means that since they cannot see one other person with blue eyes, they must be the other person with blue eyes. On the second night, A and B leave, showing c he doesn't have blue eyes.

You can do this with all p(2,n) because adding another green eyed person does not change the pressure provided by A and B knowing the other either sees nobody with blue eyes or them with blue eyes.

To get somewhere interesting lets look at p(3,1)

• A,B,C,d see each other on the first night. A,B,C see two others with blue eyes, while d sees 3. This is where the metathought begins. A realizes that B and C see either 1 or 2 other blue eyed people. A further realizes that if B and C see only 1, they will have to wait to make sure that they are not alone. So the first night is spent confirming to A, B, and C that each sees at least 1 other person. The second night confirms 2, at which point, A,B,C realize they are the 3 people, so they leave on the third night.

From d's perspective, d sees 3 people with blue eyes. d realizes that if d doesn't have blue eyes, A,B,C will see only two people with blue eyes. If A,B,C only see two people with blue eyes, A will have to wait for B and C to be convinced that each other sees the other has blue eyes. This means d waits one day for each of the three with blue eyes. d MUST wait for this process because even though d can see quite plainly that A,B,C all see at least 2 people, it realizes that A doesn't see that B sees 2 people, so the knowledge must trickle up incrementally.

Finally, we scale this to p(B,g)

• B people see B-1 people and must wait B days for it to be satisfactory that all B people are aware of their status. The realization that each has blue eyes occurs simultaneously. g people wait B+1 days to realize that they don't have blue eyes because it isn't until people with blue eyes leave that those without glean that information.

The important thing to note is that without the knowledge that ALL of the others are attempting to solve this puzzle at the same time in the most efficient way possible, none of this logic matters. If there is even a one day offset in the counting, or a slightly different approach attempted in solving it, the knowledge that people aren't leaving because they know they don't know they can can't be utilized to determine if any individual is in the set allowed to leave. —Preceding unsigned comment added by 174.16.227.147 (talk) 07:20, 12 March 2011 (UTC)

It doesn't matter anyway because if the population n = 1 or n = 2, the solutions are trivial. But if n >= 3, the situations considered in the given "solution", in which n = 1 and n = 2, are not possible. The initial deductions which lead to a 'serial' solution will not occur. That leaves you starting with n >= 3, which has no solution. -- Jane Q. Public (talk) 09:17, 25 April 2016 (UTC)

Update: I've continued the argument above, and I see that my initial conditions were wrong. In order to follow my logic you'd have to have population n >=5 and k = 4, or in your terminology p(4,1).

Here's the problem. When you have k >= 4, all the islanders can see directly that k >= 2. They already know this: it is common knowledge. Therefore, the announcement that "at least one" has blue eyes imparts no new information. Further, because it is already known that k >=2, after the first night, that first critical deduction when k = 2, is impossible to make because the equation has changed.

Two of them could be in an isolated corner of the island, but there are still other people on the island so k is never 2, and the reasoning that applies to k = 2 does not apply to them.

It doesn't matter how much meta-thinking you apply because the critical deduction which kicks off the induction chain never occurs.

This puzzle's fault is that the generalized "solution" calls the reasoning "IF k = 2" as valid, even when k is never, at any time, actually equal to 2. In all of those (an infinite number) of cases, there is no solution because k is NOT 2. Rather, k is always > 2. There are too many variables and not enough knowns, and successive nights do not impart any new information. That particular situation is unique to k = 2 and the inductive chain that follows it. If you're starting with it known that k >= 2, and nobody leaves on the first night, nothing of consequence may be deduced from that and you're at a dead end.

As I stated above: the only way it could actually be done when k is more than a few would be for the islanders to kill each other off until k = 2.

-- Jane Q. Public (talk) 08:58, 13 May 2016 (UTC)

Modal logic (syntactic characterization) --- finite or infinte?

Am I missing something? First, you say that there are n modal operators Ki (with i = 1, ..., n). Then you define a conjunction of the Ki with i in G (a possibly infinite set) and complain that this conjunction is not finitary. But you just finished saying that there are only finitely many Ki. Which is it?

In my opinion, G should always be countable (although that is not crucial as far as I can see) but the conjunction should always be of only finitely many of the Ki. (I think G should be countable in any real world situation, but I see no harm in allowing uncountable G. However, for common knowledge to be meaningful, I can't see how an infinite conjunction can be allowed.)

I'll leave it to someone else to edit this, using the correct symbols. Dagme (talk) 20:02, 21 May 2011 (UTC)

Can someone please explain why this logic doesn't work?

Firstly, let us assert that people don't *want* to leave the island, so they will work to avoid knowing it if they possibly can, and that this is common knowledge too.

Secondly, let us assert the the number of blue eyed people on the island is 'large' - let us assume 10.

What prevents the reasoning: "What if the blue-eyed people I see don't leave the island, despite the taboo? Then I would leave, in the mistaken belief that I had blue eyes! I should not leave the island because I won't know my own eye colour. Since there are a large number of blue-eyed people on the island, they can come to the same conclusion, so they may choose not leave the island, despite of the taboo - because the taboo is not broken. No-one must leave." — Preceding unsigned comment added by 2.26.62.147 (talk) 10:42, 29 June 2011 (UTC)

All of the above is indeed correct. However, for purposes of the problem, the islanders simply cannot help but count the number of blue-eyed people and work out all the deductions. And they all know this about each other, and they all know that they all know this about each other, etc. So no "deliberate ignorance" is possible. 71.162.46.164 (talk) 17:37, 11 February 2012 (UTC)

The blue eyes puzzle is wrong

I feel like I'm being trolled on a mass scale.

Everyone uses examples of 1 and 2 people, where it works, and then jumps to it working for k > 2, when it just doesn't. If k > 1, *everyone* already sees blue eyes, and the announcement doesn't introduce any new knowledge in any way.

We are to assume the islanders can count the number of blue eyes people to induce the number of days to wait as k, but they have some inexplicable internal block that says despite everyone seeing at least one blue eye person (in k>2) they don't know it until the oracle states it explicitly?

I've spent the last few days trying to "understand" the solution, wracking my brain, and now I'm calling bullshit. I really just think people are being dishonest here and introducing a secretive vague absurdly ridiculous rule (everyone can see blue eyes, yet doesn't *technically* know that everyone else knows there are blue eyes) to justify a CLEARLY flawed example.

I also appreciate the correct answer, which is that if(k > 1) everyone blue-eyes person leaves on the kth day /from when they arrived/. But it doesn't seem to be anything more than a deceptive puzzle, and has little to do with the actual topic of common knowledge, and any attempt to amend the puzzle to account for this vague extra rule would seem to make it lose its appeal and just be convoluted.

"Oh yeah, everyone sees blue eyes but no one's really sure that everyone else sees them, oh but, wait - no, they do know that later when they are counting days, because someone announced it... dur de dur"

The premise of not being able to assume that the other agents are paying attention to their surroundings, really breaks down when they all pay attention to their surroundings to induce the number of days they have to wait to leave.

--173.228.31.160 (talk) 11:42, 14 July 2012 (UTC)

While this comment is several years later, you are correct. The others are wrong. See my explanation above. -- Jane Q. Public (talk) 11:50, 22 January 2018 (UTC)

• Sorry, but of course it introduces new knowledge. It works with 3 guys, just as well as with 2 or a million. But let p1,p2,p3 be your guys. Then, and try following this. Before the statement, this is the case: p1 can imagine that p2 sees p1 having red eyes (p1 does not know his own color). Furthermore, the same holds if we swap p2 and p1. Thus: p1 can imagine that p2 believes p2's colors to be red and furthermore that he sees p1 having red eyes. This is the case for two agents. Then we proceed. If we take our first statement, and changes p1,p2 with p2,p3, we get that p2 can imagine that p3 sees p2 having red eyes (p2 does not know his own color). Furthermore, the same holds if we swap p2 and p3. Now, we already know that p1 accepts that p2 can believe that both p1 and p2 has red eyes. According to the sentence above, p1 can also accept that p2 believes that p3 believes that p3 has red eyes. Hence, p1 accepts that p2 can believe that p3 believes that everyone has red eyes. Now, if some deus says that some guy has blue eyes, p1 cannot anymore accept that statement. Hence something new has been learned. -- Pål GD (80.203.133.93 (talk) 09:51, 9 August 2012 (UTC))

Hey 173.228.31.160,

in case you are still trying to wrap your brain around this problem I will try point out something important here (in case the very nice post of 80.203.133.93 did not already clarify it):

You wrote: "If k > 1, *everyone* already sees blue eyes, and the announcement doesn't introduce any new knowledge in any way."

Let's say for K=5 (p1-5): Before the announcement p1 can think that p2 can think that p3 can think that p4 can think that p5 can think that there are only green eyed people. Understand? Even though everyone already *sees* blue eyes, everyone can *think* that another person can *think* ... (and so on for the correct amount of times) ... that another person *thinks* there are only green-eyed people. But that is not possible anymore after the announcement! This is a very relevant example for common knowledge (everyone knows that everyone else knows).

Importantly, p1 CANNOT e.g. think that p5 can think that there are only green-eyed people (because p1 thinks that p5 sees at least 3 blue-eyed people) Or e.g. p1 CANNOT think that p2 can think that p5 can think that there are only green-eyed people (because p1 thinks that p2 thinks that p5 sees at least 2 blue-eyed people).

It has to always go through the whole "recursion chain"! (the order does not matter btw)

--Felix Tritschler (talk) 22:37, 24 September 2012 (UTC)

There is a problem with the way the induction is commonly presented, in that k is used both for the day and the number of blue-eyed islanders. Separate variables should be used, because you are given an island with n blue-eyed residents and never change that number. You can do induction only on the what each knows about the others' knowledge on day k. This article could clarify this in its discussion of the puzzle. --98.69.157.202 (talk) 11:03, 3 November 2012 (UTC)

Better puzzle explanation as observer vs partcipant

I see a lot of formal logic chains confusing and overwhelming people. Here's a simpler explanation. Consider that as an islander, you can consider two possibilities: 1. You are a blue-eyed islander. 2. You are an observer to what happens with the blue-eyeds since you are not one.

• With 1 blue-eyed islander: As blue-eyed yourself, you only learn that blue eyes exist after announcement, you see none so it must be you, and you leave. As observer, you watch the one person leave.
• With 2 blue-eyed islanders: As blue-eyed yourself, you see only one person with blue eyes, so you wonder if you are just an observer of a 1-blue-eyed situation. But since you don't see the one person leave, you must be a participant in the blue-eyed group, so you leave the second day.
• With 3 blue-eyed islanders: As blue-eyed yourself, you see only 2 blue-eyed islanders. So, you wonder if you are an observer of a 2-blue-eyed situation. There is no way for a 2 blue-eyed situation not to work out as above, so you wait to just watch it play out. When it doesn't, you realize you have blue eyes too, and you leave.
• With 4 blue-eyed islanders: As blue-eyed yourself, you see only 3 blue-eyed islanders. So, you wonder if you are an observer of a 3-blue-eyed situation. There is no way for a 3 blue-eyed situation not to work out as above (because if it's really just 3, each of the participants will wonder if it is just 2 etc), so you wait to just watch it play out. When it doesn't, you realize you have blue eyes too, and you leave.

Going into layers upon layers of knowledge of what others know just makes this hard to follow. And treating it like a chain that actually plays out as an order of operations is confusing too. The approach above simply shows that if you are blue-eyed, you can discover this when you fail to see the logic play out without you.

Backfromquadrangle (talk) 19:43, 23 June 2016 (UTC)

Being logical they all know how this puzzle works and that it requires a starting date from which to start counting the days. Not being able to discuss blue eyes they can't agree on a starting date. The extra common knowledge brought by the visitor is the start date. 194.207.86.26 (talk) 22:39, 25 June 2018 (UTC)

Islander fiction

[1] I'm tempted to put this in External Links but will leave it for others to consider. 2602:24A:DE47:BB20:50DE:F402:42A6:A17D (talk) 00:09, 21 October 2020 (UTC)