5.10: Las definiciones por recursión son representables

Si observas la definición de un término (Definición 1.3.1), la definición de fórmula (Definición 1.3.3), la definición de\(u_t^x\) (Definición 1.8.1) y la definición de (Definición 1.8.2), notarás que todas estas definiciones eran definiciones “por recursión”. Por ejemplo, en la definición de un término, se ve la frase

\(\ldots t\)es\(f t_1 t_2 \ldots t_n\), donde\(f\) es una función\(n\) -aria símbolo de\(\mathcal{L}\) y cada uno de los\(t_i\) son términos de\(\mathcal{L}\)

por lo que un término puede tener partes constitutivas que son en sí mismas términos. En las dos últimas secciones hemos utilizado el dispositivo de secuencias de construcción para mostrar que los conjuntos\(TERM\),\(FORMULA\),\(TERMSUB\), y\(SUB\) son conjuntos representables. En esta sección esbozamos una prueba de que todos esos conjuntos de cadenas, definidos “por recursión”, dan lugar a conjuntos de números de Gödel que son representables. De nuestra exposición quedará claro que se podría probar una afirmación más general de nuestro teorema, pero lo que presentamos será suficiente para nuestras necesidades.

Definición 5.10.1.

Una cadena de símbolos\(s\) de un lenguaje de primer orden\(\mathcal{L}\) se llama expresión si\(s\) es un término de\(\mathcal{L}\) o una fórmula de\(\mathcal{L}\).

teorema 5.10.2.

Supongamos que tenemos un conjunto de\(\mathcal{L}_{NT}\) -expressions, que llamaremos\(\textit{Set}\), definido de la siguiente manera: Una expresión\(s\) es un elemento de\(\textit{Set}\) if y solo if:

1. \(s\)es un elemento de\(\textit{BaseCaseSet}\), o
2. Hay una expresión\(t\), una subcadena apropiada de\(s\), tal que\(\left( t, s \right)\) es un elemento de\(\textit{ConstructionSet}\).

Si los conjuntos de cadenas\(\textit{BaseCaseSet}\) y\(\text{ConstructionSet}\) dan lugar a conjuntos de números de Gödel\(BASECASESET\) y\(CONSTRUCTIONSET\) que están definidos por\(\Delta\) -fórmulas, entonces el conjunto

\[SET = \{ \ulcorner s \urcorner | s \in \textit{Set} \}\]

es representable, y tiene una\(\Delta\) -definición\(Set\).

Chaff:Trate de mantener los distintos tipos de letra rectos:

• \(\textit{Set}\)es un montón de\(\mathcal{L}_{NT}\) -expresiones - cadenas de símbolos de\(\mathcal{L}_{NT}\).
• \(SET\)es un conjunto de números naturales - los números Gödel de las cuerdas en\(\textit{Set}\).
• \(Set\)es una\(\mathcal{L}_{NT}\) -fórmula tal que\(\mathfrak{N} \models Set \left( \bar{a} \right)\) si y sólo si hay\(s \in Set\) tal que\(\ulcorner s \urcorner = a\).

Prueba

Seguimos muy de cerca la prueba de la representabilidad del conjunto\(TERM\), que se encuentra en la Sección 5.8. Al trabajar a través del Ejercicio 6 en la Sección 5.8, vio que podría probar los análogos de Lemmas 5.8.4 a 5.8.6 para fórmulas, por lo que ha establecido el siguiente lema:

lema 5.10.3.

Supongamos que\(s\) es una\(\mathcal{L}_{NT}\) expresión -y\(u\) es una subcadena de\(s\) que también es una expresión. Entonces

1. Si\(\ulcorner s \urcorner = a\), entonces el número de símbolos en\(s\) es menor o igual a\(a\).
2. La longitud de la secuencia de construcción más corta de\(s\) es menor o igual que el número de símbolos en\(s\).
3. \(\ulcorner u \urcorner < \ulcorner s \urcorner\).

prueba

Ahora podemos escribir una\(\Delta\) -definición de\(SETCONSTRUCTIONSEQUENCE\) y luego usar este lema para mostrar\(SET\) es representable:

\(SetConstructionSequence \left( c, a \right) =\)

