Uniform definition of sets using relations and complement of Presburger Arithmetic

2016/11/11 by Milchior, Arthur
#03B10 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1611.03839

Abstract

In 1996, Michaux and Villemaire considered integer relations R which are not definable in Presburger Arithmetic. That is, not definable in first-order logic over integers with the addition function and the order relation (FO[N,+,

Related

• Undefinability of multiplication in Presburger arithmetic with sets of powers
• One-Variable Logic Meets Presburger Arithmetic
• Uniformity_and_nonuniformity
• Arithmetic, First-Order Logic, and Counting Quantifiers
• The First-Order Theory of Sets with Cardinality Constraints is Decidable