Carreiro, Facundo;
Facchini, Alessandro;
Venema, Yde;
Zanasi, Fabio;
(2021)
Model theory of monadic predicate logic with the infinity quantifier.
Archive for Mathematical Logic
, 61
pp. 465-502.
10.1007/s00153-021-00797-0.
Preview |
Text
s00153-021-00797-0.pdf - Accepted Version Download (586kB) | Preview |
Abstract
This paper establishes model-theoretic properties of ME∞, a variation of monadic first-order logic that features the generalised quantifier ∃ ∞ (‘there are infinitely many’). We will also prove analogous versions of these results in the simpler setting of monadic first-order logic with and without equality (ME and M, respectively). For each logic L∈ { M, ME, ME∞} we will show the following. We provide syntactically defined fragments of L characterising four different semantic properties of L-sentences: (1) being monotone and (2) (Scott) continuous in a given set of monadic predicates; (3) having truth preserved under taking submodels or (4) being truth invariant under taking quotients. In each case, we produce an effectively defined map that translates an arbitrary sentence φ to a sentence φp belonging to the corresponding syntactic fragment, with the property that φ is equivalent to φp precisely when it has the associated semantic property. As a corollary of our developments, we obtain that the four semantic properties above are decidable for L-sentences.
| Type: | Article |
|---|---|
| Title: | Model theory of monadic predicate logic with the infinity quantifier |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00153-021-00797-0 |
| Publisher version: | http://doi.org/10.1007/s00153-021-00797-0 |
| Language: | English |
| Additional information: | © The Author(s) 2021. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. |
| Keywords: | Monadic first-order logic, Generalised quantifier, Infinity quantifier, Characterisation theorem, Preservation theorem, Continuity |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10160498 |
Archive Staff Only
 |
View Item |
