22 2118

Towards Syntactic Epistemic Logic

# Towards Syntactic Epistemic Logic

Sergei Artemov
The Graduate Center Address for correspondence: The Graduate Center, The City
University of New York, 365 Fifth Avenue, New York City, NY 10016, USA. The
City University of New York
365 Fifth Avenue  New York City  NY 10016  USA
<EMAIL_ADDRESS>
###### Abstract

Traditionally, Epistemic Logic represents epistemic scenarios using a single
model. This, however, covers only complete descriptions that specify truth
values of all assertions. Indeed, many—and perhaps most—epistemic descriptions
are not complete. Syntactic Epistemic Logic, SEL, suggests viewing an
epistemic situation as a set of syntactic conditions rather than as a model.
This allows us to naturally capture incomplete descriptions; we discuss a case
study in which our proposal is successful. In Epistemic Game Theory, this
closes the conceptual and technical gap, identified by R. Aumann, between the
syntactic character of game-descriptions and semantic representations of
games.

††volume: 186††issue: 1-4

##  1 Introduction

In this paper, we argue for a paradigm shift in the way that logic and
epistemic-related applications – in particular, game theory – specify
epistemic scenarios.111The preliminary version of this paper was delivered as
an invited talk at the 15th LMPS Congress in 2015 [3]. Given a verbal
description of a situation, a typical epistemic user cherrypicks a “natural
model” (Kripke or Aumann’s) and then regards it as a formalization of the
original description. This approach carries with it two fundamental
deficiencies:

> I. It covers only complete descriptions, whereas many (intuitively most)
> epistemic situations are partially described and cannot be adequately
> specified by a single model.222Epistemic logicians have been mostly aware of
> (I) but this did not stop the wide spread culture of identifying an
> epistemic scenario with a single Kripke model (or Aumann structure in Game
> Theory).
>
> II. The traditional epistemic reading of Kripke/Aumann models requires
> common knowledge of the model which restricts their generality and utility
> even further.

###  1.1 Overspecification

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.

$\textstyle{2}$$\textstyle{1}$$\textstyle{h}$$\textstyle{\neg
h}$$\textstyle{R_{B}}$$\textstyle{R_{A,B}}$$\textstyle{R_{A,B}}$$\textstyle{\bullet}$$\textstyle{\bullet}$

Figure 1: Model $\mathcal{M}_{1}$.

In this model, there are two possible worlds 1 and 2, arrows represent
indistinguishability relations $R_{A}$ and $R_{B}$ between worlds, $h$ is a
propositional letter for “heads,” and node 1 represents the real world at
which $h$ holds.

$\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$;333$\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).

##  2 What is Syntactic Epistemic Logic?

The name Syntactic Epistemic Logic was suggested by Robert Aumann (cf. [9])
who identified the conceptual and technical gap between the syntactic
character of game descriptions and the predominantly semantic way of analyzing
games via relational/partition models.

Suppose the initial description ${\cal I}$ of an epistemic situation is
syntactic in a natural language. The long-standing tradition in epistemic
logic and game theory is then to proceed to a specific epistemic model ${\cal
M}_{\cal I}$, and take the latter as a mathematical definition of ${\cal I}$:

$\mbox{\it informal description $\cal I$}\ \ \Rightarrow\ \mbox{\it``natural
model'' ${\cal M}_{\cal I}$.}$ (2)

Hidden dangers lurk within this process: a syntactic description $\cal I$ may
have multiple models and picking one of them (especially declaring it common
knowledge) is not generally sound. Furthermore, if we seek an exact
specification, then only deductively complete scenarios can be represented
(cf. Theorem 4.3). Epistemic scenarios outside this group, which include
situations with asymmetric and less-than-common knowledge (e.g., mutual
knowledge) of conditions, do not have single-model presentations, but can be
specified and handled syntactically.

Through the framework of Syntactic Epistemic Logic, SEL, we suggest making the
syntactic formalization ${\cal S}_{\cal I}$ a formal definition of the
situation described by $\cal I$:

$\mbox{\it description $\cal I$}\ \Rightarrow\ \mbox{\it syntactic
formalization ${\cal S}_{\cal I}$}\Rightarrow\mbox{\it all of ${\cal S}_{\cal
I}$'s models.}$ (3)

The first step from $\cal I$ to ${\cal S}_{\cal I}$ is formalization and it
has its own subtleties which we will not analyze here.

The SEL approach (3), we argue, encompasses a broader class of epistemic
scenarios than a semantic approach (2). In this paper, we provide motivations
and sketch basic ideas of Syntactic Epistemic Logic. Specific suggestions of
general purpose formal systems is a work in progress, cf. [4].

SEL provides a more balanced view of the epistemic universe as being comprised
of two inseparable entities, syntactic and semantic. Such a dual view of
objects is well-established in mathematical logic where the syntactic notion
of a formal theory is supplemented by the notion of a class of all its models.
One could expect equally productive interactions between syntax and semantics
in epistemology as well.

The definition of a game with epistemic conditions, cf. [6, 7], was originally
semantic in a single-model format. In more recent papers (cf. [1, 9]), Aumann
acknowledges the deficiencies of purely semantic formalizations and asks for
some kind of “syntactic epistemic logic” to bridge a gap between the syntactic
character of game descriptions and the semantic way of analyzing games.

In this paper, we look at extensive games; the syntactic epistemic approach to
strategic games has been tried in [2]. However, neither of these papers
considers Epistemic Game Theory in its entirety, including probabilistic
belief models, cf. [12]; we leave this for future studies.

##  3 Logical postulates and derivations

We consider the language of classical propositional logic augmented by
modalities $\mathbf{K}_{i}$, for agent $i$’s knowledge, $i=1,2,\ldots,n$. For
the purposes of this paper, we consider the usual “knowledge postulates” (cf.
[10, 13, 14, 16, 19]) corresponding to the multi-agent modal logic ${\sf
S5}_{n}$:444The same approach works for other epistemic modal logics.

  * •

classical logic postulates and rule Modus Ponens $A,A\\!\rightarrow\\!B\vdash
B$;

  * •

distributivity:
$\mathbf{K}_{i}(A\\!\rightarrow\\!B)\\!\rightarrow\\!(\mathbf{K}_{i}A\\!\rightarrow\\!\mathbf{K}_{i}B)$;

  * •

reflection: $\mathbf{K}_{i}A\\!\rightarrow\\!A$;

  * •

positive introspection:
$\mathbf{K}_{i}A\\!\rightarrow\\!\mathbf{K}_{i}\mathbf{K}_{i}A$;

  * •

negative introspection:
$\neg\mathbf{K}_{i}A\\!\rightarrow\\!\mathbf{K}_{i}\neg\mathbf{K}_{i}A$;

  * •

necessitation rule: $\vdash A\ \ \Rightarrow\ \ \vdash\mathbf{K}_{i}A$.

A derivation in ${\sf S5}_{n}$ is a derivation from ${\sf S5}_{n}$-axioms by
${\sf S5}_{n}$-rules (Modus Ponens and necessitation). The notation

$\vdash A$ (4)

is used to represent the fact that $A$ is derivable in ${\sf S5}_{n}$.

###  3.1 Derivations from hypotheses

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).

