This is the
talk page for discussing improvements to the
Common knowledge (logic) article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||||||||
|
To-do list for Common knowledge (logic):
|
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)
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)
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)
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)
"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.
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)
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 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)
The last premise is, of course, flawed. 71.162.46.164 ( talk) 17:48, 11 February 2012 (UTC)
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:
However, we as observers also know:
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.
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
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)
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)
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)
OK for N = 3 A, B, C are our blue eyed islanders. D is a brown eyed islander for ease of reference
Before Announcement
After Announcement (This rules out all models where nobody has blue eyes as it has become common knowledge that there are blue eyes)
After Night 1 (This rules out all models where only one person has blue eyes as nobody left)
After Night 2 (This rules out all models where only two people have blue eyes as nobody left)
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)
-- Jane Q. Public ( talk) 07:37, 10 May 2016 (UTC)
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.
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.
"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."
"The new information each night is that "at least x+1 people have blue eyes is common knowledge."
-- Jane Q. Public ( talk) 09:10, 13 May 2016 (UTC)
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.
"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.
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)
Example textand 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.
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.
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)
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)
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
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)
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)
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)
-- Jane Q. Public ( talk) 08:58, 13 May 2016 (UTC)
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)
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)
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)
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)
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.
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)
[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)
This is the
talk page for discussing improvements to the
Common knowledge (logic) article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||||||||
|
To-do list for Common knowledge (logic):
|
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)
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)
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)
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)
"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.
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)
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 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)
The last premise is, of course, flawed. 71.162.46.164 ( talk) 17:48, 11 February 2012 (UTC)
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:
However, we as observers also know:
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.
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
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)
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)
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)
OK for N = 3 A, B, C are our blue eyed islanders. D is a brown eyed islander for ease of reference
Before Announcement
After Announcement (This rules out all models where nobody has blue eyes as it has become common knowledge that there are blue eyes)
After Night 1 (This rules out all models where only one person has blue eyes as nobody left)
After Night 2 (This rules out all models where only two people have blue eyes as nobody left)
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)
-- Jane Q. Public ( talk) 07:37, 10 May 2016 (UTC)
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.
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.
"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."
"The new information each night is that "at least x+1 people have blue eyes is common knowledge."
-- Jane Q. Public ( talk) 09:10, 13 May 2016 (UTC)
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.
"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.
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)
Example textand 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.
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.
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)
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)
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
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)
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)
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)
-- Jane Q. Public ( talk) 08:58, 13 May 2016 (UTC)
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)
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)
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)
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)
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.
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)
[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)