On model reasoning in epistemic scenarios

Computational Logic SeminarTuesday, February 19, 20132:00 pmCUNY Graduate Center, rm 3209

Sergei Artemov

On model reasoning in epistemic scenarios

The CUNY Graduate Center

It was long noticed that the textbook “solution” of the Muddy Children puzzle MC via reasoning on the n-dimensional cube Q_n had a fundamental gap since it presupposed common knowledge of the Kripke model Q_n which was not assumed in the puzzle description. In the MC scenario, the verbal description and logical postulates are common knowledge, but this does not yield common knowledge of the model.

Of course, a rigorous solution of MC can be given by a formal deduction in an appropriate epistemic logic with updates after epistemic actions (public announcements). This way requires an advanced and generally accepted logical apparatus, certain deductive skills in modal logic, and, most importantly, steers away from the textbook “solution.”

We argue that the gap in the textbook “solution” of MC can be fixed. We establish that MC_n is complete with respect to Q_n and hence a reasoning on Q_n can be accepted as a substitute for the aforementioned deductive solution (given that kids are smart enough to establish that this completeness theorem is itself common knowledge). This yields the following clean solution of MC:
1. prove the completeness of MC_n w.r.t. Q_n;
2. argue that (1) is common knowledge;
3. use a properly worded version of the textbook “solution.”
This approach seems to work for some other well-known epistemic scenarios related to knowledge. However, it does not appear to be universal, e.g., it does not work in the case of beliefs. In general, we have to rely on the deductive solution which fits the syntactic description of the problem.

The completeness of MC_n w.r.t. Q_n was established by me some years ago, and shortly after my corresponding seminar presentation, Evan Goris offered an elegant and more general solution which will be presented at this talk.

Professor Artemov holds a Distinguished Professor position at the Graduate Center of the City University of New York, in the Computer Science, Mathematics and Philosophy programs. He is also Professor of Mathematics at Moscow State University, the founder and the Head of the research laboratory Logical Problems in Computer Science. He conducts research in the areas of logic in computer science, mathematical logic and proof theory, knowledge representation and artificial intelligence, automated deduction and verification and optimal control and hybrid systems.

Posted by on February 18th, 2013