###### Example 3.1

If we want to describe a situation in which proposition $m$ is known to agent
1, we consider the set of assumptions $\Gamma$:

$\Gamma=\\{\mathbf{K}_{1}m\\}.$

From this $\Gamma$, by reflection principle
$\mathbf{K}_{1}m\\!\rightarrow\\!m$ from ${\sf S5}_{n}$, we can derive $m$,

$\Gamma\vdash m.$

Likewise, we can conclude ‘1 knows that 1 knows $m$’ by using positive
introspection:

$\Gamma\vdash\mathbf{K}_{1}\mathbf{K}_{1}m.$

However, we cannot conclude that agent 2 knows $m$:

$\Gamma\not\vdash\mathbf{K}_{2}m.$

This is rather clear intuitively since when assuming ‘1 knows $m$,’ we do not
settle the question of whether ‘2 knows $m$.’555A rigorous proof of this non-
derivability can be made by providing a counter-model. Therefore, there is no
necessitation in this $\Gamma$, since we have $\Gamma\vdash m$ but
$\Gamma\not\vdash\mathbf{K}_{2}m$.

###  3.2 Common knowledge and necessitation

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$.

###### Proposition 3.2

A set of formulas $\Gamma$ is closed under necessitation if and only if
$\Gamma\vdash{\bf C}\Gamma$, i.e., that $\Gamma$ proves its own common
knowledge.

###### Proof 3.3

Direction ‘if.’ Assume $\Gamma\vdash{\bf C}\Gamma$ and prove by induction on
derivations that $\Gamma\vdash X$ yields $\Gamma\vdash\mathbf{K}_{i}X$. For
$X$ being a theorem of ${\sf S5}_{n}$, this follows from the rule of
necessitation in ${\sf S5}_{n}$. For $X\in\Gamma$, it follows from the
assumption that $\Gamma\vdash{\bf C}X$, hence $\Gamma\vdash\mathbf{K}_{i}X$.
If $X$ is obtained from Modus Ponens, $\Gamma\vdash Y\\!\rightarrow\\!X$ and
$\Gamma\vdash Y$. By the induction hypothesis,
$\Gamma\vdash\mathbf{K}_{i}(Y\\!\rightarrow\\!X)$ and
$\Gamma\vdash\mathbf{K}_{i}Y$. By the distributivity principle of ${\sf
S5}_{n}$, $\Gamma\vdash\mathbf{K}_{i}X$.

For ‘only if,’ suppose that $\Gamma$ is closed under necessitation and
$X\in\Gamma$, hence $\Gamma\vdash X$. Using appropriate instances of the
necessitation rule in $\Gamma$ we can derive $P_{1}P_{2}P_{3},\ldots,P_{k}X$
for each prefix $P_{1}P_{2}P_{3},\ldots,P_{k}$ with $P_{i}$ is one of
$\mathbf{K}_{1},\mathbf{K}_{2},\ldots,\mathbf{K}_{n}$. Therefore,
$\Gamma\vdash{\bf C}X$ and $\Gamma\vdash{\bf C}\Gamma$.

##  4 Kripke structures and models

A Kripke structure is a convenient vehicle for specifying epistemic assertions
via truth values of atomic propositions and the combinatorial structure of the
set of global states of the system. A Kripke structure

${\cal M}=\langle W,R_{1},R_{2},\ldots,\\!\Vdash\\!\rangle$

consists of a non-empty set $W$ of possible worlds, “indistinguishability”
equivalence relations $R_{1},R_{2},\ldots$ for each agent, and truth
assignment ‘$\ \\!\Vdash\\!\ $’ of atoms at each world. The predicate ‘$F$
holds at $u$’ ($u\\!\Vdash\\!F$) respects Booleans and reads epistemic
assertions as

$\mbox{\em$u\\!\Vdash\\!\mathbf{K}_{i}F\ \ \ $ {\em iff} $\ \ \ $ for each
state $v\in W$ with $uR_{i}v$, $v\\!\Vdash\\!F$ holds}.$

Conceptually, ‘agent $i$ at state $u$ knows $F$’
$(u\\!\Vdash\\!\mathbf{K}_{i}F)$ encodes the situation in which $F$ holds at
each state indistinguishable from $u$ for agent $i$.

A model of a set of formulas $\Gamma$ is a pair $({\cal M},u)$ of a Kripke
structure ${\cal M}$ and a state $u$ such that all formulas from $\Gamma$ hold
at $u$:

${\cal M},u\\!\Vdash\\!F\ \ \mbox{\em for all $F\in\Gamma$.}$

A pair $({\cal M},u)$ is an exact model of $\Gamma$ if

$\Gamma\vdash F\ \ \Leftrightarrow\ \ {\cal M},u\\!\Vdash\\!F.$

An epistemic scenario (a set of ${\sf S5}_{n}$-formulas) $\Gamma$ admits a
semantic definition iff $\Gamma$ has an exact model.

There is a simple criterion to determine whether $\Gamma$ admits semantic
definitions (Theorem 4.3) and we argue that “most” epistemic scenarios lack
semantic definitions. These observations provide a justification for Syntactic
Epistemic Logic with its syntactic approach to epistemic scenarios.

A formula $F$ follows semantically from $\Gamma$,

$\Gamma\models F,$

if $F$ holds in each model $({\cal M},u)$ of $\Gamma$. A well-known fact
connecting syntactic derivability from $\Gamma$ and semantic consequence is
given by the Completeness Theorem777There are many sources in which the proof
of this theorem can be found, e.g., [10, 11, 13, 14, 15, 16, 19].:

$\Gamma\vdash F\ \ \Leftrightarrow\ \ \Gamma\models F.$

This fact has been used to claim the equivalence of the syntactic and semantic
approaches and to define epistemic scenarios semantically by a model. However,
the semantic part of the Completeness Theorem

$\Gamma\models F$

refers to the validity of $F$ in all models of $\Gamma$, not in an arbitrary
single model.

