1
$\begingroup$

According to Wikipedia, Presberger Arithmetic is the first-order theory of the natural numbers with addition. It can be proved to be consistent, complete, and decidable.

Though it contains no axioms per se regarding multiplication or division, it certainly has wffs of the following type:

$n_1$+$n_2$+...+$n_m$=b, where $n_1$=$n_2$=...=$n_m$ (i.e., n is added 'm times').

This, of course is just the elementary-school definition of 'multiplication'. The elementary-school definition of 'division' can be (seemingly) defined from this also, by 'stipulation'. The notions of 'divisibility' and 'prime number' can also be (seemingly) defined in Presburger Arithmetic by 'stipulation' just as they were defined in elementary school.

Since all one has (seemingly) done is stipulated a particular type of 'addition' as 'multiplication' (and defined the notions of 'division', 'divisibility', and 'prime number' from this stipulation) one seems still safely within the bounds of Presburger arithmetic, and Presburger Arithmetic with these stipulations is still consistent, complete, and decidable(?).

Question: How does Peano Arithmetic differ from Presburger Arithmetic with the aforementioned stipulated 'definitions'?

$\endgroup$
  • 2
    $\begingroup$ Think about how you would define divisibility using this idea: it'd look something like $\exists m:\exists n_1,n_2,...,n_m:\text{(everything else)}$. This is not a first order formula, because number of quantifiers must be fixed in a single first order formula, and in this example, it depends on $m$. $\endgroup$ – Wojowu Oct 24 '15 at 7:08
  • $\begingroup$ Note that with this idea you can, for any single fixed $m$, exhibit a formula $P(a)$ which represents $m\mid a$, but not a single formula $P(m,a)$ which works for every $m$. $\endgroup$ – Wojowu Oct 24 '15 at 7:10
  • $\begingroup$ @Wojowu: So you are saying, in effect, that one cannot define 'multiplication' in Presburger Arithmetic as 'addition' of a 'distinguished type', that is, of "n+n+n...+n=b" because the number of times 'n' is added to itself ('m times') takes us out of first-order definition into the realm of second-order definitions? As regards your comment immediately prior to this, cannot $P$$($$m$,$a$$)$ be a schematized definition in Presburger Arithmetic? $\endgroup$ – Thomas Benjamin Oct 24 '15 at 7:26
  • $\begingroup$ I'm not sure what "schematized definition" is, but what I can tell you is that your definition of multiplication is external. This is to say, if we want to talk about this multiplication, we cannot do it in Presburger arithmetic. If we denote "$n+...+n$ $m$ times" as $n*m$, then we can make claims like "for every $n,m$ Presburger proves existence of $n*m$", but it makes no real sense to state "Presburger arithmetic proves "for all $n,m$, $n*m$ exists"", because the latter cannot be even expressed in the langauge of Presburger arithmetic. $\endgroup$ – Wojowu Oct 24 '15 at 7:33
  • $\begingroup$ Also, as more of a side note, definition of multiplication as "$n+...+n$ $m$ times" is not even second order. $\endgroup$ – Wojowu Oct 24 '15 at 7:33
3
$\begingroup$

I'll give first a proof that multiplication can't be defined in Presburger arithmetic by characterizing exactly the sets definable in this theory; in order to do this, I'll assume as known, but won't prove the results from Presburger himself about quantifier elimination for this theory. In particular, I'll assume that every formula in Presburger arithmetic is equivalent to one of four basic forms, to be specified. I'll then close with some more general remarks about this undefinability phenomenon. Incidentally, if you want a proof of quantifier elimination for Presburger arithmetic, I suggest checking out an introductory logic textbook, such as Enderton's, Hinman's, or Monk's. Smoryński's Logical Number Theory I also contains a rather detailed account of Presburger arithmetic, including the quantifier elimination procedure (which is rather tricky) and the result I'm about to prove.

Let's start with a definition: a set $X$ of natural numbers is eventually periodic iff there exist some positive numbers $p$ and $n$ such that, for all $x > n$, $x \in X \iff x+p \in x$ ($p$ is usually called the period of $X$).

Claim: that every finite and co-finite set is eventually periodic.

Proof: Suppose $X$ is finite and let $n \in X$ be the greatest element of $X$. Then, for every $x > n$, $x \in X \iff x + 1 \in X$ (clearly), so $X$ is eventually periodic. Similarly, let $X$ be a co-finite set and let $X'$ be its complement. Since $X$ is co-finite, $X'$ is finite. Let $n \in X'$ be its greatest element. Then, for every $x > n$, $x \not \in X'$, whence $x \in X$. Thus, for this $n$, $x \in X \iff x+1 \in X$, so $X$ is eventually periodic.

