Name
Abstract | ||
|---|---|---|
This paper establishes model-theoretic properties of
$$\texttt {M} \texttt {E} ^{\infty }$$
, 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 (
$$\texttt {M} \texttt {E} $$
and
$$\texttt {M} $$
, respectively). For each logic
$$\texttt {L} \in \{ \texttt {M} , \texttt {M} \texttt {E} , \texttt {M} \texttt {E} ^{\infty }\}$$
we will show the following. We provide syntactically defined fragments of
$$\texttt {L} $$
characterising four different semantic properties of
$$\texttt {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}$$
belonging to the corresponding syntactic fragment, with the property that
$$\varphi $$
is equivalent to
$$\varphi ^\mathsf{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
$$\texttt {L} $$
-sentences.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00153-021-00797-0 | Archive for Mathematical Logic |
Keywords | Field | DocType |
Monadic first-order logic, Generalised quantifier, Infinity quantifier, Characterisation theorem, Preservation theorem, Continuity, 03C80, 03C40 | Discrete mathematics,Modulo,Quotient,Infinity,Decidability,Invariant (mathematics),Model theory,Predicate logic,Mathematics,Monotone polygon | Journal |
Volume | Issue | ISSN |
61 | 3 | 0933-5846 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Facundo Carreiro | 1 | 12 | 4.09 |
| Alessandro Facchini | 2 | 35 | 9.47 |
| Yde Venema | 3 | 609 | 65.12 |
| Fabio Zanasi | 4 | 110 | 13.89 |