We challenge the model theoretical doctrine in epistemology and show the
limitations of single-model semantic specifications, cf. Theorem 4.3.

###  4.1 Canonical model

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.$

###  4.2 Deductive completeness

###### Definition 4.1

A set of ${\sf S5}_{n}$-formulas $\Gamma$ is deductively complete if

$\Gamma\vdash F\ \ \mbox{ or }\ \ \Gamma\vdash\neg F.$

###### Example 4.2

Consider examples in the language of the two-agent epistemic logic ${\sf
S5}_{2}$ with one propositional variable $m$ and knowledge modalities
$\mathbf{K}_{1}$ and $\mathbf{K}_{2}$.

1\. $\Gamma_{1}=\\{m\\}$, where $m$ is a propositional letter. Neither
$\mathbf{K}_{1}m$ nor $\neg\mathbf{K}_{1}m$ is derivable in $\Gamma_{1}$ and
this can be easily shown on corresponding models. Hence $\Gamma_{1}$ is not
deductively complete.888In classical logic without epistemic modalities,
$\Gamma_{1}$ is deductively complete: for each modal-free formula $F$ of one
variable $m$, either $\Gamma_{1}\vdash F$ or $\Gamma_{1}\vdash\neg F$.

2\. $\Gamma_{2}=\\{{\bf E}m\\}$, i.e., both agents have first-order knowledge
of $m$. However, the second-order knowledge assertions, e.g.,
$\mathbf{K}_{2}\mathbf{K}_{1}m$, are independent,999Again, there are easy
countermodels.

$\Gamma_{2}\not\vdash\mathbf{K}_{2}\mathbf{K}_{1}m\ \ \mbox{\ and }\ \
\Gamma_{2}\not\vdash\neg\mathbf{K}_{2}\mathbf{K}_{1}m.$

This makes $\Gamma_{2}$ deductively incomplete.

3\. $\Gamma_{3}={\bf C}m$, i.e., it is common knowledge that $m$. This set is
deductively complete. Indeed, first note that, by Proposition 3.2,
$\Gamma_{3}$ admits necessitation:101010which is not the case for $\Gamma_{1}$
and $\Gamma_{2}$.

$\Gamma_{3}\vdash F\ \ \Rightarrow\ \ \Gamma_{3}\vdash\mathbf{K}_{i}F,\ \ \
i=1,2.$

To establish the completeness property: for each formula $F$,

$\Gamma_{3}\vdash F\ \ \mbox{ or }\ \ \Gamma_{3}\vdash\neg F,$

run induction on $F$. The base case when $F$ is $m$ is covered, since
$\Gamma_{3}\vdash m$. The Boolean cases are straightforward. Case
$F=\mathbf{K}_{i}X$. If $\Gamma_{3}\vdash X$, then, by necessitation,
$\Gamma_{3}\vdash\mathbf{K}_{i}X$. If $\Gamma_{3}\vdash\neg X$, then, since S5
proves $\neg X\\!\rightarrow\\!\neg\mathbf{K}_{i}X$,
$\Gamma_{3}\vdash\neg\mathbf{K}_{i}X$.

###  4.3 Semantic definitions and complete scenarios

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}$.111111The same criteria hold for any other normal
modal logic which has a canonical model in the usual sense.

###### Theorem 4.3

$\Gamma$ is semantically definable if and only if it is deductively complete.

###### Proof 4.4

The ‘only if’ direction. Suppose $\Gamma$ has an exact model $({\cal M},u)$,
i.e.,

$\Gamma\vdash F\ \ \ \Leftrightarrow\ \ \ {\cal M},u\\!\Vdash\\!F.$

The set of true formulas in $({\cal M},u)$ is maximal: for each formula $F$,

${\cal M},u\\!\Vdash\\!F\ \ \mbox{ or }\ \ {\cal M},u\\!\Vdash\\!\neg F,$

hence $\Gamma$ is deductively complete: for each $F$,

$\Gamma\vdash F\ \ \mbox{ or }\ \ \Gamma\vdash\neg F.$

The ‘if’ direction. Suppose $\Gamma$ is consistent and deductively complete.
Then the deductive closure $\widetilde{\Gamma}$ of $\Gamma$

$\widetilde{\Gamma}=\\{F\mid\Gamma\vdash F\\},$

is a maximal consistent set, hence an element of the canonical model ${\cal
M}({\sf S5}_{n})$. We claim that $({\cal M}({\sf S5}_{n}),\widetilde{\Gamma})$
is an exact model of $\Gamma$, i.e., for each $F$,

$\Gamma\vdash F\ \ \ \Leftrightarrow\ \ \ {\cal M}({\sf
S5}_{n}),\widetilde{\Gamma}\\!\Vdash\\!F.$

Indeed, if $\Gamma\vdash F$, then $F\in\widetilde{\Gamma}$ by the definition
of $\widetilde{\Gamma}$. By the Truth Lemma in ${\cal M}({\sf S5}_{n})$, $F$
holds at the world $\widetilde{\Gamma}$. If $\Gamma\not\vdash F$, then, by
deductive completeness of $\Gamma$, $\Gamma\vdash\neg F$, hence, as before,
$\neg F$ holds at $\widetilde{\Gamma}$, i.e., ${\cal M}({\sf
S5}_{n}),\widetilde{\Gamma}\not\\!\Vdash\\!F$.

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.

##  5 The Muddy Children puzzle

Consider the standard Muddy Children puzzle, which is formulated
syntactically.

> A group of $n$ children meet their father after playing in the mud. Their
> father notices that $k>0$ of the children have mud on their foreheads. The
> children see everybody else’s foreheads, but not their own. The father says:
> “some of you are muddy,” then adds: “Do any of you know that you have mud on
> your forehead? If you do, raise your hand now.” No one raises a hand. The
> father repeats the question, and again no one moves. After exactly $k$
> repetitions, all children with muddy foreheads raise their hands
> simultaneously. Why?

###  5.1 Standard syntactic formalization

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.

###  5.2 Semantic solution

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$.

$\textstyle{1,0}$$\textstyle{1,1}$$\textstyle{0,0}$$\textstyle{0,1}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$

Figure 2: Model $Q_{2}$.

Logical possibilities for the truth value combinations121212$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.

$\textstyle{1,0}$$\textstyle{1,1}$$\textstyle{0,1}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{1,1}$$\textstyle{\bullet}$

Figure 3: Models $\mathcal{M}_{2}$ and $\mathcal{M}_{3}$.

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.

###  5.3 Justifying the model

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)$.

###### Theorem 5.1

