I have just begun reading about Epistemic Logic from Reasoning About Knowledge, Fagin et. al. $\mathcal K_i$ is defined as the possibility relation between two worlds, and the author says that for the most part - one would want $\mathcal K_i$ to be an equivalence relation. I do not understand the author's intuition.

Here is some setup to give you background - there are $n$ agents, $\{1,2,...,n\}$. As usual, $\Phi$ denotes a set of propositional variables, and $S$ is a non-empty set of states/possible worlds for the Kripke structure. $\pi$ is a valuation, which associates each state in $S$ with a map as follows: $$\pi(s): \Phi\to\{T,F\}$$ Then, the author says the following about $\mathcal K_i$:

The binary relation $\mathcal K_i$ is intended to capture the possibility relation according to agent $i$: $(s, t) \in \mathcal K_i$ if agent $i$ considers world $t$ possible, given his information in world $s$. We think of $\mathcal K_i$ as a possibility relation, since it defines what worlds agent $i$ considers possible in any given world. Throughout most of the book (in particular, in this chapter), we further require that $\mathcal K_i$ be an equivalence relation on $S$. We take $\mathcal K_i$ to be an equivalence relation since we want to capture the intuition that agent $i$ considers $t$ possible in world $s$ if in both $s$ and $t$ agent $i$ has the same information about the world, that is, the two worlds are indistinguishable to the agent. Making $\mathcal K_i$ an equivalence relation seems natural and turns out to be the appropriate choice for many applications.

I find it difficult to understand what intuition the authors are trying to capture with such a definition. Could someone help me better understand the motivation and reason behind such an assumption? Thanks a lot!

  • $\begingroup$ What exactly do you not understand about the quoted passage? I'm not sure what explanation you want that would not just be restating what it says... $\endgroup$ – Eric Wofsey Mar 24 at 16:35
  • $\begingroup$ In particular, the passage quite directly answers your question about what notion/intuition they are trying to capture: namely, they are trying to capture the notion that "agent $i$ considers $t$ possible in world $s$" means that worlds $s$ and $t$ are indistinguishable to $i$. What about that is confusing you? $\endgroup$ – Eric Wofsey Mar 24 at 16:43
  • $\begingroup$ I don't see why we would want the two worlds to be indistinguishable to the agent. Could you throw some light on that? How does the possibility relation connect with indistinguishability? $\endgroup$ – epsilon-emperor Mar 24 at 17:05
  • $\begingroup$ I mean, you can just take it as a definition. This is what we are defining the word "possible" to mean. $\endgroup$ – Eric Wofsey Mar 24 at 17:07

There are several motivations behind taking possibility relations to be equivalence relations. Some are logical, some have to do with applications of epistemic logic.

From a logical point of view, using equivalence models (i.e. modal models with equivalence relations) allows reducing modal models to a very simple form, at least in the monomodal case (just one possibility relation): you can equate such models with sets of classical propositional models (sets of atoms). Correspondingly, the satisfiability problem for formulas in equivalence models is extremely simple: it is NP-complete and so does not add any complexity to the case of classical propositional logic.

From a pragmatic point of view using equivalence models is a natural way of formalizing distributed systems, which is a core area of applying epistemic logic to computer science. Fagin et al. provide such applications in the very book you are citing.

  • $\begingroup$ I would also add that such treatment of knowledge is the classic one dating back to Hintikka's 'Knowledge and Belief'. Fagin et al. work with this classic approach. And of course, there are other approaches to knowledge. $\endgroup$ – Charles Bronson Mar 25 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.