Autor Tema: Comentarios a "Ordinales menores que \(\epsilon_0\)"

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

03 Junio, 2023, 02:35 pm
Respuesta #70

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Hace unos días que estaba pensando que podría ser interesante un hilo que presentara la Aritmética Recursiva Primitiva, porque no es muy popular, en el sentido de que es difícil encontrarla con detalle salvo en libros y artículos técnicos, y no me parece que sea "una más en el zoo de subteorías de AP". De hecho, si me planteaba presentarla es porque basta para formalizar la lógica matemática básica (es decir, no el teorema de completitud, por ejemplo, pero sí lo necesario para construir ZFC y, a partir de ahí, usarlo para hacer matemática formal, aunque sin entrar en las garantías de que su lógica es la que debe ser) y requiere aceptar muy pocos hechos intuitivamente ciertos sobre los números naturales (los demás se pueden demostrar formalmente en ella misma).

Ahora, la verdad es que no sé lo largo que se podría hacer un hilo sobre ARP, pero si os interesa, podríamos meternos en harina a ver hasta dónde llegamos.

Pues, personalmente, seguiría el hilo con mucha curiosidad ;)

Un saludo.

03 Junio, 2023, 03:35 pm
Respuesta #71

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El Principio de Inducción parece que se usa libremente en el "lado" Metamatemático.
O sea, se la toma como una más de las leyes naturales del razonamiento lógico,
aunque no se pueda formalizar dentro de un Álgebra de Boole.

Es decir.
Ya que los Números Naturales (y su consabida inducción) se consideran intuitivamente fiables,
no podría dar lugar a contradicciones ningún Axioma que exprese leyes inductivas.

Aunque bueno, la incompletitud es otra cosa...

Sí, yo hablaba de incompletitud: el teorema de Gödel dice que cualquier teoría axiomática recursiva (es decir, que se pueda saber qué es un axioma y qué no) en la que se puedan demostrar los axiomas de Peano es incompleta, y lo que decía es que, aunque no se pueda demostrar el principio de inducción, da igual, el argumento de Gödel vale también. En cambio, hay teorías axiomáticas recursivas en las que se puede hablar de cosas sofisticadas (pero no de números naturales) que son completas, como la geometría elemental de Tarski.

Igual, estoy algo confuso con el significado de Inducción en sentido Metamatemático,
porque mientras las teorías formales restringen el Principio de Inducción
a propiedades sobre un cierto dominio o conjunto,
no sé si tiene sentido considerar que hay un único Principio de Inducción en Metamatemática, o si hay uno para cada situación que se presente.

Las leyes lógicas son universales y funcionan igual en todo contexto.

¿Pero qué significa inducción?

Para un razonamiento de tipo clásico, uno hace algo así:

\(P\) y \(P\to Q\)
__________________
\(Q\)

Aquí, \(P\) y \(Q\) son sentencias, y que, si fueran verdaderas, sería verdadera \(Q\).

No interesa el contenido de \(P\) y \(Q\), sino solamente que son verdaderas.

Ese es un razonamiento válido que se asume, digamos, Metamatemáticamente.

Pero no sé cómo expresar algo así para la inducción.
Imagino un esquema como el siguiente,
para expresar un razonamiento por inducción:

\(P(1)\) y \(\forall n\in\mathbb N: P(n)\to P(n+1)\)
_________________________________________
\(\forall n\in\mathbb N: P(n)\).

La cuestión es que \(P\) podría ser una proposición muy general sobre cualquier cosa,
atada sólo a un valor \(n\in\mathbb N\), pero que incluso el dominio de discurso
de \(P(n)\) y \(P(n+1) \) no tengan relación alguna entre sí.
O sea, para cada \(n\), \(P(n)\) sería una proposición muy distinta.

Podría, más bien, tener una lista infinita de proposiciones \(P_n\) no relacionadas entre sí,
y todavía pretender que sea válido lo siguiente:

