Autor Tema: Logicismo, Intuicionismo y Formalismo (review de un libro sobre el tema)

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

11 Agosto, 2011, 08:38 am
Respuesta #30

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Hice uso del UNICODE porque tiene comas, puntos y otros signos, además de los alfabéticos.

Se puede pensar lo mismo con caracteres que no sean de UNICODE.

Se supone que lo relevante son los signos alfabéticos escritos, y no los bits del UNICODE.
Porque si estás mirando los bits de cada caracter, eso es otra codificación del mismo mensaje.

Se puede hacer todo en binario, pero si no le das ningún significado, entonces es sólo una lista de bits 0 1.

Es la paradoja de Berry, y conviene buscar información por ese lado.
Yo no voy a detenerme demasiado en eso. (Por ahora, al menos eso creo).

Saludos

12 Agosto, 2011, 06:33 am
Respuesta #31

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Anterior   <<
Siguiente >>

Más de Dedekind

Voy a continuar con algunas cuentas sobre la teoría de Dedekind del infinito.
No sé dónde estará el resultado original de Dedekind, pero no es muy relevante.

Voy a suponer que estamos en la teoría de conjuntos de Zermelo-Fraenkel, sin asumir que vale el Axioma de Elección, escrito todo, claro está, en la lógica de primer orden.
Es lo que conocemos como teoría ZF. Al agregarle el axioma de elección, queda ZFC, que es la teoría estándar de conjuntos.

Es usual en dicha teoría asumir el Axioma del Infinito, el cual afirma básicamente que: existe un conjunto que satisface las propiedades de los números naturales.

Pero esa afirmación es demasiado "fuerte", además de innecesaria.

Podemos asumir, como Dedekind, solamente que "existe un conjunto infinito", y luego proceder a "demostrar" la existencia de un conjunto de números naturales.

Para ello, quitamos el Axioma del Infinito, y lo reemplazamos por la hipótesis de que existe al menos un conjunto Dedekind-infinito.

El sistema axiomático que resulta de quitar el Axioma del Infinito se denota usualmente con ZF-.

Me interesa demostrar lo siguiente:

Teorema. En ZF-, si existe un conjunto infinito \( X \), entonces existe un sistema simplemente infinito \( N \) que además es subconjunto de \( X \).

En otras palabras: hay un subconjunto de números naturales que es subconjunto de \( X \).



Antes de pasar a la demostración, agradezco una intervención posterior de Oscar que sirvió para corregir las cuentas, y de paso aclarar algunas cosas importantes.


Primero que nada, debemos dejar claro que en una teoría como ZF-, que parte de una lista de axiomas más chica que la teoría estándar ZFC, hay hechos naturalmente ciertos en ZFC que no pueden ser demostrados en ZF-.

Más aún, hay "modelos" de muchas de esas afirmaciones que verifican la "negación" de ellas en ZF-.
Sin entrar por ahora en detalles de qué son los "modelos", tomémoslo intuitivamente diciendo que "un modelo es un ejemplo en el que se satisfacen las propiedades listadas en los Axiomas por uno escogidos".

Un ejemplo de estas diferencias es el concepto básico de "finitud" e "infinitud".
En ZFC son equivalentes las nociones de conjunto infinito y conjunto Dedekind-infinito, lo cual se demuestra fácilmente con el Axioma de Elección.
En cambio, en ZF esto no es cierto, y más aún, hay "modelos" en los que un conjunto puede ser a la vez "infinito" en el sentido usual del término (no biyectable con algún conjunto de naturales {1, ...., n}) pero también "Dedekind-finito".

Si bien vamos a probar ahora que todo conjunto Dedekind-infinito en ZF- es también infinito en sentido estándar, la recíproca no es cierta.

Estos "modelos" rebeldes no los voy a postear ahora, aunque más adelante voy a intentar hacerlo, porque sin dudas es algo muy interesante para esta discusión.

Por ahora sólo tengamos en cuenta que:

* Si tenemos una familia de conjuntos Dedekind-finitos, no necesariamente son ellos finitos en sentido estándar.
* Luego, se hace necesario "extraer" alguna subfamilia de todos ellos para obtener conjuntos que sean "finitos" en sentido usual.



Para demostrar el Teorema, vamos a necesitar un resultado previo:

Proposición. Si en ZF- existe un conjunto Dedekind-infinito \( X \), entonces existe un conjunto simplemente infinito, o sea, que cumple los axiomas de los números naturales.

Demostración de la Proposición.

La estrategia de la demostración será la siguiente: (la pongo en spoiler porque ocupa mucho espacio visual).

Spoiler
  • Querríamos decir que el "0" corresponde al conjunto vacío,
    luego elegir sucesivamente elementos distintos \( x_1,x_2,x_3,...\in X \) y probar que los conjuntos \( \{x_1\},\{x_1,x_2\},\{x_1,x_2,x_3\}, \) etc., van formando una secuencia de conjuntos.
    La colección de todos estos conjuntos, junto con una función "sucesor" adecuadamente definida, si se pudiera hacer, nos serviría como conjunto de números naturales.
  • Sin embargo el proceso anterior no puede llevarse a cabo, porque en cada caso hay que "elegir" elementos de conjuntos "grandes".
    O sea, debo elegir un elemento \( x_1\in X \), luego  \( x_2\in X\setminus \{x_1\} \), \( x_3\in X\setminus \{x_1,x_2\} \), y así sucesivamente.

    Esa "elección" no puede hacerse, porque no tengo Axioma de Elección.
    Además, aparece al menos "complicado" definir un proceso en forma recursiva como el expuesto, porque al no tener "aún" un conjunto de números naturales, no tengo "autorización" para usar el Principio de Definición por Recurrencia.

  • Así que no queda más remedio que considerar "los subconjuntos de \( X \) de 1 elemento, todos a la vez", luego a esos agregarles un elemento de \( X \), y considerar "todos los subconjuntos de 2 elementos", y así sucesivamente.

    Con este "proceso" estamos evitando el uso del Axioma de Elección.
    Sin embargo, aún no puedo formalizar bien el "así sucesivamente", porque no tengo números naturales, luego no tengo inducción ni recurrencia. No tengo secuencias, y me está prohíbido decir cosas como "y así sucesivamente".
  • Sin embargo, puedo hacer algunas cosas "periféricas". Por ejemplo, dado un subconjunto Dedekind-finito \( F\subset X \) puedo formarme el conjunto de todos los subconjuntos de \( X \) biyectivos con \( F \).

    A ese conjunto lo denotaremos como \( [F] \) (notación de "clases de equivalencia"), y es posible definir una noción de "siguiente" de \( [F] \), obteniendo un conjunto similar \( [F'] \) asociado a algún \( F'\subset X \) también Dedekind-finito.

  • La familia de todos esos "conjuntos de conjuntos" \( [F] \) (asociados a un Dedekind-finito \( F\subset X \)) es tal que la función "sucesor" estará bien definida como una aplicación "inyectiva".

    Tendremos también un "primer elemento", a saber, el \( [\emptyset ] \).

    La pregunta es si esto alcanza para decir que tenemos un sistema de números naturales.

  • La respuesta es que no, porque aún faltaría probar que vale el Principio de Inducción.

    Pero recordemos la discusión previa de que "no es lo mismo" finito-estándar que Dedekind-finito.

    Así, mientras yo puedo obtener clases que "sucesivamente" vayan teniendo cada una un cardinal inmediatamente siguitente que la anterior, lo cual sin duda se parece a los números naturales,
    lo cierto es que la colección de todas las clases \( [F] \)  puede contener muchos más elementos que los deseados.

    O sea, tendría una primer clase asociada al vacío: \( [\emptyset ] \).
    La clase "siguiente" sería \( [\{x_1\}] \), donde \( x_1 \) es cualquier elemento de \( X \).
    La "siguiente" de esta sería \( [\{x_1,x_2\}] \), donde \( x_1,x_2 \) son cualesquiera elementos "disintos" de \( X \), y así sucesivametne.

    Esas clases son las que uno quiere que se asocien sucesivamente a nuestra idea de números naturales 0, 1, 2, etc.
    Pero no hay modo de "enumerar" dichas clases, porque aún no tenemos justamente la escala de los números naturales.

    Así que tenemos que considerar la familia completa de todas las clases \( [F] \) con \( F \) Dedekind-finito.

    Pero corremos el riesgo de que estas clases sean "demasiadas", y no valga el principio de inducción.

  • La solución típica al último problema sería: probar que la familia de todas las clases satisface "cierta" propiedad "inductiva".

    Luego tomar la mínima de todas las subfamilias inductivas, y llamar "números naturales" a esta clase mínima.

    ¿Por qué debería funcionar?
    Bueno, porque el Principio de Inducción es justamente una forma de "minimalidad" para conjuntos inductivos.
    Es común "cazar" el Principio de Inducción de esta forma.
[cerrar]


A continuación van los detalles formales de la prueba, los cuales también pongo en Spoiler.

Demostración.

Construcción de un sistema de números naturales "en alguna parte"

Sea \( X \) un conjunto Dedekind-infinito dado.
Fijado un elemento \( z\in X \), el conjunto \( \{z\} \) es Dedekind-finito, y además es subconjunto de \( X \).

Dado cualquier subconjunto Dedekind-finito \( F \) de \( X \), es claro que \( X\setminus F \) es no vacío, porque si no, \( X \) sería Dedekind-finito.
Luego, existe algún \( x\in X\setminus F \).

El conjunto \( F'=F\cup \{x\} \) es subconjunto de \( X \) y es Dedekind-finito.
Porque si fuese Dedekind-infinito, habría una biyección \( f \) con un subconjunto propio \( G \) de \( F' \).
Si \( G\subset F \), entonces quitando el elemento \( f^{-1}(x) \) obtenemos una biyección entre \( F \) y un subconjunto propio de \( F \), absurdo.
En cambio, si \( x\in G \), tomando un \( z\in F'\setminus G \), nos queda que \( z\in F\setminus G \), pues \( z\neq x \), y la aplicación \( g:G\to F \), \( g(a) = a, a\neq x, g(x) = z \) es una biyección, lo cual nos permite hallar un subconjunto propio de \( F \) biyectivo con \( F \), absurdo otra vez.

Así que la clase \( \mathcal S_F \) de todos los conjuntos de la forma \( F\cup \{x\} \) para \( x\in X\setminus F \) es no vacía, y además consta de conjuntos Dedekind-finitos.

Se puede probar fácilmente que todos los elementos de \( \mathcal S_F \) son biyectivos entre sí.

Definamos la relación de equivalencia \( \apporx \) entre subconjuntos de \( X \) Dedekind-finitos mediante:
\( F\approx G \) si y sólo si existen \( F'\in \mathcal S_F,G'\in \mathcal S_G \) tales que \( F',G' \) son biyectivos entre sí.

Por la observación anterior, si esto ocurre, todos los elementos de \( \mathcal S_F \) serán biyectivos con todos los de \( \mathcal S_G \).

Si ahora \( \mathcal C \) denota la clase de todos los subconjuntos Dedekind-finitos de \( X \),
tenemos que \( \approx \) induce una partición de \( \mathcal C \) en clases de equivalencia, como es usual.
Esto es fácil, faltando sólo comprobar el sencillo hecho de que \( \approx \) es una relación de equivalencia.
Denotemos con \( [F] \) la clase de equivalencia asociada a \( F \).

Se puede demostrar que, si \( x\not\in F \), entonces \( F'=F\cup \{x\} \), y así todo elemento de \( S_F \) pertenece a la clase \( [F'] \). En símbolos:

\( \mathcal S_F\subset [F'] \)

Más aún, la unión de todos los conjuntos \( S_E \) tales que \( E\approx F \) coincide con la clase \( [F'] \).

Definamos ahora la operación sucesor en la familia de las clases de equivalencia, así:

\( s([F])=[F'] \)

donde \( F'\in S_F \). En particular podemos decir algo como: \( \mathcal S_F\subset s(F) \), lo cual nos permite asociar claramente a un conjunto \( F \) "todos sus siguientes".

Recordemos que nuestro impedimento de no poder echar mano del Axioma de Elección no nos deja "elegir" uno solo de los "siguientes conjuntos" de \( F \).
Es por eso que no nos queda más remedio que trabajar con todos ellos.

La colección de clases de equivalencia se denota, como es usual, mediante \( \mathcal C/\approx \). Simple notación: prohíbido asustarse. Más aún, es un subconjunto de "partes de partes de \( X \)". En símbolos:

\( \mathcal C/\approx\subset \mathcal P(\mathcal P(X)). \)

Definamos ahora la noción de familia inductiva en el conjunto \( \mathcal P(\mathcal P(X)) \).
Decimos que un conjunto \( \mathcal J\subset \mathcal P(\mathcal P(X)) \) es una familia inductiva, si cumple los siguientes requisitos:

  • Todo elemento de \( \mathcal J \) es una de las clases de equivalencia \( [F] \), para algún \( F\subset X \) Dedekind-finito.
    (Esta condición la pido sólo para que la demostración no sea demasiado engorrosa).
  • La clase \( [\emptyset ] \) está en \( \mathcal J \), o sea: \( [\emptyset ]\in\mathcal J \).
  • Si \( [F]\in\mathcal J \), entonces el "siguiente" también está: \( s([F])\in \mathcal J \).

Es claro que \( \mathcal C/\approx \) es ella misma una familia inductiva.
Pero es posible que haya subconjuntos de esa familia que aún sean inductivas.

Esta posibilidad nos impide demostrar que en \( \mathcal C/\approx \) vale un Principio de Inducción.
Así que busquemos la "mínima" subfamilia inductiva, y verifiquemos que esa es la que nos sirve.
Para ellos, denotamos con \( \mathcal U \) al conjunto de todas las familias inductivas.
(Para entender en qué "país" vive ese conjunto, notemos que \( \mathcal U\subset \mathcal P(\mathcal P(\mathcal P(X))) \))

Como \( \mathcal U\neq \emptyset  \), la intersección de todos los conjuntos que pertenecen a \( \mathcal U \) está bien definido, o sea, existe un conjunto

\( \mathcal N=\bigcap\{\mathcal J:\mathcal J\in \mathcal U\} \).

Es fácil verificar que \( \mathcal N \) es también una familia inductiva.
Además, dada cualquier otra familia inductiva \( \mathcal U\subset \mathcal N \), se tiene necesariamente, por la intersección involucarada en la definición de \( \mathcal N \), que \( \mathcal N\subset \mathcal U \), y esto implica que

\( \mathcal U=\mathcal N. \)

¡Pero esto es el Principio de Inducción relativo a la terna \( (\mathcal N,s,[\emptyset ]) \)!


Se obtiene entonces que \( (\mathcal N, s, [\emptyset ] ) \) es un sistema simplemente infinito, o sea, un sistema de números naturales.

Así que hemos probado nuestra Proposición auxiliar: existe un sistema \( \mathcal N \) de números naturales con sólo suponer que existe un conjunto infinito.

Ese conjunto aún no es subconjunto de \( X \).
Es tan sólo un conjunto números naturales que construimos "por ahí" (en realidad es subconjunto de "partes de partes de \( X \)").

[cerrar]

La prueba que he usado tiene para mí "olor a no-corriente".
Imagino que la prueba típica utiliza construcciones del tipo Von-Neumann para generar la secuencia de números naturales.

Como sea, ahí está.

Ahora procedamos a construir un subconjunto numerable de \( X \).

Por definición, existe \( X'\subset X \) tal que \( X'\neq X \) y tal que existe una biyección \( f:X\to X' \).
Ahora, la mera existencia de un sistema de números naturales nos permite definir funciones por recurrencia (lo cual es un Teorema que puede probarse en ZF-, a partir de las propiedades de Peano de cualquier sistema de números naturales que tengamos a mano).

Así que, por el Principio de Definición por Recurrencia, tiene sentido definir la composición de \( n \) funciones \( f^{(n)}:X\to X \), siendo \( f^{(n)}=\underbrace{f\circ f\circ \cdots \circ f}_{n} \).

Ahora definimos la función \( g:\mathcal N\to X \), \( g(n)=f^{(n)}(x_0) \), donde \( x_0 \) es un elemento prefijado del conjunto no vacío \( X\setminus X' . \)

Se puede, además, definir la sucesión de conjuntos \( X_0=X, \qquad X_n=f^{(n)}(X) \).
Se puede probar por inducción que \( X_0\supset X_1\supset X_2\supset \cdots \).
En efecto, la primer inclusión es trivial, y dado \( n \), asumiendo que \( X_{n-1}\supset X_n \), tenemos ahora que:
\( X_n=f(X_{n-1})\supset f(X_n)=X_{n+1} \).

Tenemos trivialmente que \( g(n)\in X_n \), todo \( n \).
Pero más aún, \( g(n)\not\in X_{n+1} \), porque si no, aplicando "a ambos miembros" \( f^{(-n)} \) obtendríamos que \( x_0=g(0)\in X_1=X' \), en contra de la forma en que elegimos \( x_0 \).

Por lo tanto, para todo \( n \), tenemos que \( g(n)\in X_{n}\setminus X_{n+1} \).
Sin embargo, los conjuntos de la forma \( E_n=X_{n}\setminus X_{n+1} \) son todos disjuntos entre sí,
lo cual muestra que \( g \) es una función inyectiva.

Ergo, hemos obtenido un subconjunto de \( X \) biyectivo con los números naturales, tal como deseábamos.



No he encontrado la prueba original de Dedekind, pero estoy seguro que en esta última parte él ha seguido este camino, que es el más simple y natural.



Anterior   <<
Siguiente >>

12 Agosto, 2011, 03:15 pm
Respuesta #32

Óscar Matzerath

  • Lathi
  • Mensajes: 565
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Antes de nada agradecerte estos posts, me parecen un trabajo magnífico y seguro que te lleva tu tiempo.

Pero sobre el último post, tengo una duda en la demostración de la existencia de un sistema de naturales a partir de la existencia de un conjunto Dedekind-infinito. Al final, dices que:


Tenemos que demostrar que:


  • \( s \) es una función inyectiva de \( \mathcal N \) en \( \mathcal N \setminus \{[\emptyset ]\} \).

  • Si \( \mathcal A\subset \mathcal N \), \( [\emptyset ]\in A \), y si \( [F]\in \mathcal A \) implica que \( [F']\in \mathcal A \) para algún \( F'\in S_F \), entonces \( \mathcal A=\mathcal N \).



La primera es muy fácil de ver que es así, por sencillos teoremas de biyecciones en ZF.
Pero la segunda no me parece nada sencilla. ¿Qué pasa si X tiene un subconjunto Dedekind-finito pero infinito? En ese caso, el principio de inducción no puede cumplirse, ya que existe un subconjunto propio de \( \mathcal{N} \) que lo cumple (aquí voy a asumir que estamos en ZF y por tanto tenemos los naturales ya construidos antes, para poder usar principio de recursión):

El conjunto \( A= \{x \in \mathcal{N} : x=s^n(0) \) para algún n natural }, que está bien definido por el teorema de recursión, es claramente isomorfo a N (con el mismo 0 y la misma s), sin embargo si F es un Dedekind-finito pero infinito, \( [F] \notin X \), ya que si \( [F] = s^n([\emptyset] \), se demuestra fácilmente (por inducción) que F tiene cardinal n, y por tanto es finito. Esto es, el conjunto \( \mathcal{N} \) no puede ser en ese caso isomorfo a los naturales, ya que cualquier isomorfismo debe mandar los naturales en el conjunto A (respetando la operación s) y por tanto como \( \mathcal{N} - A \) es no vacío, no puede ser exhaustiva.

Saludos

12 Agosto, 2011, 03:30 pm
Respuesta #33

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Tenés razón Oscar, voy a tener que revisar esa prueba. Me confié demasiado.

Tengo que considerar los conjuntos asociados a "finitos" en sentido "estándar" y no los Dedekind-finitos.
Por otra parte, así está pensada esa prueba, ya que los "finitos" son "Dedekind-finitos", y son ellos quienes forman una secuencia de naturales.
Luego la reviso...

12 Agosto, 2011, 04:57 pm
Respuesta #34

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Agradezo a Oscar su corrección, ya que me ha hecho recordar que esta cuenta no sale así no más, sino que al menos falta un paso.

Como bien él menciona, no es equivalente en ZF- decir "finito" que "Dedekind-finito".

El problema con los conjuntos "finitos" es que no los puedo definir, porque un conjunto es "finito" en sentido estándar, si es coordinable con algún conjunto de naturales {1, ..., n}, pero resulta que los números naturales "aún" no los tengo.

Y si los tuviera, no podría asegurar en ZF- que están autorizados a "juntarse" para formar un "conjunto".

Así que hay que "producir" un conjunto de números naturales de algún modo.
La aplicación s() que definí está bien definida en esas clases asociadas a conjuntos Dedekind-finitos.

Pero tengo que asegurarme de que puedo "extraer" de ahí algún subconjunto de naturales.
Para eso, la estrategia básica que se me ocurre es la siguiente, que es bastante estándar además:

* Demostrar que la familia de clases [F] asociadas a conjuntos Dedekind-finitos es "inductiva".
* Tomar la "mínima" subfamilia inductiva (que existe trivialmente, tomando intersección), y a esa llamarla \( \mathcal N \).
* Finalmente chequear que esta subfamilia satisface los axiomas de los números naturales, lo cual es siempre bastante trivial debido a que el principio de inducción es una forma de "minimalidad inductiva".

Cuando corrija estas cosas este post quedará redundante, pero está bien que Oscar haya intervenido, porque de paso decimos algo importante y es que no es para nada equivalente la noción estándar de finitud con la que da Dedekind.


12 Agosto, 2011, 06:11 pm
Respuesta #35

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
YA está corregido el error en el post de "Dedekind-infinito".

Bueno, aprovechando la intervención de Oscar, decidí corregir la demostración, y además agregué muchos comentarios de tipo "pedagógico" porque me di cuenta que estuve algo tacaño con las ideas y claves tras este tema de los Dedekind-infinitos.

Ahora puse más explicaciones de "por qué" uno tiene que probar las cosas de un modo y no de otro, para que la demostración no sea algo extraño que deje perplejo al lector incauto.


12 Agosto, 2011, 07:24 pm
Respuesta #36

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

El conjunto \( A= \{x \in \mathcal{N} : x=s^n(0) \) para algún n natural }, que está bien definido por el teorema de recursión, es claramente isomorfo a N (con el mismo 0 y la misma s),


En este punto no estoy muy de acuerdo, a ver...

Al decir que A es isomorfo a N, estás asumiendo que "ya hay" algún N.

Eso no puede hacerse en ZF-.
Con los Axiomas de ZF-, uno puede generar los números naturales de uno en uno, con varios métodos distintos,
pero no puede afirmar (creo yo) que la "colección" de todos esos naturales realmente se pueda "formar" o sea, constituir como un "conjunto" con pleno "certificado" otorgado por ZF-.

Justamente, hay que construirse un conjunto así.
Para eso hace falta al menos un conjunto infinito.
En ZF- ni siquiera se asume la existencia de un tal conjunto.
El universo podría quizá constar de conjuntos "finitos" solamente.

Además, cuando has hablado del Teorema de Recursión, ¿te estás refiriendo al Teorema de Definición por Recurrencia que se deduce de los Axiomas de Peano, o estás pensando en unos naturales "concretos" ya "fabricados" en la teoría de conjuntos a lo Von Neumann con ordinales?

A lo mejor se pueda trabajar con ordinales para probar que existe un conjunto de naturales.
Pero no lo he hecho, porque preferí no asumir nada previo.
Y de hecho, creo que no se puede asumir que la construcción típica de ordinales de Von Neumann conduzca a un conjunto de naturales... a menos que haya supuesto que hay un conjunto infinito, y pase por las demostraciones que antes expuse, o algo análogo.

 ???

12 Agosto, 2011, 07:46 pm
Respuesta #37

Óscar Matzerath

  • Lathi
  • Mensajes: 565
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Tienes razón en todo lo que dices, en ZF- puede pasar que no haya conjuntos infinitos, y que no exista el conjunto de todos los naturales, de hecho es el modelo más natural para ZF + ¬Inf, y el teorema de recursión para naturales (de hecho estaba pensando en los naturales típicos en ZF, es decir, los ordinales finitos) no se puede demostrar en ZF- simplemente porque no hay conjunto de todos los naturales (no está garantizado que exista) así que ni siquiera el enunciado tiene sentido.

Por cierto, como nota al margen, ¿a qué teorema te refieres exactamente cuando hablas del teorema de definición por recurrencia que se deduce de los axiomas de Peano?

De todas maneras eso no invalida para nada mi post anterior. Me explico. Como digo en el párrafo anterior, no trabajo en ZF- sino en ZF, donde tengo a mi disposición N, el teorema de recursión y todas las demás herramientas. Esto me basta para ver que la demostración falla, porque yo sé que existe un modelo de ZF donde existe un conjunto infinito pero Dedekind-finito. Ahora, en ese modelo, mi conjunto A está bien definido y todo lo demás es válido (ya que estoy en ZF, con infinitud), y muestro que no puede haber ningún isomorfismo entre los naturales (que los tengo en mi modelo, por ser modelo de ZF) y el \( \mathcal{N} \) de ese modelo, tal como lo habías definido. Por tanto, tengo un modelo de ZF donde es cierto que "\( \mathcal{N} \) no es un sistema de naturales" (ya que de serlo, sería isomorfo con los naturales que tengo, N). Pero como ZF es una extensión de ZF- (es ZF- con un axioma más) todo modelo de ZF es también modelo de ZF-, luego tengo un modelo de ZF- que cumple "\( \mathcal{N} \) no es un sistema de naturales", y por tanto, ZF- no prueba que "\( \mathcal{N} \) es un sistema de naturales, para cualquier X Dedekind-infinito".

Otra manera de verlo, más sintáctica. He demostrado que en ZF+"existe un conjunto Dedekind-finito pero infinito" es consistente que exista un X Dedekind-infinito tal que "\( \mathcal{N} \) no es un sistema de naturales" y por tanto ZF+"existe un conjunto Dedekind-finito pero infinito" no prueba "para cualquier X Dedekind-infinito, \( \mathcal{N} \) es un sistema de naturales". Pero si no lo prueba ZF+"existe un conjunto Dedekind-finito pero infinito", tampoco lo puede probar ZF- que es estrictamente más débil.

Saludos

12 Agosto, 2011, 07:58 pm
Respuesta #38

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Está bien Oscar, estoy de acuerdo con eso último, y por eso corregí la demostración para distinguir justamente los Dedekind-finitos de los finitos.

Es cierto que no sólo en ZF- sino también en ZF, no es lo mismo Dedekind-finito que finito.

En ZF uno tiene los naturales, y entonces la demostración de que existe un subconjunto numerable de un Dedekind-infinito es como puse al final del post, que es bastante directo, al menos la idea es clara.

Mi dilema está entonces cuando trabajamos en ZF-, donde no tenemos asumido que existe un conjunto de números naturales.

Ahí TODO me lo tengo que fabricar, incluidos los números.

En cuanto al Teorema de definición por recurrencia, puede "demostrarse" una vez que uno ha conseguido un sistema de números naturales.
Las cuentas las hice en este thread:

Números Naturales

(Las ideas seguro las habré copiado de algún otro lado, pero son cuentas tan típicas que usualmente las vuelvo a hacer cada vez que hace falta).

En ese thread usé ZFC sin avisar.
De todos modos, estoy seguro de que no se usa el Axioma de Elección en el Teorema de Definición por Recurrencia.
Así que es válido en ZF.
No creo que haga falta revisar si es válido en ZF-, porque la mera hipótesis de que hay un conjunto que cumple los Axiomas de Peano nos da un conjunto infinito, con lo cual se sigue la construcción que hice unos posts atrás en este hilo que me da la existencia de un tal conjunto.
Puedo luego demostrar que es válido usar "recurrencia" en general en ZF- (siempre que sigamos suponiendo que hay algún X infinito).

Yo no sé si vos te referías a alguna forma de recurrencia más típica de la teoría de conjuntos, como las que a lo mejor podrían aparecer al manipular "ordinales" (o sea, te lo estoy preguntando porque no me acuerdo si se habla de "recurrencia" en este contexto).


12 Agosto, 2011, 08:09 pm
Respuesta #39

Óscar Matzerath

  • Lathi
  • Mensajes: 565
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Ah, me refería exactamente al mismo teorema entonces (lo de usar N como ordinales u otro sistema isomorfo es irrelevante). El teorema es válido en ZF, no se usa elección en ninguna parte. Tambien hay un teorema de definición recursiva para ordinales en general, y para cosas más generales, pero aquí me refería al que has puesto tú.

Es que por un momento creí (al mencionar axiomas de Peano) que hablabas de la aritmética de Peano como sistema formal, sin teoría de conjuntos, y por eso me chocaba tal teorema.

Por cierto, fíjate que lo que has demostrado realmente es que ZF- + "existe un X Dedekind-infinito" es equivalente a ZF, ya que una vez tienes tu sistema de naturales, puedes demostrar un teorema de definición recursiva para ellos, y usarlo para demostrar la existencia del N típico (y por tanto la existencia de un conjunto inductivo, que es lo que afirma el axioma de infinitud): la imagen de f definida por recursión como \( f(0)= \emptyset \), \( f(s(n)) = n \cup \{ n \} \). Por otro lado, en ZF existe un Dedekind-infinito, el mismo N.

Saludos

Saludos