5
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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}; +)$.

$\endgroup$
  • $\begingroup$ Does that mean we cannot decide if two finite sets $A$ and $B$ have same cardinality in Presburger? $\endgroup$ – T.... Jun 27 at 2:11
  • $\begingroup$ So somehow if we introduce multiplication we can compare cardinalities? $\endgroup$ – T.... Jun 27 at 2:11
  • $\begingroup$ @Turbo "Does that mean we cannot decide if two finite sets $A$ and $B$ have same cardinality in Presburger?" How would you even phrase the question in the context of addition alone? "So somehow if we introduce multiplication we can compare cardinalities?" Once we have multiplication, we can talk about numbers representing sets. We can (for example) view a number $n$ as coding the set $\{i: p_i\vert n\}$, where $p_i$ is the $i$th prime. (cont'd) $\endgroup$ – Noah Schweber Jun 27 at 2:19
  • $\begingroup$ So e.g. $12$ would code $\{1, 2\}$ since $p_1=2$ and $p_2=3$ are the only primes dividing $12$. Now it turns out that we can express "$a$ is in the set coded by $b$" just in terms of $+$ and $\times$, although this isn't obvious at all. And then we can indeed say "the set coded by $a$ has the same cardinality as the set coded by $b$," and many other things besides. This kind of coding is a key component of the proof of Godel's incompleteness theorem. $\endgroup$ – Noah Schweber Jun 27 at 2:22
  • $\begingroup$ @Turbo "What if I have many quantifiers?" I don't know what you mean by that. Again, how do you intend to even phrase the question in Presburger arithmetic? $\endgroup$ – Noah Schweber Jun 27 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy