Minimal Predicates. Fixed-Points, and Definability
Journal of Symbolic Logic 70 (3):696 - 712 (2005)
| Abstract | Minimal predicates P satisfying a given first-order description ϕ(P) occur widely in mathematical logic and computer science. We give an explicit first-order syntax for special first-order 'PIA conditions' ϕ(P) which quarantees unique existence of such minimal predicates. Our main technical result is a preservation theorem showing PIA-conditions to be expressively complete for all those first-order formulas that are preserved under a natural model-theoretic operation of 'predicate intersection'. Next, we show how iterated predicate minimization on PIA-conditions yields a language MIN(FO) equal in expressive power to LFP(FO), first-order logic closed under smallest fixed-points for monotone operations. As a concrete illustration of these notions, we show how our sort of predicate minimization extends the usual frame correspondence theory of modal logic, leading to a proper hierarchy of modal axioms: first-order-definable, first-order fixed-point definable, and beyond. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,875 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJohan van Benthem (2005). Minimal Predicates, Fixed-Points, and Definability. Journal of Symbolic Logic 70 (3):696-712.
Anuj Dawar & Yuri Gurevich (2002). Fixed Point Logics. Bulletin of Symbolic Logic 8 (1):65-88.
Bektur Sembiuly Baizhanov (2001). Expansion of a Model of a Weakly o-Minimal Theory by a Family of Unary Predicates. Journal of Symbolic Logic 66 (3):1382-1414.
James Cain & Zlatan Damnjanovic (1991). On the Weak Kleene Scheme in Kripke's Theory of Truth. Journal of Symbolic Logic 56 (4):1452-1468.
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Craig Smorynski (1979). Calculating Self-Referential Statements, I: Explicit Calculations. Studia Logica 38 (1):17 - 36.
Nino Cocchiarella (1976). On the Logic of Natural Kinds. Philosophy of Science 43 (2):202-222.
Michael Benedikt & H. Jerome Keisler (2003). Definability with a Predicate for a Semi-Linear Set. Journal of Symbolic Logic 68 (1):319-351.
Johan Van Benthem (2006). Modal Frame Correspondences and Fixed-Points. Studia Logica 83 (1-3).
Johan Van Benthem (2006). Modal Frame Correspondences and Fixed-Points. Studia Logica 83 (1/3):133 - 155.
Anand Pillay (1994). Definability of Types, and Pairs of o-Minimal Structures. Journal of Symbolic Logic 59 (4):1400-1409.
Martin Otto (1996). The Expressive Power of Fixed-Point Logic with Counting. Journal of Symbolic Logic 61 (1):147-176.
Giovanni Sambin (1976). An Effective Fixed-Point Theorem in Intuitionistic Diagonalizable Algebras. Studia Logica 35 (4):345 - 361.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2011-05-29Total downloads1 ( #277,406 of 556,840 )Recent downloads (6 months)1 ( #64,931 of 556,840 )How can I increase my downloads? |
My notes
Discussion