\(P_1\) y \(\forall n\in\mathbb N:P_n\to P_{n+1}\)
________________
 \(\forall n\in\mathbb N:P_n\).

Por ejemplo, si \(n\) impar, denotamos
\(P_n\) = una especie animal con \(n\) miembros suma en total al menos \(n\) átomos.

Si \(n\) es par:
\(Q_n\) = entre \(n\) y \(2^n\) hay al menos un número primo.

Esas afirmaciones son verdaderas,
así que el esquema de inducción funcionará.
Pero no sé qué tan general puede enunciarse un Principio de Inducción fuera de una teoría formal.

Yo diría que el principio de inducción afirma que si el 0 tiene una propiedad y, supuesto que la tenga un número natural \( n \), puedes probar que también la tiene \( n+1 \), podemos estar seguros de que todo número natural tiene esa propiedad.

Como bien dices, la naturaleza de la propiedad en cuestión puede ser de lo más diverso, desde propiedades que podamos constatar siempre si un número dado la tiene o no, hasta propiedades que no sepamos cómo verificar, como "2n es la diferencia de dos números primos". Si encontramos los primos, constatamos que es cierta, pero si no los encontramos, nos quedará la duda de si no hemos buscado entre primos suficientemente altos.

Pero el punto más delicado es en realidad que tenemos que poder asegurar que \( P(n) \) realmente expresa una propiedad que se pueda decir objetivamente que un número natural la cumple o no la cumple. Eso no es trivial. Por ejemplo, uno podría considerar aceptable tomar

\( P(n):  \) n es un número natural definible (en castellano) con menos de 12 palabras,

pero, si realmente esto fuera una propiedad bien definida, podríamos razonar que existe

El mínimo número natural definible con menos de 12 palabras

y tenemos la paradoja de Berry. La conclusión es que "ser definibile en castellano" no es una propiedad bien definida que podamos decir objetivamente si un número natural dado la cumple o no, por lo que no podemos aceptar alegremente razonamientos por inducción sobre propiedades que involucren el concepto de "ser definible" (otra cosa es "ser definible en AP" o "ser definible en ZFC", etc.)

¿Y qué propiedades están bien definidas y cuáles no? Pues no es posible responder a eso en general, pero ni falta que hace. Cuando alguien te demuestra algo por inducción, sólo tienes que tener en cuenta, a la hora de decidir si el argumento te convence o no, si la propiedad sobre la que se lleva a cabo la inducción es realmente algo que, si te dan un número natural, sabes comprobar si se cumple o no o, al menos, si puedes asegurar que es verdadera o falsa, aunque no sepas seguro cómo comprobarlo (como el ser diferencia de dos primos).

Citar
Ahora, la verdad es que no sé lo largo que se podría hacer un hilo sobre ARP, pero si os interesa, podríamos meternos en harina a ver hasta dónde llegamos.

Si tenés energía y ganas, pues estaría bueno.

Pues, personalmente, seguiría el hilo con mucha curiosidad ;)

Vale, pues, en cuanto pueda me pondré a ello. De momento he publicado un último mensaje en el hilo principal a modo de conclusión. Por supuesto, como digo allí, este hilo sigue abierto para lo que sea.

09 Junio, 2023, 04:34 pm
Respuesta #72

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo.

Estoy pasando a latex el hilo (porque me ha gustado mucho y quería tenerlo en pdf), y he encontrado unas erratas y un error (no se como se me pudo escapar en su día ::)) en lo siguiente. Marco en rojo lo que comento después y en azul las erratas corregidas.

  • Si \( \lambda \) es un ordinal límite, entonces \( \alpha+\lambda \) es el supremo de los ordinales \( \alpha+\beta \) con \( \beta\prec\lambda \).

En efecto, pongamos que \( \alpha = \omega^{\delta_1}+\cdots + \omega^{\delta_m} \) y \( \lambda = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \), donde \( \epsilon_n\succ 0 \), ya que \( \lambda \) es un ordinal límite. Entonces

\( \alpha+\lambda = \omega^{\delta_1}+\cdots + \omega^{\delta_k}+\omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \),

donde \( k \) es el mayor índice que cumple \( \delta_k\succeq \epsilon_1 \) (con la posibilidad de que \( k=0 \) y no esté la primera parte). Es fácil ver que si \( \beta\prec \lambda \), entonces \( \alpha+\beta\prec \alpha+\lambda \). Recíprocamente, tomemos \( \eta\prec \alpha+\lambda \) y vamos a ver que existe un \( \beta\prec \lambda \) tal que \( \eta\prec \alpha+\beta \). Distingamos varios casos:

Puede ser que la expresión de \( \eta \) se prolongue hasta la de \( \alpha+\lambda \), en cuyo caso hay dos posibilidades:

Si \( \eta = \omega^{\delta_1}+\cdots + \omega^{\delta_j} \), con \( j\leq k \), entonces \( \eta\preceq \alpha= \alpha+0 \), con \( 0\prec \lambda \), y se cumple lo que queremos probar.

Si \( \eta = \omega^{\delta_1}+\cdots + \omega^{\delta_k}+\omega^{\epsilon_1}+\cdots + \omega^{\epsilon_j} \), con \( j <n \), entonces tomamos \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_j}\prec \lambda \) y se cumple que \( \eta\prec\alpha+\color{blue}\beta \).

La alternativa es que un (mínimo) exponente de \( \eta \) sea menor que el correspondiente de \( \alpha+\lambda \), y también hay dos casos:

Si \( \eta = \omega^{\delta_1}+\cdots + \omega^{\delta_j}+\omega^{\delta'_{j+1}}+\cdots \), con \( \delta'_{j+1}\prec \delta_{j+1} \), entonces \( \eta\prec \alpha= \alpha+0 \), como antes.

Si \( \eta = \omega^{\delta_1}+\cdots + \omega\color{blue}^{\delta_k}\color{black}+\omega^{\epsilon_1}+\cdots + \omega\color{blue}^{\epsilon_j}\color{black}+\omega^{\epsilon'_{j+1}}+\cdots \), con \( \epsilon'_{j+1}\prec \epsilon_{j+1} \), entonces tomamos \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_j}+\omega^{\epsilon'_{j+1}}\prec \lambda \) y \( \eta \prec \alpha+\beta \).

Lo primero, he marcado la palabra "recíprocamente", porque creo que no es correcto utilizarla, ya que no estamos probando exactamente el recíproco de lo que se ha dicho anteriormente, sino la otra condición para que \( \alpha + \lambda \) sea supremo.

Respecto a lo marcado en rojo al final, es falso, ¿no? Tal y como esta puesto creo que sería \( \alpha + \beta \preceq \eta \), puesto que \( \eta \) extiende a \( \alpha + \beta \). Para finalizar la prueba creo que habría que distinguir otros dos subcasos:

  • Si \( j+1<n \) tomamos \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_j}+\omega^{\epsilon_{j+1}}\prec \lambda \) y \( \eta \prec \alpha+\beta \).
  • Si \( j+1=n \) tomamos \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_{n-1}}+\omega^{\epsilon'_n} + 1 \prec \lambda \) y \( \eta \prec \alpha+\beta \).

Un saludo.

09 Junio, 2023, 05:17 pm
Respuesta #73

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Estoy pasando a latex el hilo (porque me ha gustado mucho y quería tenerlo en pdf), y he encontrado unas erratas y un error (no se como se me pudo escapar en su día ::)) en lo siguiente. Marco en rojo lo que comento después y en azul las erratas corregidas.

En efecto, estaba mal ese punto. Ya lo he corregido. Mil gracias una vez más.

09 Junio, 2023, 10:44 pm
Respuesta #74

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Otra pregunta:

\( \phi-\text{IND}(\epsilon_0)\equiv \forall \alpha\in E\ \forall \beta((\beta\prec \alpha\land \phi(\beta))\rightarrow \phi(\alpha))\rightarrow \forall \alpha\in E\,\phi(\alpha). \)

Ahí afirmamos lo que habíamos planteado antes en azul: si bajo el supuesto de que todo \( \beta\prec \alpha \) cumple \( \phi(\beta) \) podemos probar \( P(\alpha) \), esto garantiza que todo ordinal cumple \( P(\alpha) \).

Notemos que, si la propiedad \( P(\alpha) \) puede definirse aritméticamente (recordemos que los ordinales no son más que números naturales, luego \( P(\alpha) \) podría ser cualquier propiedad del estilo "\( \alpha \) es múltiplo de 5" etc.) este principio de inducción puede formalizarse en el lenguaje de la aritmética, mediante la fórmula que en la respuesta #7 hemos llamado

\( P-\mbox{IND}(\epsilon_0)\equiv \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \alpha\in E\,P(\alpha) \).

¿Son realmente estas dos fórmulas equivalentes?

Es que, pensándolo ahora mejor si veo claro que la segunda fórmula (en azul) expresa formalmente lo que buscamos de la inducción, pero no lo veo tan claro para la primera, ni veo claro que formalmente sean equivalentes ???

Un saludo.

09 Junio, 2023, 11:16 pm
Respuesta #75

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Son realmente estas dos fórmulas equivalentes?

No. Era otra errata.  ::)  Ya la he corregido.    \gracias

10 Junio, 2023, 05:08 pm
Respuesta #76

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

No. Era otra errata.  ::)  Ya la he corregido.    \gracias

Pero, insisto, tras la corrección que has hecho las fórmulas correspondientes son:

\( \forall \alpha\in E\ \color{blue}\forall \beta((\beta\prec \alpha{\rightarrow} \phi(\beta))\rightarrow \phi(\alpha)) \color{black}\rightarrow \forall \alpha\in E\,\phi(\alpha) \)

y

\( \forall \alpha\in E(\color{blue}\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha)\color{black})\rightarrow \forall \alpha\in E\,P(\alpha) \)

¿Son equivalentes?

Porque las partes azules (en general, tal vez no en este caso concreto) no me parecen equivalentes.
Serían dos expresiones de la forma \( \forall x (\psi \rightarrow \zeta) \) (la primera) y \( \forall x \psi \rightarrow \zeta \) (la segunda) y, aunque la primera implica la segunda, en general no son lógicamente equivalentes. Por ejemplo, en AP tomando \( \psi \equiv x+y=2 \) y \( \zeta \equiv x \cdot y = 2x \), se tiene que la segunda es cierta en el modelo estándar, pero la primera no lo es, por tanto no pueden ser lógicamente equivalentes.

Así que, me surge de nuevo la duda de si en este caso particular sí son equivalentes, o si de nuevo hay una errata con los paréntesis de la primera fórmula.

Un saludo.

10 Junio, 2023, 05:25 pm
Respuesta #77

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero, insisto, tras la corrección que has hecho las fórmulas correspondientes son:

\( \forall \alpha\in E\ \color{blue}\forall \beta((\beta\prec \alpha{\rightarrow} \phi(\beta))\rightarrow \phi(\alpha)) \color{black}\rightarrow \forall \alpha\in E\,\phi(\alpha) \)

y

\( \forall \alpha\in E(\color{blue}\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha)\color{black})\rightarrow \forall \alpha\in E\,P(\alpha) \)

¿Son equivalentes?

 :banghead:   Vi que había una conjunción donde debía haber una implicación y la cambié, y no se me ocurrió revisar los paréntesis. Ya está corregido. He añadido el \( \beta \in E \) para que las dos fórmulas queden iguales, aunque en realidad \( \beta\prec \alpha \) ya implica \( \beta\in E \).

¡Odio las erratas!

Gracias de nuevo.

11 Junio, 2023, 11:42 am
Respuesta #78

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
¡Odio las erratas!

Pues si pusiera aquí todas las que realmente estoy encontrando respecto a pequeñas erratas ortográficas creo que me matas... ::) Pero, como las corrijo casi sin darme cuenta, se me olvida apuntar donde están y ahora ya me es imposible encontrarlas :banghead:

Aun así, he encontrado un par más que creo que si merece la pena comentar aquí:

Si \( \eta=0 \) tenemos que probar \( P^*(\alpha+1) \), pero la hipótesis \( P^*(\alpha) \) equivale a que \( \forall \beta\in E(\beta\prec \alpha+1\rightarrow P(\beta)) \), y entonces podemos aplicar (B), que nos da \( P^*(\alpha+1) \), como queríamos.

Aquí, más que aplicar (B) (que directamente no se podría pues la hipótesis no es exactamente igual, en ella aparece \( P^*(\beta) \) y aquí \( P(\beta) \)), creo que aplicamos (A) para obtener \( P(\alpha+1) \) y luego, junto a \( P^*(\alpha) \) obtenemos ya \( P^*(\alpha+1) \)

De hecho, creo que fue culpa mía, porque eso de aplicar B está corregido y te lo comenté yo :P

Supongamos ahora que \( \eta = \delta+1 \), y entonces tenemos que probar \( P^*(\alpha+\omega^{\delta+1}) \), es decir, tenemos que probar:

(F) \( \forall \beta\in E(\beta\prec \alpha+\omega^\delta\cdot \omega\rightarrow P\color{red}^*\color{black}(\beta)) \).

Ahora bien, en el mensaje sobre aritmética ordinal hemos visto que si \( \beta\prec \alpha+\omega^\delta\cdot\omega \), existe un \( \gamma <\omega^\delta\cdot \omega \) tal que \( \beta\prec \alpha+\gamma \), y a su vez existe un \( k\prec \omega \) tal que \( \gamma \prec \omega^\delta\cdot k \), luego en total \( \beta \prec \alpha+\omega^\delta \cdot k \).

Esto hace que baste con demostrar:

(G) \( \forall k\in E(k\prec \omega\rightarrow P^*(\alpha+\omega^\delta\cdot k)) \).

En efecto, admitiendo (G), para probar (F) basta observar que si \( \beta\prec \alpha+\omega^\delta\cdot \omega \) existe un \( k \) tal que \( \beta\prec \alpha+\omega^\delta\cdot k \), luego por (G) se cumple \( P^*(\alpha+\omega^\delta\cdot k) \), luego también \( P\color{red}^*\color{black}(\beta) \), por la definición de \( P^* \), y así tenemos (F).

Sobran los dos "*" marcados en rojo.

Un saludo.

11 Junio, 2023, 12:55 pm
Respuesta #79

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pues si pusiera aquí todas las que realmente estoy encontrando respecto a pequeñas erratas ortográficas creo que me matas... ::) Pero, como las corrijo casi sin darme cuenta, se me olvida apuntar donde están y ahora ya me es imposible encontrarlas :banghead:

No te preocupes. Ya haces mucho detectando todas las erratas que detectas.

Sobran los dos "*" marcados en rojo.

No. Están bien como están. Lo que era confuso era la frase que precede a (F) y que he cambiado. Tú has entendido que (F) era la definición de \( P^*(\alpha+\omega^{\delta+1}) \), pero para ello en (F) debería haber un \( \preceq \) en lugar de un \( \prec \). En realidad (F) implica \( P^*(\alpha+\omega^{\delta+1}) \) por (B).

En cuanto al segundo asterisco que querías quitar, cuando digo "por la definición de \( P^* \)", me refiero a que de ella se sigue inmediatamente que si se cumple \( P^* \) para un ordinal, se cumple para cualquier otro menor.