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

Question

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?

Answer 1

Note that your title and body differ - are you asking about reperesentability or definability? The latter is a much weaker criterion in general, although in this case the answer is the same. Below I'll assume you meant to ask about representability.

---

Sure - each specific natural number $k$ has a corresponding "Presburger numeral" $\underline{k}$ (e.g. $\underline{3}$ is the term $1+1+1$, or $+(+(1,1),1)$ if you want to be very precise) so you can just brute-force it: $$\varphi_f(x,y,z)\equiv\bigwedge_{1\le i\le m, 1\le j\le n}[x=\underline{i}\wedge y=\underline{j}\rightarrow z=\underline{f(x,y)}].$$ Of course this doesn't help represent functions with infinite domain at all.

Note that I'm tacitly assuming that we have symbols for $0$ and $1$ in our language. Otherwise, we don't quite have Presburger numerals as such. However, we're still fine since $0$ and $1$ can be defined from addition alone, the corresponding $\varphi$s are just a bit messier. In fact, all we really need is the definability of the successor operation: every finite function on naturals is representable in the theory of the structure $(\mathbb{N};\mathsf{succ})$, which is already much weaker than Presburger arithmetic.