5 votos

Maridaje en la aritmética de Presburger

¿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.

7voto

ManuelSchneid3r Puntos 116

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: