Autor Tema: Número 1. (2012) - 2. NFA

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

24 Febrero, 2012, 09:45 pm
Respuesta #40

Raúl Aparicio Bustillo

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
Citar
La estratificación está puesta para evitar ante todo que se pueda probar que la colección de todos los conjuntos que no se pertenecen a sí mismos sea un conjunto

Pero da la sensación de que la restricción es demasiado fuerte, desde luego la estratificación evita la circularidad en las fórmulas atómicas con el relator \(  \in{}  \). Una circularidad en la que para ver si un objeto pertenece a un conjunto haya que mirar precisamente dicho hecho, como ocurre en la paradoja de Russell ( y sospecho que en muchas de las otras paradojas conjuntistas) no es aceptable . Pero ese tipo de circularidad ya se evita exigiendo que sean de tipos diferentes los 2 términos relacionados, no veo la necesidad de que sean tipos consecutivos y de que se mantengan los tipos de cada variable cuando se forma una fórmula compuesta a partir de 2 atómicas diferentes del tipo \(  a \in{b}  \).

Tampoco termino de ver la necesidad de igualar el tipo de las variables en relaciones con \(  =   \), y en las componentes del par ordenado. Aunque desde luego esta última no sé si necesaria pero es al menos una forma de evitar la inconsistencia en el momento en que la teoría hay conjuntos no cantorianos: no veo otra forma de prohibir una biyección de la forma \(  x\longrightarrow{\{x\}}  \) sobre un dominio que sea no cantoriano,  y tengo la sospecha que el "capricho" de tener conjunto universal en nuestra teoría y complementario de cada conjunto con respecto al universo también, hace que efectivamente tenga que haber conjuntos no cantorianos (este último parrafo tan sólo son conjeturas)

24 Febrero, 2012, 09:57 pm
Respuesta #41

Carlos Ivorra

  • Administrador
  • Mensajes: 9,184
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero ese tipo de circularidad ya se evita exigiendo que sean de tipos diferentes los 2 términos relacionados, no veo la necesidad de que sean tipos consecutivos y de que se mantengan los tipos de cada variable cuando se forma una fórmula compuesta a partir de 2 atómicas diferentes del tipo \(  a \in{b}  \).

Tampoco termino de ver la necesidad de igualar el tipo de las variables en relaciones con \(  =   \),

Sin esas condiciones podrías expresar \( x\notin x \) en la forma \( \exists y (y\notin x\land y = x) \) y la fórmula estaría estratificada (si es que admites que los tipos en \( y = x \) no necesiten ser iguales, o que cada variable pueda tener un tipo diferente en cada subfórmula).

y en las componentes del par ordenado.

Eso no es una restricción, en el sentido de una limitación, sino todo lo contrario, algo que te da más posibilidades que si no dispusieras de ello.

Aunque desde luego esta última no sé si necesaria pero es al menos una forma de evitar la inconsistencia en el momento en que la teoría hay conjuntos no cantorianos: no veo otra forma de prohibir una biyección de la forma \(  x\longrightarrow{\{x\}}  \) sobre un dominio que sea no cantoriano,  y tengo la sospecha que el "capricho" de tener conjunto universal en nuestra teoría y complementario de cada conjunto con respecto al universo también, hace que efectivamente tenga que haber conjuntos no cantorianos (este último parrafo tan sólo son conjeturas)

Claro. El conjunto \( V \) no puede ser cantoriano, pues si lo fuera llevaría a una contradicción al aplicarle el argumento del teorema de Cantor.

25 Febrero, 2012, 12:05 am
Respuesta #42

Raúl Aparicio Bustillo

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
Citar
Sin esas condiciones podrías expresar \(  x\notin x  \) en la forma \(  \exists y (y\notin x\land y = x)  \)y la fórmula estaría estratificada (si es que admites que los tipos en [y = x] no necesiten ser iguales, o que cada variable pueda tener un tipo diferente en cada subfórmula).

Pues es verdad. Pero ¿la estratificación es la condición mínima que hay que exigir a una fórmula para que no encierre algún tipo de circularidad, en el caso de fórmulas construidas mediante conectivas lógicas a partir de relaciones \(  \in{}]  \) e =  ?

Lo que no termino de ver es cuando dices refiriendote a la estratificación de los pares ordenados:

Citar
Eso no es una restricción, en el sentido de una limitación, sino todo lo contrario, algo que te da más posibilidades que si no dispusieras de ello.

La no existencia de la función singlete \(  x\longrightarrow{{x}}  \)  en conjuntos no cantorianos salva a la teoría de la inconsistencia claro, en ese sentido da más posibilidades, si no no hay universo, pero la verdad que se hace algo incomodo tener que descartar funciones definibles

¿también se podría, no exigiendo la estratificación a los pares ordenados, camuflar la circularidad de ciertas definiciones usando pares ordenados en la definición ? ¿Encierra quizás por ese motivo la función singlete e \(  x\longrightarrow{{x}}  \)  algún tipo de singularidad?

No sé si en esto último  entraríamos ya en la cuestión de la naturaleza del par ordenado:  intuitivamente da la sensación de que son átomos más bien, supongo que si es un par ordenado de átomos será atomo y que será conjunto sólo en el caso de que el par sea de conjuntos. No sé si tienes pensado en tu exposición de NFA tratar un poco más este tema, pero creo sería interesante

Para poner llaves en LaTeX debes escribir \{ en lugar de {, porque si no, no se ven.

25 Febrero, 2012, 01:18 am
Respuesta #43

Carlos Ivorra

  • Administrador
  • Mensajes: 9,184
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Citar
Sin esas condiciones podrías expresar \(  x\notin x  \) en la forma \(  \exists y (y\notin x\land y = x)  \)y la fórmula estaría estratificada (si es que admites que los tipos en [y = x] no necesiten ser iguales, o que cada variable pueda tener un tipo diferente en cada subfórmula).

Pues es verdad. Pero ¿la estratificación es la condición mínima que hay que exigir a una fórmula para que no encierre algún tipo de circularidad, en el caso de fórmulas construidas mediante conectivas lógicas a partir de relaciones \(  \in{}]  \) e =  ?

Dudo que haya una condición mínima. Hay condiciones que lo consiguen de un modo y otras de otro.

Lo que no termino de ver es cuando dices refiriendote a la estratificación de los pares ordenados:

Citar
Eso no es una restricción, en el sentido de una limitación, sino todo lo contrario, algo que te da más posibilidades que si no dispusieras de ello.

Pues que siempre puedes considerar pares ordenados no estratificados, desde los usuales \( (x, y)\equiv \{\{x\},\{x,y\}\} \), hasta otros que suban más el tipo, como  \( (x, y)\equiv \{\{\{\{x\},\{x,y\}\}\}\} \), e incluso es posible definir (aunque es más complicado) otros que sólo suban el tipo una unidad. Disponer de pares ordenados que no suban el tipo es una ventaja más, algo cuya existencia debes postular (o demostrar), no una limitación que te impida hacer nada. Si no te gustan los pares nivelados, siempre puedes no usarlos. Postular su existencia no te restringe en nada.

La no existencia de la función singlete \(  x\longrightarrow{{x}}  \)  en conjuntos no cantorianos salva a la teoría de la inconsistencia claro, en ese sentido da más posibilidades, si no no hay universo, pero la verdad que se hace algo incomodo tener que descartar funciones definibles

Je, je. Es que eso es lo que hace de NFA una teoría "extraña", que niega la existencia de conjuntos que ningún matemático "clásico" estaría dispuesto a admitir que no existen. Obliga a quien quiera trabajar en la teoría a decir "esto existe, pero oficialmente no existe", y eso no es nada natural. En ZFC también pasa eso, pero con colecciones más "exóticas", alejadas de la práctica matemática corriente. En NFA pasa con conjuntos "cotidianos". No obstante, hay que reconocer que el axioma de cómputo (y alguno otro más fuerte) alivia bastante la situación.

¿también se podría, no exigiendo la estratificación a los pares ordenados, camuflar la circularidad de ciertas definiciones usando pares ordenados en la definición ? ¿Encierra quizás por ese motivo la función singlete e \(  x\longrightarrow{{x}}  \)  algún tipo de singularidad?

No te entiendo. Insisto en que la estratificación de los pares ordenados no es una exigencia, sino una concesión. Bueno, en realidad creo que nos estamos liando: lo que se "exige" o "concede" no es que los pares ordenados estén estratificados, sino que estén nivelados, es decir, que su tipo sea el mismo que el de sus componentes. Siempre puedes definir pares ordenados no estratificados, pero no podrías hacer nada con ellos, porque no podrías usarlos para definir conjuntos. Lo que se hace para simplificar NFA es, no limitarse a construir los pares ordenados usuales, que resultan estratificados de tipo dos unidades superior a los tipos de sus componentes (para obtener esos pares no necesitas aludir a ellos en la definición de estratificación), sino postular la existencia de pares ordenados "mejores", nivelados. Pero postular la existencia de algo no es una limitación, sino todo lo contrario.

No sé si en esto último  entraríamos ya en la cuestión de la naturaleza del par ordenado:  intuitivamente da la sensación de que son átomos más bien, supongo que si es un par ordenado de átomos será atomo y que será conjunto sólo en el caso de que el par sea de conjuntos.

Si no supones la existencia de pares ordenados nivelados, es decir, si no mencionas pares ordenados en la definición de estratificación, puedes trabajar (más incómodamente) con pares ordenados usuales, y demostrar (suponiendo el axioma de infinitud, que está implícito en la existencia de pares nivelados) que \( |V\times V| = |V| \). En otras palabras, pruebas que existe una biyección \( F: V\times V\longrightarrow V \) biyectiva (de hecho, para lo que voy a decir basta con tomar F inyectiva). Entonces, puedes definir \( (x, y) \equiv F(x,y) \) y tienes un término que cumple lo que yo he postulado sobre pares ordenados nivelados.

Puesto que la aplicación F la puedes elegir arbitrariamente y retocarla como quieras, siempre puedes tomarla de forma que la imagen de un par de átomos sea un átomo. Lo que no puedes hacer es exigir que todos los pares ordenados sean conjuntos, porque hemos visto que hay menos conjuntos que átomos, pero sí puedes exigir que todos los pares ordenados sean átomos, o que los de los átomos sean átomos y los de los conjuntos conjuntos, pues siempre puedes tomar una F que cumpla cualquiera de estas condiciones.

No sé si tienes pensado en tu exposición de NFA tratar un poco más este tema, pero creo sería interesante

En la exposición de NFA sería complicado, porque he supuesto la existencia de pares nivelados desde un principio, luego resultaría tonto construirlos en ese contexto. Trataré el asunto al hablar de modelos de NFA.

25 Febrero, 2012, 06:41 pm
Respuesta #44

Raúl Aparicio Bustillo

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
 
Citar
lo que se "exige" o "concede" no es que los pares ordenados estén estratificados, sino que estén nivelados, es decir, que su tipo sea el mismo que el de sus componentes

Sí, creo que he sido yo el causante de la confusión: cuando decía par ordenado estratificado me refería a par ordenado nivelado . Estratificada o no estratificada está una fórmula, un término en forma de par ordenado está si acaso  nivelado, en el caso de que los términos que formen su primera componente y los que formen su segunda componente tengan el mismo tipo. Y a la hora de mirar la estratificación de la fórmula en la que aparezca el par ordenado al par ordenado nivelado le tengo que asignar el tipo de sus componentes. Si en la fórmula aparece un par ordenado no nivelado entonces la fórmula ya no está estratificada. Es así ¿no?

Citar
¿también se podría, no exigiendo la estratificación a los pares ordenados, camuflar la circularidad de ciertas definiciones usando pares ordenados en la definición ? ¿Encierra quizás por ese motivo la función singlete \(  x\longrightarrow{\{x}\}}  \) algún tipo de singularidad?