Each instance ${\sf MC}_{n}(u)$ of Muddy Children is deductively complete and
$(Q_{n},u)$ is its exact model

${\sf MC}_{n}(u)\vdash F\ \ \ \mbox{ iff }\ \ \ \ Q_{n},u\\!\Vdash\\!F.$

Proof:131313We have chosen to present a syntactic proof of Theorem 5.1. A
semantic proof that makes use of bi-simulations can also be given. The
direction ‘only if’ claims that $(Q_{n},u)$ is a model for ${\sf MC}_{n}(u)$
is straightforward. First, $Q_{n}$ is an ${\sf S5}_{n}$-model and all
principles of ${\sf S5}_{n}$ hold everywhere in $Q_{n}$. It is easy to see
that principles ‘knowing about the others’ and ‘not knowing about himself’
hold at each node. Furthermore, as $\pi(u)$ holds at $u$, everything that can
be derived from ${\sf MC}_{n}(u)$ holds at $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 coordinate141414Formally,
$\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.

###  5.4 Incomplete scenario: Muddy Children Explicit

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 complete151515In 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.

###  5.5 Some additional observations

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.

##  6 Syntactic Epistemic Logic and games

Consider a variant Centipede Lite, CL, of the well-known Centipede game (cf.
[17]) with risk-averse rational players Alice and Bob. No cross-knowledge of
rationality, let alone common knowledge, is assumed!

$\textstyle{2,1}$$\textstyle{\bullet}$$\textstyle{1(A)}$$\textstyle{1,4}$$\textstyle{\bullet}$$\textstyle{2(B)}$$\textstyle{4,3}$$\textstyle{\bullet}$$\textstyle{3(A)}$$\textstyle{3,6}$

Figure 4: Centipede game tree

CL admits the following rigorous analysis.

> At 3, Alice plays down. At 2, Bob plays down because he is risk-averse and
> cannot rule out that Alice plays down at 3 (since it is true). At 1, Alice
> plays down because she cannot rule out Bob’s playing down at 2. So, CL has
> the so-called Backward Induction solution “down at each node.”

CL is not complete (epistemic assumptions, such as Bob knows that Alice plays
“across” at 3, are not specified), hence CL cannot be defined by a single
Kripke/Aumann model.

##  7 Incomplete and complete scenarios

How typical are deductively incomplete epistemic scenarios? We argue that this
is the rule rather than the exception. Epistemic conditions more flexible than
common knowledge of the game and rationality (mutual knowledge of rationality,
asymmetric epistemic assumptions when one player knows more than the other,
etc.) lead to semantic undefinability.

Semantically non-definable scenarios are the “dark matter” of the epistemic
universe: they are everywhere, but cannot be visualized as a single model. The
semantic approach does not recognize these “dark matter” scenarios; SEL deals
with them syntactically.

The question remains: how manageable are semantic definitions of deductively
complete scenarios?

###  7.1 Cardinality and knowability issue

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.

###  7.2 Complexity considerations

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.

##  8 Further observations

An interesting question is why the traditional semantic approach, despite its
aforementioned shortcomings, produces correct answers in many situations. One
of possible reasons for this is pragmatic self-limitation.

Given a syntactic description $\cal D$, we intuitively seek a solution that
logically follows from $\cal D$. Even if we reason on a “natural model” of
$\cal D$, normally overspecified, we try not to use features of the model that
are not supported by $\cal D$. If we conclude a property $P$ by such self-
restricted reasoning about the model, then $P$ indeed logically follows from
$\cal D$.

> This situation resembles Geometry, in which we reason about “models”, i.e.,
> combinations of triangles, circles, etc., but have a rigorous system of
> postulates in the background. We are trained not to venture beyond given
> postulates even in informal reasoning.

Such an ad hoc pragmatic approach needs a scientific foundation, which could
be provided within the framework of Syntactic Epistemic Logic.

##  9 Syntactic Epistemic Logic suggestions

The Syntactic Epistemic Logic suggestion, in brief, is to make an appropriate
syntactic formalization of an epistemic scenario its formal specification.
This extends the scope of scientific epistemology and offers a remedy for two
principal weaknesses of the traditional semantic approach. The reader will
recall that those weaknesses were the restricting single model requirement and
a hidden assumption of the common knowledge of this model.

SEL suggests a way to handle incomplete scenarios which have rigorous
syntactic descriptions (cf. Muddy Children Explicit, Centipede Lite, etc.).

SEL offers a scientific framework for resolving the tension, identified by R.
Aumann [9], between a syntactic description and its hand-picked model. If,
given a syntactic description $\Gamma$ we prefer to reason on a model $\cal
M$, we have to establish completeness of $\Gamma$ with respect to $\cal M$.

Appropriate syntactic specifications could also help to handle situations for
which natural models exist but are too large for explicit presentations.

SEL can help to extend Epistemic Game Theory to less restrictive epistemic
conditions. A broad class of epistemic scenarios does not define higher-order
epistemic assertions and rather addresses individual knowledge, mutual and
limited-depth knowledge, asymmetric knowledge, etc. and hence is deductively
incomplete and has no exact single model characterizations. However, if such a
scenario allows a syntactic formulation, it can be handled scientifically by a
variety of mathematical tools, including reasoning about its models.

Since the basic object in SEL is a syntactic description of an epistemic
scenario rather than a specific model, there is room for a new syntactic
theory of updates and belief revision.

### Acknowledgements

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.

## References

  * [1] Arieli I, Aumann R.  The logic of backward induction.  doi:10.2139/ssrn.2133302,  2012\.
  * [2] Artemov S.  On Definitive Solutions of Strategic Games.  Alexandru Baltag and Sonja Smets, eds. _Johan van Benthem on Logic and Information Dynamics_. Outstanding Contributions to Logic 5:487–507, Springer, 2014.  doi: 10.1007/978-3-319-06025-5_17.
  * [3] Artemov S.  Syntactic Epistemic Logic.  _Book of Abstracts. 15th Congress of Logic, Methodology and Philosophy of Science, University of Helsinki, 2015_ , 109–110.
  * [4] Artemov S.  Hyperderivations.  _The Hausdorff Trimester Program: Types, Sets and Constructions, Hausdorff Center for Mathematics, Bonn, 2018_.
