Vicious Circles: On the Mathematics of Non-Wellfounded Phenomena

Title ......Page 3
Copyright ......Page 4
Dedication ......Page 5
Contents ......Page 7
Part I. Background ......Page 11
1 Introduction ......Page 13
1.1 Set theory and circularity ......Page 15
1.2 Preview ......Page 16
2.1 Some basic operations on sets ......Page 21
2.2 Sets and classes ......Page 25
2.3 Ordinals ......Page 27
2.4 The Axiom of Plenitude ......Page 31
2.5 The Axiom of Foundation ......Page 34
2.6 The axioms of set theory ......Page 37
Part II. Vicious Circles ......Page 41
3 Circularity in computer science ......Page 43
3.1 Streams ......Page 44
3.2 Labeled transition systems ......Page 45
3.3 Closures ......Page 50
3.4 Self-applicative programs ......Page 52
3.5 Common themes ......Page 55
4.1 Common knowledge and the Conway Paradox ......Page 57
4.2 Other intentional phenomena ......Page 59
4.3 Back to basics ......Page 60
4.4 Examples from other fields ......Page 61
5.1 The Liar Paradox ......Page 65
5.2 Paradoxes of denotation ......Page 67
5.3 The Hypergame Paradox ......Page 68
5.4 Russell\'s Paradox ......Page 69
5.5 Lessons from the paradoxes ......Page 70
Part III. Basic Theory ......Page 75
6 The Solution Lemma ......Page 77
6.1 Modeling equations and their solutions ......Page 80
6.2 The Solution Lemma formulation of AFA ......Page 82
6.3 An extension of the Flat Solution Lemma ......Page 84
7.1 Bisimilar systems of equations ......Page 87
7.2 Strong extensionality of sets ......Page 91
7.3 Applications of bisimulation ......Page 93
7.4 Computing bisimulation ......Page 97
8 Substitution ......Page 101
8.2 Substitution ......Page 102
8.3 The general form of the Solution Lemma ......Page 107
8.4 The algebra of substitutions ......Page 110
9 Building a model of ZFA ......Page 113
9.1 The model ......Page 114
9.2 Bisimulation systems ......Page 117
9.3 Verifying ZFC~ ......Page 119
9.4 Verifying AFA ......Page 121
Part IV. Elementary Applications ......Page 127
10.1 Graphs and the sets they picture ......Page 129
10.2 Labeled graphs ......Page 135
10.3 Bisimilar graphs ......Page 138
11 Modal logic ......Page 141
11.1 An introduction to modal logic ......Page 142
11.2 Characterizing sets by sentences ......Page 147
11.3 Baltag\'s Theorems ......Page 152
11.4 Proof theory and completeness ......Page 155
11.5 Characterizing classes by modal theories ......Page 159
12.1 Modeling games ......Page 169
12.2 Applications of games ......Page 175
12.3 The Hypergame Paradox resolved ......Page 180
13.1 Partial model theory ......Page 187
13.2 Accessible models ......Page 191
13.3 Truth and paradox ......Page 193
13.4 The Liar ......Page 197
13.5 Reference and paradox ......Page 201
14.1 The set A°° of streams as a fixed point ......Page 207
14.2 Streams, coinduction, and corecursion ......Page 210
14.3 Stream systems ......Page 215
Part V. Further Theory ......Page 219
15 Greatest fixed points ......Page 221
15.1 Fixed points of monotone operators ......Page 222
15.2 Least fixed points ......Page 224
15.3 Greatest fixed points ......Page 226
15.4 Games and fixed points ......Page 230
16 Uniform operators ......Page 233
16.1 Systems of equations as coalgebras ......Page 234
16.2 Morphisms ......Page 238
16.3 Solving coalgebras ......Page 240
16.4 Representing the greatest fixed point ......Page 243
16.5 The Solution Lemma Lemma ......Page 245
16.6 Allowing operations in equations ......Page 249
17 Corecursion ......Page 253
17.1 Smooth operators ......Page 254
17.2 The Corecursion Theorem ......Page 258
17.3 Simultaneous corecursion ......Page 265
17.4 Bisimulation generalized ......Page 268
Part VI. Further Applications ......Page 275
18 Some Important Greatest Fixed Points ......Page 277
18.1 Hereditarily finite sets ......Page 278
18.2 Infinite binary trees ......Page 282
18.3 Canonical labeled transition systems ......Page 285
18.4 Deterministic automata and languages ......Page 287
18.5 Labeled sets ......Page 291
19 Modal logics from operators ......Page 293
19.1 Some example logics ......Page 294
19.2 Operator logics defined ......Page 296
19.3 Characterization theorems ......Page 304
20.1 Paradise lost ......Page 311
20.2 What are ZFC and ZFA axiomatizations of? ......Page 313
20.3 Four criteria ......Page 317
20.4 Classes as a facon de par/er ......Page 319
20.5 The theory SEC0 ......Page 321
20.6 Parting thoughts on the paradoxes ......Page 329
21 Past, present, and future ......Page 333
21.1 The past ......Page 334
21.2 The present ......Page 335
21.3 The future ......Page 336
Appendix: definitions and results on operators ......Page 345
Answers to the Exercises ......Page 347
Bibliography ......Page 391
Index ......Page 395