Rosser’s undecidability theorem for very weak (fuzzy) arithmetics

Abstract

In [7, Theorem III], Rosser famously established that Peano Arithmetic was essentially undecidable, that is, that no consistent extension of it was decidable. After Rosser’s essential undecidability theorem, it was natural to ask for weaker theories of arithmetic that would still yield undecidability along similar lines. Three well known examples of such theories important for us are • Robinson arithmetics Q introduced in [6]. • Grzegorczyk’s arithmetics Q− , introduced in [1], where addition and multiplication are neither total nor functional. • Arithmetics R, also due to Robinson [9, p. 53], which contains only the minimal arithmetical facts which seem to be needed for the proof.