# Why does undecidability of arithmetic not follow from that of first-order logic?

As far as I understand, first-order arithmetic incorporates first-order logic. It is a fact that a first-order logic with at least two binary predicates is undecidable. Doesn't this imply immediately the undecidability of arithmetic?

• Actually you only need one binary predicate for undecidability. However, as you add axioms, the set of provable sentences grows and may or may not become decidable depending on what axioms you add. – Rob Arthan Oct 27 '13 at 16:29
• @RobArthan sorry, I meant two predicates including equality. The thing I still don't understand is how can it become decidable? See my comment to André Nicolas's answer. – level1807 Oct 27 '13 at 16:42
• Actually, you don't even need equality for undecidability. Just one binary predicate (that is not necessarily equality) will do. – Rob Arthan Oct 28 '13 at 1:07
• Indeed, it is also well known that these two sets (arithmetic truths versus firs-order validities) have different Turing (undecidability) degrees. In particular, there is no computable reduction reducing "arithemtic truths" to "first-order validities". If you want to take a deeper look at this I suggest you start looking at the artihmetical hierarchy (for instance, at wikipedia en.wikipedia.org/wiki/Arithmetical_hierarchy ) – boumol Oct 28 '13 at 11:11

Suppose you have two binary predicates $R$ and $S$. If you add the axiom $(\forall x)(\forall y)[R(x,y) \land S(x,y)]$, the resulting theory is complete and decidable. Basically, with that axiom $R$ and $S$ are always true, so you can replace them with "True" and ignore all quantifiers.
One can make an argument along those lines, by making "incorporates" precise enough. However, note that the first-order theory of algebraically closed fields of characteristic $0$ is decidable, as is the theory of real-closed fields.