Autor Tema: El teorema de Gödel (en Z)

0 Usuarios y 1 Visitante están viendo este tema.

23 Abril, 2018, 10:38 am
Leído 5350 veces

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Desde hace unas semanas estoy impartiendo un seminario sobre pruebas de consistencia y, aunque no estaba en lo previsto, sobre la marcha me han preguntado si podía explicar el teorema de incompletitud de Gödel. Como el teorema en sí quedaba muy alejado de los contenidos que estamos viendo, he preparado una demostración del teorema —los teoremas, mejor dicho— para el caso particular de la teoría de conjuntos, que, partiendo del material visto en el seminario, no necesitaba más que cinco páginas.

Abro este hilo para exponer aquí esa prueba (en bastante más de cinco páginas, para partir de cero) porque creo que puede ser un enfoque interesante y, si algún lector interesado va preguntando lo que no entienda, seguro que entre todos podemos pulir la exposición para que resulte lo más clara posible. Abro para eso un hilo de comentarios:

Comentarios a El teorema de Gödel (en Z)

No sé si un lector familiarizado con la prueba general considerará que el enfoque que presento aquí es más claro o más oscuro que el clásico, si muestra más claramente las ideas relevantes o si las oculta, si aporta algo o no aporta nada. Yo creo que algo tiene de esclarecedor, pero será interesante conocer otras opiniones.

La idea fundamental es que muchos tecnicismos de la prueba del teorema de incompletitud se vuelven innecesarios si renunciamos a probar el teorema en toda su generalidad y nos limitamos a aplicarlos a la teoría de conjuntos. Esto no es una gran pérdida, porque no tiene nada de extraño que haya afirmaciones que no sean demostrables ni refutables a partir de una teoría axiomática débil, como pueda ser la determinada por los axiomas de Peano sin más. Eso es comprensible sin más que tener en cuenta que los axiomas de Peano nos proporcionan una capacidad de argumentación relativamente débil, desde luego mucho más débil que la capacidad de argumentación que tiene un matemático cuando razona "libremente", sin exigirse que todo cuanto diga pueda probarse a partir de esos modestos axiomas.

Lo realmente sorprendente del hecho de que el teorema de incompletitud sea aplicable a cualquier teoría axiomática que cumpla sus débiles hipótesis no es que se aplique a las teorías más débiles, sino justo lo contrario, que también sea aplicable a las teorías axiomáticas más fuertes como son las teorías de conjuntos usuales. Lo sorprendente es que, aunque permitamos a un matemático razonar sin restricciones de ninguna clase, es decir, partiendo de los axiomas de la teoría de conjuntos, que permiten demostrar todo lo que los matemáticos admiten como demostrable, aun así existen necesariamente afirmaciones que no podrá demostrar ni refutar.

Pero sucede que para demostrar los teoremas de incompletitud para tales teorías fuertes, para teorías de conjuntos suficientemente potentes, podemos eliminar de la demostración toda referencia a funciones recursivas y a números de Gödel, lo que permite centrarse en las ideas fundamentales de la demostración con menos árboles que distraigan la atención a la hora de ver el bosque.

Más concretamente, al tratar con una teoría de conjuntos en lugar de un sistema aritmético arbitrario, los tecnicismos de la prueba original de Gödel relativos a la representación de funciones recursivas mediante fórmulas aritméticas pueden ser sustituidos por un principio general:

Si un matemático afirma que algo se cumple a ciencia cierta, es que ese "algo" se puede formalizar en la teoría de conjuntos ZFC.

Cuando el matemático sabe dar explícitamente un argumento que prueba su afirmación, y descartamos que pueda haber cometido un error, que pueda haber pasado algo por alto, si su prueba es aceptable en el sentido usual en que una prueba matemática se considera válida, entonces es seguro que dicha prueba se puede formalizar en ZFC. El proceso de formalización será más mecánico cuanto más detallada sea la prueba original, y menos mecánico cuantas más veces se diga en ella "es fácil ver que\ldots", "dejamos como ejercicio comprobar que\ldots"  Si la prueba se da con el suficiente detalle como para no apelar a la imaginación del lector a la hora de cubrir ciertos huecos, el proceso de formalización es meramente rutinario para alguien familiarizado con la lógica de ZFC.

Pese a todo, para que no se nos acuse de estar haciendo trampas y argumente que, después de todo, los tecnicismos de la prueba clásica de los teoremas de Gödel sí que son necesarios incluso en el caso de la teoría de conjuntos, trataremos de dar indicaciones a los lectores morbosos sobre cómo puede justificarse que cada hecho obvio que utilicemos es demostrable en ZFC.

Obviamente, demostrar los teoremas de incompletitud en ZFC requiere cierto conocimiento de ZFC, así que dedicaré los primeros mensajes a describir brevemente la lógica y los fundamentos de la teoría de conjuntos para después pasar a la prueba de los teoremas de incompletitud propiamente dicha.

El programa de la primera parte es el siguiente: imaginemos que queremos empezar a construir las matemáticas "desde cero" con todo rigor. El proceso para ello (según los usos modernos) es el siguiente:

  • Primero hay que definir un lenguaje en el que se puedan enunciar todas las afirmaciones matemáticas, pero que sea técnicamente lo más simple posible, para que sea fácil razonar sobre él.
  • En segundo lugar debemos precisar qué significa que una afirmación de ese lenguaje sea demostrable a partir de unos axiomas formulados también en dicho lenguaje.
  • En tercer lugar hay que seleccionar los axiomas de la teoría de conjuntos, es decir, los axiomas que permiten demostrar todo lo que los matemáticos consideran demostrable.
  • En cuarto lugar hay que mostrar que, realmente, a partir de esos axiomas se pueden demostrar todos los hechos básicos que cualquier matemático acepta sin cuestionárselos cuando tiene que argumentar algo.
  • En quinto lugar ya podemos demostrar cualquier resultado de álgebra, análisis, geometría, topología, etc.

En los próximos mensajes nos ocuparemos de los tres primeros puntos y parcialmente del cuarto. Obviamente, no vamos a entrar en el quinto y demostrar todos los teoremas del mundo.

23 Abril, 2018, 11:20 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Todas las matemáticas conocidas se pueden formular en un lenguaje sorprendentemente simple:

  • En primer lugar necesitamos una sucesión infinita de signos a los que llamaremos variables:

    \( x_0, x_1, x_2,\ldots \)

    En la práctica usaremos letras cualesquiera para nombrar variables, de modo que si escribimos \( x=y \), habrá que entender que \( x \) e \( y \) son dos variables cualesquiera, como \( x_0=x_1 \) o bien \( x_{15}=x_{262} \). En el trabajo cotidiano del matemático es siempre irrelevante qué signos usa como variables, por lo que da igual escribir \( x_5 \) que \( \alpha \) que \( A \), etc. Pero, desde un punto de vista teórico, es útil convenir que las letras a las que recurre un matemático cuando necesita "una letra cualquiera" son signos de una lista predeterminada. Pedimos que sea infinita porque un matemático, después de haber llenado 20 pizarras con una demostración, siempre tiene que tener derecho a escribir una línea más en la que aparezca una variable nueva que no haya aparecido hasta entonces. Un matemático nunca usará más de una cantidad finita de variables, pero siempre puede ir añadiendo más según le vaya haciendo falta.

  • Además de las variables necesitamos dos conectores lógicos \( \lnot \) y \( \rightarrow \) y un cuantificador universal \( \forall \).

    El lector echará en falta algunos signos más, pero es que los definiremos luego a partir de éstos.

  • Por último, necesitaremos dos signos que llamaremos relatores: \( = \) y \( \in \).


En resumen, los signos del lenguaje de la teoría de conjuntos son

\( \begin{array}{ccccccccc}
\lnot&\rightarrow&\forall&=&\in&x_0&x_1&x_2&\cdots
\end{array}
 \)

y ninguno más. No obstante, como ya hemos advertido, cuando no importe si consideramos la variable \( x_0 \) o \( x_{1000} \), usaremos letras cualesquiera para representar las variables.

Las sucesiones finitas de signos (con al menos un signo) de este lenguaje se llaman cadenas de signos. Por ejemplo, una cadena de signos es

\( x_0\forall==\in x_7\in x_2x_1. \)


De entre todas las cadenas de signos, vamos a definir las que "tendrán sentido" para un matemático, y las llamaremos fórmulas. En primer lugar definimos las fórmulas atómicas, que son las de la forma

\( =xy,\qquad \in xy, \)

donde \( x \) e \( y \) son dos variables cualesquiera (tal vez la misma). Adoptamos el convenio de que los relatores van delante de las variables, pero en la práctica escribiremos

\( x=y,\qquad x\in y. \)

Esto hay que entenderlo bien: cuando escribimos \( x=y \) debemos entender que nos referimos a la cadena de signos formada por tres signos, el primero de los cuales es \( = \), el segundo es \( x \) y el tercero es \( y \), sólo que no escribimos los signos en el orden en que aparecen en la cadena, sino en otro más cómodo para nosotros.

Ahora definimos una sucesión generadora de fórmulas como una sucesión finita de cadenas de signos, digamos \( \alpha_1,\ldots, \alpha_n \), con la propiedad de que cada término de la sucesión esté en uno de los casos siguientes:

  • Sea una fórmula atómica.
  • Sea de la forma \( \lnot\alpha \), donde \( \alpha \) es una cadena previa en la sucesión.
  • Sea de la forma \( \rightarrow \alpha\beta \), donde \( \alpha \) y \( \beta \) son cadenas previas en la sucesión.
    En la práctica, en lugar de \( \rightarrow\alpha\beta \) escribiremos \( \alpha\rightarrow \beta \).
  • Sea de la forma \( \forall x \alpha \), donde \( x \) es una variable y \( \alpha \) es una cadena previa en la sucesión.

Diremos que una cadena de signos es una fórmula si es la última cadena de signos de una sucesión generadora de fórmulas.

Ejemplo Veamos que \( \forall u(u\in x\rightarrow u\in y) \) es una fórmula. La tabla siguiente muestra una sucesión generadora. La segunda columna contiene las fórmulas escritas con notación de "bajo nivel", es decir, nombrando los signos en el orden que aparecen, y la tercera columna contiene la notación de "alto nivel" en la que hemos alterado las posiciones para leerlas más cómodamente.

\( \begin{array}{l|l|l|l|}
&\mbox{Bajo nivel}&\mbox{Alto nivel}\\
\hline
1&\in ux&u\in x&\mbox{atómica}\\
2&\in u y&u\in y&\mbox{atómica}\\
3&\rightarrow\in ux\in uy&u\in x\rightarrow u\in y&\mbox{Implicación 1,2}\\
4&\forall u\rightarrow\in ux\in uy&\forall u(u\in x\rightarrow u\in y)&\mbox{generalización 3}\\
\hline
\end{array} \)

La diferencia entre la notación de "bajo nivel" y la de "alto nivel" es que la primera es inequívoca, mientras que la segunda requiere paréntesis para evitar ambigüedades. Si en la línea 4 quitáramos los paréntesis, no estaría claro si nos referimos a la fórmula que aparece en la segunda columna o si, por el contrario, nos referimos a

\( (\forall u u\in x)\rightarrow u\in y. \)

Con la notación de "bajo nivel" no hay ambigüedad, pues esta fórmula sería

\( \rightarrow \forall u\in ux \in uy. \)


Otro ejemplo: sería ambiguo escribir

\( x=y\rightarrow x\in v\rightarrow p\in q, \)

pues esto puede referirse tanto a

\( (x=y\rightarrow x\in v)\rightarrow p\in q\equiv\ \rightarrow \rightarrow=xy \in x v\in p q, \)

como a

\( x=y\rightarrow (x\in v\rightarrow p\in x)\equiv\ \rightarrow=xy\rightarrow\in xv\in px. \)

Si tuviéramos que programar un ordenador para manipular fórmulas, veríamos que todo es mucho más sencillo si las representamos a "bajo nivel", es decir, con los signos en orden según las definiciones que hemos dado. Podemos pensar que la notación de "alto nivel" es como un lenguaje de programación (tipo C o Java, etc.) mientras que la notación de "bajo nivel" es el lenguaje máquina que, en último extremo, no es más que una sucesión de ceros y unos, que es lo que realmente se guarda en la memoria del ordenador. Cualquier afirmación de un lenguaje de programación sólo es aceptable en la medida en que el ordenador sepa transformarla en instrucciones de lenguaje máquina, que es lo único que realmente tiene sentido para él y sabe ejecutar. Del mismo modo, somos libres de nombrar a las fórmulas con los convenios que juzguemos convenientes siempre y cuando esté claro en todo momento a qué cadena de signos estamos haciendo referencia con nuestros criterios de notación.

Veamos un ejemplo de la ventaja que supone considerar que "en el fondo" las fórmulas tienen sus signos dispuestos como hemos exigido, independientemente de cómo las nombremos en la práctica.

Teorema Sean \( \alpha_1,\ldots, \alpha_m \) y \( \beta_1,\ldots, \beta_n \) dos sucesiones de fórmulas. Si se cumple que \( \alpha_1\cdots \alpha_m\equiv \beta_1\cdots \beta_n \), entonces \( m=n \) y cada \( \alpha_i\equiv \beta_i \).

El signo \( \equiv \) lo usamos para indicar que los dos miembros que relaciona son en realidad dos nombres para una misma sucesión de signos.

Entendamos esto: si tomamos las palabras "bocado" y "cena" y las unimos sin espacio de separación, para formar "bocadocena", alguien que lea esto no podrá saber si hemos unido "bocado" con "cena" o bien "boca" con "docena". Pues esto no sucede con las fórmulas de nuestro lenguaje. Si yuxtaponemos varias de ellas sin marcar dónde termina una y dónde empieza la siguiente, siempre es posible determinar cuántas fórmulas hemos yuxtapuesto y dónde empieza y termina cada una.

Demostración
Tenemos una yuxtaposición de fórmulas

\( \zeta \equiv \alpha_1\cdots \alpha_m\equiv \beta_1\cdots \beta_n \)

y queremos probar que las dos descomposiciones son la misma. Razonamos por inducción sobre el número de signos de \( \zeta \).

La menor longitud posible para \( \zeta \) es \( 3 \), en cuyo caso tiene que constar de una única fórmula atómica, luego tiene que ser \( m=1=n \) y  \( \zeta\equiv\alpha_1\equiv \beta_1 \).

Supongamos que es cierto para yuxtaposiciones de longitud menor que \( \zeta \) y distingamos casos según cuál es el primer signo \( \zeta \) (que tiene que ser también el primer signo de \( \alpha_1 \) y el de \( \beta_1 \)). Si este signo es un \( = \) o un \( \in \), entonces necesariamente \( \alpha_1 \) y \( \beta_1 \) son una fórmula atómica (de longitud \( 3 \)), luego tiene que ser \( \alpha_1\equiv \beta_1 \) y, al eliminar los tres primeros signos, resulta que \( \alpha_2\cdots \alpha_m\equiv \beta_2\cdots \beta_n \). Por hipótesis de inducción \( m=n \) y cada \( \alpha_i\equiv \beta_i \).

Supongamos ahora que el primer signo es \( \lnot \). Entonces \( \alpha_1\equiv \lnot\gamma_1 \) y \( \beta_1\equiv\lnot\delta_1 \), luego al eliminar el negador resulta que \( \gamma_1\alpha_2\cdots \alpha_m\equiv \delta_1\beta_2\cdots \beta_n \). Por hipótesis de inducción \( m=n \), \( \gamma_1\equiv \delta_1 \) y \( \alpha_i\equiv \beta_i \), para \( i\geq 2 \), pero la primera identidad implica a su vez que \( \alpha_1\equiv \beta_1 \).

Si el primer signo es \( \rightarrow \) razonamos igualmente. Ahora \( \alpha_1\equiv \rightarrow \gamma_1\gamma_2 \) y \( \beta_1\equiv \rightarrow\delta_1\delta_2 \), y basta eliminar el implicador de ambos miembros y aplicar la hipótesis de inducción.

Similarmente, si el primer signo es \( \forall \), el segundo debe ser en ambos miembros la misma variable \( x \), de modo que \( \alpha_1\equiv \forall x \gamma_1 \) y \( \beta_1\equiv \forall x \delta_1 \). Basta suprimir los dos primeros signos y aplicar la hipótesis de inducción.
[cerrar]

