Fixed-point extensions of first-order logic
type: Item
instance of: scholarly article
title: Fixed-point extensions of first-order logic
zbMATH Open document ID: 0621.03013
DOI: 10.1016/0168-0072(86)90055-2
author: Yuri Gurevich
author: S. Shelah
published in: Annals of Pure and Applied Logic
publication date: 1986-01-01T00:00:00Z
full work available at URL: http://hdl.handle.net/2027.42/26387
review text: The authors define fixed-point-extensions of first-order logic by the least fixed point predicate LFP, by the monotone fixed point predicate LFP', and the inflationary fixed point predicate IFP, respectively. It is proved that these three extensions have the same expressive power on finite structures.
Mathematics Subject Classification ID: 03B60
zbMATH DE Number: 4006239
zbMATH Keywords: fixed-point-extensions of first-order logic
zbMATH Keywords: least fixed point
zbMATH Keywords: monotone fixed point predicate
zbMATH Keywords: inflationary fixed point predicate
zbMATH Keywords: expressive power on finite structures
reviewed by: Erica Melis
MaRDI profile type: Publication
OpenAlex ID: W2059144726
Wikidata QID: Q105978978
cites work: Monotone versus positive
cites work: A zero-one law for logic with a fixed-point operator
cites work: Model theory
cites work: Q5649409
cites work: The complexity of explicit definitions
cites work: Q3758820
cites work: On monotone vs. nonmonotone induction
cites work: Q4168046
cites work: Q3919123
cites work: Properties preserved in subdirect products
cites work: Elementary induction on abstract structures
cites work: On nonmonotone inductive definability
cites work: Q5624635
cites work: Q5665177
cites work: Q5724782
cites work: Q3347338
Recommended article: Q4858033
Recommended article: Q3204028
Recommended article: Fixed Point Logics
Recommended article: Extended First-Order Logic
Recommended article: Q5483318
Recommended article: Q3681906
Recommended article: Q3204446
Recommended article: Extended Lambek Calculi and First-Order Linear Logic
Recommended article: Axiomatizing fixpoint logics
Recommended article: Fixed-point logics, generalized quantifiers, and oracles
description: scientific article; zbMATH DE number 4006239