8

A proposition p in a consistent formal language is decidable when we can assert either the truth of p or the truth of not p

(But not both, for then it would be inconsistent and we have already said that we are only dealing with consistent formal languages).

Godel famously showed that the theory of the usual arithmetic is undecidable.

What about simpler forms of arithmetic? There are two ways we can simplify:

  1. The usual arithmetic has two operations, addition and multiplication; what happens if we forget multiplication and just consider addition?

  2. We can truncate the integers; for example, there are such things as finite rings.

In the first we're simplifying the operations, and in the second we're simplifying the elements with which we do arithmetic with; thus we have a third option that combines the above:

  1. We could have just addition in a finite ring; this would be a cyclic group; the easy example here is adding time on a clock.

Are all these cases decidable?

Since undecidability is the more interesting notion did Gödel choose arithmetic because it was the simplest natural theory where the notion of undecidability first expresses itself?

  • Note: His theory did not show that arithmetic is undecidable. He showed that a self-referential system which is capable of proving all statement in arithmetic cannot be consistent and prove all statements in the system. If you don't have the self-reference, Godel's theorem says nothing. – Cort Ammon Sep 11 '16 at 5:44
  • @CortAmmon If you have arithmetic strong enough to express factorizations of numbers and compare them (via equality or subtraction), you construct the self reference via Goedel-numbering (using powers of primes to indicate the letters in the formulas) and you compare the proveable list to the constructed numbers. So it does not have to exist already. And it is pointless (to the point of being misleading) to list that as a requirement. – jobermark Oct 9 '16 at 0:37
  • @jobermark I missed the scoping of the question to consistent formal languages (the wording to get there was a bit unusual). You are correct within that scope. – Cort Ammon Oct 9 '16 at 1:06
  • @CortAmmon That is weirdly evasive. In what domain does arithmetic still act like arithmetic and yet not allow for the construction of the Goedel numbers? That is the only way an arithmetic domain can, in fact, not be self-referential. The thing does note even need to allow the follow-up diagonalization, the Godel numbers are, in and of themselves, going to make self-referential sentences. Injecting self-reference in spite of not allowing it by axiom is the genius of the whole thing. – jobermark Oct 9 '16 at 1:12
  • @jobermark You can define a consistent self-referential language which is not formal and embed arithmetic in it. As an example, consider a language whose symbols are taken from an uncountably infinite set. Such a language would defy construction of Godel numbers. I find the distinction important, given that it is common to believe that we live in a world whose behavior is specified by real numbers. – Cort Ammon Oct 9 '16 at 2:49
9

Yes, there are decidable arithmetics. But Gödel's original 1931 proof was in the framework of Russell's Principia Mathematica, chosen because it was the most developed logical framework for reproducing all of mathematics at the time. Later he simplified the proof and showed that the Peano Arithmetic was enough.

Along the lines of your first suggestion, there is the Presburger arithmetic, introduced in 1929, about a year before Gödel obtained his result. It has addition, equality, and even induction, but no multiplication. The absence of multiplication precludes the definition of Gödel numbering, and therefore the construction of Gödel sentences. This is not a proof of completeness, but it explains why it holds retroactively, Presburger himself produced an explicit deciding algorithm. An algorithm it may be, but it is not too easy, Fischer and Rabin proved in 1974 that the computational complexity of the decision problem is doubly exponential. An interesting factoid concerning the difference between the two arithmetics: Glivický and Kala recently produced a model of Presburger arithmetic where the Fermat Last Theorem fails, and there are infinitely many counterexamples. It is believed that this can not happen for the Peano arithmetic, although this does not technically follow from Wiles's proof, see Are there non-standard counterexamples to the Fermat Last Theorem?

It is not so easy to implement the other two suggestions because finiteness is property of a model, not of a formal theory. Attempts to write finiteness into (first order) axioms, a la Dedekind for example, produce something which is not what it intuitively means (there are infinite models of theories which "claim" in axioms to be finite). If we settle for a model with finite domain instead of a first order theory though, that of course will be decidable, because one can check all possibilities by exhaustive search.