Sucede que todos los teoremas matemáticos enunciados en todos los libros y artículos de matemáticas pueden escribirse como sucesiones finitas (a "bajo nivel") de los signos que estamos considerando, en el mismo sentido en que cualquier programa de ordenador se guarda en la memoria del ordenador que lo ejecuta como una sucesión de ceros y unos. Sin embargo, al igual que ningún programador escribe programas recitando sucesiones de ceros y unos, sino que usa un lenguaje "de alto nivel" y luego deja que un programa transforme sus instrucciones en la sucesión de ceros y unos adecuada, ningún matemático escribe nunca fórmulas "a bajo nivel", sino que usa todo un complejo sistema de abreviaturas para que lo que escribe resulte legible. Ya hemos introducido algunas, pero he aquí algunas más:

\( \alpha\lor\beta \equiv \lnot\alpha\rightarrow \beta,\quad \alpha\land \beta\equiv \lnot(\lnot\alpha\lor\lnot\beta),\quad \alpha\leftrightarrow\beta\equiv (\alpha\rightarrow\beta)\land(\beta\rightarrow\alpha),\quad \exists x\alpha \equiv \lnot\forall x\lnot\alpha.
 \)

Así, por ejemplo, la fórmula

\( x=y\lor x=z \)

es exactamente la misma (no "equivalente a", sino "la misma que")

\( \lnot x=y\rightarrow x=z, \)

que a su vez es la misma que

\( \rightarrow \lnot = xy=xz. \)


Ésta sería su representación a "bajo nivel", la que nunca usaremos, pero la que más le gustaría a un ordenador que tuviera que trabajar con fórmulas.

Otras abreviaturas convenientes a la hora de escribir a "alto nivel" son:

\( x\neq y\equiv \lnot x = y,\quad x\notin y\equiv \lnot x\in y \),

así como que escribiremos \( \forall xyz\alpha\equiv \forall x\forall y\forall z\alpha \) y \( \exists xyz\alpha\equiv \exists x\exists y\exists z\alpha \), es decir, que no repetiremos los cuantificadores cuando haya que escribir varios seguidos.

También escribiremos \( \alpha\lor \beta\lor \gamma\lor \delta  \) en lugar de \( ((\alpha\lor \beta)\lor\gamma)\lor \delta \), e igualmente con las conjunciones.

23 Abril, 2018, 01:19 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ya hemos definido el lenguaje de la teoría de conjuntos. Ahora pasamos a definir qué significa que una fórmula \( \alpha \) sea consecuencia lógica de un conjunto de premisas \( \Gamma \) (un conjunto de fórmulas).

Para ello definimos primero el concepto de axioma lógico. Diremos que una fórmula es un axioma lógico si es de una de las formas siguientes:

\( \begin{array}{lll}
1)&\alpha\rightarrow (\beta\rightarrow \alpha)\\
2)&(\alpha\rightarrow (\beta\rightarrow \gamma))\rightarrow ((\alpha\rightarrow\beta)\rightarrow (\alpha\rightarrow \gamma))\\
3)&(\lnot\alpha\rightarrow\lnot\beta)\rightarrow (\beta\rightarrow\alpha)\\
4)&\forall x\alpha\rightarrow S_x^y\alpha&\mbox{donde $y\equiv x$ o bien no está en $\alpha$.}\\
5)&\forall x(\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \forall x\beta)&\mbox{si $x$ no está en $\alpha$.}\\
6)&\forall x(x=y\rightarrow \alpha)\leftrightarrow S_x^y\alpha&\mbox{donde $y\equiv x$ o bien no está en $\alpha$.}
\end{array}
 \)

Aquí hay que entender que \( S_x^y\alpha \) representa la fórmula que resulta de cambiar todas las \( x \) por \( y \) en \( \alpha \). Por ejemplo, la fórmula

\( \forall x \exists u x\in u \rightarrow \exists u y\in u  \)

es un axioma de tipo 4, ya que cumple el requisito de que la variable \( y \) no está en \( \exists u x\in u \). En cambio, no es un axioma la fórmula

\( \forall x \exists u x\in u \rightarrow \exists u u\in u, \)

porque la variable \( u \) por la que hemos sustituido la \( x \) sí que está en \( \exists u x\in u \).

Si \( \Gamma \) es un conjunto de fórmulas, una deducción con premisas en \( \Gamma \) es una sucesión de fórmulas, digamos \( \alpha_1,\ldots, \alpha_n \) de modo que cada una de ellas cumple una de las condiciones siguientes:

  • Es una premisa (una fórmula de \( \Gamma \)).
  • Es un axioma lógico.
  • Es de la forma \( \alpha \), de modo que entre las fórmulas anteriores de la sucesión se encuentren \( \beta\rightarrow \alpha \) y \( \beta \), en cuyo caso diremos que \( \alpha \) se deduce por Modus Ponens (MP) de dichas fórmulas.
  • Es de la forma \( \forall x \alpha \), donde \( \alpha \) es una fórmula anterior de la sucesión, en cuyo caso diremos que \( \forall x \alpha \) se deduce por Introducción del generalizador (IG) a partir de \( \alpha \).

Diremos que \( \alpha \) es una consecuencia lógica de \( \Gamma \), y lo representaremos por \( \Gamma\vdash \alpha \), si \( \alpha \) es la última línea de una deducción con premisas en \( \Gamma \).

Sucede que esta definición de consecuencia lógica se corresponde exactamente con lo que un matemático entiende por consecuencia de unas premisas dadas (entendiendo que hay que incluir entre las premisas cualquier axioma que pretenda suponer en su argumento). No es evidente en absoluto que esta definición aparentemente tan restrictiva contenga todas las formas de razonamiento que un matemático acepta como tales. El lector interesado puede consultar el hilo  Lógica de primer orden en el que muestro cómo a partir de esta definición de deducción "a bajo nivel" es posible introducir abreviaturas "de alto nivel" que dan cabida a todos los modos de razonar habituales en matemáticas, incluyendo el probar una implicación \( \alpha\rightarrow \beta \) suponiendo \( \alpha \) y llegando a \( \beta \), la argumentación por reducción al absurdo, etc.

En última instancia, lo que justifica que esta definición de consecuencia lógica es adecuada es el teorema de completitud de Gödel, que viene a decir que \( \Gamma\vdash \alpha \) se cumple si y sólo si el hecho de que unos objetos cualesquiera satisfagan las premisas de \( \Gamma \) hace necesariamente que también hagan verdadera a \( \alpha \).

Por ejemplo,

\( \forall x(x\in y\rightarrow x\in z), \exists u u\in y\vdash \exists u u\in z, \)

porque si unos objetos cualesquiera cumplen que todo \( x \) que pertenezca a \( y \) (sea lo que sea "pertenecer") también pertenece a \( z \) y uno de esos objetos \( u \) pertenece a \( y \), es necesariamente cierto que ese \( u \) (sea lo que sea) tiene que pertenecer a \( z \) (sea lo que sea "pertenecer"). El teorema de completitud garantiza que, dado que esto es así, va a existir una deducción lógica de \( \exists uu\in z \) a partir de las dos premisas dadas.

Notemos que éste es un hecho en el que se apoya cualquier demostración de los teoremas de incompletitud, es decir, en cualquiera de ellas se da una definición de "deducción" similar a la que hemos dado (si no igual) y se asume que cuando se habla de "demostrar" en la teoría considerada se habla de "demostrar" en este sentido aparentemente tan restrictivo, y es el teorema de completitud el que garantiza que con ello realmente se está hablando de lo que un matemático entiende por "demostrar".

En conclusión, debemos tener presente que dar una demostración matemática en los términos estrictos que exige la definición que hemos dado sería tan suicida como tratar de analizar un algoritmo a partir del código binario escrito en la memoria del ordenador que lo ejecuta. Un argumento matemático se considera completamente detallado cuando ya no hace falta ninguna idea original para entender cómo se pasa de una afirmación a la siguiente, sino que formalizar ese paso es una mera tarea rutinaria. Rutinaria no quiere decir "fácil", en el sentido de que un programador no tiene por qué saber qué secuencia de ceros y unos se corresponde exactamente con las instrucciones que está programando a alto nivel, sino que rutinaria significa que se puede hacer con más o menos trabajo, pero sin necesidad de aportar ninguna idea original y sin riesgo de que realmente no pueda hacerse.

23 Abril, 2018, 03:48 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Para tener completamente definida la teoría de conjuntos sólo nos falta especificar los axiomas que un matemático acepta en sus razonamientos, más allá de los meros axiomas lógicos. En primer lugar presentamos la teoría de Zermelo que contiene todos los axiomas de ZFC excepto tres que aquí no vamos a necesitar, y que discutiremos más adelante:

\( \begin{array}{ll}
\mbox{Extensionalidad}&\forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y)\\
\mbox{Vacío}&\exists x\forall y\, y\notin x\\
\mbox{Par}&\forall xy\exists z\forall u(u\in z\leftrightarrow u=x\lor u=y)\\
\mbox{Unión}&\forall x\exists y\forall u(u\in y\leftrightarrow \exists v(u\in v\land v\in x))\\
\mbox{Especificación}&\forall x\exists z\forall u(u\in z\leftrightarrow u\in x\land \alpha)\\
\mbox{Partes}&\forall x\exists y\forall u(u\in y\leftrightarrow u\subset x)\\
\mbox{Infinitud}&\exists x(\emptyset\in x\land \forall u(u\in x\rightarrow u'\in x))
\end{array} \)

El axioma de especificación no es un único axioma, sino que comprende infinitas fórmulas, todas las que tengan la forma indicada, donde \( \alpha \) recorre todas las fórmulas en las que no aparezca la variable \( z \).

Los dos últimos axiomas contienen notación "de alto nivel" que todavía no hemos introducido. Podríamos haberlos enunciado "a más bajo nivel", pero a costa de dificultar su legibilidad, así que los hemos enunciado así a falta de explicar la notación empleada. Pero antes de entrar en ello analizaremos brevemente los axiomas precedentes.

La idea básica es que vamos a hablar de unos objetos llamados "conjuntos" entre los que hay establecida una relación de pertenencia. No se define lo que es un conjunto ni lo que es la pertenencia, del mismo modo que en la geometría axiomática no se define lo que es un punto o una recta ni lo que es que una recta pase por un punto, sino que se dan unos axiomas que determinan las propiedades de los puntos y las rectas. Igualmente, aquí damos unos axiomas que determinan las propiedades de los conjuntos sin necesidad de definirlos.

  • El axioma de extensionalidad afirma que si dos conjuntos tienen los mismos elementos, entonces son iguales, es decir, que un conjunto está completamente determinado por los conjuntos que le pertenecen.

  • El segundo axioma afirma que hay un conjunto que no tiene elementos. Claramente es único, pues dos conjuntos sin elementos tendrían los mismos elementos (ninguno), luego serían el mismo por el axioma de extensionalidad.

    Esto hace que podamos definir \( \emptyset \) como el único conjunto sin elementos. Para un matemático esto es suficiente, pero para nosotros va a ser importante entender la lógica subyacente a esta definición:

    Sucede que el signo \( \emptyset \) no se corresponde con ningún signo o cadena de signos de nuestro lenguaje formal. "Oficialmente no es nada". Lo que sí es algo es la fórmula \( x=\emptyset \). Esto ha de entenderse, por definición, como una forma de escritura de "alto nivel" de la fórmula

    \( x=\emptyset \equiv \forall y\, y\notin x. \)


    Así, por ejemplo, si escribimos \( \emptyset \in z \), esto debe entenderse como

    \( \emptyset\in z\equiv \exists x(x=\emptyset \land x\in z)\equiv \exists x(\forall y\, y\notin x\land x\in z). \)


    A su vez, podríamos seguir desarrollando estas expresiones hasta llegar a una expresión equivalente en puro "lenguaje máquina", pero no ganaremos nada con ello. Lo importante es entender en qué sentido decimos que \( \emptyset \) no es nada en sí mismo, pero que toda fórmula en la que aparezca $\emptyset$ puede (y debe) entenderse como un nombre de alto nivel de la fórmula que resulta de poner "existe un \( x \) tal que \( \forall y \, y\notin x \) y que cumple lo que la fórmula dada afirma de \( \emptyset \)".

  • Lo mismo sucede con el tercer axioma, que postula la existencia de un conjunto \( z \) que contiene exactamente a dos conjuntos dados \( x, y \) (no necesariamente distintos). Nuevamente, dicho conjunto es único, porque si dos conjuntos tienen por elementos a \( x, y \), tienen los mismos elementos, luego por el axioma de extensionalidad son el mismo conjunto. Esto nos permite representar por \( \{x, y\} \) al único conjunto cuyos elementos son \( x \) e \( y \).

    Nuevamente, de cara a entender bien los mensajes siguientes, debemos insistir en que, técnicamente, \( \{x, y\} \) no es nada expresable en el lenguaje de la teoría de conjuntos, pero cualquier fórmula que contenga \( \{x, y\} \) puede verse como una descripción "de alto nivel" de una fórmula en la que esto no aparece. El caso más elemental es

    \( z=\{x, y\}\equiv \forall u(u\in z\leftrightarrow u=x\lor u = y), \)

    que a su vez permite eliminar \( \{x, y\} \) de cualquier otra fórmula. Por ejemplo,

    \( \{x,y\}\in w\equiv \exists z(z=\{x, y\}\land z\in w), \)

    donde a su vez \( z=\{x,y\} \) se elimina como hemos indicado. Otro ejemplo:

    \( \{x, y\}=\{p, q\}\equiv \exists zr(z=\{x,y\}\land r=\{p, q\}\land z=r), \)

    donde a su vez los dos pares se pueden eliminar como sabemos, etc.

    Tomando \( x=y \) en el axioma del par tenemos la existencia de un (único) conjunto cuyo único elemento es un conjunto dado \( x \). Lo representaremos por \( \{x\} \), de modo que

    \( z=\{x\}\equiv \forall u(u\in z\leftrightarrow u=x). \)

    Notemos que \( \{x\}=\{x, x\} \), pues ambos conjuntos tienen los mismos elementos. A partir de los pares desordenados \( \{x, y\} \) podemos definir los pares ordenados como

    \( (x, y)=\{\{x\}, \{x,y\}\}. \)


    Técnicamente, esto significa que, aunque \( (x, y) \) no es ninguna expresión de nuestro lenguaje formal, hay que entender que

    \( z=(x, y)\equiv \forall u(u\in z\leftrightarrow u=\{x\}\lor u=\{x, y\}), \)

    donde los pares desordenados pueden eliminarse como ya sabemos.

  • Similarmente, el axioma de la unión afirma que, para cada conjunto \( x \), existe un conjunto (claramente único) que podemos representar por \( \bigcup x \) cuyos elementos son los elementos de los elementos de \( x \). En particular \( \bigcup\{x, y\} \) es un conjunto cuyos elementos son los elementos de \( x \) y los de \( y \). Lo representaremos por \( x\cup y = \bigcup\{x, y\} \). Concretamente, adoptamos como definición que

    \( z=x\cup y\equiv \forall u(u\in z\leftrightarrow u\in x\lor u\in y). \)


    En particular, dado un conjunto \( x \), tenemos que \( x\cup\{x\} \) es un conjunto cuyos elementos son los elementos de \( x \) y el propio \( x \). Por el axioma de extensionalidad hay un único conjunto que cumple esto, y lo representaremos por \( x' \). Concretamente, tomamos como definición que

    \( z=x'\equiv \forall u(u\in z\leftrightarrow u\in x\lor u=x). \)
  • El axioma de especificación afirma que, dado un conjunto \( x \), existe el subconjunto formado por los elementos de \( x \) que cumplen lo que dice una fórmula \( \alpha \). Es el conjunto que habitualmente se representa como

    \( \{u\in x\mid \alpha\}. \)

    Por ejemplo, si tomamos \( \alpha\equiv u\in y \) tenemos que

    \( \{u\in x\mid u\in y\} \)

    es decir, que dados dos conjuntos \( x, y \), existe un conjunto \( z \) (único por extensionalidad) cuyos elementos son los que están a la vez en \( x \) y en \( y \). A este conjunto lo llamaremos \( x\cap y \). Así, por definición,

    \( z=x\cap y\equiv \forall u(u\in z\leftrightarrow u\in x\land u\in y). \)

  • En el enunciado del axioma de partes hemos usado la notación

    \( u\subset x\equiv \forall v(v\in u\rightarrow v\in x), \)

    que significa que el conjunto \( u \) es un subconjunto de \( x \), en el sentido de que todos los elementos de \( u \) lo son también de \( x \). Lo que afirma el axioma de partes es que, dado \( x \) existe un conjunto (claramente único) que contiene a todos los subconjuntos de \( x \). Usaremos la notación

    \( y=\mathcal Px\equiv \forall u(u\in y\leftrightarrow u\subset x). \)

  • Finalmente, el enunciado que hemos dado del axioma de infinitud es una forma de representar la fórmula

    \( \exists x(\exists y(y=\emptyset \land y\in x)\land \forall u(u\in x\rightarrow \exists z(z=u'\land z\in x))), \)

    donde ya hemos visto a qué fórmulas representan las expresiones \( y=\emptyset \) y \( z= u' \).

    En el mensaje siguiente explicaremos brevemente el significado de este axioma.

Aquí terminamos señalando que, a partir de estos axiomas, introduciendo definiciones cada vez más sofisticadas, es posible demostrar casi todos los resultados matemáticos contenidos en todos los libros y artículos de investigación publicados hasta la fecha y los que se publicarán en el futuro. El "casi" es porque algunos requieren dos o tres axiomas más. La teoría Z que acabamos de describir basta para formalizar las pruebas de todos los resultados que se enseñan en la enseñanza secundaria y buena parte de los universitarios. Los tres axiomas que faltan para tener todo ZFC son los siguientes:

  • El axioma de reemplazo (que al  añadírselo a Z da lugar a la teoría de Zermelo-Fraenkel ZF). En realidad no es un axioma, sino un esquema que comprende infinitos axiomas, como el axioma de especificación. Se necesita para construir los ordinales, definir y demostrar las propiedades de los cardinales infinitos no numerables (los álefs) realizar construcciones por recursión transfinita y otras sutilezas completamente apartadas de las matemáticas más terrenales, así como algunas equivalencias puñeteras entre distintas formas alternativas de definir los números naturales y poco más.

    Está formado por las fórmulas que responden al esquema siguiente:

    \( \forall xyz(\alpha(x,y)\land \alpha(x, z)\rightarrow y=z)\rightarrow \forall a\exists b\forall y(y\in b\leftrightarrow \exists x(x\in a\land \alpha(x, y))),
     \)
    donde, si \( \alpha(x, y) \) es cualquier fórmula que contenga las variables \( x, y \), entonces \( \alpha(x, z) \) es la fórmula que resulta de cambiar \( y \) por una variable \( z \) cualquiera que no esté en la fórmula.

  • El segundo axioma es el axioma de elección, del que todo el mundo ha oído hablar, con el que obtenemos la teoría ZFC.
     
  • Hay argumentos muy técnicos propios de la teoría de conjuntos más abstracta que requieren un axioma más, el llamado axioma de regularidad:

    \( \forall x(x\neq \emptyset\rightarrow \exists u(u\in x\land u\cap x=\emptyset)) \)


No comentamos nada sobre estos axiomas porque no los vamos a necesitar. Remito a este hilo de argentinator para más detalles sobre los axiomas de la teoría de conjuntos. En la práctica nos bastará con tener presente el hecho que ya hemos señalado anteriormente: cualquier cosa que un matemático considera un "teorema" (algo demostrado, desde que \( 2+2=4 \) hasta el teorema de Galois) es algo que puede expresarse en el lenguaje que hemos descrito y que puede demostrarse a partir de los axiomas lógicos y los axiomas de ZFC con una demostración en el sentido preciso que hemos definido en el mensaje precedente. Y en la mayoría de los casos, los axiomas de Z son más que suficientes.

23 Abril, 2018, 05:54 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
De acuerdo con el plan trazado en el primer mensaje, una vez establecidos los axiomas de la teoría de conjuntos, lo que toca es comprobar que a partir de ellos es posible demostrar todos los resultados básicos sobre conjuntos, que a su vez permiten demostrar todos los teoremas que uno conozca, sean del álgebra, del análisis matemático, etc. Sólo poniéndose a ello se convence uno de que los axiomas dados son suficientes para demostrar cualquier cosa que un matemático acepta como demostrada. Lo que hace un matemático cuando demuestra algo es equivalente (lo sepa él o no) a demostrar la formalización de su teorema en el lenguaje de la teoría de conjuntos a partir de los axiomas de ZFC, entendiendo por "demostración" lo que hemos definido como tal, y en la mayor parte de casos es suficiente con los axiomas de Z o los de ZC.

No vamos a "demostrar todo" aquí, por razones obvias, sino que nos limitaremos a señalar algunas consecuencias que vamos a necesitar de los axiomas.

\paragraph{Relaciones y funciones} En primer lugar observamos que, por la definición de par ordenado, dados conjuntos \( u\in x,v\in y \), se cumple que \( u, v\in x\cup y \), de donde \( \{u\},\{u,v\}\in \mathcal P(x\cup y) \), de donde \( (u,v)=\{\{u\},\{u,v\}\}\in \mathcal P\mathcal P(x\cup y) \), lo que permite definir el producto cartesiano a partir del axioma de especificación:

\( x\times y=\{z\in \mathcal P\mathcal P(x\cup y)\mid \exists uv(u\in x\land v\in y\land z=(u,v))\}. \)

A su vez, esto permite definir las relaciones en un conjunto \( x \) como subconjuntos de \( x\times x \) (y a su vez distinguir entre relaciones reflexivas, simétricas, transitivas, antisimétricas, de equivalencia, de orden, etc.) y las aplicaciones \( f:x\longrightarrow y \) como subconjuntos \( f\subset x\times y \) que para cada \( u\in x \) contienen un único par \( (u,v) \) con \( v\in y \). Esto permite definir los conceptos de aplicación inyectiva, suprayectiva, biyectiva, composición de aplicaciones, aplicación inversa, etc.\ y demostrar sus propiedades.

Números naturales Veamos ahora cómo el axioma de infinitud permite definir los números naturales. Lo que afirma este axioma es que existe un conjunto inductivo, donde un conjunto inductivo se define como un conjunto \( x \) que cumpla

\( x\mbox{ inductivo} \equiv \emptyset\in x\land \forall u(u\in x\rightarrow u'\in x). \)

Fijado un conjunto inductivo, podemos definir, por el axioma de especificación, el conjunto

\( \mathbb N=\{n\in x\mid \forall y(y\mbox{ inductivo}\rightarrow n\in y)\}, \)

de modo que \( \mathbb N \) contiene a todos los conjuntos \( n \) que pertenecen a todos los conjuntos inductivos. Notemos que \( \mathbb N \) es independiente de la elección de \( x \), pues, sea quien sea \( x \), los elementos de \( \mathbb N \) son siempre los mismos: los conjuntos que están en todo conjunto inductivo. El conjunto \( x \) sólo sirve para asegurar la existencia de \( \mathbb N \) como subconjunto de \( x \) por el axioma de especificación. Los elementos de \( \mathbb N \) se llaman números naturales. Por definición

\( x=\mathbb N\equiv \forall n(n\in x\leftrightarrow \forall y(y\mbox{ inductivo}\rightarrow n\in y)). \)

Por definición de conjunto inductivo tenemos que \( \emptyset\in \mathbb N \), es decir, que el conjunto vacío es un número natural. Cuando pensemos en el conjunto vacío como número natural lo representaremos por \( 0 \).

También por definición de conjunto inductivo es inmediato que si \( n\in \mathbb N \), también \( n'\in \mathbb N \) (pues si \( n \) está en todos los conjuntos inductivos, lo mismo le sucede a \( n' \)). Nos referiremos a \( n' \) como el número natural siguiente a \( n \).

Con esto tenemos demostrados los dos primeros axiomas de Peano. En total son los siguientes:

  • \( 0\in \mathbb N \)
  • \( \forall n(n\in \mathbb N\rightarrow n'\in \mathbb N) \)
  • \( \forall n\, n'\neq 0 \)
  • \( \forall mn(m'=n'\rightarrow m=n) \)
  • \( \forall x(0\in x\land \forall n(n\in \mathbb N\land n\in x\rightarrow n'\in x)\rightarrow \mathbb N\subset x. \)

Definimos

\( 1\equiv 0' = \emptyset \cup \{\emptyset\} = \{0\},\quad 2=1'=1\cup\{1\}=\{0,1\}, \quad 3=2'=\{0, 1, 2\},\ldots
 \)

Más precisamente, los términos \( 0, 1, 2, \ldots \) no son oficialmente nada en el lenguaje de la teoría de conjuntos, pero las fórmulas que los contienen son expresiones "de alto nivel" de fórmulas del lenguaje de la teoría de conjuntos, gracias a las identidades

\( x =0\equiv \forall u\,u\notin x,\quad x=1\equiv \forall u(u\in x\leftrightarrow u=0),\quad x=2\equiv \forall u(u\in x\leftrightarrow u=0\lor u=1),\ldots \)

Por ejemplo, \( 3\in 5 \) no es más que una expresión "de alto nivel" para nombrar la fórmula

\( 3\in 5\equiv \exists xy(x=3\land y=5\land x\in y), \)

donde a su vez \( x=3 \) e \( y=5 \) se reducen a fórmulas sin números naturales mediante las identidades precedentes.

Aparte de esto, lo único que vamos a necesitar sobre resultados demostrables en Z sobre números naturales es el hecho de que es posible definir funciones por recurrencia, es decir, que para definir una función sobre todos los números naturales, podemos definirla sobre \( 0 \) y definirla sobre \( n \) supuesto que ya está definida sobre los números menores que \( n \).

Sucesiones finitas En lo sucesivo trataremos a menudo con sucesiones finitas de números naturales, entendidas como aplicaciones \( s: n\longrightarrow \mathbb N \), donde \( n \) es un número natural, al que llamaremos longitud de la sucesión \( s \) y lo representaremos por \( \ell(s) \).

Por ejemplo, una sucesión de longitud \( 3 \) es \( s=(3,5,1) \), donde esta notación debe entenderse como que \( s:3\longrightarrow \mathbb N \) es la aplicación dada por \( s(0)=3, s(1)=5, s(2)=1 \) o, más explícitamente,

\( s=\{(0,3), (1, 5), (2, 1)\}. \)

Más explícitamente aún,

\( s=\{(0,3), (1, 5), (2, 1)\}\equiv \forall u(u\in s\leftrightarrow u=(0, 3)\lor u=(1, 5)\lor u=(2,1)). \)


Técnicamente, tenemos que distinguir entre un número natural, como \( 5 \), y la sucesión \( (5) \) formada sólo por él. Concretamente, \( (5)=\{(0,5)\} \), aunque en la práctica podemos identificar uno y otra.

Si llamamos \( S^1 \) al conjunto de todas las sucesiones finitas de números naturales, en él podemos definir la aplicación \( S^1\times \mathbb N\longrightarrow S^1 \) dada por

\( s*n=s\cup\{(\ell(s),n)\}. \)

Por ejemplo,

\( \{(0,3), (1, 5), (2, 1)\}*7=\{(0,3), (1, 5), (2, 1)\}\cup\{(3,7)\}=\{(0,3), (1, 5), (2, 1),(3, 7)\}. \)

En definitiva, \( s*n \) es la sucesión que resulta de añadir \( n \) a \( s \). A su vez, esto permite definir la yuxtaposición \( S^1*S^1\longrightarrow S^1 \) como la única operación que cumple:

\( s*\emptyset = s,\qquad s*(t*n)=(s*t)*n, \)

donde estamos contando al conjunto vacío como la única sucesión de números naturales de longitud \( 0 \). Por ejemplo:

\( (3, 5, 1)*(2, 9)=(3, 5, 1)*((2)*9) = ((3, 5, 1)*(2))*9=((3, 5, 1)*(\emptyset*2))*9 \)

\( =(((3,5,1)*\emptyset)*2)*9=((3,5,1)*2)*9=(3,5,1,2)*9=(3,5,1,2,9). \)

En suma, la yuxtaposición consiste en poner la segunda sucesión a continuación de la primera.

Finalmente, necesitaremos considerar también el conjunto \( S^2 \) formado por las sucesiones finitas de sucesiones finitas de números naturales. Un elemento de \( S^2 \) es por ejemplo

\( ((3, 3, 8, 1), (1, 1), (0, 1, 2, 3)). \)

La teoría Z es más que suficiente para demostrar todas las propiedades obvias relativas a sucesiones finitas de números naturales y sucesiones finitas de sucesiones finitas, y esto es todo lo que necesitamos para pasar a demostrar los teoremas de incompletitud para Z o para cualquier teoría de conjuntos tan potente como ella (o más).

24 Abril, 2018, 03:17 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
A partir del mensaje siguiente empezaré a exponer la prueba de los teoremas de incompletitud, pero antes voy a dar una visión de conjunto de todo lo visto hasta ahora, para evitar que los tecnicismos oculten las ideas relevantes.

Imaginemos que alguien diseña un algoritmo para calcular cualquier cosa, por ejemplo, todos los primos menores que \( 1\,000 \). Si sólo quiere convencerse de que un ordenador puede hacer ese cálculo, le bastará dar un esbozo del procedimiento a seguir, asegurándose de que no contiene ningún paso que requiera una imaginación de la que el ordenador carece.

Pero si quiere que un ordenador haga el cálculo, tendrá que concretar ese esbozo en una sucesión de instrucciones de acuerdo con la sintaxis de algún lenguaje de programación, como C, Java, etc.

Pero un ordenador no sabe realmente leer esas instrucciones. Necesita un software que las traduzca a su vez a lenguaje máquina, lo que en definitiva no es más que una sucesión de números entre 0 y 255 o, si se quiere, una sucesión de ceros y unos.

El proceso no es reversible, en el sentido de que si alguien analiza la sucesión de ceros y unos resultante, no le será fácil reconstruir qué hará el ordenador al ejecutarla (no es fácil a partir del código que uno compra cuando compra una aplicación reconstruir las instrucciones de alto nivel que lo generan para entender cómo funciona). Sin embargo, el ordenador lo entenderá perfectamente y, si no hay errores de programación, lo ejecutará e imprimirá los primos buscados.

Similarmente, si alguien quiere conocer la demostración de, digamos, el teorema del valor medio, es posible que le baste con algunas indicaciones sobre el argumento que lo justifica (el equivalente al esbozo de algoritmo), pero si quiere que un profesor se lo dé por bueno en un examen, tendrá que presentar una prueba lo suficientemente detallada. Ahora bien "lo suficientemente" es relativo. Siempre puede haber alguien que quiera entender la prueba que pregunte: cuando dices "es fácil ver que...", ¿eso cómo se ve?, cuando dices que aplicas el teorema de Bolzano, ¿eso qué es?

Si uno entiende realmente la demostración, podrá expandirla al máximo hasta el punto de que no sea necesario conocer ningún resultado previo para entenderla: si se usa el teorema de Bolzano, se incluye en la prueba la demostración del teorema de Bolzano, si éste usa otros a su vez, se incluye también su demostración, etc.

Ahora bien, no es posible demostrar cada cosa que se diga a partir de hechos previos, y éstos a su vez a partir de otros, etc. así ad infinitum. Tiene que haber algunas afirmaciones que se presenten en la prueba sin necesidad de una justificación previa. Esas afirmaciones son, o bien verdades lógicas, o bien los axiomas de la teoría de conjuntos que hemos presentado en el mensaje correspondiente.

Por "verdades lógicas" nos referimos a que si, por ejemplo, estamos hablando de un número real \( x \), en cualquier momento podemos distinguir dos casos: o bien \( x=0 \), o bien \( x\neq 0 \). Con ello estamos afirmando que \( x=0\lor x\neq 0 \), y esto es una verdad lógica, algo que tenemos que aceptar sin que pueda deducirse de los axiomas de la teoría de conjuntos. Así pues:

Toda demostración matemática puede expandirse hasta otra que no presente ninguna afirmación sin justificar que no sea una verdad lógica o uno de los axiomas de la teoría de conjuntos.

Esto sería el equivalente a un algoritmo de ordenador escrito en un lenguaje de programación.

Pero podemos ir más lejos. Si, por ejemplo, en un momento de la prueba, tenemos que \( x\in \mathbb R\land x>0 \) y de ahí concluimos que \( x>0 \) (para usar este hecho en otra parte del argumento), alguien puede preguntar: ¿cómo deduces que \( x>0 \) a partir de \( x\in \mathbb R\land x>0 \)?

Ningún matemático se tomaría en serio esa pregunta, sino que lo más que diría es que eso es obvio y que, si uno no lo entiende, mejor se dedica a otra cosa. No obstante, es posible expandir aún más una demostración "completa" desde un punto de vista matemático (es decir, en la que no falta justificar ningún paso matemático) para reducir todos los pasos puramente lógicos a dos posibilidades: o bien la introducción sin justificación de uno de los axiomas lógicos que hemos enumerado en su momento, o bien a aplicar una de dos reglas de inferencia: la que justifica escribir \( \beta \) si antes hemos justificado \( \alpha\rightarrow \beta \) y \( \alpha \) (el modus ponens) y la que justifica escribir \( \forall x\alpha \) si antes hemos justificado \( \alpha \) (para un \( x \) arbitrario). En conclusión:

Toda demostración matemática puede expandirse aún más hasta que todas las afirmaciones introducidas sin justificación sean axiomas lógicos o axiomas de la teoría de conjuntos y todas las demás se justifican únicamente por modus ponens o generalización.

Así, si en la prueba original se pasaba de \( x\in \mathbb R\land x>0 \) a \( x>0 \), en la prueba expandida habría varias (muchas) líneas intermedias que unirían una con la otra usando en cada paso o bien axiomas lógicos o bien modus ponens (justo en este caso, no sería necesaria la otra regla de inferencia, aunque eso es irrelevante).

Pero aún podemos ir más lejos. Todas las afirmaciones que aparecen en dicha prueba expandida podrían escribirse en términos exclusivamente de los signos \( \lnot, \rightarrow, \forall, =, \in \) y las variables. Para ello sólo hay que ir eliminando definiciones. Si partimos de \( x\in \mathbb R \), empezaremos aplicando la definición de \( \mathbb R \), y así, podríamos decir que \( x \) es un subconjunto no vacío de \( \mathbb Q \), distinto de \( \mathbb Q \), sin máximo y de modo que contiene a cualquier número menor que cualquiera de sus elementos. A su vez, habría que sustituir \( \mathbb Q \) por su definición a partir de \( \mathbb Z \), y la de \( \mathbb Z \) por su definición a partir de \( \mathbb N \), etc. Y cuando ya sólo quedaran signos lógicos como \( \land, \lor, \leftrightarrow \), éstos también pueden ser sustituidos por sus definiciones hasta que sólo queden los cinco indicados previamente. Así pues:

Toda demostración matemática puede expandirse al máximo hasta convertirla en una sucesión finita de fórmulas que no contengan más que los signos \( \lnot, \rightarrow, \forall, =, \in \) y variables, y en la que cada una de ellas sea un axioma lógico, u axioma de la teoría de conjuntos o una consecuencia de afirmaciones anteriores por modus ponens o generalización.

El resultado sería un monstruo indigerible para un humano (como una sucesión de ceros y unos equivalente a un código escrito en C), pero que un ordenador podría chequear sin dificultad para concluir si corresponde a una demostración correcta o no (igual que una sucesión de ceros y unos se le puede dar a un ordenador para que la ejecute de modo que hará lo que tiene que hacer si y sólo si corresponde a un programa correcto).

Esto es algo que nunca tendrá nadie necesidad de hacer, pero, para demostrar los teoremas de incompletitud, necesitamos comprender que, en teoría, es posible hacerlo, de modo que si una afirmación matemática es demostrable, podemos afirmar que existe un monstruo como el que acabamos de describir cuya última fórmula es precisamente la que queremos demostrar y, recíprocamente, si justificamos que, para una afirmación matemática dada, no puede existir un monstruo así (una demostración en el sentido técnico que hemos dado a la palabra), podemos asegurar que ningún matemático podrá demostrarla lo plantee como lo plantee.

Los mensajes precedentes sólo pretenden puntualizar los únicos aspectos de este proceso que serán necesarios más adelante. Concretamente, para entender la prueba de los teoremas de incompletitud hay que tener claro lo siguiente:

  • Lo dicho: que toda demostración matemática es correcta en la medida en que se puede reducir al concepto técnico de demostración que hemos dado.

  • Que los axiomas lógicos necesarios en las demostraciones matemáticas están perfectamente clasificados en seis familias de fórmulas.

    No necesitaremos los detalles sobre cómo son esas familias. Por ejemplo, la primera está formada por las fórmulas de tipo \( \alpha\rightarrow (\beta\rightarrow\alpha) \), pero basta tener claro que esta familia y otras cinco similares son suficientes para llevar adelante cualquier demostración matemática. La prueba de ello está en el hilo Lógica de primer orden, ya citado en su momento.

  • Que los axiomas conjuntistas necesarios en las demostraciones matemáticas están perfectamente inventariados, y son los expuestos en el mensaje correspondiente de este hilo.

    No es necesario conocer cómo se usan esos axiomas, sino únicamente saber que todo teorema matemático puede demostrarse a partir de ellos. La forma de justificar esto es estudiar la teoría de conjuntos ZFC y ver cómo en ella se demuestran todos los hechos básicos sobre conjuntos que los matemáticos dan por evidentes y cómo cualquier teorema matemático se justifica en último extremo a partir de estos hechos.

  • La definición de fórmula (de bajo nivel), es decir, la estructura última a la que puede reducirse cualquier enunciado matemático, que es muy simple: las fórmulas se construyen a partir de fórmulas atómicas (las de la forma \( =xy \) o \( \in xy \) mediante un número finito de pasos, consistentes en anteponer un negador a una fórmula anterior, anteponer un implicador a dos fórmulas anteriores o anteponer un \( \forall x \) a una fórmula anterior.

  • Que en la teoría de conjuntos (en Z es suficiente) se pueden definir los números naturales y demostrar que cumplen los axiomas de Peano, así como que es posible definir funciones por recurrencia (definiéndolas para un \( n \) supuesto que ya están definidas para los números anteriores). No necesitamos conocer las demostraciones de estos hechos. Basta con saber que son demostrables en ZFC (de hecho, en Z).

  • Que en Z se pueden definir también las sucesiones finitas de números naturales y las sucesiones finitas de sucesiones finitas de números naturales, y que se pueden definir los conceptos básicos asociados (longitud, yuxtaposición), etc. A su vez, para ello es necesario definir antes los conceptos de par desordenado, par ordenado y producto cartesiano.

    No es necesario conocer las definiciones y las demostraciones. Basta tener claro que todos los hechos básicos sobre sucesiones finitas son demostrables en Z, lo cual es un caso particular de que casi todo es demostrable en Z, y todo es demostrable en ZFC.

  • La definición explícita a bajo nivel de las fórmulas \( x=0, x=1, x=2 \), etc.

    No vamos a necesitar en ningún momento la definición de número natural, pero sí que, cuando un matemático escribe \( x=0 \), eso significa exactamente \( \forall u\,u\notin x \) (que \( x \) es el conjunto vacío), que cuando escribe \( x=1 \) eso hay que entenderlo como \( \forall u(u\in x\leftrightarrow u=0) \), donde a su vez \( u=0 \) se puede sustituir como acabamos de ver, que cuando escribe \( x=2 \) eso es lo mismo que \( \forall u(u\in x\leftrightarrow u=0\lor u=1) \), donde \( u=0 \) y \( u=1 \) pueden eliminarse según las definiciones precedentes, etc.

  • La definición explícita de las sucesiones finitas de fórmulas, es decir, que cuando decimos \( x=(3, 5, 1) \) eso es lo mismo que decir \( \forall u(u\in x\leftrightarrow u=(0, 3)\lor u=(1, 5)\lor u=(2,1)) \), donde a su vez \( u=(0, 3) \) puede reducirse mediante la definición de par ordenado que hemos visto, y así podríamos llegar a una fórmula a "bajo nivel" que no involucrara ni números naturales, ni pares ordenados ni nada más allá de los cinco signos básicos y las variables.

  • Lo mismo con sucesiones de sucesiones finitas de números naturales.

Eso es todo. Para seguir los mensajes siguientes, el lector debería releer los anteriores asegurándose de que estos puntos le han quedado claros (o preguntando lo que no acabe de ver claro).

25 Abril, 2018, 02:28 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Los conceptos y resultados que hemos introducido hasta ahora son hechos generales relacionados con la fundamentación de la matemática, pero no expresamente con los teoremas de incompletitud. Ahora daremos el primer paso hacia la prueba de estos teoremas.

Lo que vamos a hacer en este mensaje debe entenderse como si fuera un capítulo más de un libro de matemáticas, es decir, como unos resultados demostrables en ZFC (más precisamente, en Z). Del mismo modo que podemos tomar un libro que en el capítulo I defina el concepto de grupo y demuestre sus propiedades básicas, luego en el capítulo II defina el concepto de anillo y demuestre sus propiedades básicas, etc., aquí vamos  a definir un concepto técnicamente análogo a los de "grupo" o "anillo", sólo que es menos habitual verlo en un libro de matemáticas. Sin embargo, lo que vamos a hacer es lo usual en matemáticas, n más ni menos: dar unas definiciones y probar algunos resultados sobre ellas.

Empezamos definiendo los signos como los números naturales, es decir, cuando digamos "\( x \) es un signo" no estaremos diciendo ni más ni menos que "\( x \) es un número natural" (algo que tenemos definido en Z).

En particular, a los números naturales mayores o iguales que \( 5 \) los llamaremos variables. Así pues, el conjunto de las variables se define como

\( \mathcal V = \{x\in \mathbb N\mid 4\in x\}. \)

Recordemos que hemos definido

\( 0=\emptyset,\quad 1 = \{0\}, \quad 2 = \{0, 1\}, \quad 3 =\{0, 1, 2\},\quad\ldots \)

de modo que un número natural cumple \( 4\in x \) si y sólo si es \( x\geq 5 \).

Al número natural \( 0 \) lo llamaremos también negador, de modo que

\( \lnot = 0 = \emptyset. \)

Del mismo modo que escribimos \( \emptyset \) cuando pensamos en este objeto como conjunto y escribimos \( 0 \) cuando lo pensamos como número natural (aunque se trata en ambos casos del mismo objeto), a partir de ahora lo llamaremos \( \lnot \) cuando queramos considerarlo como signo. Similarmente, llamaremos \( \rightarrow \), \( \forall \), \( = \), \( \in \) a los números naturales \( 1, 2, 3, 4 \), y estas definiciones se resumen en la tabla siguiente:

\( \begin{array}{|c|c|c|c|c|c|c|c|c|}
\lnot&\rightarrow&\forall&=&\in&x_0&x_1&x_2&\cdots\\
\hline
0&1&2&3&4&5&6&7&\cdots
\end{array}
 \)

Aquí adoptamos también el convenio de representar por \( x_0 \) el número \( \color{red} 5 \), por \( x_1 \) el número \( 6 \), etc.

Ahora es fundamental tener presente en todo momento que estamos dando los mismos nombres a muchos pares de cosas distintas. Por ejemplo, si escribimos \( \in \in \mathbb N \), esto tiene sentido si entendemos que el primer \( \in \) es el número natural \( \in = 4 \), mientras que el segundo \( \in \) es el relator de pertenencia del lenguaje de la teoría de conjuntos. Igualmente, una afirmación tan surrealista como \( \forall \in = \) tiene sentido (y es verdadera) si la entendemos como \( 2\in 3 \).

Por razones obvias evitaremos expresiones como éstas que "dañan a la vista", y procuraremos que el contexto deje siempre claro cuándo un signo lógico es un signo lógico "de verdad" y cuando es uno de los nombres aparentemente caprichosos que hemos dado a los números naturales.

A los elementos de \( S^1 \), es decir, las sucesiones finitas de números naturales, las llamaremos también cadenas de signos. Por ejemplo, con los convenios adoptados la sucesión \( (4, 5, 6) \) puede representarse también como \( (\in, x_0, x_1) \), y en la práctica la representaremos también como \( (x_0\in x_1) \).

Más en general, llamaremos fórmulas atómicas a las cadenas de signos de longitud \( 3 \) de la forma \( (3, m, n) \) o \( (4, m, n) \), donde \( m, n \) son números naturales \( \geq 5 \) (es decir, variables). Equivalentemente, las fórmulas atómicas son las sucesiones de la forma

\( (=,x_i, x_j), \qquad (\in, x_i, x_j), \)

y en la práctica las representaremos por \( (x_i=x_j) \), \( (x_i\in x_j) \).

Una sucesión generadora de fórmulas es un elemento de \( S^2 \) (una sucesión finita de cadenas de signos) tal que cada término de la sucesión esté en uno de los casos siguientes:

  • Sea una fórmula atómica.
  • Sea de la forma \( \lnot*\alpha \), donde \( \alpha \) es un término anterior de la sucesión.
  • Sea de la forma \( \rightarrow *\alpha*\beta \), donde \( \alpha \) y \( \beta \) son términos anteriores de la sucesión
  • Sea de la forma \( \forall * x_i*\alpha \), donde \( x_i \) es una variable y \( \alpha \) es un término anterior de la sucesión.

Llamaremos fórmulas a los elementos de \( S^1 \) que forman parte de una sucesión generadora de fórmulas y llamaremos \( \mathcal F \) al conjunto de todas las fórmulas.

En otras palabras, una fórmula es una sucesión finita de números naturales que puede construirse a partir de fórmulas atómicas mediante un número finito de aplicaciones de tres procesos:

  • Anteponer el negador a una fórmula previamente construida,
  • Anteponer el implicador a dos fórmulas previamente construidas,
  • Anteponer el cuantificador y una variable a una fórmula previamente construida.

En particular, podemos definir las operaciones

\( \lnot:\mathcal F\longrightarrow \mathcal F\qquad \rightarrow: \mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \forall: \mathcal V\times\mathcal F\longrightarrow \mathcal F
 \)
dadas por

\( \lnot \alpha = \lnot*\alpha,\qquad \alpha\rightarrow\beta = \rightarrow*\alpha*\beta,\qquad \forall x_i\alpha=\forall*x_i*\alpha.
 \)

Más aún, también podemos definir operaciones

\( \lor:\mathcal F\times\mathcal F\longrightarrow\mathcal F\quad \land:\mathcal F\times\mathcal F\longrightarrow\mathcal F,\quad \leftrightarrow:\mathcal F\times\mathcal F\longrightarrow\mathcal F,\quad \exists:\mathcal V\times\mathcal F\longrightarrow \mathcal F
 \)
dadas por

\( \alpha\lor\beta = \lnot\alpha\rightarrow \beta,\quad \alpha\land \beta=\lnot(\lnot\alpha\lor\lnot\beta),\quad \alpha\rightarrow\beta=(\alpha\rightarrow\beta)\land (\beta\rightarrow\alpha),\quad \exists x\alpha =\lnot\forall\lnot\alpha.
 \)

Por ejemplo, la sucesión

\( (2, 7, 1,4,7,5,4,7,6) \)

es una fórmula. Esto se ve más claramente si la escribimos así:

\( (\forall, x_2,\rightarrow, \in,x_2,x_0,\in,x_2,x_1) \),

 y más claramente aún si la escribimos así:

\( (\forall x_2(x_2\in x_0\rightarrow x_2\in x_1)) \).

La sucesión de fórmulas que la genera es

\( ((x_2\in x_0), (x_2\in x_1), (x_2\in x_0\rightarrow x_2\in x_1),(\forall x_2(x_2\in x_0\rightarrow x_2\in x_1)). \)

Similarmente, con las definiciones dadas tenemos que

\( (x_0=x_1\lor x_0=x_2) = (\lnot x_0=x_1\rightarrow x_0=x_2) = (\rightarrow, \lnot, =,x_0, x_1, =, x_0, x_2)=(1, 0, 3, 5, 6, 3, 5, 7). \)

El teorema que hemos probado en la respuesta #1 puede concebirse ahora como una prueba en Z del mismo resultado, pero entendido ahora como un resultado sobre las fórmulas definidas en Z en lugar de sobre fórmulas metamatemáticas.

Del mismo modo que hemos "calcado" en Z (formalizado, si somos más finos) la definición de fórmula, podemos calcar la definición de deducción. Para ello, en primer lugar tenemos que definir los axiomas lógicos. Por ejemplo, podemos definir

\( A_1=\{\gamma\in \mathcal F\mid \exists \alpha\beta\in\mathcal F\, \gamma = (\alpha\rightarrow(\beta\rightarrow\alpha))\},
 \)

e igualmente podemos definir los conjuntos de axiomas \( A_2,\ldots, A_6 \), y el conjunto \( A\subset \mathcal F  \) de axiomas como la unión de estos seis conjuntos.

Con esto ya podemos definir una deducción a partir de un conjunto \( \Gamma\subset \mathcal F \) como un elemento de \( S^2 \) tal que cada uno de sus términos cumpla una de las condiciones siguientes:

  • Es un elemento de \( \Gamma \).
  • Es un elemento de \( A \).
  • Es de la forma \( \alpha \), de modo que entre las fórmulas anteriores de la sucesión se encuentren \( \beta\rightarrow \alpha \) y \( \beta \).
  • Es de la forma \( \forall x \alpha \), donde \( \alpha \) es una fórmula anterior de la sucesión.

Diremos que una fórmula \( \alpha \) es una consecuencia lógica de \( \Gamma\subset \mathcal F \), y lo representaremos por \( \Gamma\vdash \alpha \), si \( \alpha \) es el último término de una deducción a partir de \( \Gamma \).

Así pues, ahora tenemos que distinguir entre, por ejemplo, el axioma de extensionalidad

\( \forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y) \)

en el sentido del mensaje número 4, es decir, como una afirmación del lenguaje de la teoría de conjuntos, que no es un conjunto, sino una de las propiedades que postulamos de los conjuntos, y, por otra parte, el axioma de extensionalidad definido como

\( \mbox{Ext} = (\forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y))\in \mathcal F, \)

que es una sucesión de números naturales cuya existencia se demuestra a partir de los axiomas de Z. Notemos que no tiene sentido preguntarse si existe el axioma de extensionalidad (el "de verdad"), sino que existe desde el momento en que sabemos escribirlo y ya está, mientras que sin los axiomas adecuados no podríamos probar que existe la sucesión de números naturales que estamos llamando axioma de extensionalidad ("de mentira").

Igualmente podemos definir en Z los demás axiomas de Z. El único más delicado es el de especificación, que no es una fórmula, sino un conjunto de fórmulas:

\( \mbox{Esp}=\{\gamma\in \mathcal F\mid \exists xuz\alpha(x, u, z\in \mathbb N\land x, u, z\geq 5\land \alpha\in \mathcal F\land x\neq u\land x\neq z\land u\neq z\land z\notin\mbox{Im}\alpha\land \gamma =(\forall x\exists z\forall u(u\in z\leftrightarrow u\in x\land \alpha)))\},
 \)

donde \( \mbox{Im} \) representa la imagen de \( \alpha \), el conjunto de los signos que aparecen en la sucesión \( \alpha \). Definimos \( Z \) como la unión de Exp y el conjunto de los seis axiomas restantes, e igualmente podemos definir ZF y ZFC añadiendo (las versiones definidas de) los axiomas que faltan en cada caso.

De este modo, hemos definido en Z lo que significa que una fórmula \( \alpha\in \mathcal F \) sea un teorema de Z (o de ZF o de ZFC).

26 Abril, 2018, 01:19 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Consideremos una fórmula como

\( \exists y\forall x\,x\notin y \)

Según lo visto hasta ahora, esto puede interpretarse de dos formas conceptualmente muy distintas:

  • Puede entenderse que con esto estamos haciendo referencia a uno de los axiomas de Z, el axioma del conjunto vacío, que es una afirmación, una cadena de signos que usamos como parte de los razonamientos que hacemos en Z.
  • Pero también puede entenderse como un conjunto definido en Z, concretamente, como una sucesión finita de números naturales. Si, concretando algo que normalmente es irrelevante, convenimos que por \( x,y \) nos referimos específicamente a las variables \( x_0, x_1 \), la fórmula anterior puede entenderse como la sucesión
    \( (\lnot,\forall, x_1,\lnot,\forall, x_0, \lnot, \in,x_0,x_1)=(0,2,6,0,2,5,0,5,6)\in S^1 \)

En este hilo necesitamos considerar ciertas relaciones entre los objetos metamatemáticos como la fórmula \( \exists y\forall x\,x\notin y \) y los objetos definidos en Z como la fórmula \( \exists y\forall x\,x\notin y \). Y como llamar igual a dos cosas cuya relación queremos estudiar ya es empezar con mal pie, a partir de aquí las distinguiremos representando por \( \exists y\forall x\,x\notin y \) a la fórmula metamatemática y por \( \ulcorner\exists y\forall x\,x\notin y\urcorner \) a la sucesión definida en Z.

Con esto estamos introduciendo los llamados ángulos de Quine, que usaremos para señalar que una expresión que hasta ahora podía interpretarse como metamatemática o como un concepto definido en Z se refiere realmente al concepto definido en Z.

Por ejemplo, ahora \( \lnot \) será el negador metamatemático, el que usamos para enunciar teoremas, mientras que \( \ulcorner\lnot\urcorner \) será el negador definido en Z, concretamente, \( \ulcorner\lnot\urcorner=0=\emptyset \).

Para cualquier sucesión finita metamatemática de números naturales, como \( (5,1,3) \), podemos definir en Z la sucesión \( \ulcorner(5, 1, 3)\urcorner \) mediante la fórmula

\( x=\ulcorner(5,1,7)\urcorner\equiv \forall u(u\in x\leftrightarrow u=(0, 5)\lor u=(1, 1)\lor u=(2,7) \),

que afirma que \( x \) es una función de dominio (longitud) \( 3=(0, 1, 2) \) determinada por que \( x(0)=5 \), \( x(1)=1 \), \( x(2)=7 \).

En general, cada sucesión finita metamatemática \( \zeta \) de números naturales puede ser formalizada igualmente mediante una fórmula \( x=\ulcorner\zeta\urcorner \) en el lenguaje de Z.

Por aumentar en la medida de lo posible el paralelismo entre los conceptos metamatemáticos y sus formalizaciones, podemos considerar que las fórmulas metamatemáticas son sucesiones finitas de números naturales metamatemáticos, es decir, podemos considerar que el signo \( \lnot \) que usamos como negador no es sino una forma de referirnos al número natural \( 0 \), e igualmente con los demás signos, con lo que podemos escribir que

\( \exists y\forall x\,x\notin y\equiv (0,2,6,0,2,5,0,5,6) \)

Paralemalmente al hecho de que, por definición.

\( \ulcorner\exists y\forall x\,x\notin y\urcorner=\ulcorner(0,2,6,0,2,5,0,5,6)\urcorner \).

Así, para toda fórmula (metamatemática) \( \alpha \), vista como sucesión finita de números naturales, tenemos definida su formalización \( \ulcorner\alpha\urcorner \).

Más aún, si \( D\equiv (\zeta_0,\ldots, \zeta_n) \) es una sucesión finita de sucesiones finitas de números naturales (por ejemplo, esto sucede si \( D \) es una demostración en Z, o en ZFC), podemos definir igualmente su formalización como

\( x=\ulcorner D\urcorner \equiv \forall u(u\in x\leftrightarrow u=(0, \ulcorner\zeta_0\urcorner)\lor\cdots\lor u = (n,\ulcorner\zeta_n\urcorner)) \).

que es una función cuyo dominio es el número natural \( n+1 \) y que cumple \( x(0)=\ulcorner\zeta_0\urcorner \), etc.

En el próximo mensaje justificaremos los hechos siguientes:

  • Si \( \alpha \) es una fórmula metamatemática, entonces en Z se puede demostrar que \( \ulcorner\alpha\urcorner\in \mathcal F \).
  • Si \( \alpha \) es una sucesión finita de números naturales que no es una fórmula, entonces en Z se puede demostrar que \( \ulcorner\alpha\urcorner\notin \mathcal F \).
  • Si \( D \) es una demostración metamatemática (en Z, ZF, ZFC, etc.) de una fórmula \( \alpha \), entonces en Z se puede demostrar que \( \ulcorner D\urcorner \) es una demostración (en Z, ZF, ZFC, etc.) de \( \ulcorner\alpha\urcorner \).
  • Si \( D \) es una sucesión metamatemática de sucesiones finitas de números naturales que no es una demostración (en Z, ZF, ZFC, etc.) de una fórmula \( \alpha \), entonces en Z se puede demostrar que \( \ulcorner D\urcorner \) no es una demostración (en Z, ZF, ZFC, etc.) de \( \ulcorner\alpha\urcorner \).

En realidad sería perfectamente razonable que el lector se saltara el próximo mensaje dado estas cuatro afirmaciones son evidentes. Es como si nos planteamos lo siguiente:

¿Es posible escribir un programa de ordenador (en cualquier lenguaje de programación usual) de modo que al ejecutarlo nos pida una sucesión finita de números naturales y nos la devuelva ordenada de menor a mayor?

Cualquiera que tenga un conocimiento razonable de lo que es un ordenador y lo que es capaz de hacer, incluso si no conoce ningún lenguaje de programación y, por lo tanto, no sería capaz de diseñar por sí mismo ese programa, comprenderá sin lugar a dudas que un ordenador puede hacer eso, aunque no sepa explícitamente cómo pedírselo. Incluso si alguien tiene conocimientos de programación, puede que necesite pararse un poco a pensar cómo diseñar ese programa, y que necesita algún tiempo para escribir el código adecuado, lo cual no afecta en nada a que, desde el primer momento, sabrá que escribir dicho código es sólo cuestión de ponerse a ello, pero que bajo ningún concepto es imaginable que dicho código no pueda escribirse concretamente si uno se pone a ello.

Igualmente, es indudable que si a un matemático se le da una sucesión finita de números naturales, va a ser capaz de estudiarla y determinar si corresponde o no a una fórmula. Es imposible estar ante una sucesión de números naturales (prescindiendo de casos prácticamente inabordables, como sucesiones de longitud mayor que el número de electrones del universo, pero también tendríamos problemas si le diéramos a un ordenador una sucesión de esa longitud para que la ordene) y que sea imposible saber si es o no una fórmula. Por lo tanto, cualquiera que tenga una idea clara de lo que es Z sabe que si un matemático siempre puede demostrar si una sucesión de números que le dan es o no una fórmula, dicha demostración se puede llevar a cabo en Z. Otra cosa es conocer los detalles de esa demostración, que es el equivalente a escribir el código concreto que le dice a un ordenador cómo ordenar números. Para ello hace falta tener cierta familiaridad sobre las peculiaridades de la lógica de Z, análogas a las peculiaridades de tal o cual lenguaje de programación.

Lo mismo sucede si a un matemático le dan una sucesión finita de fórmulas y le preguntan si constituyen una demostración o no de la última de ellas. Siempre es posible saber (demostrar) si la respuesta es sí o no. Ojo: en la práctica esto no es cierto, pues si uno coge la demostración del Último Teorema de Fermat y le preguntan si es correcta o tiene algún fallo, la respuesta más probable será "no tengo ni idea, no entiendo nada", pero es que no hablamos de demostraciones presentadas así, sino que nos estamos planteando el caso de que a un matemático le presenten una demostración escrita a "bajo nivel", de modo que lo único que hay que comprobar es si cada una de las fórmulas es un axioma lógico (cosa que siempre se puede determinar sin saber nada de curvas modulares) si es un axioma de ZFC (cosa que siempre se puede determinar sin saber nada de curvas elípticas) o si se deduce de fórmulas anteriores por modus ponens o generalización (para lo cual no hace falta conocer la conjetura de Shimura-Taniyama).

En resumen: cuando una demostración se presenta a bajo nivel, es un monstruo que nadie es capaz de entender (ni el mismo Wiles entendería nada de su demostración escrita a bajo nivel) pero, a cambio, no es necesario entender nada para comprobar si es una demostración correcta o no. Es como el código último en el que se transforma un código escrito en un lenguaje de programación para que lo lea un ordenador: una sucesión de ceros y uno que no es capaz de entender ni el programador, pero que un ordenador puede ejecutar sin problemas. (También podría ejecutarla a ciegas cualquier otro, con un papel y un lápiz, pero sin entender qué está haciendo con ello.)

Ante la posibilidad de que esto convenza al lector de que no lea el mensaje siguiente, incluimos aquí unas observaciones más que sí que necesitaremos después. Todo lo que digamos en el próximo mensaje será prescindible para todos aquellos lectores que no necesiten poner el dedo en la llaga para convencerse de que en Z se pueden demostrar todas las cosas que los cuatro resultados anteriores afirman que se pueden demostrar en Z. (Ojo: notemos que no se trata de probar cuatro teoremas en Z, sino de probar que las infinitas cosas que los cuatro enunciados anteriores afirman que se pueden demostrar en Z son realmente demostrables en Z.)

Lo último que necesitamos señalar en este mensaje es la conveniencia de usar ángulos de Quine para distinguir los números naturales metamatemáticos de los definidos en Z, es decir, que conviene representar por \( \ulcorner0\urcorner, \ulcorner1\urcorner, \ulcorner2\urcorner, \) etc. lo que hasta ahora, al trabajar en Z, representábamos simplemente por \( 0, 1, 2,  \) etc. Por ejemplo, en la definición de \( \ulcorner D\urcorner \), hubiera sido más claro escribir:

\( x=\ulcorner D\urcorner \equiv \forall u(u\in x\leftrightarrow u=(\ulcorner0\urcorner, \ulcorner\zeta_0\urcorner)\lor\cdots\lor u = (\ulcorner n\urcorner,\ulcorner\zeta_n\urcorner)) \)

para dejar claro que la \( n \) que aparece al final entre ángulos de Quine no es una variable, como lo son \( x, u \), sino que en \( \ulcorner n\urcorner \) no hay ninguna variable libre.

Quizá esto se vea más claro si comparamos las fórmulas \( x=n \) y \( x=\ulcorner n\urcorner\ \). La primera es una fórmula con exactamente dos variables, y las dos están libres (no están afectadas por cuantificadores), mientras que \( x=\ulcorner n\urcorner\ \) es una fórmula con muchas variables, de las cuales sólo \( x \) está libre. Eso se ve claramente si consideramos casos concretos:

\( x=\ulcorner 0\urcorner\equiv \forall u\,u\notin x \)

es una fórmula con dos variables, de las cuales sólo $x$ está libre.  Igualmente,

\( x=\ulcorner 1\urcorner\equiv \forall u(u\in x\leftrightarrow u=\ulcorner 0\urcorner)\equiv \forall y(u\in x\leftrightarrow \forall v\,v\notin u)) \)

es una fórmula con tres variables, de las cuales sólo \( x \) está libre. Igualmente podemos comprobar que \( x=\ulcorner 2\urcorner, x=\ulcorner 3\urcorner \), etc.\ son siempre fórmulas con \( x \) como única variable libre, y en este mismo sentido podemos decir que, sea cual sea el número \( n \) (sea \( 0, 1, 2, \ldots \)) la fórmula \( x= \ulcorner n\urcorner \) sólo tiene a \( x \) como variable libre, al contrario que \( x=n \), si ahí entendemos que \( x \) y \( n \) son ambas variables del lenguaje de la teoría de conjuntos.


26 Abril, 2018, 11:31 pm
Respuesta #8

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Como explicamos en el mensaje anterior, este mensaje sólo necesitan leerlo los lectores tomistas, no en el sentido de ser seguidores de santo Tomás de Aquino, sino de santo Tomás Apóstol, el que tuvo que poner el dedo en la llaga.

Vamos a explicar cómo se demuestra en Z que las fórmulas y las demostraciones son fórmulas y demostraciones, y lo que no son fórmulas ni demostraciones no son fórmulas ni demostraciones, es decir, las cuatro afirmaciones que enunciamos en el mensaje anterior. Empecemos con algunos hechos elementales sobre números naturales:

  • Para cada número natural \( n \), en Z se prueba que \( \ulcorner  n+1\urcorner=\ulcorner  n\urcorner' \).

    Con esto estamos afirmando que en Z se demuestra que \( \ulcorner  1\urcorner \) es el siguiente de \( \ulcorner  0\urcorner \), que \( \ulcorner  2\urcorner \) es el siguiente de \( \ulcorner  1\urcorner \), etc.

    Cualquier matemático zanjaría la cuestión diciendo "esto es obvio", pero he aquí la prueba para tomistas:

    Demostración
    Casi podríamos decir que esto se cumple por definición, pero si nos atenemos estrictamente a las definiciones que hemos dado, sucede que

    \( x=\ulcorner  n+1\urcorner\equiv \forall u(u\in x\leftrightarrow u=\ulcorner  0\urcorner\lor \cdots \lor u=\ulcorner  n\urcorner)
     \)
    y, si \( n>0 \),

    \( x=\ulcorner  n\urcorner\equiv \forall u(u\in x\leftrightarrow u=\ulcorner  0\urcorner\lor \cdots \lor u=\ulcorner  n-1\urcorner),
     \)
    y de ambas definiciones se deduce lógicamente que

    \( x=\ulcorner  n+1\urcorner\leftrightarrow \forall u(u\in x\leftrightarrow u\in \ulcorner  n\urcorner\lor u=\ulcorner  n\urcorner)\leftrightarrow x = \ulcorner  n\urcorner',
     \)
    donde hemos usado además la definición de \( x=y' \). El caso \( n=0 \) es una ligera variante del caso \( n>0 \).
    [cerrar]

  • Si \( m=n \) entonces en Z se puede probar \( \ulcorner  m\urcorner=\ulcorner  n\urcorner \).

    Esto, aun siendo obvio, es ligeramente menos obvio que lo que parece, porque, técnicamente, debemos recordar que \( \ulcorner m\urcorner \) no es nada en el lenguaje de Z, sino que lo que hemos definido realmente es \( x=\ulcorner m\urcorner \). Teniendo esto en cuenta, lo que hay que probar no es una igualdad, sino la fórmula

    \( \forall xy(x=\ulcorner m\urcorner\land y=\ulcorner m\urcorner\rightarrow x=y) \),

    donde las dos primeras "igualdades" no son igualdades, sino las fórmulas que hemos definido en su momento.

    Prueba para tomistas
    Recordamos que, por definición, en el caso \( m>0 \),

    \( x=\ulcorner m\urcorner \equiv \forall u(u\in x\leftrightarrow u=\ulcorner0\urcorner\lor \cdots \lor \ulcorner m-1\urcorner) \)

    Por lo tanto, la hipótesis \( x=\ulcorner m\urcorner\land y=\ulcorner m\urcorner \) implica que

    \( \forall u(u\in x\leftrightarrow u\in y) \),

    y el axioma de extensionalidad implica que \( x=y \).
    [cerrar]

  • Si \( m\neq n \), entonces en Z se puede probar \( \ulcorner  m\urcorner\neq \ulcorner  n\urcorner \).

    Ahora se trata de comprobar que en Z puede probarse que \( \ulcorner  3\urcorner\neq \ulcorner  7\urcorner \), que \( \ulcorner  5\urcorner\neq \ulcorner  2\urcorner \), etc. Estos infinitos teoremas se siguen todos ellos de los axiomas de Peano.

    Prueba para tomistas
    Por ejemplo, para probar que \( \ulcorner  5\urcorner\neq \ulcorner  2\urcorner \) suponemos por reducción al absurdo que \( \ulcorner  5\urcorner=\ulcorner  2\urcorner \), y entonces \( \ulcorner  4\urcorner'=\ulcorner  1\urcorner' \), luego, por el cuarto axioma de Peano, \( \ulcorner  4\urcorner=\ulcorner  1\urcorner \), luego \( \ulcorner  3\urcorner'=\ulcorner  0\urcorner' \), luego \( \ulcorner  3\urcorner=\ulcorner  0\urcorner \), luego \( \ulcorner  2\urcorner'=\ulcorner  0\urcorner \), y esto contradice al segundo axioma. Es claro que podemos construir una demostración análoga para cualquier par de números naturales distintos entre sí de los que partamos.
    [cerrar]

Pasamos ahora a considerar las formalizaciones de las sucesiones finitas de números naturales. Observemos en primer lugar que si una sucesión \( \zeta \) tiene longitud \( n \), en Z se demuestra que \( \ulcorner \zeta\urcorner\in S^1 \) y que su longitud (definida como el dominio de la sucesión)es \( \ulcorner  n\urcorner \). Por ejemplo, para la sucesión \( (7, 1, 1) \), tenemos que

\( \ulcorner(7,1,1)\urcorner = \{(\ulcorner,0\urcorner, \ulcorner7\urcorner), (\ulcorner,1\urcorner, \ulcorner1\urcorner), (\ulcorner,2\urcorner, \ulcorner1\urcorner)\},
 \)

y es claro que este conjunto cumple la definición conjuntista de aplicación con dominio \( \ulcorner3\urcorner=\{\ulcorner0\urcorner,\ulcorner1\urcorner,\ulcorner2\urcorner\} \) e imagen en \( \mathbb N \), y eso es precisamente lo que significa ser un elemento de \( S^1 \) de longitud \( \ulcorner3\urcorner \). Es claro que podemos razonar igual con cualquier sucesión finita dada.

  • Si \( \zeta_1 =\zeta_0*n \), en Z se demuestra que \( \ulcorner  \zeta_1\urcorner=\ulcorner  \zeta_0\urcorner*\ulcorner  n\urcorner \).

    Nuevamente estamos ante un hecho obvio cuya demostración es un tecnicismo irrelevante:

    Demostración
    Si \( \zeta_0=(k_0,\ldots, k_{m-1}) \) tiene longitud \( m \), por definición de yuxtaposición,

    \( \ulcorner  \zeta_0\urcorner*\ulcorner  n\urcorner=\ulcorner  \zeta_0\urcorner\cup\{(\ell(\ulcorner  \zeta_0\urcorner), \ulcorner n\urcorner)\},
     \)

    pero podemos probar que \( \ell(\ulcorner\zeta_0\urcorner)=\ulcorner m\urcorner \) y, por definición de unión,

    \( \forall u(u\in \ulcorner  \zeta_0\urcorner*\ulcorner  n\urcorner\leftrightarrow u\in \ulcorner\zeta_0\urcorner\lor u = (\ulcorner m\urcorner,\ulcorner n\urcorner,)).
     \)

    Por definición de \( \ulcorner \zeta_0\urcorner \),

    \( \forall u(u\in \ulcorner  \zeta_0\urcorner*\ulcorner  n\urcorner\leftrightarrow u=(\ulcorner 0\urcorner, \ulcorner k_0\urcorner)\lor \cdots \lor u= (\ulcorner m-1\urcorner, \ulcorner k_{m-1}\urcorner)\lor u = (\ulcorner m\urcorner, \ulcorner n\urcorner))
     \)

    y por definición de \( \ulcorner\zeta_1\urcorner \)

    \( \forall u(u\in \ulcorner  \zeta_0\urcorner*\ulcorner  n\urcorner\leftrightarrow u\in \ulcorner\zeta_1\urcorner), \)

    luego, por el axioma de extensionalidad, \( \ulcorner  \zeta_1\urcorner=\ulcorner  \zeta_0\urcorner*\ulcorner  n\urcorner \).
    [cerrar]

  • Si \( \zeta_1=\zeta_2*\zeta_3 \), en Z se demuestra que \( \ulcorner  \zeta_1\urcorner=\ulcorner  \zeta_2\urcorner*\ulcorner  \zeta_3\urcorner \).

    Basta tener en cuenta el apartado anterior y recordar el cálculo explícito de

    \( \ulcorner(3, 5, 1)\urcorner*\ulcorner(2, 9)\urcorner = \ulcorner(3,5,1,2,9)\urcorner \)

    que mostramos al final de la respuesta #4. Es obvio que el mismo procedimiento puede usarse para calcular en Z cualquier yuxtaposición de sucesiones finitas de números naturales.

  • Si \( \zeta_1=\zeta_2 \), en Z se demuestra que \( \ulcorner  \zeta_1\urcorner=\ulcorner  \zeta_2\urcorner \).

    La prueba es análoga a la que hemos visto para la igualdad de números naturales.

  • Si \( \zeta_1\neq \zeta_2 \), en Z se demuestra que \( \ulcorner  \zeta_1\urcorner\neq \ulcorner  \zeta_2\urcorner \).

    Demostración
    Si \( \zeta_1 \) y \( \zeta_2 \) tienen longitudes distintas, en Z se prueba que \( \ulcorner  \zeta_1\urcorner \) y \( \ulcorner  \zeta_2\urcorner \) tienen longitudes distintas, luego son sucesiones distintas.
    Si ambas tienen la misma longitud, tiene que existir un \( i \) menor que dicha longitud tal que \( (\zeta_1)_i\neq (\zeta_2)_i \), pero de la propia definición de \( x=\ulcorner  \zeta\urcorner \) se sigue entonces que \( (\ulcorner  i\urcorner,\ulcorner  (\zeta_1)_i\urcorner)\in \ulcorner  \zeta_1\urcorner \), mientras que \( (\ulcorner  i\urcorner,\ulcorner  (\zeta_1)_i\urcorner)\notin \ulcorner  \zeta_2\urcorner \), luego ambas sucesiones son distintas.
    [cerrar]


Ahora ya podemos probar dos de los enunciados que presentamos en el mensaje anterior:

Si \( \alpha \) es una fórmula, entonces en Z se demuestra que \( \ulcorner \alpha\urcorner\in \mathcal F \), mientras que si \( \alpha \) es una sucesión finita de números naturales que no es una fórmula, entonces en Z se demuestra que \( \ulcorner \alpha\urcorner\notin \mathcal F \).

Si la prueba es algo más sofisticada que la de los resultados precedentes (y siguientes) no es porque sea menos rutinaria, sino porque la definición de fórmula es más sofisticada y requiere distinguir muchos casos.

Demostración
Probaremos algo más general: si \( \zeta \) es cualquier sucesión finita de números naturales, o bien es una yuxtaposición de \( n \) fórmulas, y en tal caso en Z se puede probar que \( \ulcorner \zeta\urcorner \) es una yuxtaposición de \( \ulcorner n\urcorner \) fórmulas, o bien no lo es, y en Z se puede probar que \( \ulcorner \zeta\urcorner \) no lo es.

Razonamos por inducción sobre la longitud de \( \zeta \). Si dicha longitud es menor que \( 3 \), entonces \( \zeta \) no puede ser una yuxtaposición de fórmulas (pues la menor fórmula tiene tres signos) y en Z se prueba igualmente que las fórmulas tienen al menos tres signos, luego también se puede probar que \( \ulcorner \zeta\urcorner \) no es una yuxtaposición de fórmulas.

Supuesto que \( \zeta \) tiene al menos tres signos, si el primero es una variable, entonces \( \zeta \) no es una yuxtaposición de fórmulas, pues una fórmula no puede empezar con una variable, y en Z se prueba también que las fórmulas no empiezan por variables, luego podemos concluir que \( \ulcorner \zeta\urcorner\notin \mathcal F \).

Si \( \zeta \) empieza por un relator (\( = \) o \( \in \)), entonces, para que sea una sucesión de fórmulas, la primera de ellas debe ser atómica, y los dos signos siguientes tienen que ser variables. Si no es así, en Z se demuestra también que alguno de los dos signos siguientes no es una variable (no es un número mayor o igual que \( \ulcorner5\urcorner \)), y de ahí se deduce que \( \ulcorner \zeta\urcorner \) no puede ser una yuxtaposición de fórmulas. En caso contrario, \( \zeta \equiv Rx_ix_j*\zeta' \), donde \( R \) es un relator y \( \zeta' \) puede ser la sucesión vacía.

Hemos probado que las fórmulas de una yuxtaposición de fórmulas están unívocamente determinadas, luego si \( \zeta \) es una yuxtaposición de \( n \) fórmulas, \( \zeta' \) tiene que ser una yuxtaposición de \( n-1 \) fórmulas, luego, por hipótesis de inducción, en Z se prueba que \( \ulcorner \zeta'\urcorner \) es una yuxtaposición de \( n-1 \) fórmulas (tal vez \( 0 \), si es la sucesión vacía), luego también que \( \ulcorner \zeta\urcorner=\ulcorner Rx_ix_j\urcorner*\ulcorner \zeta'\urcorner \) es una yuxtaposición de \( \ulcorner n\urcorner \) fórmulas.

Recíprocamente, si \( \zeta \) no es una yuxtaposición de fórmulas, entonces \( \zeta'  \)tampoco puede serlo, luego en Z se prueba que \( \ulcorner \zeta'\urcorner \) no es una yuxtaposición de fórmulas, luego \( \ulcorner \zeta\urcorner=\ulcorner Rx_ix_j\urcorner*\ulcorner \zeta'\urcorner \) tampoco lo es, pues si lo fuera, la primera sería necesariamente \( \ulcorner Rx_ix_j\urcorner \), luego \( \ulcorner \zeta'\urcorner \) sería la yuxtaposición de las restantes.

Si \( \zeta\equiv \lnot*\zeta' \) y es una yuxtaposición de \( n \) fórmulas, entonces \( \zeta' \) también es una yuxtaposición de \( n \) fórmulas, y basta aplicar la hipótesis de inducción. Si \( \zeta \) no es una yuxtaposición de fórmulas, entonces \( \zeta' \) tampoco puede serlo, y concluimos análogamente.

Si \( \zeta\equiv \rightarrow*\zeta' \) y es una yuxtaposición de \( n \) fórmulas, entonces \( \zeta' \) es una yuxtaposición de \( n+1 \) fórmulas, y basta aplicar la hipótesis de inducción. Si \( \zeta \) no es una yuxtaposición de fórmulas, entonces \( \zeta' \) tampoco lo es o bien es una única fórmula, y se concluye fácilmente.

Si \( \zeta \) empieza por un \( \forall \), o bien el signo siguiente no es una variable, en cuyo caso \( \zeta \) no es una sucesión de fórmulas y en Z se prueba lo mismo, o bien \( \zeta\equiv \forall x\zeta' \). En este caso, si \( \zeta \) es una yuxtaposición de \( n \) fórmulas, lo mismo vale para \( \zeta' \) y basta aplicar la hipótesis de inducción. Recíprocamente, si \( \zeta \) no es una yuxtaposición de fórmulas, tampoco puede serlo \( \zeta' \) y se concluye análogamente.
[cerrar]

Pasamos ahora a ocuparnos de la formalización de las demostraciones:

  • Si \( \zeta \) es un axioma lógico de tipo 1), entonces en Z se demuestra que \( \ulcorner \zeta \urcorner\in A_1 \), mientras que si una fórmula \( \zeta \) no es un axioma de tipo 1), en Z se demuestra que \( \ulcorner \zeta \urcorner\notin A_1 \).

    Recordemos que los axiomas de tipo 1 son los de la forma

    \( \alpha\rightarrow (\beta\rightarrow \alpha)\equiv \rightarrow \alpha\rightarrow\beta\alpha. \)


    Se trata de probar que si en Z tenemos una sucesión finita de números naturales dada explícitamente (es decir, definida como la sucesión cuyo primer signo es tal, su segundo signo es cual, etc.), si responde a este esquema podemos demostrar que así es, y si no responde a este esquema podemos probar también que así es.

    Cualquier matemático diría que es obvio que es capaz de distinguir si una fórmula dada responde o no a este esquema, pero vamos a detallar el argumento por si alguien duda de que "distinguir" en este caso equivale a "demostrar":

    Demostración
    Miramos el primer signo de \( \zeta \). Si no es el implicador, entonces \( \zeta \) no es un axioma de tipo 1, y en Z se demuestra que el primer signo de \( \ulcorner \zeta\urcorner \) no es el implicador, lo que, por definición de \( A_1 \), implica que \( \ulcorner \zeta\urcorner\notin A_1 \).

    Supongamos que el primer signo de \( \zeta \) es un implicador, con lo que \( \zeta\equiv \rightarrow \alpha\gamma \). En Z se demuestra que \( \ulcorner \zeta \urcorner=\ulcorner \rightarrow\urcorner*\ulcorner \alpha \urcorner*\ulcorner \gamma \urcorner \).

    Si el primer signo de \( \gamma \) no es un implicador, concluimos que \( \zeta \) no es un axioma de tipo 1) y en Z se demuestra lo mismo para \( \ulcorner \zeta \urcorner \). Supongamos que sí que lo es, con lo que

    \( \zeta\equiv \rightarrow \alpha\rightarrow\beta\delta. \)

    En Z se demuestra que \( \ulcorner \zeta \urcorner=\ulcorner \rightarrow \urcorner*\ulcorner \alpha \urcorner*\ulcorner \rightarrow \urcorner*\ulcorner \beta \urcorner*\ulcorner \delta \urcorner \).

    Si \( \delta\equiv \alpha \), entonces \( \zeta \) es un axioma de tipo 1, y en Z se demuestra que \( \ulcorner \delta \urcorner=\ulcorner \alpha \urcorner \), de donde se sigue que \( \ulcorner \zeta \urcorner \) cumple la definición de \( A_1 \). Si, por el contrario, \( \delta\not\equiv \alpha \), en Z se demuestra que \( \ulcorner \delta \urcorner\neq \ulcorner \alpha \urcorner \), y de aquí se sigue que \( \ulcorner \zeta \urcorner \) no es un axioma de tipo \( A_1 \).
    [cerrar]

    Igualmente se pude razonar con los otros tipos de axiomas lógicos (sólo hay que ir analizando la fórmula signo a signo hasta que se acabe), por lo que concluimos:

  • Si \( \zeta \) es un axioma lógico, entonces en Z se demuestra que \( \ulcorner \zeta \urcorner \) es un axioma lógico, y si no lo es, en Z se demuestra que \( \ulcorner \zeta \urcorner \) no es un axioma lógico.

  • Si \( \gamma \) es un caso particular del axioma de especificación, en Z se demuestra que \( \ulcorner \gamma \urcorner\in \mbox{Esp} \), y en caso contrario se demuestra que \( \ulcorner \gamma \urcorner\notin \mbox{Esp} \).

    Recordemos que en Z se define el conjunto Esp como el conjunto de fórmulas de la forma

    \( \gamma = \forall x\exists z\forall u(u\in z\leftrightarrow u\in x\land \alpha))\equiv  \forall x\lnot\forall z\lnot \forall u\rightarrow\lnot\lnot\lnot \rightarrow\in uz\lnot\rightarrow\lnot\lnot\in ux\lnot \alpha\lnot\rightarrow\lnot\lnot \in ux\lnot\alpha\rightarrow \in uz,
     \)
    donde la variable \( z \) no está en \( \alpha \).

    Demostración
    Si los signos segundo, quinto y octavo de \( \gamma \) no son tres variables distintas \( x, z, u \), entonces \( \gamma \) no puede ser un axioma de especificación y en Z se demuestra que los signos segundo, quinto y octavo de \( \ulcorner \gamma \urcorner \) no son variables distintas, de donde se concluye que \ulcorner \( \gamma \urcorner\notin \mbox{Esp} \). En caso contrario, fijadas las variables \( x, z, u \), nos fijamos en los \( 24 \) primeros signos de \( \gamma \), para ver si son, concretamente \( \forall x\lnot\forall z\lnot \forall u\rightarrow\lnot\lnot\lnot \rightarrow\in uz\lnot\rightarrow\lnot\lnot\in ux\lnot \) o si forman una sucesión distinta. Si no forman esta sucesión (en particular, si la longitud de \( \gamma \) es menor que \( 24 \)), es decir, si \( \gamma \) no es de la forma

    \( \gamma \equiv \forall x\lnot\forall z\lnot \forall u\rightarrow\lnot\lnot\lnot \rightarrow\in uz\lnot\rightarrow\lnot\lnot\in ux\lnot \zeta,
     \)

    no es un axioma de especificación, y en Z se demuestra que \( \ulcorner \gamma \urcorner \) tampoco es de esta forma (o bien tiene longitud menor que \( \ulcorner 24\urcorner \) o bien la sucesión de sus primeros \( 24 \) signos no es la considerada), lo que implica a su vez que no está en Esp.

    Si \( \gamma \) si que es de esta forma, para que pueda ser un axioma de especificación es necesario que \( \zeta\equiv \alpha\zeta' \) sea una yuxtaposición de fórmulas en cuya primera fórmula \( \alpha \) no esté \( z \). Si no es así, en Z se puede demostrar que no es así, y de ahí que \( \ulcorner \gamma \urcorner\notin \mbox{Esp} \). Si \( \gamma \) es de esta forma, si es un axioma de especificación tendremos que \( \zeta'\equiv \lnot\rightarrow\lnot\lnot \in ux\lnot\alpha\rightarrow \in uz \) y en Z se puede demostrar que \( \ulcorner \zeta' \urcorner=\ulcorner \lnot\rightarrow\lnot\lnot\in ux\lnot \urcorner*\ulcorner \alpha \urcorner*\ulcorner \rightarrow\in uz \urcorner \), lo que permite concluir que \( \ulcorner \gamma \urcorner\in \mbox{Esp} \), mientras que si \( \zeta' \) no es de esta forma en Z se puede demostrar que \( \ulcorner \zeta' \urcorner\neq \ulcorner \lnot\rightarrow\lnot\lnot\in ux\lnot \urcorner*\ulcorner \alpha \urcorner*\ulcorner \rightarrow\in uz \urcorner \), de donde  \( \ulcorner \gamma \urcorner\notin \mbox{Esp} \).
    [cerrar]

    Para los demás axiomas de Z la situación es trivial. Se trata de seis fórmulas concretas \( \zeta_1,\ldots, \zeta_6 \). Por ejemplo,

    \( \zeta_2\equiv \exists x\forall y\, y\notin x\equiv \lnot\forall x_0\lnot  \forall x_1\lnot\in x_1x_0. \)

    Si una fórmula \( \zeta \) es una de las \( \zeta_i \), sabemos que en Z puede probarse \( \ulcorner \zeta \urcorner=\ulcorner \zeta_i \urcorner \), y si \( \zeta \) no es ninguna de las \( \ulcorner \zeta_i \urcorner \), en Z se prueba que \( \ulcorner \zeta\urcorner\neq \ulcorner \zeta_i \urcorner \). Por lo tanto, combinando esto con el resultado precedente sobre Esp y definiendo

    \( \mbox{Z}=\{\ulcorner \zeta_1 \urcorner,\ulcorner \zeta_2 \urcorner,\ulcorner \zeta_3 \urcorner,\ulcorner \zeta_4 \urcorner,\ulcorner \zeta_5 \urcorner,\ulcorner \zeta_6 \urcorner \}\cup\mbox{Esp},
     \)

    concluimos:

  • Si una fórmula \( \alpha \) es un axioma de Z, en Z se demuestra \( \ulcorner \alpha \urcorner\in \mbox{Z} \), y si \( \alpha \) no es un axioma de Z, en Z se demuestra \( \ulcorner \alpha \urcorner\notin \mbox{Z} \).

    Ahora bien, es obvio que la misma forma de argumentación que hemos empleado para probar que en Z puede probarse si una fórmula dada está o no en Esp, puede aplicarse con el axioma de reemplazo de ZF, por lo que el teorema anterior vale igualmente para ZF o ZFC. (Pero las demostraciones correspondientes pueden hacerse siempre en Z, sin necesidad de más axiomas, por ejemplo, si \( \alpha \) es un axioma de ZFC, en Z puede probarse que \( \ulcorner \alpha \urcorner\in \mbox{ZFC} \).)


En general, podemos llegar a la misma conclusión para los axiomas de cualquier teoría de conjuntos "razonable" en el sentido de que podamos distinguir si una fórmula dada es o no un axioma mediante argumentos formalizables en Z. Por ejemplo, si llamamos ZZ a la teoría de conjuntos que resulta de añadir a los axiomas de Z todas las afirmaciones verdaderas sobre números naturales, puede ocurrir que tengamos un axioma de ZZ explícitamente escrito en un papel, pero que no seamos capaces de probar que lo es. Para unos axiomas definidos así, no podemos extender los razonamientos precedentes, pero se trata de unos axiomas inútiles, porque no podemos usarlos en demostraciones, ya que no sabríamos si una fórmula que escribimos es o no un axioma, por lo que no sabríamos si una demostración en la que usáramos la fórmula en cuestión sería correcta o no.

En particular, para cualquier teoría de conjuntos con un número finito de axiomas (que podamos escribir explícitamente en un papel) se puede aplicar la parte trivial de los argumentos anteriores (la que involucra a los seis axiomas de Z distintos del de especificación) para concluir que si \( \alpha \) es un axioma de la teoría, entonces en Z puede probarse que \( \ulcorner \alpha \urcorner \) está en subconjunto de \( \mathcal F \) que formaliza al conjunto de axiomas de la teoría. Es el caso, por ejemplo, de la teoría de conjuntos NBG, que admite un número finito de axiomas.

Si \( D \) es una demostración de una fórmula \( \alpha \) en Z (ZF, ZFC, etc.) en Z se demuestra que \( \ulcorner D \urcorner \) es una demostración de \( \ulcorner \alpha\urcorner \) en la teoría correspondiente, y si \( D \) es una sucesión de fórmulas que no es una demostración de \( \alpha \), entonces en Z se demuestra que \( \ulcorner D \urcorner \) no es una demostración de \( \ulcorner \alpha\urcorner \).

Si ya de por sí podemos decir que esto es obvio, con todo lo probado hasta aquí es más que obvio:

Demostración
Si \( D=(\alpha_0,\ldots, \alpha_n) \) es realmente una demostración, en Z podemos probar que \( \ulcorner D \urcorner\in S^2 \) y, como todos sus términos son fórmulas, en Z podemos probar que es una sucesión finita de fórmulas. Para cada \( i\leq n \), se cumplirá uno de los casos siguientes:

  • \( \alpha_i \) es un axioma lógico.

    En este caso sabemos que en Z se demuestra que \( \ulcorner \alpha_i \urcorner\in \mbox{A} \).

  • \( \alpha_i \) es un axioma de Z (o de ZF, ZFC, etc.).

    En este caso sabemos que en Z se demuestra que  $\ulcorner \alpha_i \urcorner\in \mbox{Z}$ (o ZF, ZFC, etc.).

  • Existen \( j,k<i \) tales que \( \alpha_j\equiv \alpha_k\rightarrow \alpha_i \).

    En tal caso en Z se demuestra que \( \ulcorner \alpha_j \urcorner = \ulcorner \alpha_j \urcorner\rightarrow \ulcorner \alpha_k \urcorner \).

  • Existe \( j<i \) y una variable \( x \) tal que \( \alpha_i\equiv \forall x \alpha_j \).

    En este caso en Z se demuestra que \( \ulcorner \alpha_i \urcorner=\ulcorner \forall\urcorner*\ulcorner x \urcorner*\ulcorner \alpha_j \urcorner \),

y esto implica que \( \ulcorner D \urcorner \) es una demostración en la teoría considerada (Z, ZF, etc.). Si además la última fórmula de \( D \) es \( \alpha \), por definición de \( \ulcorner D\urcorner \) se concluye que la última fórmula de \( \ulcorner D\urcorner \) es \( \ulcorner \alpha\urcorner \).
Recíprocamente, si \( D \) no es una demostración de \( \alpha \), o bien alguno de sus términos no es una fórmula (en cuyo caso sabemos que en Z puede probarse que así es, y eso implica que \( \ulcorner D\urcorner \) no es una demostración de \( \ulcorner\alpha\urcorner \)), o bien todos sus términos son fórmulas, pero alguno de ellos, digamos \( \alpha_i \), no cumple ninguno de los cuatro casos anteriores, en cuyo caso es claro que en Z puede probarse que \( \ulcorner \alpha_i \urcorner \) no cumple ninguna de las cuatro posibilidades que requiere la definición de demostración, o bien \( D \) sí que es una demostración, pero su última fórmula no es \( \alpha \), en cuyo caso en Z se prueba que la última fórmula de \( \ulcorner D\urcorner \) no es \( \ulcorner \alpha\urcorner \), y esto implica que \( \ulcorner D\urcorner \) no es una demostración de \( \ulcorner \alpha\urcorner \).
[cerrar]

En particular:

Si \( \alpha \) es un teorema de Z (ZF, ZFC, etc.), entonces en Z se demuestra que \( \ulcorner \alpha \urcorner \) es un teorema de Z (ZF, ZFC, etc.).

Demostración
En efecto, si \( \alpha \) es un teorema de cualquiera de las teorías consideradas, entonces tiene una demostración \( D \), y en Z se demuestra que \( \ulcorner D\urcorner \) es una demostración cuya última fórmula es \( \ulcorner \alpha \urcorner \), y eso significa que \( \ulcorner \alpha\urcorner \) es un teorema de la teoría en cuestión.
[cerrar]

En cambio, no podemos asegurar que si \( \alpha \) no es un teorema, en Z pueda probarse que \( \ulcorner \alpha \urcorner \) no es un teorema, pues ello requeriría justificar de algún modo que no existe ninguna demostración \( D \) de \( \ulcorner \alpha \urcorner \), y no está claro cómo podría hacerse tal cosa.

28 Abril, 2018, 12:21 am
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La prueba de los teoremas de incompletitud contiene varias ideas brillantes de Gödel:

  • La primera es la posibilidad de formalizar la lógica a través de fórmulas aritméticas (fórmulas que hablan sólo de números naturales) a través de los números de Gödel.

    Esta idea no aparece en la versión que estamos probando aquí porque estamos formalizando la lógica en Z, lo cual no tiene ningún mérito, ya que en Z se puede formalizar cualquier cosa razonable (en ZFC, que hubiéramos podido usar si nos hubiera hecho falta) cualquier cosa. En particular, la numeración de Gödel la hemos reducido a su mínima expresión, al limitarla a asignar un número a cada signo del lenguaje, pero no a las fórmulas ni a las demostraciones.

  • La segunda es la forma de justificar que a partir de los axiomas de Peano es posible demostrar todas las cosas que es necesario demostrar para probar los teoremas de incompletitud. Para ello Gödel se apoyó en la teoría de la recursión.

    En nuestro contexto esto también desaparece, porque para demostrar que en Z se puede demostrar todo lo necesario no hace falta ninguna artillería. En particular, no hemos necesitado mencionar para nada la teoría de la recursión.

  • La tercera es la posibilidad de aprovechar lo anterior para definir fórmulas autorreferentes, es decir, fórmulas que hablen de sí mismas en un sentido que precisaremos en el mensaje siguiente.

    Esto requiere un resultado técnico previo al que dedicaremos este mensaje, resultado que en la prueba clásica no llama mucho la atención ya que se obtiene de forma inmediata a partir de las técnicas relacionadas con el punto anterior y que aquí no hemos necesitado. En cambio, aquí vamos a poner el foco sobre él.

  • La cuarta y la quinta son los argumentos en sí que prueban los dos teoremas de incompletitud.

Para explicar el resultado que tenemos que demostrar aquí consideremos una sucesión finita metamatemática de números naturales, por ejemplo, \( \zeta = (3,5,1) \). Tenemos definida su formalización en Z, que representamos por \( \ulcorner(3, 5, 1)\urcorner \). Con precisión, esto no es nada en nuestro lenguaje formal, sino que lo que tenemos definido realmente es la fórmula

\( x=\ulcorner(3, 5, 1)\urcorner\equiv \forall u(u\in x\leftrightarrow u = (\ulcorner0\urcorner,\ulcorner3\urcorner)\lor u = (\ulcorner1\urcorner, \ulcorner5\urcorner)\lor u=(\ulcorner2\urcorner, \ulcorner1\urcorner)).
 \)

Esto es una fórmula metamatemática, luego también tenemos definida su formalización \( \ulcorner x=\ulcorner(3, 5, 1)\urcorner\urcorner \), de modo que, según hemos visto en el mensaje anterior, en Z podemos demostrar que \( \ulcorner x=\ulcorner(3, 5, 1)\urcorner\urcorner\in \mathcal F \).

Lo que nos proponemos demostrar es que es posible definir en Z una aplicación \( \mathcal V\times S^1\longrightarrow \mathcal F \), que representaremos por \( (x, \zeta)\mapsto [x=\zeta] \), con la propiedad de que, para toda variable metamatemática \( x \) y toda sucesión finita metamatemática de números naturales \( \zeta \), se cumple que

\( \color{blue}[\ulcorner x\urcorner=\ulcorner\zeta\urcorner] = \ulcorner x=\ulcorner\zeta\urcorner\urcorner, \)

es decir que, en el ejemplo que estábamos considerando, la fórmula  \( \ulcorner x=\ulcorner(3, 5, 1)\urcorner\urcorner\in \mathcal F \) puede calcularse en Z aplicando una función (la que vamos a definir) a la variable \( \ulcorner x\urcorner \) y a la sucesión \( \ulcorner\zeta\urcorner \). En otras palabras, que en Z podemos describir el proceso que permite construir la formalización de \( x= \ulcorner\zeta\urcorner \) a partir de \( \ulcorner x\urcorner \) y de \( \ulcorner\zeta\urcorner \).

Nuestro objetivo es, pues, definir una cierta función \( \mathcal V\times S^1\longrightarrow \mathcal F \), para lo cual tendremos que definir algunas funciones previas.

Por ejemplo, empezamos considerando las funciones

\( \ulcorner=\urcorner: \mathcal V\times\mathcal V\longrightarrow \mathcal F,\qquad \ulcorner\in\urcorner:\mathcal V\times\mathcal V\longrightarrow \mathcal F
 \)
dadas por

\( x\,\ulcorner=\urcorner\, y=(\ulcorner=\urcorner, x, y),\qquad x\,\ulcorner\in\urcorner\,y=(\ulcorner\in\urcorner, x, y). \)

Es importante entender esto: estamos definiendo una aplicación, exactamente igual que si definiéramos \( f:\mathbb N\times \mathbb N\longrightarrow \mathbb N \) mediante \( f(x, y) = xy^2 \). En este ejemplo, cuando a las variables (metamatemáticas) \( x, y \) les damos valores en los números naturales, la aplicación \( f \) nos da un número natural. En el ejemplo que nos interesa, cuando a la aplicación \( \ulcorner=\urcorner(x, y) \) le damos valores en \( \mathcal V \) a las dos variables (metamatemáticas) \( x,y \), obtenemos un elemento de \( \mathcal F \).

También es importante no confundir \( x\,\ulcorner=\urcorner\,y \) con \( \ulcorner x=y\urcorner \). La primera expresión es como \( xy^2 \). No es un número natural, sino que cuando damos a \( x,y \) diferentes valores naturales obtenemos distintos números naturales. Igualmente, \( x\,\ulcorner=\urcorner\,y \) no es una fórmula, sino que cuando sustituimos las variables metamatemáticas \( x,y \) por distintas variables (formalizadas) de \( \mathcal V \) (es decir, por números naturales mayores o iguales que \( 5 \)) obtenemos distintas fórmulas atómicas de \( \mathcal F \). Por el contrario, \( \ulcorner x=y\urcorner \) es una fórmula concreta de \( \mathcal F \).

La relación entre ambas es que si \( x,y \) son variables metamatemáticas, tenemos que

\( \ulcorner x\urcorner\,\ulcorner=\urcorner\,\ulcorner y\urcorner = (\ulcorner=\urcorner, \ulcorner,x\urcorner, \ulcorner y\urcorner) = \ulcorner x=y\urcorner,
 \)
e igualmente \( \ulcorner x\urcorner\,\ulcorner\in\urcorner\,\ulcorner y\urcorner = \ulcorner x\in y\urcorner \).

Ahora recordamos otras funciones que ya teníamos definidas, sólo que ahora las representamos con ángulos de Quine:

\( \ulcorner\lnot\urcorner: \mathcal F\longrightarrow \mathcal F,\quad \ulcorner\rightarrow\urcorner:\mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\forall\urcorner:\mathcal V\times\mathcal F\longrightarrow \mathcal F,
 \)

\( \ulcorner\lor\urcorner: \mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\land\urcorner: \mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\leftrightarrow\urcorner:\mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\exists\urcorner:\mathcal V\times\mathcal F\longrightarrow \mathcal F.
 \)

Es inmediato que en Z se prueban las propiedades siguientes:

\( \ulcorner\lnot\urcorner\ulcorner\alpha\urcorner=\ulcorner\lnot\alpha\urcorner,\quad \ulcorner\alpha\urcorner\ulcorner\rightarrow\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\rightarrow\beta\urcorner,\quad \ulcorner\forall\urcorner\ulcorner x\urcorner\ulcorner\alpha\urcorner=\ulcorner\forall x \alpha\urcorner,
 \)

\( \ulcorner\alpha\urcorner\ulcorner\lor\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\lor\beta\urcorner,\quad \ulcorner\alpha\urcorner\ulcorner\land\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\land\beta\urcorner,\quad \ulcorner\alpha\urcorner\ulcorner\leftrightarrow\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\leftrightarrow\beta\urcorner,\quad \ulcorner\exists\urcorner\ulcorner x\urcorner\ulcorner\alpha\urcorner=\ulcorner\exists x \alpha\urcorner.
 \)

Por ejemplo, por definición de \( \ulcorner\lor\urcorner \):

\( \ulcorner\alpha\urcorner\ulcorner\lor\urcorner\ulcorner\beta\urcorner = (\ulcorner\lnot\urcorner\ulcorner\alpha\urcorner)\ulcorner\rightarrow\urcorner\ulcorner\beta\urcorner = \ulcorner\lnot\alpha\urcorner\ulcorner\rightarrow\urcorner\ulcorner\beta\urcorner = \ulcorner\lnot\alpha\rightarrow\beta\urcorner=\ulcorner\alpha\lor \beta\urcorner.
 \)

Números naturales Como primer paso para demostrar el resultado que perseguimos probaremos el hecho análogo para números naturales. Empezamos con el caso del \( 0 \). Por definición,

\( x=\ulcorner0\urcorner\equiv \forall u\, u\notin x, \)

donde \( u \) es una variable distinta de \( x \). En general no importa cuál sea, pero en este contexto necesitamos precisarlo, y podemos convenir en que \( u \) es la menor variable distinta de \( x \) (teniendo en cuenta que estamos identificando las variables con los números naturales mayores o iguales que \( 5 \)).

Así, \( x=\ulcorner0\urcorner \) no es una única fórmula, sino una fórmula distinta para cada elección de \( x \). Esto determina una función que podemos formalizar en Z como la aplicación

\( \mathcal V\longrightarrow \mathcal F \)
dada por

\( [x=\ulcorner0\urcorner]=\ulcorner\forall\urcorner u\ulcorner\lnot\urcorner\, u\ulcorner\in\urcorner x, \)
donde \( u \) es el menor elemento de \( \mathcal V \) distinto de \( x \).

Entendamos esto: Acabamos de definir una función en Z como podríamos haber definido \( f:\mathbb N\longrightarrow \mathbb N \) dada por \( f(x)=x^u \), donde \( u \) es el menor natural distinto de \( x \). Así, por ejemplo, \( f(3)=3^4 = 81 \).

Igual que, cuando la variable \( x \) recorre los números naturales, la expresión \( f(x) \) recorre algunos números naturales, cuando la variable (metamatemática) \( x \) recorre las variables (formalizadas) de \( \mathcal V \), la expresión \( [x= \ulcorner0\urcorner] \) recorre algunos elementos de \( \mathcal F \).

En particular, no es lo mismo \( [x=\ulcorner0\urcorner] \) que \( \ulcorner x=0\urcorner \). Lo segundo es un elemento concreto de \( \mathcal F \), mientras que lo primero es una expresión que recorre distintos elementos de \( \mathcal F \) cuando la variable \( x \) adopta diferentes valores en \( \mathcal V \). La relación entre ambas expresiones es que, si \( x \) es una variable metamatemática y \( u \) es la menor variable distinta de \( x \), entonces, por definición,

\( [\ulcorner x\urcorner=\ulcorner 0\urcorner]=\ulcorner\forall\urcorner\ulcorner u\urcorner\ulcorner\lnot\urcorner\ulcorner u\urcorner\ulcorner\in\urcorner\ulcorner x\urcorner=\ulcorner\forall u\,u\notin x\urcorner=\ulcorner x=\ulcorner0\urcorner\urcorner.
 \)

Ahora vamos a definir una función \( \mathcal V\times \mathbb N\longrightarrow \mathcal F \), que representaremos por \( [x=n] \), por recurrencia sobre \( n \), es decir, la definiremos para \( n=\ulcorner0\urcorner \) y, supuesta definida para los números naturales \( \leq n \), la definiremos para \( n+1 \). Concretamente, \( [x=\ulcorner0\urcorner]\in \mathcal F \) es la fórmula que hemos definido previamente, y

\( [x=n+1]=\ulcorner\forall\urcorner \ulcorner u\urcorner(u\,\ulcorner\in\urcorner\, x\,\ulcorner\leftrightarrow\urcorner\, [u=\ulcorner0\urcorner]\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner[u=n]),
 \)
donde \( u \) es el menor elemento de \( \mathcal V \) distinto de \( x \).

Nota técnica
Los puntos suspensivos de la definición precedente esconden a su vez una definición por recurrencia. Definimos:

\( F(u,\ulcorner0\urcorner)=[u=\ulcorner0\urcorner],\quad F(u, n+1)=F(u,n)\ulcorner\lor \urcorner\,[u=n+1]. \)

Así, \( [u=\ulcorner0\urcorner]\,\ulcorner\lor\urcorner\cdots \ulcorner\lor\urcorner\,[u=n] \) es una forma de representar \( F(u, n) \). Una simple inducción sobre \( n \) prueba que

\( F(u, \ulcorner n\urcorner) = [u=\ulcorner0\urcorner]\ulcorner\lor \urcorner\,\cdots \ulcorner\lor\urcorner\,[u=\ulcorner n\urcorner].
 \)
[cerrar]

Así, si \( x \) es una variable metamatemática y \( n \) es un número natural, en Z se demuestra que

\( [\ulcorner x\urcorner=\ulcorner n\urcorner]=\ulcorner x=\ulcorner n\urcorner\urcorner. \)

Demostración
Razonamos por inducción sobre \( n \). Para \( n=0 \) ya lo hemos probado, y si se cumple para todo número natural \( \leq n \), resulta que, llamando \( u \) a la menor variable distinta de \( x \),

\( [\ulcorner x\urcorner=\ulcorner n+1\urcorner]=\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\,\ulcorner\leftrightarrow\urcorner\,[\ulcorner u\urcorner=\ulcorner 0\urcorner]\ulcorner\lor\urcorner\cdots \ulcorner\lor\urcorner[\ulcorner u\urcorner=\ulcorner n\urcorner])
 \)

Por hipótesis de inducción:

\( [\ulcorner x\urcorner=\ulcorner n+1\urcorner]=\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\ulcorner\leftrightarrow\urcorner\,\ulcorner u=\ulcorner0\urcorner\urcorner\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\ulcorner u=\ulcorner n\urcorner\urcorner
 \)

\( =\ulcorner\forall u(u\in x\leftrightarrow u=0\lor \cdots \lor u=n)\urcorner=\ulcorner x=\ulcorner n+1\urcorner\urcorner. \)
[cerrar]

Pares desordenados  Para pasar de aquí al caso de sucesiones finitas de números naturales necesitamos formalizar la formalización de los pares ordenados. Empezamos con los pares desordenados. Teniendo en cuenta que

\( z=\{x,y\}\equiv \forall u(u\in z\leftrightarrow u=x\lor u=y), \)

donde podemos convenir en que \( u \) es la menor variable distinta de \( x, y, z \), definimos en Z una función \( \mathcal V\times\mathcal V\times\mathcal V\longrightarrow \mathcal F \) dada por

\( [z=\{x,y\}] = \ulcorner\forall\urcorner u(u\,\ulcorner\in\urcorner\,z\ \ \ulcorner\leftrightarrow\urcorner\ \ u\,\ulcorner=\urcorner\,x\ \ \ulcorner\lor\urcorner\ \ u\,\ulcorner=\urcorner\,y),
 \)
donde \( u\in \mathcal V \) es la menor variable distinta de \( x, y, z \).

Si aplicamos la función que acabamos de definir a \( \ulcorner x\urcorner, \ulcorner y\urcorner, \ulcorner z\urcorner\in \mathcal V \) obtenemos

\( [\ulcorner z\urcorner=\{\ulcorner x\urcorner, \ulcorner y\urcorner\}]= \ulcorner\forall\urcorner \ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner z\urcorner\ \ \ulcorner\leftrightarrow\urcorner\ \ \ulcorner u\urcorner\,\ulcorner=\urcorner\,\ulcorner x\urcorner\ \ \ulcorner\lor\urcorner\ \ \ulcorner u\urcorner\,\ulcorner=\urcorner\,\ulcorner y\urcorner)
 \)

\( =\ulcorner\forall x(u\in z\leftrightarrow u=x\lor u=y\urcorner = \ulcorner z=\{x,y\}\urcorner. \)

Pares ordenados Similarmente, como \( (x, y)=\{\{x\},\{x,y\}\} \), tenemos que

\( z=(x, y)\equiv \forall u(u\in z\leftrightarrow u=\{x, x\}\lor u=\{x,y\}), \)

lo que nos lleva a definir una función $\mathcal V\times\mathcal V\times \mathcal V\longrightarrow \mathcal F$ mediante

\( [z=(x, y)]= \ulcorner\forall\urcorner u(u\,\ulcorner\in\urcorner\,z\ \ \ulcorner\leftrightarrow\urcorner\ \ [u=\{x,x\}]\,\ulcorner\lor\urcorner\,[u=\{x,y\}]),
 \)

donde \( u \) es la menor variable distinta de \( x, y, z \). Así, si \( x, y, z \) son variables metamatemáticas y \( u \) es la menor variable distinta de ellas, tenemos que

\( [\ulcorner z\urcorner=(\ulcorner x\urcorner, \ulcorner y\urcorner)]=\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner z\urcorner\,\ulcorner\leftrightarrow\urcorner[\ulcorner u\urcorner=\{\ulcorner x\urcorner,\ulcorner x\urcorner\}]\,\ulcorner\lor\urcorner\,[\ulcorner u\urcorner=\{\ulcorner x\urcorner, \ulcorner y\urcorner\}])
 \)

\( =\ulcorner\forall \urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner z\urcorner\,\ulcorner\leftrightarrow\urcorner\,\ulcorner u=\{x\}\urcorner\,\ulcorner\lor\urcorner\,\ulcorner u=\{x,y\}\urcorner)
 \)

\( =\ulcorner\forall u(u\in z\leftrightarrow u=\{x\}\lor u=\{x,y\})\urcorner=\ulcorner z=(x, y)\urcorner. \)

Pares de números naturales Seguidamente definimos una función \( \mathcal V\times \mathbb N\times \mathbb N\longrightarrow \mathcal F \), que representaremos por \( [x=(m,n)] \), mediante

\( [z=(m,n)]=\ulcorner\exists\urcorner xy([x=m]\,\ulcorner\land \urcorner\,[y=n]\,\ulcorner\land\urcorner\, [z=(x,y)]). \)

donde \( x,y \) son las menores variables distintas de \( z \). Así, si \( z \) es una variable metamatemática y \( m, n \) son dos números naturales, se cumple que

\( [\ulcorner z\urcorner=(\ulcorner m\urcorner, \ulcorner n\urcorner)]=\ulcorner\exists\urcorner\ulcorner x\urcorner\ulcorner y\urcorner([\ulcorner x\urcorner=\ulcorner m\urcorner]\ulcorner\land\urcorner[\ulcorner y\urcorner=\ulcorner n\urcorner]\ulcorner\land\urcorner [\ulcorner z\urcorner=(\ulcorner x\urcorner, \ulcorner y\urcorner)])
 \)

\( =\ulcorner\exists \urcorner\ulcorner x\urcorner\ulcorner y\urcorner(\ulcorner x=\ulcorner m\urcorner\urcorner\ulcorner\land\urcorner\ulcorner y=\ulcorner n\urcorner\urcorner\ulcorner\land \urcorner\ulcorner z=(x,y)\urcorner)
 \)

\( =\ulcorner \exists xy(x=\ulcorner m\urcorner\land y=\ulcorner n\urcorner\land z=(z, y))\urcorner=\ulcorner z=(\ulcorner m\urcorner, \ulcorner n\urcorner)\urcorner.
 \)

Conclusión Finalmente, si \( x\in \mathcal V \) y \( \zeta\in S^1 \) es una sucesión de longitud \( n+1 \), ya podemos definir

\( [x=\zeta]=\ulcorner\forall\urcorner\, u\, (u\ \ulcorner\in \urcorner\,x\,\ulcorner\leftrightarrow\urcorner[u=(\ulcorner 0\urcorner, \zeta(\ulcorner0\urcorner))]\,\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\,[u=(n,\zeta(n))]),
 \)

donde \( u \) es la menor variable distinta de \( x \).

Notas técnicas
Para la sucesión vacía de longitud \( 0 \) podemos definir \( [x=\emptyset]=[x=\ulcorner0\urcorner] \), aunque nunca necesitaremos este caso.

En el caso \( n>0 \), los puntos suspensivos de la definición precedente representan otra definición por recurrencia, análoga a la que hemos visto en la formalización de la formalización de los números naturales.
[cerrar]

 De este modo, si \( \zeta \) es una sucesión finita metamatemática, teniendo en cuenta que \( \ulcorner\zeta\urcorner(\ulcorner i\urcorner)=\ulcorner\zeta_i\urcorner \), se cumple que

\( [\ulcorner x\urcorner = \ulcorner\zeta\urcorner]=\ulcorner\forall \urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\,\ulcorner\leftrightarrow\urcorner\,[\ulcorner u\urcorner\,=(\ulcorner 0\urcorner,\ulcorner\zeta_0\urcorner)]\,\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\,[\ulcorner u\urcorner=(\ulcorner n\urcorner,\ulcorner\zeta_n\urcorner)])
 \)

\( =\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\,\ulcorner\leftrightarrow\urcorner\,\ulcorner u=(\ulcorner0\urcorner,\ulcorner\zeta_0\urcorner)\urcorner\,\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\ulcorner u=(\ulcorner n\urcorner,\ulcorner\zeta_n\urcorner)\urcorner)
 \)

\( =\ulcorner\forall u(u\in x\leftrightarrow u=(\ulcorner 0\urcorner,\ulcorner\zeta_0\urcorner)\lor\cdots\lor u=(\ulcorner n\urcorner,\ulcorner\zeta_n\urcorner))\urcorner=\ulcorner x=\ulcorner\zeta\urcorner\urcorner.
 \)