Towards Syntactic Epistemic Logic

A typical case of (I) is the overspecification problem. Consider the following description:

A tossed coin lands heads up. Alice sees the coin, Bob does not.

(1)

Students in an epistemic logic class normally produce a Kripke S5-model of this situation as in Figure 1.

$\mathcal{M}_{1}$ is a model of (1) which, however, overspecifies (1): in this model there are propositions which are true but do not follow from (1), e.g.,

• •

  $\mathbf{K}_{A}\neg\mathbf{K}_{B}h$ - Alice knows that Bob does not know $h$;³³3$\mathbf{K}_{A}$ and $\mathbf{K}_{B}$ are knowledge modalities for Alice and Bob.

• •

  $\mathbf{K}_{B}(\mathbf{K}_{A}h\vee\mathbf{K}_{A}\neg h)$ - Bob knows that Alice knows whether $h$;

• •

  etc.

We will see in Section 4 that scenario (1) “as is” does not have a single-model specification at all.

In a situation in which an epistemic scenario is described syntactically but formalized as a model, a completeness analysis relating these two modes is required. For example, the Muddy Children puzzle is given syntactically but then presented as a model tacitly presumed to be commonly known (cf. [14, 16, 17, 18, 19]). In Section 5, we show that this choice of a specifying model can be justified. However, the Muddy Children case is a fortuitous exception: see Sections 5 and 6 for more epistemic scenarios without single model specifications.

Existing approaches to mitigate overspecification include

• •

  Supervaluations: given a syntactically defined situation $\cal S$, assume

  “$F$ holds in $\cal S$” iff “$F$ is true in all models of $\cal S$.”

  This approach has been dominant in mathematical logic with formal theories as “situations,” and it manifests itself in Gödel’s Completeness Theorem.

• •

  Non-standard truth values: Kleene three-valued logic or other, more exotic ways of defining truth values. This approach has generated mathematically attractive models, but it has neither dethroned the supervaluation tradition in mathematical logic, nor changed the ill-founded “natural model culture” in epistemology.

Here we explore the supervaluation approach in epistemology by representing epistemic scenarios in a logical language syntactically and considering the whole class of the corresponding models, not just one cherrypicked model. This also eliminates problem (II).

For a given set of formulas $\Gamma$ (here called “hypotheses” or “assumptions”) we consider derivations from $\Gamma$: assume all ${\sf S5}_{n}$-theorems, $\Gamma$, and use classical reasoning (rule Modus Ponens). The notation

$$\Gamma\vdash A$$

(5)

represents $A$ is derivable from $\Gamma$.

It is important to distinguish the role of necessitation in reasoning without assumptions (4) and in reasoning from a nonempty set of assumptions (5). In (4), necessitation can be used freely: what is derived from logical postulates ($\vdash A$) is known ($\vdash\mathbf{K}_{i}A$). In (5), the rule of necessitation is not postulated: if $A$ follows from a set of assumptions $\Gamma$, we cannot conclude that $A$ is known, since $\Gamma$ itself can be unknown. However, for some “good” sets of assumptions $\Gamma$, necessitation is a valid rule (cf. $\Gamma_{3}$ from Example 4.2, ${\sf MC}_{n}$ from Section 5).

We will also use abbreviations: for “everybody’s knowledge”

$${\bf E}X={\mathbf{K}_{1}}X\wedge\ldots\wedge{\mathbf{K}_{n}}X,$$

and “common knowledge”

$${\bf C}X=\{X,\ {\bf E}X,\ {\bf E}^{2}X,\ {\bf E}^{3}X,\ \ldots\}.$$

As one can see, ${\bf C}X$ is an infinite set of formulas. Since modalities $\mathbf{K}_{i}$ commute with the conjunction, ${\bf C}X$ is provably equivalent to the set of all formulas which are $X$ prefixed by iterated knowledge modalities:

$${\bf C}X=\{P_{1}P_{2}\ldots P_{k}X\mid k=0,1,2,\ldots,\ \ P_{i}\in\{\mathbf{K}_{1},\ldots,\mathbf{K}_{n}\}\}.$$

Naturally,

$${\bf C}\Gamma=\bigcup\{{\bf C}F\mid F\in\Gamma\}$$

that states “$\Gamma$ is common knowledge.”

