Why is the Fixed-Point Axiom true?

Question

In Epistemic Logic, the Fixed-Point Axiom says that $\varphi$ is common knowledge among the group $G$ if and only if all the members of $G$ know that $\varphi$ is true and is common knowledge: $$\vDash C_G\varphi \Leftrightarrow E_G(\varphi \land C_G\varphi)$$ Thus, the Fixed-Point Axiom says that $C_G\varphi$ can be viewed as a fixed point of the function $f(x) = E_G (\varphi\land x)$, which maps a formula $x$ to the formula $E_G (\varphi\land x)$.

---

Here, $G$ is a group of agents, $C_G\varphi$ means that "group $G$ has common knowledge of $\varphi$" and $E_G\varphi$ means that "everyone in the group $G$ knows $\varphi$". For those who are not familiar with these technical differences, $E_G\varphi$ is straightforward, but $C_G\varphi$ means $E_G^k\varphi$ for every $k\in\mathbb N$. In other words, if a group $G$ has common knowledge of $\varphi$, then everyone knows $\varphi$, everyone knows that everyone knows $\varphi$, everyone knows that everyone knows that everyone knows $\varphi$ and so on ad infinitum. Common knowledge is a much stronger condition!

Why should the Fixed-Point Axiom hold? I am unable to understand the intuition behind it. Could someone explain this perhaps with the help of an example?

Answer 1

The fixed-point treatment of common knowledge is not very intuitive. However, I will try to provide some explanation why it captures the properties of operators $C_G \varphi$.

First, recall that intuitively $C_G \varphi := \bigwedge_{n \in \mathbb{N}} E_G^n \varphi$, where $E_G^0 \varphi:= \varphi$ and $E_G^{n+1}:= E_G E_G^n \varphi$. This is your definition of the fact that $\varphi$ is common knowledge if everyone knows $\varphi$, everyone knows that everyone knows $\varphi$, and so on. We cannot have this formula in the language as the conjunction is infinite.

Second, since common knowledge is a type of knowledge, it is veridical, i.e. if $\varphi$ is common knowledge, then $\varphi$ is true.

Now, let's have a look at the axiom: $C_G \varphi \leftrightarrow E_G (\varphi \land C_G \varphi)$. The first conjunct on the right corresponds to common knowledge being veridical. In particular, $E_G \varphi$ implies $\varphi$. The second conjunct, $E_G C_G \varphi$, allows to generate $E_G^n \varphi$ for any finite $n$.

For example, let $C_G \varphi$. This is equivalent to $E_G (\varphi \land C_G \varphi)$, which in turn is equivalent to $E_G \varphi \land E_G C_G \varphi$. From $E_G \varphi$ we can imply $\varphi$ (the 'being veridical' part). In the second conjunct we can make a substitution according to the axiom: $E_G E_G (\varphi \land C_G \varphi)$. Again it can be broken down to $E_G E_G \varphi \land E_G E_G C_G \varphi$. So we get 'everyone knows that everyone knows $\varphi$'. By the same reasoning we can get an arbitrary long (and finite) stack of $E_G$'s that corresponds to $\varphi$ being a common knowledge.

Answer 2

The definition seems to be trying to capture exactly the recursive definition of "common knowledge" that you describe in your post. Using the axiom repeatedly, we would be able to reason that $$C_G\varphi \implies E_G(\varphi \wedge C_G(\varphi)) \implies E_G(C_G(\varphi))\\ \implies E_G(E_G(\varphi \wedge C_G\varphi)) \implies E_G(E_G(\varphi)),$$ for example -- so that common knowledge of $\varphi$ implies that "everyone knows everyone knows $\varphi$", as it should.

Answer 3

The existing answers are flawless, but I was able to gain some more intuition after writing down a formal proof. I decided to post it as an answer in case anyone's interested:

$[\Rightarrow]$: Suppose $(M,s)\vDash C_G\varphi$. Thus, $(M,t)\vDash\varphi$ for all states $t$ that are $G$-reachable from $s$. In particular, if $u$ is $G$-reachable from $s$ in 1 step, then $(M,u)\vDash\varphi$ and $(M,t)\vDash\varphi$ for all $t$ that are $G$-reachable from $u$. Then, $(M,u)\vDash \varphi \land C_G\varphi$ for all $u$ that are $G$-reachable from $s$ in 1 step, so $(M,s)\vDash E_G(\varphi \land C_G\varphi)$.

$[\Leftarrow]$: Suppose $(M,s)\vDash E_G(\varphi \land C_G\varphi)$. Suppose $t$ is $G$-reachable from $s$, and $s'$ is the first node after $s$ on a path from $s$ to $t$ whose edges are labeled by members of $G$. Since $(M,s)\vDash E_G(\varphi \land C_G\varphi)$, it follows that $(M,s')\vDash \varphi \land C_G\varphi$. Two cases arise: either $s' = t$ or $t$ is $G$-reachable from $s'$. If $s' = t$, we get $(M,t)\vDash\varphi$ due to $(M,s')\vDash\varphi$. If $t$ is $G$-reachable from $s'$, we get $(M,t)\vDash\phi$ since $(M,s')\vDash C_G\varphi$. Since $(M,t)\vDash\varphi$ for all $t$ that are $G$-reachable from $s$, it follows that $(M,s)\vDash C_G\varphi$.