Maridaje en la aritmética de Presburger

Question

¿Es posible definir la función de emparejamiento (y los inversos) en la aritmética de Presburger?

Supongo que no pero yo no puedo localizar una referencia ni construir una prueba de una manera u otra.

Answer 1

La respuesta es no.

Pequeño comentario: os muestro a continuación que no hay función de sincronización es definible en la estructura de la $(\mathbb{N}; +)$. Esto es estrictamente más fuerte que decir que no hay vinculación de la función se puede definir en la aritmética de Presburger, que está diciendo que no hay ninguna definición que la aritmética de Presburger demuestra es una función de sincronización.

Recuerde que en $(\mathbb{N}; +)$, cada definibles por el conjunto es el tiempo de periódico. Así que la construcción de un "suficientemente disperso" de una función de sincronización será suficiente para demostrar que una función no puede ser definible en esta estructura.

Así que supongamos $\langle \cdot,\cdot\rangle:\mathbb{N}^2\rightarrow\mathbb{N}$ fueron un bijection definible en $(\mathbb{N}; +)$. En primer lugar, tenga en cuenta que la costumbre de ordenar $<$ $\mathbb{N}$ es definible en $(\mathbb{N}; +)$: $$a<b\iff [\exists c(a+c=b)\wedge \forall c(b+c\not=a)].$$ (This assumes $0\en\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}; +)$.

Ahora considere la función $$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}; +)$.