Next, I'll show that every set definable in Presburger arithmetic is eventually periodic. The proof relies on the quantifier elimination procedure. Using this procedure, it's possible to show that every formula from Presburger arithmetic is equivalent to a Boolean combination of four basic types:

\begin{align} n v_0 &= k\\ n v_0 &< k\\ k &< n v_0 \\ n v_0 &\equiv_m k \end{align}

Where $n v_0$ denotes $v_0 + \dots + v_0$ $n$ many $v_0$'s, $n v_0 + m \equiv_s k$ has the usual interpretation, $k$ is a fixed numeral (obtained by repeated application of the successor function to $0$), and with the convention that $0 v_0$ denotes $0$.

Claim: these four basic types define eventually periodic sets.

Proof: In the cases in which $n = 0$, each formula above reduces to a sentence that is either true or false. In the former case, the sentence will then define $\omega$, whereas in the latter case the sentence will define $\varnothing$, both of which are eventually periodic sets. Consider thus $n \geq 1$.

In the first two cases, the formulas will define finite sets (in the first one, a singleton, in the latter, the sets of multiples of $n$ less than $k$), which, by the above, are always eventually periodic. In the third case, the formula will define a co-finite set, which again, by the above, is eventually periodic.

For the final case, let $d$ be the greatest common divisor of $n$ and $m$. If $d$ doesn't divide $k$, then the formula is not satisfiable by any natural number, whence it defines $\varnothing$, which is eventually periodic. On the other hand, if $d$ dives $k$, then divide $m$, $n$, and $k$ to obtain $m_0 v_0 \equiv_{n_0} k_0$, with $m_0$, $n_0$, and $k_0$ relatively prime. Using basic facts from modular arithmetic, it follows that $m_0$ has a multiplicative inverse $m'$ modulo $n_0$ (because $m_0$ and $n_0$ are relatively prime), whence we also have that $m'm_0 v_0 \equiv_{n_0} m' k$, i.e. $v_0 \equiv_{n_0} m' k$ (you can check any basic text on modular arithmetic for this). But this obviously defines a periodic set, so an eventually periodic set. This ends the proof.

Since any definable set in Presburger arithmetic must be obtained from those four basic types above, it follows that all definable sets in Presburger arithmetic are eventually periodic. From this it follows easily that the multiplication function is not definable in Presburger arithmetic.

Claim: the multiplication relation $R_\times = \{\langle m, n, p\rangle \; | \; p = m \times n \in \omega \}$ is not definable in Presburger arithmetic.

Proof: The idea is simple. If we could define $R_\times$, we could use it to define (say) the set of squares. But the set of squares is not eventually periodic, so it's not definable in Presburger arithmetic. Therefore, $R_\times$ is not definable in Presburger arithmetic.


Some comments: the above gives a rather abstract answer to your question, but it does not answer directly why the procedure outlined in your question won't work. In particular, for each $n$, we can define, for a fixed $m$, the operation $n \times m$ (just use the repeated addition trick). So why can't we somehow merge these definitions into a single one which would capture multiplication? The short answer is: for that, we would need to use recursion (in fact, primitive recursion), but Presburger arithmetic is not enough to capture to recursive functions. In particular, say that a theory $T$ captures a binary function $f$ iff for any $m$, $n$ and $p$, if $f(m, n) = p$, then there's a formula $\phi(x, y, z)$ in $T$ such that $T$ proves that $\forall y(\phi(m, n, y) \iff y = p)$ (where $m, n, p$ are constants with the obvious denotations). Although we may have infinitely many formulas that "approximate" multiplication, there's no single formula that will do this work inside Presburger arithmetic.

