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 (categorize this paper)
DOI 10.2178/jsl/1122038910
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 29,495
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
The Many Faces of Interpolation.van Benthem Johan - 2008 - Synthese 164 (3):451-460.
The Bounded Proof Property Via Step Algebras and Step Frames.Nick Bezhanishvili & Silvio Ghilardi - 2014 - Annals of Pure and Applied Logic 165 (12):1832-1863.

Add more citations

Similar books and articles
Minimal Predicates, Fixed-Points, and Definability.Johan van Benthem - 2005 - Journal of Symbolic Logic 70 (3):696-712.
Fixed Point Logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.
On the Weak Kleene Scheme in Kripke's Theory of Truth.James Cain & Zlatan Damnjanovic - 1991 - Journal of Symbolic Logic 56 (4):1452-1468.
On the Logic of Natural Kinds.Nino Cocchiarella - 1976 - Philosophy of Science 43 (2):202-222.
Definability of Types, and Pairs of o-Minimal Structures.Anand Pillay - 1994 - Journal of Symbolic Logic 59 (4):1400-1409.
The Expressive Power of Fixed-Point Logic with Counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
Added to PP index
2011-05-29

Total downloads
9 ( #494,003 of 2,210,566 )

Recent downloads (6 months)
1 ( #356,847 of 2,210,566 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature