Bès, Alexis - Expansions of MSO by cardinality relations

lmcs:747 - Logical Methods in Computer Science, December 5, 2013, Volume 9, Issue 4
Expansions of MSO by cardinality relations

Authors: Bès, Alexis

We study expansions of the Weak Monadic Second Order theory of (N,<) by cardinality relations, which are predicates R(X1,...,Xn) whose truth value depends only on the cardinality of the sets X1, ...,Xn. We first provide a (definable) criterion for definability of a cardinality relation in (N,<), and use it to prove that for every cardinality relation R which is not definable in (N,<), there exists a unary cardinality relation which is definable in (N,<,R) and not in (N,<). These results resemble Muchnik and Michaux-Villemaire theorems for Presburger Arithmetic. We prove then that + and x are definable in (N,<,R) for every cardinality relation R which is not definable in (N,<). This implies undecidability of the WMSO theory of (N,<,R). We also consider the related satisfiability problem for the class of finite orderings, namely the question whether an MSO sentence in the language {<,R} admits a finite model M where < is interpreted as a linear ordering, and R as the restriction of some (fixed) cardinality relation to the domain of M. We prove that this problem is undecidable for every cardinality relation R which is not definable in (N,<).


Source : oai:arXiv.org:1310.8182
DOI : 10.2168/LMCS-9(4:18)2013
Volume: Volume 9, Issue 4
Published on: December 5, 2013
Submitted on: April 20, 2013
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic


Share

Consultation statistics

This page has been seen 86 times.
This article's PDF has been downloaded 55 times.