Quise decir "circularidad", no singularidad, aunque creo que aún así debería matizar un poco a qué tipo de impredicatividad me estoy refiriendo. Lo dejo para otro post


25 Febrero, 2012, 09:24 pm
Respuesta #45

Carlos Ivorra

  • Administrador
  • Mensajes: 9,184
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Citar
lo que se "exige" o "concede" no es que los pares ordenados estén estratificados, sino que estén nivelados, es decir, que su tipo sea el mismo que el de sus componentes

Sí, creo que he sido yo el causante de la confusión: cuando decía par ordenado estratificado me refería a par ordenado nivelado . Estratificada o no estratificada está una fórmula, un término en forma de par ordenado está si acaso  nivelado, en el caso de que los términos que formen su primera componente y los que formen su segunda componente tengan el mismo tipo. Y a la hora de mirar la estratificación de la fórmula en la que aparezca el par ordenado al par ordenado nivelado le tengo que asignar el tipo de sus componentes. Si en la fórmula aparece un par ordenado no nivelado entonces la fórmula ya no está estratificada. Es así ¿no?

Creo que sigue flotando alguna clase de confusión. El par ordenado que se introduce axiomáticamente está nivelado, en el sentido de que tiene el mismo tipo que sus componentes, mientras que el par ordenado usual de ZFC, es decir, \( (x,y)\equiv \{\{x\},\{x,y\}\} \) está estratificado, y define fórmulas estratificadas, pero no está nivelado, porque tiene tipo dos unidades mayor que sus componentes.

26 Febrero, 2012, 01:29 pm
Respuesta #46

Carlos Ivorra

  • Administrador
  • Mensajes: 9,184
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El axioma de cómputo (en adelante AC) admite varias versiones equivalentes. Fue introducido por Rosser en la forma siguiente:

\( \forall n\in \mathbb{N}\ |\{1,\ldots, n\}|=n \)

Aunque casi pueda parecer "vergonzoso" que esta afirmación necesite ser introducida como axioma, lo cierto es que no puede probarse en NFA. Una consecuencia que puede extraerse de aquí es que el hecho de que algo sea un axioma en una teoría no significa que exprese una verdad profunda y sutil "indemostrable", sino que es una mera cuestión técnica que depende de los axiomas concretos de la teoría. Por ejemplo, el hecho de que en ZFC sin el axioma de infinitud no pueda demostrarse el axioma de infinitud no debe llevarnos a suponer que la existencia de conjuntos infinitos sea algo "dudoso" o "que escapa al razonamiento humano". De hecho, en ZFC sin el axioma de infinitud se demuestra la existencia de infinitos conjuntos (los números naturales, por ejemplo), lo que no puede probarse es que estén contenidos en un conjunto, y eso es un mero tecnicismo (con consecuencias drásticas en la teoría, pero un tecnicismo al fin y al cabo). Por otro lado, en NFA sí que puede demostrarse el axioma de infinitud (la existencia del conjunto de los números naturales).

Hecha esta digresión, pasamos a observar que si llamamos \( I_n = \{m\mid m\in \mathbb{N}\land 1\leq m\leq n\} \), tenemos una biyección \( f: \text{Ord}_n^<\longrightarrow I_n \) dada por \( m\mapsto \text{card}(m)+1 \), con lo que en NFA se prueba que \( |I_n| = |\text{Ord}_n^<| = T^2(n) \).

Por lo tanto, el axioma de cómputo equivale a que todos los ordinales finitos cumplen \( T^2(n)=n \). Ahora bien, esto implica que \( T(n)=n \), ya que si fuera \( T(n)<n \), entonces \( n=T^2(n)<T(n) \), contradicción, y si fuera \( n<T(n) \) entonces \( T(n)<T^2(n)=n \), contradicción.

Por lo tanto, tenemos dos equivalencias del axioma de cómputo:

Todo ordinal finito cumple \( T(n)=n \).
y
Todo cardinal finito (todo número natural) cumple \( T(n)=n \).

En los términos introducidos en el mensaje anterior a su vez podemos expresar estas dos variantes como sigue:

Todos los ordinales finitos son cantorianos.
y
Todos los números naturales son cantorianos.

En el mensaje anterior demostramos que si todos los ordinales menores que un ordinal dado son cantorianos, entonces el ordinal dado es fuertemente cantoriano. Recíprocamente, todos los ordinales menores que un ordinal fuertemente cantoriano son fuertemente cantorianos. Esto nos da las equivalencias siguientes (del axioma de cómputo):

\( \omega \) es un ordinal fuertemente cantoriano.

Todos los ordinales finitos son fuertemente cantorianos.

De las propias definiciones se sigue que cada una de ellas equivale a una de las siguientes:

\( \aleph_0 \) es un cardinal fuertemente cantoriano.

Todos los números naturales son fuertemente cantorianos.

Hasta aquí las equivalencias. Ahora destacamos algunas consecuencias. Por los resultados del mensaje anterior, el hecho de que los ordinales finitos sean fuertemente cantorianos implica que también lo son los cardinales \( \aleph_n \), lo que a su vez implica que \( \kappa_0 \) no puede ser ninguno de ellos, luego existe el cardinal \( \aleph_\omega \), cosa que no puede probarse en NFA. De hecho, \( \aleph_\omega \) es un cardinal fuertemente cantoriano, al igual que  \( \aleph_{\omega+1}, aleph_{\omega+2},\ldots aleph_{\omega+\omega} \) y muchos cardinales más. Lo mismo vale cambiando \( \aleph \) por \( \beth \). Esto significa que todos los conjuntos numerables son fuertemente cantorianos, al igual que todos los de cardinal \( 2^{\aleph_0} \) (o menor), y todos los de cardinal \( 2^{2^{\aleph_0}} \), etc.