https://www.youtube.com/watch?v=kytYAi6Ln7U&t=1276s

  * [5] Artemov S, Nogina E.  On completeness of epistemic theories.  _The Bulletin of Symbolic Logic_ , 24(2):232, 2018.  https://doi.org/10.1017/bsl.2018.13.
  * [6] Aumann R.  Agreeing to disagree.  _The Annals of Statistics_ , 4(6):1236–1239, 1976.  https://doi.org/10.1214/ aos/1176343654.
  * [7] Aumann R.  Backward induction and common knowledge of rationality.  _Games and Economic Behavior_ , 8(1):6–19, 1995.  https://doi.org/10.1016/S0899-8256(05)80015-6.
  * [8] Aumann R.  Interactive epistemology I: Knowledge.  _International Journal of Game Theory_ , 28:263–300, 1999.  https://doi.org/10.1007/s001820050111.
  * [9] Aumann R.  Epistemic Logic: 5 Questions, 2010.  Vincent F. Hendricks and Olivier Roy, eds. Automatic Press/VIP, pp. 21–33.  ISBN 8792130240, 9788792130242
  * [10] Blackburn P, de Rijke M, Venema Y.  Modal Logic.  _Cambridge Tracts in Theoretical Computer Science_ , 53, 2001.
  * [11] Blackburn P, van Benthem J.  Modal logic: A semantic perspective.  _Handbook of Modal Logic._ pp.1–84.  _Studies in Logic and Practical Reasoning_ 3, Elsevier, 2007.
https://doi.org/10.1016/S1570-2464(07)80004-8

  * [12] Brandenburger A.  The Language of Game Theory: Putting Epistemics Into the Mathematics of Games.  World Scientific Publishing Company, 2014.  ISSN 2251-2071.
  * [13] Chagrov A, Zakharyaschev M.  Modal Logic.  _Oxford Logic Guides_ 35, 1997.  ISBN-13: 978-0198537793; ISBN-10: 0198537794.
  * [14] Fagin R, Halpern J, Moses Y, Vardi M.  Reasoning About Knowledge.  MIT Press, 1995.  ISBN-13: 978-0262562003; ISBN-10: 9780262562003.
  * [15] Fitting M.  Modal proof theory.  _Handbook of Modal Logic._ pp.85–138.  _Studies in Logic and Practical Reasoning_ 3, Elsevier, 2007.  https://doi.org/10.1016/S1570-2464(07)80005-X
  * [16] Meyer JJC, van der Hoek W.  Epistemic Logic for AI and Computer Science.  _Cambridge Tracts in Theoretical Computer Science_ 41, 1995.
  * [17] Osborne M, Rubinstein A.  A Course in Game Theory.  MIT Press, 1994.
  * [18] Pauly M, van der Hoek W.  Modal logic for games and information.  Handbook of Modal Logic. pp.1077–1148.  _Studies in Logic and Practical Reasoning_ 3, Elsevier, 2007.  https://doi.org/10.1016/S1570-2464(07)80023-1
  * [19] Van Benthem J.  Logic in Games.  MIT Press, 2014.


# Large scale compressible turbulence in the ism of CSWA13, a star-Forming
Lensed Galaxy at z = 1.87 with outflowing wind

Itzhak Goldman 1,2 1Physics Department Afeka College, Tel Aviv 6998812, Israel
2 Astrophysics Department, Tel Aviv University, Tel Aviv 6997801 , Israel

###### Abstract

Recently, Keerthi Vasan G. et al. (2024)presented spatially resolved
observations of a wind outflow in CSWA13, a gravitationally lensed Star-
Forming galaxy at $z=1.87$. The gravitational lensing allowed for a
substantially improved spatial and kinematic resolution of the wind and of the
nebular gas. In this paper we take advantage of the resolved data to test for
the existence of turbulence and to study its nature. We derive the spatial
structure functions of the residual nebular and wind velocities along the
major axis of the galaxy. The structure functions, of both velocity fields,
reveal a supersonic compressible large scale turbulence. The turbulent
timescale corresponding to the largest scale is about 200 Myr, an order of
magnitude larger than the estimated age of the wind and of the young stars.
This implies that the turbulence in the ism formed well before the wind and
the young stars. Given the large spatial scale of the turbulence, it is
plausible that the source of the turbulence is a large scale one e.g. a merger
or tidal event that triggered the formation of molecular clouds, in the cores
of which the young stars formed. A steepening of the structure functions on
the smaller scales provides an estimate of the effective depth along the line
of sight of the turbulent layer. The latter turns out to be $\sim 2kpc$.

###### keywords:

galaxy outflows , galaxy evolution, interstellar turbulence

##  1 introduction

High redshift galaxies are characterized by high star formation rates as well
as outflowing winds, generated by the young stars, e.g. (Bournaud et al.,
2009; Hoffmann et al., 2022; Rizzo et al., 2021; Sanders et al., 2023; Shah et
al., 2022) The high rate of star formation is attributed to the assembly
process of the galaxy, involving gas inflow from the circum galactic medium
(CGM) and also by more violent events such as mergers that lead to formation
of molecular clouds and eventually to star formation. Such mergers could
result in large scale shocks and also in large scale turbulence, created by
the shocks and by the instabilities caused by the mergers.

Observations of high redshift galaxies indeed display velocity dispersions
that are usually interpreted as manifestation of turbulence. It has been
argued that accretion onto disk galaxies can generate large scale turbulence,
in particular at the disk outskirts, e. g. (Forbes et al., 2023; Goldman &
Fleck, 2023). Turbulence can be generated also by mergers and tidal
interactions. To establish the existence of turbulence and moreover, to
understand its nature, a power spectrum or structure function of the velocity
field are needed. This in turn demands observations with high enough spatial
resolution which, for galaxies at high redshifts, are challenging.

Gravitational lensing can help with this regard. A recent paper (Keerthi Vasan
G. et al., 2024) presented a study of a wind outflow in CSWA13, which is a
gravitationally lensed star-forming galaxy at $z=1.87$. The gravitational
lensing allowed for a substantially improved spatial and kinematic resolution.
The authors obtained, among other results, two velocity fields along the major
axis of the galaxy: the nebular gas velocity traced by the $C_{|||]}$ emission
line. that represents also the velocity of the young stars embedded in the
nebular gas and the wind velocity traced by the $Si_{||}^{*}$ florescent
emission line. Each of these velocity fields , exhibits a large scale shear.

In the present paper we set to check wether these velocity fields can be used
to test for the existence of turbulence, and if so to obtain its
characteristics.

The two residual velocity fields are obtained in section 2. The
autocorrelation functions are presented in section 3. In section 4 we obtain
the structure functions. In the appendix, the theoretical structure function
of a quantity that is the result of integration along the line of sight
direction, is derived. This provides an estimate of the depth of the turbulent
layer. Discussion is presented in section 5.

