Tytuł pozycji:
Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable
We consider the Σ10 -fragment of second-order logic over the vocabulary [+;x; 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 THERE EXISTS-quantifier fragment and undecidable for the THERE EXISTS*FOR ALL- and FOR ALL*-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.