3 ms·
Skolem arithmetic is decidable too: https://en.wikipedia.org/wiki/Skolem_arithmetic https://en.wikipedia.org/wiki/Skolem_arithmetic I'm wondering whether there
by 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 agoI 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 agoSome 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 agoThere 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