##  2 The residual velocity fields

We digitized the velocity curves of Fig. 8 in Keerthi Vasan G. et al. (2024)
and obtained the nebular and wind velocity as functions of position along the
galactic major axis.The nebular velocity and the wind velocity exhibit each a
large scale shear. We subtracted from each velocity field the corresponding
large scale shear, and then removed the remaining mean value. Doing so
resulted in two residual velocity fields along the major galactic axis. We
derived the autocorrelation function and the structure function for each.

Structure functions rather as function of$x/D$.than power spectra were
employed since the former are more detailed on the smaller and medium spatial
scales. They are also more reliable at treating data at the borders of the
data domain (Nestingen-Palm et al., 2017).

###  2.1 The residual nebular velocity along the major galaxy axis

The velocity posses a large scale shear of $96.2km\ s^{-1}/(6.43kpc)$. After
subtracting the shear, and the remaining mean value , the residual velocity is
obtained and is displayed in Fig. 1.

Figure 1: The residual nebular velocity in units of $km/s$ as function of
position along the major axis, in units of $207.5pc$.

###  2.2 The residual wind velocity along the major galaxy axis

The velocity posses a large scale shear of $152.2km\ s^{-1}/(6.43kpc)$. After
subtracting the shear, and the remaining mean value , the residual velocity is
obtained and is displayed in Fig. 2.

Figure 2: The residual wind velocity in units of $km/s$ as function of
position along the major axis, in units of $207.5pc$.

##  3 autocorrelation functions

The one-dimensional autocorrelation function, $C(x)$, of a residual velocity
$v(x)$ (with a zero mean value) is

$C(x)=<v(x+x^{\prime})v(x^{\prime})>,$ (1)

The brackets indicate ensemble average which by invoking the ergodic principle
can be replaced by an average over $x^{\prime}$. Here $x$ denotes the spatial
lag between two positions along the major galaxy axis.

###  3.1 The autocorrelation function of the residual nebular velocity

The computed observational normalized autocorrelation function of the residual
nebular velocity is displayed in Fig, 3. It implies that the residual values
of the nebular velocity are in fact correlated over large spatial range,
comparable to the size of the major axis.

Figure 3: The normalized observational autocorrelation function of the
residual nebular velocity as function of the spatial lag, in units $207.5pc$.

###  3.2 The autocorrelation function of the residual wind velocity

Fig.4. presents the normalized autocorrelation function of the wind velocity.
It exhibits long range correlation similar to that of the nebular velocity.

Figure 4: The normalized observational autocorrelation function of the
residual wind velocity as function of the spatial lag, in units of $207.5pc$.

##  4 structure functions

Long range autocorrelation could be a signature of turbulence. In order to
test for the existence of turbulence and understand its nature, we evaluate
the structure functions for the two residual velocity fields.

The one-dimensional structure function of a quantity $f(x)$ defined along a
straight line is

$S_{f}(x)=<\left(f(x^{\prime}+x)-f(x^{\prime})\right)^{2}>=2C_{f}(0)-2C_{f}(x),$
(2)

with the lag $x$ being the difference between two positions. $C_{f}(x)$ is the
auto correlation function of $f(x)$ defined as

$C_{f}(x)=<f(x^{\prime}+x)f(x)>.$ (3)

In the following, the computed structure functions of the observational
residual nebular velocity, and of the residual wind velocity are presented,

###  4.1 The observational structure function of the residual nebular velocity

Fig.5 displays the structure function of the observational residual nebular
velocity. The blue line has a logarithmic slope of 1. The orange line has a
logarithmic slope of 2. In the appendix it is shown that the structure
function, evaluated along a lateral line, of a quantity that is an integral
over the line of sight direction increases the logarithmic slope by 1 when the
lateral lag is smaller than the effective depth of the turbulent layer.

The structure function at the largest lag is $2<C(0)^{2}=391(km/s)^{2}$. Thus,
the one dimensional rms turbulent velocity is $13.9km/s$. Assuming isotropic
turbulence, the three-dimensional turbulent velocity is $24km/s$

Figure 5: The observational structure function of the residual nebular
velocity in units of $(km/s)^{2}$ as function of the spatial lag, in units of
$207.5pc$. The asymptotes have logarithmic slopes of 1 and 2.

###  4.2 The observational structure functions of the residual wind velocity

Fig.6 displays the structure function of the residual wind velocity. The blue
line has a logarithmic slope of 1. The orange line has a logarithmic slope of
2. This behavior is similar to that of the structure function of the residual
nebular velocity.

The structure function at the largest lag is $2<C(0)^{2}=291(km/s)^{2}$,
implying a one-dimensional rms turbulent velocity of $12.1km/s$. Assuming
isotropic turbulence, the three-dimensional turbulent velocity is $21km/s$

Figure 6: The observational structure function of the residual wind velocity,
in units of $(km/s)^{2}$ as function of the spatial lag in units of $207.5pc$.
The asymptotes have logarithmic slopes of 1 and 2.

##  5 discussion

###  5.1 The nature of the turbulence

The observational structure functions of the two residual velocity fields
have, each, a logarithmic slope equaling 1 on the large spatial scales and a
logarithmic slope of 2 on the small spatial scales. This dependence
characterizes compressible turbulence with a one-dimensional power spectrum
$\propto k^{-2}$ with $k$ denoting the one -dimensional spatial wave number.

This power spectrum is steeper than the Kolmogorov power spectrum, which
corresponds to subsonic incompressible turbulence with a one-dimensional power
law with exponent of $-5/3$ and structure function with logarithmic slope of
2/3 and 5/3 for the large and small scales, respectively.

Such a power spectrum was derived by Burgers (1948) describing a hierarchy of
shocks in compressible gas. Compressible turbulence power spectra were
observed in HI intensity maps in the Milky Way (MW) galaxy (Green, 1993)and in
the SMC (Stanimirovic et al., 1999). This power spectrum has been observed
also in molecular clouds (Larson, 1981; Leung et al., 1982; Dame et al.,
1986),in the HII region Sharpless 142 (Roy & Joncas, 1985). It has been found
in a shocked cloud near the Milky Way galaxy center (Contini & Goldman, 2011),
and recently in the Gamma ray emission from the large Magellanic Cloud.
(Besserglik & Goldman, 2021). It has been also obtained in numerical
simulations e.g. (Passot et al., 1988; Vázquez-Semadeni et al., 1997; Kritsuk
et al., 2007; Federrath et al., 2021).

