Minimal Predicates. Fixed-Points, and Definability

Journal of Symbolic Logic 70 (3):696 - 712 (2005)

Authors
Johan Van Benthem
University of Amsterdam
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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,683
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 Bounded Proof Property Via Step Algebras and Step Frames.Nick Bezhanishvili & Silvio Ghilardi - 2014 - Annals of Pure and Applied Logic 165 (12):1832-1863.
The Many Faces of Interpolation.Johan van Benthem - 2008 - Synthese 164 (3):451-460.

View all 7 citations / 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.

Analytics

Added to PP index
2011-05-29

Total views
17 ( #474,810 of 2,242,830 )

Recent downloads (6 months)
7 ( #254,543 of 2,242,830 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature