Publication Date:
2021-10-27
Description:
This paper establishes model-theoretic properties of $$exttt {M} exttt {E} ^{infty }$$ M E ∞ , a variation of monadic first-order logic that features the generalised quantifier $$exists ^infty $$ ∃ ∞ (‘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 ($$exttt {M} exttt {E} $$ M E and $$exttt {M} $$ M , respectively). For each logic $$exttt {L} in { exttt {M} , exttt {M} exttt {E} , exttt {M} exttt {E} ^{infty }}$$ L ∈ { M , M E , M E ∞ } we will show the following. We provide syntactically defined fragments of $$exttt {L} $$ L characterising four different semantic properties of $$exttt {L} $$ 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 $$varphi $$ φ to a sentence $$varphi ^mathsf{p}$$ φ p belonging to the corresponding syntactic fragment, with the property that $$varphi $$ φ is equivalent to $$varphi ^mathsf{p}$$ φ 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 $$exttt {L} $$ L -sentences.
Print ISSN:
0933-5846
Electronic ISSN:
1432-0665
Topics:
Mathematics
Permalink