The steeper slope signals that (unlike in the Kolmogorov spectrum) the rate of
energy transfer in the turbulence cascade is not constant but decreases with
increasing wavenumber. This is expected in a compressible turbulence since
part of the energy at a given wavenumber in the cascade, is diverted to
compression of the gas. Indeed, a theoretical derivation of the compressible
turbulence power spectrum based on this argument has been obtained (Goldman,
2021a).

The three-dimensional rms turbulent velocities estimated in section 4.are
supersonic, in line with the shape of the structure functions.

The turbulence timescale of the largest scale eddies is $\sim l_{0}/v_{0}\sim
200$ Myr where $l_{0}$ is the largest spatial scale and $v_{0}$ is the
turbulent velocity on this scale. This timescale represents the eddy
correlation time on the largest spatial scale and therefore a lower bound on
the time span over which the turbulence was generated. This time span is an
order of magnitude larger than the age of the young stars and the outflowing
wind. Thus, the turbulence is older than the young stars and the wind that was
created by the latter. The timescales of the large scale shears are about 20
Myr, so they formed at the same time as the wind. The emerging picture is that
the young stars as well as the wind and the shear were formed on the
background of the turbulent interstellar gas. The generating source of this
large scale turbulence, must itself be correlated over the largest scale of
the turbulence, rather than a collection of smaller scale sources. The
probable source is a merger or a close tidal interaction with a smaller
galaxy.

###  5.2 The effective depth of the turbulent region

. The emitted photons that determine the velocities originate from different
depths along the line of sight. The issue of power spectra and structure
functions of quantities which are the result of integration along the line-of-
sight has been addressed by e.g. (Stutzki et al., 1998; Goldman, 2000, 2021b;
Lazarian & Pogosyan, 2000; Miville-Deschênes et al., 2003a). These authors
concluded that when the lateral spatial scale is smaller than the depth of the
layer, the logarithmic slope of the power spectrum steepens by $-1$ compared
to its value when the lateral scale is large compared to the depth. The
logarithmic slope of the structure function increases by 1. This behavior was
indeed revealed in observational power spectra of Galactic and extra Galactic
turbulence ( e.g. Elmegreen et al. (2001),Block et al. (2010), Miville-
Deschênes et al. (2003b) ) and in solar photospheric turbulence (Abramenko &
Yurchyshyn, 2020)).

In the appendix, the theoretical structure function of a quantity that is the
result of integration along the line of sight, is obtained. For the specific
case of compressible turbulence we found that $D=1.83x_{tr}$, where $D$ is the
effective depth of the turbulent layer and $x_{tr}$ is the observational lag
marking the slopes transition. The effective depth is the depth of a layer
with depth independent of the lateral coordinate, that would yield the
observational structure function.

From Fig.5 the observational transition lag for the nebular velocity $(1.31\pm
0.04)kpc$ yielding an effective depth of $(2.4\pm 0.07)kpc$. The observational
transition lag of the wind velocity structure function, from Fig.6, is
$(1.06\pm 0.04)kpc$ implying an effective depth of $(1.9.\pm 0.07)kpc$.

##  Appendix A The theoretical structure function of a quantity that is the
result of integration along the line of sight

Consider a function $f(x)$ where $x$ is a straight line in a lateral
direction. and is an integral along the line of sight:

$f(x)=\int_{0}^{D}g(x,z)dz.$ (4)

Here, $z$ is the line of sight coordinate and $D$ the depth. A plane parallel
geometry is assumed for simplicity.

The autocorrelation function of $f(x$ is:

$\displaystyle C_{f}(x)=<f(x+x^{\prime})f(x)>=$ (5)
$\displaystyle\int_{0}^{D}\int_{0}^{D}<g(x^{\prime},z)g(x+x^{\prime},z^{\prime})>dzdz^{\prime}=$
$\displaystyle\int_{0}^{D}\int_{0}^{D}C_{g}(x,z-z^{\prime})dzdz^{\prime}.$

,

The autocorrelation function $C_{g}(x,z-z^{\prime})$ can be expressed by the
two-dimensional power spectrum, $P_{2}(k_{x},k_{z})$,

$\displaystyle\hskip-42.67912ptC_{g}(x,z-z^{\prime})=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}e^{i(k_{x}x+k_{z}(z-z^{\prime}))}$
(6) $\displaystyle P_{2}(k_{x},k_{z})dk_{x}dk_{z}.$

leading to

$C_{f}(x)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}e^{ik_{x}x}P_{2}(k_{x},k_{z})\frac{\sin^{2}\left(k_{z}D/2\right)}{\left(k_{z}D/2\right)^{2}}dk_{x}dk_{z}.$
(7)

from equations (2) and (A4) follows the expression for the structure function

$\displaystyle
S_{f}(x,D)\propto\int_{0}^{\infty}\int_{0}^{\infty}\sin^{2}(k_{x}x/2)\frac{\sin^{2}\left(k_{z}D/2\right)}{\left(k_{z}D/2\right)^{2}}$
(8) $\displaystyle P_{2}(k_{x},k_{z})dk_{x}dk_{z}.$

In the case of a turbulence with a one-dimensional power spectrum which is a
power law with index $-m$, the two dimensional power spectrum is

$P_{2}(k_{x},k_{z})\propto\left(k_{x}^{2}+k_{z}^{2}\right)^{-(m+1)/2.}\ \ \ \
\ \ $ (9)

resulting in

$\displaystyle
S_{f}(x,D)\propto\int_{0}^{\infty}\int_{0}^{\infty}\sin^{2}(k_{x}x/2)\frac{\sin^{2}\left(k_{z}D/2\right)}{\left(k_{z}D/2\right)^{2}}$
(10) $\displaystyle\left(k_{x}^{2}+k_{z}^{2}\right)^{-(m+1)/2}dk_{x}dk_{z}.$

It is convenient to define the dimensionless variables

$\eta=k_{z}D/2.\ \ \ \ \ \ \ ;\ \ \ \mu=k_{x}D/2.$

Figure 7: Theoretical structure function, which is an integral along the line
of sight, as function of$x/D$. The straight lines have logarithmic slopes
equaling 1 and 2. Figure 8: Theoretical structure function of a quantity,
which is an integral along the line of sight, as function of$x/D$. The
straight line has a logarithmic slope of 1.5.

The structure function of equation (A7) can be expressed as

$S_{f}(x,D)\propto\int_{0}^{\infty}I(\mu)\sin^{2}\left(\mu x/D\right)d\mu.$
(11)

where $I(\mu)$ is

$I(\mu)=\int_{0}^{\infty}\left(\mu^{2}+\eta^{2}\right)^{-(m+1)/2}\frac{\sin^{2}\eta}{\eta^{2}}d\eta.$

