Logical omniscience and common knowledge: WHAT do we know and what do WE know?

ABSTRACT

Two difficult issues for the logic of knowledge have been logical omniscience and common knowledge. Our existing logics of knowledge based on Kripke structures seem to justify logical omniscience, but we know that in real life it does not exist. Also, common knowledge appears to be needed for certain real life procedures to work. But it seems quite implausible that it actually exists in real people.We suggest two procedure based semantics for knowledge which seem to take care of both these issues in a relatively realistic way.What this suggests is that if we really want to understand knowledge, then existing customs and plans must play a greater role than we are used to assigning them.

REFERENCES

• 1: {AN05} Artemov, S., and E. Nogina, "Basic epistemic logics with justifications", Technical report TR-2005004, CUNY Ph.D. program in Computer Science, 2005. To appear in TARK-X.
• 2: {Art04} Artemov, S., "Evidence based common knowledge", Technical report TR-2004018, CUNY Ph.D. program in Computer Science, to appear in TCS.
• 3: {Aum} Aumann, R., "Agreeing to disagree", Annals of Statistics, 4 (1976) 1236--1239.
• 4: {Block80} Block, N., "Introduction: what is functionalism?", in Readings in Philosophy of Psychology, (Ned Block, editor) Harvard University Press (1980) 171--184.
• 5: {CM81} Clark, H., and C. Marshall, "Definite reference and mutual knowledge", in Elements of Discourse Understanding, Ed. Joshi, Webber and Sag, Cambridge U. Press 1981, 10--63.
• 6: K. M. Chandy , Jayadev Misra, How processes learn, Distributed Computing, v.1 n.1, p.40-52, Jan. 1986 [doi>10.1007/BF01843569]
• 7: {CW05} Chopra, S., and L. White, "Attribution of Knowledge to Artificial Agents and their Principals", Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, August 2005, forthcoming.
• 8: {D} F. Dretske, Knowledge and the flow of information, MIT Press, 1981.
• 9: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 10: {Fit04} Fitting, M., "A logic for explicit knowledge", to appear in proceedings of Lgica 2004.
• 11: {Gaif04} Gaifman, H., "Reasoning with limited resources and assigning probabilities to arithmetical statements", Synthese, 140 (2004) 97--119.
• 12: {Hay36} Hayek, F. A., Individualism and Economic Order, University of Chicago Press. See especially chapters II and IV.
• 13: Joseph Y. Halpern , Ronald Fagin, A formal model of knowledge, action, and communication in distributed systems: preliminary report, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.224-236, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323617]
• 14: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.50-61, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806735]
• 15: Paul Krasucki , Rohit Parikh , Gilbert Ndjatou, Probabilistic knowledge and probabilistic common knowledge, Methodologies for intelligent systems, 5, Elsevier North-Holland, Inc., New York, NY, 1991
• 16: {Noz81} Nozick, R., Philosophical Explanations, Harvard University Press, 1981.
• 17: {Pa86} Parikh, R., "Levels of Knowledge in Distributed Computing", in Proc IEEE Symposium on Logic in Computer Science, June 1986, 314--321.
• 18: R. Parikh, Knowledge and the problem of logical omniscience, Proceeding of the Second International Symposium on Methodologies for intelligent systems, p.432-439, December 1987, Charlotte, North Carolina, United States
• 19: {Pa91} Parikh, R., "Finite and Infinite Dialogues", in the Proceedings of a Workshop on Logic from Computer Science, Ed. Moschovakis, MSRI publications, Springer 1991 481--498.
• 20: {Pa91b} Parikh, R., "Propositions, propositional attitudes and belief revision" in K. Segerberg, M. Zakharyaschev, M. de Rijke, H. Wansing, editors, Advances in Modal Logic, Volume 2, CSLI Publications, 2001.
• 21: Rohit Parikh, Logical Omniscience, Selected Papers from the International Workshop on Logical and Computational Complexity, p.22-29, October 13-16, 1994
• 22: Rohit Parikh, Knowledge Based Computation (Extended Abstract), Proceedings of the 4th International Conference on Algebraic Methodology and Software Technology, p.127-132, July 03-07, 1995
• 23: Rohit Parikh, Logical Omniscience, Selected Papers from the International Workshop on Logical and Computational Complexity, p.22-29, October 13-16, 1994
• 24: {Pa02} Parikh, R., "Social Software", Synthese, 132, Sep 2002, 187--211.
• 25: {P03} Parikh, R., Levels of knowledge, games, and group action, in Research in Economics, 57, (2003) 267--281.
• 26: {PK} Parikh, R., and P. Krasucki, "Levels of knowledge in distributed computing", Sadhana - Proc. Ind. Acad. Sci.17 (1992) 167--191.
• 27: {PaPa} Pacuit, E., and R. Parikh, A Logic for communication graphs, to appear in the proceedings of DALT 2004.
• 28: Rohit Parikh , R. Ramanujam, Distributed Processes and the Logic of Knowledge, Proceedings of the Conference on Logic of Programs, p.256-268, June 17-19, 1985
• 29: Rohit Parikh , Ramaswamy Ramanujam, A Knowledge Based Semantics of Messages, Journal of Logic, Language and Information, v.12 n.4, p.453-467, Fall 2003 [doi>10.1023/A:1025007018583]
• 30: {Ram26} Ramsey, F. P., 'Truth and probability', in The Foundations of Mathematics, Routledge and Kegan Paul (1931), 156--198.
• 31: {Sav54} Savage, Leonard, The Foundations of Statistics, Wiley 1954.
• 32: {Stal99} Stalnaker, R., Context and Content, Oxford University Press, 1999.
• 33: {Witt} Wittgenstein, L., Philosophical Investigations, MacMillan, 1958.
• 34: Ruili Ye , Melvin C. Fitting, Belief, names and modes of presentation: a first-order logic formalization, 1999