9 Epistemic Logic
Modal logic has been used to model knowledge and belief. Epistemic logic provides a formal framework for the study of different aspects of knowledge and its interaction with belief.
9.1 Knowledge
Basic epistemic logic begins with (Hintikka 1962). The first step is to supplement the language of propositional logic with a family of propositional operators \(\textsf{K}_i\) for a family of epistemic agents \(i\in I\). A formula of the form \(\textsf{K}_i \varphi\) is read: “agent \(i\) knows that \(\varphi\),” and \(\neg \textsf{K}_i \varphi\) is read: “agent \(i\) does not know that \(\varphi\).” On the other hand, \(\textsf{K}_i \neg \varphi\) is read: “agent \(i\) knows that not-\(\varphi\),” which amounts to the claim that agent \(i\) has ruled out that \(\varphi\). The dual of \(\textsf{K}_i\), \(\neg \textsf{K}_i \neg\), is symbolized: \(\langle \textsf{K}_i \rangle\), is read: “agent \(i\) has not ruled out \(\varphi\)” or “for all agent \(i\) knows, might be the case.” If to know that not-\(\varphi\) is to rule \(\varphi\) out, then to not know that not-\(\varphi\) is to not rule \(\varphi\) out, which is to say that \(\varphi\) might, for all the agent knows, the case.
Here is the broad picture as described by Lewis (1986) in terms of epistemic alternatives:
The content of someone’s knowledge of the world is given by his class of epistemically accessible worlds. These are the worlds that might, for all he knows, be his world; world \(w\) is one of them iff he knows nothing, either explicitly or implicitly, to rule out the hypothesis that \(w\) is the world where he lives.
In what follows we speak of states rather than worlds, and we take a state \(v\) to be accessible from another state \(u\) just in case whatever the agent knows to be the case in \(u\) is the case in \(v\).
Definition 9.1 (States of Information) A relational model \(M\) for \(\mathcal{L}^{K_i}\) is a structure \((W, \{R_i: i\in I\}, V)\), where:
- \(W\) is a non-empty set of information states or states of the world,
- For each \(i\in I\), \(R_i\) is a binary accessibility relation on \(W\), and
- \(V\) is a function, which assigns to each propositional variable \(p\) a set of states \(V(p)\).
States encode information. In a poker game, players may be concerned with what cards other players may have, and they may therefore consider deals consistent with the cards they have received. We may think of a state in that case as given by a distribution of cards to the relevant players. As the game progresses, players may gain information allowing them to rule out certain distributions as live epistemic alternatives.
Or consider another real-life example. Suppose you have lost sight of your phone, which you think, you may have been stolen. In one state, your phone has been stolen (\(p\)), whereas in another state it has merely been misplaced but not stolen (\(\neg p\)). In all epistemically accessible states, however, your phone had been with you just yesterday night (\(q\)). That would place you in a state in which you know your phone had been with you yesterday night, \(\textsf{K}_i q\), but you do not know whether your phone has been stolen: \(\neg \textsf{K}_i p \wedge \neg \textsf{K}_i \neg p\).
One way to model the situation is through a model, which consists of two states \(s_1\) and \(s_2\) corresponding to two epistemic alternatives: one in which your phone has been stolen (\(p\)), and one in which it has not been stolen (\(\neg p\)).
Notice that \(\textsf{K}_i q\) is true at either state because \(q\) is true at all epistemically accessible states, yet neither \(\textsf{K}_i p\) nor \(\textsf{K}_i \neg p\) is true at either state.
Knowledge rules out epistemic alternatives and helps one locate the actual world within the space of epistemic live options. Your lack of knowledge whether your phone has been stolen is represented by your inability to locate the actual world in the space of epistemic live alternatives described above. Nothing you know enables you to distinguish \(s_1\) from \(s_2\).
We now explain what it is for a formula \(\varphi\) true at a state \(s\) in a model \(M\) of the form \((W, \{R_i: i\in I\}, V)\), written \(M, s \Vdash \varphi\), inductively.
Definition 9.2 (Truth at a State) If \(M\) is a model of the form \((W, \{R_i: i\in I\}, V)\), we define \(M, s \Vdash \varphi\) as follows:
\[\begin{array}{lll} M, s \Vdash p & \text{iff} & s \in V(p)\\ M, s \Vdash \neg \varphi & \text{iff} & M, s \nVdash \varphi\\ M, s \Vdash (\varphi \to \psi) & \text{iff} & M, s \nVdash \varphi \ \text{or} \ M, s \Vdash \psi\\ M, s \Vdash \textsf{K}_i \varphi & \text{iff} & \text{for every} \ u \in W \ \text{s.t.} \ R_i su, \ M, u \Vdash \varphi\\ \end{array}\] Since \(\langle \textsf{K}_i \rangle\) as the dual of \(\textsf{K}_i\), that is, \(\neg \textsf{K}_i \neg\), we have: \[\begin{array}{lll} M, s \Vdash \langle \textsf{K}_i \rangle \varphi & \text{iff} & \text{for some} \ u \in W \ \text{s.t.} \ R_i su, \ M, u \Vdash \varphi\\ \end{array}\]
We are now in a position to define truth in a model of epistemic logic.
Definition 9.3 (Truth in a Model) A formula \(\varphi\) is true in a model \(M\) of the form \((W, \{R_i: i\in I\}, V)\), written \(M\Vdash \varphi\), if, and only if, for every \(s\in W\), \(M, s \Vdash \varphi\).
9.1.1 Axioms for Epistemic Logic
These decisions are not inconsequential. For it follows that agents know all logical truths and that they know what follows from what they know. That is the framework vindicates a rule of necessitation and all substitution instances of axiom \(\textsf{K}\): \[\tag{\textsf{RN}} \varphi / \textsf{K}_i \varphi\]
\[\tag{\textsf{K}} \textsf{K}_i(p \to q) \to (\textsf{K}_ip \to \textsf{K}_iq)\]
This involves a modicum of idealization: ordinary knowledge is not closed under logical consequence, and it is not all that , plausible to think agents ordinarily know all logical truths.
One important consequence is that knowledge commutes with conjunction:
\[\tag{\textsf{M}} \textsf{K}_i(p \wedge q) \to (\textsf{K}_ip \wedge \textsf{K}_iq)\]
One way to cope with these observation is to let \(\textsf{K}_i\) model not ordinary knowledge but rather knowledge by an idealized agent equipped with unlimited logical capabilities. Alternatively, one may instead take \(\textsf{K}_i\) to model implicit knowledge, which is what follows from knowledge we may reasonably attribute to ordinary agents even if it is not explicitly known by them.
The next step is to consider the epistemic interpretation of different modal axioms and to ask whether or not they are candidates for the logic of knowledge.
What is known is the case.
\[\tag{\textsf{T}} \textsf{K}_i p \to p\]
The principle that knowledge implies truth is virtually uncontroversial, and a firm candidate for the logic of knowledge. From a semantic point of view, \(\textsf{T}\) modally defines the class of reflexive frames, and its substitution instances are true in all reflexive models: if \(\textsf{K}_i p\) is true in all epistemic alternatives to a given state \(s\), then since \(s\) itself is such an alternative, \(p\) is true at \(s\).
One consequence of the combination of \(\textsf{T}\) and \(\textsf{M}\), according to which knowledge commutes with conjunction, is that Moorean sentences of the form
\[(\varphi \wedge \neg \textsf{K}_i \varphi)\]
become unknowable. Consider what happens if I tell you that your phone has been stolen but you do not know it, which we could formalize \(p \wedge \neg \textsf{K}_i p\). Could you ever come to know that conjunction? That is, could it be the case that \(\textsf{K}_i(p \wedge \neg \textsf{K}_ip)\)? Notice that the sentence is falsified at every state of the model we considered. For suppose you come to know the conjunction \(p \wedge \neg \textsf{K}_i p\): \(\textsf{K}_i(p \wedge \neg \textsf{K}_ip)\). By (\(\textsf{M}\)) above, you would come to know the two conjuncts: \(\textsf{K}_i p \wedge \textsf{K}_i \neg \textsf{K}_i p\). But that would give us both \(\textsf{K}_ip\) and \(\textsf{K}_i\neg \textsf{K}_ip\). By axiom \(\textsf{T}\), the latter would only be true if \(\neg \textsf{K}_ip\), which would contradict \(\textsf{K}_i p\).
What might be known is the case.
Recall that we are able to move freely from \((\textsf{B})\) to its dual \((\textsf{B}_\Diamond)\):
\[\tag{$\textsf{B}$} p \to \textsf{K}_i \langle \textsf{K}_i \rangle p\]
\[\tag{$\textsf{B}_\Diamond$} \langle \textsf{K}_i \rangle \textsf{K}_i p \to p\]
Here is a gloss of the dual: if for all \(i\) knows, \(i\) knows that \(p\), then \(p\) is the case. In other words, if it is compatible with what I know that I know \(p\), then \(p\) is in fact the case. Or, for a more compact formulation: whatever might be known is the case.
\((\textsf{B})\) corresponds to the symmetry of the \(i\)-accessibility relations: for all \(s, t \in W\), if \(R_i st\), then \(R_i ts\). (Williamson 2000) observes that symmetry plays a role in arguments for radical skepticism. For suppose that in a given state \(s\), the agent \(i\) truly believes that they have a hand. The skeptic describes an epistemic alternative \(t\) at which the agent \(i\) believes that they have a hand while being in fact a brain in a vat. It is uncontroversial that the non-skeptic state is an epistemic alternative to \(s\) in the skeptic scenario: \(Rts\). That is, all \(i\) knows at \(t\) is in fact the case at \(s\). The agent does not know, for example, that they are a brain in a vat. Given symmetry then, \(Rst\), which is to say that all \(i\) knows at \(s\) is in fact the case at \(t\). But since \(i\) does not have a hand at \(t\), it follows that, at \(s\), agent \(i\) does not know that they have a hand.
One way to undermine confidence in \((\textsf{B})\) is to note that it delivers substitution instances of the principle:
\[\neg p \to \textsf{K}_i \neg \textsf{K}_i \varphi.\]
If you fail to know something, then you know that you do not know it. The problem is that the brain in a vat neither have hands nor know that they do not know that they have hands. In other words, they do not have hands, and they do not know that they do not know.
Symmetry follows from the combination of reflexivity and the euclidean condition: if \(R_i\) is reflexive and euclidean, then \(R_i\) is symmetric. But the euclidean condition corresponds to axiom \(\textsf{5}\). To the extent to which \(\textsf{KT5}\) or \(\textsf{S5}\) extends \(\textsf{KTB}\), the above considerations extend to axiom \(\textsf{5}\), which in the presence of \(\textsf{T}\) would give us \(\textsf{B}\).
What is not ruled out is known to not be ruled out.
\[\tag{$\textsf{5}$} \langle \textsf{K}_i\rangle p \to \textsf{K}_i \langle \textsf{K}_i \rangle p\]
Consider the dual:
\[\tag{$\textsf{5}_\Diamond$} \langle \textsf{K}_i \rangle \textsf{K}_i p \to \textsf{K}_i p\]
If an agent \(i\) has not ruled out that she knows that \(p\), then she knows that \(p\). This is implausible. There are many cases in which agents mistakenly take themselves to know something that is in fact not the case. For example, I may mistakenly take myself to know that taking a certain route is the most effective way to reach my destination at a given time. Unbeknownst to me, there are special circumstances that make it the case that the rout in question is not in fact the most effective. Since knowledge entails truth, I do not know that, but I have still not ruled out that I know the proposition in question. According to a substitution instance of \(\textsf{5}\), it follows that I know the proposition when in fact I do not. In other words, \(\textsf{5}\) would require agents to be immune to error of the sort just now described, which is again quite implausible.
For another related consideration against \(\textsf{5}\), consider extensions of epistemic logic with a doxastic operator \(\textsf{B}_i\), where the condition \(\textsf{B}_i \varphi\) is read: “agent \(i\) believes that \(\varphi\).” Two attractive principles are:
\[\textsf{K}_i \varphi \to \textsf{B}_i \varphi\]
\[\tag{\textsf{D}} \textsf{B}_i \varphi \to \neg \textsf{B}_i \neg \varphi\]
The problem is that the combination of \((\textsf{5})\) with these two principles delivers an implausible consequence:
\[B_i K_ip \to K_i p\]
Proof. The key is to begin with a simple consequence of \(\textsf{5}\):
\[\begin{array}{lll} 1 & \neg \textsf{K}_i \varphi \to \textsf{K}_i \neg \textsf{K}_i \varphi & \textsf{5} \\ 2 & \textsf{K}_i \neg \textsf{K}_i \varphi \to \textsf{B}_i \neg \textsf{K}_i \varphi & \textsf{K}_i \to \textsf{B}_i\\ 3 & \textsf{B}_i \neg \textsf{K}_i \varphi \to \neg \textsf{B}_i \textsf{K}_i \varphi & \textsf{D} \ \text{for} \ \textsf{B}_i\\ 4 & \textsf{B}_i \textsf{K}_i \varphi \to \textsf{K}_i \varphi & \textsf{PL} \ 1, 2, 3 \end{array}\]
It follows that to believe that you know is sufficient for you to know, and no one can ever mistakenly believe that the know what they in fact fail to know. That seems utterly implausible.
What is known is known to be known.
\[\tag{\textsf{4}} \textsf{K}_i p \to \textsf{K}_i \textsf{K}_i p\]
This is the principle commonly known as the \(\textsf{K}\textsf{K}\)-principle. It encodes the view that knowledge is transparent to the agent: if you know something, then you know that you know. The thought is that agents with unlimited introspection capabilities ought to be able to recognize their own knowledge: agents should be able to introspectively attend to their reasons for belief, which should be conclusive in cases of knowledge and not defeasible by new information.
From a semantic point of view, \(\textsf{4}\) requires the \(i\)-accessibility relations to be transitive: if a state \(t\) is an genuine epistemic alternative for \(i\) at \(v\), and \(v\) is an epistemic alternative for \(i\) at \(u\), then \(t\) is an epistemic alternative for \(i\) at \(u\).
Hintikka (1962) adopted axioms \(\textsf{T}\) and \(\textsf{4}\) and identified \(\textsf{S4}\) as a candidate logic for knowledge. His reasons for that is that he regarded axioms \(\textsf{B}\) and \(\textsf{5}\) as implausible epistemic principles.
On the other hand, the interaction between knowledge and belief offers some reason to be concerned. For \(\textsf{4}\) immediately delivers:
\[\textsf{K}_i \varphi \to \textsf{B}_i \textsf{K}_i \varphi\]
Proof. The argument combines \(\textsf{4}\) with the principle that knowledge entails belief:
\[\begin{array}{lll} 1 & \textsf{K}_i \varphi \to \textsf{K}_i \textsf{K}_i \varphi & \textsf{4}\\ 2 & \textsf{K}_i \textsf{K}_i \varphi \to \textsf{B}_i \textsf{K}_i \varphi & \textsf{Knowledge entails belief}\\ 3 & \textsf{K}_i \varphi \to \textsf{B}_i \textsf{K}_i \varphi & \textsf{PL} \ 1, 2 \end{array}\]
In other words, I know something only if I believe that I know it.
The most influential argument against \(\textsf{4}\) comes from Timothy Williamson’s margin of error principles in Williamson (2000, chap. 5). Suppose you glance at the crowd in a stadium and estimate the attendance. Let \(p_n\) be the proposition that the true count is \(n\). Because your eyesight has limited powers of discrimination, you cannot tell apart crowds that differ by a single person. So, a margin of error principle looks plausible:
\[\begin{equation}\tag{\textsf{MEP}} \forall n\,(\textsf{K}\neg p_n \to \neg p_{n+1}). \end{equation}\]
In words, you know the count is not \(n\) only if it is not \(n+1\) either. Here is why. Suppose the true count were \(n+1\) and you believed it was not \(n\). A crowd of \(n\) would look exactly the same to you as this crowd, which means that you would have formed the same belief if the count had been \(n\), and then it would have been false. Your belief would be true only by luck, and a belief that is true by luck cannot be knowledge.
Now suppose you are reflective enough to know the margin of error principle for yourself. in combination with \(\textsf{4}\), it yields that you know the count is not \(p_{n}\) only if you know it is not \(p_{n+1}\):
Proof. We use a known instance of \(\textsf{MEP}\):
\[\begin{array}{lll} 1 & \textsf{K}\neg p_n \to \textsf{K}\textsf{K}\neg p_n & \textsf{4}\\ 2 & \textsf{K}(\textsf{K}\neg p_n \to \neg p_{n+1}) & \text{known instance of \textsf{MEP}}\\ 3 & \textsf{K}\textsf{K}\neg p_n \to \textsf{K}\neg p_{n+1} & \textsf{K}, 2\\ 4 & \textsf{K}\neg p_n \to\textsf{K}\neg p_{n+1} & \textsf{K},\ \textsf{PL},\ 1, 3 \end{array}\]
So if you know that the true count is not \(n\), you also know it is not \(n+1\). That is unacceptable. You surely know the count is not \(0\). A simple induction would now reveal that for every number \(n\), including the true count, you know that it is not the count of people in attendance. Something must give, and Williamson’s suggestion is to blame substitution instances of axiom \(\textsf{4}\).
9.1.2 Applications
9.1.2.1 The Unexpected Examination
The paradox of the unexpected examination arises when a teacher makes the announcement that there will be an exam next term, which will come as a surprise: students will not know on the morning of the exam, that it is that day. Students reason backwards. The exam cannot be on the last day of classes, since otherwise, they would know that the exam is that day. Given that, it cannot be on the penultimate day either: they ruled out the last day, which means that if the exam has not taken place by the penultimate day, then that would be the only available option. Similar reasons rule out other days until no day is left. Yet, the teacher gives the exam and the students are surprised.
Williamson (2000, chap. 6) suggests the same issue arises in a much simpler case, which he dubs Glimpse. Students know that the teacher circles all and only examination dates on her office calendar. From a distant glimpse, they note that exactly one date is circled, and that it is not very near the end of term, but they cannot narrow it down much further. Let \(e_n\) be the claim that the exam will take place \(n\) days before the end of term. That is, \(e_0\) is the claim that the exam will take place on the last day, and \(e_1\) is the claim that the exam will take place on the penultimate day. Because the glimpse is imprecise, the students’ knowledge is subject to a margin of error principle:
\[\tag{\textsf{MEP}} \forall n \,(\textsf{K}\neg e_n \to \neg e_{n+1}).\]
The glimpse is too coarse to rule out that the exam will take place \(n\) days before the end of term if the exam does in fact take place \(n+1\) days before the end of term. Because the students understand their situation, they are aware of this principle. Furthermore, they know from the glimpse that the exam will not take place on the very last day of term: \(\textsf{K} \neg e_0\). Given axiom \(\textsf{4}\), they are able to argue:
\[\textsf{K} \neg e_0 \to \textsf{K} \neg e_1\]
Proof. The argument uses a known instance of \(\textsf{MEP}\):
\[\begin{array}{lll} 1 & \textsf{K}\neg e_0 \to \textsf{K}\textsf{K}\neg e_0 & \textsf{4}\\ 2 & \textsf{K}(\textsf{K}\neg e_0 \to \neg e_{1}) & \text{known instance of \textsf{MEP}}\\ 3 & \textsf{K}\textsf{K}\neg e_0 \to \textsf{K}\neg e_{1} & \textsf{K}, 2\\ 4 & \textsf{K}\neg e_0 \to\textsf{K}\neg e_{1} & \textsf{K},\ \textsf{PL},\ 1, 3 \end{array}\]
But once they can rule out \(e_1\), by \(\textsf{4}\), they know that they know, and a similar argument enables them to rule out \(e_2\). More generally, we have:
\[\textsf{K} \neg e_n \to \textsf{K} \neg e_{n+1}\]
Students are thus in a position to rule out \(e_{n+1}\) once they rule out \(e_n\). That means that they are, on the face of it, able to rule out every day of term, and yet the exam takes place and they are surprised. Something must give again, and Williamson suggests that the students’ error is to rely on \(\textsf{4}\).
9.1.2.2 Fitch’s paradox of knowability
Some philosophers claim that what is true never outstrips what can be known: whatever is the case can, in principle, be known. When we read \(\Diamond \varphi\) as: “\(\varphi\) is metaphysically possible”, we may regiment the principle: \[p \to \Diamond \textsf{K}_i p \tag{\textsf{Knowability}}\] Fitch’s paradox is the observation that \(\textsf{Knowability}\) entails what looks like an implausible principle: \[\tag{\textsf{Knowledge}} p \to \textsf{K}_i p,\] according to which whatever is true is known.
Recall the observation that Moorean propositions cannot be known. If, unbeknownst to you, your iphone has been stolen, then we have this: \[p \wedge \neg \textsf{K}_i p\]This would be a perfectly ordinary truth that you could never come to know. To know the conjunction, you must come to know each conjunct, but as soon as you come to know the first conjunct, \(p\), the second conjunct, \(\neg \textsf{K}_i p\), becomes false and thus cannot be known. The formal argument requires only instances of \(\textsf{M}\) and \(\textsf{T}\): \[\begin{array}{lll} 1 & \textsf{K}_i(p \wedge \neg \textsf{K}_i p) \to (\textsf{K}_i p \wedge \textsf{K}_i \neg \textsf{K}_i p) & \textsf{M}\\ 2 & \textsf{K}_i \neg \textsf{K}_i p \to \neg \textsf{K}_i p & \textsf{T}\\ 3 & \neg \textsf{K}_i(p \wedge \neg \textsf{K}_i p) & \textsf{PL} \ 1, 2 \end{array}\]
Since the conclusion of the argument is a theorem, it depends only on logical and epistemic principles that should be available across possibilities. Given the rule of necessitation \(\textsf{RN}\) for \(\Box\), we obtain: \[\begin{array}{lll} 4 & \Box \neg \textsf{K}_i(p \wedge \neg \textsf{K}_i p) & \textsf{RN} \ 3\\ 5 & \neg \Diamond \textsf{K}_i(p \wedge \neg \textsf{K}_i p) & \textsf{Def} \ \Diamond \ 4 \end{array}\]
We are now in a position to appreciate how \(\textsf{Knowability}\) collapses into \(\textsf{Knowledge}\): \[\begin{array}{lll} 6 & (p \wedge \neg \textsf{K}_i p) \to \Diamond \textsf{K}_i(p \wedge \neg \textsf{K}_i p) & \textsf{Knowability}\\ 7 & p \to \textsf{K}_i p & \textsf{PL} \ 5, 6 \end{array}\]
That is, if \(p\) is an unknown truth, then the Moorean proposition \(p \wedge \neg \textsf{K}_i p\) becomes unknowable. It follows that if all truths are indeed knowable, then all truths are indeed known.
Consider the issue from a semantic point of view. A model for the hybrid language requires two accessibility relations: \(R_i\) for \(i\)’s knowledge and \(R_\Diamond\) for metaphysical possibility. \(\textsf{K}_i\varphi\) is true at \(w\) iff \(\varphi\) is true at every \(R_i\)-successor of \(w\), and \(\Diamond\varphi\) is true at \(w\) iff \(\varphi\) is true at some \(R_\Diamond\)-successor of \(w\).
Two points stand out. First, the application of \(\textsf{RN}\) in line 4 presupposes that line 3 obtains not just at the world of evaluation but at all \(R_\Diamond\)-accessible worlds. Since line 3 depends on \(\textsf{T}\), this requires \(R_i\) to be reflexive at every world.
Second, and more important, \(\Diamond\) shifts the world of evaluation for the embedded formula, which includes the inner \(\neg \textsf{K}_i p\), to another \(R_\Diamond\)-accessible world. Consider a world \(w\) at which \(p \wedge \neg \textsf{K}_i p\) is true, and a world \(v\) \(R_\Diamond\)-accessible from \(w\), where \(i\) has learned that \(p\).
\[\underset{p,\ \neg \textsf{K}_i p}{w} \quad \xrightarrow{\;R_\Diamond\;} \quad \underset{p,\ \textsf{K}_i p}{v}\]
For \(\textsf{Knowability}\) to be true at \(w\), \(\textsf{K}_i (p \wedge \neg \textsf{K}_i p)\) must be true at some \(R_\Diamond\)-accessible world \(u\). Since knowledge of the conjunction requires knowledge of the conjuncts, this has to be a world like \(v\), where \(i\) knows \(p\). But at \(v\), the second conjunct states that \(i\) does not know \(p\) at \(v\), not at \(w\). Since knowledge is factive, \(i\) cannot know the conjunction at \(v\) or at any other world at which she knows \(p\). On the face of it, what we want is a world like \(v\), where \(i\) knows that \(p\) and knows that she did not know \(p\) at \(w\). But the formula \(\textsf{K}_i (p \wedge \neg \textsf{K}_i p)\) cannot express this, because the inner \(\textsf{K}_i\) concerns the epistemic state of \(i\) at the world of evaluation. The paradox, on this view, arises because there are truths concerned with the agent’s epistemic situation, and coming to know them makes them false.
9.2 Information Flow
The main heuristic of epistemic logic is that agents locate themselves in the space of epistemic alternatives by ruling out states as epistemic alternatives in light of new information. The Muddy Children puzzle illustrates the dynamic aspect of this update mechanism:
Example 9.1 (Muddy Children) Three children \(a\), \(b\), and \(c\) have been playing outside when they are called back inside by their guardian. Two of them, say \(a\) and \(c\), have mud on their forehead, but none of them can see what is on their forehead. Each child, however, can see which of the other children are muddy. Once inside, the guardian asserts:
- At least one of you is muddy.
followed by an initial request:
- If you know you are muddy, please step forward.
None of the children step forward after the first request. Each child will see other children with mud in their forehead, but they do not yet know whether they themselves are muddy.
Matters change when she repeats the same request:
- If you know you are muddy, please step forward.
After the second request, the two muddy children, \(a\) and \(c\), will step forward while the other child, \(b\), stays behind. For \(a\) and \(c\) now know that they are muddy.
The example raises some questions:
Did the children learn anything new after the announcement that one of them was muddy? They each knew after all that some children were muddy. (We return to this question in ?sec-common-knowledge.)
What changed between the initial request when no one stepped forward and the later one when two muddy children did?
How did the muddy children \(a\) and \(c\) come to know that they had mud in their foreheads?
Here is a diagrammatic representation of the situation before the initial announcement.
We represent the relevant states of information with respect to the question at hand by ordered triples of digits, which encode the state of each child in that order. Thus for example:
- \(101\) encodes the actual state of the world on which \(a\) is muddy, \(b\) is not muddy, and \(c\) is muddy.
- \(111\) encodes an epistemic live option for \(b\) (though not for \(a\) or \(c\)) on which all three children are muddy.
- \(001\) encodes an epistemic live option for \(a\) (though not for \(b\) or \(c\)) on which only \(c\) is muddy.
The eight nodes correspond to eight states, which consist of different distributions of mud across the children. The nodes are connected by different accessibility relations, one for each child. When an edge labeled $a$ connects two nodes, the two states are indistinguishable as far as $a$ is concerned. Each relation is an equivalence relation, which means that the model is an $\textsf{S5}$ model. This is one case in which the idealization is harmless. Unlike the crowd at the stadium or the glimpse of the calendar, the children’s perception of one another is not subject to a margin of error: each child sees exactly who else is muddy, and the only thing she cannot see is her own forehead.
The effect of the announcement \(A\) is to let the children exclude \(000\) as a live epistemic option.
While announcement \(A\) excludes \(000\) as actuality, none of the children regarded \(000\) as an epistemic live option. That is because each child is able to see mud in the forehead of at least one other child.
The children learn valuable information from the fact that no one steps forward after the first request, \(B\), is made. This is because the children now learn that none of the other two children know that they are muddy. This suffices to rule out states at which exactly one child is muddy.
After the second request, \(C\), \(a\) and \(c\) will simultaneously step forward since they find no epistemically open alternative at which they are not muddy. On the other hand, \(b\) will stay back because she cannot tell which of \(101\) or \(111\) are actual. That is, \(b\) stays back because \(b\) cannot rule out that she is muddy. When \(a\) and \(c\) step forward, the children are able to eliminate every alternative to \(101\). So, the epistemic situation after the second request is that the children know exactly who is muddy and who is not.
Nothing changes when we complicate the situation. If, for example, seven out of ten children happened to be muddy, then no one would step forward until after the guardian makes the seventh request at which point exactly those seven children would simultaneously step forward.
9.2.1 Public Announcements
The diagrams suggest a simple update mechanism. Once a truth \(\varphi\) is announced, agents are in a position to eliminate states at which \(\varphi\) fails.
Definition 9.4 (Update) If \(M = (W, \{R_i: i\in I\}, V)\) and \(\varphi\) is a formula, the update of \(M\) by \(\varphi\) is the model \(M|\varphi = (W', \{R'_i: i \in I\}, V')\), where:
\(W' = \{s \in W : M, s \Vdash \varphi\}\),
\(R'_i = R_i \cap (W' \times W')\), and
\(V'(p) = V(p) \cap W'\)
We now add an operator \([!\varphi]\), where: \([!\varphi]\psi\) is read: “after the announcement of \(\varphi\), \(\psi\). Its truth clause is:
\[\begin{array}{lll} M, s \Vdash [!\varphi] \psi & \text{iff} & M, s \Vdash \varphi \ \text{only if} \ M|\varphi, s \Vdash \psi\\ \end{array}\]
The antecedent reflects the assumption that announcements are true. Notice that an update never undermines the structure of an \(\textsf{S5}\) model. \(R_i\) is reflexive, symmetric, or transitive only if its restriction \(R'_i\) is. So our discussion of the logic of knowledge in the static setting remains in place after the updates.
To return to the Muddy Children case, let \(p_i\) be the proposition that child \(i\) is muddy with \(a\), \(b\), and \(c\) are children \(1\), \(2\), and \(3\), respectively. Then, \(A\) is the announcement:
\[p_1 \vee p_2 \vee p_3\]
The effect of the announcement is to remove the state \(000\), which is exactly the transition from the first to the second diagram. Now, the failure to step forward after \(B\) is itself informative as it amounts to the public announcement that no child knows that they are muddy:
\[\neg \textsf{K}_a p_1 \wedge \neg \textsf{K}_b p_2 \wedge \neg \textsf{K}_c p_3\]
This formula is true at \(101\), since \(a\) cannot rule out \(001\) and \(c\) cannot rule out \(100\). It is false at every state with exactly one muddy child, since such a child sees no mud on any other child and, after \(A\), must know that they are muddy. The update removes those states, which is exactly the transition from the second to the third diagram.
Finally, when \(a\) and \(c\) step forward and \(b\) does not, they publicly announce:
\[\textsf{K}_a p_1 \wedge \neg \textsf{K}_b p_2 \wedge \textsf{K}_c p_3\]
Of the four states that remain, this formula is true only at \(101\). At \(011\) and \(111\), \(a\) cannot rule out a state at which she is clean, and at \(110\), \(c\) cannot. The update leaves a single state, which is the final diagram.
9.2.2 Unsuccessful Updates
Something remarkable happened above. The announcement of ignorance after request \(B\) was true at \(101\) when it was made. But after the update, \(a\) and \(c\) know that they are muddy, which means that the announced formula has become false. The children step forward precisely because the announcement of their ignorance refutes itself.
This is the dynamic counterpart of the Moorean observation from the previous section. For a propositional variable \(p\), announcing \(p\) invariably produces knowledge of \(p\):
\[[!p]\textsf{K}_i p\]
Once all states that remain satisfy \(p\), \(\textsf{K}_i p\) is true throughout the updated model. But once we announce a Moorean formula, it becomes false:
\[[!(p \wedge \neg \textsf{K}_i p)]\neg(p \wedge \neg \textsf{K}_i p)\]
After the update, all states that remain satisfy \(p\), so \(\textsf{K}_i p\) is likewise true throughout and the second conjunct fails. As observed above, if I tell you “your phone has been stolen, but you do not know it,” what I say may be perfectly true, but my announcement makes it false. Formulas that remain true after being announced are called successful, and those that do not are called unsuccessful.
Unsuccessful formulas leave a trace in the logic. The formula \([!p]\textsf{K}_i p\) is valid, but if we substitute \(p \wedge \neg \textsf{K}_i p\) for \(p\), we obtain \([!(p \wedge \neg \textsf{K}_i p)]\textsf{K}_i(p \wedge \neg \textsf{K}_i p)\), which is false at all states at which the announcement can be made. So, unlike the logics we have studied thus far, the logic of public announcements is not closed under uniform substitution.
Which formulas are safe? Call a formula persistent if, whenever it is true at a state, it remains true at that state after any update. Propositional formulas are persistent, since updates do not change the valuation at surviving states. So are formulas built from literals by \(\wedge\), \(\vee\), and \(\textsf{K}_i\): if \(\varphi\) is true at every \(R_i\)-successor of a state, it remains true at every successor that survives the update. What is not persistent is ignorance. A formula of the form \(\neg \textsf{K}_i \varphi\) says that some alternative is still open, and an update may close it. All persistent formula are successful, and Moorean formulas, which combine a fact with ignorance of it, are the paradigm of unsuccessful ones.
9.2.3 The Unexpected Examination Revisited
The update framework provides a new view of the unexpected examination paradox. Gerbrandy (2007) asks us to consider the simplest case, in which the exam is either on Monday (\(m\)) or on Tuesday (\(t\)), but not both. On Sunday, the student cannot tell the two states apart:
\[\underset{m}{w_m} \quad \overset{i}{\longleftrightarrow} \quad \underset{t}{w_t}\]
What does it mean for the exam to be a surprise? If the exam is on Monday, the student must not know on Sunday that it is on Monday. If it is on Tuesday, the student must not know it is on Tuesday even after learning, on Monday, that there was no exam that day. The teacher’s announcement is therefore:
\[S = (m \wedge \neg \textsf{K}_i m) \vee (t \wedge [!\neg m]\neg \textsf{K}_i t)\]
Evaluate \(S\) at each state:
- At \(w_m\), \(m\) is true and \(w_t\) is still open, so \(\neg \textsf{K}_i m\) holds, and \(S\) is true.
- At \(w_t\), the update by \(\neg m\) leaves only \(w_t\), so the student would know \(t\), and \(S\) is false.
So the student’s first step is sound: if the announcement is true, the exam is not on the last day. But now suppose the teacher announces \(S\) and the student takes her at her word. The update by \(S\) removes \(w_t\) and leaves only \(w_m\). At \(w_m\), the student now knows \(m\), so \(S\) is false:
\[M, w_m \Vdash S \wedge [!S]\neg S\]
The teacher’s announcement is unsuccessful. It can be true when made, but it cannot survive being accepted. The same analysis extends to longer terms. With three days, the first elimination remains sound. But after the update by \(S\), \(S\) itself fails at one of the remaining states, so the student no longer knows \(S\). The backward induction proceeds as if the student could keep eliminating days on the strength of an announcement she continues to know. That assumption is exactly what fails.
The model thus makes precise a diagnosis due to Kripke (2011). Kripke agrees that the students may know the announcement when it is made. What they cannot do is retain that knowledge as they acquire more information. As the exam-free days go by, they forget nothing, but what they learn undermines their knowledge of the announcement. This diagnosis competes with Williamson’s. On Williamson’s view, the students’ error is to rely on \(\textsf{4}\). On Kripke’s view, it is to assume that knowledge of the announcement survives the passage of time. In the update model, \(\textsf{4}\) holds throughout and the problem arises nonetheless, which suggests that \(\textsf{4}\) is not the only culprit.
9.2.4 Fitch’s Paradox Revisited
The dynamic framework suggests a different interpretation of the knowability thesis. Rather than read \(\Diamond \textsf{K}_i \varphi\) as metaphysical possibility, we may read it, following Benthem (2004), as learnability: \(\varphi\) can be known at \(s\) just in case some truth could be announced after which \(i\) knows \(\varphi\). In symbols, there is some formula \(\psi\) such that:
\[M, s \Vdash \psi \quad \text{and} \quad M|\psi, s \Vdash \textsf{K}_i \varphi\]
The question is now whether all truths are learnable in this sense. Moorean propositions are not, since \(\textsf{K}_i(p \wedge \neg \textsf{K}_i p)\) is false at all states of a reflexive model, updated or not. So, the dynamic interpretation cannot rescue an unrestricted knowability thesis. But it does yield a positive result. Persistent truths are learnable: just announce it. After the update, it remains true at all states that remain, and so \(i\) knows it. Unlearnable truths are those that concern the agent’s own ignorance, which is just what the earlier discussion of Fitch’s paradox led us to expect.
9.3 Group Knowledge
One question remains open from our discussion of the Muddy Children. What do the children learn after the first announcement? Even prior to the announcement, they all knew that some of the other children are muddy because they all could see at least one muddy child. And yet, the announcement makes a difference.
To make progress on that question, we distinguish some ways in which a group \(G\) may be said to know a proposition. Consider the contrast between four claims:
- Someone in \(G\) knows that \(\varphi\).
- Everyone in \(G\) knows that \(\varphi\).
- It is common knowledge in \(G\) that \(\varphi\).
- It is distributed knowledge in \(G\) that \(\varphi\).
The first two are familiar. The third requires not just that everyone know, but that everyone know that everyone knows, that everyone know that everyone know that everyone knows, etc. The fourth concerns what the group would know if its members pooled their information, even if no individual member knows it. This section introduces each type of group knowledge, explains how to evaluate it in a model, and how they are related to each other.
In what follows, \(G\) is a nonempty set of agents, \(G \subseteq I\). When \(G = I\), we drop the subscript.
9.3.1 Someone Knows and Everyone Knows
The first two types of group knowledge are definable in the language of epistemic logic. If \(G\) is finite, let:
\[\textsf{S}_G \varphi \ := \ \bigvee_{i \in G} \textsf{K}_i \varphi \qquad\qquad \textsf{E}_G \varphi \ := \ \bigwedge_{i \in G} \textsf{K}_i \varphi\]
\(\textsf{S}_G \varphi\) is read “someone in \(G\) knows that \(\varphi\),” and \(\textsf{E}_G \varphi\) is read “everyone in \(G\) knows that \(\varphi\)” or “it is general knowledge in \(G\) that \(\varphi\).”
Let us return to the model of the Muddy Children before the guardian’s announcement, where \(p_1\), \(p_2\), and \(p_3\) say that \(a\), \(b\), and \(c\), respectively, are muddy:
At the actual state \(101\), someone knows that \(c\) is muddy, since \(a\) can see her. But not everyone knows it, since \(c\) cannot see her own forehead:
\[M, 101 \Vdash \textsf{S}\, p_3 \wedge \neg \textsf{E}\, p_3\]
On the other hand, everyone knows that at least one child is muddy:
\[M, 101 \Vdash \textsf{K}_a (p_1 \vee p_2 \vee p_3) \wedge \textsf{K}_b (p_1 \vee p_2 \vee p_3) \wedge \textsf{K}_c (p_1 \vee p_2 \vee p_3)\]
That is, \(M, 101 \Vdash \textsf{E}(p_1 \vee p_2 \vee p_3)\).
9.3.2 Iterated General Knowledge
Thus everyone knows that someone is muddy even prior to the first announcement. Does everyone know that everyone knows it? We may now iterate the general knowledge operator:
\[\textsf{E}^1_G \varphi \ := \ \textsf{E}_G \varphi \qquad\qquad \textsf{E}^{n+1}_G \varphi \ := \ \textsf{E}_G \textsf{E}^n_G \varphi\]
\(\textsf{E}^2_G \varphi\) says that everyone knows that everyone knows that \(\varphi\), \(\textsf{E}^3_G \varphi\) adds a further layer, and there is no end to successive iterations. One way to picture these iterations is as follows. Call a state \(t\) is reachable from \(s\) in one step, in symbols \(sR^1_G t\), iff \(sR_i t\) for some \(i \in G\). And say that \(t\) is reachable from \(s\) in \(n+1\) steps, in symbols \(sR^{n+1}_G t\), iff for some state \(u\), \(sR^n_G u\) and \(uR_i t\) for some \(i \in G\). Then:
Proposition 9.1 \(M, s \Vdash \textsf{E}^n_G \varphi\) iff \(M, t \Vdash \varphi\) for every state \(t\) such that \(sR^n_G t\).
Proof. By induction on \(n\). For \(n = 1\), \(\textsf{E}_G \varphi\) is true at \(s\) iff each \(i \in G\) knows \(\varphi\) at \(s\), that is, iff \(\varphi\) is true at every state that is \(R_i\)-accessible from \(s\) for some \(i \in G\). Suppose the claim is true for \(n\). Then \(\textsf{E}^{n+1}_G \varphi = \textsf{E}_G \textsf{E}^n_G \varphi\) is true at \(s\) iff \(\textsf{E}^n_G\varphi\) is true at every \(u\) with \(sR^1_G u\), which by the induction hypothesis is true iff \(\varphi\) is true at every \(t\) reachable in \(n\) steps from some such \(u\), that is, at every \(t\) with \(sR^{n+1}_G t\).
In words, \(\textsf{E}^n \varphi\) fails at \(s\) just in case there is a path of length \(n\), each step of which may be taken by a different agent, from \(s\) to a state where \(\varphi\) is false.
Now we can see what the children lack before the announcement. In the initial model, there is a two-step path from \(101\) to \(000\):
\[101 \ R_a \ 001 \quad \text{and} \quad 001 \ R_c \ 000\]
Therefore:
\[M, 101 \Vdash \textsf{E}(p_1 \vee p_2 \vee p_3) \wedge \neg \textsf{E}^2(p_1 \vee p_2 \vee p_3)\]
In particular, \(a\) does not know that \(c\) knows that someone is muddy. The reason is simple. For all \(a\) knows, she herself is clean, in which case \(c\) sees only one clean child and no mud at all. So, for all \(a\) knows, \(c\) might believe that no child is muddy.
This example illustrates an important feature of the logic of \(\textsf{E}\). Recall that we described the model as a \(\textsf{S5}\)-model, which means that individual knowledge satisfies \(\textsf{4}\). And yet:
\[M, 101 \nVdash \textsf{E}\varphi \to \textsf{E}\textsf{E}\varphi\]
The \(\textsf{K}\textsf{K}\)-principle does not guarantee what we may call the \(\textsf{E}\textsf{E}\)-principle. Every individual may know \(\varphi\) in which case every individual knows that they know \(\varphi\), and yet everyone may know \(\varphi\) without knowing that everyone knows \(\varphi\).
The pattern generalizes. If exactly \(k\) children are muddy, then before the announcement, the fact that at least one child is muddy is \(\textsf{E}^{k-1}\) known but not \(\textsf{E}^k\) known. With two muddy children, it is general knowledge that someone is muddy but it is not general knowledge that it is general knowledge that someone is muddy. With three, it is \(\textsf{E}^2\) known but not \(\textsf{E}^3\) known.
9.3.3 Common Knowledge
A group has common knowledge that \(\varphi\) when all the iterations are true at once: everyone knows that \(\varphi\), everyone knows that everyone knows that \(\varphi\), etc. As a first approximation:
\[\textsf{C}_G \varphi \ \text{ iff } \ \textsf{E}_G \varphi \wedge \textsf{E}^2_G \varphi \wedge \textsf{E}^3_G \varphi \wedge \dots\]
Common knowledge plays a crucial role in social interaction. When we drive, for example, we rely on the fact that it is common knowledge that a red light requires drivers to stop. It is not enough for a pedestrian to know this rule. She needs to know that drivers know it, and drivers need to know that pedestrians know that they know it, and so on. Philosophers since Lewis (2008) have argued that conventions, such as driving on the right, depend on common knowledge of this sort.
Unlike \(\textsf{S}_G\) and \(\textsf{E}_G\), common knowledge cannot be defined in the language of epistemic logic, since that would require an infinite conjunction. We instead expand the language with a new operator \(\textsf{C}_G \varphi\), read: “it is common knowledge in \(G\) that \(\varphi\).” To evaluate common knowledge attributions, we consider whether a state \(t\) is reachable from \(s\) in a finite number of steps*:
- a state \(t\) is reachable from \(s\) in a finite number of steps, in symbols \(R^\star\), iff there is some \(n\) such that \(t\) is reachable from \(s\) in \(n\) steps.
That is, \(sR^\star_G t\), iff \(sR^n_G t\) for some \(n \geq 1\). Equivalently, \(R^\star_G\) is the transitive closure of the union of the relations \(R_i\) for \(i \in G\). The truth clause for \(\textsf{C}_G \varphi\) is:
\[\begin{array}{lll} M, s \Vdash \textsf{C}_G \varphi & \text{iff} & M, t \Vdash \varphi \ \text{for every} \ t \in W \ \text{such that} \ sR^\star_G t \end{array}\]
By Proposition 9.1, \(\textsf{C}_G \varphi\) is true at \(s\) iff \(\textsf{E}^n_G \varphi\) is true at \(s\) for every \(n \geq 1\), which matches the informal characterization.
We are now in a position to answer the question with which we began. Let us revisit the model for the Muddy Children Puzzle prior to the first announcement:
Before the announcement, \(000\) is reachable from \(101\) in two steps, which means:
\[M, 101 \nVdash \textsf{C}(p_1 \vee p_2 \vee p_3)\]
The announcement removes \(000\).
If we use \(M'\) for the updated model \(M|(p_1 \vee p_2 \vee p_3)\), the disjunction is now true at every state reachable from \(101\), which means:
\[M', 101 \Vdash \textsf{C}(p_1 \vee p_2 \vee p_3)\]
Thus the children do learn something from the announcement: \(a\) knows that \(c\) knows, \(b\) knows that \(a\) knows that \(c\) knows, etc at every level. The announcement turns general knowledge into common knowledge.
It matters that the announcement is public. Suppose instead that the guardian had whispered “at least one of you is muddy” to each child in private. Each child would hear something she already knew, no state would be eliminated, and no child would ever step forward. Every public announcement of a propositional fact \(p\) makes \(p\) common knowledge, since every state that survives the update satisfies \(p\):
\[[!p]\textsf{C}_G\, p\]
Private messages, by contrast, do not by themselves produce common knowledge, as we will see in a moment. Consider the later stages of the puzzle as well. After request B, the states with exactly one muddy child are eliminated:
It is now common knowledge that at least two children are muddy, since every state reachable from \(101\) has at least two muddy children. But it is not yet common knowledge that exactly two children are muddy, since \(111\) is still reachable from \(101\) (via \(b\)). Only after \(a\) and \(c\) step forward does the actual distribution of mud become common knowledge, since \(101\) is then the only state left:
The Logic of Common Knowledge
\(R^\star_G\) is a transitive relation, and it is reflexive whenever each \(R_i\) is. The relation is symmetric whenever each \(R_i\) is, since one can traverse a path from \(s\) to \(t\) in reverse. Therefore \(R^\star_G\) is an equivalence relation when each individual knowledge relation is. That would make common knowledge be governed by the principles of \(\textsf{S5}\). Contrast this with \(\textsf{E}_G\), which, as we saw, does not even satisfy \(\textsf{4}\).
One axiomatization of the logic of common knowledge adds an axiom and a rule of inference:
\[\tag{Fixed Point} \textsf{C}_G \varphi \to \textsf{E}_G(\varphi \wedge \textsf{C}_G \varphi)\]
\[\tag{Induction} \frac{\chi \to \textsf{E}_G(\varphi \wedge \chi)}{\chi \to \textsf{C}_G \varphi}\]
The Fixed Point axiom says that common knowledge that \(\varphi\) is general knowledge of two items: that \(\varphi\), and that it is common knowledge that \(\varphi\). In other words, \(\textsf{C}_G \varphi\) is a fixed point of the map that sends a formula \(X\) to \(\textsf{E}_G(\varphi \wedge X)\). The Induction rule says that it is the greatest such fixed point: anything that guarantees general knowledge of \(\varphi\) together with itself guarantees common knowledge of \(\varphi\).
To appreciate the fact that Induction preserves validity, suppose that \(\chi \to \textsf{E}_G(\varphi \wedge \chi)\) is valid and that \(\chi\) is true at \(s\). Then \(\varphi \wedge \chi\) is true at every state reachable from \(s\) in one step. Since \(\chi\) is true at each such state, the same reasoning shows that \(\varphi \wedge \chi\) is true at every state reachable from \(s\) in two steps, and so on. By induction on \(n\), \(\varphi\) is true at every state reachable from \(s\) in \(n\) steps, for every \(n\). So \(\textsf{C}_G \varphi\) is true at \(s\).
We are now in a position to prove some theorems of the logic of common knowledge. We drop the subscript \(G\).
Proposition 9.2 \(\vdash \textsf{C}p \to \textsf{E}\textsf{C}p\)
Proof. This is a simple consequence of the Fixed Point axiom: \[\begin{array}{lll} 1 & \textsf{C}p \to \textsf{E}(p \wedge \textsf{C}p) & \text{Fixed Point}\\ 2 & \textsf{E}(p \wedge \textsf{C}p) \to (\textsf{E}p \wedge \textsf{E}\textsf{C}p) & \textsf{M} \ \text{for each} \ \textsf{K}_i\\ 3 & \textsf{C}p \to \textsf{E}\textsf{C}p & \textsf{PL} \ 1, 2 \end{array}\]
Proposition 9.3 \(\vdash \textsf{C}p \to \textsf{C}\textsf{C}p\)
Proof. This is a simple consequence of the Induction rule: \[\begin{array}{lll} 1 & \textsf{C}p \to \textsf{E}\textsf{C}p & \textsf{Proposition 9.2}\\ 2 & \textsf{C}p \to \textsf{E}(\textsf{C}p \wedge \textsf{C}p) & \textsf{RE} \ 1\\ 3 & \textsf{C}p \to \textsf{C}\textsf{C}p & \text{Induction} \ [\textsf{C}p/\chi, \textsf{C}p/\varphi] \ 2 \end{array}\]
In line 2, \(\textsf{RE}\) is the rule of replacement of provable equivalents, here applied to \(\textsf{C}p \leftrightarrow (\textsf{C}p \wedge \textsf{C}p)\).
Is Common Knowledge Attainable?
Common knowledge is not difficult to obtain in the Muddy Children, where announcements are public and perception is perfect. Real communication is not often like that. Suppose two generals on opposite hills must attack at the same time to succeed, and can communicate only by messengers who may be captured on the way. General \(a\) sends the message “attack at dawn.” If it arrives, \(b\) knows the plan, but \(a\) does not know that \(b\) knows, so \(b\) sends an acknowledgment. If that arrives, \(a\) knows that \(b\) knows, but \(b\) does not know that \(a\) knows that \(b\) knows, and so on. Each successful message adds one level of iteration. No finite number of messages ever produces common knowledge.
Williamson’s margin of error principles raise a similar concern. If each iteration of knowledge based on inexact perception requires a further margin for error, then common knowledge of facts known by perception would require infinitely many margins (Williamson 2000, chap. 5). This suggests that common knowledge is best seen either as an idealization or as something attained only through public events whose occurrence is itself perfectly evident to all, like the guardian’s announcement.
Distributed Knowledge
Distributed knowledge takes us in the opposite direction. Common knowledge is very demanding for every member of the group. Distributed knowledge asks for what the group would know if its members combined what they know.
Here is a simple example. Ann knows that if the meeting is on Tuesday, it is in Room 101. Bob knows that the meeting is on Tuesday. Neither knows where the meeting is. But the information needed to work it out is present in the group, distributed between Ann and Bob. We write that it is distributed knowledge in \(\{\text{Ann}, \text{Bob}\}\) that the meeting is in Room 101.
How should we evaluate this? Each agent’s knowledge rules out some states. Combining information amounts to ruling out every state that some member of the group is able to rule out. The states that remain are those that every member of the group regards as epistemically open. So we take the intersection of the individual relations:
\[\begin{array}{lll} M, s \Vdash \textsf{D}_G \varphi & \text{iff} & M, t \Vdash \varphi \ \text{for every} \ t \in W \ \text{such that} \ sR_i t \ \text{for all} \ i \in G \end{array}\]
(Do not confuse the operator \(\textsf{D}_G\) with axiom \(\textsf{D}\) from modal propositional logic. The subscript will keep them apart.) Like \(\textsf{C}_G\), the operator \(\textsf{D}_G\) is added to the language as a new primitive. Since the intersection of equivalence relations is an equivalence relation, distributed knowledge obeys the principles of \(\textsf{S5}\) whenever individual knowledge does. One axiom, which we may call Inclusion, amounts to the claim that what is individually known is distributively known by the group:
\[\tag{Inclusion} \textsf{K}_i \varphi \to \textsf{D}_G \varphi \quad \text{for} \ i \in G\]
Distributed knowledge sheds new light on the Muddy Children. Before the announcement, the children’s information at \(101\) is as follows:
- \(a\) cannot distinguish \(101\) from \(001\).
- \(b\) cannot distinguish \(101\) from \(111\).
- \(c\) cannot distinguish \(101\) from \(100\).
The only state that all three regard as possible is \(101\) itself. So:
\[M, 101 \Vdash \textsf{D}(p_1 \wedge \neg p_2 \wedge p_3)\]
Before the guardian says a word, the exact distribution of mud is distributed knowledge among the children, even though no child knows it. Each child’s forehead is visible to the other two, which means that they collectively have access to the full configuration. The puzzle may thus be redescribed as a process that turns distributed knowledge into individual knowledge and, eventually, common knowledge, by means of public announcements, some of which are announcements of the children’s ignorance.
There is a subtlety here. Distributed knowledge describes what is implicit in the group’s information as it currently stands. It need not be what the group would know after actually communicating, since communication can change the very facts that the combined information describes. Suppose \(b\) knows that \(p\) and that \(a\) does not know that \(p\). Then it is distributed knowledge in \(\{a, b\}\) that \(p \wedge \neg \textsf{K}_a p\). But if \(b\) shares what she knows with \(a\), the second conjunct becomes false. This is the Moorean phenomenon we discussed in the last section once again.