Author(s): Tomohiro Hoshi
Series: ILLC Dissertation Series DS-2009-08
Publisher: University of Amsterdam
Year: 2009
Language: English
Pages: 200
City: Amsterdam
I Formal Framework 1
Introduction 3
1 Merging Frameworks 15
1.1 Epistemic Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2 Dynamic Epistemic Logic . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Public Announcement Logic . . . . . . . . . . . . . . . . . 18
1.2.2 Event Models and Product Update . . . . . . . . . . . . . 20
1.2.3 Protocol Information in DEL? . . . . . . . . . . . . . . . . 24
1.3 Epistemic Temporal Logic . . . . . . . . . . . . . . . . . . . . . . 25
1.3.1 Branching-Time Tree Structure . . . . . . . . . . . . . . . 25
1.3.2 Epistemic Dynamics in ETL? . . . . . . . . . . . . . . . . 27
1.4 Merging DEL and ETL . . . . . . . . . . . . . . . . . . . . . . . . 28
1.4.1 Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.4.2 DEL-Generated ETL Models . . . . . . . . . . . . . . . . 29
1.5 Comparing DEL and ETL . . . . . . . . . . . . . . . . . . . . . . 34
1.5.1 Reinterpreting DEL-Operators as ETL-Operators . . . . . 35
1.5.2 Representation Theorem . . . . . . . . . . . . . . . . . . . 35
1.6 Conclusion and Discussion . . . . . . . . . . . . . . . . . . . . . . 40
2 Logics 43
2.1 Temporal Public Announcement Logic . . . . . . . . . . . . . . . 44
2.2 Semantic Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.1 PAL and TPAL . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.2 Simple Observations . . . . . . . . . . . . . . . . . . . . . 47
2.2.3 Model Normalization . . . . . . . . . . . . . . . . . . . . . 49
2.3 Complete Axiomatization . . . . . . . . . . . . . . . . . . . . . . 51
2.3.1 Axiomatic System . . . . . . . . . . . . . . . . . . . . . . . 52
2.3.2 Completeness Proof . . . . . . . . . . . . . . . . . . . . . . 53
2.3.3 Decidability via Finite Completeness Proof . . . . . . . . . 57
2.3.4 Common Knowledge . . . . . . . . . . . . . . . . . . . . . 59
2.4 Other Results in TPAL . . . . . . . . . . . . . . . . . . . . . . . . 62
2.4.1 Uniform Protocols . . . . . . . . . . . . . . . . . . . . . . 63
2.4.2 Embedding PAL into TPAL . . . . . . . . . . . . . . . . . 64
2.5 Temporal Dynamic Epistemic Logic . . . . . . . . . . . . . . . . . 66
2.5.1 Axiomatization of TDEL . . . . . . . . . . . . . . . . . . . 66
2.5.2 Completeness Proof . . . . . . . . . . . . . . . . . . . . . . 68
2.5.3 TDEL Restricted to Subclasses of Protocols . . . . . . . . . 70
2.5.4 Decidability . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.5.5 Other Epistemic Operators? . . . . . . . . . . . . . . . . . 71
2.6 Generalization of Other Results in TDEL . . . . . . . . . . . . . . 71
2.6.1 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.6.2 Uniform Protocols . . . . . . . . . . . . . . . . . . . . . . 72
2.6.3 Embedding DEL into TDEL . . . . . . . . . . . . . . . . . 74
2.7 Conclusion and Discussion . . . . . . . . . . . . . . . . . . . . . . 74
3 Extensions 77
3.1 Quantifying over Public Announcements . . . . . . . . . . . . . . 78
3.1.1 Temporal Arbitrary Public Announcement Logic . . . . . . 78
3.1.2 Semantic Results . . . . . . . . . . . . . . . . . . . . . . . 80
3.1.3 Axiomatization . . . . . . . . . . . . . . . . . . . . . . . . 83
3.1.4 Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.1.5 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2 Describing the Past . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.2.1 TPAL with Labelled Past Operators . . . . . . . . . . . . 90
3.2.2 Semantic Results . . . . . . . . . . . . . . . . . . . . . . . 91
3.2.3 Axiomatization . . . . . . . . . . . . . . . . . . . . . . . . 93
3.2.4 Soundness Proof . . . . . . . . . . . . . . . . . . . . . . . 94
3.2.5 Completeness Proof . . . . . . . . . . . . . . . . . . . . . . 96
3.3 Announcements about Announcements . . . . . . . . . . . . . . . 97
3.3.1 Higher-Order Public Announcements . . . . . . . . . . . . 97
3.3.2 Generalization of PAL-Generated ETL Models . . . . . . . 98
3.3.3 Representation Theorem . . . . . . . . . . . . . . . . . . . 101
3.3.4 Axiomatization . . . . . . . . . . . . . . . . . . . . . . . . 102
3.4 Discussion: Extensions in TDEL . . . . . . . . . . . . . . . . . . . 103
3.4.1 Extending TDEL with Generalized Event Operators . . . . 103
3.4.2 Extending TDEL with Labelled Past Operators . . . . . . 106
3.4.3 Events with Future Preconditions . . . . . . . . . . . . . . 108
3.5 Conclusion and Discussion . . . . . . . . . . . . . . . . . . . . . . 110
3.6 Appendix 1: Soundness of TAPAL . . . . . . . . . . . . . . . . . . 110
3.6.1 Grafting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.6.2 Soundness of R() . . . . . . . . . . . . . . . . . . . . . . 112
3.6.3 The Soundness of R() . . . . . . . . . . . . . . . . . . . 113
3.7 Appendix 2: Completeness of TPAL over F(PAL+) . . . . . . . . 116
II Applications 119
4 Knowability Paradox 121
4.1 The Paradoxes of Knowability and Previous Solutions . . . . . . . 123
4.1.1 Paradoxes . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.1.2 Logical Revision . . . . . . . . . . . . . . . . . . . . . . . . 125
4.1.3 Semantic Reformulation . . . . . . . . . . . . . . . . . . . 125
4.1.4 Syntactic Restriction . . . . . . . . . . . . . . . . . . . . . 126
4.1.5 Dynamic Epistemic Logic . . . . . . . . . . . . . . . . . . 126
4.2 Vericationism without the Knowability Thesis . . . . . . . . . . 127
4.2.1 Proposal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.2.2 Hand's Vericationist Account . . . . . . . . . . . . . . . . 130
4.3 TAPAL: Vericationist Interpretation . . . . . . . . . . . . . . . . 130
4.3.1 Interpreting TAPAL . . . . . . . . . . . . . . . . . . . . . . 131
4.3.2 Intended Semantics . . . . . . . . . . . . . . . . . . . . . . 132
4.3.3 Deductive System . . . . . . . . . . . . . . . . . . . . . . . 133
4.4 Logical Analysis of the Knowability Thesis . . . . . . . . . . . . . 134
4.4.1 New Knowability Thesis . . . . . . . . . . . . . . . . . . . 134
4.4.2 Fitch's Paradox and the Idealism Problem . . . . . . . . . 135
4.4.3 Comparison with Alternatives . . . . . . . . . . . . . . . . 136
4.5 Objections and Discussions . . . . . . . . . . . . . . . . . . . . . . 138
4.5.1 The axiom R3: perfect recall and no miracle . . . . . . . . 138
4.5.2 In Some Sense Knowable . . . . . . . . . . . . . . . . . . . 139
4.5.3 Logical Omniscience on Knowledge . . . . . . . . . . . . . 140
4.5.4 Why Do We Have to Buy the Semantics? . . . . . . . . . . 140
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5 Logical Omniscience and Deductive Inference 143
5.1 Stalnaker on the Problem of Logical Omniscience . . . . . . . . . 145
5.2 Explicit Knowledge and Deductive Inference . . . . . . . . . . . . 148
5.3 Formalizing Explicit Knowledge . . . . . . . . . . . . . . . . . . . 150
5.3.1 Reinterpretation of TPAL . . . . . . . . . . . . . . . . . . 150
5.3.2 Dynamic Characterization of Explicit Knowledge . . . . . 152
5.3.3 Epistemic Information and Protocol Information . . . . . . 154
5.3.4 Avoiding the Problem of Logical Omniscience . . . . . . . 155
5.4 Formalizing Deductive Inference . . . . . . . . . . . . . . . . . . . 157
5.5 Logical Omniscience vs. Epistemic Closure . . . . . . . . . . . . . 158
5.5.1 Formalizing the Epistemic Closure Principle . . . . . . . . 160
5.5.2 Independence . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.6 Concluding Discussion . . . . . . . . . . . . . . . . . . . . . . . . 164
5.6.1 Comparison with Other Systems . . . . . . . . . . . . . . . 164
5.6.2 Extension to Multi-agent with TDEL . . . . . . . . . . . . 166
Conclusion 167
Bibliography 169
Index 175
List of Symbols 179
Samenvatting 181