@article{39ba6896-978b-42a6-9f4d-0e30e26e37fa, author = {Rafael Grimson, Bart Kuijpers}, title = {Some Fragments of Second-Order Logic Over the Reals for Which Satisfiability and Equivalence Are (Un)Decidable}, journal = {Reports on Mathematical Logic}, volume = {2014}, number = {Number 49}, year = {2014}, issn = {0137-2904}, pages = {23-34},keywords = {}, abstract = { We consider the Σ1-fragment of second-order logic over the vocabulary (+, ×, 0, 1, <, S1, ..., Sk), interpreted over the reals, where the predicate symbols Si are interpreted as semi- algebraic sets. We show that, in this context, satisfiability of formulas is decidable for the first-order ∃∗-quantifier fragment and undecidable for the ∃∗∀- and ∀∗-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.}, doi = {10.4467/20842589RM.14.002.2272}, url = {https://ejournals.eu/en/journal/reports-on-mathematical-logic/article/some-fragments-of-second-order-logic-over-the-reals-for-which-satisfiability-and-equivalence-are-un-decidable} }