5.3: Conjuntos y funciones representables

Por el bien de la discusión, supongamos que dejamos\(f \left( x \right) = x^2\). No te sorprenderá enterarte de eso\(f \left( 4 \right) = 16\), así que nos gustaría escribir\(\mathfrak{N} \models f \left( 4 \right) = 16\). Desafortunadamente, no se nos permite hacer esto, ya que el símbolo\(f\), por no mencionar\(4\) y\(16\), no son parte del lenguaje.

Lo que podemos hacer, sin embargo, es representar la función\(f\) por una fórmula en\(\mathcal{L}_{NT}\). Para ser específicos, supongamos que\(\phi \left( x, y \right)\) es

\[y = ExSS0.\]

Entonces, si nos permitimos una vez más usar la abreviatura\(\bar{a}\) para el\(\mathcal{L}_{NT}\) -term\(SSS \cdots S0 \left( aS \text{'s} \right)\), podemos afirmar que

\[\mathfrak{N} \models \phi \left( \bar{4}, \overline{16} \right)\]

que es lo mismo que

\[\mathfrak{N} \models = SSSSSSSSSSSSSSSS0ESSSS0SS0.\]

(¿No te alegra que no utilicemos muy a menudo el idioma oficial?) De todas formas, la situación es incluso mejor que esto, pues\(\phi \left( \bar{4}, \overline{16} \right)\) es derivable de\(N\) más que solo verdad en\(\mathfrak{N}\). De hecho, si miras hacia atrás en Lemma 2.8.4, probablemente no tendrás ningún problema para creer las siguientes afirmaciones:

• \(N \vdash \phi \left( \bar{4}, \overline{16} \right)\)
• \(N \vdash \neg \phi \left( \bar{4}, \overline{17} \right)\)
• \(N \vdash \neg \phi \left( \bar{1}, \overline{714} \right)\)

De hecho, esta fórmula\(\phi\) es tal, y\(N\) es tal, que si\(a\) es algún número natural y\(b = f \left( a \right)\), entonces

\[N \vdash \forall y \left[ \phi \left( \bar{a}, y \right) \leftrightarrow y = \bar{b} \right].\]

Diremos que la fórmula\(\phi\) representa la función\(f\) en la teoría\(N\).

Definición 5.3.1.

Se dice que un conjunto\(A \subseteq \mathbb{N}^k\) es representable (in\(N\)) si hay una\(\mathcal{L}_{NT}\) fórmula\(\phi \left( \underset{\sim}{x} \right)\) -tal que

\[\begin{array}{ll} \forall \underset{\sim}{a} \in A & N \vdash \phi \left( \bar{\underset{\sim}{a}} \right) \\ \forall \underset{\sim}{b} \not\in A & N \vdash \neg \phi \left( \bar{\underset{\sim}{b}} \right). \end{array}\]

En este caso diremos que la fórmula\(\phi\) representa el conjunto\(A\).

Definición 5.3.2.

Se dice que un conjunto\(A \subseteq \mathbb{N}^k\) es débilmente representable (in\(N\)) si hay una\(\mathcal{L}_{NT}\) fórmula\(\phi \left( \underset{\sim}{x} \right)\) tal que

\[\begin{array}{ll} \forall \underset{\sim}{a} \in A & N \vdash \phi \left( \bar{\underset{\sim}{a}} \right) \\ \forall \underset{\sim}{b} \not\in A & N \nvdash \phi \left( \bar{\underset{\sim}{b}} \right). \end{array}\]

En este caso diremos que la fórmula representa\(\phi\) débilmente el conjunto\(A\).

Observe que si\(A\) es representable, entonces\(A\) es débilmente representable. En algunas ocasiones hablaremos de un conjunto siendo representable en\(T\), donde\(T\) está un conjunto diferente de\(\mathcal{L}_{NT}\) -fórmulas. Esto solo significa que todas las deducciones mencionadas en las dos definiciones anteriores deben ser deducciones -de-\(T\), en lugar de deducciones- de-\(N\).

Chaff: Aquí se ha deslizado un poco de notación. En lugar de escribir una y\(x_1, x_2, \ldots, x_k\) otra y otra vez en las próximas secciones, abreviaremos esto como\(\underset{\sim}{x}\). Del mismo modo,\(\bar{\underset{\sim}{x}}\) es la taquigrafía de\(\overline{x_1}, \overline{x_2}, \ldots, \overline{x_k}\). Si quieres, solo puedes asumir que solo hay uno\(x\), no hará ninguna diferencia en la exposición.

También discutiremos funciones representables, y esto trae a colación un par de puntos sutiles que deben abordarse. La idea general es que una función\(f : \mathbb{N}^k \rightarrow \mathbb{N}\) debe ser representable si\(N\) es capaz de demostrar que una fórmula que representa la función hace lo correcto, pero históricamente el término débilmente representable se ha aplicado a funciones cuyos dominios son (posiblemente estrictos) subconjuntos de\(\mathbb{N}^k\), lo que agrega cierta complejidad.

Para empezar, tendremos que poder hablar de los dominios de las funciones con un poco más de precisión.

Definición 5.3.3.

Supongamos eso\(A \subseteq \mathbb{N}^k\) y supongamos que\(f : A \rightarrow \mathbb{N}\). Si\(A = \mathbb{N}^k\) vamos a decir que\(f\) es una función total. Si\(A \subsetneq \mathbb{N}^k\), llamaremos a\(f\) una función parcial.

Ahora podemos definir lo que significa que una función sea representable o débilmente representable.

Definición 5.3.4.

Supongamos que\(f : \mathbb{N}^k \rightarrow \mathbb{N}\) es una función total. Vamos a decir que\(f\) es una función representable (in\(N\)) si existe una\(\mathcal{L}_{NT}\) -fórmula\(\phi \left( x_1, \ldots, x_{k+1} \right)\) tal que, para todos\(a_1, a_2, \ldots, a_{k+1} \in \mathbb{N}\),

\[\text{If} \: f \left( a_1, \ldots, a_k \right) = a_{k+1}, \: \text{then} \: N \vdash \phi \left( \overline{a_1}, \ldots, \overline{a_{k+1}} \right) \\ \text{If} \: f \left( a_1, \ldots, a_k \right) \neq a_{k+1}, \: \text{then} \: N \vdash \neg \phi \left( \overline{a_1}, \ldots, \overline{a_{k+t}} \right).\]

Observe que una función total es una función representable si y solo si es un subconjunto representable de\(\mathbb{N}^{k+1}\). Ver Ejercicio 4.

Definición 5.3.5.

Supongamos que\(A \subseteq \mathbb{N}^k\) y\(f : A \rightarrow \mathbb{N}\) es una (posiblemente) función parcial. Vamos a decir que\(f\) es una función débilmente representable (in\(N\)) si existe una\(\mathcal{L}_{NT}\) -fórmula\(\phi \left( x_1, \ldots, x_{k+1} \right)\) tal que, para todos\(a_1, a_2, \ldots, a_{k+1} \in \mathbb{N}\),

\[\text{If} \: f \left( a_1, \ldots, a_k \right) = a_{k+1}, \: \text{then} \: N \vdash \phi \left( \overline{a_1}, \ldots, \overline{a_{k+1}} \right) \\ \text{If} f \left( a_1, \ldots, a_k \right) \neq a_{k+1}, \: \text{then} \: N \nvdash \phi \left( \overline{a_1}, \ldots, \overline{a_{k+1}} \right).\]

Chaff: En la definición anterior, observe que si, por ejemplo, 5 no es un elemento del dominio de la función unaria\(f\), entonces no\(f \left( 5 \right)\) va a ser igual a nada, entonces eso lo sabemos\(f \left( 5 \right) \neq 17\). Todo lo que pedimos, en ese caso, es que\(N\) no prueba\(\phi \left( \bar{5}, \overline{17} \right)\). No necesitamos, y no podemos esperar,\(N\) probar\(\neg \phi \left( \bar{5}, \overline{17} \right)\).

¿Qué importancia tiene saber si una función es total o no? En cuanto a la representabilidad, el gran resultado es el siguiente, cuya prueba se omite.

proposición 5.3.6.

Supongamos que\(f\) es una función total de\(\mathbb{N}^k\) a\(\mathbb{N}\). Entonces\(f\) es representable si y sólo si\(f\) es débilmente representable.

Las funciones parciales serán muy importantes para nosotros a medida que trabajemos a través del Capítulo 7, pero para el próximo par de capítulos, casi todas nuestras funciones serán totales. Si\(f\) es representable, podemos decir un poco más sobre lo que\(N\) puede probar sobre\(f\).

proposición 5.3.7.

Supongamos que\(f : \mathbb{N}^k \rightarrow \mathbb{N}\) es una función total. Entonces los siguientes son equivalentes.

1. \(f\)es una función representable.
2. Existe una\(\mathcal{L}_{NT}\) -fórmula\(\psi \left( x_1, \ldots, x_{k+1} \right)\) tal que para todos\(\underset{\sim}{a} \in \mathbb{N}^k\),
   \[N \vdash \left( \forall y \right) \left[ \psi \left( \bar{\underset{\sim}{a}}, y \right) \leftrightarrow y = \overline{f \left( \underset{\sim}{a} \right)} \right].\]

prueba

El ejercicio 9 proporciona un esquema de una prueba.

Chafia:

¿Qué hay en un nombre? aquello que llamamos rosa
Por cualquier otro nombre olería
tan dulce; entonces Romeo lo haría, si no llamara Romeo,
conservaría esa querida perfección que debe
Sin ese título.
- Romeo y Julieta, Acto II, Escena II

En los cursos de informática, en muchos textos de lógica matemática, y de hecho en el capítulo 7 de este libro, se adopta un enfoque diferente cuando se introducen conjuntos y funciones representables. A partir de ciertas funciones iniciales, la idea de recursión y un objeto llamado\(\mu\) -operator, se define una colección de funciones parciales de tal manera que cada función de la colección es efectivamente calculable. Esto se llama la colección de funciones computables, lo que lleva a algo llamado conjuntos decidibles (o computables). Entonces estos textos prueban que la colección de conjuntos representables que acabamos de definir es la misma que la colección de conjuntos decidibles. Así todos terminamos en el mismo lugar, con una colección bien definida de conjuntos y funciones, que llamamos computable. O representables. O recursivo. Entonces, si te confunden las diferentes definiciones, solo recuerda que todas definen el mismo concepto, y recuerda que los objetos que son recursivos (o representables o computables) son (en cierto sentido) los simples, aquellos en los que se puede probar la pertenencia\(N\).

Para ser justos, no es tan sencillo como Julieta lo hace parecer. (Nunca lo es, ¿verdad?) El camino que hemos tomado hacia conjuntos representables es limpio y directo pero enfatiza las deducciones sobre las funciones. El enfoque a través de funciones iniciales enfatiza el hecho de que todo lo que discutimos se puede calcular, y ese punto de vista da un vínculo natural entre la lógica que hemos estado discutiendo y sus aplicaciones a la informática. Para más información sobre esta conexión, véanse la Sección 5.4 y el Capítulo 7.

Definición 5.3.8.

Diremos que un conjunto\(A \subseteq \mathbb{N}^k\) es definible si hay una fórmula\(\phi \left( \underset{\sim}{x} \right)\) tal que

\[\begin{array}{ll} \forall \underset{\sim}{a} \in A & \mathfrak{N} \models \phi \left( \bar{\underset{\sim}{a}} \right) \\ \forall \underset{\sim}{b} \notin A & \mathfrak{N} \models \neg \phi \left( \bar{\underset{\sim}{b}} \right). \end{array}\]

En este caso, diremos que\(\phi\) define el conjunto\(A\).

Chaff: Es muy importante notar la diferencia entre decir que\(\phi\) representa\(A\) y\(\phi\) define\(A\), que es lo mismo que la diferencia entre\(N \vdash\) y\(\mathfrak{N} \models\). Observe que cualquier conjunto representable debe ser definible y está definido por cualquier fórmula que lo represente. Lo contrario, sin embargo, no es automático. De hecho, lo contrario no es cierto. Pero nos estamos adelantando a nosotros mismos.

Hemos mencionado varias veces que el sistema de axiomas\(N\) es relativamente débil. Mostraremos en esta sección que\(N\) es lo suficientemente fuerte como para probar algunas de las\(\mathcal{L}_{NT}\) fórmulas en las que son ciertas\(\mathfrak{N}\), es decir, la clase\(\Sigma\) de frases verdaderas. Y esto nos permitirá demostrar que si un conjunto\(A\) tiene una definición relativamente simple, entonces el conjunto\(A\) será representable.

Recordemos del Capítulo 4 que una fórmula es una\(\Delta\) fórmula -si contiene solo cuantificadores acotados. Un poco más complicadas son las\(\Sigma\) fórmulas -que pueden contener cuantificadores acotados y cuantificadores existenciales no acotados, y\(\Pi\) -formulas, que pueden usar tanto cuantificadores acotados como cuantificadores universales no acotados.

Ejemplo 5.3.9:

Aquí hay un ejemplo perfectamente agradable\(\Delta\) de una fórmula\(\phi\):\(\left( \forall x < t \right) \left( x = 0 \right)\). Observe que la negación de no\(\phi\) es una\(\Delta\) fórmula, como no lo\(\neg \left( \forall x < t \right) \left( x = 0 \right)\) es ni a\(\Sigma\) - ni a\(\Pi\) -fórmula. Pero una cadena de equivalencias lógicas nos muestra que\(\neg \phi\) es equivalente a una\(\Delta\) fórmula -si simplemente empujamos el signo de negación dentro del cuantificador:

\[\neg \phi \\ \neg \left( \forall x < t \right) \left( x = 0 \right) \\ \left( \exists x < t \right) \neg \left( x = 0 \right).\]

Del mismo modo, podemos demostrar que cualquier combinación proposicional (usando\(\land\)\(\lor\)\(\neg\),\(\rightarrow\),,,\(\leftrightarrow\))\(\Delta\) de fórmulas es equivalente a una\(\Delta\) fórmula. Utilizaremos este hecho aproximadamente 215,342 veces en el resto de este libro.

Una\(\Sigma\) oración es, por supuesto, una\(\Sigma\) fórmula que también es una oración. Nos interesará particularmente\(\Sigma\) -fórmulas y\(\Delta\) -fórmulas, pues vamos a mostrar si\(\phi\) es una\(\Sigma\) -oración y\(\mathfrak{N} \models \phi\), entonces el conjunto de axiomas\(N\) es lo suficientemente fuerte como para proporcionar una deducción de\(\phi\). Dado que cada\(\Delta\) -oración es también una\(\Sigma\) -oración, cualquier\(\Delta\) -oración que sea verdadera en también\(\mathfrak{N}\) es demostrable a partir de\(N\).

El primer lema que proporcionaremos muestra que\(N\) es lo suficientemente fuerte como para demostrarlo\(1 + 1 = 2\). En realidad, ya lo sabemos ya que se comprobó de nuevo en Lemma 2.8.4. Ahora ampliamos ese resultado y demostramos que si\(t\) es algún término libre de variables, entonces\(N\) demuestra que\(t\) es igual a lo que se supone que es igual a lo que se supone que es igual.

Recordemos que si\(t\) es un término, entonces\(t^\mathfrak{N}\) está la interpretación de ese término en la estructura\(\mathfrak{N}\). Por ejemplo, supongamos que ese\(t\) es el término\(ESSS0SS0\), también conocido como\(SSS0^{SS0}\). Entonces\(t^\mathfrak{N}\) sería el número 9, y\(\overline{t^\mathfrak{N}}\) sería el término\(SSSSSSSSS0\). Entonces cuando este lema dice que eso\(N\) prueba\(t = \overline{t^\mathfrak{N}}\), deberías pensar que eso\(N\) prueba\(SSS0^{SS0} = SSSSSSSSS0\), que es lo mismo que decir eso\(N \vdash \bar{3}^\bar{2} = \bar{9}\).

lema 5.3.10.

Por cada término libre de variables\(t\),\(N \vdash t = \overline{t^\mathfrak{N}}\).

prueba

Se procede por inducción sobre la complejidad del término\(t\). Si\(t\) es el término 0, entonces\(t^\mathfrak{N}\) es el número natural 0, y\(\overline{t^\mathfrak{N}}\) es el término 0. Así tenemos que probarlo\(N \vdash 0 = 0\), que es una consecuencia inmediata de nuestros axiomas lógicos.

Si\(t\) es\(S \left( u \right)\), donde\(u\) es un término libre de variables, entonces el término\(\overline{t^\mathfrak{N}}\) es idénticala al término\(S \left( \overline{u^\mathfrak{N}} \right)\). También,\(N \vdash u = \overline{u^\mathfrak{N}}\), por la hipótesis inductiva, y así\(N \vdash Su = S \left( \overline{u^\mathfrak{N}} \right)\), gracias al axioma de igualdad (E2). Armando todo esto, lo conseguimos\(N \vdash t = Su = S \left( \overline{u^\mathfrak{N}} \right) = \overline{t^\mathfrak{N}}\), según sea necesario.

Si\(t\) es\(u + v\) así, recordamos que Lemma 2.8.4 lo demostró\(N \vdash \overline{u^\mathfrak{N}} + \overline{v^\mathfrak{N}} = \overline{u^\mathfrak{N} + v^\mathfrak{N}}\). Pero entonces\(N \vdash t = u + v = \overline{u^\mathfrak{N}} + \overline{v^\mathfrak{N}} = \overline{u^\mathfrak{N} + v^\mathfrak{N}} = \overline{t^\mathfrak{N}}\), que es lo que necesitábamos mostrar. Los argumentos a favor de términos de la forma\(u \cdot v\) o\(u^v\) son similares, por lo que la prueba es completa.

El siguiente lema y su corolario serán utilizados en nuestra prueba de que las\(\Sigma\) frases verdaderas son demostrables a partir de\(N\).

lema 5.3.11: Lema de Rosser

Si\(a\) es un número natural,

\[N \vdash \left( \forall x < \bar{a} \right) \left[ x = \bar{0} \lor x = \bar{1} \lor \cdots \lor x = \overline{a - 1} \right].\]

prueba

Utilizamos inducción en\(a\). Si\(a = 0\), basta con probarlo\(N \vdash \forall x \left[ x < 0 \rightarrow \perp \right]\). Por Axioma 9 de\(N\), lo sabemos\(N \vdash \neg \left( x < 0 \right)\), entonces\(N \vdash \left( x < 0 \right) \rightarrow \perp\), según sea necesario.

Para el paso inductivo, supongamos que\(a = b + 1\). Debemos demostrar que

\[N \vdash \forall x \left[ x < \overline{b + 1} \rightarrow x = \bar{0} \lor \cdots \lor x = \bar{b} \right].\]

Dado que\(\overline{b + 1}\) y\(S \bar{b}\) son idénticos, basta con demostrar que

\[N \vdash \forall x \left[ x < \overline{Sb} \rightarrow x = \bar{0} \lor \cdots \lor x = \bar{b} \right].\]

Por Axioma 10, sabemos que\(N \vdash x < S \bar{b} \rightarrow \left( x < \bar{b} \lor x = \bar{b} \right)\), y luego por la hipótesis inductiva, estamos terminados.

corolario 5.3.12.

Si\(a\) es un número natural, entonces

\[N \vdash \left[ \left[ \left( \forall x < \bar{a} \right) \phi \left( x \right) \right] \leftrightarrow \left[ \phi \left( \bar{0} \right) \land \phi \left( \bar{1} \right) \land \cdots \land \phi \left( \overline{a -1} \right) \right] \right].\]

prueba

Ejercicio 11.

Ahora llegamos al resultado mayor de esta sección, que nuestro sistema de axiomas es lo suficientemente fuerte como para probar todas las\(\Sigma\) frases verdaderas.

proposición 5.3.13.

Si\(\phi \left( \underset{\sim}{x} \right)\) es una\(\Sigma\) fórmula -con variables libres\(\underset{\sim}{x}\), si\(\underset{\sim}{t}\) son términos libres de variables, y si\(\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)\), entonces\(N \vdash \phi \left( \underset{\sim}{t} \right)\).

prueba

Esto es una prueba por inducción sobre la complejidad de la fórmula\(\phi\).

1. Si\(\phi\) es atómico, digamos por ejemplo que\(\phi\) es\(x < y\) y términos\(t\) y\(u\) son tales que\(\mathfrak{N} \models t < u\). Entonces\(t^\mathfrak{N} < u^\mathfrak{N}\), así por Lemma 2.8.4,\(N \vdash \overline{t^\mathfrak{N}} < \overline{u^\mathfrak{N}}\). Pero también sabemos\(N \vdash t = \overline{t^\mathfrak{N}}\) y\(N \vdash u = \overline{u^\mathfrak{N}}\), por Lema 5.3.10, así\(N \vdash t < u\), según sea necesario.
2. Las negaciones de las fórmulas atómicas se manejan de la misma manera.
3. Si\(\phi\) es\(\alpha \lor \beta\) o\(\alpha \land \beta\), el argumento se deja en manos de los Ejercicios.
4. Supongamos que\(\mathfrak{N} \models \exists x \psi \left( x \right)\), donde asumimos que\(\psi\) tiene sólo una variable libre por simplicidad. Entonces hay un número natural\(a\) tal que\(\mathfrak{N} \models \psi \left( \bar{a} \right)\), y así\(N \vdash \psi \left( \bar{a} \right)\) por la hipótesis inductiva. Pero entonces nuestro segundo axioma cuantificador nos dice, como\(\bar{a}\) es sustituible\(x\) en\(\psi\), eso\(N \vdash \exists x \psi\), según sea necesario.
5. Ahora si\(\mathfrak{N} \models \left( \forall x < u \right) \psi \left( x \right)\), sabemos por la hipótesis inductiva que
   \[N \vdash \left[ \psi \left( \bar{0} \right) \land \psi \left( \bar{1} \right) \land \cdots \land \psi \left( \overline{u^\mathfrak{N} - 1} \right) \right].\]
   Pero entonces por Corolario 5.3.12,
   \[N \vdash \left( \forall x < \overline{u^\mathfrak{N}} \right) \psi \left( x \right).\]
   Así, ya que\(N \vdash \overline{u^\mathfrak{N}} = u\),\(N \vdash \left( \forall x < u \right) \psi \left( x \right)\), según sea necesario.

Así si\(\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)\), entonces\(N \vdash \phi \left( \underset{\sim}{t} \right)\).

Vamos a decir que\(\phi\) es demostrable (de\(N\)) si\(N \vdash \phi\). Y diremos que\(\phi\) es refutable si\(N \vdash \neg \phi\).

Supongamos que\(\phi\) es una\(\Delta\) -oración. Si\(\mathfrak{N} \models \phi\), como sabemos que también\(\phi\) es una\(\Sigma\) sentencia, la Proposición 5.3.13 lo demuestra\(N \vdash \phi\). Pero supongamos que eso\(\phi\) es falso; es decir, supongamos eso\(\mathfrak{N} \not\models \phi\). Entonces\(\mathfrak{N} \models \neg \phi\), y\(\neg \phi\) es equivalente a una\(\Delta\) -oración. Así, por el mismo argumento que el anterior,\(N \vdash \neg \phi\). Por lo que hemos demostrado lo siguiente:

Proposición 5.3.14.

Si\(\phi \left( \underset{\sim}{x} \right)\) es una\(\Delta\) fórmula -con variables libres\(\underset{\sim}{x}\), si\(\underset{\sim}{t}\) son términos libres de variables, y si\(\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)\), entonces\(N \vdash \phi \left( \underset{\sim}{t} \right)\). Si, por otro lado,\(\mathfrak{N} \models \neg \phi \left( \underset{\sim}{t} \right)\), entonces\(N \vdash \neg \phi \left( \underset{\sim}{t} \right)\).

