Autor Tema: Modelos de la teoría de conjuntos

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

17 Septiembre, 2012, 02:06 am
Leído 35958 veces

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Es bastante frecuente que en muchos hilos sobre temas conjuntistas se termine hablando de modelos de la teoría de conjuntos, pero no hay en este foro ningún hilo que recoja las definiciones básicas al que el lector no familiarizado pueda remitirse, y eso hace que todo lo relacionado con modelos acabe sonando como algo más o menos "misterioso".

Por ello he decidido crear un hilo con este fin: presentar para futuras consultas o referencias, los conceptos básicos de la teoría de modelos orientada especialmente al trabajo con modelos de ZFC y otras teorías relacionadas. Trataré de reducir al mínimo las consideraciones metamatemáticas subyacentes.

Por razones de claridad he separado en el hilo Comentarios al hilo de modelos de la teoría de conjuntos todos los comentarios que se han ido haciendo sobre este hilo.



Salvo que se indique lo contrario, todo los resultados se definen, enuncian y demuestran en ZF (el axioma de elección no es necesario, salvo que se indique explícitamente) y, de hecho, un lector familiarizado con los axiomas de ZF advertirá que el axioma de partes tampoco es necesario.

Para empezar necesitamos introducir el concepto de lenguaje formal.



Definición: Un lenguaje formal (de primer orden) es una eneatupla ordenada \( \mathcal L = (\ulcorner \lnot\urcorner, \ulcorner \rightarrow\urcorner, \ulcorner \forall\urcorner,\ulcorner = \urcorner,\ulcorner ( \urcorner,\ulcorner ) \urcorner, V,R,F) \), donde:

  • \( \ulcorner \lnot\urcorner, \ulcorner \rightarrow\urcorner, \ulcorner \forall\urcorner,\ulcorner = \urcorner,\ulcorner ( \urcorner,\ulcorner ) \urcorner \) son objetos (es decir, conjuntos) cualesquiera, distintos entre sí, a los que llamaremos negador, implicador, cuantificador universal, igualador, paréntesis abierto y paréntesis cerrado del lenguaje \( \mathcal L \), respectivamente. Para referirnos a cualquiera de ellos indistintamente los llamaremos signos lógicos de \( \mathcal L \).
  • \( V \) es un conjunto infinito a cuyos elementos llamaremos \( variables \) de \( \mathcal L \). Usaremos la notación \( \mbox{Var}(\mathcal L) \) para referirnos al conjunto de variables (es decir, a la quinta componente) de un lenguaje formal \( \mathcal L \).
  • \( R \) es una función cuyo dominio es el conjunto de los números naturales \( n>0 \). A los elementos del conjunto \( R(n) \) los llamaremos relatores \( n \)-ádicos de \( \mathcal L \). Representaremos por \( \mbox{Rel}_n(\mathcal L) \) al conjunto de relatores \( n \)-ádicos del lenguaje formal \( \mathcal L \). Cualquiera de estos conjuntos puede ser vacío excepto \( \mbox{Rel}_2(\mathcal L) \), porque exigimos que \( \ulcorner = \urcorner\in \mbox{Rel}_2(\mathcal L) \).
  • \( F \) es una función cuyo dominio es el conjunto de los números naturales. A los elementos de \( F(0) \) los llamaremos constantes de \( \mathcal L \) y representaremos \( \mbox{const}(\mathcal L) = F(0) \). A los elementos de \( F(n) \), para \( n>0 \), los llamaremos funtores \( n \)-ádicos de \( \mathcal L \). Representaremos por \( \mbox{Fn}_n(\mathcal L) \) al conjunto (tal vez vacío) de funtores \( n \)-ádicos de \( \mathcal L \).

Exigimos además como parte de la definición que los distintos conjuntos de relatores, funtores, variables y constantes sean disjuntos entre sí dos a dos (es decir, que un funtor diádico no puede ser también un relator triádico, etc.) y ninguno de ellos puede contener a ninguno de los signos lógicos salvo por que \( \ulcorner = \urcorner\in \mbox{Rel}_2(\mathcal L) \). Insistimos en que cualquiera de estos conjuntos puede ser vacío excepto el conjunto de las variables (al que le hemos exigido que sea infinito) y el conjunto de los relatores diádicos (que debe contener al igualador).

Llamaremos signos de \( \mathcal L \) a los elementos del conjunto

\( \mbox{Sig}(\mathcal L) = \) \( \{\ulcorner \lnot\urcorner, \ulcorner \rightarrow\urcorner, \ulcorner \forall\urcorner,\ulcorner = \urcorner,\ulcorner ( \urcorner,\ulcorner ) \urcorner\}\cup \mbox{Var}(\mathcal L)\cup \mbox{Const}(\mathcal L)\cup \bigcup\limits_{n\geq 1}\mbox{Rel}_n(\mathcal L)\cup \bigcup\limits_{n\geq 1}\mbox{Fn}_n(\mathcal L) \).

Así pues, podemos pensar que un lenguaje formal no es más que un conjunto de objetos llamados signos clasificados arbitrariamente en varias categorías (a uno lo clasificamos como "negador", otro como "implicador", a otros infinitos como "variables", etc.), de modo que un mismo signo no puede estar clasificado en dos sitios a la vez, salvo que el signo clasificado como "igualador" es también un "relator diádico".

El hecho de que usemos el mismo signo \( \ulcorner \lnot\urcorner \) para representar el negador de un lenguaje formal no debe entenderse como que todos los lenguajes deben tener el mismo negador. Es lo mismo que sucede cuando representamos por \( 0 \) el neutro para la suma de un anillo cualquiera. Esto no impide que cada anillo tenga su propio "cero", que será un conjunto distinto en cada caso.

Ejemplo
Llamaremos lenguaje de la teoría de anillos al lenguaje \( \mathcal L_A \) cuyos signos son:

  • \( \ulcorner \lnot\urcorner = 2,\ \ulcorner \rightarrow\urcorner = 4,\ \ulcorner \forall\urcorner = 8,\ \ulcorner = \urcorner = 16,\ \ulcorner ( \urcorner = 32,\ \ulcorner ) \urcorner=64 \).
  • \( \mbox{Var}(\mathcal L) = \{3^n\mid n\geq 1\} \). Representaremos por \( \ulcorner x_i\urcorner = 3^i \) a la variable \( i \)-ésima de \( \mathcal L_A \).
  • \( \mbox{Rel}_2(\mathcal L_A) = \{16\} \), y los demás conjuntos de relatores son todos vacíos.
  • \( \mbox{Const}(\mathcal L_A) = \{5, 25\} \),  \( \mbox{Fn}_1(\mathcal L_A)=\{125\} \), \( \mbox{Fn}_2(\mathcal L_A)=\{625, 3125\} \). Representaremos \( \ulcorner 0 \urcorner = 5 \), \( \ulcorner 1 \urcorner = 25 \), \( \ulcorner - \urcorner = 125 \), \( \ulcorner + \urcorner = 625 \), \( \ulcorner \cdot \urcorner = 3125 \). Todos los demás conjuntos de funtores son vacíos.

Veremos que en la práctica no importará para nada qué conjunto concreto es cada signo de un lenguaje formal, por lo que una definición abreviada de \( \mathcal L_A \) sería definirlo como un lenguaje formal cuyos únicos signos opcionales son dos constantes \( \ulcorner 0 \urcorner \) y \( \ulcorner 1 \urcorner \), un funtor monádico \( \ulcorner - \urcorner \) y dos funtores diádicos \( \ulcorner + \urcorner \) y \( \ulcorner \cdot \urcorner \).

Vemos así que todos los signos de \( \mathcal L_A \) son números naturales. De hecho, para nuestros fines, no perderíamos generalidad si exigiéramos que los signos de cualquier lenguaje formal deben ser números naturales, pero es más cómodo no exigirlo en teoría.

Notemos que \( \ulcorner 0 \urcorner \) es un número natural, pero \( \ulcorner 0 \urcorner\neq 0 \), sino que \( \ulcorner 0 \urcorner = 5 \). Se ve así la importancia de los ángulos de Quine que estamos usando para distinguir los signos de un lenguaje formal. Sería un error muy grave confundir el cuantificador \( \forall \) (para todo) con el signo de \( \mathcal L_A \) \( \ulcorner \forall \urcorner \), que no es sino el número \( 8 \). Podemos escribir \( \ulcorner \forall \urcorner\in \mathbb N \) (y es verdad), mientras que \( \forall \in \mathbb N \) es un sinsentido que ni el estudiante de matemáticas más novato escribiría jamás.
[cerrar]

Cadenas de signos Llamaremos cadenas de signos de \( \mathcal L \) a las sucesiones finitas de signos de \( \mathcal L \). Representaremos por \( \mbox{Cad}(\mathcal L) \) al conjunto de todas las cadenas de signos de \( \mathcal L \).

Conjuntistamente, una sucesión de longitud \( n \) en un conjunto \( X \) es una aplicación del conjunto \( \{0, 1, 2, \ldots, n-1\} \) en \( X \), luego es un conjunto de pares ordenados. Para representar cadenas de signos concretas usaremos la notación siguiente:

\( (\ulcorner \lnot\urcorner,\ulcorner \lnot\urcorner,\ulcorner \forall\urcorner,\ulcorner =\urcorner) \) representará la sucesión que tiene a los signos indicados en el orden indicado. Conjuntistamente:

\( (\ulcorner \lnot\urcorner,\ulcorner \lnot\urcorner,\ulcorner \forall\urcorner,\ulcorner =\urcorner) = \{(0, \ulcorner \lnot\urcorner),(1,\ulcorner \lnot\urcorner),(2,\ulcorner \forall\urcorner),(3,\ulcorner =\urcorner)\}\in \mbox{Cad}(\mathcal L) \).

Técnicamente hay que distinguir entre el signo \( \ulcorner \forall\urcorner \) y la cadena de signos  \( (\ulcorner \forall\urcorner) = \{(0, \ulcorner \forall\urcorner)\} \) de longitud \( 1 \).

El el conjunto \( \mbox{Cad}(\mathcal L) \) tenemos definida la operación asociativa de yuxtaposición, que representaremos por \( * \). Omitimos la definición explícita, pero en definitiva se trata de la operación que hace que si