The set of formulas ${\bf C}X$ emulates common knowledge of $X$ using the conventional modalities $\{\mathbf{K}_{1},\ldots,\mathbf{K}_{n}\}$. This allows us to speak, to the extent we need here, about common knowledge without introducing a special modality and new principles.

The following proposition states that the rule of necessitation corresponds to common knowledge of all assumptions. If $\Gamma,\Delta$ are sets of formulas, then $\Gamma\vdash\Delta$ means $\Gamma\vdash X$ for each $X\in\Delta$.

The Completeness Theorem claims that if $\Gamma$ does not derive $F$, then there is a model $({\cal M},u)$ of $\Gamma$ in which $F$ is false. Where does this model come from?

The standard answer is given by the canonical model construction. In any model $({\cal M},u)$ of $\Gamma$, the set of truths $\cal T$ contains $\Gamma$ and is maximal, i.e., for each formula $F$,

$$F\in{\cal T}\ \ \ \mbox{ or }\ \ \ \neg F\in{\cal T}.$$

This observation suggests the notion of a possible world as a maximal set of formulas $\Gamma$ which is consistent, i.e., $\Gamma\not\vdash\bot$.

A canonical model ${\cal M}({\sf S5}_{n})$ of ${\sf S5}_{n}$ (cf. [10, 11, 13, 14, 15, 16]) consists of all possible worlds over ${\sf S5}_{n}$. Accessibility relations are defined on the basis of what is known at each world: for maximal consistent sets $\alpha$ and $\beta$,

$\alpha R_{i}\beta\ \ \$ iff $\ \ \ \alpha_{\mathbf{K}_{i}}\subseteq\beta$

where

$$\alpha_{\mathbf{K}_{i}}=\{F\mid\mathbf{K}_{i}F\in\alpha\},$$

i.e.,

$$\mbox{\em all facts that are known at $\alpha$ are true at $\beta$}.$$

Evaluations of atomic propositions are defined accordingly:

$$\alpha\!\Vdash\!p_{i}\ \ \mbox{ iff }\ \ p_{i}\in\alpha.$$

The standard Truth Lemma shows that Kripkean truth values in the canonical model agree with possible worlds: for each formula $F$,

$$\alpha\!\Vdash\!F\ \ \mbox{ iff }\ \ F\in\alpha.$$

The canonical model ${\cal M}({\sf S5}_{n})$ of ${\sf S5}_{n}$ serves as a parametrized universal model for each consistent epistemic scenario $\Gamma$. Given $\Gamma$, by the well-known Lindenbaum construction, extend $\Gamma$ to a maximal consistent set $\alpha$. By definition, $\alpha$ is a possible world in ${\cal M}({\sf S5}_{n})$. By the Truth Lemma, all formulas from $\Gamma$ hold in $\alpha$:

$${\cal M}({\sf S5}_{n}),\alpha\ \!\Vdash\!\ \Gamma.$$

The following observation provides a necessary and sufficient condition for semantic definability. Let $\Gamma$ be a consistent set of formulas in the language of ${\sf S5}_{n}$.¹¹¹¹11The same criteria hold for any other normal modal logic which has a canonical model in the usual sense.

Theorem 4.3 shows serious limitations of semantic definitions. Since, intuitively, deductively complete scenarios $\Gamma$ are exceptions, “most” epistemic situations cannot be defined semantically.

In Section 5.4, we provide a yet another example of an incomplete but meaningful epistemic scenario, a natural variant of the Muddy Children puzzle, which, by Theorem 4.3 does not have a semantic definition, but can nevertheless be easily specified and analyzed syntactically.

In Section 6, we consider an example of an extensive game with incomplete epistemic description which cannot be defined semantically, but admits an easy syntactic analysis.

This can be described in ${\sf S5}_{n}$ with modalities $\mathbf{K}_{1},\mathbf{K}_{2},\ldots,\mathbf{K}_{n}$ for the children’s knowledge and atomic propositions $m_{1},m_{2},\ldots,m_{n}$ with $m_{i}$ stating “child $i$ is muddy.” The initial configuration, which we call ${\sf MC}_{n}$, includes common knowledge assertions of the following assumptions:

1. Knowing about the others:

$$\bigwedge_{i\neq j}[\mathbf{K}_{i}(m_{j})\vee\mathbf{K}_{i}(\neg m_{j})].$$

