Model Theory of Monadic Predicate Logic with the Infinity Quantifier

DOI10.1007/S00153-021-00797-0MaRDI QIDQ6306481arXivWikidataFDO

Authors Facundo Carreiro, Alessandro Facchini, Yde Venema, Fabio Zanasi

Publication date 10 September 2018

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00153-021-00797-0

Mathematics Subject Classification ID

Interpolation, preservation, definability (03C40) Logic with extra quantifiers and operators (03C80)

arXiv classification

cs.LOmath.LO

Abstract: This paper establishes model-theoretic properties of $mathrm{FOE}^{infty}$, a variation of monadic first-order logic that features the generalised quantifier $exist{s}^{i}nfty$ (`there are infinitely many'). We provide syntactically defined fragments of $mathrm{FOE}^{infty}$ characterising four different semantic properties of $mathrm{FOE}^{infty}$-sentences: (1) being monotone and (2) (Scott) continuous in a given set of monadic predicates; (3) having truth preserved under taking submodels or (4) invariant under taking quotients. In each case, we produce an effectively defined map that translates an arbitrary sentence $varphi$ to a sentence $varph{i}^p$ belonging to the corresponding syntactic fragment, with the property that $varphi$ is equivalent to $varph{i}^p$ precisely when it has the associated semantic property. Our methodology is first to provide these results in the simpler setting of monadic first-order logic with ($mathrmFOE$) and without ($mathrmFO$) equality, and then move to $mathrm{FOE}^{infty}$ by including the generalised quantifier $exist{s}^{i}nfty$ into the picture. As a corollary of our developments, we obtain that the four semantic properties above are decidable for $mathrm{FOE}^{infty}$-sentences. Moreover, our results are directly relevant to the characterisation of automata and expressiveness modulo bisimilirity for variants of monadic second-order logic. This application is developed in a companion paper.

This page was built for publication: Model Theory of Monadic Predicate Logic with the Infinity Quantifier

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