Pairing in Presburger arithmetic Is it possible to define pairing function (and the inverses) in Presburger arithmetic?
I would guess no but I can't locate a reference nor construct a proof to one way or another.
 A: The answer is no.
Small comment: I show below that no pairing function is definable in the structure $(\mathbb{N}; +)$. This is strictly stronger than saying that no pairing function can be defined in Presburger arithmetic, which is saying that there is no definition which Presburger arithmetic proves is a pairing function.
Remember that in $(\mathbb{N}; +)$, every definable set is eventually periodic. So building a "sufficiently sparse" set from a pairing function will be sufficient to show that such a function can't be definable in this structure.
So suppose $\langle \cdot,\cdot\rangle:\mathbb{N}^2\rightarrow\mathbb{N}$ were a bijection definable in $(\mathbb{N}; +)$. First, note that the usual ordering $<$ on $\mathbb{N}$ is definable in $(\mathbb{N}; +)$: $$a<b\iff [\exists c(a+c=b)\wedge \forall c(b+c\not=a)].$$ (This assumes $0\in\mathbb{N}$; if not, we can do away with the second conjunct.) Similarly, the minimum function is definable, in the sense that if $\varphi(x, y)$ is any formula of two variables, the function $x\mapsto \min\{y: \varphi(x, y)\}$ is a definable (possibly partial) function in $(\mathbb{N}; +)$.
Now consider the function $$f(x)=\min\{y: \forall a, b<x(\langle a, b\rangle<y)\},$$ and let $$X=ran(f).$$ Clearly $X$ is definable by the considerations above and the fact that the range of a definable function is a definable set; however, it's easy to see that $f$ grows at least as fast as $x^2,$ and so $X$ is too sparse to be definable in $(\mathbb{N}; +)$.