\( \zeta_1 = (\ulcorner \forall\urcorner,\ulcorner \forall\urcorner,\ulcorner )\urcorner) = \{(0,\ulcorner \forall\urcorner),(1,\ulcorner \forall\urcorner),(2,\ulcorner )\urcorner)\} \) y \( \zeta_2 = (\ulcorner \rightarrow\urcorner,\ulcorner (\urcorner) = \{(0,\ulcorner \rightarrow\urcorner),(1,\ulcorner (\urcorner)\} \), entonces

\( \zeta_1*\zeta_2 =  (\ulcorner \forall\urcorner,\ulcorner \forall\urcorner,\ulcorner )\urcorner,\ulcorner \rightarrow\urcorner,\ulcorner (\urcorner) =  \{(0,\ulcorner \forall\urcorner),(1,\ulcorner \forall\urcorner),(2,\ulcorner )\urcorner)(3,\ulcorner \rightarrow\urcorner),(4,\ulcorner (\urcorner)\} \).

Cuando no haya confusión escribiremos \( \zeta_1\zeta_2 \) en lugar de \( \zeta_1*\zeta_2 \).

Términos Vamos a definir un subconjunto \( \mbox{Term}(\mathcal L)\subset \mbox{Cad}(\mathcal L) \) del conjunto de todas las cadenas de signos de un lenguaje formal \( \mathcal L \). A los elementos de \( \mbox{Term}(\mathcal L) \) los llamaremos términos de \( \mathcal L \).

Damos la definición por recurrencia:

Los términos de orden \( 0 \) son las cadenas de signos de longitud 1 determinadas por las variables o las constantes de \( \mathcal L \), es decir:

\( \mbox{Term}_0(\mathcal L) = \{(x)\mid x\in \mbox{Var}(\mathcal L)\}\cup \{(c)\mid c\in \mbox{Const}(\mathcal L)\} \).

Supuesto definido el conjunto \( \mbox{Term}_n(\mathcal L) \) definimos

\( \mbox{Term}_{n+1}(\mathcal L) = \mbox{Term}_n(\mathcal L)\cup \{(f)t_1\cdots t_m\mid m\geq 1, f\in \mbox{Fn}_m(\mathcal L), t_i\in \mbox{Term}_n(\mathcal L)\} \).

Por último: \( \mbox{Term}(\mathcal L) = \bigcup\limits_{n\in \mathbb N}\mbox{Term}_n(\mathcal L) \).

Así, un término de orden \( n+1 \) se forma yuxtaponiendo un funtor m-ádico con m términos de órdenes anteriores.

Notemos que si un lenguaje formal no tiene constantes ni funtores, entonces sus términos son simplemente sus variables (las sucesiones de longitud 1 correspondientes a variables).

Ejemplo
Consideremos el lenguaje \( \mathcal L_A \) definido antes. Tenemos que \( (\ulcorner x_1\urcorner) \) es un término de orden \( 0 \), porque  \( \ulcorner x_1\urcorner \)  es una variable, y  \( (\ulcorner 0\urcorner) \) es otro término de orden \( 0 \), porque  \( \ulcorner 0\urcorner \) es una constante.

A su vez,  \( (\ulcorner -\urcorner, \ulcorner x_1\urcorner) \) es un término de orden 1, por ser la yuxtaposición de un funtor monádico y un término de orden 0. En la práctica lo representaremos por \( \ulcorner (-x_1)\urcorner \) y, más en general, si \( \ulcorner t\urcorner\in \mbox{term}(\mathcal L) \), representaremos \( \ulcorner (-t)\urcorner = (\ulcorner -\urcorner)*\ulcorner t\urcorner\in \mbox{Term}(\mathcal L) \).

A su vez, \( \ulcorner+\urcorner* (\ulcorner0\urcorner)*\ulcorner-x_1\urcorner \) es un término de orden 2, porque consta de un funtor diádico seguido de dos términos. En la práctica lo representaremos por \( \ulcorner(0+(-x_1))\urcorner \) y, en general, siempre que tengamos un funtor diádico \( \ulcorner f\urcorner \) de un lenguaje formal y dos términos \( \ulcorner t_1\urcorner \) y \( \ulcorner t_2\urcorner \), escribiremos \( \ulcorner (t_1\,f\,t_2)\urcorner = (f)*\ulcorner t_1\urcorner*\ulcorner t_2\urcorner\in \mbox{Term}(\mathcal L) \).

Este tipo de convenios de notación son necesarios para pasar de una notación cómoda en teoría (como \( (f)t_1\cdots t_n \) para referirse a un funtor n-ádico seguido de n términos) a una notación cómoda en la práctica (como escribir el \( + \) en medio de los sumandos y no delante). Más aún, en cada lenguaje formal concreto conviene introducir convenios de notación específicos. Por ejemplo, en el lenguaje de la teoría de anillos es conveniente escribir \( \ulcorner t_1-t_2\urcorner = \ulcorner (t_1+(-t_2))\urcorner \), pero debemos entender que son abusos de lenguaje, de modo que, por ejemplo, mediante \( \ulcorner 0-x_1\urcorner \) estamos representando de una forma cómoda un término de \( \mathcal L_A \) que sigue siendo el mismo por mucho que alteremos la forma de referirnos a él, a saber,  \( \ulcorner 0-x_1\urcorner = (\ulcorner +\urcorner, \ulcorner 0\urcorner, \ulcorner -\urcorner,\ulcorner x_1\urcorner) \).

En la práctica, los signos concretos de que conste una cadena de signos será irrelevante. Lo que importa es que un término de un lenguaje formal, o bien es una constante, o bien es una variable, o bien está formado por la yuxtaposición de un funtor n-ádico y n términos construidos previamente. No importa si a la hora de representarlo en la práctica escribimos el funtor delante o en medio.

Lo que sí que es importante es no olvidar que, le demos el aspecto que le demos, un término como \( \ulcorner 0-x_1\urcorner \) no es más que una sucesión finita de signos, que en la práctica será una sucesión finita de números naturales, en este caso de cuatro números naturales, a saber \( (625, 5,125,3) \), ni más ni menos.
[cerrar]

Fórmulas Definimos ahora otro subconjunto \( \mbox{Form}(\mathcal L)\subset \mbox{Cad}(\mathcal L) \) del conjunto de cadenas de signos de un lenguaje formal, a cuyos elementos llamaremos fórmulas de \( \mathcal L \). Lo hacemos de nuevo por recurrencia:

\( \mbox{Form}_0(\mathcal L) = \{\ulcorner(\urcorner(R)t_1\cdots t_n \ulcorner)\urcorner\mid n\geq 1,  R\in \mbox{Rel}_n(\mathcal L), t_i\in \mbox{Term}(\mathcal L)\} \).

Es decir, las fórmulas de orden 0, también llamadas fórmulas atómicas, son las cadenas resultantes de yuxtaponer un relator n-ádico seguido de n términos con paréntesis al principio y al final. En la práctica escribiremos los relatores diádicos (en particular el igualador) en medio de los dos términos que le corresponden.

Ejemplo
Un ejemplo de fórmula atómica de \( \mathcal L_A \) sería \( \ulcorner 0+0 = 1\urcorner \), que es una forma práctica de abreviar la fórmula que más fielmente escrita sería \( \ulcorner(\urcorner*\ulcorner=\urcorner*\ulcorner0+0\urcorner*\ulcorner1\urcorner*\ulcorner)\urcorner \), es decir, el igualador, seguido de dos términos y todo entre paréntesis. Deshaciendo el convenio de poner el \( + \) entre los ceros, la sucesión explícita sería: \(  \ulcorner (\urcorner, \ulcorner =\urcorner, \ulcorner +\urcorner, \ulcorner 0\urcorner, \ulcorner 0\urcorner,\ulcorner 1\urcorner, \ulcorner )\urcorner) \), pero esto es irrelevante.

Nótese cómo los ángulos de Quine hacen que no dañe a la vista escribir  \( \ulcorner 0+0 = 1\urcorner\in \mbox{Form}_0(\mathcal L_A) \).
[cerrar]

\( \mbox{Form}_{n+1}(\mathcal L) = \mbox{Form}_n(\mathcal L)\cup \{ \ulcorner \lnot\urcorner*\alpha\mid \alpha\in \mbox{Form}_n(\mathcal L)\}\cup  \) \( \{\ulcorner (\urcorner*\alpha*\ulcorner \rightarrow \urcorner*\beta*\ulcorner )\urcorner\mid \alpha,\beta\in \mbox{Form}_n(\mathcal L)\}\cup  \) \( \{\ulcorner \forall\urcorner* x*\alpha\mid x\in \mbox{Var}(\mathcal L), \alpha\in \mbox{Form}_n(\mathcal L)\} \)

Con palabras: una fórmula de orden \( n+1 \) se forma anteponiendo el negador a una fórmula de orden n, o bien intercalando el implicador entre dos fórmulas de orden n (y encerrándolas entre paréntesis) o bien anteponiendo en cuantificador universal seguido de una variable a una fórmula de orden n. Finalmente definimos:

\( \mbox{Form}(\mathcal L) = \bigcup\limits_{n\in \mathbb N}\mbox{Form}_n(\mathcal L) \).

Ejemplo
Una fórmula de \( \mathcal L_A \) es, por ejemplo, \( \ulcorner \forall x\forall y(((x\cdot y) = 1)\rightarrow ((y\cdot x) = 1))\urcorner \), donde \( x, y\in \mbox{Var}(\mathcal L) \). En efecto:

Tenemos que \( \ulcorner (x\cdot y)\urcorner \) e \( \ulcorner(y\cdot x) \urcorner \) son términos, porque cada uno consta de un funtor diádico seguido de dos términos (dos variables), aunque en la práctica escribimos el funtor en medio, por ser diádico. Entonces, como \( (\ulcorner 1\urcorner) \) también es un término (por ser una constante), tenemos que \( \ulcorner ((x\cdot y) = 1)\urcorner \) y \( \ulcorner ((y\cdot x)=1)\urcorner \) son fórmulas atómicas, porque constan de un relator diádico seguido de dos términos (aunque en la práctica escribamos el relator en medio).

A su vez,\(  \ulcorner (((x\cdot y)=1)\rightarrow ((y\cdot x)=1))\urcorner \) es una fórmula, porque consta de dos fórmulas con el implicador en medio y rodeadas por paréntesis.

Esta fórmula da lugar a otra fórmula cuando se le antepone \( \ulcorner \forall y\urcorner \) y ésta a su vez da lugar a otra cuando se le antepone \( \ulcorner \forall x\urcorner \).

Si deshacemos todos los convenios de notación, observamos que la fórmula anterior no es ni más ni menos que la sucesión de números naturales:

\( (\ulcorner \forall\urcorner,\ulcorner x\urcorner, \ulcorner \forall\urcorner, \ulcorner y \urcorner, \ulcorner (\urcorner, \ulcorner( \urcorner,\ulcorner =\urcorner, \ulcorner \cdot\urcorner, \ulcorner x\urcorner, \ulcorner y\urcorner,\ulcorner 1\urcorner,\ulcorner )\urcorner, \ulcorner \rightarrow\urcorner, \ulcorner (\urcorner, \ulcorner =\urcorner, \ulcorner \cdot\urcorner,\ulcorner y\urcorner, \ulcorner x\urcorner,\ulcorner 1\urcorner,\ulcorner )\urcorner,\ulcorner )\urcorner) \)

Pero esto lo detallo sólo para recalcar que las fórmulas no son ni más ni menos que sucesiones de números naturales, aunque en la práctica no importará nada qué sucesión concreta es una fórmula dada, sino únicamente su estructura, la forma en que ha sido construida a partir de los signos del lenguaje. Por eso en la práctica adoptaremos todos los convenios de notación oportunos que no den lugar a ambigüedades sobre dicha estructura. Por ejemplo, en este caso podemos escribir, más simplemente, \( \ulcorner \forall xy(x\cdot y = 1\rightarrow y\cdot x = 1)\urcorner \), donde adoptamos el convenio de que un cuantificador seguido de varias variables equivale a repetir el cuantificador ante cada una de ellas. Pero es importante entender que esta última expresión no es sino otra forma de representar en la práctica, mediante abusos de lenguaje, a la misma sucesión 21 números naturales escrita más arriba.
[cerrar]

Convenios de notación Ya hemos visto varios convenios de notación que vamos a adoptar a la hora de nombrar términos y fórmulas de un lenguaje formal. El criterio general es que cualquier convenio es aceptable mientras no deje lugar a dudas sobre la estructura del término o la fórmula que se pretende nombrar.

Por ejemplo, en lugar de escribir \( \ulcorner\lnot (t_1 = t_2)\urcorner \), en la práctica escribiremos \( \ulcorner t_1\neq t_2\urcorner \), pero con este cambio de nombre estamos representando la misma sucesión de signos que con el nombre original, sin cambiar nada en ella.

Otros convenios útiles serán los siguientes:

  • \( \ulcorner \alpha\lor\beta\urcorner = \ulcorner \lnot\alpha\rightarrow \beta\urcorner \)
  • \( \ulcorner \alpha\land \beta \urcorner = \ulcorner \lnot(\lnot\alpha\lor \lnot\beta)\urcorner \)
  • \( \ulcorner \alpha\leftrightarrow \beta\urcorner = \ulcorner(\alpha\rightarrow\beta)\land (\beta\rightarrow\alpha)\urcorner \)
  • \( \ulcorner \exists x\alpha\urcorner = \ulcorner \lnot\forall x\lnot\alpha\urcorner \)

Claramente, si \( \alpha,\beta\in \mbox{Form}(\mathcal L) \) y \( x\in \mbox{Var}(\mathcal L) \), las cadenas de signos anteriores son fórmulas de \( \mathcal L \). Por ejemplo, tenemos que \( \ulcorner\lnot\alpha\urcorner \) es una fórmula porque resulta de anteponer el negador a una fórmula, luego a su vez \( \ulcorner \lnot\alpha\rightarrow \beta\urcorner\in \mbox{Form}(\mathcal L) \) porque resulta de intercalar el implicador entre dos fórmulas (faltarían unos paréntesis que suprimimos por abuso de notación), y dicha fórmula es por definición \( \ulcorner \alpha\lor\beta\urcorner \). Igualmente se razona con las demás.

También adoptaremos el convenio de suprimir cuantificadores iguales repetidos, es decir, que escribiremos \( \exists xy\ldots \) en lugar de \( \exists x\exists y\ldots \)

Observaciones finales La idea subyacente en la construcción anterior es que si \( \mathcal L \) es un lenguaje formal, entonces los términos de \( \mathcal L \) son las cadenas de signos "pensadas" para nombrar objetos. Por ejemplo, un término de \( \mathcal L_A \) es \( \ulcorner (1+1)\cdot (x*x)+(x-1)\urcorner \), donde hemos adoptado algunos de los convenios de notación indicados anteriormente.

Por el contrario, las fórmulas de \( \mathcal L \) son las cadenas de signos "pensadas" para afirmar algo. Por ejemplo, la fórmula \( \ulcorner \forall xy(x\neq 0\land y\neq 0\rightarrow x\cdot y\neq 0)\urcorner \) "pretende" afirmar que no hay divisores de cero, pero decimos "pretende" porque sólo es una sucesión finita de números naturales, y no hemos asignado hasta ahora ningún significado a las sucesiones finitas de números naturales. Decir que esa fórmula significa algo es en estos momentos tan absurdo como preguntarse si \( (3, 15, 19) \) es verdad o mentira.

Faltaría definir algunos conceptos lógicos, como el concepto de variable libre o ligada en una fórmula. No vamos a dar la definición explícita por brevedad, pero la idea es que en una fórmula como \( \ulcorner\exists x(x + y = 0)\urcorner \) la variable \( x \) está ligada (es decir, dentro del alcance del cuantificador \( \ulcorner \exists x\urcorner \)), mientras que la variable \( y \) está libre (no está dentro del alcance de ningún cuantificador \( \ulcorner \forall y\urcorner \) o \( \ulcorner \exists y\urcorner \). Dar una definición precisa de esto es pura rutina.

Definición Las fórmulas sin variables libres se llaman sentencias, los términos sin variables libres se llaman designadores.

Otro concepto básico es el de sustituición de una variable libre por un término. Es frecuente usar la notación \( \ulcorner\alpha(x, y)\urcorner \) para indicar que \( \alpha \) es una fórmula y \( \ulcorner x\urcorner \), \( \ulcorner y\urcorner \) son dos variables cualesquiera. Entonces, si \( \ulcorner t\urcorner \) es un término, la notación \( \ulcorner \alpha(t,y)\urcorner \) representa la fórmula que resulta de sustituir la variable \( \ulcorner x\urcorner \) en todos los lugares donde aparezca libre en la fórmula (si es que aparece) por el término \( \ulcorner t\urcorner \). A la hora de definir esto con rigor surgen ciertos problemas técnicos en los que no voy a entrar que hacen que la definición acabe siendo un poco más sofisticada de lo que podría pensarse, pero en la práctica no necesitaremos entrar en ello. Igualmente podemos sustituir una variable libre por un término en otro término.

Por ejemplo, con esta notación para las sustituciones es fácil introducir un nuevo convenio de notación:

\( \ulcorner \exists! x\alpha(x)\urcorner = \ulcorner \exists x\alpha(x)\land \forall xy(\alpha(x)\land \alpha(y)\rightarrow x=y)\urcorner \),

donde \( \ulcorner \alpha\urcorner \) es una fórmula que tiene libre la variable \( \ulcorner x\urcorner \) e \( \ulcorner y\urcorner \) es cualquier variable que no aparezca en \( \ulcorner \alpha\urcorner \). (En contextos como éste estamos usando que las fórmulas son sucesiones finitas y el conjunto de variables es infinito.)

No sé si habré convencido al lector de la utilidad de usar ángulos de Quine, pero espero que ésta se ponga de manifiesto en la próxima entrega, en la que hablaré del lenguaje formal de la teoría de conjuntos. De todos modos, conviene advertir que el uso que estoy haciendo aquí de ellos no es exactamente el estándar. No es algo importante para seguir el hilo, pero aquí hay algunos comentarios al respecto (que tal vez el lector prefiera ojear más adelante, cuando tenga ya cierta familiaridad con la forma en que los estamos empleando).

Cualquier observación, duda o sugerencia será bienvenida.

17 Septiembre, 2012, 04:48 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En este mensaje introduciré el lenguaje de la teoría de conjuntos y trataré de condensar las mínimas ideas sobre la metamatemática imprescindibles para entender bien el hilo.

Representaremos por \( \ulcorner\mathcal L_{\rm tc}\urcorner \) al lenguaje de la teoría de conjuntos. Una definición breve podría ser la siguiente:

Definición Llamaremos \( \ulcorner\mathcal L_{\rm tc}\urcorner \) a un lenguaje formal con un conjunto numerable de variables y cuyo único signo opcional es un relator diádico que representaremos por \( \ulcorner\in\urcorner \).

Con esto no hemos precisado cuáles son concretamente los signos de \( \ulcorner\mathcal L_{\rm tc}\urcorner \), cosa que en ningún momento será relevante, como cuando decimos "Sea \( G \) un grupo cíclico de 5 elementos" sin precisar cuáles son esos elementos. No obstante, vamos a dar una definición "detallada" de \( \ulcorner\mathcal L_{\rm tc}\urcorner \) únicamente por clarificar ideas:

  • \( \ulcorner \lnot\urcorner = 2,\ \ulcorner \rightarrow\urcorner = 4,\ \ulcorner \forall\urcorner = 8,\ \ulcorner = \urcorner = 16,\ \ulcorner ( \urcorner = 32,\ \ulcorner ) \urcorner=64 \).
  • \( \mbox{Var}(\mathcal L) = \{3^n\mid n\geq 1\} \). Representaremos por \( \ulcorner x_n\urcorner = 3^n \) la variable \( n \)-ésima de \( \mathcal L_A \).
  • \( \mbox{Rel}_2(\mathcal L_A) = \{16,128\} \), y los demás conjuntos de relatores son todos vacíos. Representaremos \( \ulcorner\in\urcorner=128 \).

Así podemos concretar que todos los signos de \( \ulcorner\mathcal L_{\rm tc}\urcorner \) son números naturales, por lo que todas las fórmulas de \( \ulcorner\mathcal L_{\rm tc}\urcorner \) no son ni más ni menos que (ciertas) sucesiones finitas de números naturales.

Notemos que como \( \ulcorner\mathcal L_{\rm tc}\urcorner \) no tiene constantes ni funtores, sus únicos términos son sus variables, de modo que las únicas fórmulas atómicas son las de la forma \( \ulcorner x=y\urcorner \) y \( \ulcorner x\in y\urcorner \).

Entre los convenios de notación específicos para \( \ulcorner\mathcal L_{\rm tc}\urcorner \), el más elemental es representar \( \ulcorner x\notin y\urcorner = \ulcorner \lnot(x\in y)\urcorner \).

Si concretamos las variables, por ejemplo,  \( \ulcorner x_1\notin x_2\urcorner \), vemos que, de acuerdo con las definiciones que hemos dado, se cumple que

\( \ulcorner \lnot(x_1\in x_2)\urcorner = (\ulcorner \lnot\urcorner,\ulcorner (\urcorner, \ulcorner \in\urcorner, \ulcorner x_1\urcorner, \ulcorner x_2\urcorner,\ulcorner )\urcorner) = (2, 32,128,3,9,64) \).

Insisto en que este desarrollo es irrelevante, pero no lo es mentalizarse de que, aunque parezca otra cosa, la expresión \( \ulcorner x_1\notin x_2\urcorner \) no representa ni más ni menos que una sucesión finita de números naturales.

Lenguaje y metalenguaje En este punto se vuelve necesaria una reflexión:

En el mensaje anterior empecé diciendo "Todos los resultados (de este hilo) se definen, enuncian y demuestran en ZF", pero, si nos planteamos cuál es todo el camino que hay que recorrer para llegar hasta ahí, el proceso es el siguiente:

  • Hay que definir el concepto de lenguaje formal, pero no en ZF, porque todavía no lo tenemos definido. Un lenguaje formal es un sistema de signos clasificados en categorías con los que podemos construir términos y fórmulas, etc.
  • Concretamente, hay que definir un lenguaje formal adecuado para construir la teoría de conjuntos, al que podemos llamar \( \mathcal L_{\rm tc} \), cuyo único signo opcional es un relator diádico \( \in \).
  • A continuación seleccionamos unas fórmulas de  \( \mathcal L_{\rm tc} \) a las que llamamos axiomas de ZF.
  • A continuación (o incluso antes) tenemos que definir qué entendemos por demostración a partir de unos axiomas dados, de modo que una demostración es una sucesión finita de fórmulas, cada una de las cuales es un axioma, o bien un axioma lógico (una lista adicional de axiomas que pueden usarse en cualquier momento) o bien se deduce de fórmulas anteriores mediante ciertas reglas precisas, como el modus ponens.
  • Con esto podemos demostrar teoremas en ZF, que son fórmulas de \( \mathcal L_{\rm tc} \), los cuales a su vez justifican la existencia de conjuntos que podemos definir, como la unión de dos conjuntos dados, la intersección, relaciones, funciones, los números naturales, sucesiones, etc.
  • Una vez contamos con todo esto podemos empezar con el primer mensaje de este hilo, donde se define el concepto de lenguaje formal y en particular, pasando ya a este segundo mensaje, podemos definir el lenguaje \( \ulcorner\mathcal L_{\rm tc}\urcorner \) que acabamos de presentar, y a partir de él sus términos, fórmulas, etc.

Esto nos obliga a distinguir entre el lenguaje \( \ulcorner\mathcal L_{\rm tc}\urcorner \) que acabamos de definir y el metalenguaje \( \mathcal L_{tc} \) que utilizamos para definir \( \ulcorner\mathcal L_{\rm tc}\urcorner \).

¿Cómo se define \( \mathcal L_{\rm tc} \)? La respuesta es que exactamente igual que \( \ulcorner\mathcal L_{\rm tc}\urcorner \). Si en el primer mensaje de este hilo suprimimos la advertencia de que vamos a trabajar en ZF y entendemos que, cuando hablamos de "números naturales" no nos referimos a los números naturales definidos en ZF, que son ciertos conjuntos, y que cuando hablamos de "signos" nos referimos a garabatos en un papel, y que cuando hablamos de sucesiones de signos nos referimos a signos puestos uno a continuación del otro, etc., todo lo dicho, literalmente, sin alterar una coma, simplemente cambiando la forma en que interpretamos lo que leemos, es la construcción metamatemática de los conceptos de lenguaje formal en general y del lenguaje \( \mathcal L_{\rm tc} \) en particular. Sin embargo no son lo mismo, porque no pueden ser lo mismo, y si alguien confunde \( \mathcal L_{\rm tc} \) con \( \ulcorner\mathcal L_{\rm tc}\urcorner \) llegará un momento en que no entenderá las cosas importantes.

La conclusión inevitable de estos hechos es que, en contra de lo que ingenuamente se podría pensar, la teoría axiomática ZF no sirve como fundamento de ciertos conceptos matemáticos básicos, como son los números naturales, las sucesiones, finitas, etc., sino que todos estos conceptos son necesarios para la construcción de ZF. Cuando en ZF definimos los números naturales, etc. no los estamos "introduciendo", sino que los estamos "reflejando", es decir, estamos creando en ZF una "copia" de unos conceptos que hemos tenido que precisar y estudiar previamente.

La forma en que es posible manejar estos conceptos metamatemáticos sin el apoyo de una teoría axiomática formal como es ZF es una cuestión sobre la que se puede filosofar mucho, pero no es el objeto de este hilo. Aquí me limito a subrayar la necesidad inexorable de distinguir entre \( \ulcorner\mathcal L_{\rm tc}\urcorner \) y \( \mathcal L_{\rm tc} \) y en el resto de este mensaje trataré de destacar lo que ello nos supone en la práctica, dejando de lado cualquier aspecto filosófico sobre el asunto.

Ejemplo
Consideremos, por ejemplo, la fórmula \( \exists x\forall y\ y\notin x \). Esta sentencia es un axioma de ZF, el llamado axioma del conjunto vacío. Es una de las sentencias de las que parten y a las que se reducen en última instancia todos los razonamientos matemáticos en todas las áreas: álgebra, análisis, geometría y, por supuesto, los razonamientos que podamos hacer aquí sobre lenguajes formales. Es una sentencia metamatemática, que no debemos confundir con la sentencia matemática \( \ulcorner\exists x\forall y\ y\notin x\urcorner \). Matemáticamente, esto último no es más que la sucesión siguiente de números naturales: \( (2,8,3,2,8,9,2,128,9,3,64) \). Ni siquiera podemos confundir el paréntesis \( ( \) que abre la expresión anterior y que indica que se trata de una sucesión con el número natural \( \ulcorner(\urcorner) = 32 \).

Por ejemplo, sería absurdo escribir:

\( (2,8,3,2,8,9,2,128,9,3,64) = 32,2,8,3,2,8,9,2,128,9,3,64,64 \).

En la "igualdad" anterior hemos cometido la aberración de sustituir dos paréntesis metamatemáticos (paréntesis del lenguaje \( \mathcal L_{\rm tc} \)) por dos paréntesis de \( \ulcorner\mathcal L_{\rm tc}\urcorner \), es decir, por los números naturales 32 y 64. El resultado es un disparate.
[cerrar]

Conceptos definidos Según hemos definido, el lenguaje de la teoría de conjuntos (tanto su versión metamatemática como su reflejo matemático) no tiene más signo opcional que el relator de pertenencia. Sin embargo, cuando los matemáticos usan \( \mathcal L_{tc} \) usan muchos más signos que el mero \( \in \). Por poner el caso más simple, es frecuente que escriban cosas como \( x\subset y \). ¿Qué es \( \subset \)? Esta pregunta admite respuestas distintas que corresponden a convenios distintos.

Una opción es responder que \( \subset \) es un relator diádico adicional. Esto supone que, bajo condiciones adecuadas, el lenguaje formal de una teoría axiomática puede enriquecerse con signos adicionales de forma no esencial, en el sentido de que toda fórmula que contenga estos signos adicionales es equivalente a otra que sólo contenga los signos primitivos del lenguaje formal. Por ejemplo, podemos introducir un relator diádico \( \subset \) en ZF estableciendo (por definición) la equivalencia:

\( x\subset y\leftrightarrow \forall u(u\in x\rightarrow u\in y) \)

Otra alternativa es considerar que al usar el signo \( \subset \) no estamos añadiendo realmente ningún signo nuevo al lenguaje \( \mathcal L_{\rm tc} \), sino que cuando escribimos \( x\subset y \) debemos entender que es una abreviatura, un abuso de lenguaje, para ahorrarnos escribir, \( \forall u(u\in x\rightarrow u\in y) \).

La diferencia es que el primer enfoque requiere hacer ciertas precisiones que a su vez permitan demostrar un (meta)teorema que justifique que, en efecto, todos los signos adicionales introducidos mediante definiciones pueden ser eliminados, de modo que al estudiar teóricamente los lenguajes formales podemos hacerlo como si tales signos nunca hubieran sido introducidos. Por el contrario, el segundo enfoque no requiere demostrar que los signos adicionales se pueden eliminar porque oficialmente nunca se les ha reconocido su existencia, relegada a meros convenios taquigráficos.

La situación es más delicada cuando los nuevos signos que introduce una definición son constantes o funtores. Pensemos, por ejemplo, en el conjunto vacío. ¿Qué clase de cosa es \( \emptyset \)? (No pregunto qué es el conjunto vacío, sino qué es el garabatito que usamos para representarlo.) Esta vez tenemos, no dos, sino tres respuestas posibles.

La primera opción es considerar que \( \emptyset \) es una constante que se añade al lenguaje \( \mathcal L_{\rm tc} \) a través de una definición, según la cual \( y = \emptyset \) es equivalente a \( \forall u\ u\notin y \).

Ahora es menos trivial justificar que toda fórmula que contenga la constante \( \emptyset \) es equivalente a otra que no la contenga, porque en principio la definición nos dice cómo sustituir las subfórmulas \( y = \emptyset \), pero no nos dice cómo eliminar la constante si aparece en otras posiciones, como \( \emptyset\in y \). Pese a ello, la eliminación es posible. Por ejemplo, esta fórmula equivale a \( \exists x(\forall u\ u\notin x\land x\in y) \). En general, estipulando las condiciones que han de darse para que sea legítimo introducir una constante o un funtor a través de una definición, es posible demostrar que todos los signos definidos pueden eliminarse para pasar a fórmulas equivalentes que sólo contengan los signos primitivos.

La segunda opción es considerar que \( \emptyset \) no existe oficialmente, de modo que toda fórmula que lo contenga tiene que verse como un abuso de notación que en realidad nombra a otra fórmula que no lo contiene. Esta opción es un poco más "escurridiza", pero tiene la ventaja de que no incorpora nuevos signos al lenguaje formal. Sólo nos exige que cada vez que usemos signos definidos nos responsabilicemos de saber decir lo mismo sin ellos, al menos en teoría.

Una opción intermedia es incluir en los lenguajes formales un signo adicional llamado descriptor, que nos permite construir términos como \( x\mid \forall u\ u\notin x \) (léase: el conjunto x tal que ningún conjunto u está en x). Esto complica un poco la definición de los conceptos de término y fórmula (porque si a partir de términos se pueden construir fórmulas atómicas, el descriptor permite construir términos a partir de fórmulas, con lo que los conceptos de término y fórmula se han de definir simultáneamente), pero a cambio nos permite considerar limpiamente que \( \emptyset \) es una abreviatura del término \( x\mid \forall u\ u\notin x \) y así tenemos la base necesaria para demostrar un teorema de eliminación de descriptores que nos asegura que toda fórmula con descriptores es equivalente a otra fórmula sin descriptores.

Todo lo que vamos a hacer aquí se puede hacer desde cualquiera de estos tres planteamientos. Si alguna vez puede afectar en algo el elegido, así lo indicaremos, pero en principio no vamos a entrar aquí en estas cuestiones "de bajo nivel" más allá de lo estrictamente imprescindible. En la práctica sólo debemos tener presente que si \( \phi \) es una fórmula metamatemática, es decir, del lenguaje \( \mathcal L_{\rm tc} \), entenderemos que \( \ulcorner \phi\urcorner \) representará su "reflejo" en \( \ulcorner \mathcal L_{\rm tc}\urcorner \), entendiendo que para calcular este reflejo previamente habrá que eliminar todos los signos definidos, lo cual se interpreta de una forma u otra según cómo se conciban los signos definidos.

Ejemplo
De este modo, entenderemos que \( \ulcorner 7\in \mathbb N\urcorner\in \mbox{Form}(\ulcorner \mathcal L_{\rm tc}\urcorner) \) es una cierta sucesión finita de números naturales en la que no aparecen más que los signos que tiene \( \ulcorner \mathcal L_{\rm tc}\urcorner \) según la definición que hemos dado. Cualquier otro signo adicional deberá ser eliminado previamente. Básicamente usamos que

\( 7\in \mathbb N\leftrightarrow \exists aA(a \) satisface la definición de \( 7 \land A  \) satisface la definición de \( \mathbb N \land a\in A) \),

donde, como conceptos matemáticos bien definidos, en las definiciones de \( 7 \) y de \( \mathbb N \) no aparecen \( 7 \) y \( \mathbb N \). Pueden aparecer, eso sí, otros conceptos previos, como \( 6 \), que a su vez deberán ser eliminados en un proceso que, tras un número finito de pasos, debe llevar a una fórmula sin signos definidos.

Todo esto puede hacerse con total rigor (a mi juicio, la forma más fácil de hacerlo es mediante descriptores), pero lo paso así por encima para evitar dedicar varios mensajes a lo que en realidad es una cuestión técnica de escasa importancia en la teoría de modelos que quiero presentar a partir de la entrega siguiente.
[cerrar]

Observaciones finales Con esto terminan las consideraciones previas que he estimado necesarias para presentar la teoría de modelos enfocada especialmente al estudio de modelos de la teoría de conjuntos. Al estudiar el lenguaje de la teoría de conjuntos desde el lenguaje de la teoría de conjuntos aparece la necesidad de distinguir entre lenguaje y metalenguaje, entre fórmulas metamatemáticas \( \phi \) y sus reflejos formales \( \ulcorner \phi\urcorner \).

Observemos que a la vista de una sentencia metamatemática como \( \exists x\forall y\ y\notin x \) estamos en condición de juzgar si es verdadera o falsa (o, al menos, de si podemos demostrarla o refutarla). En este caso concreto es trivialmente demostrable porque es un axioma. Sin embargo, con lo que hemos visto hasta aquí no tiene ningún sentido plantearse si \( \ulcorner\exists x\forall y\ y\notin x\urcorner \) es verdadero o falso o siquiera si es demostrable o refutable. Quien no lo reconozca así debe recordar que estamos hablando simplemente de la sucesión   \( (2,8,3,2,8,9,2,128,9,3,64) \) y ¿qué sentido tiene decir si esta sucesión es verdadera o falsa, demostrable o refutable?

Cuando "interpretamos" esa sucesión lo hacemos contemplándola en la forma \( \ulcorner\exists x\forall y\ y\notin x\urcorner \), lo que nos permite identificarla con la sentencia metamatemática \( \exists x\forall y\ y\notin x \) y en realidad es esta sentencia la que juzgamos. Pero hasta aquí no hemos dado ninguna definición matemática (que no requiera traducciones a sentencias metamatemáticas) de lo que significa que una sentencia = cierta sucesión de números sea verdadera o falsa, y eso es precisamente lo que conseguiremos a través del concepto de modelo.

17 Septiembre, 2012, 09:22 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Consideremos el lenguaje \( \mathcal L_A \) de la teoría de anillos. Entre sus signos está el funtor diádico \( \ulcorner +\urcorner \). Que sea un funtor diádico significa que necesita dos términos \( \ulcorner t_1\urcorner \) y \( \ulcorner t_2\urcorner \) para formar un nuevo término \( \ulcorner t_1+t_2\urcorner \). Podemos decir que \( \ulcorner +\urcorner \) se comporta como una función o, más exactamente, como el nombre de una posible función, pues en la definición de \( \mathcal L_A \) no hay ninguna función asociada a \( \ulcorner +\urcorner \), sino que éste es un simple número. El lenguaje formal "habla" de una posible función, y nos permite expresar propiedades de dicha función, a través de fórmulas como \( \ulcorner \forall xy(x+y = y+x)\urcorner \), pero no nos dice qué función es esa de la que está hablando. Mejor dicho, puede ser cualquiera. Similarmente, la constante \( \ulcorner 0\urcorner \) es el nombre de un objeto, pero el lenguaje \( \mathcal L_A \) no nos dice qué objeto se supone que está siendo nombrado por \( \ulcorner 0\urcorner \).

En general, las constantes de un lenguaje formal son nombres para objetos, los relatores son nombres para relaciones entre objetos y los funtores son nombres para funciones entre objetos, pero todos ellos están abiertos a cualquier interpretación. El concepto de modelo que vamos a introducir asigna una interpretación concreta a cada "nombre" acorde a su categoría (un objeto a cada constante, una relación a cada relator y una función a cada funtor):

Definición: Sea \( \mathcal L \) un lenguaje formal. Un modelo para \( \mathcal L \) es un par \( (M,I) \), donde \( M \) es un conjunto no vacío llamado universo del modelo e \( I \) es una función definida sobre el subconjunto de \( \mbox{Sig}(\mathcal L) \) formado por las constantes, los relatores y los funtores de \( \mathcal L \) de modo que se cumplen las propiedades siguientes:
  • Si \( c\in \mbox{Const}(\mathcal L) \) entonces \( I(c)\in M \). Diremos que \( I(c) \) es el objeto denotado por \( c \) en el modelo.
  • Si \( R\in \mbox{Rel}_n(\mathcal L) \), con \( n\geq 1 \), entonces \( I(R)\subset M^n \) y, concretamente, exigimos que \( I(\ulcorner =\urcorner) = \{(x,y)\in M\times M\mid x=y\} \). En otras palabras, la interpretación de un relator n-ádico es una relación n-ádica en \( M \) de modo que la relación asociada al igualador sea la de igualdad.
  • Si \( f\in \mbox{Fn}_n(\mathcal L) \), con \( n\geq 1 \), entonces \( I(f): M^n\longrightarrow M \). En otras palabras, la intepretación de un funtor n-ádico es una función de n variables.

En la práctica escribiremos \( M \) en lugar de \( (M,I) \), entendiendo que cada modelo \( M \) no es sólo un conjunto, sino que tiene asociada una función de interpretación \( I \).

Ejemplos
Para determinar un modelo del lenguaje \( \mathcal L_A \) debemos especificar:
  • Un conjunto \( M \) no vacío.
  • Dos objetos \( 0, 1\in M \), de modo que \( I(\ulcorner 0 \urcorner)=0,\ \ I(\ulcorner 1\urcorner) = 1 \).
  • Una función \( -: M\longrightarrow M \), de modo que \( I(\ulcorner -\urcorner) = - \).
  • Dos leyes de composición interna \( +: M\times M\longrightarrow M \) y \( \cdot: M\times M\longrightarrow M \), de modo que \( I(\ulcorner +\urcorner)=+ \) e \( I(\ulcorner\cdot \urcorner) = \cdot \).

Una vez hechas estas asignaciones ya podemos decir que (con respecto a ellas) las constantes, los relatores y los funtores de \( \mathcal L_A \) tienen un significado concreto.



Para determinar un modelo del lenguaje \( \ulcorner \mathcal L_{\rm tc}\urcorner \) sólo necesitamos especificar un conjunto no vacío \( M \) y una relación \( R\subset M\times M \), de modo que \( I(\ulcorner \in\urcorner) = R \). Por ello, en la práctica es frecuente considerar que un modelo de \( \ulcorner \mathcal L_{\rm tc}\urcorner \) es un par \( (M,R) \) con \( R\subset M\times M \), lo cual no es un modelo en el sentido exacto de la definición general, pero determina unívocamente un tal modelo haciendo \( I(\ulcorner \in\urcorner)=R \).

Fijado un modelo, el signo \( \ulcorner \in\urcorner \), que en principio es un mero nombre para una posible relación binaria, pasa a tener una interpretación concreta, a saber, la relación \( R \).
[cerrar]

Vemos, pues, que un modelo deja sin interpretar los signos lógicos y las variables de un lenguaje formal. No interpretamos los signos lógicos porque les vamos a asignar siempre la misma interpretación, independiente del modelo, y no interpreta las variables por el motivo opuesto: porque nos interesa que las variables puedan variar su significado dentro de un modelo fijo.

Para asignar una interpretación a cada variable usaremos un concepto auxiliar:

Definición Una valoración en un modelo \( M \) de un lenguaje formal \( \mathcal L \) es cualquier aplicación \( v: \mbox{Var}(\mathcal L)\longrightarrow M \).

Así, consideraremos que una valoración asigna un significado temporal a cada variable del lenguaje. Si \( x\in \mbox{Var}(\mathcal L) \) y \( a\in M \), llamaremos \( v_x^a: \mbox{Var}(\mathcal L)\longrightarrow M \) a la valoración que coincide con \( v \) excepto por que \( v_x^a(x) = a \).

Llamaremos \( \mbox{Val}(\mathcal L, M) \) al conjunto de todas las valoraciones de \( \mathcal L \) en \( M \).

Objetos denotados por términos Fijado un modelo \( M \) de un lenguaje formal \( \mathcal L \) y una valoración \( v\in \mbox{Val}(\mathcal L, M) \), podemos asignar a cada término \( t \) de \( \mathcal L \) un objeto \( M(t)[v]\in M \) al que llamaremos objeto denotado por \( t \) en \( M \) respecto de \( v \).

La definición se da por recurrencia. En primer lugar definimos una aplicación \( f_0: \mbox{Term}_0(\mathcal L)\longrightarrow M \) como sigue: recordemos que los términos de orden 0 son las variables y las constantes de \( \mathcal L \), luego podemos definir \( f_0(\ulcorner x\urcorner) = v(\ulcorner x\urcorner) \) si \( \ulcorner x\urcorner \) es una variable y \( f_0(\ulcorner c\urcorner) = I(\ulcorner c\urcorner) \) si \( \ulcorner c\urcorner \) es una constante.

En resumen, el objeto denotado por una variable es el que le asigna la valoración, y el denotado por una constante es el que le asigna la función de interpretación del modelo.

Supuesta definida una función \( f_k: \mbox{Term}_k(\mathcal L)\longrightarrow M \), definimos como sigue una función \( f_{k+1}:\mbox{Term}_{k+1}(\mathcal L)\longrightarrow M \).

Recordemos que un término \( \ulcorner t\urcorner\in \mbox{Term}_{k+1}(\mathcal L) \) puede estar en dos circunstancias: o bien \( \ulcorner t\urcorner\in \mbox{Term}_k(\mathcal L) \), en cuyo caso definimos \( f_{k+1}(\ulcorner t\urcorner) = f_k(\ulcorner t\urcorner) \) o, si no se da este caso, necesariamente \( \ulcorner t\urcorner = \ulcorner ft_1\ldots t_m\urcorner \), donde los \( \ulcorner t_i\urcorner \) son términos de orden \( k \) (sobre los que está definida \( f_k \)) y \( \ulcorner f\urcorner \) es un funtor \( m \)-ádico, que tiene asocidada la función \( I(\ulcorner f\urcorner) \). Definimos entonces

\( f_{k+1}(\ulcorner t\urcorner) = I(\ulcorner f\urcorner)(f_k(\ulcorner t_1\urcorner), \ldots, f_k(\ulcorner t_m\urcorner)) \).

En palabras: el objeto denotado por \( \ulcorner ft_1\cdots t_m\urcorner \) es el que resulta de hacer actuar la función denotada por el funtor \( \ulcorner f\urcorner \) a los objetos denotados por los términos \( \ulcorner t_i\urcorner \).

Por construcción cada \( f_{k+1} \) extiende a \( f_k \), por lo que la sucesión \( \{f_k\}_{k=0}`\infty \) induce una única función \( f: \mbox{Term}(\mathcal L)\longrightarrow M \). Es esta función la que representaremos por \( M(\ )[v] \).

De la construcción se deduce inmediatamente:

  • Si \( \ulcorner x\urcorner \) es una variable, entonces \( M(\ulcorner x\urcorner)[v] = v(\ulcorner x\urcorner). \)
  • Si \( \ulcorner c\urcorner \) es una constante, entonces \( M(\ulcorner c\urcorner)[v] = I(\ulcorner c\urcorner) \).
  • Si \( f \) es un funtor \( m \)-ádico, entonces \( M(\ulcorner ft_1\ldots t_m\urcorner)[v] = I(\ulcorner f\urcorner)(M(\ulcorner t_1\urcorner)[v], \ldots, M(\ulcorner t_m\urcorner)[v]) \).

Para probar el tercer punto basta tomar el mínimo natural \( l \) tal que \( \ulcorner ft_1\ldots t_m \urcorner\in \mbox{Term}_l(\mathcal L) \). Como el término no es una variable ni una constante, no puede ser \( l = 0 \), luego \( l=k+1 \) y podemos aplicar la definición de \( f_{k+1} \).

Ejemplo
Consideremos el modelo de \( \mathcal L_A \) definido como sigue: el universo es \( M = \mathbb Z \), \( I(\ulcorner 0\urcorner) = 0,\ \ I(\ulcorner 1\urcorner) = 1 \), las funciones denotadas por \( \ulcorner +\urcorner \) y \( \cdot \) son la suma y el producto usual en los números enteros, y la función denotada por \( \ulcorner -\urcorner \) es la función \( \mathbb Z\longrightarrow \mathbb Z \) dada por \( a\mapsto -a \).

Entonces dada cualquier valoración \( v:\mbox{Var}(\mathcal L_A)\longrightarrow \mathbb Z \), se cumple que \( M(\ulcorner (1+1)\cdot x+1\urcorner)[v] = 2v(\ulcorner x\urcorner)+1 \).

En efecto, basta ir aplicando sucesivamente la definición anterior:

\( M(\ulcorner (1+1)\cdot x+1\urcorner)[v] = M(\ulcorner (1+1)\cdot x\urcorner)[v]+M(\ulcorner 1\urcorner)[v] =  \) \( M(\ulcorner 1+1\urcorner)[v]\cdot M(\ulcorner x\urcorner)[v]+1 =  \) \(  (M(\ulcorner 1\urcorner)[v]+M(\ulcorner 1\urcorner)[v])v(\ulcorner x\urcorner)+1 = (1+1)v(\ulcorner x\urcorner)+1 = 2v(\ulcorner x\urcorner)+1 \).

En la práctica, basta tener en cuenta que la definición de "denotación" es "la que tiene que ser" y, si de un golpe de vista vemos que \( \ulcorner (1+1)\cdot x+1\urcorner \) significa "dos veces lo que sea x más uno", pues eso será lo que denote este término.
[cerrar]

Satisfacción de fórmulas Ahora vamos a definir lo que significa que una fórmula sea verdadera o falsa en un modelo. Para ello vamos a definir una función \( f: \mbox{Form}(\mathcal L)\times \mbox{Val}(\mathcal L,M)\longrightarrow \{0,1\} \) de modo que \( f(\ulcorner \alpha\urcorner, v)=1 \) si y sólo si la fórmula \( \ulcorner \alpha\urcorner \) es verdadera en \( M \) cuando sus variables se interpretan mediante \( v \). Para ello definiremos recurrentemente funciones \( f_k: \mbox{Form}_k(\mathcal L)\times \mbox{Val}(\mathcal L,M)\longrightarrow \{0,1\} \).

Recordemos que toda fórmula de orden \( 0 \) es una fórmula atómica, es decir, de la forma \( \ulcorner Rt_1\ldots t_m\urcorner \), donde \( \ulcorner R\urcorner \) es un relator \( m \)-ádico y los \( \ulcorner t_i\urcorner \) son términos.

Entonces podemos definir \( f_0(\ulcorner Rt_1\ldots, t_m\urcorner,v) = 1 \) si y sólo si \( I(R)(M(\ulcorner t_1\urcorner)[v],\ldots, M(\ulcorner t_m\urcorner)[v]) \).

En palabras: una fórmula atómica es verdadera si y sólo si los objetos denotados por sus términos satisfacen la relación denotada por el relator.

Supongamos definida la función \( f_k: \mbox{Form}_k(\mathcal L)\times \mbox{Val}(\mathcal L,M)\longrightarrow \{0,1\} \) y recordemos que una fórmula \( \ulcorner \phi\urcorner \) de orden \( k+1 \) puede encontrarse en varios casos. El más simple es que sea una fórmula de orden \( k \), en cuyo caso definimos \( f_{k+1}(\ulcorner \phi\urcorner, v) = f_k(\ulcorner \phi\urcorner,v) \).

Si no se da este caso, quedan las posibilidades siguientes:
  • Si \( \ulcorner \phi\urcorner = \ulcorner \lnot\alpha\urcorner \), para cierta fórmula \( \ulcorner \alpha\urcorner\in \mbox{Form}_k(\mathcal L) \), entonces definimos \( f_{k+1}(\ulcorner \lnot\alpha\urcorner, v) = 1-f_k(\ulcorner \alpha\urcorner, v) \), es decir, \( \ulcorner \lnot\alpha\urcorner \) es verdadera si y sólo si \( \ulcorner \alpha\urcorner \) es falsa.
  • Si \( \ulcorner \phi\urcorner = \ulcorner \alpha\rightarrow\beta\urcorner \), para ciertas fórmulas \( \ulcorner \alpha\urcorner, \ulcorner \beta\urcorner\in \mbox{Form}_k(\mathcal L) \), entonces definimos \( f_{k+1}(\ulcorner \alpha\rightarrow\beta\urcorner,v) = 1 \) si y sólo si \( f_k(\ulcorner \alpha,v\urcorner) = 0 \) o bien \( f_k(\ulcorner \beta\urcorner,v)=1 \), es decir, \( \ulcorner \alpha\rightarrow\beta\urcorner \) es verdadera cuando, si lo es \( \ulcorner \alpha\urcorner \), también lo es \( \ulcorner \beta\urcorner \).
  • Si \( \ulcorner \phi\urcorner = \ulcorner \forall x\alpha\urcorner \), para cierta variable \( \ulcorner x\urcorner \) y cierta fórmula \( \ulcorner \alpha\urcorner\in \mbox{Form}_k(\mathcal L) \), entonces definimos \( f_{k+1}(\ulcorner \forall x\alpha\urcorner,v)=1 \) si y sólo si para todo \( a\in M \) se cumple \( f_k(\ulcorner \alpha\urcorner,v_x^a)=1 \), es decir, \( \ulcorner \forall x\alpha\urcorner \) es verdadera si y sólo si \( \ulcorner \alpha\urcorner \) es verdadera para cualquier interpretación en \( M \) de la variable \( \ulcorner x\urcorner \).

Por construcción, la función \( f_{k+1} \) extiende a la función \( f_k \), por lo que la sucesión de funciones \( \{f_k\}_{k=0}^\infty \) define una única función \( f: \mbox{Form}(\mathcal L)\times \mbox{Val}(\mathcal L,M)\longrightarrow \{0,1\} \).

Definimos \( M\vDash\phi[v]\leftrightarrow f(\phi,v)=1 \), y diremos que \( M \) satisface la fórmula \( \phi\in \mbox{Form}(\mathcal L) \) respecto de la valoración \( v \).

En términos de la relación de satisfacción, la construcción anterior se expresa en los términos siguientes:

  • \( M\vDash \ulcorner Rt_1\ldots t_m\urcorner[v]\leftrightarrow I(R)(M(\ulcorner t_1\urcorner)[v],\ldots, M(\ulcorner t_m\urcorner)[v]) \).
  • \( M\vDash \ulcorner \lnot\alpha\urcorner[v]\leftrightarrow \lnot M\vDash \ulcorner \alpha\urcorner[v] \).
  • \( M\vDash \ulcorner \alpha\rightarrow\beta\urcorner[v]\leftrightarrow (M\vDash \ulcorner \alpha\urcorner[v]\rightarrow M\vDash \ulcorner \beta\urcorner[v]) \).
  • \( M\vDash \ulcorner \forall x\alpha\urcorner[v]\leftrightarrow \forall a\in M\ M\vDash \ulcorner \alpha\urcorner [v_x^a] \).

La segunda propiedad es la que expresa que \( \ulcorner\lnot \urcorner \) se interpreta como una negación, la tercera que \( \ulcorner \rightarrow\urcorner \) se interpreta como "implica" y la cuarta es la que expresa que \( \ulcorner \forall\urcorner \) se interpreta como "para todo". Notemos que cada signo logico de \( \mathcal L \) en la parte izquierda queda asociado así al signo lógico metamatemático correspondiente en la parte derecha.

Nota
Veamos con más detalle el significado de la condición relativa al cuantificador \( \forall \). Lo que afirma es que \( M\vDash \forall x\,\alpha \) se cumple si \( M\vDash \ulcorner \alpha\urcorner[v_x^a \) se cumple para todo \( a\in M \), es decir, si se cumple \( \ulcorner \alpha\urcorner \) para toda interpretación posible \( a \) para la variable \( \ulcorner x\urcorner \), es decir, sea cual sea el significado que le demos a  \( \ulcorner x\urcorner \).

Por ejemplo, si \( \ulcorner \alpha\urcorner = \ulcorner Rx\urcorner \), donde \( \ulcorner R\urcorner \) es un relator monádico, tenemos que

\( M\vDash \ulcorner \forall x\,Rx\urcorner[v] \) \( \leftrightarrow \forall a\in M\ M\vDash \ulcorner Rx\urcorner[v_x^a]\leftrightarrow \forall a\in M\ I(R)(a) \).

En suma, se cumple \( M\vDash \ulcorner \forall x\,Rx\urcorner[v] \) si y sólo si todo \( a\in M \) cumple la relación \( I(\ulcorner R\urcorner) \), que es lo que cabía esperar.

Aquí puede verse otro ejemplo.
[cerrar]

A partir de aquí es fácil demostrar lo siguiente:

  • \( M\vDash \ulcorner \alpha\lor \beta\urcorner[v]\leftrightarrow M\ulcorner \alpha\urcorner[v]\lor M\vDash \ulcorner\beta \urcorner[v] \).
  • \( M\vDash \ulcorner \alpha\land\beta\urcorner[v]\leftrightarrow M\vDash \ulcorner \alpha\urcorner[v]\land M\vDash \ulcorner\beta \urcorner[v] \).
  • \( M\vDash \ulcorner \alpha\leftrightarrow \beta\urcorner[v]\leftrightarrow (M\vDash \ulcorner \alpha\urcorner[v]\leftrightarrow M\vDash \ulcorner \beta\urcorner[v]) \).
  • \( M\vDash \ulcorner \exists x\alpha\urcorner[v]\leftrightarrow \exists a\in M\ M\vDash \ulcorner \alpha\urcorner[v_x^a] \).

Por ejemplo, recordando que, por definición (por abuso de lenguaje) \( \ulcorner \alpha\lor\beta\urcorner = \ulcorner \lnot\alpha\rightarrow \beta\urcorner \), tenemos que

\( M\vDash \ulcorner \alpha\lor\beta\urcorner[v]\leftrightarrow (M\vDash \lnot\alpha[v]\rightarrow M\vDash \ulcorner \beta\urcorner[v])\leftrightarrow (\lnot M\vDash \ulcorner \alpha\urcorner[v]\rightarrow M\vDash \ulcorner \beta\urcorner[v]) \) \( \leftrightarrow M\vDash \ulcorner \alpha\urcorner[v]\lor M\vDash \ulcorner \beta\urcorner[v]. \)

Observaciones
Notemos que, en la definición recurrente de \( f_{k+1} \), para definir \( f_{k+1}(\ulcorner \forall x\alpha\urcorner[v]) \) hemos usado que teníamos definida \( f_k \), no sólo para \( (\ulcorner \alpha\urcorner, v) \), sino para todos los pares \( (\ulcorner \alpha\urcorner, w) \), donde \( w \) es cualquier otra valoración, no necesariamente \( v \), ya que necesitamos saber si \( \ulcorner \alpha\urcorner \) es satisfecha o no por cualquiera de las valoraciones \( v_x^a \). Por eso, para definir recurrentemente \( M\vDash \ulcorner \alpha\urcorner[v] \) no podíamos fijar una valoración \( v \) y definir funciones \( f_k: \mbox{Form}_k(\mathcal L)\longrightarrow \{0,1\} \), sino que teníamos que incluir el conjunto de todas las valoraciones en el dominio de las \( f_k \).

Este detalle técnico es crucial, porque es la razón por la cual en ZFC, o en NBG no es posible definir \( M\vDash \alpha[v] \) cuando \( M \) es una clase propia, sino que tenemos que exigir que \( M \) sea un conjunto, como hemos hecho en la definición de modelo.

En efecto, si generalizamos la noción de modelo para permitir que el universo \( M \) sea una clase propia, cuando esto sucede la clase \( \mbox{Val(\mathcal L), M)} \) de todas las valoraciones en \( M \) es también una clase propia, y las \( f_k \) también serían clases propias por serlo su dominio. Esto hace que no pueda definirse la sucesión \( \{f_k\}_k \), ya que ello exigiría que las \( f_k \) fueran conjuntos. No obstante, se puede intentar un "truco":

Definimos

\( A =\{k\in \mathbb N\mid \exists f\ (f: \mbox{Form}_k(\mathcal L)\times \mbox{Val}(\mathcal L, M)\longrightarrow \{0,1\}\land \cdots)\} \)
donde los puntos suspensivos representan la fórmula que dice que \( f \) cumple las propiedades que caracterizan a \( f_k \), es decir, que sobre las fórmulas atómicas actúa como hemos definido \( f_0 \), que sobre las negaciones actúa como corresponde, que sobre las implicaciones actúa como corresponde, etc.

Es fácil probar que si \( k\in A \) entonces existe una única clase propia \( f \) que cumple las propiedades requeridas, y que si \( f \) las cumple para \( k \) entonces existe otra clase  \( f' \) que extiende a \( f \) y las cumple para \( k+1 \). Por inducción concluimos que \( A= \mathbb N \), luego podemos definir

\( M\vDash \phi[v]\leftrightarrow \exists k\in \mathbb N\exists f (\phi\in \mbox{Form}_k(\mathcal L)\land f: \mbox{Form}_k(\mathcal L)\times \mbox{Val}(\mathcal L, M)\longrightarrow \{0,1\} \) \( \land \cdots \land f(\phi,v)=1) \),
donde nuevamente los puntos suspensivos significan lo mismo que en la definición de \( A \). De este modo hemos definido la relación \( M\vDash\phi[v] \) que cumple exactamente las mismas propiedades que la que hemos definido para conjuntos, pero...

¡Esta construcción no puede hacerse en ZFC ni en NBG! La razón es que el conjunto \( A\subset \mathbb N \) está definido mediante una fórmula en la que el cuantificador \( \exists f \) se aplica a una clase \( f \) que necesariamente es una clase propia ¡y ésa es precisamente la frontera entre NBG y MK! En NBG el axioma de formación de clases exige que las fórmulas a las que se aplican tengan todas sus variables ligadas restringidas a conjuntos, mientras que en MK no se impone esta condición. Por lo tanto, el conjunto \( A \) está bien definido en MK, pero no en NBG. En MK sí que es posible definir modelos que sean clases propias, pero en NBG no, luego en ZFC tampoco, ya que NBG y ZFC son teorías totalmente equivalentes.
[cerrar]

Teorema La relación \( M\vDash\ulcorner \phi\urcorner[v] \) sólo depende de cómo actúa \( v \) sobre las variables libres en \( \ulcorner \phi\urcorner \).

Demostración
En esta prueba hay que tener presente que no hemos dado explícitamente la definición de variable libre en una fórmula, pero en el fondo se deduce de lo que vamos a decir.

Primeramente hemos de probar que si \( \ulcorner t\urcorner \) es un término de \( \mathcal L \), entonces \( M(\ulcorner t\urcorner)[v] \) depende únicamente de la restricción de \( v \) a las variables que aparecen en \( \ulcorner t\urcorner \). En otros términos, que si \( v \) y \( w \) son dos valoraciones que coinciden sobre las variables de \( \ulcorner t\urcorner \), entonces \( M(\ulcorner t\urcorner)[v]=M(\ulcorner t\urcorner)[w] \).

Lo razonamos por inducción sobre la longitud de \( \ulcorner t\urcorner \). Si el término tiene longitud \( 1 \), o bien es una variable o bien una constante. Si es una variable, \( \ulcorner t\urcorner=\ulcorner x\urcorner \), entonces por hipótesis \( v(\ulcorner x\urcorner)=w(\ulcorner x\urcorner) \) y

\( M(\ulcorner t\urcorner)[v] = v(\ulcorner x\urcorner) = w(\ulcorner x\urcorner)=M(\ulcorner t\urcorner)[w] \).

Si \( \ulcorner t\urcorner = \ulcorner c\urcorner \), entonces \( \ulcorner t\urcorner \) no tiene variables, luego no suponemos ninguna coincidencia entre \( v \) y \( w \), pero aun así:

\( M(\ulcorner t\urcorner)[v]=I(c) = M(\ulcorner t\urcorner)[w] \).

Si suponemos cierta la propiedad para términos de longitud menor que la longitud de \( \ulcorner t\urcorner \), entonces, si \( \ulcorner t\urcorner \) no es una variable o una constante (casos ya tratados), tiene que ser de la forma \( \ulcorner t\urcorner = \ulcorner ft_1\cdots t_n\urcorner \), donde \( \ulcorner f\urcorner \) es un funtor \( n \)-ádico y \( \ulcorner t_i\urcorner \) son términos (de menor longitud).

Si \( v \) y \( w \) coinciden en las variables que aparecen en \( \ulcorner t\urcorner \), en particular coinciden sobre las variables de cada \( \ulcorner t_i\urcorner \), luego por hipótesis de inducción \( M(\ulcorner t_i\urcorner)[v]=M(\ulcorner t_i\urcorner)[w] \), luego

\( M(\ulcorner t\urcorner)[v] = I(\ulcorner f\urcorner)(M(\ulcorner t_1\urcorner)[v],\ldots, M(\ulcorner t_n\urcorner)[v]) =  \) \( I(\ulcorner f\urcorner)(M(\ulcorner t_1\urcorner)[w],\ldots, M(\ulcorner t_n\urcorner)[w] = M(\ulcorner t\urcorner)[w] \).

Ahora probamos el teorema por inducción sobre la longitud de \( \ulcorner \phi\urcorner \). Suponemos el teorema cierto para fórmulas de longitud menor que la de \( \ulcorner \phi\urcorner \).

Si \( \ulcorner \phi\urcorner = \ulcorner Rt_1,\ldots, t_n\urcorner \), donde \( \ulcorner R\urcorner \) es un relator \( n \)-ádico y \( \ulcorner t_i\urcorner \) son términos, las variables libres de \( \ulcorner \phi\urcorner \) son por definición todas las variables que aparecen en los términos, luego si \( v \) y \( w \) son valoraciones que coinciden sobre ellas, por lo que acabamos de probar sabemos que \( M(\ulcorner t_i\urcorner)[v] = M(\ulcorner t_i\urcorner)[w] \), luego

\( M\vDash \ulcorner \phi\urcorner[v]\leftrightarrow I(\ulcorner R\urcorner)(M(\ulcorner t_1\urcorner)[v],\ldots, M(\ulcorner t_n\urcorner)[v]) \) \( \leftrightarrow I(\ulcorner R\urcorner)(M(\ulcorner t_1\urcorner)[w],\ldots, M(\ulcorner t_n\urcorner)[w])\leftrightarrow M\vDash \ulcorner \phi\urcorner[w] \).

Si \( \ulcorner \phi\urcorner = \ulcorner \lnot\psi\urcorner \), entonces las variables libres de \( \ulcorner \phi\urcorner \) son por definición las mismas que las de \( \ulcorner \psi\urcorner \), pero \( \psi \) tiene longitud menor, luego por hipótesis de inducción, si \( v \) y \( w \) coinciden sobre dichas variables se cumple que \( M\vDash \ulcorner \psi\urcorner[v]\leftrightarrow M\vDash \ulcorner \psi\urcorner[w] \). Por lo tanto

\( M\vDash \ulcorner \phi\urcorner[v]\leftrightarrow \lnot M\vDash \ulcorner \psi\urcorner[v]\leftrightarrow  \) \( \lnot M\vDash \psi[w]\leftrightarrow M\vDash \ulcorner \phi\urcorner[w] \).

Dejamos el caso \( \ulcorner \phi\urcorner = \ulcorner \psi\rightarrow \chi\urcorner \) porque es análogo (se cumple por definición que las variables libres de \( \ulcorner \phi\urcorner \) son la unión de las variables libres en \( \ulcorner \psi\urcorner \) y las variables libres en \( \ulcorner \chi\urcorner \)).

Veamos por último el caso en que \( \ulcorner \phi\urcorner = \ulcorner \forall x\psi\urcorner \). Entonces las variables libres de \( \ulcorner \phi\urcorner \) son las variables libres de \( \ulcorner \psi\urcorner \) menos \( \ulcorner x\urcorner \). Así pues, suponemos que \( v \) y \( w \) conciden sobre las variables libres de \( \ulcorner \psi\urcorner \) salvo a lo sumo \( \ulcorner x\urcorner \). Entonces

\( M\vDash \ulcorner \phi\urcorner[v]\leftrightarrow \forall a\in M\ M\vDash \ulcorner \psi\urcorner[v_x^a] \) \( \leftrightarrow \forall a \in M\ M\vDash \ulcorner \psi\urcorner [w_x^a]\leftrightarrow M\vDash \ulcorner \phi\urcorner[w] \),

donde hemos aplicado la hipótesis de inducción a la fórmula \( \ulcorner \psi\urcorner \) y a las valoraciones \( v_x^a \) y \( w_x^a \), que coinciden sobre todas las variables libres en \( \psi \), porque sobre \( \ulcorner x\urcorner \) ambas toman el valor \( a \) y sobre las demás variables coinciden porque así les sucede a \( v \) y a \( w \).
[cerrar]

Esto implica que si \( \ulcorner \phi(x_1,\ldots, x_n)\urcorner \) es una fórmula cuyas variables libres están entre las indicadas explícitamente, entonces, dados \( a_1,\ldots, a_n\in M \), podemos definir \( M\vDash \ulcorner \phi\urcorner[a_1,\ldots, a_n] \) como \( M\vDash \ulcorner \phi\urcorner[v] \), siendo \( v \) cualquier valoración que cumpla \( v(\ulcorner x_i\urcorner)=a_i \).

Fórmulas verdaderas y falsas Diremos que una fórmula \( \alpha \) de un lenguaje formal \( \mathcal L \) es verdadera en un modelo \( M \) de \( \mathcal L \) (y lo representaremos mediante \( M\vDash \alpha \)) si \( M\vDash \alpha[v] \) para toda valoración \( v \), es decir, si es satisfecha con cualquier interpretación de las variables.

Diremos que \( \alpha \) es falsa en \( M \) si \( \lnot M\vDash \phi[v] \) para toda valoración \( v \), es decir, si no es satisfecha se interpreten como se interpreten las variables. Equivalentemente, \( \alpha \) es falsa si y sólo si \( \lnot\alpha \) es verdadera, y viceversa.

Ejemplo
Consideremos el modelo \( M \) de \( \mathcal L_A \) de universo \( \mathbb Z \) que hemos definido antes. Entonces \( M\vDash\ulcorner x+y=y+x\urcorner \), pues sean cuales sean los dos números enteros que usemos para interpretar sus variables, se va a cumplir \( M\vDash \ulcorner x+y=y+x\urcorner[v] \), pues esto equivale a que \( v(\ulcorner x\urcorner)+v(\ulcorner y\urcorner) = v(\ulcorner y\urcorner)+v(\ulcorner x\urcorner) \).

Por el contrario, la fórmula \( \ulcorner x\cdot 0 = 1\urcorner \) es falsa, pues \( M\vDash \ulcorner x\cdot 0=1\urcorner[v] \) equivale a que \( v(\ulcorner x\urcorner)\cdot 0 = 1 \), y ningún número entero que podamos asignar a \( \ulcorner x\urcorner \) cumple esto.

A su vez, la fórmula \( \ulcorner x+y=1\urcorner \) no es ni verdadera  ni falsa en \( M \), pues según cómo interpretemos las variables, será satisfecha o no.

Lo que nunca puede suceder en un modelo es que una fórmula sea verdadera y falsa a la vez, pues eso significaría que es satisfecha con todas las valoraciones y a la vez no es satisfecha con ninguna valoración.
[cerrar]

Puesto que \( M\vDash \alpha[v] \) sólo depende de cómo actúa \( v \) sobre las variables libres en \( \alpha \), si \( \alpha \) es una sentencia, es decir, si no tiene variables libres, o bien es satisfecha por todas las valoraciones, o bien no es satisfecha por ninguna. Por consiguiente:

Teorema Una sentencia siempre es verdadera o falsa en un modelo (pero no ambas cosas).

Demostración
Acabamos de ver que si dos valoraciones \( v \) y \( w \) coinciden sobre las variables libres de una fórmula \( \ulcorner\alpha\urcorner \), entonces \( M\vDash \ulcorner \alpha\urcorner[v]\leftrightarrow M\vdash \ulcorner \alpha\urcorner[w] \). Por lo tanto, si \( \alpha \) no tiene variables libres, la equivalencia anterior vale para dos valoraciones cualesquiera. En otras palabras, que si se cumple \( M\vDash \ulcorner \alpha\urcorner[v] \) para una cierta valoración, entonces lo mismo vale para cualquier otra.

En particular, si \( \ulcorner \alpha\urcorner \) es una sentencia, tenemos dos posibilidades: la primera es que, fijada una valoración \( v \), se cumpla \( M\vDash \ulcorner \alpha\urcorner[v] \), en cuyo caso lo mismo vale para toda \( v \) y, por definición, eso significa que \( M\vDash \ulcorner\alpha\urcorner \) (es decir, que \( \ulcorner\alpha\urcorner \) es verdadera en \( M \))

La otra posibilidad es que, para la valoración fijada \( v \) se cumpla \( \lnot M\vDash \ulcorner \alpha\urcorner[v] \), en cuyo caso lo mismo vale para todas las valoraciones, y eso es lo que significa que \( \ulcorner\alpha\urcorner \) es falsa en \( M \).
[cerrar]

Teorema Si \( \ulcorner \alpha\urcorner \) es cualquier fórmula de un lenguaje formal \( \mathcal L \), \( \ulcorner x\urcorner \) es cualquier variable y \( M \) es un modelo de \( \mathcal L \), entonces \( M\vDash \ulcorner \alpha\urcorner\leftrightarrow M\vDash \ulcorner \urcorner\forall x\,\alpha \).

Demostración
Si \( M\vDash \ulcorner \alpha\urcorner \), entonces, para toda valoración \( v \), se cumple \( M\vDash \ulcorner \alpha\urcorner[v] \). En particular, para todo \( a\in M \), esto se aplica a la valoración \( v_x^a \), luego tenemos que \( \forall a\in M\ M\vDash \ulcorner \alpha\urcorner[v_x^a] \), pero esto significa que \( M\vDash \ulcorner \forall x\, \alpha\urcorner[v] \) y, como esto vale para toda valoración \( v \), concluimos que \( M\vDash \ulcorner \forall x\,\alpha\urcorner \).

La implicación contraria es similar.
[cerrar]

De aquí se sigue que una fórmula es verdadera si y sólo si lo es la sentencia que resulta de ligar todas sus variables libres con cuantificadores universales, o de añadirle cuantificadores triviales (sobre variables que no aparezcan en la fórmula), lo cual no afecta a su interpretación.

18 Septiembre, 2012, 01:52 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Aunque mi intención es centrarme en los modelos de la teoría de conjuntos, no está de más observar algunos ejemplos en otros contextos para advertir la generalidad del concepto de "modelo".

Definición Sea \( \mathcal L \) un lenguaje formal, \( M \) un modelo de \( \mathcal L \) y \( \Gamma\subset \mbox{Form}(\mathcal L) \). Diremos que \( M \) es un modelo de \( \Gamma \), y lo expresaremos \( M\vDash \Gamma \) si todas las fórmulas de \( \Gamma \) son verdaderas en \( M \).

Ejemplo 1 Consideremos el lenguaje \( \mathcal L_A \) de la teoría de anillos y sean

\( \gamma_1 = \ulcorner \forall xyz((x+y)+z=x+(y+z))\urcorner \),

\( \gamma_2 =  \ulcorner \forall x (x+0=x)\urcorner \),

\( \gamma_3 =  \ulcorner \forall x (x+(-x)=0)\urcorner \),

\( \gamma_4 =  \ulcorner \forall xy(x+y = y+x)\urcorner \),

\( \gamma_5 =  \ulcorner \forall xyz( (xy)z = x(yz))\urcorner \),

\( \gamma_6 =  \ulcorner \forall x\ (x\cdot 1 =x\land 1\cdot x = x\urcorner \),

\( \gamma_7 =  \ulcorner \forall xyz(x(y+z) = xy+xz\land (y+z)x = yz+zx\urcorner \).

El conjunto de los axiomas de anillo es \( \mbox{AxAn} = \{\gamma_1,\gamma_2,\gamma_3,\gamma_4,\gamma_5,\gamma_6, \gamma_7\} \).

Ahora observamos que el concepto algebraico de anillo (unitario) es equivalente al de modelo de los axiomas de anillo. En efecto, si \( M\vDash \mbox{AxAn} \), entonces \( +=I( \ulcorner +\urcorner) \) y \( \cdot = I( \ulcorner \cdot\urcorner) \) son dos leyes de composición interna en el conjunto \( M \), y el hecho de que los axiomas de anillo sean verdaderos en \( M \) se traduce en que \( (M,+,\cdot) \) es un anillo unitario.

Recíprocamente, si \( (A, +, \cdot) \) es un anillo unitario arbitrario, podemos convertirlo en un modelo de los axiomas de anillo sin más que interpretar \(  \ulcorner +\urcorner \) y \(  \ulcorner \cdot \urcorner \) como la suma y el producto en \( A \), las constantes \(  \ulcorner 0\urcorner \) y \(  \ulcorner 1\urcorner \) como el cero y el uno del anillo y el funtor \(  \ulcorner -\urcorner \) como la función \( a\mapsto -a \).

Ejemplo 2 Definimos el lenguaje \( \mathcal L_G \) de la teoría de grupos como el lenguaje cuyos signos opcionales son una constante \(  \ulcorner 1\urcorner \), un funtor diádico \(  \ulcorner \cdot\urcorner \) y un funtor monádico \(  \ulcorner f\urcorner \), aunque en lugar de \(  \ulcorner ft\urcorner \) escribiremos \( t^{-1} \), para todo término \(  \ulcorner t\urcorner \).

Definimos el conjunto de axiomas de grupo como el conjunto \( \mbox{AxG} \) formado por las tres sentencias \(  \ulcorner \forall xyz\ (xy)z = x(yz)\urcorner \),   \(  \ulcorner \forall x(x\cdot 1 = x\land 1\cdot x = x)\urcorner \),    \( \ulcorner \forall x(x\cdot x^{-1}=1\land x^{-1}\cdot x = 1)\urcorner \).

Es inmediato comprobar que los grupos se pueden identificar con los modelos de los axiomas de grupo exactamente en el mismo sentido que en el ejemplo anterior.

Ejemplo 3 Sea ahora \( \mathcal L_o \) un lenguaje formal con un único relator diádico (aparte del igualador) que representaremos por \(  \ulcorner \leq\urcorner \). El conjunto de los axiomas de orden (total) es el formado por las sentencias

\(  \ulcorner \forall x\ x\leq x\urcorner \),   \(  \ulcorner \forall xy(x\leq y\land y\leq x\rightarrow x=y)\urcorner \),   \( \ulcorner\forall xyz(x\leq y\land y\leq z\rightarrow x\leq z)\urcorner \),   \( \ulcorner\forall xy(x\leq y\lor y\leq x)\urcorner \).

Claramente, los conjuntos totalmente ordenados se identifican con los modelos de los axiomas de orden.

Vemos así que un modelo es una "estructura generalizada", en el sentido de que no tiene que tener una cantidad fija de funciones y relaciones, como ocurre con los anillos, los grupos, los conjuntos ordenados, etc., sino que todas estas estructuras, cada cual con su sistema de relaciones y funciones, pueden verse como casos particulares del concepto de modelo.

El "ejemplo" que nos va a interesar aquí es el siguiente:

Ejemplo 4 Llamaremos \( \ulcorner \mbox{ZFC}\urcorner\subset \mbox{Form}(\ulcorner \mathcal L_{\rm tc}\urcorner \) al conjunto  \( \ulcorner \mbox{ZFC}\urcorner =\{\ulcorner \mbox{ext}\urcorner, \ulcorner \mbox{par}\urcorner, \ulcorner \mbox{vacío}\urcorner, \ulcorner \mbox{unión}\urcorner, \ulcorner \mbox{AP}\urcorner, \ulcorner \mbox{AI}\urcorner, \ulcorner \mbox{V=R}\urcorner,\ulcorner \mbox{AE}\urcorner\}\cup \ulcorner \mbox{Reemplazo}\urcorner \), donde

\( \ulcorner \mbox{ext}\urcorner = \ulcorner \forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y)\urcorner \),

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

\( \ulcorner \mbox{vacío}\urcorner =\ulcorner \exists x\forall y\ y\notin x\urcorner \),

\( \ulcorner \mbox{unión}\urcorner = \ulcorner \forall x\exists y\forall u(u\in y\leftrightarrow \exists v (u\in v\land v\in x))\urcorner \),

\( \ulcorner \mbox{AP}\urcorner = \ulcorner \forall x\exists y\forall u(u\in y\leftrightarrow u\subset x)\urcorner \),

\( \ulcorner \mbox{AI}\urcorner = \ulcorner \exists x(\emptyset \in x\land \forall y(y\in x\rightarrow y\cup\{y\}\in x))\urcorner \),

\( \ulcorner \mbox{V=R}\urcorner = \ulcorner \forall x(x\neq\emptyset\rightarrow \exists y(y\in x\land y\cap x = \emptyset))\urcorner \),

\( \ulcorner \mbox{AE}\urcorner = \ulcorner \forall x\exists f(f \mbox{ es una función de dominio }x\land  \) \( \forall u(u\in x\land u\neq \emptyset\rightarrow f(u)\in u))\urcorner \),

\( \ulcorner \mbox{Reemplazo}\urcorner = \{\ulcorner \forall uvw(\alpha(u,w)\land \alpha(v,w)\rightarrow u=v)\rightarrow \forall x\exists y\forall v(v\in y\leftrightarrow \exists u(u\in x\land \alpha(u,v)))\urcorner\mid \ulcorner\alpha\urcorner\in \mbox{Form}(\mathcal L_{\rm st})\} \).

El objetivo de este hilo es familiarizar al lector con los modelos de \( \ulcorner \mbox{ZFC}\urcorner \), es decir, con los pares \( (M,R) \), donde \( M \) es un conjunto no vacío y \( R\subset M\times M \), tales que \( (M,R)\vDash \ulcorner \mbox{ZFC}\urcorner \).

Observemos que acabamos de definir \( \ulcorner\mbox{ZFC}\urcorner \) dentro de ZFC. Es un ejemplo claro de la necesidad de distinguir entre las definiciones matemáticas como la de \( \ulcorner\mbox{ZFC}\urcorner \) y las definiciones metamatemáticas como la de ZFC. ¡Necesitamos definir ZFC antes de poder definir \( \ulcorner\mbox{ZFC}\urcorner \)!

18 Septiembre, 2012, 12:24 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Como último preliminar antes de entrar en el estudio de los modelos conviene tener presente la relación entre la teoría de modelos y la teoría de la demostración. Trataré de describirla en este hilo dejando sin demostración el resultado principal porque requeriría entrar en la teoría de la demostración con mucho más detalle que la descripción superficial que voy a dar aquí.

Añadido posteriormente: Una demostración del teorema de completitud puede verse en este artículo de la Revista del Foro.

Deducciones A cada lenguaje formal \( \mathcal L \) se le puede asociar un conjunto de fórmulas llamadas axiomas lógicos. Concretamente, el conjunto \( \mbox{AxL}(\mathcal L) \) está formado por las seis familias de fórmulas siguientes, donde \( \ulcorner \alpha\urcorner \), \( \ulcorner \beta\urcorner \), \( \ulcorner \gamma\urcorner \) son fórmulas arbitrarias de \( \mathcal L \) y \( \ulcorner t\urcorner \) es un término arbitrario de \( \mathcal L \):

\( \ulcorner \alpha\rightarrow (\beta\rightarrow\alpha)\urcorner \)

\( \ulcorner (\alpha\rightarrow (\beta\rightarrow\gamma))\rightarrow ((\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow \gamma)\urcorner \)

\( \ulcorner (\lnot\alpha\rightarrow\lnot\beta)\rightarrow (\beta\rightarrow \alpha)\urcorner \)

\( \ulcorner \forall x\alpha(x)\rightarrow \alpha(t)\urcorner \)

\( \ulcorner \forall x(\alpha\rightarrow \beta(x))\rightarrow (\alpha\rightarrow \forall x\beta(x))\urcorner \) (una fórmula de este tipo es, por definición, un axioma lógico si y sólo si la variable \( \ulcorner x\urcorner \) no está libre en \( \ulcorner \alpha\urcorner \)).

\( \ulcorner \forall x(x=t\rightarrow \alpha(x))\rightarrow \alpha(t)\urcorner \) (supuesto que \( \ulcorner x\urcorner \) no esté libre en el término \( \ulcorner t\urcorner \)).

Una deducción a partir de un conjunto de premisas \( \Gamma\subset \mbox{Form}(\mathcal L) \) es una sucesión finita \( \alpha_1,\ldots, \alpha_n \) de fórmulas de \( \mathcal L \) tal que cada una de ellas es un axioma lógico, una premisa o bien una consecuencia de una o dos fórmulas precedentes por una de las dos reglas de inferencia siguientes:

Modus ponens: de \( \ulcorner \alpha\rightarrow \beta\urcorner \) y \( \ulcorner \alpha\urcorner \) es consecuencia lógica \( \ulcorner \beta\urcorner \).

Generalización: de \( \ulcorner \alpha\urcorner \) es consecuencia lógica \( \ulcorner\forall x\alpha\urcorner \).

Más en general, se dice que una fórmula \( \ulcorner \alpha\urcorner \) es consecuencia lógica de un conjunto de premisas \( \Gamma \), y se representa \( \Gamma\vdash \ulcorner \alpha\urcorner \), si existe una deducción con premisas en \( \Gamma \) cuya última fórmula es \( \ulcorner \alpha\urcorner \).

Este concepto de deducción es, en principio, arbitrario, en el sentido de que alguien podría preguntarse por qué no tomamos otros axiomas lógicos u otras reglas de inferencia. Sin embargo, la definición es razonable porque admite una caracterización que excluye toda arbitrariedad:

Teorema de completitud semántica (Gödel) Sea \( \mathcal L \) un lenguaje formal, sea \( \Gamma\subset \mbox{Form}(\mathcal L) \) y sea \( \ulcorner \alpha\urcorner\in \mbox{Form}(\mathcal L) \). Entonces \( \Gamma\vdash \ulcorner \alpha\urcorner \) si y sólo si \( \ulcorner \alpha\urcorner \) es verdadera en todos los modelos de \( \Gamma \).

De este modo, cualquier sistema alternativo de axiomas o de reglas de inferencia será igualmente aceptable en lugar del que hemos dado siempre y cuando permita llegar a esta misma caracterización, que viene a decir que deducir una fórmula a partir de unas premisas equivale a garantizar que siempre que las premisas sean verdaderas (en un modelo), la conclusión que hemos extraído de ellas será necesariamente verdadera (en el mismo modelo).

De las dos implicaciones del teorema de completitud, hay una que es fácil de probar (algo laboriosa, pero fácil): Si suponemos que \( \Gamma\vdash\ulcorner \alpha\urcorner \) y que \( M\vDash \Gamma \), es fácil probar que \( M\vDash\ulcorner \alpha\urcorner \).

Demostración
El primer paso para ello es probar que los axiomas lógicos que hemos dado son lógicamente válidos, es decir, son verdaderos en cualquier modelo. Eso es una comprobación rutinaria, que para las dos últimas familias de axiomas requiere ciertos resultados previos sobre la relación entre la satisfacción en un modelo y la sustitución de un término en una fórmula. Por ejemplo, para un axioma del primer tipo, se trata de probar que, para toda valoración \( v \), se cumple

\( M\vDash \ulcorner(\alpha\rightarrow(\beta\rightarrow\alpha)\urcorner[v] \),

pero esto equivale, por definición de satisfacción, a que

\( M\vDash \ulcorner \alpha\urcorner[v]\rightarrow (M\vDash \ulcorner \beta\urcorner[v]\rightarrow M\vDash \ulcorner \alpha\urcorner[v]) \),

lo cual es cierto, pues una afirmación verdadera es implicada por cualquier afirmación. Para los demás se procede de forma similar.

Una vez tenemos esto, podemos considerar una deducción \( \ulcorner\alpha_1\urcorner,\ldots, \ulcorner\alpha_n\urcorner \) de \( \ulcorner\alpha\urcorner \) a partir de \( \Gamma \). Como \( \ulcorner\alpha_n\urcorner=\ulcorner\alpha\urcorner \), basta probar que \( M\vDash \ulcorner\alpha_i\urcorner \) por inducción sobre \( i \).

Necesariamente \( \ulcorner\alpha_1\urcorner \) es un axioma lógico (en cuyo caso sabemos que es verdadero en \( M \)) o bien una premisa (en cuyo caso es verdadero en \( M \) por hipótesis) y, en general, si ya suponemos que \( M\vDash \ulcorner\alpha_j\urcorner \) para todo \( j<i \), entonces \( \ulcorner\alpha_i\urcorner \) es, o bien un axioma lógico o una premisa, en cuyo caso es verdadero en \( M \) como en el caso inicial, o bien es una consecuencia de fórmulas anteriores (luego verdaderas en \( M \)) por una de las dos reglas de inferencia. Así pues, sólo necesitamos comprobar que ambas reglas de inferencia pasan de fórmulas verdaderas en un modelo a fórmulas verdaderas en un modelo.

Esto ya lo hemos comentado para el caso de la regla de generalización: \( M\vDash \ulcorner \alpha\urcorner \) si y sólo si \( M\vDash \ulcorner\forall x\alpha\urcorner \).

En cuanto al modus ponens, si \( M\vDash \ulcorner\alpha\rightarrow \beta\urcorner \) y \( M\vDash \ulcorner \alpha\urcorner \), entonces, para toda valoración \( v \) tenemos que \( M\vDash \ulcorner \alpha\rightarrow \beta\urcorner[v] \) y \( M\vDash \ulcorner \alpha\urcorner[v] \), y lo primero es equivalente a la implicación

\( M\vDash \ulcorner \alpha\urcorner[v]\rightarrow M\vDash \ulcorner \beta\urcorner[v] \),

luego concluimos que \( M\vDash \ulcorner \beta\urcorner[v] \) para toda \( v \), luego \( M\vDash \ulcorner\beta \urcorner \).
[cerrar]

Esto significa que si \( M \) es un modelo de un conjunto de fórmulas \( \Gamma \), entonces \( M \) satisface automáticamente todas las consecuencias lógicas de \( \Gamma \).

La parte difícil del teorema de completitud semántica es una consecuencia sencilla de otro resultado:

Teorema (Gödel) Un conjunto de fórmulas \( \Gamma \) es consistente si y sólo si tiene un modelo.

Aquí definimos \( \mbox{Consis}\,\Gamma\leftrightarrow \lnot\Gamma\vdash \ulcorner x\neq x\urcorner \) (y es fácil ver que, más en general, \( \Gamma \) es consistente si y sólo si de \( \Gamma \) no puede deducirse una fórmula y también su negación).

De nuevo, este teorema tiene una implicación fácil: Si \( \Gamma \) tiene un modelo, entonces es consistente.

Demostración
Supongamos que \( M\vDash \Gamma \). Si \( \Gamma \) no fuera consistente entonces \( \Gamma\vDash \ulcorner x\neq x\urcorner \), luego, según hemos probado, \( M\vDash \ulcorner x\neq x\urcorner \), luego, dada cualquier valoración \( v \), tendríamos que \( \Gamma\vDash \ulcorner x\neq x\urcorner[v] \), lo que significa que \( v(x)\neq v(x) \), contradicción.
[cerrar]

Veamos cómo la implicación no trivial del teorema de completitud se deduce de este segundo teorema:

Demostración
Basta probar que si \( \lnot \Gamma\vdash \ulcorner \alpha\urcorner \), entonces \( \ulcorner \alpha\urcorner \) no es verdadera en cierto modelo de \( \Gamma \). Por simplicidad lo probaremos en el caso en que \( \ulcorner \alpha\urcorner \) es una sentencia (es decir, no tiene variables libres). El caso general se obtiene de éste con algunas manipulaciones sencillas.

Un resultado elemental de la teoría de la demostración dice que si  \( \lnot \Gamma\vdash \ulcorner \alpha\urcorner \) entonces \( \Gamma\cup\{\ulcorner \lnot\alpha\urcorner\} \) es consistente (aquí se usa que \( \ulcorner \alpha\urcorner \) es una sentencia). Por el teorema de Gödel, existe un modelo \( M \) tal que \( M\vDash \Gamma\cup\{\ulcorner \lnot\alpha\urcorner\} \). En particular \( M\vDash \Gamma \), luego \( M \) es un modelo de \( \Gamma \) en el que \( \ulcorner \lnot\alpha\urcorner \) es verdadera, luego \( \ulcorner \alpha\urcorner \) es falsa.
[cerrar]

Conexión con el teorema de incompletitud El segundo teorema de incompletitud de Gödel, en el caso particular de ZFC, puede enunciarse como sigue:

Segundo teorema de incompletitud de Gödel: Si ZFC es consistente, entonces en ZFC no puede demostrarse \( \mbox{Consis}\, \ulcorner \mbox{ZFC}\urcorner \).

En realidad esto vale para cualquier teoría de conjuntos que cumpla los siguientes requisitos mínimos:
  • Que sea recursiva (es decir, que exista un procedimiento práctico para reconocer qué fórmulas son axiomas de la teoría y cuáles no lo son),
  • Que en la teoría puedan definirse los números naturales y demostrarse los axiomas de Peano,
  • Que en la teoría puedan definirse los conceptos de lenguaje formal, deducción, modelo etc. y demostrarse sus propiedades elementales.

Esto vale, por ejemplo, para ZF. En particular combinando esto con el teorema de Gödel mencionado antes, tenemos:

Teorema Si ZFC (o cualquier teoría similar) es consistente, entonces en ZFC no puede demostrarse la existencia de un modelo de \( \ulcorner \mbox{ZFC}\urcorner \).

Así pues, decíamos que el objeto de este hilo es estudiar los modelos de \( \ulcorner \mbox{ZFC}\urcorner \) ¡y acabamos de demostrar que no puede demostrarse que exista ninguno! Veremos que esto es menos grave de lo que parece.

Consecuencias metamatemáticas
La definición de deducción que hemos dado es el "reflejo" matemático de la definición metamatemática (o una de las muchas definiciones equivalentes posibles) de deducción que forma parte de la definición de ZFC, es decir, para que todo lo que estamos diciendo aquí tenga sentido, primero es necesario considerar la definición de deducción que acabamos de dar como una definición metamatemática, lo que nos define el concepto de "teorema de ZFC" como consecuencia lógica de los axiomas de ZFC, lo que nos permite empezar a demostrar teoremas en ZFC y es en este contexto en el que podemos demostrar los teoremas de ZFC que estamos considerando aquí.

Tenemos, pues, dos conceptos de deducción formalmente idénticos, uno metamatemático y otro matemático, y la relación es la obvia: si \( \alpha_1,\ldots, \alpha_n \) es una sucesión de fórmulas metamatemáticas de \( \mathcal L_{tc} \) que constituyen una demostración (metamatemática) a partir de los axiomas de ZFC (u otra teoría similar que sepamos definir dentro de ZFC), entonces en ZFC podemos probar que  \( \ulcorner \alpha_1\urcorner,\ldots, \ulcorner \alpha_n\urcorner \) es una deducción de \( \ulcorner \alpha \urcorner \) a partir de \( \ulcorner \mbox{ZFC}\urcorner \).

Nota
Esta última afirmación es un hecho inmediato, no un teorema profundo. La idea es la siguiente: tomemos un axioma lógico (metamatemático), por ejemplo, de la forma \( \alpha\rightarrow (\beta\rightarrow\alpha) \). Entonces, ¿no es inmediato que \( \ulcorner \alpha\rightarrow(\beta\rightarrow\alpha)\urcorner \) es un axioma lógico (matemático)? Pues lo mismo vale para todos los axiomas.

Igualmente, tomemos un axioma de ZFC, por ejemplo, \( \exists x\forall y\ y\notin x \). ¿No es inmediato a partir de la definición de \( \ulcorner \mbox{ZFC}\urcorner \) que \( \ulcorner\exists x\forall y\ y\notin x \urcorner\in \ulcorner \mbox{ZFC}\urcorner \)? Pues lo mismo vale para todos los demás axiomas.

Y también, si una fórmula metamatemática \( \beta \) se deduce por modus ponens de otras dos, es porque estas dos son de la forma \( \alpha\rightarrow \beta \) y \( \alpha \) y, entonces, ¿no es obvio que \( \ulcorner \beta\urcorner \) se deduce por modus ponens de \( \ulcorner \alpha\rightarrow\beta\urcorner \) y \( \alpha \)? Lo mismo vale para la regla de generalización.

Por lo tanto, si \( \alpha_1,\ldots, \alpha_n \) es una deducción metamatemática a partir, de los axiomas de ZFC, cada \( \alpha_i \) es un axioma lógico (en cuyo caso sabemos probar que \( \ulcorner \alpha_i\urcorner\in \mbox{AxL}(\mathcal L_{\rm tc} \)), o bien \( \alpha_i \) es un axioma de ZFC, en cuyo caso sabemos probar que \( \ulcorner \alpha_i\urcorner\in \ulcorner \mbox{ZFC}\urcorner \), o bien \( \alpha_i \) se deduce de fórmulas anteriores por una de las dos reglas de inferencia, en cuyo caso sabemos probar que a \( \ulcorner \alpha_i\urcorner \) le ocurre lo mismo.
[cerrar]

Consecuentemente, si \( \mbox{ZFC}\vdash \alpha \) es decir, si \( \alpha \) es un teorema de ZFC, (de los que vienen en los libros, como el teorema del valor medio o el teorema de Galois), entonces \( \mbox{ZFC}\vdash \ulcorner \mbox{ZFC}\urcorner\vdash \ulcorner \alpha\urcorner \). En particular, en todo modelo de \( \ulcorner\mbox{ZFC} \urcorner \) son verdaderos (los reflejos de) todos los teoremas de ZFC.

Para terminar observamos que los resultados que hemos visto aquí explican por qué no puede existir un razonamiento "convincente" que asegure la consistencia de ZFC. Sabemos que ZFC es suficientemente potente como para que en su seno pueda formalizarse cualquier argumento que a un matemático le parece lógicamente aceptable. Si fuera posible argumentar la consistencia de ZFC, sería posible considerar esa argumentación como un teorema de ZFC, y habríamos probado \( \mbox{Consis}\ulcorner \mbox{ZFC}\urcorner \) en ZFC, y el teorema de incompletitud de Gödel dice que eso es imposible. Más aún, su prueba es constructiva, en el sentido de que se puede programar a un ordenador para que si le damos una demostración de  \( \mbox{Consis}\ulcorner \mbox{ZFC}\urcorner \) en ZFC el ordenador calcule a partir de ella la demostración de una contradicción en ZFC.

19 Septiembre, 2012, 11:21 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Según hemos visto, el concepto de modelo de un lenguaje formal generaliza a diversas estructuras, como la de grupo, anillo, conjunto ordenado, etc. Vamos a introducir ahora el concepto correspondiente al de homomorfismo de grupos, anillos, etc.

Definición Dados dos modelos \( M \) y \( N \) de un mismo lenguaje formal \( \mathcal L \), una inmersión \( i: M\longrightarrow N \) es una aplicación que cumpla las propiedades siguientes:
  • Para cada constante \( c \) de \( \mathcal L \), se cumple que \( i(I_M(c)) = I_N(c) \).
  • Para cada relator \( n \)-ádico \( R \) de \( \mathcal L \) y cada \( x_1,\ldots, x_n\in M \), se cumple que \( I_M(R)(x_1,\ldots,x_n)\leftrightarrow I_N(R)(i(x_1),\ldots, i(x_n)) \),
  • Para cada funtor \( n \)-ádico \( f \) de \( \mathcal L \) y cada \( x_1,\ldots, x_n\in M \) se cumple que \( i(I_M(f)(x_1,\ldots, x_n)) = I_N(f)(i(x_1),\ldots, i(x_n)) \).

Ejemplo
Si \( M \) y \( N \) son dos anillos unitarios (considerados como modelos del lenguaje \( \mathcal L_A \)), lo que dice la primera propiedad es que \( i(0) = 0,\ \ i(1) = 1 \) (la inmersión transforma el objeto denotado por la constante \( \ulcorner 0\urcorner \) en \( M \) por el objeto denotado en \( N \), y lo mismo con el uno).

La tercera propiedad dice que \( i(x+y) = i(x)+i(y),\ \ i(xy) = i(x)i(y) \) (la inmersión transforma la ley de composición denotada por el funtor \( \ulcorner +\urcorner \) en \( M \) en la ley de composición que denota en \( N \)), así como que \( i(-x) = -i(x) \) (la inmersión transforma la operación \( x\mapsto -x \) de \( M \) en la operación correspondiente en \( N \).

Por lo tanto, las inmersiones entre modelos de \( \mathcal L_A \) son homomorfismos de anillos, pero, más aún, son monomorfismos de anillos, a causa del siguiente hecho general:
[cerrar]

Toda inmersión de modelos es inyectiva (de ahí el nombre de inmersión). Ello se debe a la segunda propiedad aplicada al igualador, según la cual, teniendo en cuenta que, por definición de modelo \( I_M(\ulcorner =\urcorner), \ \ I_N(\ulcorner =\urcorner) \) son respectivamente la identidad en \( M \) y en \( N \), se traduce en que \( x=y\leftrightarrow i(x)=i(y) \).

Ejemplo (continuación)
Es fácil ver que las inmersiones entre anillos, vistos como modelos del lenguaje de la teoría de anillos (unitarios), son exactamente los monomorfismos de anillos (unitarios), las inmersiones entre grupos, vistos como modelos del lenguaje de la teoría de grupos, son exactamente los monomorfismos de grupos, las inmersiones entre conjuntos ordenados, vistos como modelos del lenguaje de la teoría de conjuntos ordenados, son las aplicaciones inyectivas y crecientes, etc. Para incluir en términos de modelos el concepto más general de homomorfismo de grupos o de anillos, etc. habría que considerar lenguajes formales sin igualador, pero no nos va a interesar ese caso.
[cerrar]

Se comprueba sin dificultad que la composición de dos inmersiones de modelos es de nuevo una inmersión.

Definición Un isomorfismo de modelos es una inmersión biyectiva. Diremos que dos modelos son isomorfos, y lo expresaremos mediante \( M\cong N \) si existe un isomorfismo \( i: M\longrightarrow N \).

Se comprueba sin dificultad que la identidad es un isomorfismo de un modelo en sí mismo, que la inversa de un isomorfismo de modelos es también un isomorfismo y que la composición de isomorfismos es también un isomorfismo.

Es claro que dos anillos son isomorfos (como anillos) si y sólo si son isomorfos como modelos del lenguaje de la teoría de anillos, e igualmente con grupos, etc.

Definición Sea \( M \) un modelo de un lenguaje formal \( \mathcal L \). Diremos que un subconjunto \( N\subset M \) es un submodelo de \( M \) si:
  • Para toda constante \( c \) de \( \mathcal L \) se cumple que \( I_M(c)\in N \).
  • Para todo funtor \( n \)-ádico \( f \) de \( \mathcal L \) y todos los \( x_1,\ldots, x_n\in N \) se cumple que \( I_M(f)(x_1,\ldots, x_n)\in N \).

Ejemplo
Si \( M \) es un anillo unitario, visto como modelo del lenguaje de la teoría de anillos, un subconjunto \( N\subset M \) es un submodelo si y sólo si contiene a \( 0, 1 \) (por la primera propiedad) y si la suma y el producto de dos elementos de \( N \) está en \( N \), así como que el opuesto de un elemento de \( N \) está en \( N \). Por lo tanto los submodelos de \( M \) son simplemente los subanillos de \( M \).
[cerrar]

Si \( N \) es un submodelo de \( M \), podemos dotarlo de estructura de modelo de \( \mathcal L \) del modo siguiente:
  • Para cada constante \( c \) de \( \mathcal L \), definimos \( I_N(c) = I_M(c) \) (que está en \( N \) por definición de submodelo.
  • Para cada relator \( n \)-ádico \( R \) de \( \mathcal L \) definimos la relación \( I_N(R)(x_1,\ldots, x_n)\leftrightarrow I_M(R)(x_1,\ldots, x_n) \). Observemos que cuando el relator es el igualador la relación así definida es la identidad en \( N \), como exige la definición de modelo.
  • Para cada funtor \( n \)-ádico \( f \) de \( \mathcal L \) definimos \( I_N(f) \) como la función dada por \( I_N(f)(x_1,\ldots, x_n)=I_M(f)(x_1,\ldots, x_n) \), que es un elemento de \( N \) por definición de submodelo.

Con esta definición, es inmediato que la inclusión \( i: N\longrightarrow M \) es una inmersión de modelos. Recíprocamente, si \( N \) y \( M \) son modelos de un lenguaje formal \( \mathcal L \) de modo que \( N\subset M \) y la inclusión es una inmersión, entonces \( N \) es un submodelo de \( M \).

En definitiva, un submodelo de un modelo es un subconjunto que contenga a los objetos denotados por las constantes del lenguaje y que sea cerrado para las funciones denotadas por los funtores del lenguaje. Notemos que los relatores no imponen ninguna condición. Por eso cualquier subconjunto de un conjunto ordenado hereda una estructura de cuerpo ordenado (porque la estructura está definida por una relación), mientras que no todos los subconjuntos de un anillo, o de un grupo, heredan estructura de anillo o grupo, porque la estructura está definida por funciones.

En general, si \( i: M\longrightarrow N \) es una inmersión de modelos y llamamos \( N_0 = i[M] \), es fácil ver que \( N_0 \) admite una única estructura de submodelo de \( N \) con la cual \( i: M\longrightarrow N_0 \) es un isomorfismo de modelos. Recíprocamente, todo isomorfismo de un modelo \( M \) en un submodelo \( N_0 \) de un modelo \( N \) es una inmersión \( M\longrightarrow N \).

Las inmersiones cumplen una propiedad ligeramente más general que la que exige la definición:

Teorema Sea \( i:M\longrightarrow N \) una inmersión entre modelos de un lenguaje formal \( \mathcal L \). Entonces, para cada término \( t \) de \( \mathcal L \) cuyas variables libres estén entre \( x_1,\ldots, x_n \) y todos los \( a_1,\ldots, a_n\in M \) se cumple que \( i(M(t)[a_1,\ldots, a_n]) = N(t)[i(a_1),\ldots, i(a_n)] \).

Es decir, la imagen del objeto denotado por un término cuando sus variables se interpretan como \( a_1,\ldots, a_n \) es el objeto denotado por el término en el segundo modelo cuando sus variables se interpretan como \( i(a_1),\ldots, i(a_n) \).

Demostración
Por inducción sobre el orden del término. Si el término tiene orden \( 0 \) es una variable o una constante. Si es la variable \( x_i \), entonces \( M(x_i)[a_1,\ldots, a_n]= a_i \), mientras que \( N(x_i)[i(a_1),\ldots, i(a_n)]=i(a_i) \), luego se cumple el teorema.

Si es una constante \( c \), entonces \( M(c)[a_1,\ldots, a_n] = I_M(c) \) y \( N(c)[i(a_1),\ldots, i(a_n)] = I_N(c) \), y la relación \( i(I_M(c)) = I_N(c) \) se cumple por la definición de inmersión.

Supongamos el teorema cierto para términos de orden \( k \). Si el término \( t \) tiene orden \( k+1 \), entonces \( t = ft_1\cdots t_m \), donde \( f \) es un funtor \( m \)-ádico de \( \mathcal L \) y \( t_i \) son términos de orden \( \leq k \). Entonces

\( i(M(t)[a_1,\ldots, a_n]) = i(I_M(f)(M(t_1)[a_1,\ldots, a_n], \ldots M(t_m)[a_1,\ldots, a_n])) \) \( =I_N(f)(i(M(t_1)[a_1,\ldots, a_n]), \ldots i(M(t_m)[a_1,\ldots, a_n])) \)

\( = I_N(f)(N(t_1)[i(a_1),\ldots, i(a_n)],\ldots, N(t_m)[i(a_1),\ldots, i(a_n)]) = N(t)[i(a_1), \ldots, i(a_n)] \),

donde hemos usado la definición del objeto denotado por un término, la definición de inmersión, la hipótesis de inducción y de nuevo la definición del objeto denotado por un término.
[cerrar]

Cabe preguntarse si se cumple el análogo para fórmulas, es decir, si en las condiciones del teorema, si \( \phi \) es una fórmula cuyas variables libres están entre \( x_1,\ldots, x_n \), se cumple que \( M\vDash \phi[a_1,\ldots, a_n]\leftrightarrow N\vDash \phi[i(a_1),\ldots, i(a_n)] \). La respuesta es claramente negativa.

Ejemplo
Pensemos por ejemplo en un grupo no abeliano \( G \) y sea \( g\in G \) un elemento que no conmute con todos los elementos de \( G \). Sea \( H \) el subgrupo generado por \( g \). Entonces \( H \) es cíclico y \( g \) conmuta con todos los elementos de \( H \). La inclusión \( i: H\longrightarrow G \) es una inmersión de modelos del lenguaje de la teoría de grupos, pero si llamamos \( \phi(x) = \ulcorner \forall y(xy=yx)\urcorner \), tenemos que \( H\vDash \phi[g] \), pero no \( G\vDash \phi[i(g)] \).
[cerrar]

No obstante, esta propiedad la cumplen, como era de esperar, los isomorfismos de modelos:

Teorema Sea \( i: M\longrightarrow N \) un isomorfismo de modelos de un lenguaje \( \mathcal L \) y sea \( \phi(x_1,\ldots, x_n) \) una fórmula cuyas variables libres estén entre \( x_1,\ldots, x_n \). Entonces, para todo \( a_1,\ldots, a_n\in M \) se cumple \( M\vDash \phi[a_1,\ldots, a_n]\leftrightarrow N\vDash \phi[i(a_1),\ldots, i(a_n)] \).

Demostración
Puesto que, según hemos visto, \( M\vDash \phi[a_1,\ldots, a_n] \) sólo depende de los \( a_i \) tales que la variable \( x_i \) está libre en \( \phi \), no perdemos generalidad si probamos el teorema bajo la hipótesis de que todas las variables \( x_i \) están libres en \( \phi \) (pues las que no lo están se pueden eliminar y obtenemos un enunciado equivalente).

Razonamos por inducción sobre el orden de \( \phi \). Si \( \phi \) tiene orden \( 0 \) es una fórmula atómica, de la forma \( Rt_1\ldots t_m \), donde \( R \) es un relator \( m \)-ádico y \( t_i \) son términos. Entonces

\( M\vDash \phi[a_1,\ldots, a_n]\leftrightarrow I_M(R)(M(t_1)[a_1,\ldots, a_n], \ldots , M(t_m)[a_1,\ldots, a_n]) \) \( \leftrightarrow I_N(R)(i(M(t_1)[a_1,\ldots, a_n]), \ldots, i(M(t_m)[a_1,\ldots, a_n])) \)

\( \leftrightarrow I_N(R)(N(t_1)(i(a_1),\ldots, i(a_n)),\ldots, N(t_1)(i(a_1),\ldots, i(a_n))) \) \( \leftrightarrow N\vDash \phi[i(a_1),\ldots, i(a_n)] \),

donde hemos usado la definición de satisfacción, la definición de inmersión, el teorema precedente y de nuevo la definición de satisfacción.

Supongamos el teorema cierto para fórmulas de orden \( k \) y que \( \phi \) tiene orden \( k+1 \). Hay tres posibilidades:

1) \( \ulcorner \phi\urcorner = \ulcorner\lnot\psi\urcorner \) (A partir de este mensaje estoy omitiendo los ángulos de Quine cuando no hay posibilidad de confusión entre fórmulas matemáticas y metamatemáticas. Aquí los pongo para distinguir el igualador metamatemático del negador matemático.) Entonces

\( M\vDash \ulcorner \phi\urcorner[a_1,\ldots, a_n]\leftrightarrow \lnot M\vDash\ulcorner\psi\urcorner[a_1,\ldots, a_n] \) \( \leftrightarrow \lnot N\vDash \ulcorner \psi\urcorner[i(a_1),\ldots, i(a_n)] \) \( \leftrightarrow N\vDash \ulcorner\phi\urcorner[i(a_1),\ldots, i(a_n)] \),

donde hemos usado la definición de satisfacción, la hipótesis de inducción y de nuevo la definición de satisfacción.

2)  \( \ulcorner \phi\urcorner = \ulcorner\psi\rightarrow \chi\urcorner \). Este caso es casi idéntico al anterior.

3)  \( \ulcorner \phi\urcorner = \ulcorner\forall x\psi(x)\urcorner \). Entonces hay dos posibilidades: si \( \ulcorner x\urcorner \) está libre en \( \ulcorner\psi\urcorner \), entonces es distinta de todas las \( \ulcorner x_i\urcorner \) (porque no está libre en \( \ulcorner\phi\urcorner \)), luego

\( M\vDash \ulcorner\phi\urcorner[a_1,\ldots, a_n]\leftrightarrow \forall a\in M\ M\vDash \ulcorner\psi\urcorner[a,a_1,\ldots, a_n] \) \( \leftrightarrow \forall a\in M\ N\vDash \ulcorner \psi\urcorner[i(a),i(a_1),\ldots, i(a_n)] \) \( \leftrightarrow \forall b\in N\ N\vDash \psi\ulcorner \psi\urcorner [b,i(a_1),\ldots, i(a_n)]\leftrightarrow N\vDash \ulcorner\phi\urcorner[i(a_1),\ldots, i(a_n)] \),

donde hemos usado la definición de satisfacción, la hipótesis de inducción, la biyectividad de \( i \) (éste es el único punto de la prueba que lo requiere) y de nuevo la definición de satisfacción.

En el caso (forzado, pero teóricamente posible) en que \( \ulcorner x\urcorner \) no está libre en \( \ulcorner\psi\urcorner \), el razonamiento es similar:

\( M\vDash \ulcorner\phi\urcorner[a_1,\ldots, a_n]\leftrightarrow \forall a\in M\ M\vDash \ulcorner\psi\urcorner[a,a_1,\ldots, a_n] \) \( \leftrightarrow \ M\vDash \ulcorner\psi\urcorner[a_1,\ldots, a_n]\leftrightarrow \ulcorner\psi\urcorner[i(a_1),\ldots, i(a_n)] \)  \( \leftrightarrow \forall a\in M\ N\vDash \ulcorner \psi\urcorner[i(a),i(a_1),\ldots, i(a_n)] \) \( \leftrightarrow \forall b\in N\ N\vDash \ulcorner \psi\urcorner [b,i(a_1),\ldots, i(a_n)]\leftrightarrow N\vDash \ulcorner\phi\urcorner[i(a_1),\ldots, i(a_n)] \)
[cerrar]

20 Septiembre, 2012, 11:40 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El concepto de inmersión de modelos es demasiado débil. Introducimos ahora el concepto de aplicación que conecta dos modelos de forma "útil":

Definición Sean \( M \) y \( B \) dos modelos de un mismo lenguaje formal \( \mathcal L \). Una aplicación \( i: M\longrightarrow N \) es una inmersión elemental si para toda fórmula \( \phi(x_1,\ldots, x_n) \) de \( \mathcal L  \) y todos los \( a_1,\ldots, a_n\in M  \) se cumple que \( M\vDash \phi[a_1,\ldots, a_n] \leftrightarrow N\vDash \phi[i(a_1),\ldots, i(a_n)] \).

El último teorema del mensaje anterior prueba que los isomorfismos de modelos son inmersiones elementales, y también hemos observado que no toda inmersión es elemental. Por otra parte, en la definición no hemos exigido que las inmersiones elementales sean inmersiones, pero lo son:

Teorema Toda inmersión elemental es una inmersión.

Demostración
Sea \( i:M\longrightarrow N  \) una inmersión elemental. Vamos a comprobar que cumple la definición de inmersión.

Si \( c  \) es una constante del lenguaje \( \mathcal L  \), consideramos la fórmula \( \phi(x)= \ulcorner x=c\urcorner \) y aplicamos la definición de inmersión elemental con \( a = I_M(c)  \):

Como \(  M\vDash \phi[a] \), también \( N\vDash \phi[i(a)]  \), lo cual significa que \( i(I_M(c)) = i(a) = I_N(c) \), como exige la definición de inmersión.

Si \( f  \) es un funtor \( n \)-ádico de \( \mathcal L  \), consideramos la fórmula \( \phi(x,x_1,\ldots, x_n)=\ulcorner x = fx_1\ldots x_n\urcorner  \), tomamos \( a_1,\ldots, a_n\in M  \) y llamamos \( a = I_M(f)(a_1,\ldots, a_n)  \). Entonces, como \( M\vDash\phi[a,a_1,\ldots, a_n]  \), por definición de inmersión elemental, \( N\vDash \phi[i(a),i(a_1),\ldots, i(a_n)]  \), lo que significa que \( i(I_M(f)(a_1,\ldots, a_n))= i(a) = I_N(f)(i(a_1),\ldots, i(a_n)) \), como exige la definición de inmersión.
[cerrar]

Definición Diremos que un submodelo \(  M \) de un modelo \( N \) es un submodelo elemental, y lo representaremos por \( M\prec N  \), si la inclusión \( i:M\longrightarrow N  \) es una inmersión elemental.

Explícitamente, esto significa que, para toda fórmula \(  \phi(x_1,\ldots, x_n) \) y todos los \( a_1,\ldots, a_n\in M  \) se cumple \( M\vDash \phi[a_1,\ldots, a_m]\leftrightarrow N\vDash \phi[a_1,\ldots, a_n] \).

Definición Diremos que dos modelos \( M \) y \( N \) de un lenguaje formal \( \mathcal L \) son elementalmente equivalentes, y se representa \( M\equiv N \), si para toda sentencia \( \phi \) de \( \mathcal L \) se cumple que \( M\vDash \phi \) si y sólo si \( N\vDash \phi \), es decir, si ambos modelos satisfacen las mismas sentencias.

Observemos que la definición de inmersión elemental se aplica a fórmulas sin variables libres, de modo que si \( i:M\longrightarrow N \) es una inmersión elemental (y en particular si \( M\prec N \)), entonces \( M \) y \( N \) son elementalmente equivalentes.

No es fácil mostrar ejemplos explícitos de inmersiones elementales, aparte de los isomorfismos de modelos. Para construir submodelos elementales no triviales conviene observar que éstos se caracterizan por una propiedad mucho más simple que su definición, en cuanto que sólo depende de la satisfacción de las fórmulas en el modelo mayor:

Teorema Sea \( N \) un modelo de un lenguaje \( \mathcal L  \). Entonces un subconjunto \( M\subset N \) es un submodelo elemental si y sólo si para toda fórmula \( \phi(x_1,\ldots, x_n,x)  \) y para todo \( a_1,\ldots, a_n \in M \) se cumple \( \exists b\in N\ N\vDash \phi[a_1,\ldots, a_n,b]\rightarrow \exists a\in M\ N\vDash \phi[a_1,\ldots, a_n,a] \).

En suma, la condición necesaria y suficiente para que un subconjunto de un modelo \( N \) sea un submodelo elemental es que si unos objetos de \( M \) verifican una propiedad en \( N \) que involucra un objeto de \( N \), dicho objeto se puede sustituir por otro de \( M \).

Demostración
Veamos en primer lugar que si un conjunto \( M \) cumple esta condición entonces es un submodelo de \( N \).

Si \( c \) es una constante de \( \mathcal L \), entonces \( b = I_N(c)\in N \) cumple \( N\vDash \ulcorner x=c\urcorner[b] \), luego por hipótesis existe un \( a\in M \) tal que \( N\vDash \ulcorner x=c\urcorner[a] \), pero esto significa que \( I_N(c) = a\in M \), como pide la definición de submodelo.

Si \( f \) es un funtor \( n \)-ádico de \( \mathcal L \) y \( a_1,\ldots, a_n\in M \), entonces \( b = I_N(f)(a_1,\ldots, a_n) \) cumple \( N\vDash \ulcorner x =fx_1\cdots x_n\urcorner[a_1,\ldots, a_n,b] \), luego por hipótesis existe un \( a\in M \) tal que \( N\vDash\ulcorner x = fx_1\cdots x_n\urcorner[a_1,\ldots, a_n,a] \), lo que significa que \( I_N(f)(a_1,\ldots, a_n) =a\in M \), como pide la definición de submodelo.

Así pues, \( M \) admite una estructura de modelo tal que la inclusión \( i: M\longrightarrow N \) es una inmersión. Hemos de probar que para toda fórmula \( \phi(x_1,\ldots, x_n) \) de \( \mathcal L \) y todos los \( a_1,\ldots, a_n\in M \) se cumple que \( M\vDash\phi[a_1,\ldots, a_n]\leftrightarrow N\vDash\phi[a_1,\ldots, a_n] \). Para ello razonamos por inducción sobre el orden de \( \phi \) exactamente igual que en la prueba del último teorema del mensaje anterior, donde sólo hemos de dar un razonamiento distinto para el caso en que \( \phi = \ulcorner \forall x\psi(x_1,\ldots, x_n,x)\urcorner  \), pues éste era el único caso en el que la prueba usaba la suprayectividad de \( i \), que ahora no tenemos.

En resumen, sabemos por hipótesis de inducción que \( M\vDash \psi[a_1,\ldots, a_n,a]\leftrightarrow N\vDash \psi[a_1,\ldots, a_n,a] \), y queremos probar lo mismo para \( \phi \). En efecto:

\( M\vDash \phi[a_1,\ldots, a_n]\leftrightarrow \forall a\in M\ M\vDash \psi[a_1,\ldots, a_n,a]\leftrightarrow \forall a\in M\ N\vDash \psi[a_1,\ldots, a_n,a] \) \(  \leftrightarrow \forall a\in N\ N\vDash \psi[a_1,\ldots, a_n,a] \),

donde, para la parte no trivial de la última equivalencia, hemos usado que si existiera un \( a\in N \) que no cumpliera \(  N\vDash \psi[a_1\ldots, a_n,a] \), cumpliría \(  N\vDash \lnot\psi[a_1,\ldots, a_n,a] \), y aplicando a esta fórmula la hipótesis del teorema, existiría un \( a\in M \) tal que \( N\vDash\lnot\psi[a_1,\ldots, a_n,a] \), es decir, tal que \( \lnot N\vDash \psi[a_1,\ldots, a_n,a] \), en contradicción con el miembro derecho de la equivalencia (que estamos suponiendo).

La cadena de equivalencias termina con  \( \leftrightarrow N\vDash \phi[a_1,\ldots, a_n]  \)  y con esto concluye la prueba de que \( M\prec N \).

El recíproco es mucho más simple: si \( M\prec N \), entonces, en las condiciones del enunciado, si existe un \( b\in N \) tal que \( N\vDash \phi[a_1,\ldots, a_n,b]  \), se cumple \( N\vDash \exists x\phi[a_1,\ldots, a_n] \), luego \( M\vDash \exists x\phi[a_1,\ldots, a_n] \), luego existe un \( a\in M \) tal que \(  M\vDash\phi[a_1,\ldots, a_n,a] \), luego \( N\vDash\phi[a_1,\ldots, a_n,a] \).
[cerrar]

Este teorema nos proporciona la clave para construir submodelos elementales de un modelo dado:

Definición Sea \( M \) un modelo de un lenguaje formal \( \mathcal L \). Supondremos fijado un orden en el conjunto de las variables de \( \mathcal L \). Para cada fórmula \( \phi(x_1,\ldots, x_n,x) \) de \( \mathcal L \) (donde suponemos las variables en orden creciente), diremos que \( h_\phi: M^n\longrightarrow M \) es una función de Skolem para \( \phi \) si para todos los \( a_1,\ldots, a_n\in M \), si \( \exists a\in M\ M\vDash \phi[a_1,\ldots, a_n,a]  \), entonces \( M\vDash \phi[a_1,\ldots, a_n, h_\phi(a_1,\ldots, a_n)] \). En caso contrario \( h_\phi(a_1,\ldots, a_n) \) puede ser cualquier elemento de \( M \).

El axioma de elección implica que toda fórmula con al menos dos variables tiene una función de Skolem, es decir, una función tal que, si \( N\subset M \), si unos elementos \( a_1,\ldots, a_n\in N  \) están en la situación del teorema anterior, es decir, satisfacen en \( M \) una fórmula \( \phi \) que depende de un cierto \( a\in M \), entonces \( h_\phi(a_1,\ldots, a_n) \) es uno cualquiera de dichos objetos \( a \). Fijemos una función de Skolem \( h_\phi \) para cada fórmula.

Si \( X\subset M \), definimos

\( N_0(X) = X  \) y \( N_{k+1}(X) = \bigcup\limits_\phi h_\phi[N_k(X)] \),

donde hay que entender que \( \phi \) recorre las fórmulas de \( \mathcal L \) con al menos dos variables libres y que, si \(  \phi \) tiene exactamente \( n+1 \) variables libres entonces \( h_\phi[N_k(X)] \) representa la imagen por \( h_\phi \) del conjunto \( N_k(X)^n \).

Definimos el núcleo de Skolem de \( X \) en \( M \) (respecto de las funciones de Skolem elegidas) como \( N(X) = \bigcup\limits_{k=0}^\infty N_k(X)  \).

Por último, definimos el cardinal de un lenguaje formal \( \mathcal L  \) como el cardinal del conjunto de sus signos, que es igual al cardinal del conjunto de sus fórmulas. Lo representaremos por \( |\mathcal L|  \).

Teorema (AE) Si \( M \) es un modelo de un lenguaje formal \( \mathcal L \) y \( X\subset M \) es un conjunto no vacío, entonces \( N(X)\prec M \) y \( |N(X)|=|X|\cdot |\mathcal L| \).

Demostración
Observemos que \( |N_0(X)| = |X|\leq |X||\mathcal L| \), si se cumple \( |N_k(X)|\leq |X||\mathcal L| \), entonces lo mismo vale para cada conjunto \( N_k(X)^n \), y también para cada conjunto \( h_\phi[N_k(X)] \) (porque una imagen de un conjunto siempre tiene cardinal menor o igual), luego \( |N_{k+1}(X)|\leq |X||\mathcal L||\mathcal L| = |X||\mathcal L| \), porque \( N_{k+1}(X) \) es la unión de a lo sumo \( |\mathcal L| \) conjuntos de cardinal a lo sumo \( |X||\mathcal L| \).

Finalmente \( |N(X)|\leq \aleph_0|X||\mathcal L| = |X||\mathcal L| \), porque \( N(X) \) es unión numerable de conjuntos de cardinal a lo sumo \( |X||\mathcal L| \). Como \( X\subset N(X) \) se tiene la igualdad.

Ahora basta probar que \( N(X) \) cumple las hipótesis del teorema anterior, y las cumple porque lo hemos construido específicamente para que las cumpla. En efecto, dada una fórmula \( \phi(x_1,\ldots, x_n,x) \) (en la que no perdemos generalidad si suponemos las variables ordenadas), tomamos \( a_1,\ldots, a_n\in N(X) \) y suponemos que existe un \( b\in M \) tal que \( M\vDash \phi[a_1,\ldots, a_n,b] \). Entonces, por la construcción de las funciones de Skolem, \( M\vDash \phi[a_1,\ldots, a_n, h_\phi(a_1,\ldots, a_n)] \).

Por construcción de \( N(X) \) existe un número natural \( k \) tal que \( a_1,\ldots, a_k\in N_k(X) \), luego \( a = h_\phi(a_1,\ldots, a_n)\in N_{k+1}(X)\subset N(X) \), es decir, tenemos que existe un \( a\in N(X) \) tal que \( M\vDash \phi[a_1,\ldots, a_n,a] \), como había que probar.
[cerrar]

En particular hemos probado lo siguiente:

Teorema de Löwenheim-Skolem (AE) Si \( M \) es un modelo de un lenguaje formal \( \mathcal L \), entonces tiene un submodelo elemental de cardinal a lo sumo \( |\mathcal L| \).

Todos los lenguajes formales que hemos considerado son numerables, en particular el lenguaje \( \ulcorner\mathcal L_{tc}\urcorner \), por lo que, para el caso más frecuente de modelos de lenguajes numerables, tenemos que todo modelo tiene un submodelo elemental numerable.

En particular, si existe un modelo de \( \ulcorner\mbox{ZFC}\urcorner \), existe un modelo numerable (porque todo submodelo elemental numerable es elementalmente equivalente al modelo dado, luego en particular también es un modelo de \( \ulcorner\mbox{ZFC}\urcorner \)). Esto puede parecer irrelevante después de que hayamos probado que no se puede demostrar en ZFC la existencia de modelos de \( \ulcorner\mbox{ZFC}\urcorner \), pero veremos que este inconveniente no es tan grave como aparenta.

En la próxima entrega empezaremos a estudiar específicamente los modelos de \( \ulcorner\mbox{ZFC}\urcorner \).

22 Septiembre, 2012, 03:07 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Recordemos que un modelo del lenguaje \( \ulcorner\mathcal L_{\rm tc}\urcorner \) de la teoría de conjuntos está determinado por un par \( (M,R) \), donde \( M \) es un conjunto no vacío y \( R\subset M\times M \) es la relación que interpreta en el modelo al relator \( \ulcorner\in \urcorner \).

Un modelo natural es un modelo en el que \( R = \{(x,y)\in M^2\mid x\in y\} \), es decir, un modelo en el que el relator \( \ulcorner \in\urcorner \) se interpreta como la relación definida por \( \in \). Así, todo conjunto no vacío \( M \) determina un único modelo natural de \( \ulcorner\mathcal L_{\rm tc} \urcorner \).

No todo modelo de \( \ulcorner\mathcal L_{\rm tc} \urcorner \) es isomorfo a un modelo natural, pero lo cierto es que una gran parte de los resultados sobre modelos de la teoría de conjuntos requiere considerar únicamente modelos naturales. Otras cuestiones mucho más avanzadas pueden involucrar modelos no naturales, y aun así, en la mayoría de los casos lo primero que se hace con dichos modelos es justificar que (bajo las condiciones adecuadas) son isomorfos a modelos naturales e inmediatamente se pasa a trabajar con dichos modelos isomorfos. Así pues, aunque con ello perdemos un poco de generalidad, en lo sucesivo vamos a considerar exclusivamente (salvo quizá en algún comentario aislado) modelos naturales.

Pero, naturalmente, no nos interesan los meros modelos naturales del lenguaje \( \ulcorner \mathcal L_{\rm tc}\urcorner \), pues eso es lo mismo que no decir nada (todo conjunto no vacío es un modelo), sino los modelos naturales de \( \ulcorner \mbox{ZFC}\urcorner \), es decir, los conjuntos \( M \) que cumplen \( M\vDash \ulcorner \mbox{ZFC}\urcorner \).

Aquí nos encontramos con un inconveniente, y es que hemos justificado más arriba que no se puede demostrar en ZFC que existan tales modelos. Demostraremos más adelante que esto puede arreglarse demostrando que en ZFC sí que puede probarse la existencia de modelos (naturales) de cualquier conjunto finito de axiomas de ZFC, y veremos que esto es suficiente en la práctica. No obstante, esta afirmación que acabo de hacer es más sutil de lo que podría pensarse y requiere una serie de precisiones antes de que pueda ser enunciada como un teorema riguroso. Este mensaje está dedicado a exponer dichas precisiones.

La idea fundamental es que "casi" podemos demostrar en ZFC que la clase \( V \) de todos los conjuntos es un modelo de \( \ulcorner \mbox{ZFC}\urcorner \), es decir, que \( V\vDash \ulcorner \mbox{ZFC}\urcorner \). Decimos "casi" porque el problema que en realidad impide demostrar este hecho en ZFC no es que carezcamos de argumentos para probarlos (existe un argumento y es trivial), sino que, según hemos observado, no podemos definir en ZFC la fórmula \(  V\vDash \alpha[v] \). Si hubiera una forma de definir esta fórmula de modo que cumpliera las propiedades que cumple \( M\vDash \alpha[v] \) cuando \( M \) es un conjunto (es decir, que \( V\vDash \lnot\alpha[v]\leftrightarrow \lnot V\vDash\alpha[v] \), etc.), entonces sería inmediato demostrar que \( V\vDash \ulcorner \mbox{ZFC}\urcorner \). Tenemos así un curioso caso en el que lo que impide demostrar un hecho poco menos que "obvio" no es la imposibilidad de razonarlo, sino la imposibilidad de enunciarlo.

Vamos a ver a continuación que, en un sentido débil, sí que podemos demostrar que \( V \) es un modelo de ZFC. Si \( \phi \) es una fórmula metamatemática del lenguaje \( \mathcal L_{\rm tc} \), tenemos definida la fórmula \( \ulcorner \phi\urcorner\in \mbox{Form}(\ulcorner \mathcal L_{\rm tc}\urcorner) \), que no es más que una sucesión de números naturales, y el problema es que no podemos definir \( V\vDash \ulcorner\phi \urcorner[v] \). Vamos a ver que sí podemos definir algo equivalente a partir de \( \phi \) a condición de no pasar a través de \( \ulcorner \phi\urcorner \).

(Meta)Definición Sea \( M \) una variable del lenguaje \( \mathcal L_{\rm tc} \) de la teoría de conjuntos y sea \( \phi \) una fórmula (metamatemática) de \( \mathcal L_{\rm tc} \) que no contenga la variable \( M \). Definimos su relativización a \( M \) como la fórmula (metamatemática) \( \phi^M \) que resulta de sustituir cada cuantificador \( \forall x \) que haya en \( \phi \) por \( \forall x\in M \) (donde estamos considerando la abreviatura habitual \( \forall x\in M\alpha\equiv \forall x(x\in M\rightarrow \alpha) \), e igualmente \( \exists x\in M\alpha\equiv \exists x(x\in M\land \alpha) \)).

Más detalladamente, la relativización de puede definir por recursión (metamatemática) sobre el orden de \( \phi \): para fórmulas de orden \( 0 \) (fórmulas atómicas), definimos

\( (x=y)^M \equiv x = y \),  \( (x\in y)^M\equiv x\in y \).

Supuesto definido \( \phi^M \) para toda fórmula de orden \( k \), para las fórmulas de orden \( k+1 \) definimos:

\( (\lnot \alpha)^M\equiv \lnot\alpha^M \),    \( (\alpha\rightarrow \beta)^M\equiv \alpha^M\rightarrow \beta^M \),     \( (\forall x\alpha)^M\equiv \forall x(x\in M\rightarrow \alpha^M) \).

A partir de aquí es fácil probar que:

\( (\alpha\lor \beta)^M\leftrightarrow \alpha^M\lor \beta^M \)

\( (\alpha\land \beta)^M\leftrightarrow \alpha^M\land \beta^M \)

\( (\alpha\leftrightarrow \beta)^M\leftrightarrow (\alpha^M\leftrightarrow \beta^M) \)

\( (\exists x\alpha)^M\leftrightarrow \exists x(x\in M\land \alpha^M) \)

\( (\exists !x\ \alpha)^M\leftrightarrow \exists ! x(x\in M\land \alpha^M) \).

Demostración
Veamos por ejemplo el caso del cuantificador existencial. Por definición

\( \exists x\alpha\equiv \lnot\forall x\lnot \alpha \), luego, aplicando las distintas reglas de la definición de relativización:

\( (\exists x\alpha)^M\equiv \lnot(\forall x\lnot\alpha)^M\equiv \lnot \forall x(x\in M\rightarrow (\lnot\alpha)^M)\equiv \lnot\forall x(x\in M\rightarrow \lnot\alpha^M) \),

y esto equivale claramente a \( \exists x(x\in M\land \alpha^M) \).
[cerrar]

Veamos por ejemplo la relativización del axioma del conjunto vacío: \( (\exists x\forall y\ y\notin x)^M\leftrightarrow \exists x\in M\forall y\in M\ y\notin x \).

Informalmente, si el axioma del conjunto vacío dice que hay un conjunto que no tiene elementos, su relativización a \( M \) dice que hay un conjunto en \( M \) que no tiene elementos en \( M \). En general, la relativización de una fórmula es otra fórmula que dice lo mismo que la dada, salvo que restringe (relativiza) todo lo que afirma a elementos de \( M \). En el fondo, lo que viene a decir es que la fórmula es "verdadera en \( M \)". Esto se traduce en el teorema siguiente:

(Meta)Teorema Sea \( M \) una variable del lenguaje \( \mathcal L_{\rm tc} \) y sea \( \phi(x_1,\ldots, x_n) \) una fórmula cuyas variables libres estén entre las indicadas (donde \( n \) es un número natural metamatemático). Entonces la fórmula siguiente es un teorema de ZF:

Para todo conjunto no vacío \( M \) y todos los \( a_1,\ldots, a_{\ulcorner n\urcorner}\in M \) se cumple \( M\vDash \ulcorner \phi\urcorner[a_1,\ldots, a_{\ulcorner n\urcorner}]\leftrightarrow \phi^M(a_1,\ldots, a_{\ulcorner n\urcorner}) \).

Demostración
Notemos que no se trata de probar un teorema de ZF, sino que, para cada fórmula metamatemática \( \phi \), tenemos un enunciado de un teorema de ZF que debemos probar. Vamos a demostrar infinitos teoremas al mismo tiempo o, más concretamente, vamos a dar un esquema de demostración que permite generar como caso particular la demostración de cualquier teorema del tipo indicado en el enunciado.

Razonamos por inducción (metamatemática) sobre el orden de la fórmula \( \phi \). Si tiene orden \( 0 \), se trata de una fórmula atómica y tenemos dos casos:

Si \( \phi\equiv x_i=x_j \), entonces \( \phi^M\equiv x_i = x_j \), con lo que

\( M\vDash \ulcorner x_i=x_j\urcorner[a_1,\ldots, a_{\ulcorner n\urcorner}]\leftrightarrow a_i=a_j\leftrightarrow \phi^M(a_1,\ldots, a_{\ulcorner n\urcorner}) \).

La prueba para \( x_i\in x_j \) es idéntica, sin más que cambiar \( = \) por \( \in \).

Supongamos que los enunciados correspondientes son demostrables en ZF para fórmulas de orden \( k \). Entonces, para las fórmulas de orden \( k+1 \) tenemos:

Si \( \phi\equiv \lnot\alpha \), entonces \( \phi^M\equiv\lnot \alpha^M \), luego

\( M\vDash \ulcorner \phi\urcorner[a_1,\ldots, a_{\ulcorner n\urcorner}]\leftrightarrow \lnot M\vDash \ulcorner \alpha\urcorner[a_1,\ldots, a_{\ulcorner n\urcorner}]\leftrightarrow \lnot \alpha^M(a_1,\ldots, a_{\ulcorner n\urcorner})\leftrightarrow \phi^M(a_1,\ldots, a_{\ulcorner n\urcorner}) \),

donde hemos usado que, por hipótesis de inducción, la segunda implicación es un teorema de ZF. El caso en que \( \phi\equiv \alpha\rightarrow \beta \) es muy similar. Pasamos directamente al caso en que \( \phi\equiv \forall x\alpha(x,x_1,\ldots, x_n) \). Entonces \( \phi^M\equiv \forall x\in M\ \alpha^M(x,x_1,\ldots,x_n) \) y

\( M\vDash \ulcorner \phi\urcorner[a_1,\ldots, a_{\ulcorner n\urcorner}]\leftrightarrow \forall a\in M\ M\vDash \ulcorner \alpha\urcorner[a,a_1,\ldots, a_{\ulcorner n\urcorner}] \) \( \leftrightarrow \forall a\in M\ \alpha^M(a,a_1,\ldots, a_{\ulcorner n\urcorner})\leftrightarrow \phi^M(a_1,\ldots, a_{\ulcorner n\urcorner}) \).
[cerrar]

Así pues, \( M\vDash \ulcorner \phi\urcorner[x_1,\ldots, x_n] \) y \( \phi^M(x_1,\ldots, x_n) \) son equivalentes cuando \( \phi \) es una fórmula metamatemática y \( n \) es un número natural metamatemático. La diferencia es que la primera expresión está definida para todo elemento de \( \mbox{Form}(\mathcal L_{\rm tc}) \) (no sólo para los de la forma \( \ulcorner \phi\urcorner \), donde \( \phi \) es una fórmula metamatemática), pero no cuando \( M \) es una clase propia, mientras que, como vamos a ver a continuación, la segunda expresión sólo está definida para fórmulas metamatemáticas, pero a cambio se generaliza trivialmente a clases propias.

En efecto, una clase propia \( M \) en ZFC no es más que una fórmula (metamatemática) \( \phi(x,x_1,\ldots, x_n) \), de modo que \( x\in M \) no es más que una abreviatura por \( \phi(x,x_1,\ldots, x_n) \). Por ejemplo, la clase \( \mathcal V_K \) de todos los espacios vectoriales sobre un cuerpo \( K \) no es más que la fórmula \( \phi(W,K)\equiv  \) "\( W \) es un espacio vectorial sobre \( K \)", de modo que la fórmula \( W\in \mathcal V_K \) no es más que una abreviatura para "\( W \) es un espacio vectorial sobre \( K \)".

De este modo, si \( M \) es una clase propia definida por la fórmula \( \psi(x,x_1,\ldots, x_n) \) para cada fórmula metamatemática \( \phi \) que no contenga ninguna de las variables que aparecen en \( \psi \), la definición que hemos dado de relativización \( \phi^M \) es válida en este contexto, con la única salvedad de que las fórmulas \( x\in M \) que se insertan junto a los cuantificadores de \( \phi \) han de entenderse como \( \psi(x,x_1,\ldots, x_n) \).

Ejemplo
La relativización del axioma del conjunto vacío a la clase de todos los espacios vectoriales sobre un cuerpo \( K \) es

\( (\exists x\forall y\ y\notin x)^{\mathcal V_K}\leftrightarrow \exists x\in \mathcal V_K\forall y\in \mathcal V_K\ y\notin x \),

que, más desarrolladamente, es la fórmula que afirma: "existe un espacio vectorial \( x \) sobre \( K \) tal que para todo espacio vectorial \( y \) sobre \( K \) se cumple que \( y\notin x \)", lo cual es trivialmente cierto, pues son muchos los espacios vectoriales (todos los habituales) cuyos elementos no son espacios vectoriales.
[cerrar]

(Meta)Definición Si \( \Gamma = \{\gamma_1,\ldots, \gamma_m\} \) es una colección finita de fórmulas metamatemáticas cuyas variables libres estén entre \( x_1,\ldots, x_n \), abreviaremos \( M\vDash \Gamma\equiv \forall x_1,\ldots, x_n\in M (\gamma_1^M\land \cdots \land \gamma_m^M) \).

De este modo, según hemos visto, si llamamos \( \ulcorner\Gamma \urcorner = \{\ulcorner \gamma_1\urcorner,\ldots, \ulcorner \gamma_m\urcorner\}\subset \mbox{Form}(\ulcorner \mathcal L_{\rm tc}\urcorner) \) a la formalización de \( \Gamma \),  podemos probar  en ZF que para todo conjunto \( M \) se cumple

(*)           \( M\vDash \ulcorner \Gamma\urcorner\leftrightarrow M\vDash \Gamma \),

donde la parte de la izquierda es la definición de satisfacción en un modelo de un conjunto de fórmulas (matemáticas) y la parte derecha es la definición que acabamos de dar de satisfacción en una clase arbitraria (conjunto o no) de una colección metamatemática de fórmulas.

Observemos que la parte izquierda de (*) está definida para cualquier subconjunto \( \Gamma \subset \mbox{Form}(\ulcorner \mathcal L_{\rm tc}\urcorner) \), finito o infinito, pues nada nos impide definirlo como \( M\vDash \Gamma\leftrightarrow \forall \gamma\in \Gamma\ M\vDash \gamma \).  En cambio, la parte derecha de (*) sólo está definida para colecciones finitas de fórmulas metamatemáticas, pues está definida como una conjunción de fórmulas, y no podemos formar la conjunción de infinitas fórmulas, ni tiene sentido escribir (en el enunciado de un teorema de ZF) \( \forall \gamma\in \Gamma \) cuando \( \gamma \) tiene que recorrer una colección de fórmulas metamatemáticas, pues las fórmulas metamatemáticas (a diferencia de los elementos de \( \mbox{Form}(\ulcorner \mathcal L_{\rm tc}\urcorner) \), que son sucesiones finitas de números naturales), no son conjuntos que puedan sustituirse por variables que a su vez puedan ligarse a un cuantificador. (Éste es uno de los momentos en que quien no distinga entre fórmulas matemáticas y fórmulas metamatemáticas no puede entender nada.)

Observemos ahora que la clase de todos los conjuntos es simplemente \( V = \{x\mid x=x\} \), es decir, la clase asociada a la fórmula \( x=x \). Por lo tanto, la relativización \( \phi^V \) de una fórmula se calcula simplemente cambiando \( \forall x \) por \( \forall x\in V \), es decir, por \( \forall x(x=x\rightarrow \cdots) \), y es obvio que esto es lógicamente equivalente a \( \forall x \).

Así pues, para toda fórmula (metamatemática) \( \phi \) se cumple que \( \phi^V\leftrightarrow \phi \), luego, en particular, si \( \Gamma = \{\gamma_1,\ldots, \gamma_n\} \) es cualquier colección finita (metamatemática) de axiomas de ZF (o ZFC), en ZF (o ZFC) puede probarse \( V\vDash \Gamma \), pues esto es por definición \( \gamma_1^V\land \cdots \land \gamma_n^V \), y esto es equivalente a \( \gamma_1\land \cdots \land \gamma_n \), que es una conjunción de axiomas, luego un teorema.

Es en este sentido en el que podemos demostrar en ZF(o ZFC) que la clase universal es un modelo de ZF (o ZFC), en el sentido de que se cumple \( V\vDash \Gamma \) para cualquier colección finita arbitrariamente grande de axiomas de ZF (o ZFC). En el fondo, esto es una obviedad, pero veremos que la prueba del teorema de Löwenheim-Skolem puede adaptarse para deducir de aquí la existencia de conjuntos (incluso numerables) \( M \) que son modelos de cualquier conjunto finito arbitrariamente grande de axiomas de ZFC. Nos ocuparemos de ello en la entrega siguiente. De momento terminamos con un resultado análogo a otro que hemos probado para modelos en el sentido de la teoría de modelos:

(Meta)Teorema Sea \( \Gamma \) una colección finita (metamatemática) de fórmulas de \( \mathcal L_{\rm tc} \) y sea \( \alpha \) una sentencia tal que \( \Gamma\vdash \alpha \). Entonces en ZF se demuestra que si \( M \) es una clase arbitraria (conjunto o no), \( (M\vDash \Gamma)\rightarrow \alpha^M \).

Demostración
En primer lugar se prueba que si \( \phi(x_1,\ldots, x_n) \) es un axioma lógico entonces \( \forall x_1\ldots x_n\in M\ \phi^M \).

Por ejemplo, si \( \phi\equiv \alpha\rightarrow (\beta\rightarrow\alpha) \), entonces su relativización es \( \alpha^M\rightarrow (\beta^M\rightarrow \alpha^M) \), que es un axioma del mismo tipo, luego en particular un teorema de ZF, y sigue siéndolo cuando se antepone el cuantificador universal. Con los demás axiomas sucede algo similar.

A continuación se prueba que las reglas de inferencia se relativizan a \( M \), es decir, que, en el caso del Modus Ponens, si \( \forall x_1\ldots x_n\in M(\alpha\rightarrow \beta)^M \) y \( \forall x_1\ldots x_n\in M\ \alpha^M \), entonces podemos concluir \( \forall x_1\ldots x_n\in M\ \beta^M \). Esto se debe a que la primera fórmula no es sino \( \forall x_1\ldots x_n\in M(\alpha^M\rightarrow \beta^M) \), luego podemos aplicar el Modus Ponens.

En el caso de la generalización, si suponemos \( \forall xx_1\ldots x_n\in M\alpha(x)^M \), esto equivale a \( \forall x_1\ldots x_n\in M\forall x\in M\ \alpha(x)^M \), y esto es lo mismo que \( \forall x_1\ldots x_n\in M(\forall x\alpha)^M \).

Y ahora, si suponemos que \( \Gamma\vdash \alpha \), existe una deducción \( \alpha_1,\ldots, \alpha_n \) de \( \alpha \) a partir de \( \Gamma \) y, si \( x_1,\ldots, x_n \) son todas las variables que aparecen en la deducción, una simple inducción (metamatemática, sobre \( i \)) prueba que \( \forall x_1\ldots x_n\in M\ \alpha_i^M \) es un teorema de ZF. Como \( \alpha \equiv \alpha_n \) y  no tiene variables libres, concluimos que \( \alpha^M \) es un teorema de ZF.
[cerrar]

23 Septiembre, 2012, 01:54 pm
Respuesta #8

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora estamos en condiciones de demostrar en ZF (o ZFC) la existencia de conjuntos que son modelos naturales de cualquier conjunto finito prefijado de axiomas de ZF (o ZFC). El argumento es una variante del que hemos empleado para probar el teorema de Löwenheim-Skolem, y en primer lugar necesitamos demostrar la versión análoga para relativización de formulas de la caracterización de los submodelos elementales en la que nos basamos para probar dicho teorema. Previamente damos una definición:

Definición: Sea \( \phi(x_1,\ldots, x_n) \) una fórmula (metamatemática) del lenguaje \( \mathcal L_{\rm tc} \). Diremos que \( \phi \) es absoluta para dos clases \( M\subset N \) (sean conjuntos o no) si

\( \forall x_1\cdots x_n\in M(\phi^M(x_1,\ldots, x_n)\leftrightarrow \phi^N(x_1,\ldots, x_n)) \).

Notemos que se trata de la propiedad que, cuando se cumple para todas las fórmulas, significa que \( M \) es un submodelo elemental de \( N \), pero hay problemas técnicos al tratar de expresar en ZF que esta propiedad "se cumple para todas las fórmulas metamatemáticas", pues no podemos cuantificar sobre cosas (fórmulas) que no son conjuntos. En su lugar nos las arreglamos para trabajar en todo momento con colecciones finitas de fórmulas:

(Meta)Teorema Sea \( \phi_1,\ldots, \phi_n \) una colección de fórmulas (metamatemáticas) cerrada para subfórmulas (es decir, tal que toda subfórmula que aparece en cualquiera de las fórmulas \( \phi_i \) es una \( \phi_j \) para cierto \( j<i \)). Sean \( M\subset N \) dos clases cualesquiera con la propiedad de que cuando \( \phi_i\equiv \forall x\ \phi_j(x,x_1,\ldots, x_n) \) entonces

\( \forall x_1,\ldots, x_n\in M(\exists x\in N\ \lnot \phi_j^N(x,x_1,\ldots, x_n)\rightarrow \exists x\in M\ \lnot\phi_j^N(x,x_1,\ldots, x_n)) \).

Entonces todas las fórmulas \( \phi_i \) son absolutas para \( M-N \).

Demostración
Demostramos por inducción sobre \( i \) que cada \( \phi_i \) es absoluta. Supongamos que las fórmulas \( \phi_j \) con \( j<i \) son absolutas y vamos a probarlo para \( \phi_i \) (esto incluye el caso \( i=1 \), en el que la hipótesis es vacía).

Distinguimos casos según la forma de \( \phi_i \). Si \( \phi_i\equiv x=y \), entonces es trivialmente absoluta, pues esto significa que \( \forall xy\in M((x=y)^M\leftrightarrow (x=y)^N) \) o, lo que es lo mismo, por definición de relativización, \( \forall xy\in M(x=y\leftrightarrow x=y) \).

Lo mismo vale si \( \phi_i\equiv x\in y \).

Si \( \phi_i\equiv \lnot\phi_j(x_1,\ldots, x_n) \), con \( j<i \), entonces, por hipótesis de inducción, \( \forall x_1\cdots x_n\in M(\phi_j^M(x_1,\ldots, x_n)\leftrightarrow \phi_j^N(x_1,\ldots, x_n)) \).

Esto implica obviamente que  \( \forall x_1\cdots x_n\in M(\lnot\phi_j^M(x_1,\ldots, x_n)\leftrightarrow \lnot\phi_j^N(x_1,\ldots, x_n)) \), lo cual, por definición de relativización, es lo mismo que  \( \forall x_1\cdots x_n\in M(\phi_i^M(x_1,\ldots, x_n)\leftrightarrow \phi_i^N(x_1,\ldots, x_n)) \).

El caso en que \( \phi_i\equiv \phi_j\rightarrow \phi_k \), con \( j,k<i \), es similar. Pasamos directamente al caso en que \( \phi_i\equiv \forall x\phi_j(x,x_1,\ldots, x_n) \). Entonces, por hipótesis de inducción,

\( \forall xx_1\cdots x_n\in M(\phi_j^M(x,x_1,\ldots, x_n)\leftrightarrow \phi_j^N(x,x_1,\ldots, x_n)) \).

Ahora, si fijamos \( x_1,\ldots, x_n\in M \), tenemos que

\( \phi^M_i(x_1,\ldots, x_n)\leftrightarrow \forall x\in M\ \phi_j^M(x,x_1,\ldots, x_n)\leftrightarrow \forall x\in M\ \phi_j^N(x,x_1,\ldots, x_n) \),

donde hemos usado la hipótesis de inducción. Ahora, por la hipótesis del teorema esto es equivalente a

\( \forall x\in N\ \phi_j^N(x,x_1,\ldots, x_n) \),

dado que una implicación es obvia ya que \( M\subset N \), y para la otra observamos que si existiera un \( x\in N \) para el que \( \lnot\phi_j^N(x,x_1,\ldots, x_n) \), por la hipótesis del teorema habría un tal \( x\in M \) y no se cumpliría \( \forall x\in M\ \phi_j^N(x,x_1,\ldots, x_n) \).

Por definición de relativización, la última fórmula a la que hemos llegado es \( \phi_i^N(x_1,\ldots, x_n) \).
[cerrar]

La clave para probar el teorema de reflexión, que es el objetivo de este mensaje, es que la clase \( V \) de todos los conjuntos tiene una estructura:

Definición Llamamos \( V_0 =\emptyset \), supuesto definido \( V_\alpha \) para un ordinal \( \alpha \), se define \( V_{\alpha+1}=\mathcal PV_\alpha \) y, supuesto definido \( \{V_\delta\}_{\delta<\lambda} \) para un ordinal límite \( \lambda \), se define \( V_\lambda = \bigcup\limits_{\delta<\lambda}V_\delta \).

Estas condiciones determinan e ZF una sucesión transfinita de conjuntos \( \{V_\alpha\}_{\alpha\in \Omega} \), donde \( \Omega \) es la clase de todos los ordinales, y el axioma de regularidad es equivalente a la igualdad \( V = \bigcup\limits_{\alpha\in \Omega}V_\alpha \).

En otras palabras, todo conjunto puede obtenerse a partir del conjunto vacío mediante aplicaciones sucesivas del operador "partes de".

Los conjuntos \( V_\alpha \) tienen una serie de propiedades. Por ejemplo, son conjuntos transitivos. En general, una clase \( X \) es transitiva si \( \forall x\in X\ x\subset X \).

Teorema Para todo ordinal \( \alpha \) se cumple que \( V_\alpha \) es un conjunto transitivo y si \( \alpha\leq \beta \) entonces \( V_\alpha\subset V_\beta \).

Demostración
Probamos que cada \( V_\alpha \) es un conjunto transitivo por inducción transfinita. Esto significa:

1) Probar que se cumple para \( \alpha=0 \), pero \( V_0=\emptyset \) y el conjunto vacío es trivialmente transitivo.

2) Probar que si se cumple para \( \alpha \), también se cumple para \( \alpha+1 \). En efecto, si \( V_\alpha \) es transitivo y \( x\in V_{\alpha+1} \), entonces \( x\subset V_\alpha \) por definición de \( V_{\alpha+1} \). Por lo tanto, si \( u\in x \), tenemos que \( u\in V_\alpha \), luego \( u\subset V_\alpha \) (porque \( V_\alpha \) es transitivo), luego \( u\in \mathcal PV_\alpha = V_{\alpha+1} \). Con esto hemos probado que \( x\subset V_{\alpha+1} \), luego \( V_{\alpha+1} \) es transitivo.

3) Probar que si se cumple para todo \( \delta<\lambda \), donde \( \lambda \) es un ordinal límite, entonces se cumple para \( \lambda \). En efecto, suponemos que \( V_\delta \) es transitivo para todo \( \delta<\lambda \) y queremos probar que \( V_\lambda = \bigcup\limits_{\delta<\lambda}V_\delta \) es transitivo. En general, la unión de conjuntos transitivos es un conjunto transitivo. La prueba es inmediata: si \( x\in V_\lambda \), entonces existe un \( \delta<\lambda \) tal que \( x\in V_\delta \), luego \( x\subset V_\delta \), pues \( V_\delta \) es transitivo, luego \( x\subset V_\lambda \), pues \( V_\delta \subset V_\lambda \).

Veamos ahora por inducción sobre \( \beta \) que cada \( V_\beta \) contiene a todos los \( V_\alpha \) anteriores. Para \( \beta = 0 \) es trivial.

Supongamos que es cierto para \( \beta \). Entonces basta observar que \( V_\beta\subset V_{\beta+1} \), pues entonces \( V_{\beta+1} \) contiene a \( V_\beta \) y también a todos los \( V_\alpha \) con \( \alpha\leq \beta \), es decir, a todos los \( V_\alpha \) con \( \alpha\leq \beta+1 \).

La inclusión se debe a que so \( x\in V_\beta \) entonces \( x\subset V_\beta \) (porque ya hemos probado que \( V_\beta \) es transitivo), luego \( x\in \mathcal PV_\beta = V_{\beta+1} \).

Por último supongamos que se cumple para todo \( \delta<\lambda \) y veamos que también se cumple para \( \lambda \), pero esto es trivial, pues \( V_\lambda = \bigcup\limits_{\delta<\lambda}V_\delta \) contiene obviamente a todos los \( V_\delta \).
[cerrar]

Veamos ya el teorema principal:

Teorema de reflexión Sean \( \phi_1,\ldots, \phi_n \) fórmulas metamatemáticas cualesquiera y sea \( \{Z_\alpha\}_{\alpha\in\Omega} \) una sucesión transfinita de conjuntos con las propiedades siguientes.

1) \( \forall \alpha\beta \in \Omega(\alpha\leq \beta\rightarrow Z_\alpha\subset Z_\beta) \)

2) Para todo ordinal límite \( \lambda \), \( Z_\lambda = \bigcup\limits_{\delta<\lambda}Z_\delta \).

Llamemos \( Z = \bigcup\limits_{\alpha\in\Omega}Z_\alpha \). Entonces, para todo ordinal \( \alpha \) existe un ordinal límite \( \lambda>\alpha \) tal que las fórmulas dadas son absolutas para \( Z_\lambda-Z \).

La idea es aplicarlo al caso en que \( Z_\alpha = V_\alpha \), en cuyo caso \( Z = V \), pues hemos probado que la sucesión \( \{V_\alpha\}_{\alpha\in \Omega} \) cumple las hipótesis del teorema.

Demostración
No perdemos generalidad si suponemos que las fórmulas dadas forman una sucesión cerrada para subfórmulas, pues siempre podemos extenderla para que lo sea, y si todas las fórmulas de la sucesión extendida son absolutas para un \( Z_\lambda \) y \( Z \), entonces las dadas, que son parte de ellas, también lo serán.

Para cada índice \( i \) tal que \( \phi_i\equiv \forall x\phi_j(x,x_1,\ldots, x_m) \) definimos la función \( G_i: Z^m\longrightarrow \Omega \) de modo que \( G_i(x_1,\ldots, x_m) \) sea el mínimo ordinal \( \alpha \) tal que \( \exists x\in Z_\alpha\lnot\phi_j^Z(x,x_1,\ldots, x_m) \) si existe tal \( \alpha \) y  \( G_i(x_1,\ldots, x_nm=0 \) si no existe tal \( \alpha \).

A su vez definimos \( F_i:\Omega\longrightarrow \Omega \) como la función dada por \( F_i(\delta) = \sup\limits_{x\in Z_\delta^m}G_i(x) \).

De este modo, si hay un \( x\in Z \) que incumple \( \forall x\in Z\phi_j^Z(x,x_1,\ldots, x_m) \) con los parámetros en \( Z_\delta \), sabemos que podemos encontrar un tal \( x \) en \( Z_{F_i(\delta)} \), concretamente.

Observemos que si \( \delta\leq\epsilon \), entonces \( Z^m_\delta\subset Z_\epsilon^m \) (por las hipótesis del teorema), luego, al tomar supremos, \( F_i(\delta)\leq F_i(\epsilon) \).

Si \( \phi_i\equiv \forall x\phi_j(x) \), sin variables libres, definimos \( F_i:\Omega\longrightarrow\Omega \) de modo que \( F_i(\delta) \) es el mínimo ordinal \( \alpha \) tal que \( \exists x\in Z_\alpha\lnot\phi_j(x) \) si existe tal \( \alpha \) y \( F_i(\delta)=0 \) en caso contrario.

Para cualquier índice \( i \) tal que \( \phi_i \) no empieza por un \( \forall \) definimos \( F_i:\Omega\longrightarrow \Omega \) como la función nula. En cualquiera de estos dos últimos casos es trivial que si \( \delta\leq \epsilon \) entonces \( F_i(\delta)\leq F_i(\epsilon) \).

Ahora consideramos el ordinal arbitrario \( \alpha \) dado en el enunciado y definimos una sucesión \( \{\alpha_k\}_{k\in \mathbb N} \) como sigue:

\( \alpha_0=\alpha \),  \( \alpha_{k+1}=\max\{\alpha_k+1, F_1(\alpha_k),\ldots, F_n(\alpha_k)\} \).

Notemos que \( \alpha_{k+1}\geq \alpha_k+1>\alpha_k \), luego la sucesión es monótona creciente. A su vez, esto se traduce en que \( \lambda = \sup\alpha_k \) es un ordinal límite, pues si \( \delta<\lambda \), entonces existe un \( k \) tal que \( \delta<\alpha_k \), luego \( \delta+1\leq \alpha_k<\alpha_{k+1}\leq \lambda \). Vamos a probar que \( \lambda \) cumple lo pedido.

La clave está en que \( \forall \delta<\lambda\ F_i(\delta)<\lambda \). En efecto, existe un \( k \) tal que \( \delta<\alpha_k \), luego \( F_i(\delta)\leq F_i(\alpha_k)\leq \alpha_{k+1}<\alpha_{k+2}\leq\lambda \).

Para probar que las fórmulas \( \phi_i \) son absolutas para \( Z_\lambda \) y \( Z \) usamos el primer teorema que hemos probado en este mensaje. Suponemos que \( \phi_i\equiv \forall x\phi_j(x,x_1,\ldots, x_m) \) (tal vez con \( m=0 \)) y que \( \exists x\in Z\lnot\phi_j^Z(x,x_1,\ldots, x_m) \), para ciertos \( x_1,\ldots, x_m\in Z_\lambda \).

Entonces cada \( x_u\in Z_{\delta} \) para un \( \delta<\lambda \), que en principio depende de \( u \), pero, como son un número finito, podemos tomar el máximo de todos ellos, y así existe un \( \delta<\lambda \) tal que \( x_1,\ldots, x_m\in Z_\delta \). Sea \( \eta \) el mínimo ordinal tal que \( \exists x\in Z_\eta\lnot \phi_j^Z(x,x_1,\ldots, x_m) \). Si \( m>0 \) entonces \( \eta = G_i(x_1,\ldots, x_m)\leq F_i(\delta)<\lambda \) y si \( m=0 \) entonces \( \eta=F_i(0)<\lambda \). En cualquier caso \( Z_\eta\subset Z_\lambda \), luego \( \exists x\in Z_\lambda\phi_j^Z(x,x_1,\ldots, x_m) \). Esto es lo que había que probar.

Observemos que, al contrario de lo que sucede con el teoremade Löwenheim-Skolem, la demostración no usa el axioma de elección, pues en dicho teorema teníamos que escoger contraejemplos posibles de fórmulas universales, mientras que aquí escogemos ordinales \( \alpha \) tales que el conjunto \( Z_\alpha \) contiene un contraejemplo, y para elegir ordinales no hace falta el axioma de elección, porque los ordinales están bien ordenados.
[cerrar]

En particular:

Teorema de reflexión Si \( \phi_1,\ldots, \phi_n \) son fórmulas metamatemáticas cualesquiera, para todo ordinal \( \alpha \) existe un ordinal límite \( \lambda>\alpha \) tal que las fórmulas dadas son absolutas para \( V_\lambda \) y \( V \).

Más en particular:

(Meta)Teorema Si \( \Gamma \) es una colección finita de axiomas de ZF (o ZFC), entonces existe un ordinal límite \( \lambda \) tal que en ZF (o ZFC) se demuestra que \( V_\lambda\vDash \Gamma \). Así, existen modelos (naturales) transitivos de cualquier colección finita de axiomas de ZF (o ZFC).

La prueba es trivial: sabemos que existe \( \lambda \) tal que los axiomas son absolutos para \( V_\lambda \) y \( V \). Si \( \gamma \) es uno de estos axiomas, entonces no tiene variables libres, y la definición de ser absoluto es simplemente que \( \gamma^{V_\lambda}\leftrightarrow \gamma^V \). Pero en el mensaje anterior vimos que en ZF (o ZFC) podemos probar que cada axioma \( \gamma \) de ZF (o ZFC) es verdadero en \( V \), es decir, podemos demostrar (trivialmente) \( \gamma^V \), luego la equivalencia anterior (que también podemos probar, por el teorema de reflexión) nos permite concluir que se cumple \( \gamma^{V_\lambda} \).

Más en general, hemos probado que podemos encontrar modelos transitivos en los que se cumpla cualquier afirmación que se cumpla en \( V \). Así, por ejemplo, si suponemos la hipótesis del continuo, entonces la hipótesis del continuo se cumple en \( V \) (es decir, se cumple \( \mbox{HC}^V \)), y por el teorema de reflexión existe un modelo \( V_\lambda \) que cumple cualquier cantidad finita de axiomas de ZFC y además \( \mbox{HC}^{V_\lambda}\leftrightarrow \mbox{HC}^V \), luego también se cumple \( \mbox{HC}^{V_\lambda} \).

Notemos ahora que si \( \Gamma \) es cualquier colección finita metamatemática de axiomas de ZFC, hemos probado que existe un conjunto \( M \) tal que \( M\vDash \Gamma \), en el sentido de que se pueden probar las relativizaciones a \( M \) de las sentencias \( \gamma \) de \( \Gamma \), pero también hemos probado que esto es equivalente a que \( M\vDash \ulcorner\Gamma\urcorner \), es decir, a que \( M\vDash \ulcorner \gamma\urcorner \), donde \( \ulcorner\gamma\urcorner\in \mbox{Form}(\ulcorner\mathcal L_{\rm tc}\urcorner) \) es el reflejo formal de la sentencia metamatemática \( \gamma \) (o sea, una sucesión finita concreta de números naturales). En otras palabras, \( M \) es un modelo (natural) de \( \ulcorner\Gamma\urcorner \) en el sentido de la teoría de modelos, por lo que podemos aplicarle el teorema de Löwenheim-Skolem para obtener un submodelo elemental numerable. Un submodelo elemental cumple en particular las mismas sentencias que son verdaderas en el modelo de partida, luego también es un modelo de \( \ulcorner\Gamma\urcorner \). En definitiva:

(Meta)Teorema Para toda colección finita \( \Gamma \) de axiomas de ZFC, en ZFC se demuestra que existe un conjunto numerable \( M \) tal que \( M\vDash \ulcorner\Gamma\urcorner \).

Notemos que este teorema usa, en principio, el axioma de elección. No es evidente, pero en realidad se puede evitar su uso.

Para acabar observamos que el teorema de reflexión nos proporciona modelos transitivos (no necesariamente numerables) de cualquier conjunto finito de axiomas de ZFC, pero al pasar a modelos numerables mediante el teorema de Löwenheim-Skolem perdemos la transitividad, es decir, obtenemos modelos naturales numerables, pero no necesariamente transitivos. Sucede que los modelos transitivos son especialmente simples de manejar y de entender, por lo que conservar la transitividad es importante. En la próxima entrega veremos que es posible conservarla.

25 Septiembre, 2012, 11:46 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 10,115
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El objetivo de este mensaje es demostrar el teorema siguiente:

Teorema del colapso de Mostowski Sea \( A \) una clase y \( R\subset A\times A \) una relación que cumpla las tres propiedades siguientes:
  • Para todo \( a\in A \) la clase \( \{x\in A\mid x\,R\,a\} \) es un conjunto. (Esto se cumple automáticamente si \( A \) es un conjunto.)
  • \( \forall ab\in A(\forall x\in A(x\,R\,a\leftrightarrow x\,R\,b)\rightarrow a=b) \). (Esto se expresa diciendo que la relación \( R \) es extensional en \( A \).)
  • Para todo \( B\subset A \), \( B\neq \emptyset \) existe un \( m\in B \) tal que ningún \( x\in B \) cumple \( x\,R\,m \). (Se dice entonces que \( m \) es un elemento \( R \)-minimal de \( B \) y la propieda de que toda subclase no vacía de \( A \) tenga un elemento \( R \)-minimal se expresa diciendo que la relación \( R \) está bien fundada en \( A \).
Entonces existe una clase transitiva \( M \) y una aplicación \( \pi: A\longrightarrow M \) biyectiva tal que \( \forall xy\in A(x\,R\,y\leftrightarrow \pi(x)\in \pi(y)) \). La clase \( M \) se llama colapso de Mostowski o colapso transitivo de \( (A,R) \), y la función \( \pi \) se llama función colapsante de \( (A,R) \).

En términos de modelos, esto significa que si \( (A,R) \) es un modelo del lenguaje de la teoría de conjuntos (donde \( A \) es un conjunto) y la relación \( R \) es extensional y está bien fundada en \( A \) entonces existe un conjunto transitivo \( M \) y un isomorfismo de modelos \( \pi: (A,R)\longrightarrow M \). En efecto, la condición que debe cumplir la función colapsante es precisamente la condición de isomorfismo de modelos para el relator \( \ulcorner \in\urcorner \), mientras que la condición para \( \ulcorner=\urcorner \) es la inyectividad.

Así pues, el teorema de Mostowski proporciona condiciones suficientes para que un modelo sea isomorfo a un modelo transitivo. Veremos que son necesarias.

Conviene observar que la única función colapsante \( \pi: (A,R)\longrightarrow M \) satisface la siguiente relación recurrente:

\( \pi(x)=\{\pi(y)\mid y\in A\land y\,R\,x\} \).

En efecto, si \( y\in A\land y\,R\,x \), por las propiedades que determinan la función colapsante tenemos que \( \pi(y)\in \pi(x) \). Recíprocamente, si \( u\in \pi(x)\in M \), entonces, como \( M \) es transitivo, se cumple \( u\in M \), luego existe un \( y\in A \) tal que \( \pi(y)=u\in \pi(x) \), luego \( y\,R\, x \).

Vamos a necesitar el concepto de clausura de una relación:

Definición Sea \( R \) una relación en una clase \( A \) que cumpla la primera condición del teorema de Mostowski, es decir, que para cada \( a\in A \) la clase \( \mbox{ext}_R(a)=\{x\in A\mid x\,R\,a\} \) (la extensión de \( a \)) sea un conjunto.

Definimos \( \mbox{cl}_R^0(a)=\mbox{ext}_R(a),\qquad\mbox{cl}_R^{k+1}(a)=\mbox{cl}_R^k(a)\cup\bigcup\limits_{x\in \mbox{cl}_R^k(a)}\mbox{ext}_R(x),\qquad \mbox{cl}_R(a)=\bigcup\limits_{k\in \mathbb N}\mbox{cl}_R^k(a) \).

Así, \( \mbox{cl}_R^0(a) \) contiene a todos los elementos relacionados con \( a \) (por la izquierda), \( \mbox{cl}_R^1(a) \) contiene, además de estos elementos, a todos los elementos relacionados con ellos por la izquierda, y \( \mbox{cl}_R^2(a) \) tiene a los elementos relacionados con los elementos relacionados con \( a \), y así sucesivamente. En total, la clausura \( \mbox{cl}_R(a) \) contiene todos los elementos \( x\in A \) de \( A \) que se pueden conectar con \( a \) mediante una cadena finita \( x = a_0\,R\, a_1\,R\cdots R\, a_k=a \).

Cuando la relación \( R \) es la relación de pertenencia en \( V \), la clausura se llama clausura transitiva de \( a \) y se representa por \( \mbox{ct}\,a \). Así,  \( \mbox{ct}\,a \) contiene a los elementos de \( a \), a los elementos de los elementos de \( a \), etc.

Dada una clase \( A \) y una relación \( R \) en \( A \) que cumpla la primera condición del teorema de Mostowski (que las extensiones de los elementos de \( A \) sean conjuntos), diremos que una subclase \( B\subset A \) es \( R \)-transitiva si cuando \( x,y\in A \) cumplen \( x\,R\,y\land y\in B \) entonces \( x\in B \) (para la relación de pertenencia en \( V \) esto no es sino la transitividad usual).

En estos términos, \( \mbox{cl}_R(a) \) es un conjunto \( R \)-transitivo (en particular, la clausura transitiva de un conjunto es un conjunto transitivo).

Demostración
Si \( x\,R\,y\in \mbox{cl}_R(a) \), entonces existe un natural \( k \) tal que \( y\in \mbox{cl}^k_R(a) \), luego \( x\in \mbox{ext}_R(y)\subset \mbox{cl}_R^{k+1}(a)\subset \mbox{cl}_R(a) \).
[cerrar]

Más aún, \( \mbox{cl}_R(a) \) es la menor clase \( R \)-transitiva \( B\subset A \) tal que \( \mbox{ext}_R(a)\subset B \) (en particular, la clausura transitiva de un conjunto \( x \) es la menor clase transitiva \( B \) tal que \( x\subset B \)).

Demostración
Si \( B\subset A \) es una clase \( R \)-transitiva tal que  \( \mbox{ext}_R(a)\subset B \), entonces, por definición, \( \mbox{cl}_R^0(a)\subset B \). Veamos por inducción que \( \mbox{cl}_R^k(a)\subset B \). Si se cumple para \( k \), un \( y\in \mbox{cl}_R^{k+1}(a) \), o bien cumple \( y\in \mbox{cl}_R^k(a) \), en cuyo caso \( y\in B \) por hipótesis de inducción, o bien existe un \( x\in \mbox{cl}_R^k(a) \) tal que \( y\in \mbox{ext}_R(x) \). Entonces \( x\in B \) por hipótesis de inducción y, como \( y\,R\,x \), también \( y\in B \) porque \( B \) es \( R \)-transitiva. Así concluimos que \( \mbox{cl}_R^{k+1}(a)\subset B \). Como esto vale para todo \( k \), por definición \( \mbox{cl}_R(a)\subset B \).
[cerrar]

Similarmente, \( C(a)=\mbox{cl}_R(a)\cup\{a\} \) es la menor clase \( R \)-transitiva \( B \) tal que \( a\in B \).

Demostración
Tenemos que \( C(a) \) es \( R \)-transitivo, porque si \( x,y\in A \) cumplen \( x\,R\,y\land y\in C(a) \), entonces, o bien \( y\in \mbox{cl}_R(a) \), en cuyo caso \( x\in \mbox{cl}_R(a) \) porque ya sabemos que la clausura es \( R \)-transitiva, luego \( x\in C(a) \), o bien \( y=a \), en cuyo caso \( x\in \mbox{ext}_R(y)\subset \mbox{cl}_R(a)\subset C(a) \).

Por otra parte, si \( B\subset A \) es una clase \( R \)-transitiva y \( a\in B \), entonces \( \mbox{ext}_R(a)\subset B \) y hemos probado que \( \mbox{cl}_R(a)\subset B \), luego también \( C(a)\subset B \).
[cerrar]

Con esto ya podemos probar que las condiciones del teorema de Mostowski son necesarias:

Demostración
En el caso general, supongamos que \( A \) es una clase (no necesariamente un conjunto) y que \( R \) es una relación en \( A \) tal que existe una clase transitiva \( M \) y una biyección \( \pi: A\longrightarrow M \) en las condiciones del teorema de Mostowski.

Entonces, dado \( a\in A \), tenemos que, para todo \( x\in A \) se cumple \( x\,R\,a\leftrightarrow \pi(x)\in \pi(a) \), es decir, que \( \pi[\{x\in A\mid x\,R\,a\}] = \pi(a) \). Así, como \( \pi \) biyecta la clase \( \{x\in A\mid x\,R\,a\} \) con el conjunto \( \pi(a) \), la primera clase es un conjunto, y \( R \) cumple la primera condición que exige el teorema de Mostowski.

Tomemos ahora \( a,b\in A \) tales que \( \forall x\in A(x\,R\,a\leftrightarrow a\,R\,b) \). Esto implica que \( \forall y\in M(y\in \pi(a)\leftrightarrow y\in \pi(b)) \). En efecto, si \( y\in M \), existe un \( x\in A \) tal que \( \pi(x) =y \). Si \( y\in \pi(a) \), entonces \( \pi(x)\in \pi(a) \), luego \( x\,R\,a \) (por la propiedad de la función colapsante), luego \( x\,R\,b \) (por hipótesis) luego \( y=\pi(x)\in \pi(b) \), e igualmente se prueba el recíproco.

Ahora, como \( M \) es transitiva se cumple que \( \forall y(y\in \pi(a)\leftrightarrow y\in \pi(b)) \). En efecto, si \( y\in \pi(a) \), como \( \pi(a)\in M \) y, por transitividad, \( \pi(a)\subset M \), tenemos que \( y\in M \), y hemos probado que entonces \( y\in \pi(b) \). Igualmente se prueba el recíproco.

Con esto tenemos que \( \pi(a) \) y \( \pi(b) \) son conjuntos con los mismos elementos, luego \( \pi(a)=\pi(b) \) y, como \( \pi \) es biyectiva, \( a=b \). Esto prueba que la relación \( R \) es extensional en \( A \).

Por último, supongamos que \( B\subset A \) es una clase no vacía. Entonces \( \pi{[}B{]}\subset M \) es una clase no vacía. Basta probar que \( \pi{[}B{]} \) tiene un elemento \( \in \)-minimal \( m' \), es decir, un elemento tal que \( m'\in \pi{[}B{]} \) pero no existe ningún \( z\in \pi{[}B{]} \) tal que \( z\in m' \). En tal caso, existe un \( m\in B \) tal que \( m'=\pi(m) \) y claramente \( m \) es un \( R \)-minimal de \( B \), ya que si existiera \( x\in B \) tal que \( x\,R\,m \) también tendríamos \( \pi(x)\in m' \), en contradicción con la minimalidad de \( m' \).

Así pues, tenemos que probar que para toda subclase no vacía \( B\subset M \) existe un \( m'\in B \) tal que no existe ningún \( z\in B \) tal que \( z\in m' \) o, lo que es lo mismo, \( m'\cap B=\emptyset \). Pero esto es casi el axioma de regularidad de ZF, que afirma que para todo conjunto \( C\neq \emptyset \) existe un \( m'\in C \) tal que \( m'\cap C =\emptyset \). La única diferencia es que nuestra \( B \) puede ser una clase propia, pero esto no es problema: tomemos cualquier \( z\in B \). Si \( z\cap B=\emptyset \) ya tenemos el \( \in \)-minimal buscado. En caso contrario tomemos \( C=\mbox{ct}\,z\cap B\neq \emptyset \). Por el axioma de regularidad existe un \( m'\in \mbox{ct}\,z\cap B \) tal que \( m'\cap\mbox{ct}\,z\cap B=\emptyset \). Entonces también \( m'\cap B=\emptyset \), pues si existiera un \( u\in m'\cap B \), como \( u\in m'\in \mbox{ct}\,z \) y la clausura es transitiva, sería \( u\in \mbox{ct}\,z \), luego \( u\in m'\cap \mbox{ct}\,z\cap B=\emptyset \).
[cerrar]

También es fácil probar que el colapso de Mostowski es único:

Teorema Sean \( M \) y \( M' \) dos clases transitivas tales que existe \( \pi: M\longrightarrow M' \) biyectiva con la propiedad de que \( \forall xy\in M(x\in y\leftrightarrow \pi(x)\in \pi(y)) \). Entonces \( M=M' \) y \( \pi \) es la identidad.

Como consecuencia, si un mismo par \( (A,R) \) tiene dos colapsos de Mostowski \( \pi_1: A\longrightarrow M_1 \) y \( \pi_2: A\longrightarrow M_2 \), es claro que la composición de una de las biyecciones con la inversa de la otra nos da una biyección \( \pi: M_1\longrightarrow M_2 \) en las condiciones del teorema, por lo que \( M_1=M_2 \) y \( \pi \) es la identidad, lo que a su vez se traduce en que \( \pi_1=\pi_2 \).

Demostración
Basta probar que \( \forall x\in M\ \pi(x)=x \). En caso contrario, si existe un \( x\in M \) tal que \( \pi(x)\neq x \), como \( \mbox{ct}\,x\subset M \), podemos considerar el conjunto \( B=\{u\in \mbox{ct}\,x\cup\{x\}\mid \pi(u)\neq u\}\neq \emptyset \). Por el axioma de regularidad existe un \( u\in B \) tal que \( u\cap B=\emptyset \), es decir, \( \pi(u)\neq u \), pero si \( v\in u \), entonces \( v\notin B \), pero \( v\in u\in \mbox{ct}\,x\cup\{x\} \), que es un conjunto transitivo, luego \( v\in  \mbox{ct}\,x\cup\{x\} \). Consecuentemente, \( v\notin B \) se traduce en que \( \pi(v)=v \).

En suma: tenemos que \( \pi(u)\neq u \), pero \( \pi(v)=v \) para todo \( v\in u \). Pero esto último implica que \( \pi(u)=u \) (contradicción), ya que si \( v\in u \) entonces \( v=\pi(v)\in \pi(u) \), y si \( v'\in \pi(u)\in M' \), entonces existe un \( v\in M \) tal que \( v'=\pi(v)\in \pi(u) \), luego \( v\in u \), luego \( v'=\pi(v)=v \), luego \( v'\in u \).
[cerrar]



Pasamos ya a probar el teorema de Mostowski. Observemos en primer lugar que si \( (A,R) \) cumple las tres hipótesis del teorema, cualquier subclase \( R \)-transitiva \( B\subset A \) las cumple también (con la restricción de \( R \)). En efecto, la \( R \)-transitividad significa que si \( b\in B \) entonces \( \mbox{ext}_R(b) \) es la misma clase calculada en \( A \) o en \( B \). Por lo tanto:

La primera propiedad es que \( \mbox{ext}_R(b) \) sea un conjunto para todo \( b\in B \), y se cumple porque se cumple en \( A \).

La segunda propiedad es que si dos elementos de \( B \) tienen la misma extensión, entonces son iguales, y se cumple en \( B \) porque se cumple en \( A \) y las extensiones son las mismas.

La tercera propiedad es trivial: si \( C\subset B \) es una clase no vacía, entonces tiene un \( R \)-minimal en \( A \), que obviamente es también un \( R \)-minimal en \( B \).

En particular, para cada \( a\in A \), los conjuntos \( \mbox{cl}_R(a) \) y \( C(a) \) son \( R \)-transitivos, luego cumplen las hipótesis del teorema de Mostowski. (Notemos que estamos usando la primera propiedad, puesto que ésta es necesaria para construir la clausura.)

Veamos que, para cada \( a\in A \), existe un conjunto transitivo \( M_a \) y una función colapsante \( \pi_a: C(a)\longrightarrow M_a \).

Demostración
En caso contrario, consideramos la clase \( B=\{a\in A\mid C(a)\mbox{ no tiene funci\'on colapsante }\} \). Si no es vacía, sea \( a\in B \) un elemento \( R \)-minimal, es decir, \( C(a) \) no tiene función colapsante, pero todo \( x\in A \) tal que \( x\,R\,a \) cumple que existe una (única) función colapsante \( \pi_x: C(x)\longrightarrow M_x \).

Aunque este caso está contenido en la prueba que sigue, es ilustrativo ver qué sucede si \( a \) es un \( R \)-minimal de \( A \), es decir, si no existen elementos tales que \( x\,R\,a \) y \( C(a)=\{a\} \). En tal caso, es fácil ver que la única aplicación \( \pi:\{a\}\longrightarrow \{\emptyset\} \) es una función colapsante. Notemos también que la extensionalidad hace que \( A \) sólo pueda tener un elemento \( R \)-minimal, pues dos cualesquiera tienen la misma extensión (vacía), luego son iguales.

Notemos que si \( \pi:A\longrightarrow M \) es una función colapsante y \( B\subset A \) es \( R \)-transitiva, entonces \( \pi{[}B{]} \) es una clase transitiva, pues si \( x\in \pi{[}B{]} \), también \( x\subset \pi{[}B{]} \), ya que si \( u\in x \) tenemos que existe un \( b\in B \) tal que \( x=\pi(b) \) y, por otra parte, \( u\in x\in M \), luego \( u\in M \) porque \( M \) es transitiva, luego existe un \( a\in A \) tal que \( u =\pi(a)\in \pi(b) \), luego \( a\,R\,b \), por definición de función colapsante, luego \( a\in B \) por \( R \)-transitividad, luego \( u=\pi(a)\in \pi{[}B{]} \), lo que prueba que \( x\subset \pi{[}B{]} \).

Por lo tanto, la restricción \( \pi|_B:B\longrightarrow \pi{[}B{]} \) es una función colapsante para \( B \).

Ahora observamos que \( \mbox{cl}_R(a)=\bigcup\limits_{x\in \mbox{ext}_R(a)}C(x) \). En efecto, si \( x\in \mbox{ext}_R(a) \), entonces \( x\in \mbox{cl}_R(a) \), luego \( C(x)\subset \mbox{cl}_R(a) \), porque hemos visto que \( C(x) \) es la menor clase \( R \)-transitiva a la que pertenece \( x \). Esto nos da la inclusión \( \supset \). Para la contraria basta probar que la unión de la derecha es \( R \)-transitiva y contiene a \( \mbox{ext}_R(a) \), pero es inmediato que la unión de conjuntos \( R \)-transitivos es \( R \)-transitivo (a partir de la definición) y si \( x\in \mbox{ext}_R(a) \), entonces \( x\in C(x) \), luego está en la unión. Esto prueba que \( \mbox{ext}_R(a) \) está contenida en la unión y queda probada la igualdad.

Ahora veamos que si \( x, y\in \mbox{ext}_R(a) \), entonces \( C(x)\cap C(y) \) es un conjunto \( R \)-transitivo (la intersección de conjuntos \( R \)-transitivos es obviamente \( R \)-transitivo), luego las restricciones de \( \pi_x \) y de \( \pi_y \) a dicha intersección son ambas funciones colapsantes de la intersección, pero por la unicidad de la función colapsante, concluimos que \( \pi_x \) y \( \pi_y \) coinciden en la parte común de su dominio. Esto nos permite definir \( \pi_0: \mbox{cl}_R(a)\longrightarrow \bigcup\limits_{x\in \mbox{ext}_R(a)}M_x=M_0 \) como la única extensión común de todas las funciones colapsantes \( \pi_x \).

Obviamente es una aplicación suprayectiva y la imagen \( M_0 \) es un conjunto transitivo (por ser unión de conjuntos transitivos). Otro hecho obvio es que si \( u\,R\,v \) son dos elementos de \( \mbox{cl}_R(a) \), entonces \( \pi_0(u)\in \pi_0(v) \). En efecto, existe un \( x\in \mbox{ext}_R(a) \) tal que \( v\in C(x) \), luego también \( u\in C(x) \) (porque es \( R \)-transitivo), luego \( \pi_0(u)=\pi_x(u)\in \pi_x(v)=\pi_0(v) \), porque \( \pi_x \) es una función colapsante.

Veamos ahora que \( \pi_0 \) es inyectiva. En caso contrario

\( B=\{u\in \mbox{cl}_R(a)\mid \exists v\in \mbox{cl}_R(a)(v\neq u\land \pi_0(u)=\pi_0(v))\}\neq\emptyset \),

luego podemos tomar un \( R \)-minimal \( u\in B \). Sea \( v\in \mbox{cl}_R(a) \) tal que \( u\neq v \) pero \( \pi_0(u)=\pi_0(v) \).

Sean \( x,y\in \mbox{ext}_R(a) \) tales que \( u\in C(x),\ v\in C(y) \).

Si \( t\,R\,u \), entonces \( \pi_0(t)\in \pi_0(u)=\pi_0(v)\in M_y \), luego, como \( M_y \) es transitivo, existe un \( t'\in C(y) \) tal que \( \pi_0(t)=\pi_y(t') \). Entonces, \( \pi_y(t')\in \pi_y(v) \) implica que \( t'\,R\,v \). Por otra parte, como \( \pi_0(t)=\pi_0(t') \) pero no puede ser que \( t\m B \), porque \( t\,R\,u \) y \( u \) es \( R \)-minimal de \( B \), concluimos que \( t=t' \), luego \( t\,R\,v \).

Así pues, hemos probado que \( t\,R\,u\rightarrow t\,R\,v \), y la implicación contraria se prueba exactamente igual. Esto significa que \( \mbox{ext}_R(u)=\mbox{ext}_R(v) \), luego \( u=v \) porque \( R \) es extensional, contradicción.

Tenemos probado que \( \pi_0 \) es biyectiva. Ahora probamos que \( \forall uv\in \mbox{cl}_R(a)(u\,R\,v\leftrightarrow \pi_0(u)\in \pi_0(v)) \). Una implicación ya la hemos visto. Para la contraria, si \( \pi_0(u)\in \pi_0(v) \), tomando \( y\in \mbox{ext}_R(a) \) tal que \( v\in C(y) \), tenemos que \( \pi_0(u)\in \pi_y(v)\in M_y \), luego existe un \( u'\in C(y) \) tal que \( \pi_0(u)=\pi_y(u')=\pi_0(u') \), luego \( u=u' \), luego \( u\in C(y) \), luego \( \pi_y(u)\in \pi_y(v) \), luego \( u\,R\,v \), porque \( \pi_y \) es una función colapsante.

Con esto hemos probado que \( \pi_0:\mbox{cl}_R(a)\longrightarrow M_0 \) es una función colapsante. Sea \( \pi_a(a)=\{\pi_0(x)\mid x\,R\,a\}\subset M_0 \). Vamos a probar que si extendemos \( \pi_0 \) a la aplicación \( \pi_a: C(a)=\mbox{cl}_R(a)\cup\{a\}\longrightarrow M_a = M_0\cup\{\pi_a(a)\} \) definiendo precisamente \( \pi_a(a) \) como acabamos de hacerlo, la aplicación \( \pi_a:C(a)\longrightarrow M_a \) es una función colapsante, en contra de la elección de \( a \).

En principio habría que probar (y puede hacerse) que \( a\notin \mbox{cl}_R(a) \), pero no es necesario, pues si \( a\in \mbox{cl}_R(a) \) entonces \( \pi_0 \) sería ya una función colapsante para \( C(a) \). Así que podemos suponer que \( a\notin \mbox{cl}_R(a) \), y entonces \( \pi_a(a)\notin M_0 \), ya que en caso contrario sería \( \pi_a(a)=\pi_0(u) \), para cierto \( u\in \mbox{cl}_R(a) \), y entonces:

Si \( t\,R\,a \), por definición de \( \pi_a(a) \), tenemos  \( \pi_0(t)\in \pi_a(a)=\pi_0(u) \), luego \( t\,R\,u \), porque \( \pi_0 \) es una función colapsante.

Recíprocamente, si \( t\,R\,u \), entonces \( \pi_0(t)\in \pi_0(u)=p_0(a) \), luego \( \pi_0(t)=\pi_0(t') \) con \( t'\,R\,a \), luego \( t=t' \), luego \( t\,R\,a \).

Con esto hemos probado que \( \mbox{ext}_R(a)=\mbox{ext}_R(u) \), luego \( a=u\in \mbox{cl}_R(a) \), en contra de lo supuesto.

Con esto hemos probado que la extensión \( \pi_a: C(a)\longrightarrow M_a \) es biyectiva, y es fácil ver entonces que es una función colapsante (hay que probar que \( M_a \) es transitivo, lo que tampoco ofrece dificultad).
[cerrar]

Ahora, exactamente igual que en la prueba precedente hemos "pegado" todas las funciones \( \pi_x \) para formar una función colapsante \( \pi_0 \), también podemos pegar todas las funciones \( \pi_a \) para formar una función colapsante \( \pi:A\longrightarrow M \) y esto termina la prueba.



Así pues, si \( (M,R) \) es un modelo del lenguaje \( \ulcorner\mathcal L_{\rm tc}\urcorner \) (en particular \( M \) es un conjunto), la primera condición del teorema de Mostowski se cumple trivialmente, y la segunda equivale a que \( (M,R)\vDash \ulcorner\forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y)\urcorner \), es decir, a que el axioma de extensionalidad sea verdadero en \( (M,R) \). Por lo tanto, si \( (M,R) \) es un modelo de \( \ulcorner\mbox{ZF}\urcorner \) (o de un subconjunto finito de axiomas de ZF que incluya al axioma de extensionalidad) la segunda condición del teorema de Mostowski está garantizada también, y la única condición no trivial para que un modelo arbitrario de \( \ulcorner\mbox{ZF}\urcorner \) sea isomorfo a un modelo transitivo (natural) es que la relación \( R \) esté bien fundada en \( M \), cosa que no tiene por qué suceder.

Consideremos ahora un modelo natural \( M \) (pero no necesariamente transitivo) de \( \ulcorner\mbox{ZF}\urcorner \) (o de un conjunto finito de axiomas que incluya al de extensionalidad). Entonces las dos primeras condiciones del teorema de Mostowski están garantizadas (porque lo están para cualquier modelo, según acabamos de indicar) y la tercera también, pues el axioma de regularidad afirma que la relación de pertenencia está bien fundada en cualquier conjunto. Por lo tanto:

Teorema Todo modelo natural de \( \ulcorner\mbox{ZF}\urcorner \) (o de un conjunto finito de axiomas que incluya al de extensionalidad) es isomorfo a un modelo transitivo.

Combinando este resultado con los del hilo anterior concluimos:

(Meta)Teorema Para toda colección finita \( \Gamma \) de axiomas de ZFC se demuestra en ZFC que existe un conjunto transitivo numerable \( M \) tal que \( M\vDash\ulcorner\Gamma\urcorner \).

A partir del próximo hilo trataremos de entender cómo son estos modelos transitivos (numerables o no). Dado que sólo podemos garantizar la existencia de modelos de un número finito de axiomas de ZFC es costumbre sobrentender que cuando decimos "Sea \( M \) un modelo (transitivo) de ZFC" queremos decir en realidad que \( M \) es un modelo de una cantidad finita arbitrariamente grande de axiomas de ZFC. Esto no supone ninguna restricción relevante. Por ejemplo, imaginemos que queremos demostrar que no es posible demostrar que \( 2^{\aleph_0}=\aleph_1 \). Para ello, basta construir un modelo transitivo de ZFC en este sentido en el que, por ejemplo, \( 2^{\aleph_0}=\aleph_2 \). En efecto, aunque sólo hemos demostrado que, para todo conjunto finito de axiomas de ZFC es posible construir un modelo de dichos axiomas más \( 2^{\aleph_0}=\aleph_2 \), esto justifica que no es posible demostrar \( 2^{\aleph_0}=\aleph_1 \). El argumento es el siguiente:

Supongamos que alguien trajera una demostración a partir de los axiomas de ZFC de que \( 2^{\aleph_0}=\aleph_1 \). Dicha demostración sólo podría usar una cantidad finita de axiomas. Viendo cuáles son dichos axiomas podríamos demostrar en ZFC la existencia de un modelo \( M \) que cumpliera dichos axiomas más \( 2^{\aleph_0}=\aleph_2 \), pero la existencia de dicha demostración nos permitiría (según hemos visto) demostrar en ZFC que \( M\vDash 2^{\aleph_0}=\aleph_1 \), con lo cual habríamos demostrado en ZFC:

\( M\vDash 2^{\aleph_0}=\aleph_1\land M\vDash 2^{\aleph_0}=\aleph_2 \),

es decir, habríamos probado una contradicción en ZFC. En resumen: si en ZFC es posible probar \( 2^{\aleph_0}=\aleph_1 \), entonces ZFC es contradictorio. Y el argumento es constructivo: es posible programar a un ordenador para que si le damos una demostración de \( 2^{\aleph_0}=\aleph_1 \) en ZFC, el ordenador construya mecánicamente una demostración de una contradicción en ZFC.