Seminar "Puzzles and Paradoxes in Logic and Probability"
[go to overview]Winter Term 2020 / 2021
Introduction
Research in logicbased artificial intelligence regularly draws inspiration from puzzles and paradoxes. Puzzles sharpen our understanding of what it takes to reason towards a solution, and are therefore excellent points of reference for developing and applying logical formalisms. This is especially true for the study of epistemic reasoning, or reasoning about knowledge, which abounds in thought provoking puzzles, often with surprising solutions. Paradoxes occur when seemingly sound reasoning leads to absurd conclusions. Paradoxes provide valuable insights, as they highlight the pitfalls and limitations that are inherent in the enterprise of formal reasoning. The bestknown paradox is perhaps the liarparadox: consider the statement "This statement is false". If this statement is true, then it must be false, and if it's false, then it must be true. This paradox teaches us about the dangers of selfreference and reasoning about truth.
Above all, puzzles and paradoxes are fun! They not only have academic value, but also serve as excellent topics for discussion among friends and family.
In this seminar you will give a presentation and write a report on one of the available topics. Each topic is about a puzzle or paradox. You are expected to present the puzzle or paradox and explain how it relates to logic or reasoning, how it is formalised, and what its relevance is in the broader context of AI.
This seminar is suitable for all students with basic knowledge of knowledge representation and reasoning (for example those who followed Artificial Intelligence 1). A number of topics furthermore require basic knowledge of probability theory.
Further Details
Please send me an email if you wish to participate. Participation is limited and on firstcomefirstserve basis. Registering on KLIPS alone is not sufficient.
Update: The seminar is now full and no further participants will be accepted.
Presentations will take place in February 2021 in an online form. The deadline for handing in reports is 31/03/2021.
Further details that you need in order to participate will be presented at the introductory meeting taking place on 19/10/2020 at 14:0015:00. Topic selection follows right after the introductory meeting.
All meetings and presentations will take place in an online format.
Topics
The list of topics below is preliminary. Additional topics and references may be added later.
Puzzles and paradoxes that involve epistemic reasoning (reasoning about knowledge):

The Sum Product Puzzle Also called the impossible puzzle because it appears to be impossible. But epistemic reasoning provides the solution [10].

The Muddy Children Puzzle This puzzle is based on the effect of what is called common knowledge [9].

The Russian Cards Problem Epistemic reasoning with applications to secure communica tions and cryptographic protocols [8, 9].

The Surprise Examination Paradox (also called Unexpected Hanging Paradox) Epistemic reasoning gone astray. But where’s the mistake? [4, 9]
Puzzles and paradoxes of logic:

The Lottery Paradox A paradox that demonstrates a fundamental problem in modelling a wellbehaved notion of belief (as opposed to knowledge) in logic [11]. (Optional: also discuss Preface Paradox)

Paradoxes of Material Implication The material implication φ → ψ (which is equivalent to ¬φ ∨ ψ) is often thought mean “if φ then ψ” but behaves in counterintuitive ways! [1].
Puzzles and paradoxes of probability:

The Monty Hall and Three Prisoner paradoxes These paradoxes are similar and deal with problems you run into when you update probabilities in a naive way. [2, 5]

Simpson’s Paradox A wellknown phenomenon in statistics that is very relevant to AI and data science [6, 7, 12].
Literature

[1] Lewis Carroll and Margaret Washburn. A logical paradox. Mind, 3(11):436–438, 1894.

[2] Wikipedia Contributors. Monty hall problem, 2019. https://en.wikipedia.org/wiki/Monty_Hall_problem

[3] Eugene Curtin and Max Warshauer. The locker puzzle. The Mathematical Intelligencer, 28 (1):28–31, 2006.

[4] Jelle Gerbrandy. The surprise examination in dynamic epistemic logic. Synthese, 155(1): 21–33, 2007.

[5] Peter D Grunwald and Joseph Y Halpern. Updating probabilities. Journal of Artificial Intelligence Research, 19:243–278, 2003.

[6] Eric Neufeld. Simpson’s paradox in artificial intelligence and in real life. Computational intelligence, 11(1):1–10, 1995.

[7] Judea Pearl. Comment: understanding simpson’s paradox. The American Statistician, 68(1): 8–13, 2014.

[8] Hans Van Ditmarsch. The russian cards problem. Studia logica, 75(1):31–62, 2003.

[9] Hans Van Ditmarsch and Barteld Kooi. The secret of my success. Synthese, 151(2):201–232, 2006.

[10] Hans P van Ditmarsch, Ji Ruan, and Rineke Verbrugge. Sum and product in dynamic epistemic logic. Journal of Logic and Computation, 18(4):563–588, 2007.

[11] Gregory Wheeler. A review of the lottery paradox. Probability and inference: Essays in honour of Henry E. Kyburg, Jr, pages 1–31, 2007.

[12] J von Kügelgen, L Gresele, B Schölkopf. Simpson’s paradox in Covid19 case fatality rates: a mediation analysis of agerelated causal effects (arxiv preprint)