Abstract

We consider McCarthy's notions of predicate circumscription and formula circumscription. We show that the decision problems “does θ have a countably infinite minimal model” and “does φ hold in every countably infinite minimal model of θ” are complete Σ 1 2 and complete π 1 2 over the integers, for both forms of circumscription. The set of structures definable as first order definable subsets of countably infinite minimal models is the set of structures which are Δ 1 2 over the integers, for both forms of circumscription. Thus, restricted to countably infinite structures, predicate and formula circumscription define the same sets and have equally difficult decision problems. With general formula circumscription we can define several infinite cardinals, so the decidability problems are dependent upon the axioms of set theory