There is a kind of arithmetic with finite models, which preserves all the resources of the Peano arithmetic, but replaces the classical logic with the paraconsistent logic LP. These are Priest's inconsistent arithmetics. Note a subtlety in the notion of completeness for inconsistent models: while there is a decision procedure that assigns true/false to each sentence, there will be some to which it assigns both, called true contradictions or dialetheias. The reason we can have a finite model is that we can have "inconsistent integers" for which n=n+1, this leads to a true contradiction but does not trivialize the theory, paraconsistent that it is. In fact, for all numbers smaller than the least inconsistent number N the model is identical to the usual Peano arithmetic, and Priest argues that we can not possibly know what is "true" of objects in our world if N is exorbitantly large, see his What could the least inconsistent number be?

This vindicates Wittgenstein's paradoxical opinion that incoherence is not a problem for calculational mathematics (or any language game), and his anticipation of paraconsistent logics:

"Something tells me that a contradiction in the axioms of a system can't really do any harm until it is revealed. We think of a hidden contradiction as like a hidden illness which does harm even though (and perhaps precisely because) it doesn't show itself in an obvious way. But two rules in a game which in a particular instance contradict each other are perfectly in order until the case turns up, and it's only then that it becomes necessary to make a decision between them by a further rule... Well then, don't draw any conclusions from a contradiction; make that a rule."

  • Re multiplication, although it's not "repeated addition", the usual binary multiplier en.wikipedia.org/wiki/Binary_multiplier implements it with addition plus a simple 2x2 (almost truth-like) table for binary digit multiplication, where 1-times-1=1 and all other entries are 0. So how does that very low-complexity little table turn a decidable theory into an undecidable one? (I guess there must be a simple approach to develop an answer, but I couldn't see it, or figure out how to ask the question so that google would cough up an answer.) – John Forkosh Sep 7 '16 at 3:22
  • Re: Glivicky and Kala's result, note that Fermat's last theorem can't even be stated in the language of Presberger arithmetic. What they actually prove is a bit more complicated; see arxiv.org/pdf/1602.03580v1.pdf. Also, note that arithmetic with only multiplication is also decidable (this is called Skolem arithmetic). – Noah Schweber Sep 7 '16 at 14:24
  • 1
    @John From what I understand the problem is that while you can rephrase atomic formulas involving multiplication in Presburger you can not rephrase ones that quantify over variables being multiplied, so things like "multiplication commutes for all numbers" or "1 times any number is itself" are ineffable, see math.stackexchange.com/questions/1109457/… – Conifold Sep 8 '16 at 0:45
  • None of this is mildly relevant to the question at hand. – Mozibur Ullah Sep 11 '16 at 4:30
  • @MoziburUllah Which is? – Conifold Sep 12 '16 at 20:06
1

An important example is the usual arithmetic of real numbers — a famous theorem of Tarski is that the theory of real closed fields is decidable.

From some point of view, the difficulty of integer arithmetic is precisely because there are aren't enough of them — the complexity of number theory comes from there being so many equations that don't have solutions. If you allow yourself to take roots of polynomials (and to be able to the real numbers out of the complex ones), the theory simplifies a lot.

  • Not only is the usual arithmetic of the real numbers decidable, but so are (consequently) of the usual arithmetics of the complex numbers, quaternions, etc. – Michael Smith Sep 30 '16 at 5:22
0

If Conifold's answer misses the point at all, given how expansive it is, then you must mean "Why did Goedel choose arithmetic?" And the answer has to be that the construction procedure would be too alien in any other form.

What is important, philosophically, is that stronger logic cannot always make things more decidable. Arithmetic is beside the point. But it is so ingrained in us that there is no point in avoiding it.

We know that ZF is not complete because we can build up arithmetic from set-theory, given the standard approach of defining the integers as a tower of initial segments of "omega". So we don't have to start from arithmetic as long as we hit it on the way by. In the case of set theory, it is not our main concern.

It seems to me that we know that the real problem hinges somehow on the strength of induction supporting recursion. Induction reduced to just the infinite set of axioms that remain first-order does not net you a proof. You get Presburger arithmetic, which is not strong enough to fail, unless you step outside of the system and pre-compute various facts of multiplication that one ordinarily deduces through complete induction over addition.

You don't necessarily even need full second-order induction, which is part of the original Peano definition. We get away with one pass of inductions to establish the behavior of addition and define multiplication, but then we only need the first-order version for the second pass of inductions.

Two passes of induction will evidently kill your ability to define truth in your system. If you want a strong, consistent system, one is not enough, and two is too many.

We can imagine that a non-arithmetic way of looking at this would still involve some concept of counting to base the equivalent of induction, but alternative concepts of counting seem like a waste of time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.