En resumen, suponiendo AC, cualquier conjunto que se vaya a encontrar cualquier matemático en su trabajo cotidiano (excluyendo a los que trabajan en teoría de conjuntos) es fuertemente cantoriano.

¿Y cuál es la ventaja de disponer de tantos conjuntos fuertemente cantorianos?

Por lo pronto, el hecho de que los números naturales cumplan \( T(n) = n \) y, por consiguiente, \( T^m(n)=n \), para todo número entero \( m \), se traduce en que podemos permitir que los números naturales violen la estratificación en las fórmulas en las que aparezcan. En efecto, el tipo de \( T^m(n) \) es el tipo de la variable \( n \) más el número entero \( m \). Por ejemplo, habíamos explicado que en NFA no podemos demostrar que la unión de \( m \) conjuntos disjuntos de cardinal \( n \) tiene cardinal \( mn \) porque la fórmula siguiente no está estratificada:

\( m_1\in \mathbb{N}_2\land \forall A_1(|A_1|_2=m_2\land \forall x_0\in A_1\ (\text{cto}\,x_0\land |x_0|_1=n_1\land{} \) \( \forall x_0y_0\in A_1(x_0\neq y_0\rightarrow x_0\cap y_0=\emptyset_0)\rightarrow |\bigcup A_1|_1=m_1n_1) \).

El problema está en que la variable \( m \) necesita aparecer con tipo \( 2 \) en un sitio y con tipo \( 1 \) en otro. En NFA esto no tiene arreglo, pero en NFA + AC basta sustituir la fórmula anterior por

\( m_1\in \mathbb{N}_2\land \forall A_1(|A_1|_2=T(m_1)_2\land \forall x_0\in A_1\ (\text{cto}\,x_0\land |x_0|_1=n_1\land{} \) \( \forall x_0y_0\in A_1(x_0\neq y_0\rightarrow x_0\cap y_0=\emptyset_0)\rightarrow |\bigcup A_1|_1=m_1n_1) \).

Como \( \forall m\in \mathbb{N}\ T(m)=m \), esta fórmula es equivalente a la anterior, pero está estratificada y define un conjunto de números naturales, el conjunto

\( A = \{m\mid m\in \mathbb{N}\land \forall A(|A|=T(m)\land \forall x\in A\ (\text{cto}\,x\land |x|=n\land{} \)\( \forall xy\in A(x\neq y\rightarrow x\cap y=\emptyset)\rightarrow |\bigcup A|=mn)\} \),

que es el mismo conjunto que

\( A = \{m\mid m\in \mathbb{N}\land \forall A(|A|=m\land \forall x\in A\ (\text{cto}\,x\land |x|=n\land{} \)\( \forall xy\in A(x\neq y\rightarrow x\cap y=\emptyset)\rightarrow |\bigcup A|=mn)\} \).

Observemos que no podemos asegurar directamente la existencia de este conjunto (con la segunda expresión), porque la fórmula que lo define no está estratificada, pero sí que podemos probar que existe \( A \) con la primera definición y resulta que satisface también la segunda definición no estratificada. En la práctica, en lugar de introducir Ts en las fórmulas, basta tener presente que no es necesario ajustar los tipos de las variables que representen números naturales, pues si incumplen la estratificación siempre se pueden sustituir por términos \( T^k(x) \) (incluso con exponentes diferentes en cada sitio) para cuadrar la estratificación.

Una vez definido \( A \), ya podemos aplicarle el principio de inducción para probar sin dificultad que \( A=\mathbb{N} \). La única dificultad de la prueba era demostrar que existe \( A \).

En realidad, no sólo podemos "subvertir" la estratificación en variables que recorran números naturales, sino en cualquier variable que recorra un conjunto fuertemente cantoriano. En efecto, si \( X \) es un conjunto fuertemente cantoriano y \( f:X\longrightarrow \mathcal P_1X \) es la aplicación dada por \( f(x)=\{x\} \), podemos definir

\( T_X(x)\equiv f^{-1}(\{x\},\qquad T_X^{-1}(x)\equiv \bigcup f(x) \),

de modo que los términos \( T_X(x) \) y \( T_X^{-1}(x) \) están estratificados, el primero sube el tipo una unidad y el segundo lo baja una unidad, pero trivialmente \( \forall x\in X\ T_X(x)=x \) y \( \forall x\in X\ T_X^{-1}(x)=x \).

Esto nos permite ajustar los tipos de una variable \( x \) que recorra el conjunto \( X \) en una fórmula sustituyendo cada una de sus apariciones por un término \( T_X^m(x) \), para un número entero \( m \) adecuado.

Por ejemplo, supongamos que \( X \) es un conjunto fuertemente cantoriano en el que hemos definido una relación de equivalencia \( R \) y queremos definir la proyección \( p: X\longrightarrow X/R \) dada por \( p(x)=[x] \). Esto no puede hacerse si \( X \) es arbitrario, porque la clase de equivalencia \( [x] \) tiene tipo una unidad mayor que \( x \), pero si \( X \) es fuertemente cantoriano basta definir \( p(x) = [T_X^{-1}(x)] \). Ahora la definición está estratificada, pero para todo \( x\in X \) se cumple que \(  [T_X^{-1}(x)] = [x] \), luego hemos definido exactamente la aplicación que queríamos definir.

En la práctica no es necesario introducir el operador \( T_X^{-1} \), sino que basta tener presente que las variables que recorren conjuntos fuertemente cantorianos no necesitan ser estratificadas. Como, según hemos destacado, en las matemáticas "cotidianas" uno trabaja siempre con fórmulas que hablan de objetos pertenecientes a conjuntos fuertemente cantorianos, la conclusión es que la necesidad de comprobar que las fórmulas que usamos para definir conjuntos estén estratificadas desaparece casi por completo. (Sólo hay que recordarla si en algún momento introducimos una condición del tipo "existe un conjunto, o un cardinal, etc. tal que...", sin que podamos prescribir un conjunto fuertemente cantoriano donde sepamos que vaya a estar ese conjunto, o cardinal, etc. que necesitamos que exista.

Naturalmente, las condiciones de estratificación no dejarán de estar presentes en teorías generales: si uno estudia espacios topológicos en general, eso incluye espacios topológicos sobre conjuntos que no sean fuertemente cantorianos. Ahora bien, si uno se restringe a considerar espacios topológicos fuertemente cantorianos (con lo cual no pierde ningún ejemplo "cotidiano" al que se pueda aplicar la topología) automáticamente puede prescindir "casi por completo" de las restricciones de estratificación.

Si el lector considera que esto es demasiado vago (que lo es), ello se debe a que la forma de ilustrar estas ideas es simplemente formalizando las matemáticas en NFA + AC (por ejemplo, la construcción de los conjuntos de números, los resultados básicos del análisis de funciones de variable real, etc.) Al hacerlo se vería claramente que es posible olvidarse completamente de la estratificación.

El axioma de cómputo no puede demostrarse en NFA, y una razón profunda es que implica la existencia de un modelo de NFA y, por consiguiente, la consistencia de NFA. El teorema de incompletitud de Gödel asegura que un axioma que implique la consistencia de una teoría no puede ser demostrado en dicha teoría.

Más precisamente, AC implica la existencia de un modelo de la teoría de Zermelo con el axioma de elección (es decir, ZFC sin el axioma del reemplazo y con el axioma de selección de subconjuntos en su lugar), y a partir de un modelo de ZC puede construirse un modelo de NFA.

04 Marzo, 2012, 01:37 pm
Respuesta #47

Carlos Ivorra

  • Administrador
  • Mensajes: 9,184
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Una vez expuestos los resultados básicos de NFA, vamos a ver que en ZFC podemos construir un modelo de NFA, lo cual se traduce en que si ZFC es consistente entonces NFA también lo es. En este mensaje expondremos los preparativos para la prueba.

Más concretamente, vamos a ver que en ZFC puede construirse un modelo de NFA a partir de un modelo de ZC, donde ZC es la teoría que resulta de eliminar el axioma del reemplazo de ZFC y sustituirlo por el axioma de especificación.

Remito al hilo http://rinconmatematico.com/foros/index.php/topic,21322.0.html de argentinator donde están detallados estos axiomas. Allí el axioma de especificación aparece como parte de los axiomas de ZFC, si bien puede demostrarse a partir del axioma de reemplazo, por lo que es redundante, pero si eliminamos el axioma de reemplazo necesitamos incluir el axioma de especificación, ya que deja de ser un teorema.

¿Por qué partimos de un modelo de ZC en lugar de ZFC? Porque en ZFC no puede demostrarse la existencia de un modelo de ZFC, pero es fácil construir modelos de ZC.

En efecto, en ZFC podemos definir: \( V_0 = \emptyset \), para cada ordinal \( \alpha \) tomamos \( V_{\alpha+1}=\mathcal PV_\alpha \) y para cada ordinal límite \( \lambda \) definimos \( V_\lambda = \bigcup\limits_{\delta<\lambda}V_\delta \).

Tenemos así definida una sucesión transfinita de conjuntos, y una simple inducción demuestra que son transitivos, es decir, que si \( x\in V_\alpha \) entonces \( x\subset V_\alpha \).

Es fácil ver que para todo ordinal límite \( \lambda>\omega \) se cumple que \( V_\lambda \) es un modelo (transitivo) de ZC, es decir, que si definimos "conjunto" como "elemento de \( V_\lambda \) y "pertenencia" como la pertenencia usual restringida a \( V_\lambda \) esos conjuntos específicos con esa pertenencia cumplen todos los axiomas de ZC.

Por ejemplo, para probar el axioma de especificación tomamos un conjunto \( A\in V_\lambda \) y otros conjuntos \( x_1,\ldots, x_n\in V_\lambda \) y una fórmula \( \phi(x,x_1,\ldots, x_n) \), y hemos de probar que el conjunto

\( \{x\in A\mid \phi(x,x_1,\ldots, x_n)\} \)

es también un "conjunto" en el sentido específico que le estamos dando a la palabra, es decir, hemos de probar que pertenece a \( V_\lambda \). Ahora bien, existe un \( \delta<\lambda \) tal que \( A\in V_\delta \). Así \( \{x\in A\mid \phi(x,x_1,\ldots, x_n)\}\subset A\subset V_\delta \), luego \( \{x\in A\mid \phi(x,x_1,\ldots, x_n)\}\in \mathcal PV_\delta = V_{\delta+1}\subset V_\lambda \).

Nota para entendidos
En realidad habría que haber probado que el conjunto definido por la relativización de \( \phi \) a \( V_\lambda \) está en \( V_\lambda \), pero da igual, pues si vale para toda fórmula vale también en particular para la relativización de toda fórmula.
[cerrar]

En particular \( V_{\omega+\omega}=V_{\omega\cdot 2} \) es el modelo más sencillo de ZC que puede construirse de esta forma (aunque no el más pequeño, pues, naturalmente, puede probarse que existen modelos numerables). Observemos que está formado por todos los conjuntos que se obtienen a partir del conjunto vacío mediante un número finito de aplicaciones del operador "partes de", lo que nos lleva al conjunto \( V_\omega \) (que sólo contiene conjuntos finitos y es un modelo de ZFC menos el axioma de infinitud), más todos los conjuntos que pueden obtenerse a partir de \( V_\omega \) aplicando otra vez un número finito de veces el operador "partes de".

Según decimos, es posible construir un modelo de NFA a partir de cualquier modelo de ZC, como por ejemplo \( V_{\omega\cdot 2} \)

Cabe advertir que este resultado puede refinarse en varios aspectos: por una parte no es necesario partir de un modelo de ZC, sino que basta un modelo de una teoría más débil, la teoría de MacLane (MAC), que resulta de restringir el axioma de especificación a fórmulas de tipo \( \Delta_0 \), es decir, que sólo tienen cuantificadores acotados, de la forma \( \forall x\in y \) o \( \exists x\in y \); por otra parte, no es necesario trabajar en ZFC, sino que bastaría por ejemplo trabajar en la teoría de Mostowski, que es una teoría que sigue siendo mucho más débil que ZFC y que resulta de añadir un axioma a MAC cuya consistencia es probable a partir de la de MAC (en el mismo sentido en que la consistencia de la hipótesis del continuo es probable a partir de la de ZFC).

También hay otro punto que debe ser matizado: en los modelos \( V_\lambda \) puede definirse la sucesión \( \{V_\delta\}_{\delta<\lambda} \), mientras que la existencia de esta sucesión no puede demostrarse en ZC. Nosotros vamos a apoyarnos en el hecho de que en nuestro modelo de partida pueden definirse los conjuntos \( V_\alpha \) para todo ordinal \( \alpha \) y cumplen que todo conjunto pertenece a un \( V_\alpha \), por lo tanto, estamos partiendo de un modelo que cumple más de lo que podemos asegurar que cumple cualquier modelo de ZC. Esto no hace que la afirmación que hemos hecho sea falsa: a partir de todo modelo de ZC puede construirse un modelo de NFA, porque sucede que a partir de todo modelo de ZC puede construirse un modelo en el que pueden definirse los conjuntos \( V_\alpha \). (En general sólo pueden definirse como una clase bien ordenada de conjuntos, sin que necesariamente se pueda asignar un ordinal a cada uno de ellos, lo cual únicamente complica un poco la notación, al tener que trabajar directamente con los conjuntos \( V_\alpha \) sin poder hacer referencia a los ordinales como subíndices, pero no es un obstáculo esencial. Aquí evitaremos estos tecnicismos partiendo de un modelo de ZC en el que cada ordinal \( \alpha \) determina un conjunto \( V_\alpha \) y todo conjunto pertenece a un \( V_\alpha \).)



El primer paso de la construcción es muy técnico, así que omitiré la prueba, salvo que haya alguien interesado que me pida los detalles. Se trata de probar el teorema siguiente, que es un caso particular del llamado teorema de Ehrenfeucht-Mostowski:

Dado un modelo \( M \) de un lenguaje formal (en nuestro caso el lenguaje de ZFC) en el que pueda definirse un subconjunto \( A\subset M \) (que no tiene por qué ser la extensión de un conjunto en \( M \), y que en nuestro caso será el conjunto formado por los elementos de \( M \) que satisfacen la definición de ordinal infinito, que no es un conjunto en \( M \)) en el que pueda definirse una relación de orden total (en nuestro caso la relación de orden usual en los ordinales), existe otro modelo \( M' \) que es elementalmente equivalente a \( M \) (es decir, que las sentencias verdaderas en \( M \) son las mismas que las sentencias verdaderas en \( M' \)) en el que existe un automorfismo \( J: M\longrightarrow M' \) que no deja invariante a algún elemento de \( A \).

Aquí es importante que si partimos de un modelo \( M \) de ZC, no es necesario que sea un modelo natural, es decir, un modelo en el que la relación de pertenencia es la pertenencia usual, como ocurre en los modelos \( V_\lambda \), sino que la pertenencia puede interpretarse mediante una relación \( E\subset M\times M \) arbitraria. Pero, tanto si partimos de un modelo natural como si no, el modelo \( M' \) resultante no tiene por qué ser natural, sino que tendrá su propia relación de pertenencia \( E'\subset M'\times M' \).

Que \( J \) sea un automorfismo significa, en este caso, que es una biyección \( J: M'\longrightarrow M' \) con la propiedad de que \( \forall xy\in M'(x\,E\,y\leftrightarrow J(x)\,E'\,J(y)) \). Puesto que \( J \) respeta la pertenencia y también la igualdad (por ser biyectiva) y toda afirmación del lenguaje de ZC se construye a partir de fórmulas construidas por variables, pertenencias e igualdades, es fácil concluir que \( J \) respeta todas las fórmulas, es decir, que si \( \phi(x_1,\ldots, x_n) \) es una fórmula cualquiera, entonces

\( \forall x_1\cdots x_n\in M' (M'\vDash \phi(x_1,\ldotx, x_n)\leftrightarrow M'\vDash \phi(J(x_1),\ldots, J(x_n)) \).

Conozco dos formas de probar este resultado: una requiere más familiaridad con la teoría de modelos, pues se basa en el teorema de compacidad y en la construcción de submodelos mediante funciones de Skolem; la otra es más conjuntista, pues en ella se obtiene el modelo como límite inductivo de un sistema de ultrapotencias del modelo de partida. Puestos a contar una de las dos, me parecería más sencillo explicar la segunda. Está expuesta en el artículo de Holmes "Strong Axioms of Infinity in NFU", que se encuentra fácilmente en internet. (Otra cosa es que, en general, y en este caso en particular, Holmes se explica como un libro cerrado.)

Aplicando este teorema tenemos un modelo \( (M,E) \), donde \( E\subset M\times M \), que cumple las mismas sentencias que cualquier \( V_\lambda \) prefijado (con la pertenencia usual), de modo que en particular es un modelo de ZC, pero en el que tenemos un automorfismo \( J: M\longrightarrow M \) tal que existe un \( \alpha\in M \) de modo que \( M\vDash \alpha \) es un ordinal infinito y \( J(\alpha)\neq \alpha \).

Conviene destacar que a la hora de entender "cómo puede ser que unos objetos cumplan los axiomas de NFA", la construcción de este modelo \( M \) (que estamos omitiendo) no arroja ninguna luz, sino que es un mero tecnicismo. Quiero decir que, al fin y al cabo, \( M \) sigue siendo un modelo de una teoría "normal", como es ZC (incluso podríamos suponer que es un modelo de ZFC si no nos importa postular su existencia, no demostrable en ZFC).  Es cierto que la existencia de \( J \) le introduce ciertas "rarezas" (lo convierte en un modelo no estándar), pero es el paso de \( M \) a un modelo de NFA, que vamos a detallar, el que muestra qué son realmente los conjuntos de NFA y por qué cumplen los axiomas que cumplen.

Como \( J \) conserva todas las fórmulas, se cumple también que \( M\vDash J(\alpha) \) es un ordinal infinito, y puesto que en \( M \) los ordinales están totalmente ordenados, tiene que ser o bien \( M\vDash \alpha<J(\alpha) \) o bien \( M\vDash J(\alpha)<\alpha \).

Si se da el primer caso, cambiamos \( J \) por \( J^{-1} \) y tenemos que se cumple el segundo. Así pues, no perdemos generalidad si suponemos que \( M\vDash J(\alpha)<\alpha \).



A partir de aquí podemos "desprendernos" de una buena parte de la teoría de modelos y los problemas conceptuales que puede presentar el tratar con modelos para alguien poco familiarizado con ellos mediante la estrategia siguiente:

Consideremos un lenguaje formal cuyos signos son los del lenguaje de ZFC más un signo de función \( j \), es decir, un signo tal que si \( t \) es un término del lenguaje, entonces \( j(t) \) también es un término. Consideremos la teoría axiomática T cuyos axiomas son los siguientes:

1) Todos los axiomas de ZC.
2) La afirmación que viene a decir que para cada ordinal \( \alpha \) existe el conjunto \( V_\alpha \) y que todo conjunto pertenece a un \( V_\alpha \) (esto es un teorema de ZFC, pero no de ZC).
3) \( \forall xy(j(x)=j(y)\leftrightarrow x = y) \)
4) \( \forall x\exists y\ x = j(y) \)  (Había una errata aquí.)
5) \( \forall xy(x\in y\leftrightarrow j(x)\in j(y)) \)
6) \( \exists \alpha\ (\alpha\text{ es un ordinal infinito}\land  j(\alpha)<\alpha) \)