corolario 5.3.15.

Supongamos que\(A \subseteq \mathbb{N}^k\) se define por una\(\Delta\) -fórmula\(\phi \left( \underset{\sim}{x} \right)\). Entonces\(A\) es representable.

prueba

Esto es inmediato de la Proposición 5.3.14 y la Definición 5.3.1.

El lector astuto y cuidadoso habrá notado que el Corolario 5.3.15 es una implicación y no un bicondicional. Por lo que el corolario nos proporciona una manera útil y conveniente de garantizar que un conjunto en particular sea representable, y aprovecharemos esa garantía frecuentemente. La versión asiento de los pantalones del corolario es que un conjunto con una definición muy simple es representable. Aunque no podremos probarlo hasta más tarde (Lema 6.3.3) hay un resultado que es un guiño en la dirección de un converse:

proposición 5.3.16.

Supongamos que eso\(A \subseteq \mathbb{N}^k\) es representable. Después hay una\(\Sigma\) -fórmula que define\(A\).

Leyendo con atención, ciertamente estás pensando que debe haber algunos conjuntos representables que, aunque son\(\Sigma\) -definibles, no tienen una\(\Delta\) -definición (si no la hubiera, ciertamente habríamos probado ese hecho en el Corolario anterior, ¿verdad?). Tienes razón, y volveremos a esta pregunta en la siguiente sección. Por ahora, estaremos contentos con cierta práctica en la definición de algunos conjuntos con\(\Delta\) -fórmulas, y así establecer que esos conjuntos son representables. Hacer esto nos mantendrá ocupados durante gran parte del resto de este capítulo.

