Autor Tema: Proceso repetido infinitas veces

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

27 Julio, 2011, 11:16 am
Respuesta #10

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Por supuesto, NFU es también una teoría de primer orden.

Infinitas premisas en principio sí que las admite la lógica de primer orden, pero por el teorema de compacidad cualquier teorema deducido a partir de infinitas premisas es deducible a partir sólo de un número finito de premisas. De todas maneras, si trabajas en ZFC o NFU tus únicas premisas son los axiomas de la teoría ZFC o NFU.

Lo de la inducción transfinita es el mismo problema de antes. La infinitud es sólo aparente, aparece dentro de la teoría (hay infinitos ordinales, cada ordinal infinito tiene infinitos ordinales anteriores a él, etc) pero a nivel de la lógica no hay ningún infinito por ninguna parte.
El principio de inducción transfinito es un esquema de fórmulas de primer orden. Una instancia de ese principio para la fórmula \( \varphi(x) \) (la propiedad que queremos probar que tienen todos los ordinales mediante inducción) es la siguiente fórmula (una sola) en lógica de primer orden (uso la convención de usar letras griegas miníusculas para los ordinales, y un cuantificador de la forma \( \forall \alpha \) se debe interpretar como "para todo ordinal" y no como "para todo conjunto") :
\( \forall \alpha ( \forall \beta (\beta < \alpha \rightarrow \varphi(\beta)) \rightarrow \varphi(\alpha)) \rightarrow \forall \alpha \varphi(\alpha)  \)

Es decir, el principio de inducción dice que si para todo ordinal \( \alpha \), si todo ordinal \( \beta < \alpha \) cumple la propiedad entonces \( \alpha \) también la cumple, entonces todo ordinal cumple la propiedad.

Entonces, basándonos en el principio de inducción, para probar que todo ordinal cumple una propiedad, debemos dar una demostración de \( \forall \alpha ( \forall \beta (\beta < \alpha \rightarrow \varphi(\beta)) \rightarrow \varphi(\alpha)) \). Para probar esto, basta probarlo para un \( \alpha \) genérico (es decir, usando sólo en la demostración que \( \alpha \) es un ordinal). Esto es porque por una propiedad bien conocida de lógica clásica de primer orden, si \( \vdash \psi(x) \) entonces también \( \vdash \forall x \psi(x) \).
Es decir, basta tomando como premisa \(  \forall \beta (\beta < \alpha \rightarrow \varphi(\beta)) \) demostrar \( \varphi(\alpha) \). La clave es fijarse en que, dado un \( \alpha \), tenemos una sola premisa: \(  \forall \beta (\beta < \alpha \rightarrow \varphi(\beta)) \). No tenemos infinitas premisas \( \varphi(\beta) \) para cada \( \beta < \alpha \). Lo que sí es cierto es que de nuestra única premisa se pueden deducir todas estas (infinitas) premisas, pero en cada demostración particular usarás como mucho un número finito de ellas. Además, la demostración de \( \varphi(\alpha) \) a partir de nuestra premisa es siempre finita: fíjate que en cualquier demostración por inducción transfinita que veas, lo que se hace es dar un argumento (finito) para probar \(  \varphi(\alpha) \).

Veamos un ejemplo concreto para ilustrar esto. Supón quieres probar que \( \alpha \leq \aleph_{\alpha} \) para todo \( \alpha \). Lo que haces es (usando la versión de inducción que separa en casos para el 0, ordinal sucesor y ordinal límite): para el 0 es obvio, ya que \( 0 < \omega = \aleph_0 \). Caso sucesor: supongamos un \( \alpha \) sucesor genérico. Entonces \( \alpha = \beta + 1 \) para algún \( \beta \). Por hipótesis de inducción, \( \beta \leq \aleph_\beta \). Luego \( \beta \leq \aleph_\beta < \aleph_{\beta + 1} = \aleph_{\alpha} \). Y de aquí se deduce (usando que para todo par de ordinales \( \gamma, \epsilon \) si \( \gamma < \epsilon \) entonces \( \gamma + 1 \leq \epsilon \)) que \( \alpha = \beta + 1 \leq \aleph_\alpha \). Como \( \alpha \) era un ordinal genérico, esta demostración (finita) nos da que \( \forall \alpha (\alpha \; sucesor \rightarrow \varphi(\alpha)) \). Finalmente sea \( \alpha \) un ordinal límite cualquiera, y suponemos como hipótesis de inducción \( \forall \beta (\beta < \alpha \rightarrow \beta \leq \aleph_\beta) \). Esta es una única premisa. Ahora, de aquí se deduce \( \forall \beta (\beta < \alpha \rightarrow \beta \leq \aleph_\alpha) \), ya que si \( \beta < \alpha \) también \( \aleph_\beta < \aleph_\alpha \) (la función \( \aleph \) es estrictamente creciente). Y finalmente de ahí se deduce que \( \bigcup_{\beta < \alpha} \beta \leq \aleph_\alpha  \). Pero, por ser \( \alpha \) límite, \( \bigcup_{\beta < \alpha} \beta = \alpha \) y por tanto \( \alpha \leq \aleph_\alpha \). Esto acaba la inducción (de nuevo, como \( \alpha \) era un ordinal límite genérico y en la demostración sólo hemos usado que es límite, hemos demostrado que para todo ordinal límite se cumple eso). Como ves, la demostración es finita (unas pocas líneas en lenguaje semiformal, muchas más si quieres una demostración formal de lógica clásica de primer orden, pero un número finito al fin y al cabo) donde hemos usado solamente una premisa en el caso límite y en cada caso la demostración es un argumento finito. En el caso límite en especial, fíjate en que hemos tratado con todas las \( \beta < \alpha \) de forma simultánea mediante el uso de cuantificadores, y eso es lo que hace que la demostración en ese caso sea finita.

