13
$\begingroup$

I was reading about quantifier elimination and discovered the Presburger Arithmetic, the article mentions two points about it:

  • It is decidable, complete and consistent.
  • It omits multiplication entirely.
  • It is weaker than Peano's arithmetic.

Whenever I hear about Peano's arithmetic, I also heard about it's undecidability/completeness/consistency. So, since it is complete, decidable and consistent why don't we use Presburger arithmetic instead? I know that it may has something to do with it's weakness, but it's not very clear what is the meaning of this weakness, presumably one can prove less things with it perhaps?

My other doubt about Presburger arithmetic is why is it a problem of it having no multiplication? I always see multiplication being defined after the operation of sum: The multiplication is just a given number of sums, can't we just make the multiplication and use it anyway or the multiplication causes problems?

Also, from the first theorem of incompleteness: "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete." Doesn't Presburger arithmetic have an elementary arithmetic?

The article I read counted only positive points in favor of Presburger arithmetic, I didn't see anything (explicitly) wrong with it's usage in the place of Peano Arithmetic.

$\endgroup$
10
  • 7
    $\begingroup$ We can't even state anything of number-theoretic interest in Presburger arithmetic. In particular, we cannot define multiplication. Yes, we can define $5\times 7$, but we cannot define $a\times b$. (Recall that sentences have finite length.) $\endgroup$ Jan 18 '15 at 19:07
  • 4
    $\begingroup$ Can you write "Every natural number greater than $1$ has a prime divisor" in Presburger Arithmetic? $\endgroup$
    – Asaf Karagila
    Jan 18 '15 at 19:09
  • 2
    $\begingroup$ One answer is that if multiplication were definable, the theory would be undecidable but it isn't. $\endgroup$ Jan 18 '15 at 19:17
  • 1
    $\begingroup$ @Vÿska The point is that if you could define it, one can prove that what you get is Peano arithmetic... As Presburger +multiplication = Peano, you either cannot define multiplication in Pre or, if you can, it is the same as peano. $\endgroup$
    – N. S.
    Jan 18 '15 at 19:18
  • 1
    $\begingroup$ @AndréNicolas: Since one can define $\mathfrak a$$\times$$\mathfrak b$ where $\mathfrak a$, $\mathfrak b$ are arbitrary numerals, but not $a$$\times$$b$, is it correct to say that Presburger Arithmetic captures the contentual, finitary 'part' of Peano Arithmetic but not the ideal 'part'? If so,the question becomes (for me, at least), how does one abstract the ideal from the finitary (as Hilbert seeks to do) without being able to produce the Goedel sentence (for his first incompleteness theorem)? $\endgroup$ Nov 24 '15 at 8:41
11
$\begingroup$

I'll try to answer your questions one by one hoping to be clear enough without making reference to very deep aspects (although your questions are already very deep):

  1. "So, since it is complete, decidable and consistent why don't we use Presburger arithmetic instead? I know that it may has something to do with it's weakness, but it's not very clear what is the meaning of this weakness, presumably one can prove less things with it perhaps?"

You are right in saying that Presburger Arithmetic proves less things. Mathematicians working in Number Theory usually like to talk about multiplication of natural numbers in general: an easy example is that they would like to have the property that "multiplication commutes for all natural numbers"; another example is that they like to talk about all the prime numbers at once. However with Presburgeer Arithmetic you cannot do that, if you check the axioms (http://en.wikipedia.org/wiki/Presburger_arithmetic) they don't talk about multiplication. So, you can only go number by number to define it. Short answer: Presburguer Arithmetic has many cute logical properties, but not enough mathematical richness, and that's why it is not "used" practically.

  1. "My other doubt about Presburger arithmetic is why is it a problem of it having no multiplication? I always see multiplication being defined after the operation of sum: The multiplication is just a given number of sums, can't we just make the multiplication and use it anyway or the multiplication causes problems?"

Yes we can, but as said earlier, we can only do it one number at a time. We would have to prove something like "the successor of the successor of zero (two) multiplied (imagine we just defined it as you suggested) with the successor of zero (one) is equal to the successor of the successor of zero." We would have to prove a theorem like this for every natural number, and it is not physically possible. We would also have to prove commutativity and associativity for multiplication by 2 for each natural number. In summary, this is not a very practical thing to do.

  1. "Also, from the first theorem of incompleteness: "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete." Doesn't Presburger arithmetic have an elementary arithmetic?"

Allow me to assume you read that in a Wikipedia article. Usually this kind of articles are written in a way that the general public understands it. However in mathematical terms a "theory capable of expressing elementary arithmetic" can be read as "a theory that at least can prove all of the axioms of PA". Hence, the answer to your question is "no", Presburger arithmetic doesn't have an elementary arithmetic. For more specific information of what you could interpret as "elementary arithmetic" you can check the MO question: https://mathoverflow.net/q/118183/32592

  1. "Why can't we define $a\times b$ for all natural numbers?"

This is rather hard to answer as I have not worked with the axioms of Presburger Arithmetic before (so take into account that the rest of the paragraph might not be very accurate). But let's try to attack another problem to get an idea of why this can't be done: How do you write in first order logic that there are two objects? $\exists x\exists y(x\neq y)$. How do you write that there are three objects? $\exists x\exists y\exists z(x\neq y\wedge x\neq z\wedge y\neq z)$. And so on. How do you write that there are infinite things? You would have to use an infinitely long formula which is physically impossible. If you want to define multiplication in Presburger Arithmetic, you would have to do something similar and you would need an infinitely long formula too.

One could also think that if Presburger arithmetic lacks multiplication, then we can do arithmetic without addition and just having multiplication. It turns out that such a system is also complete and consistent but it still has the practicality issue pointed above: https://mathoverflow.net/a/19874/32592

$\endgroup$
11
$\begingroup$

Godel's incompleteness theorem, philosophically (and morally) speaking it says that a consistent theory cannot have all the following properties:

  1. Can be handled algorithmically (not too complicated)
  2. Interesting as a foundational theory (can prove useful statements)
  3. Complete (every statement over it is provable or disprovable)

From $\sf PA$ we expect the first two conditions to be true: we want it to be at least somewhat "computer friendly", and we want it to allow us to do things we normally do with the natural numbers (things like investigate the structure of prime numbers, and so on).

The language of Presburger arithmetic omits multiplication, and since the theory is consistent, recursive, and complete, it follows that it cannot properly interpret multiplication either (if it could, we would get $\sf PA$ in full). So there is no formula $\varphi(x)$ in the language of Presburger arithmetic, such that Presburger arithmetic proves $\varphi(x)$ if and only if $x$ is a prime number.

It follows, if so, that Presburger arithmetic cannot prove that every natural number $>1$ has a prime divisor. If it could, ask what are the numbers which have no nontrivial divisors, and you get the prime numbers.

This shows how weak the theory is, compared to $\sf PA$, and why we don't use it to investigate the natural numbers.

$\endgroup$
2
  • $\begingroup$ @user21820: I'm not sure why the edit was necessary. $\endgroup$
    – Asaf Karagila
    Mar 22 '16 at 6:49
  • 1
    $\begingroup$ Originally you said something like "a consistent theory is either too complicated to handle algorithmically; non-interesting as a foundational theory; or incomplete." and then in the second paragraph you said "we expect the first two conditions to be true... so I reworded your first paragraph so that it is not incongruous with the second, that's all. $\endgroup$
    – user21820
    Mar 22 '16 at 11:43

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.