Lo que prueban los resultados descritos en el apartado anterior es que si ZFC es consistente, entonces T también es consistente, pues el modelo \( M \) que hemos construido (o cuya existencia hemos afirmado que puede probarse en ZFC) cumple todos los axiomas de T sin más que interpretar el nuevo signo \( j \) como el automorfismo \( J \).

Por consiguiente, lo único que queda por hacer es construir un modelo de NFA partiendo de los axiomas de T. De este modo, si NFA fuera contradictorio, en T podríamos demostrar que no existen modelos de NFA, pero habremos demostrado que existe uno, luego tendremos que T es también contradictoria y, según hemos dicho, esto implica que ZFC es contradictorio.

Cabe señalar que la prueba en su conjunto es totalmente constructiva y finitista. Es decir, el argumento (debidamente detallado) proporciona un algoritmo por el que podríamos programar a un ordenador para que a partir de la demostración de una contradicción en NFA nos diera una demostración de una contradicción en ZFC, e incluso la demostración de una contradicción en la teoría MAC + consis MAC, que es mucho más débil que ZFC.

Completaremos la prueba la semana que viene. Soy consciente de que este mensaje puede resultar mucho más oscuro que cualquiera de los anteriores, así que si algún lector necesita aclaraciones adicionales sobre lo dicho aquí, que no dude en preguntar.