Saludos

27 Julio, 2011, 12:02 pm
Respuesta #11

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Hola

Creo que ya lo he entendido: un proceso que conste de  lo que yo entiendo por"infinitos pasos", pero que dichos pasos se puedan "resumir" en una sola linea mediante el cuantificador universal por ejemplo  [ \forall \beta (\beta &lt; \alpha \rightarrow \varphi(\beta))] , se considera como un paso único finito de la demostración.

Mi error era que yo a dichos pasos , aunque fueran resumibles a un paso finito cuantificando sobre variables, los consideraba infinitos cuando el dominio de dicha variable era infinito

Resumiendo, que mientras me limite a los símbolos del lenguaje formal de primer orden (incluyendo o no cuantificadores), toda demostración  que se puede escribir con un número finito de signos, es una demostración finitista.¿Es así?

Otra cuestión, en el caso restringido de inducción sobre N (el último axioma de Peano) Peano lo introduce como un axioma más, aunque a mi me parece de "pura lógica". La inducción transfinita (que es la generalización de ese axioma de Peano para poder aplicarlo hasta más alla de los ordinales finitos y que tambien resulta intuitivamente claro), se utiliza la palabra principio. Entonces, ¿la inducción transfinita es un teorema o es un axioma en las teorías de conjuntos?

27 Julio, 2011, 01:17 pm
Respuesta #12

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Así es.

Otra cuestión, en el caso restringido de inducción sobre N (el último axioma de Peano) Peano lo introduce como un axioma más, aunque a mi me parece de "pura lógica". La inducción transfinita (que es la generalización de ese axioma de Peano para poder aplicarlo hasta más alla de los ordinales finitos y que tambien resulta intuitivamente claro), se utiliza la palabra principio. Entonces, ¿la inducción transfinita es un teorema o es un axioma en las teorías de conjuntos?

El axioma de Peano de inducción es de tan "pura lógica" como los demás (por ejemplo, es de pura lógica que el 0 es el único natural que no es sucesor de algún otro). Precisamente porque es de pura lógica lo añadió Peano a sus axiomas para la aritmética. Piensa que los axiomas de Peano no son más que propiedades muy simples que cumplen los naturales y que, en principio, son suficientes para demostrar todas las demás propiedades de los naturales (aunque ahora sabemos que esto es falso, sí es suficiente para demostrar prácticamente todas las propiedades sobre naturales que se presentan en la práctica -teoría de números, etc-).

La inducción transfinita es un teorema en ZFC (creo que en NFU también). Es decir, se demuestra de los axiomas básicos de ZFC. De hecho, los principios de inducción estan muy estrechamente ligados a principios de buen orden. Lo que se demuestra es que los ordinales están bien ordenados (todo conjunto no vacío de ordinales tiene mínimo), que es un teorema bien conocido sobre ordinales, y a partir de aquí el principio del buen orden sale como corolario de la siguiente forma, usando reducción al absurdo: supongamos que se cumple \( \forall \alpha (\forall \beta < \alpha \; \varphi(\beta) \rightarrow \varphi(\alpha)) \) pero no se cumple \( \forall \alpha \varphi(\alpha) \). Entonces existe algún ordinal \( \gamma \) tal que \( \neg \varphi(\gamma) \). Luego el conjunto \( \{ \epsilon \leq \gamma : \neg \varphi(\epsilon) \} \) es no vacío y al ser un conjunto de ordinales tiene mínimo, digamos \( \chi \). Entonces, por ser \( \chi \) mínimo tenemos que \( \forall \beta < \chi \; \varphi(\beta) \) luego por la hipótesis del principio de inducción \( \forall \alpha (\forall \beta < \alpha \; \varphi(\beta) \rightarrow \varphi(\alpha)) \) debemos tener \( \varphi(\chi) \). Contradicción, pues teníamos que \( \neg \varphi (\chi) \).

De manera parecida todo principio de inducción se puede deducir de un principio de buen orden. La implicación inversa también es cierta, de un principio de inducción se puede obtener un principio de buen orden.

Saludos