# Questions tagged [presburger-arithmetic]

Presburger arithmetic is the first-order theory of the natural numbers with addition.

37 questions
Filter by
Sorted by
Tagged with
33 views

### Are functions $f: \{1,\ldots,m\} \times \{1,\ldots,n\} \to \{1,\ldots,n\}$ definable in Presburger arithmetic?

Given a function $f: \{1,\ldots,m\} \times \{1,\ldots,n\} \to \{1,\ldots,n\}$ where $m,n$ are strictly positive natural numbers. Is there a Presburger arithmetic formula that represents it?
• 5,965
75 views

• 61
1 vote
63 views

### Axioms of Linear Integer Arithmetic?

The slides I am reading don't give the axioms of LIA (linear integer arithmetic) instead only give it's signature. I looked on the internet and can't find the axioms of LIA. For the following ...
• 2,479
166 views

### Presburger arithmetic is consistent, but relative to what?

In the Wikipedia article for (the first-order theory of) Presburger arithmetic, it is stated (among other properties) that Presburger arithmetic is consistent. What meta-theory does he rely on in ...
1 vote
156 views

### Is it possible to use order relation in Presburger arithmetic?

The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. Is it possible to state and prove theorems in Presburger ...
• 435
131 views

### Is Presburger arithmetic in "Ramsey logic" complete?

Let $\Sigma=\{+,<,0,1\}$ be the usual language of Presburger arithmetic - so we have addition but no multiplication (the additional symbols for $<,0,1$ are unnecessary but convenient). Given a &...
• 250k
1 vote
137 views

### What is the interpretation of Presburger Arithmetic in WS1S?

It’s my understanding that Julius Büchi showed that $WS1S$, the weak monadic second-order theory of one successor is decidable by a finite-state automaton, and that this implies that Presburger ...
• 10.4k
305 views

### Is it not possible to state the Collatz Conjecture in a decidable theory?

I believe that the answer is no (evidenced by the 80+ year "open" status of the conjecture), but I am self-taught in formal logic and decidability theory, so I would like to present my ...
• 7,297
1 vote
251 views

### Presburger arithmetic vs Linear Integer Arithmetic

I always work with these two and use it with no distinction, but I am probably wrong. I mean, are their signatures the same? And their axioms? I know that, for instance, the quantifier elimination ...
• 247
1 vote
199 views

### Question concerning Presburger arithmetic

Context: Presburger arithmetic is the theory $\tau$ of structure $$A = (\mathbb{N},0,1,+,\{c|\cdot\}_{c\in\mathbb{N}})$$ where for each integer $c > 1$, the unary predicate c|n holds if and only ...
• 47
151 views

1 vote
241 views

### Do induction axioms of Peano Arithmetic have other simple equivalent forms?

For the example of Presburger Arithmetic, which consists of basic axioms for successor, addition, as well as an infinite set of induction axioms. However, it is well known that Presburger Arithmetic ...
112 views

### Systems of arithmetic models [closed]

Presburger Arithmetic is decidable theory but weaker than Peano Arithmetic. Are there systems in some sense that are: stronger than Presburger but weaker than Peano and remain decidable? weaker than ...
• 6,251
1 vote
69 views

### Strongest decidable system of arithmetics

I have taken no formal mathematics logic course yet, I'm sorry for unclear parts of this question. I've learned about Presburger Arithmetics few days ago, it seemed really interesting. But since then,...
• 332
819 views

### Showing that Presburger arithmetic is decidable by deciding if $\mathbb N \models \varphi$, but does it give provability in the axioms?

Here Presburger arithemtic is given by a set of axioms over the signature with binary operation $+$ and two constants $0$ and $1$. Similarly in Presburgers original paper he gives the arithmetic in ...
• 18.2k
366 views

• 9,337