Ejemplo 5.3.17:

Supongamos que miramos los números pares. Es posible que desee definir este conjunto por la\(\mathcal{L}_{NT}\) fórmula -

\[\phi \left( x \right) \: \text{is}: \: \left( \exists y \right) \left( x = y + y \right).\]

Pero podemos, de hecho, hacerlo incluso mejor que esto. Podemos definir el conjunto de pares por una\(\Delta\) fórmula

\[Even \left( x \right) = \left( \exists y \leq x \right) \left( x = y + y \right).\]

Entonces ahora tenemos una\(\Delta\) -definición de\(EVEN\), el conjunto de números pares. (Intentaremos ser consistentes y usar\(SMALL CAPITALS\) cuando nos referimos a un conjunto de números y\(Italics\) cuando nos referimos a la\(\mathcal{L}_{NT}\) fórmula -que define ese conjunto.) Entonces, por Corolario 5.3.15, vemos que el conjunto de números pares es un subconjunto representable de los números naturales.

En las próximas secciones estaremos haciendo mucho de esto. Veremos un conjunto de números y demostraremos que es representable produciendo una\(\Delta\) -definición del conjunto. En muchos casos, los trucos que usaremos para producir los límites en los cuantificadores serán bastante impresionantes.

Ejemplo 5.3.18:

Tómate un minuto y escribe\(Prime \left( x \right)\), una\(\Delta\) -definición de\(PRIME\), el conjunto de números primos. Una vez hecho eso, aquí hay una definición del conjunto de pares primos, el conjunto de pares de números\(x\) y\(y\) tal que ambos\(x\) y\(y\) son primos, y\(y\) es el siguiente primo después\(x\):

\[Primepair \left( x, y \right) = Prime \left( x \right) \land Prime \left( y \right) \land \left( x < y \right) \land \left[ \left( \forall z < y \right) \left( Prime \left( z \right) \rightarrow z \leq x \right) \right].\]

Observe que\(Primepair\) tiene dos variables libres, como\(PRIMEPAIR \subseteq \mathbb{N}^2\), mientras que su fórmula\(Prime\) tiene exactamente una variable libre. También observe que todos los cuantificadores en cada definición están acotados, por lo que sabemos que las definiciones son\(\Delta\) -definiciones.

Chaff: También esperamos que hayas notado que en la definición de\(Primepair\) usamos tu fórmula\(Prime\), y no intentamos insertar toda tu fórmula cada vez que la necesitábamos -acabamos de escribir\(Prime \left( x \right)\) o\(Prime \left( y \right)\). A medida que resuelvas las muchas definiciones a seguir, será fundamental que hagas lo mismo. Usa libremente fórmulas previamente definidas y conéctalas usando sus nombres. Hacer lo contrario es condenarse a arroyos interminables de símbolos ininteligibles. Estas cosas se vuelven lo suficientemente densas tal como son. No es necesario hacer las cosas más difíciles de lo que son.