2. Not knowing about themselves:

$$\bigwedge_{i=1,\ldots,n}[\neg\mathbf{K}_{i}(m_{i})\wedge\neg\mathbf{K}_{i}(\neg m_{i})].$$

Transition from the verbal description of the situation to ${\sf MC}_{n}$ is a straightforward formalization of a given syntactic description to another, logic friendly syntactic form.

In the standard semantic solution, the set of assumptions ${\sf MC}_{n}$ is replaced by a Kripke model: $n$-dimensional cube $Q_{n}$ ([14, 16, 17, 18, 19]). To keep things simple, we consider the case $n=k=2$.

Logical possibilities for the truth value combinations¹²¹²12$1$ standing for ‘true’ and $0$ for ‘false’ of $(m_{1},m_{2})$, namely (0,0), (0,1), (1,0), and (1,1) are declared possible worlds. There are two indistinguishability relations denoted by solid arrows (for 1) and dotted arrows (for 2). It is easy to check that conditions 1 (knowing about the others) and 2 (not knowing about themselves) hold at each node of this model. Furthermore, $Q_{2}$ is assumed to be commonly known.

After the father publicly announces $m_{1}\vee m_{2}$, node $(0,0)$ is no longer possible and model $\mathcal{M}_{2}$ now becomes common knowledge. Both children realize that in $(1,0)$, child 2 would know whether (s)he is muddy (no other 2-indistinguishable worlds), and in $(0,1)$, child 1 would know whether (s)he is muddy. After both children answer “no” to whether they know what is on their foreheads, worlds $(1,0)$ and $(0,1)$ are no longer possible, and each child eliminates them. The only remaining logical possibility here is model ${\cal M}_{3}$. Now both children know that their foreheads are muddy.

The semantic solution in Section 5.2 adopts $Q_{n}$ as a semantic equivalent of a theory ${\sf MC}_{n}$. Can this choice of the model be justified? In the case of Muddy Children, the answer is ‘yes.’

Let $u$ be a node at $Q_{n}$. i.e., $u$ is an $n$-tuple of $0$’s and $1$’s and $u\!\Vdash\!m_{i}$ iff $i$’s projection of $u$ is $1$. Naturally, $u$ is represented by a formula $\pi(u)$:

$$\pi(u)=\bigwedge\{m_{i}\mid u\!\Vdash\!m_{i}\}\wedge\bigwedge\{\neg m_{i}\mid u\!\Vdash\!\neg m_{i}\}.$$

It is obvious that $v\!\Vdash\!\pi(u)$ iff $v=u$.

By ${\sf MC}_{n}(u)$ we understand the Muddy Children scenario with specific distribution of truth values of $m_{i}$’s corresponding to $u$:

$${\sf MC}_{n}(u)={\sf MC}_{n}\cup\{\pi(u)\}.$$

So, each specific instance of Muddy Children is formalized by an appropriate ${\sf MC}_{n}(u)$.

To establish the ‘if’ direction, we first note that, by Proposition 3.2, necessitation is admissible in ${\sf MC}_{n}$: for each $F$,

$${\sf MC}_{n}\vdash F\ \ \Rightarrow\ \ \ {\sf MC}_{n}\vdash\mathbf{K}_{i}F.$$

The theorem now follows from the statement ${\cal S}(F)$:

for all nodes $u\in Q_{n}$,

