Graduate studies at Western
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||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Johan 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):133-155.
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.
Sorry, there are not enough data points to plot this chart.
Added to index2011-05-29
Total downloads1 ( #292,081 of 739,304 )
Recent downloads (6 months)1 ( #61,243 of 739,304 )
How can I increase my downloads?