Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).

  • $\begingroup$ In "two-variable arithmetic" does every sentence have an equivalent prenex form consisting of an $x$-quantifier and a $y$-quantifier (in some order) followed by an open formula? $\endgroup$ Apr 3 '16 at 9:13
  • $\begingroup$ No. In the first place, there are only finitely many formulae of the type you are talking about because the open formula can only say how x and y stand in relation to each other and the vocabulary is finite. $\endgroup$ Apr 3 '16 at 17:21
  • 1
    $\begingroup$ Sorry, I should have asked "Is every sentence equivalent to a boolean combination of 2-quantifier formulas in prenex form?" Also, It would be helpful if you said what you mean by "the two variable fragment of arithmetic". $\endgroup$ Apr 3 '16 at 19:04
  • 1
    $\begingroup$ @ThinniyamSrinivasanRamanatha That's true in a relational language, but not one with function symbols. There are infinitely many non-equivalent quantifier-free ("open") formulas, e.g. $x = y$, $x + x = y$, $x+x+x = y$, etc. $\endgroup$ Apr 3 '16 at 19:32
  • 1
    $\begingroup$ If we just look at sentences with two quantifiers, without allowing variables to be rebound, then the answer is positive in practice, and conjectured to be always positive -- see the answer and comment of @FelipeVoloch at mathoverflow.net/a/21503/44143 $\endgroup$
    – Matt F.
    Feb 8 '19 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.