$$Q_{n},u\!\Vdash\!F\ \ \ \ \Rightarrow\ \ \ {\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!F$$

and

$$Q_{n},u\!\Vdash\!\neg F\ \ \ \Rightarrow\ \ {\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!\neg F.$$

We prove that ${\cal S}(F)$ holds for all $F$ by induction on $F$.

The case $F$ is one of the atomic propositions $m_{1},m_{2},\ldots,m_{n}$ is trivial since ${\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!m_{i}$, if $u\!\Vdash\!m_{i}$ and ${\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!\neg m_{i}$, if $u\!\Vdash\!\neg m_{i}$. The Boolean cases are also straightforward.

The case $F=\mathbf{K}_{i}X$. Consider the node $u^{i}$ which differs from $u$ only at the $i$-coordinate. Without a loss of generality, we may assume that $u\!\Vdash\!m_{i}$ and $u^{i}\!\Vdash\!\neg m_{i}$; the alternative $u\!\Vdash\!\neg m_{i}$ and $u^{i}\!\Vdash\!m_{i}$ is similar.

Suppose $Q_{n},u\!\Vdash\!\mathbf{K}_{i}X$. Then $Q_{n},u\!\Vdash\!X$ and $Q_{n},u^{i}\!\Vdash\!X$. By the induction hypothesis,

${\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!X\ \$ and $\ \ {\sf MC}_{n}\vdash\pi(u^{i})\!\rightarrow\!X$.

By the rules of logic (splitting premises)

${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!(m_{i}\!\rightarrow\!X)\ \$ and $\ \ {\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!(\neg m_{i}\!\rightarrow\!X)$,

where $\pi(v)_{-i}$ is $\pi(v)$ without its $i$-th coordinate¹⁴¹⁴14Formally, $\pi(v)_{-i}=\bigwedge\{m_{j}\mid v\!\Vdash\!m_{j},\ j\neq i\}\wedge\bigwedge\{\neg m_{j}\mid v\!\Vdash\!\neg m_{j},\ j\neq i\}$. . By further reasoning,

${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!X$.

By necessitation in ${\sf MC}_{n}$, and distributivity,

${\sf MC}_{n}\vdash\mathbf{K}_{i}\pi(u)_{-i}\!\rightarrow\!\mathbf{K}_{i}X$.

By ‘knowing about the others’ principle, and since $\pi(u)_{-i}$ contains only atoms other them $m_{i}$,

${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!\mathbf{K}_{i}\pi(u)_{-i}$,

hence

${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!\mathbf{K}_{i}X$,

and

${\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!\mathbf{K}_{i}X$.

Now suppose $Q_{n},u\!\Vdash\!\neg\mathbf{K}_{i}X$. Then $Q_{n},u\!\Vdash\!\neg X$ or $Q_{n},u^{i}\!\Vdash\!\neg X$. By the induction hypothesis,

${\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!\neg X\ \$ or $\ \ {\sf MC}_{n}\vdash\pi(u^{i})\!\rightarrow\!\neg X$.

In the former case we immediately get ${\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!\neg\mathbf{K}_{i}X$, by reflection $\neg X\!\rightarrow\!\neg\mathbf{K}_{i}X$. So, consider the latter, i.e., ${\sf MC}_{n}\vdash\pi(u^{i})\!\rightarrow\!\neg X$. As before,

$${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!(\neg m_{i}\!\rightarrow\!\neg X).$$

By contrapositive,

$${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!(X\!\rightarrow\!m_{i}).$$

By necessitation and distribution,

$${\sf MC}_{n}\vdash\mathbf{K}_{i}\pi(u)_{-i}\!\rightarrow\!(\mathbf{K}_{i}X\!\rightarrow\!\mathbf{K}_{i}m_{i}).$$

By ‘knowing about others,’ as before,

$${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!(\mathbf{K}_{i}X\!\rightarrow\!\mathbf{K}_{i}m_{i}).$$

By ‘not knowing about himself,’ ${\sf MC}_{n}\vdash\neg\mathbf{K}_{i}m_{i}$, hence

$${\sf MC}_{n}\vdash\pi(u)_{-i}\!\rightarrow\!\neg\mathbf{K}_{i}X,$$

and

$${\sf MC}_{n}\vdash\pi(u)\!\rightarrow\!\neg\mathbf{K}_{i}X.\vskip 3.0pt plus 1.0pt minus 1.0pt$$

As we see, in the case of Muddy Children given by a syntactic description, ${\sf MC}_{n}(u)$, picking one “natural model” $(Q_{n},u)$ could be justified. However, in a general setting, the approach

given a syntactic description, pick a “natural model”

is intrinsically flawed: by Theorem 4.3, in many (intuitively, most) cases, there is no model description at all. Furthermore, if there is a “natural model,” a completeness analysis in the style of what we did for ${\sf MC}_{n}$ in Theorem 5.1 is required.

Here is a natural modification, ${\sf MCE}_{n,k}$, of the standard Muddy Children.

A group of $n$ children meet their father after playing in the mud. Each child sees everybody else’s foreheads. The father says: “$k$ of you are muddy” after which it becomes common knowledge that all children know whether they are muddy. Why?

This description does not specify whether children initially know if they are muddy; hence the initial description of ${\sf MCE}_{n,k}$ is, generally speaking, not complete¹⁵¹⁵15In particular, prior to father’s announcement ${\sf MCE}_{2,2}$ does not specify whether $\mathbf{K}_{1}m_{1}$ holds or not.. By Theorem 4.3, the initial ${\sf MCE}_{2,2}$ is not semantically definable. Therefore, ${\sf MCE}_{2,2}$ cannot be treated by “natural model” methods.

However, here is a syntactic analysis of ${\sf MCE}_{n,k}$ which can be shaped as a formal logical reasoning within an appropriate extension of ${\sf S5}_{n}$.

After father’s announcement, each child knows that if she sees $k$ muddy foreheads, then she is not muddy, and if she sees $k\!-\!1$ muddy foreheads, she is muddy: this secures that each child knows whether she is muddy. Moreover, everybody can reflect on this reasoning and this makes it common knowledge that each child knows whether she is muddy.

If we want to go beyond complete epistemic scenarios, we need a mathematical apparatus to handle classes of models, and not just single models. The format of syntactic specifications in some version of the modal epistemic language is a viable candidate for such an apparatus.

The traditional model solution of ${\sf MC}_{n}$ without completeness analysis uses a strong additional assumption – common knowledge of a specific model $Q_{n}$ and hence, strictly speaking, does not resolve the original Muddy Children puzzle; it rather corresponds to a different scenario of a more tightly controlled epistemic states of agents, e.g.,

A group of robots programmed to reason about model $Q_{n}$ meet their programmer after playing in the mud. …

One could argue that the given model solution of ${\sf MC}_{n}$ actually codifies some deductive solution in the same way that geometric reasoning is merely a visualization of a rigorous derivation in some sort of axiom system for geometry. This is a valid point which can be made scientific within the framework of Syntactic Epistemic Logic.

Models of complete $\Gamma$’s provided by Theorem 4.3 are instances of the canonical model ${\cal M}({\sf S5}_{n})$ at nodes $\widetilde{\Gamma}$ corresponding to $\Gamma$. This generic solution is, however, not satisfactory because of the highly nonconstructive nature of the canonical model ${\cal M}({\sf S5}_{n})$.

As was shown in [8], the canonical model ${\cal M}({\sf S5}_{n})$ for any $n\geq 1$ has continuum-many possible worlds even with just one propositional letter. This alone renders models $({\cal M}({\sf S5}_{n}),\widetilde{\Gamma})$ not knowable under any reasonable meaning of “known.” The canonical model for ${\sf S5}_{n}$ is just too large to be considered known and hence does not a priori satisfy the knowability of the model requirement II from Section 1.

This observation suggests that the question about existence of an epistemically acceptable (“known”) model for a given deductively complete set $\Gamma$ requires a case-by-case consideration.

Epistemic models of even simple and complete scenarios can be prohibitively large compared to their syntactic descriptions. For example, the Muddy Children model $Q_{n}$ is exponential in $n$ whereas its syntactic description ${\sf MC}_{n}$ is quadratic in $n$.

Consider a real-life epistemic situation after the cards have been initially dealt in the game of poker. One can show that for each distribution of cards, its natural syntactic description in epistemic logic is deductively complete ([5]) and hence admits a model characterization. Moreover, it has a natural finite model of the type given in [14] with hands as possible worlds and with straightforward knowledge relations. However, with 52 cards and 4 players there are over $10^{24}$ different combinations of hands. This yields that explicit formalization of the model not practical. Players reason using concise syntactic descriptions of the rules of poker and of its “large” model in the natural language, which can also be syntactically formalized in some kind of extension of epistemic logic.

In this and some other real life situations, models are prohibitively large whereas appropriate syntactic descriptions can be quite manageable.

The author is grateful to Adam Brandenburger, Alexandru Baltag, Johan van Benthem, Robert Constable, Melvin Fitting, Vladimir Krupski, Anil Nerode, Elena Nogina, Eoin Moore, Vincent Peluce, Tudor Protopopescu, Bryan Renne, Richard Shore, and Cagil Tasdemir for useful discussions. Special thanks to Karen Kletter for editing early versions of this text.