Quantifiers and congruence closure

DOI10.1023/A:1005190726000MaRDI QIDQ1300006zbMATH OpenOpenAlexFDO

Authors Jörg Flum, Matthias Schiehlen, Jouko Väänänen

Publication date 25 October 2000

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1005190726000

zbMATH Keywords

bounded quantifierscongruence closure propertyexpressive power of quantifiers on finite structuresgeneralized quantifierHärtig quantifiermeager quantifiersmonadic quantifiersrelativizing quantifier

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80)

Review text

The authors investigate the expressive power of quantifiers on finite structures. They introduce the notion of bounded quantifiers and show that each relativizing quantifier which is bounded is first-order definable. They define meager quantifiers and show that no proper extension of first-order logic by means of meager quantifiers is weakly congruence-closed. They investigate the full congruence closure property and show that it fails in proper extensions of first-order logics by means of meager quantifiers, monadic quantifiers, and the Härtig quantifier.

Recommendations

• scientific article; zbMATH DE number 4083696
• Definability properties and the congruence closure
• Some results on quantifiers
• About \({|}/{|}\)-quantifiers
• Generalized Quantifiers and Logical Reducibilities
• scientific article; zbMATH DE number 4027448
• Artificial Intelligence and Symbolic Computation
• Generalized quantifiers, and beyond
• scientific article; zbMATH DE number 1136077
• scientific article; zbMATH DE number 1163950

Cited in

(7)

• First-order concatenation theory with bounded quantifiers
• scientific article; zbMATH DE number 4083696 (Why is no real title available?)
• Relational structures constructible by quantifier free definable operations
• scientific article; zbMATH DE number 3265727 (Why is no real title available?)
• Term Rewriting and Applications
• An arithmetical view to first-order logic
• Definability properties and the congruence closure

This page was built for publication: Quantifiers and congruence closure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1300006)