The Journal of Symbolic Logic

Research Article

Minimal predicates, fixed-points, and definability

Johan Van Benthem

Institute for Logic, Language and Computation Illc, Universiteit Van Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Nederlands E-mail:, johan@science.uva.nl

Department of Philosophy, Stanford University, Stanford. CA 94305-2155., USA E-mail:, johan@science.uva.nl

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 guarantees 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.

(Received January 23 2004)

(Revised October 19 2004)