Numerical expressive power of logical languages with cardinality comparison
Xiaoxuan Fu, Zhiguang Zhao · Journal of Logic and Computation · 2024
Abstract In this paper, we investigate the numerical expressive power of various logical languages, encompassing fragments of Presburger Arithmetic (PbA), monadic second-order logic with counting with respect to finite domains (MSO$^{\phi }(\#)$) and shallow second-order graded modal logic with counting with respect to image-finite frames (SOGML$^{\textsf{s},\phi }$(#)). We show that in their respective existential fragments, the $1$-free fragment of PbA, the =-free fragment of MSO$^{\phi }(\#)$ and the graded modality-free fragment of SOGML$^{\textsf{s},\phi }$(#) possess equivalent numerical expressive power, specifically defining strongly semilinear sets. When adding universal quantifiers or adding $1$, = and graded modality to these three languages, the resulting definable sets become semilinear sets.