Equation (A9) implies that the structure function argument is $x/D$. Also,
inspection of equations (A9) and (A10) reveals that for $x<<D$ the structure
function is proportional to $x^{m}$ while for $x>>D$ it is proportional to
$x^{m-1}$ .

A numerical solution for the case of $m=2$ is presented in Fig.7together power
laws with exponents 1 and 2. In order to find the value of $x_{tr}/D$ where
$x_{tr}$ denotes the transition lag between the two slopes a power law with
exponent of 1.5 is plotted in Fig.8 together with the structure function. The
value of $x_{tr}/D$ is taken to be the value for which the logarithmic slope
of the structure function equals 1.5, i.e. where the straight line is tangent
to the structure function. The result is $x_{tr}/D\sim 0.547$ thus $D\sim
1.83x_{tr}$.

## References

  * Abramenko & Yurchyshyn (2020) Abramenko, V. I. & Yurchyshyn, V. B. 2020, MNRAS, 497, 5405. doi:10.1093/mnras/staa2427.
  * Besserglik & Goldman (2021) Besserglik, D. & Goldman, I. 2021, ApJ, 915, 117. doi:10.3847/1538-4357/ac0247.
  * Block et al. (2010) Block, D. L., Puerari, I., Elmegreen, B. G., et al. 2010, ApJ, 718, L1. doi:10.1088/2041-8205/718/1/L1.
  * Bournaud et al. (2009) Bournaud, F., Elmegreen, B. G., & Martig, M. 2009, ApJ, 707, L1. doi:10.1088/0004-637X/707/1/L1.
  * Burgers (1948) Burgers, j. M. 1948, Advances in Applied Mechanics, 1, 171.
  * Contini & Goldman (2011) Contini, M. & Goldman, I. 2011, MNRAS, 411, 792. doi:10.1111/j.1365-2966.2010.17719.x.
  * Dame et al. (1986) Dame, T. M., Elmegreen, B. G., Cohen, R. S., et al. 1986, ApJ, 305, 892. doi:10.1086/164304.
  * Elmegreen et al. (2001) Elmegreen, B. G., Kim, S., & Staveley-Smith, L. 2001, ApJ, 548, 749.
  * Federrath et al. (2021) Federrath, C., Klessen, R. S., Iapichino, L., et al. 2021, Nature Astronomy, 5, 365. doi:10.1038/s41550-020-01282-z.
  * Forbes et al. (2023) Forbes, J. C., Emami, R., Somerville, R. S., et al. 2023, ApJ, 948, 107. doi:10.3847/1538-4357/acb53e.
  * Goldman & Fleck (2023) Goldman, I. & Fleck, R. 2023, MNRAS, 521, 2949. doi:10.1093/mnras/stad737.
  * Goldman (2021a) Goldman, I. 2021a, Physics of Fluids, 33, 071706. doi:10.1063/5.0058074. .
  * Goldman (2021b) Goldman, I. 2021b, MNRAS, 504, 4493. doi:10.1093/mnras/stab1227.
  * Goldman (2000) Goldman, I. 2000, ApJ, 541, 701.
  * Green (1993) Green, D. A. 1993, MNRAS, 262, 327. doi:10.1093/mnras/262.2.327.
  * Hoffmann et al. (2022) Hoffmann, K., Laigle, C., Chisari, N. E., et al. 2022, MNRAS, 515, 3603. doi:10.1093/mnras/stac1988.
  * Kolmogorov (1941) Kolmogorov, A. 1941, Akademiia Nauk SSSR Doklady, 30, 301.
  * Larson (1981) Larson, R. B. 1981, MNRAS, 194, 809. doi:10.1093/mnras/194.4.809.
  * Keerthi Vasan G. et al. (2024) Keerthi Vasan G., C., Jones, T., Shajib, A. J., et al. 2024, arXiv:2402.00942. doi:10.48550/arXiv.2402.00942.
  * Kritsuk et al. (2007) Kritsuk, A. G., Norman, M. L., Padoan, P., et al. 2007, ApJ, 665, 416. doi:10.1086/519443.
  * Lazarian & Pogosyan (2000) Lazarian, A. & Pogosyan, D. 2000, ApJ, 537, 7.
  * Leung et al. (1982) Leung, C. M., Kutner, M. L., & Mead, K. N. 1982, ApJ, 262, 583. doi:10.1086/160450.
  * Miville-Deschênes et al. (2003a) Miville-Deschênes, M.-A., Levrier, F., & Falgarone, E. 2003a, ApJ, 593, 831.
  * Miville-Deschênes et al. (2003b) Miville-Deschênes, M.-A., Joncas, G., Falgarone, E., et al. 2003b, A&A, 411, 109.
  * Shah et al. (2022) Shah, E. A., Kartaltepe, J. S., Magagnoli, C. T., et al. 2022, ApJ, 940, 4. doi:10.3847/1538-4357/ac96eb.
  * Nestingen-Palm et al. (2017) Nestingen-Palm, D., Stanimirović, S., González-Casanova, D. F., et al. 2017, ApJ, 845, 53. doi:10.3847/1538-4357/aa7e78.
  * Passot et al. (1988) Passot, T., Pouquet, A., & Woodward, P. 1988, A&A, 197, 228.
  * Roy & Joncas (1985) Roy, J.-R. & Joncas, G. 1985, ApJ, 288, 142. doi:10.1086/162772.
  * Rizzo et al. (2021) Rizzo, F., Vegetti, S., Fraternali, F., et al. 2021, MNRAS, 507, 3952. doi:10.1093/mnras/stab2295.
  * Sanders et al. (2023) Sanders, R. L., Shapley, A. E., Jones, T., et al. 2023, ApJ, 942, 24. doi:10.3847/1538-4357/aca46.
  * Shah et al. (2022) Shah, E. A., Kartaltepe, J. S., Magagnoli, C. T., et al. 2022, ApJ, 940, 4. doi:10.3847/1538-4357/ac96eb.
  * Stanimirovic et al. (1999) Stanimirovic, S., Staveley-Smith, L., Dickey, J. M., et al. 1999, MNRAS, 302, 417. doi:10.1046/j.1365-8711.1999.02013.
  * Stutzki et al. (1998) Stutzki, J., Bensch, F., Heithausen, A., et al. 1998, A&A, 336, 697.
  * Vázquez-Semadeni et al. (1997) Vázquez-Semadeni, E., Ballesteros-Paredes, J., & Rodríguez, L. F. 1997, ApJ, 474, 292. doi:10.1086/303432.