$\endgroup$
  • $\begingroup$ Could Primitive Recursive Arithmetic be construed as an extension by definitions of Presburger Arithmetic (the notion of "extension by definition" is found on pp. 57-61 of Shoenfield's book $Mathematical$ $Logic$)? $\endgroup$ – Thomas Benjamin Oct 28 '15 at 0:32
  • 1
    $\begingroup$ @ThomasBenjamin - No, because if $T'$ is an extension by definitions of $T$, then $T'$ has the same definable sets as $T$. But if we introduce the primitive recursive functions into Presburger arithmetic, multiplication becomes definable (by primitive recursion on addition), which shows that Presburger Arithmetic + PRA can define a set which Presburger arithmetic alone can't. $\endgroup$ – Nagase Oct 28 '15 at 18:19
  • $\begingroup$ Did you mean to say "Presburger Arithmetic +$PRA$" or did you mean to say "Presburger Arithmetic + $Primitive$ $Recursive$ $Functions$"? $\endgroup$ – Thomas Benjamin Oct 28 '15 at 19:06
  • $\begingroup$ @ThomasBenjamin - Sorry, I meant the latter, in the sense of augmenting Presburger Arithmetic with a primitive recursion scheme, either for all primitive recursive function, or else just for addition (both won't be extensions by definitions of Presburger arithmetic). $\endgroup$ – Nagase Oct 28 '15 at 19:37
  • 2
    $\begingroup$ @ThomasBenjamin - That's not the definition of multiplication. As Wojowu explained in the comments above, that will give you, for each $n$, a definition for, say, $\times_n$, where $\times_n(v_0)$ is as in your definition. As I said in the comments at the end of my answer, however, that won't provide you with a uniform definition of multiplication of the form $\phi(x, y, z)$ (in the language of Presburger arithmetic) such that Presburger arithmetic is able to prove $\forall x, y, z (\phi(x, y, z) \iff \times(x, y) = z)$. That is what missing. $\endgroup$ – Nagase Oct 28 '15 at 19:46
2
$\begingroup$

You're right that Presburger arithmetic can talk about (standard) individual instances of multiplication. Here's why that doesn't get you very far:

  • There's no way to talk about nonstandard instances of multiplication. Suppose $(N, +)$ is a nonstandard model of Presburger arithmetic, with $c$ a nonstandard element. How would you define "$c\times c$"?

  • There's no way to talk about variable multiplication. You move blithely from individual instances of multiplication to "is prime," but if you try to write down a first-order sentence defining primality, you'll run into problems. It gets even worse if you try to involve aternating quantifiers - how would you define something like "square-free"? "A product of seven square-free numbers?" Etc. Even schemes won't really help you here - what you need are infinitary formulas. And sure enough this will make Presburger arithmetic complicated - even "computable infinitary" Presburger arithmetic is extremely complicated. But that's a very different thing than first-order Presburger arithmetic.

$\endgroup$
  • $\begingroup$ Note that a single infinitary sentence, using just one infinite disjunction, is strong enough to characterize $(\mathbb{N}, 0, +)$ up to isomorphism. So even allowing a little infinitarity can wreak great havoc. $\endgroup$ – Noah Schweber Oct 24 '15 at 20:45
  • $\begingroup$ I'd like to see (so to speak) the infinitary disjunction you speak of. Thanks in advance. Also, consider (for example) the 'Hilbertian' number-signs |,||,|||,... . One can easily define 'addition' via concatination 'subtraction' by $\mathfrak n$ by removal of $\mathfrak n$ strokes, 'multiplication' by concatination of n groupings of m strokes (does this mean that we ascend into the realm of the "ideal" when one multiplies?), and division by 'partitioning', say, the numeral |||| into [||][||]. $\endgroup$ – Thomas Benjamin Oct 28 '15 at 12:55
  • $\begingroup$ (cont.) From these operations one should be able to define the property of 'primeness' ("$\mathfrak m$ is a prime number"), assuming $\mathfrak m$ represents a prime number by the inability to partition $\mathfrak m$ into groupings of any other numeral except for $\mathfrak m$ and | (what elementary property of numerals could not be defined in terms of these operations?). The question is, is there a way to abstract the Hilbertian numerals with these operations in a first-order theory that is consistent, complete, and decidable (as Presburger Arithmetic is)? $\endgroup$ – Thomas Benjamin Oct 28 '15 at 13:11
  • $\begingroup$ @ThomasBenjamin "One should be able to . . ." No. Try actually writing down a first-order definition of primeness, in the language of Presburger arithmetic (or the variant of your choice - using Hilbert numerals really doesn't change anything) - or if you aren't limiting yourself to first-order definitions, make clear what kind of definition you are interested in. The answer to the question at the end of your comment is pretty obviously "no," since that would contradict Godel. When you're talking about modifications of logical systems, please be precise. $\endgroup$ – Noah Schweber Oct 28 '15 at 19:25
  • $\begingroup$ (As to the infinitary definitions: first, you want an infinitary sentence saying "every natural number is standard." This would just be $\forall x(\bigvee x=SS. . . .S0)$. Next, to say "$x$ is prime," you would write the conjunction (over $n>0$) of the formulas $\pi_n(x)$, where $\pi_n(x)\equiv n\not=x\implies \forall k(k+ . . . +k\not=x)$ (with $n$ "+" signs). Putting all this together, you'd get a formula $\varphi(x)$ which carves out exactly the prime numbers. (Maybe you also want the formula "$x\not=0, 1$" in there, too.) Note that such infinitary formulas are defined externally.) $\endgroup$ – Noah Schweber Oct 28 '15 at 19:30

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.