Ejercicios

1. Demuestre que el conjunto\(\{ 17 \}\) es representable encontrando una\(\Delta\) fórmula -que defina el conjunto. ¿Se te ocurre una\(\Delta\) fórmula no (probablemente tonta) que defina el mismo conjunto?
2. Supongamos que\(A \subseteq \mathbb{N}\) es representable y representado por la fórmula\(\phi \left( x \right)\). Supongamos también que\(B \subseteq \mathbb{N}\) es representable y representado por\(\psi \left( x \right)\). Demostrar que los siguientes conjuntos también son representables, y encontrar una fórmula que represente a cada uno:
   a)\(A \cup B\)
   \(A \cap B\)
   b) c) El complemento de\(A\),\(\{ x \in \mathbb{N} | x \notin A \}\)
3. Mostrar que cada subconjunto finito de los números naturales es representable y que cada subconjunto de\(\mathbb{N}\) cuyo complemento es finito también es representable.
4. Supongamos que\(f : \mathbb{N}^k \rightarrow \mathbb{N}\) es una función total. Mostrar que\(f\) es una función representable si y solo si\(f\) es un subconjunto representable de\(\mathbb{N}^{k+1}\).
5. Vamos\(A \subseteq \mathbb{N}\). Defina la función característica de\(A\),\(\chi_A : \mathbb{N} \rightarrow \mathbb{N}\) por
   \[ \chi_A \left( x \right) = \begin{cases} \begin{array}{ll} 0 & \text{if} \: x \in A \\ 1 & \text{if} \: x \notin A \end{array} \end{cases}\]
   Mostrar que\(A\) es un subconjunto representable de\(\mathbb{N}\) si y solo si\(\chi_A\) es una función representable.