11 Marzo, 2012, 04:04 pm
Respuesta #48

Carlos Ivorra

  • Administrador
  • Mensajes: 9,184
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Continuamos la demostración de que si ZFC es consistente también lo es NFA. Hasta ahora hemos probado (o hemos esbozado la prueba de) que si ZFC es consistente también lo es la teoría ZC más la existencia de un automorfismo \( j \) de la clase de todos los conjuntos que, para un cierto ordinal infinito \( \alpha \), se cumple que \( j(\alpha)<\alpha \).

Que \( j \) sea un automorfismo significa que cumple los axiomas

\( \forall xy(j(x)=j(y)\leftrightarrow x = y) \)

\( \forall x\exists y\ x = j(y) \)

\( \forall xy(j(x)\in j(y)\leftrightarrow x \in y) \)

Los dos primeros axiomas permiten definir \( j^{-1}(x) \) como el único conjunto \( y \) tal que \( x = j(y) \), y es fácil ver que los tres axiomas anteriores se cumplen también si cambiamos \( j \) por \( j^{-1} \).

Más en general, si \( \phi(x_1,\ldots, x_n) \) es cualquier fórmula del lenguaje de ZFC (es decir, en la que no aparezca \( j \)) se cumple

\( \forall x_1\cdots x_n(\phi(x_1,\ldots,x_n)\leftrightarrow \phi(j(x_1),\ldots, j(x_n)) \),

y lo mismo es válido para \( j^{-1} \) en lugar de \( j \).

Demostración
Supongamos que existe una fórmulapara la que el teorema no es cierto. Entonces podemos tomar una subfórmula \( \phi \)  de longitud mínima que lo incumpla, de modo que todas las subfórmulas de  \( \phi \) cumplen el teorema, pero  \( \phi \) lo incumple.

La fórmula \( \phi \) no puede ser de la forma \( x_i = x_j \) o \( x_i\in x_j \), pues éstas cumplen el teorema como consecuencia de los axiomas que estamos suponiendo.

Tampoco puede ser de la forma \( \lnot\psi \), pues, como \( \psi \) es una subfórmula de \( \phi \), tenemos que

\( \forall x_1\cdots x_n(\psi(x_1,\ldots,x_n)\leftrightarrow \psi(j(x_1),\ldots, j(x_n)) \),

y esto implica

\( \forall x_1\cdots x_n(\lnot\psi(x_1,\ldots,x_n)\leftrightarrow \lnot\psi(j(x_1),\ldots, j(x_n)) \).

Igualmente se razona que  \( \phi \) no puede ser de la forma  \( \psi\rightarrow \chi \),  \( \psi\lor\chi \) o  \( \psi\land \chi \), pues  las subfórmulas \( \psi \) y  \( \chi \) cumplirían el teorema y esto implica que  \( \phi \) también lo cumple.

Veamos el caso en que  \( \phi \) es  \( \exists x\psi(x,x_1,\ldots, x_n) \). Estamos suponiendo que la subfórmula  \( \psi \) cumple el teorema, es decir, que

\( \forall xx_1\cdots x_n(\psi(x,x_1,\ldots,x_n)\leftrightarrow \psi(j(x),j(x_1),\ldots, j(x_n)) \)

Entonces, si se cumple \( \phi(x_1,\ldotx, x_n) \), existe un conjunto \( x \) tal que \( \phi(x,x_1,\ldots, x_n) \), luego \( \psi(j(x),j(x_1),\ldots, j(x_n)) \), luego \( \exists x\psi(x,j(x_1),\ldots, j(x_n)) \), es decir, \( \phi(j(x_1),\ldots, j(x_n)) \).

Recíprocamente, si \( \phi(j(x_1),\ldots, j(x_n)) \) existe un \( x \) tal que \( \psi(x,j(x_1),\ldots, j(x_n) \), luego existe un \( y \) tal que \( x = j(y) \), de modo que \( \psi(j(y),j(x_1),\ldots, j(x_n) \), y por hipótesis de inducción \( \psi(y,x_1,\ldots, x_n)) \), luego \( \exists x\psi(x,x_1,\ldots, x_n) \), que es lo mismo que \( \phi(x_1,\ldots, x_n) \).

El caso en que \( \phi \) sea \( \forall x \psi(x,x_1,\ldots, x_n) \) se trata análogamente o bien se reduce a los anteriores mediante la equivalencia entre \( \phi \) y \( \lnot \exists x\lnot\psi \).

Esto prueba que el contraejemplo \( \phi \) no puede existir en ningún caso, luego el teorema es correcto.
[cerrar]

En otras palabras, si un conjunto \( x \) cumple cualquier propiedad expresable con una fórmula que depende de unos parámetros, entonces \( j(x) \) cumple la misma propiedad respecto de las imágenes por \( j \) de los parámetros. En particular, si \( \phi(x) \) es una fórmula sin parámetros, tenemos que todo conjunto cumple \( \phi(x)\leftrightarrow  \phi(j(x)) \).

Por ejemplo, si tomamos \( \phi(x) \equiv \forall y\ y\notin x \), tenemos que \( \phi(\emptyset) \), luego \( \phi(j(\emptyset) \), luego \( j(\emptyset) =\emptyset \).

Similarmente, si \( \phi(x,y) \equiv y \) es el ordinal siguiente a \( x \), entonces, para todo ordinal \( \delta \) se cumple \( \phi(\delta, \delta+1) \), luego \( \phi(j(\delta),j(\delta+1) \), luego \( j(\delta+1)=j(\delta)+1 \).

A partir de aquí fijamos un ordinal infinito \( \alpha \) tal que \( j(\alpha)<\alpha \) y vamos a construir un modelo de NFA. Su universo será \( M = V_\alpha \), es decir, los objetos de NFA (conjuntos y átomos) serán los elementos de \( V_\alpha \) y, de entre ellos llamaremos conjuntos a los elementos de \( C = V_{j(\alpha)+1} \).

Notemos que esto tiene sentido, pues, como \( j(\alpha)<\alpha \), tenemos que \( j(\alpha)+1\leq \alpha \), luego \( C=V_{j(\alpha)+1}\subset V_\alpha=M \).

En particular, los átomos de \( M \) serán los elementos de \( M\setminus C \).

Nota
Observemos que si fuera \( \alpha = j(\alpha)+1 \) tendríamos que \( M=C \) y no habría átomos, pero este caso no puede darse, pues, todo ordinal infinito \( \alpha \) puede expresarse de forma única como \( \alpha = \lambda+n \), donde \( \lambda \) es un ordinal límite y \( n \) un número natural, con lo que \( j(\alpha) = j(\lambda)+j(n) \) y, si se diera la igualdad anterior, sería \( \alpha = j(\lambda)+j(n)+1 \), donde \( j(\lambda) \) es un ordinal límite y \( j(n) \) es un número natural. Por la unicidad \( n = j(n)+1 \), pero esto no puede ser, porque \( n \) es par si y sólo si \( j(n) \) es par.

Esto no significa que no pueda construirse un modelo de NFA sin átomos por otro procedimiento, pero por éste no puede ser. Hasta ahora nadie ha sabido construir un modelo de NFA sin átomos a partir de un modelo de ZFC.
[cerrar]

Definimos ahora la relación de pertenencia entre los objetos de \( M \). Concretamente, definimos \( E\subset M\times M \) de modo que

\( x\,E\,y\leftrightarrow y\in C\land j(x)\in y \).

Notemos que, en principio, \( x\in V_\alpha \), \( y\in V_{j(\alpha)+1} \), luego \( y\subset V_{j(\alpha)} \) y \( j(x)\in V_{j(\alpha)} \).

Por último, como \( V_\alpha \) es infinito, existe una aplicación inyectiva (biyectiva si queremos) \( F: V_\alpha\times V_\alpha\longrightarrow V_\alpha \). Para cada par de objetos \( x,y\in M \), definimos su par ordenado (nivelado) como \( (x,y) = F(x,y) \), que es ciertamente otro objeto de \( M \).

Lo que hemos de probar a partir de aquí es que si llamamos "objetos" a los elementos de \( M \), llamamos "conjuntos" a los elementos de \( C \), llamamos "átomos" a los elementos de \( M\setminus C \), llamamos "par ordenado de componentes \( x,y \)" a \( F(x,y) \) y consideramos que la pertenencia entre dos objetos es la relación \( E \), entonces se cumplen los axiomas de NFA.

Notemos que el modelo \( M \) que acabamos de definir cumple el axioma de los átomos, pues (en la definición de \( E \)) hemos exigido como condición para que un objeto \( x \) pueda pertenecer a un objeto \( y \) que el segundo sea un conjunto. Así pues, los átomos no tienen elementos.

Axioma de extensionalidad: Tomamos dos conjuntos \( x, y\in C \) y suponemos que tienen los mismos elementos, es decir, que para todo objeto \( u\in M \) se cumple que \( u\,E\,x\leftrightarrow u\,E\,y \). Hemos de probar que \( x=y \).

La hipótesis es que, para todo \( u\in V_\alpha \), se cumple \( j(u)\in x\leftrightarrow j(u)\in y \).

Ahora bien, \( u\in V_\alpha \) equivale a \( j(u)\in j(V_\alpha) = V_{j(\alpha)} \), luego la hipótesis es también que para todo \( v\in V_{j(\alpha)} \) se cumple \( v\in x\leftrightarrow v\in y \), Como \( x,y\subset V_{j(\alpha)} \), esto implica que \( x=y \).

Axioma de los pares ordenados: El axioma de los pares ordenados se cumple trivialmente en \( M \), pues si \( x,y,u,v \) son cuatro objetos de \( M \) que cumplen \( (x,y) = (u,v) \), esto no significa sino que \( F(x,y) = F(u,v) \), pero \( F \) es inyectiva, luego \( x=u\land y=v \).

Axioma de formación de conjuntos: Ahora hemos de probar que las fórmulas estratificadas del lenguaje de NFA definen conjuntos. Toda fórmula estratificada es equivalente a una fórmula estratificada sin descriptores, así que podemos partir de una fórmula sin descriptores.

Más precisamente, toda fórmula estratificada es equivalente a otra fórmula estratificada cuyas subfórmulas son únicamente de uno de los tipos siguientes:

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

Esbozo de prueba
Una subórmula general sería de la forma \( t_1=t_2 \) o \( t_1\in t_2 \), donde \( t_1 \) y \( t_2 \) son términos formados con pares ordenados y variables, pero ambos tipos de subfórmulas son equivalentes a fórmulas de la forma \( \existx xy(x=t_1\land y=t_2\land x=y) \) o bien \( \exists xy(x=t_1\land x = t_2\land x\in y) \), que claramente están estratificadas si lo están las fórmulas de partida.

A su vez, una fórmula de tipo \( x =(t_1,t_2) \) es equivalente a \( \exists uv(x = (u, v)\land u = t_1\land v=t_2) \), y aplicando transformaciones de este tipo un número finito de veces llegamos a una fórmula cuyas subfórmulas sean todas de los tipos indicados, sin perder la estratificación en el proceso.
[cerrar]

Si \( \phi(x_1,\ldots, x_n) \) es cualquier fórmula del lenguaje de NFA cuyas subfórmulas se restringan a los tipos indicados, podemos definir a partir de ella una fórmula \( \phi^1(x_1,\ldots, x_n,a,f) \) del lenguaje de ZFC más el signo j de modo que la fórmula \( \phi(x_1,\ldots, x_n) \) es verdadera en el modelo \( M \) si y sólo si \( \phi^1(x_1,\ldots, x_n, \alpha, F) \), donde \( F \) es la función que define los pares ordenados nivelados en \( M \).

En efecto, para construir \( \phi^1 \) basta sustituir cada subfórmula de tipo \( \text{cto}\,x \) por \( x\in V_{j(\alpha)+1} \), cada subfórmula de tipo \( x\in y \) por \( y\in V_{j(\alpha)+1}\land j(x)\in y \), cada subfórmula \( x = (u,v) \) por \( x = F(u,v) \) y cada cuantificador \( \forall x \) o \( \exists x \) por \( \forall x\in V_\alpha \) o \( \exists x\in V_\alpha \).

Supongamos ahora que la fórmula de partida admite una estratificación en la que cada variable \( x \) tiene asignado un tipo \( t_x \), y sea \( N \) un número natural mayor que todos los tipos asignados. En tal caso, en lugar de construir la fórmula \( \phi^1 \), podemos construir otra fórmula equivalente \( \phi^2 \) del modo siguiente:

En lugar de sustituir cada subfórmula \( \text{cto}\,x \) por \( x\in V_{j(\alpha)+1} \), la sustituimos por la subfórmula equivalente \( j^{N-t_x}(x)\in V_{j^{N-t_x+1}(\alpha)+1} \).

(Aquí \( j^3(x) = j(j(j(x))) \), etc.)

En lugar de dejar invariante cada subfórmula \( x=y \), la sustituimos por la subfórmula equivalente \( j^{N-t_x}(x)=j^{N-t_y}(y) \).

La fórmula es equivalente porque, como \( x=y \) es una subfórmula de \( \phi \), la definición de estratificación exige que \( t_x=t_y \), luego hemos aplicado \( j \) el mismo número de veces a ambos miembros.

En lugar de sustituir una subfórmula \( x\in y \) por \( y\in V_{j(\alpha)+1}\land j(x)\in y \), la sustituimos por la subfórmula equivalente \( j^{N-t_y}(y)\in V_{j^{N-t_y+1}(y)}\land j^{N-t_x}(x)\in j^{N-t_y}(y) \).

Nuevamente hemos usado que, por definición de estratificación, \( t_y = t_x+1 \), por lo que en la parte final hemos aplicado \( j \) el mismo número de veces a los dos miembros.

En lugar de sustituir \( x = (u,v) \) por \( x = F(u,v) \) la sustituimos por \( j^{N-t_x}(x) = j^{N-t_x}(F)(j^{N-t_u}(u),j^{N-t_v}(v)) \), donde la estratificación garantiza una vez más que \( t_x = t_u = t_v \), por lo que las fórmulas son ciertamente equivalentes.

De este modo, en la fórmula \( \phi^2 \) cada variable \( x \) distinta de la variable \( a \) que sustituimos por \( \alpha \) aparece en un término de la forma \( j^{N-t_x}(x) \). Además en \( \phi^2 \) pueden aparecer varios parámetros de la forma \( j^k(F) \), para distintos valores de \( k \).

En particular, cada variable que en \( \phi \) está ligada por un cuantificador \( \forall x \) aparece en \( \phi^2 \) en la forma \( \forall x\in V_\alpha\,\psi(j^{N-t_x}(x),\ldots) \), pero esto es equivalente a

\( \forall x\in V_{j^{N-t_x}(\alpha)}\,\psi (x,\ldots,) \), ya que cuando \( x \) recorre todos los elementos de \( V_\alpha \), tenemos que \( j^{N-t_x}(x) \) recorre todos los elementos de \( V_{j^{N-t_x}(\alpha)} \). (Lo mismo vale para cuantificadores existenciales.)

Esto significa que la fórmula \( \phi^2(x_1,\ldots, x_n,) \) es equivalente a una fórmula \( \phi^3(j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n)) \), donde \( \phi^3(u_1,\ldots, u_n) \) es una fórmula del lenguaje de ZFC (sin el signo \( j \)) que, además de las variables \( u_1,\ldots, u_n \), tiene otras variables libres como parámetros que en  \( \phi^3(j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n)) \) aparecen sustituidas por conjuntos de la forma \( V_{j^k(\alpha)} \) (los que acotan las variables ligadas por cuantificadores) o \( j^k(F) \).

En definitiva, dada una fórmula estratificada \( \phi(x_1,\ldots, x_n) \) del lenguaje de NFA, hemos encontrado una fórmula \( \phi^3(u_1,\ldots, u_n,\ldots) \) del lenguaje de ZFC tal que \( \phi(x_1,\ldots, x_n) \) es verdadera en \( M \) si y sólo si \( \phi^3(j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n),\ldots) \), donde los puntos suspensivos representan conjuntos de la forma \( V_{j^k(\alpha)} \) o \( j^k(F) \).

A partir de aquí consideramos una instancia concreta del axioma de formación de conjuntos, es decir, dada una fórmula estratificada \( \phi(x,x_1,\ldots, x_n) \), queremos probar que, dados \( x_1,\ldots, x_n\in M \), existe un conjunto \( A\in C \) tal que para todo objeto \( x\in M \) se cumple que \( x\,E\,A \) si y sólo si la fórmula \( \phi(x,x_1,\ldots, x_n) \) es verdadera en \( M \). Equivalentemente, buscamos un \( A\in V_{j(\alpha)+1} \) tal que:

\( \forall x\in V_\alpha(j(x)\in A\leftrightarrow \phi^3(j^{N-t_x}(x),j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n))) \).

Ahora bien, cuando \( x \) recorre \( V_\alpha \) tenemos que \( j(x) \) recorre \( V_{j(\alpha)} \), luego la equivalencia anterior es equivalente a

\( \forall x\in V_{j(\alpha)}(x\in A\leftrightarrow \phi^3(j^{N-t_x-1}(x),j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n))) \).

El \( A \) que buscamos tiene que ser un elemento de \( V_{j(\alpha)+1} \), es decir, un subconjunto de \( V_{j(\alpha)} \), para cualquier \( A\subset V_{j(\alpha)} \) la equivalencia anterior equivale a

\( \forall x(x\in A\leftrightarrow x\in V_{j(\alpha)}\land \phi^3(j^{N-t_x-1}(x),j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n))) \).

Una vez más, cuando un conjunto \( x \) recorre \( V_{j(\alpha)} \), el término \( j^{N-t_x-1}(x) \) recorre \( V_{j^{N-t_x}(\alpha)} \), luego la condición anterior equivale a

\( \forall x(x\in A\leftrightarrow x\in V_{j^{N-t_x}(\alpha)}\land \phi^3(x,j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n))) \).

