Filtrations and Basic Proof Theory Notes for Lecture 5
Note that !Σ is an equivalence relation. Let |w|Σ = {v | w !Σ v} denote the equivalence class of w under !Σ. Definition 1.1 (Filtration) Let M = 〈W,R, V 〉 be a Kripke model. Given a set of formulas closed under subformulas, a model Mf = 〈W f , Rf , V f 〉 is said to be a filtration of M through Σ provided • W f = {|w|Σ | w ∈W} • If wRv then |w|ΣR |v|Σ • If |w|ΣR |v|Σ then for each 3φ ∈ Σ, if M, v |= φ then M, w |= 3φ • V f (p) = {|w|Σ | w ∈ V (p)} /
FINITE MODELS CONSTRUCTED FROM CANONICAL FORMULAS
This paper obtains the weak completeness and decidability results for standard systems of modal logic using models built from formulas themselves. This line of work began with Fine (Notre Dame J. Form. Log. 16:229–237, 1975). There are two ways in which our work advances on that paper: First, the definition of our models is mainly based on the relation Kozen and Parikh used in their proof of the completeness of PDL, see (Theor. Comp. Sci. 113–118, 1981). The point is to develop a general model-construction method based on this definition. We do this and thereby obtain the completeness of most of the standard modal systems, and in addition apply the method to some other systems of interest. None of the results use filtration, but in our final section we explore the connection.
Vicious circles - on the mathematics of non-wellfounded phenomena
Part I. Background: 1. Introduction 2. Background on set theory Part II. Vicious Circles: 3. Circularity in computer science 4. Circularity in philosophy 5. Circularity and paradox Part III. Basic Theory: 6. The solution dilemma 7. Bisimulation Part IV. Elementary applications: 8. Graphs 9. Modal logic 10. Streams 11. Games 12. Modeling the semantic paradoxes Part V. Further Theory: 13. Greatest fixed points 14. Uniform operators 15. Corecursion Part VI. Further Applications: 16. Some applications 17. Modeling partial information 18. Circularity and the notion of set 19. Conclusions and future directions.