6. Let\(p \left( x \right)\) Ser un polinomio con coeficientes enteros no negativos. Demuestre que el conjunto\(\{ a \in \mathbb{N} | p \left( a \right) = 0 \}\) es representable. Después de que demuestres esto de la manera obvia, encuentra una manera resbaladiza de escribir la prueba. (O, si fuiste resbaladiza la primera vez, ¡encuentra el camino prosaico!)
7. Escribe una\(\Delta\) -definición para el conjunto\(DIVIDES\). Por lo que se debe llegar a una fórmula con dos variables libres,\(Divides \left( x, y \right)\), que tenga la propiedad de que\(\mathfrak{N} \models Divides \left( \bar{a}, \bar{b} \right)\) si y sólo si\(a\) es un factor de\(b\).
8. Demostrar que el conjunto\(\{ 1, 2, 4, 8, 16, \ldots \}\) de poderes de 2 es representable.
9. Supongamos que sabes que\(\phi \left( x, y \right)\) representa la función total\(f : \mathbb{N} \rightarrow \mathbb{N}\). Mostrar que\(\psi \left( x, y \right) : \equiv \phi \left( x, y \right) \land \left( \forall z < y \right) \left( \neg \phi \left( x, z \right) \right)\) también representa\(f\), y además, para cada uno\(a \in \mathbb{N}\),
   \ [N\ vdash\ left (\ forall y\ right)\ left (\ psi\ left (\ bar {a}, y\ right)\ left trightarrow y =\ overline {f\ left (a\ right)}\ right).
   [Sugerencia: Después de mostrar que\(\psi\) representa\(f\), la segunda parte equivale a mostrar\(N \vdash \psi \left( \bar{a}, \overline{f \left( a \right)} \right)\), lo cual es bastante trivial, y luego demostrar que
   \[N \vdash \left[ \left( \phi \left( \bar{a}, y \right) \land \left( \forall z < y \right) \left( \neg \phi \left( x, z \right) \right) \right) \rightarrow y = \overline{f \left( a \right)} \right].\]
   Así, tomar como hipótesis\(N\),\(\phi \left( \bar{a}, y \right)\), y \(\left( \forall z < y \right) \left( \neg \phi \left( x, z \right) \right)\)y demostrar que hay una deducción de ambos\(\neg \left[ \overline{f \left( a \right)} < y \right]\) y\(\neg \left[ y < \overline{f \left( a \right)} \right]\). Entonces el último de los axiomas de te\(N\) dará lo que necesitas. Para los detalles, véase [Enderton 72, Teorema 33K].]
10. En el último paso inductivo de la prueba de Lema 5.3.10, el uso de la hipótesis inductiva está bastante oculto. Exponga el uso de la hipótesis inductiva y escriba ese paso de la prueba de manera más completa. Terminar los casos para multiplicación y exponenciación.
11. Demostrar Corolario 5.3.12.
12. Rellene los datos de los pasos omitidos en la prueba inductiva de la Proposición 5.3.13. En los dos últimos casos, ¿cómo cambia el argumento si hay más variables libres? Si, por ejemplo, en vez de\(\phi\) ser el de la forma\(\exists x \psi \left( x \right)\),\(\phi\) es de la forma\(\exists x \psi \left( x, y \right)\), ¿eso cambia la prueba?
13. Diremos que una fórmula\(\phi \left( x \right)\) con una variable libre se determina positivamente numéricamente si, para cada una\(a \in \mathbb{N}\), si\(\mathfrak{N} \models \phi \left( a \right)\) entonces\(N \vdash \phi \left( \bar{a} \right)\). Decir\(\phi \left( x \right)\) se determina numéricamente si ambos\(\phi \left( x \right)\) y\(\neg \phi \left( x \right)\) se determinan positivamente numéricamente. Demostrar que\(\phi\) representa un conjunto\(A\) si y sólo si\(\phi\) define\(A\) y\(\phi\) se determina numéricamente. Para reiterar, un conjunto\(A\) es representable si y sólo si\(A\) tiene una definición determinada numéricamente.
14. Demostrar que cada fórmula atómica está determinada numéricamente. Luego mostrar que la colección de fórmulas determinadas numéricamente se cierra bajo\(\neg\),\(\lor\),\(\land\), y cuantificación delimitada.