4 ms·

Another one is Presburger Arithmetic, which is Peano Arithmetic minus the multiplication. What makes it interesting (and useful) is that this removal makes the

• ogogmad 2y ago
  Skolem arithmetic is decidable too: https://en.wikipedia.org/wiki/Skolem_arithmetic https://en.wikipedia.org/wiki/Skolem_arithmetic I'm wondering whether there are decidable first-order theories about the natural numbers that are stronger than either Skolem or Presburger arithmetic, that presumably use more powerful number theory. Ask "Deep Research"? [edit] Found something without AI help: The theory of real-closed fields is decidable, PLUS the theory of p-adically closed fields is also decidable - then combined with Hasse's Principle, this might take you beyond Skolem. [edit] Speculating about something else: Is there a decidable first-order theory of some aspects of analytic number theory, like Dirichlet series? That might also take you beyond Skolem. https://en.wikipedia.org/wiki/Analytic_number_theory#Methods_of_analytic_number_theory https://en.wikipedia.org/wiki/Analytic_number_theory#Methods...
  • gwern 2y ago
    I recently learned about https://en.wikipedia.org/wiki/Self-verifying_theories https://en.wikipedia.org/wiki/Self-verifying_theories which gives you most of multiplication while still being decidable, which is pretty crazy.
    • ogogmad 2y ago
      That's cool, but where does it say it's decidable?
      • eru 2y ago
        Not on that Wikipedia page, but you might want to have a look at the papers?
  • ogogmad 2y ago
    Some decidable extensions of Skolem and Presburger, searched for and found by ChatGPT: https://chatgpt.com/share/67e1d302-c930-800f-bc2a-85bdc6056376 https://chatgpt.com/share/67e1d302-c930-800f-bc2a-85bdc60563...
    • culi 2y ago
      There are no specific extensions mentioned, a bunch of math symbol rendering issues, and what seems like maybe some hallucinations? Thanks for proving once again how useless chatgpt is if you're not already an expert on what you're asking it