Así pues, basta definir

\( A = \{x\in V_{j^{N-t_x}(\alpha)}\mid  \phi^3(x,j^{N-t_{x_1}}(x_1),\ldots, j^{N-t_{x_n}}(x_n))\} \),

que existe por el axioma de especificación de ZC. Esto termina la prueba de que el modelo \( M \) cumple el axioma de formación de conjuntos y, por consiguiente, es un modelo de NFA.

La semana que viene demostraremos que \( M \) cumple también el axioma de elección. De momento termino contestando una cuestión que planteaba Sailor Starruler, que conjeturaba que en NFA los pares ordenados de átomos deben ser átomos y los de conjuntos conjuntos.

Acabamos de ver que podemos construir un modelo de NFA en el que los pares ordenados nivelados se correspondan con cualquier función inyectiva \( F:M\times M\longrightarrow M \) prefijada. Si tomamos \( F \) biyectiva tenemos un modelo de NFA en el que todos los objetos son pares ordenados. Si, más concretamente, tomamos \( F \) como unión de una biyección \( C\times C\longrightarrow C \) y una biyección \( (M\setminus C)\times (M\setminus C)\longrigntarrow M\setminus C \), obtenemos un modelo de NFA en el que los pares ordenados de átomos son átomos y los de conjuntos son conjuntos, mientras que si partimos de una biyección \( F: M\times M\longrightarrow M\setminus C \) obtenemos un modelo de NFA en el que todos los pares ordenados son átomos. Lo que no podemos conseguir es un modelo de NFA en el que todos los pares ordenados sean conjuntos, pues \( |C|<|M| \), luego no existen inyecciones \( M\times M\longrightarrow C \). Por otra parte, también podemos diseñar una aplicación inyectiva \( F:M\times M\longrightarrow M \) que asigne algunos pares de átomos a conjuntos y otros a átomos, y algunos pares de conjuntos a átomos y otros a conjuntos.

