¿Hay ecuaciones no triviales para hyperoperations encima de exponenciación?

Question

Una pregunta similar se le pidió a los comentarios de otros lugares.

Un papel de Roberto Di Cosmo y Thomas Dufour ("La Teoría Ecuacional de 〈ℕ, 0, 1, + , ×, ↑〉 Es Decidable, pero No Finitely Axiomatisable"), afirma en la nota 2 (p.3) que se ha demostrado "que no hay ninguna que no sea trivial ecuaciones para $⟨\mathbb{N}, \mathrm{Ack}(n, \_, \_)⟩$ si $n > 2.$" Referencias dejar claro que $\mathrm{Ack}(n,x,y)=H_{n+1}(x,y)$ en el hyperoperation secuencia, por lo que la afirmación es la siguiente:

$\text{There are no nontrivial equations for the binary function }(\_\uparrow^y\_)\text{ if }y>1\\ \text{ (i.e., for hyperoperations above exponentiation)}\tag{*}.$

(Para esto, el papel más arriba de la cites Charles F. Martin, "Axiomático bases para ecuacional teorías de los números naturales", Avisos de de la Am. De matemáticas. Soc., 19(7):778, 1972, que no he encontrado en línea.)

P. 1: Lo que, precisamente, se entiende por "no trivial de la ecuación" aquí?

(La definición de recursividad $$x\uparrow^{y+1}(z+1)=x\uparrow^y (x\uparrow^{y+1}z),$$ which certainly holds for $y>1$, evidentemente es considerado trivial.)

P. 2: Es la siguiente una prueba válida basada en la afirmación de $(*)$? ...

Reclamo:

Si $x,y,z$ son enteros $\gt 1$, entonces el valor de $\ x\uparrow^y z\ $ únicamente determina $x,y,z$; es decir, $$x\uparrow^y z = x'\uparrow^{y'} z' \quad\implies\quad x=x',\ y=y',\ z=z'.\quad \tag{1}$$

(El propósito de restringir el dominio de los enteros $>1$ es para quitar obvio contraejemplos que surgen de las ecuaciones como $x\uparrow (a\cdot z) = (x\uparrow a)\uparrow z\ \ $ o $\ \ 2\uparrow^y 2=4\uparrow^{y'} 1\ \ $ o $\ \ 1\uparrow^y z=1\uparrow^{y'} z'.$)

Prueba:

Supongamos, por el bien de la contradicción, que no es un contraejemplo a $(1)$, en la cual el lado izquierdo de la implicación que tiene, pero no la RHS. A continuación, el lado izquierdo es un trivial de la ecuación para algunos hyperoperation(s) más allá de la exponenciación, lo cual es imposible, como por $(*)$. QED

Answer 1

Para entender el vinculado pregunta y su respuesta, es importante darse cuenta de que la palabra "ecuación" tiene un significado preciso en este contexto.

Resumen rápido de lo que sigue: la definición de recursividad de la función de Ackermann es trivial, pero no es una ecuación en el idioma correcto; y el argumento de la pregunta 2 es incorrecta, ya que las ecuaciones implican la cuantificación sobre todos los elementos de la estructura.

En primer lugar, debemos definir los términos. Un término en un lenguaje funcional (que es sólo una colección de símbolos de función, nada demasiado complicado; la palabra "funcional" se incluye, ya que a menudo considerar otros tipos de idiomas) es una expresión construida a partir de los símbolos de función en ese idioma, variables, y entre paréntesis; una ecuación es entonces una frase de la forma $$\forall x_1,...,x_n(s(x_1, ..., x_n)=t(x_1, ..., x_n)),$$ where $s, t$ are terms in the variables $x_1, ..., x_n$. Por ejemplo, el lenguaje de los grupos contiene una función binaria símbolo (el grupo de operación), un único símbolo de función (la operación inversa), y un nullary símbolo de función (el elemento de identidad).

Por el contrario, la definición de recursividad de la función de Ackermann no es una ecuación en la lengua de que se trate: que el lenguaje se compone sólo de los binarios de la función del símbolo "$\uparrow^n$", y la definición de recursividad consiste en el símbolo"$+$". De modo que la definición de "ecuación" es bastante estricto. Tenga en cuenta que este surge en un par de lugares en los enlaces de la pregunta, donde varias propiedades de la exponenciación, son propuestas que no son, de hecho, las ecuaciones en el lenguaje de la exponenciación solo.

Una estructura en un determinado lenguaje funcional es un conjunto, junto con algunas de las funciones correspondientes a los símbolos de función (con la correcta arities). Por ejemplo, si nuestro idioma $\Sigma$ se compone de dos unario símbolos de función $@$$\%$, a continuación, un ejemplo de una $\Sigma$-estructura es $(\mathbb{Z}; @(x)=x+1, \%(x)=x-1)$. Se debe tener claro lo que significa para una ecuación para sostener en una estructura - por ejemplo, en la anterior estructura de la ecuación de $$\forall x(@(\%(x))=\%(@(x))).$$ sostiene.

Una ecuación es trivial si es cierto, no importa cómo la función de los símbolos son interpretados. Es decir, dado un lenguaje funcional $\Sigma$, una ecuación de $E$ en el idioma $\Sigma$ es trivial si es cierto en todos los $\Sigma$-estructura. Por ejemplo, la ecuación en el párrafo anterior no es trivial: considerar el $\Sigma$-estructura en la que tanto $@(x)$ $\%(x)$ son interpretados como "$x+1$."

No es difícil convencerse de que realmente no hay muchos de estos, de hecho, una ecuación es trivial iff los dos términos son exactamente lo mismo! Lo que justifica aún más el nombre.

Esto responde a su primera pregunta. Hacia el segundo, se nota el cuantificador universal en la definición de una ecuación: el simple hecho de tener una instancia de una cosa igual a otra no constituyen una ecuación, la ecuación especifica que los dos términos son siempre iguales. Así que la respuesta a la segunda pregunta es no.

---

Por cierto, la más relevante del tema aquí es álgebra universal.