Epistemic Dynamics and Protocol Information [PhD Thesis]

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

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 Veri cationism without the Knowability Thesis . . . . . . . . . . 127
4.2.1 Proposal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.2.2 Hand's Veri cationist Account . . . . . . . . . . . . . . . . 130
4.3 TAPAL: Veri cationist 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