Editing Common knowledge (logic) (section)

== Example ==

=== Puzzle ===

The idea of common knowledge is often introduced by some variant of [[induction puzzles]] (e.g. [[Induction puzzles#Muddy Children Puzzle|Muddy children puzzle]]):{{ref|Sevitan}}

On an island, there are ''k'' people who have blue eyes, and the rest of the people have green eyes. At the start of the puzzle, no one on the island ever knows their own eye color. By rule, if a person on the island ever discovers they have blue eyes, that person must leave the island at dawn; anyone not making such a discovery always sleeps until after dawn. On the island, each person knows every other person's eye color, there are no reflective surfaces, and there is no communication of eye color.

At some point, an outsider comes to the island, calls together all the people on the island, and makes the following [[Dynamic epistemic logic#Public Events|public announcement]]: "At least one of you has blue eyes". The outsider, furthermore, is known by all to be truthful, and all know that all know this, and so on: it is common knowledge that they are truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes (<math>C_G[\exists x\! \in\! G ( Bl_{x})]</math>). The problem: finding the eventual outcome, assuming all persons on the island are completely logical (every participant's knowledge obeys the [[Epistemic modal logic#The properties of knowledge|axiom schemata for epistemic logic]]) and that this too is common knowledge.

=== Solution ===

The answer is that, on the ''k''th dawn after the announcement, all the blue-eyed people will leave the island.<ref>{{cite news |last1=Bennett |first1=Jay |title=Solution to Riddle of the Week #27: The Blue-Eyed Islanders |url=https://www.popularmechanics.com/science/math/a26564/solution-to-riddle-of-the-week-27/ |access-date=31 May 2025 |work=Popular Mechanics |date=18 May 2017}}</ref>

==== Proof ====
The solution can be seen with an inductive argument. If ''k''&nbsp;=&nbsp;1 (that is, there is exactly one blue-eyed person), the person will recognize that they alone have blue eyes (by seeing only green eyes in the others) and leave at the first dawn. If ''k''&nbsp;=&nbsp;2, no one will leave at the first dawn, and the inaction (and the implied lack of knowledge for every agent) is observed by everyone, which then becomes ''common knowledge'' as well (<math>C_G[\forall x\! \in\! G ( \neg K_{x}Bl_{x})]</math>). The two blue-eyed people, seeing only one person with blue eyes, ''and'' that no one left on the first dawn (and thus that ''k''&nbsp;>&nbsp;1; and also that the other blue-eyed person does not think that everyone except themself are not blue-eyed <math>\neg K_{a}[\forall x\! \in\! (G-a) (\neg Bl_{x})]</math>, so ''another'' blue-eyed person <math>\exists x\! \in\! (G-a) (Bl_{x})</math>), will leave on the second dawn. Inductively, it can be reasoned that no one will leave at the first ''k''&nbsp;−&nbsp;1 dawns if and only if there are at least ''k'' blue-eyed people. Those with blue eyes, seeing ''k''&nbsp;−&nbsp;1 blue-eyed people among the others and knowing there must be at least ''k'', will reason that they must have blue eyes and leave.

For ''k''&nbsp;>&nbsp;1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not ''common knowledge'', but instead [[Mutual knowledge (logic)|mutual knowledge]].

For ''k''&nbsp;=&nbsp;2, it is merely "first-order" knowledge (<math>E_G[\exists x\! \in\! G ( Bl_{x})]</math>). Each blue-eyed person knows that there is someone with blue eyes, but each blue eyed person does ''not'' know that the other blue-eyed person has this same knowledge.

For ''k''&nbsp;=&nbsp;3, it is "second order" knowledge (<math>E_GE_G[\exists x\! \in\! G ( Bl_{x})]=E_G^2[\exists x\! \in\! G ( Bl_{x})]</math>). Each blue-eyed person knows that a second blue-eyed person knows that a third person has blue eyes, but no one knows that there is a ''third'' blue-eyed person with that knowledge, until the outsider makes their statement.

In general: For ''k''&nbsp;>&nbsp;1, it is "(''k''&nbsp;&minus;&nbsp;1)th order" knowledge (<math>E_G^{k-1} [\exists x\! \in\! G ( Bl_{x})]</math>). Each blue-eyed person knows that a second blue-eyed person knows that a third blue-eyed person knows that.... (repeat for a total of ''k''&nbsp;&minus;&nbsp;1 levels) a ''k''th person has blue eyes, but no one knows that there is a "''k''th" blue-eyed person with that knowledge, until the outsider makes his statement. The notion of ''common knowledge'' therefore has a palpable effect. Knowing that everyone knows does make a difference. When the outsider's public announcement (a fact already known to all, unless k=1 then the one person with blue eyes would not know until the announcement) becomes common knowledge, the blue-eyed people on this island eventually deduce their status, and leave.

In particular:
# <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math> is free (i.e. known prior to the outsider's statement) [[iff]] <math>i + j \le k</math>.
# <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math>, with a passing day where no one leaves, implies the next day <math>E_G^{i - 1} [|G ( Bl_{x})| \ge j + 1]</math>.
# <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math> for <math>j \ge k</math> is thus reached iff it is reached for <math>i + j > k</math>.
# The outsider gives <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math> for <math>i = \infty, j = 1</math>.