I’ve discussed Gödel’s Incompleteness theorems before, and sometimes pointed out that they carry an exception: if your logical system lacks sufficient power to describe the concept of a number, the theorems don’t apply. The theorems depend on being able to map logical expressions to numeric codes, after all. Defining numbers depends on a form of induction, so I thought that if your logical system has that then the theorems apply.

But via a recent blog post of Jeffrey Shallit, I’ve learned that’s not correct. The dividing line is not being able to define numbers, nor is it even addition. Robinson arithmetic is undecidable, yet Presburger arithmetic is. The former doesn’t officially have induction, while the latter does. The line isn’t multiplication, either;  Peano arithmetic adds multiplication to Robinson and is undecidable, yet Skolem arithmetic defines multiplication while still being decidable.

So I’ve been a bit too restrictive about when Gödel’s theorems apply. My apologies if I’ve misled anyone because of that.