Decidability and definability with circumscription
type: Item
instance of: scholarly article
title: Decidability and definability with circumscription
zbMATH Open document ID: 0625.03017
DOI: 10.1016/0168-0072(87)90062-5
author: John S. Schlipf
published in: Annals of Pure and Applied Logic
publication date: 1987-01-01T00:00:00Z
review text: Circumscription was introduced by J. McCarthy to formalise everyday reasoning. Circumscribing the predicate formula F(R) with respect to R one obtains the value of R in a minimal model satisfying F(R). This is described by a second order \(\Pi^ 1_ 1\)-formula. The author shows that this complexity estimate is optimal for countable models. The predicates ``F has a countably infinite minimal model'' and ``G holds in every countably infinite model of F'' are respecitvely \(\Sigma^ 1_ 2\) and \(\Pi^ 1_ 2\) complete. If arbitrary models are allowed, then the expressive power of circumscription is measured by the least ordinal indescribable by a \(\Delta^ 1_ 2\)-formula. So it is more expressive than dynamic logic (which corresponds to the first non-recursive ordinal) and some questions about circumscription are independent of ZFC.
Mathematics Subject Classification ID: 03C85
Mathematics Subject Classification ID: 68T99
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 4014687
zbMATH Keywords: everyday reasoning
zbMATH Keywords: minimal model
zbMATH Keywords: countable models
zbMATH Keywords: infinite model
zbMATH Keywords: expressive power
zbMATH Keywords: circumscription
zbMATH Keywords: dynamic logic
reviewed by: G. E. Mints
MaRDI profile type: Publication
full work available at URL: 0168-0072(87)90062-5
OpenAlex ID: W2055029276
cites work: Q4075450
cites work: The mathematics of non-monotonic reasoning
cites work: On the satisfiability of circumscription
cites work: Q4146722
cites work: Circumscription - a form of non-monotonic reasoning
cites work: Definability in dynamic logic
cites work: Elementary induction on abstract structures
cites work: Descriptive set theory
cites work: Completeness results for circumscription
Recommended article: Decidability of Definability
Recommended article: Circumscription and implicit definability
Recommended article: Q4012238
Recommended article: Q4000240
Recommended article: Decidability of Circumscribed Description Logics Revisited
Recommended article: Decidability in analysis
Recommended article: Decidable and enumerable predicate logics of provability
Recommended article: On the computability of circumscription
Recommended article: Q5871535
description: scientific article; zbMATH DE number 4014687