Classification of $σ$-validity
2026-07-06 • Logic in Computer Science
Logic in Computer Science
AI summaryⓘ
The authors studied how certain types of announcements in logic affect what is known or believed by one or more agents. They examined different patterns called $σ$-validity that describe when announcements succeed, fail, or cycle through being true or false. They disproved a previous guess about how these patterns work and provided corrected classifications for various logical systems. Their findings show that truthful announcements tend to stay true, while false or ‘lying’ announcements behave less predictably and may become true or false over time. Some lies can cause permanent falsehoods, while others are unstable and can revert to truth.
public announcementsmodal logicσ-validitysuccess formulasself-refuting formulasK45KD45S5multi-agent systemsdynamic epistemic logic
Authors
Eiji Yamada
Abstract
In their 2018 paper, Agotnes, van Ditmarsch, and Wang extended the notions of success and self-refutation in public announcements to true lies, impossible lies, and $σ$-validity in general, where $σ$ is a finite or infinite sequence of $0$s and $1$s. For example, successful formulas and self-refuting formulas are $11$-valid and $10$-valid, respectively. They then posed a conjecture on the classification of such sequences in terms of $σ$-validity. In this paper, we disprove the conjecture and give corrected classifications for multi-agent K45, single-agent KD45, and multi-agent S5 after reformulating the statement more explicitly. We leave the multi-agent KD45 case with more than one agent open. The results indicate that there is an asymmetry between truthful announcements and false announcements: the former are stable while the latter are unstable. In particular, successful formulas remain true forever while impossible lies can be true at some point when repeatedly announced. Also, although self-refuting formulas can become true again after following the truth pattern $10$, $100$-valid formulas are destructive in the sense that they remain false forever once they become false. On the other hand, true lies are fragile in the sense that truths created by lying can become false again.