\[CodeNumber \left( c \right) \land \\ \left( \exists l < c \right) \left[ Length \left( c, l \right) \land IthElement \left( a, l, c \right) \land \\ \left( \forall i \leq l \right) \left( \forall e < c \right) \left( IthElement \left( e, i, c \right) \rightarrow \\ BaseCaseSet \left( e \right) \lor \\ \left( \exists j < i \right) \left( \exists e_j < c \right) \\ \left( IthElement \left( e_j, j, c \right) \land ConstructionSet \left( e_j, e \right) \right) \right) \right].\]

Sabemos, por suposición, que hay\(\Delta\) -fórmulas\(BaseCaseSet\) y\(ConstructionSet\) que definen los conjuntos representables\(BASECASESET\) y\(CONSTRUCTIONSET\). Así, todos los cuantificadores en la definición anterior están acotados, y\(SetConstructionSequence\) es una\(\Delta\) fórmula.

Como antes podemos usar Lemmas 5.8.5 y 5.8.7 para encuadernar el tamaño de la secuencia de construcción más corta para\(a\): Por el mismo argumento que en la Sección 5.8, hay una secuencia de construcción codificada por un número\(c\) tal que\(c < \left( 2^{a^a} \right)^{a^2 + a}\). Así definimos

\(Set \left( a \right) =\)

\[\left( \exists c < \left( \bar{2}^{a^a} \right)^{a^\bar{2} + a} \right) SetConstructionSequence \left( c, a \right)\]

y tenemos una\(\Delta\) -definición del conjunto\(SET\), terminando nuestra prueba.

Este es un teorema maravilloso, ya que nos ahorra mucho trabajo. El mero hecho de señalar que sus definiciones se ajustan a los requisitos del Teorema 5.10.2, los siguientes conjuntos resultan ser representables y tienen\(\Delta\) -definiciones:

1. \(FREE\), donde\(\left( x, f \right) \in FREE\) si y sólo si\(x\) es el número Gödel de una variable que está libre en la fórmula con el número de Gödel\(f\).
2. \(SUBSTITUTABLE\), donde\(\left( t, x , f \right) \in SUBSTITUTABLE\) si y sólo si\(t\) es el número Gödel de un término que se puede sustituir por la variable con el número de Gödel\(x\) en la fórmula con el número de Gödel\(f\).

Ejercicios

1. Trabajar a través de los detalles (incluyendo la modificación necesaria del Teorema 5.10.2) y mostrar que ambos\(FREE\) y\(SUBSTITUTABLE\) son representables.
2. Supongamos que la función\(f : \mathbb{N}^{k+1} \rightarrow \mathbb{N}\) se define de la siguiente manera:
   \[\begin{align} f \left( \underset{\sim}{a}, 0 \right) &= g \left( \underset{\sim}{a} \right) \\ f \left( \underset{\sim}{a}, b + 1 \right) &= h \left( \underset{\sim}{a}, b f \left( \underset{\sim}{a}, b \right) \right), \end{align}\]
   donde\(g\) y\(h\) son funciones representables representadas por\(\Delta\) -formulas. Mostrar que\(f\) es una función representable. [Sugerencia: Un enfoque es definir la fórmula\(f ConstructionSequence \left( c, \underset{\sim}{a}, l \right)\), con la idea de que la secuencia codificada por\(c\) será\(\left( f \left( 0 \right), f \left( 1 \right), \ldots, f \left( l \right) \right)\). O bien, podrías intentar encajar esta situación en un teorema siguiendo las líneas del Teorema 5.10.2.]
3. Utilice el Ejercicio 2 para mostrar que las siguientes funciones son representables:
   (a) La función factorial\(n !\)
   (b) La función Fibonacci\(F\), donde\(F \left( 1 \right) = F \left( 2 \right) = 1\), y para\(k \geq 3\),\(F \left( k \right) = F \left( k - 1 \right) + F \left( k - 2 \right)\)
   (c) La función\(a \uparrow i\), donde\(a \uparrow 0 = 1\) y \(a \uparrow \left( j + 1 \right) = a^{a \uparrow j}\)(También debe calcular algunos valores, a lo largo de las líneas de\(2 \uparrow 3\)\(2 \uparrow 4\), y\(2 \uparrow 5\).)