Así pues, todas las posibilidades sobre la "naturaleza" de los pares ordenados nivelados son consistentes con los axiomas de NFA excepto que todos sean conjuntos.

25 Marzo, 2012, 03:37 pm
Respuesta #49

Carlos Ivorra

  • Administrador
  • Mensajes: 9,184
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En este mensaje terminamos la descripción del modelo de NFA que hemos construido. Resumo lo que tenemos hasta ahora:

1) Estamos trabajando en ZFC más la existencia de un automorfismo j que cumple \( j(\alpha)<\alpha \) para cierto ordinal infinito \( \alpha \).

2) Fijado un ordinal en estas condiciones, el conjunto de los objetos de nuestro modelo de NFA es \( M = V_\alpha \)

3) De entre ellos, serán conjuntos los elementos de \( C = V_{j(\alpha)+1} \) y los restantes serán átomos.

4) Definimos la relación de pertenencia en \( M \) como la dada por

\( x\,E\,y\leftrightarrow y\in C\land j(x)\in y \).

5) Fijamos una aplicación inyectiva \( F: M\times M\longrightarrow M \) y definimos el par ordenado determinado por dos objetos de \( M \) como \( (x,y)^M = F(x,y) \).

Hemos demostrado que si tomamos como objetos los elementos de \( M \) y definimos los conjuntos, la pertenencia y los pares ordenados como acabamos de hacer, se cumplen todos los axiomas de NFA. Falta probar que también se cumple el axioma de elección.

Para ello observamos que si \( x,y\in C \) son dos \( \text{conjuntos}^M \) cualesquiera (el superíndice indica que son conjuntos respecto al modelo \( M \), pues, por ejemplo, si \( x\in M\setminus C \), entonces \( x \) es un conjunto, pero no es un \( \text{conjunto}^M \), sino un  \( \text{\'atomo}^M \)) , entonces \( x\subset^M y \) equivale a \( x\subset y \).

Demostración
La fórmula \( x\subset^M y \) significa que \( x \) e \( y \) satisfacen la definición de inclusión en NFA, lo cual equivale a que sean conjuntos (que lo son, porque así lo estamos suponiendo) y además cumplan

\( \forall u\in M(u\,E\,x\rightarrow u\,E\, y) \),

Pero esto equivale a \( \forall u\in M(j(u)\in x\rightarrow j(u)\in y) \), o también a \( \forall u\in M(u\in j^{-1}(x)\rightarrow u\in j^{-1}(y)) \), es decir, a \( j^{-1}(x)\subset j^{-1}(y) \) (porque \( x, y\subset M \)) y, como \( j \) es un automorfismo, esto equivale a \( x\subset y \).
[cerrar]

Más en general, si \( y\in C \) y \( x\subset y \), entonces automáticamente \( x\in C \) y \( x\subset^M y \).

Demostración
Tenemos que \( y\in V_{j(\alpha)+1} \), luego \( x\subset y\subset V_{j(\alpha)} \), luego \( x\in \mathcal PV_{j(\alpha)} = V_{j(\alpha)+1}= C \).
[cerrar]

Por otra parte, si \( x,y\in C \), se cumple que \( (x\times y)^M = j(F)[x\times y] \).

Demostración
Tenemos que \( u\in (x\times y)^M\leftrightarrow j(j^{-1}(u))\in (x\times y)^M\leftrightarrow j^{-1}(u)\,E\,(x\times y)^M \)\( \leftrightarrow (j^{-1}(u)\in x\times y)^M \)

Esto último equivale a que \( j^{-1}(u) \) sea un par ordenado en \( M \) con primera componente en \( x \) y segunda componente en \( y \), es decir a que

\( \exists vw\in M(v\,E\,x\land w\,E\, y\land j^{-1}(u) = (v,w)^M) \), que a su vez equivale a \( \exists vw\in M(j(v)\in x\land j(w)\in y\land j^{-1}(u) = F(v,w)) \), o también a \( \exists vw\in M(v\in j^{-1}(x)\land w\in j^{-1}(y)\land j^{-1}(u) = F(v,w)) \). Esto significa que \( j^{-1}(u)\in F[j^{-1}(x)\times j^{-1}(y)] \) y, como \( j \) es un automorfismo, es equivalente a \( u\in j(F)[x\times y] \).
[cerrar]

Por lo tanto, si \( x,y\in C \) y \( R\subset x\times y \), tenemos que \( j(F)[R]\subset j(F)[x\times y] \), luego, llamando \( R^*=j(F)[R] \), tenemos que \( R^*\subset (x\times y)^M \). De este modo, a cada relación \( R \) entre dos conjuntos \( x \) e \( y \) podemos asociarle una \( \text{relaci\'on}^M \) \( R^* \) tal que, para todo \( u,v\in M \), se cumple

\( (u\,R^*\,v)^M\leftrightarrow (u,v)^M\,E\, R^*\leftrightarrow j(F(u,v)) = j(F)(j(u),j(v))\in j(F)(R) \) \( (j(u),j(v))\in R\leftrightarrow j(u)\,R\,j(v) \).

Ahora es fácil probar que si \( R \) es un buen orden en un conjunto \( x\in C \), entonces (\( R^* \) es un buen orden en \( x)^M \).

Demostración
Las propiedades de las relaciones de orden se traducen fácilmente a \( M \). Veamos, por ejemplo, la propiedad simétrica: si \( (u\,R^*\,v)^M\land (v\,R^*\,u)^M \), entonces \( j(u)\,R\,j(v)\land j(v)\,R\,j(u) \), luego \( j(u) = j(v) \) y, por consiguiente, \( u=v \).

Supongamos ahora que \( y\in C \) cumple \( (y\subset x\land y\neq \emptyset)^M \). Hemos de probar que \( y \) tiene un mínimo elemento para la relación \( R^* \). La hipótesis equivale a que \( y\subset x\land y\neq \emptyset \), por lo que \( y \) tiene un mínimo elemento para \( R \), es decir, existe \( u\in y \) tal que \( \forall v\in y\ u\,R\,v \).

Por lo tanto, si \( (v\in y)^M \), es decir, si \( j(v)\in y \), tenemos que \( j(j^{-1}(u))\,R\,j(v) \), que equivale a \( (j^{-1}(u)\,R^*,v)^M \), y esto prueba que \( j^{-1}(u) \) es el mínimo de \( y \) en \( M \).
[cerrar]

Ahora es inmediato que \( M \) cumple el axioma de elección, pues cumple que todo conjunto puede ser bien ordenado. En efecto, dado \( y\in C \), podemos tomar un buen orden \( R \) en \( y \), y acabamos de probar que \( (R^* \) es un buen orden en \( y)^M \).

También es inmediato probar que si \( x,y\in C \) y \( f: x\longrightarrow y \) (inyectiva, suprayectiva, biyectiva) entonces \( (f^*: x\longrightarrow y)^M \) (inyectiva, suprayectiva, biyectiva) y se cumple que \( (f^*(u))^M = j^{-1}(f)(u) \). Además, toda aplicación en \( M \) es de esta forma.

Demostración
Si \( (g: x\longrightarrow y)^M \), entonces \( g\subset (x\times y)^M = j(F)[x\times y] \), luego \( f = j(F)^{-1}[g]\subset x\times y \) y se cumple que \( g = j(F)[f]=f^* \). El hecho de que \( g \) sea una aplicación (inyectiva, suprayectiva, biyectiva) en \( M \) se traduce fácilmente en que \( f \) también lo es (fuera de \( M \)).
[cerrar]

Tanto en \( M \) como fuera de \( M \) tenemos que un conjunto \( x \) es infinito si y sólo si existe \( f: x\longrightarrow x \) inyectiva y no suprayectiva, luego podemos concluir que, para todo  \( x\in C \), se cumple que \( x \) es infinito en \( M \) si y sólo si es infinito, luego \( x \) es finito en \( M \) si y sólo si es finito.

Por otro lado, \( (|x| = |y|)^M \) si y sólo si existe una biyección \( f: x\longrightarrow y \) (en M o, equivalentemente, fuera de M) si y sólo si \( |x| = |y| \).

Dado \( (n\in \mathbb{N})^M \), tomemos un conjunto \( u\,E\,n \), es decir, \( j(u)\in n \). Entonces \( u \) es finito en \( M \), luego es finito, y existe un número natural \( \nu\in \omega \) (el conjunto de los ordinales finitos de von Neumann) tal que \( |u|=\nu = |\nu| \), luego \( (|u| = |\nu|)^M \), luego \( \nu\in n \).

En definitiva, todo número natural en M contiene un número natural (ordinal de von Neumann), que claramente es único (pues si contuviera dos, serían equipotentes en M, luego serían equipotentes). Recíprocamente, todo número natural \( \nu \) es finito, luego finito en M, luego pertenece a un número natural en M, es decir \( j(\nu) \) pertenece a un número natural en M. Tenemos así una biyección \( N: \omega\longrightarrow \mathbb{N}^M \) que a cada número natural \( \nu \) le asigna el único número natural \( n \) en \( M \) que cumple \( j(\nu)\in n \).

Veamos ahora que si \( u\in M \) entonces \( \{u\}^M = \{j(u)\} \).

Demostración
\( v\in \{u\}^M\leftrightarrow j(j^{-1}(v))\in \{u\}^M\leftrightarrow j^{-1}(v)\,E\,\{u\}^M\leftrightarrow j^{-1}(v)=u\leftrightarrow v = j(u) \)
[cerrar]

Por otro lado, si \( x\in C \), se cumple que \( (\mathcal P_1x)^M =j(\mathcal P_1x) \).

Demostración
\( u\in (\mathcal P_1x)^M\leftrightarrow j(j^{-1}(u))\in (\mathcal P_1x)^M\leftrightarrow (j^{-1}(u)\,E\,(\mathcal P_1x))^M \) \( \leftrightarrow \exists v(v\,E\,x\land j^{-1}(u) = (\{v\}^M))\leftrightarrow \exists v(j(v)\in x\land j^{-1}(u) = \{j(v)\}) \) Esto equivale a que \( j^{-1}(u)\in \mathcal P_1x \), luego a que \( u\in j(\mathcal P_1x) \).
[cerrar]

Ahora es inmediato que si \( (n\in \mathbb{N})^M \) es un número natural que se corresponde con \( \nu\in \omega \), entonces \( (Tn)^M \) se corresponde con \( j(\nu) \).

Demostración
Tenemos que \( \nu\,E\,n \), luego \( (\mathcal P_1\nu)^M\,E\, (Tn)^M \), pero \( (\mathcal P_1\nu)^M = j(\mathcal P_1\nu) \) y \( |\mathcal P_1\nu| = |\nu| \), luego \( |j(\mathcal P_1\nu)| = |j(\nu)| \), luego \( (|j(\nu)| = |\mathcal P_1\nu|)^M \), luego \( j(\nu)\,E\, (Tn)^M \), y esto significa que \( j(\nu) = N((Tn)^M) \).
[cerrar]


Así pues, el axioma de cómputo, que en una de sus formas equivalentes afirma que \( \forall n\in \mathbb{N}\ T(n)=n \), se cumple en \( M \) si y sólo si \( \forall \nu\in \omega\ j(\nu) = \nu \), es decir, si y sólo si \( j \) fija a todos los números naturales.

No hemos visto los detalles de la construcción del modelo de ZC dotado del automorfismo \( J \) que garantiza la consistencia de la existencia del automorfismo \( j \) con el que estamos trabajando, pero en ella podemos exigir que \( J \) tenga la propiedad de dejar fijos a todos los números naturales. Cuidando de que esto sea así, llegamos a que el modelo \( M \) que estamos considerando es un modelo de NFA + AC, luego esta teoría es consistente si ZFC es consistente.