Supongo que está familiarizado con los números ordinales (http://en.wikipedia.org/wiki/Ord…), el espacio en el que generalmente se aplica la inducción transfinita.
La inducción simple funciona así: si puedo probar P0 y puedo probar Pn -> P (n + 1) para todos los n, entonces probé Pn para todos los n. Esto se debe a que se puede alcanzar cada número natural dando pasos uno a la vez desde 0. El supuesto central aquí que no es cierto para los números ordinales es que cada elemento tiene un predecesor inmediato.
Para evitar esto, usamos “inducción fuerte”, que en el caso de los números naturales resulta ser equivalente. Dice así:
- ¿Sigue siendo relevante el trabajo 'Principia Mathematica' (de Bertrand Russell y AN Whitehead) en Lógica y Matemáticas?
- ¿Mathcounts da premios? Si es así, ¿se otorgan premios por el desempeño de la competencia o por resolver problemas abiertos particulares en la investigación matemática?
- ¿Cuál es la conjetura de Hodge en términos simples?
- ¿Cómo cambiará la industria del software si definimos x / 0 como 0 o una cantidad definida?
- ¿Qué significa [matemáticas] L ^ 2 (\ mathbb {R} ^ 2) [/ matemáticas] en matemáticas?
[matemáticas] (P (0) \ wedge \ forall x ((\ forall y <x (Py)) \ to Px)) \ to \ forall x (Px). [/ math]
En otras palabras, en lugar de probar Pn -> P (n + 1), supongo Py para todo y <x e intento probar Px. Suena como una suposición más fuerte, pero resulta que es más ampliamente aplicable. En realidad puede saltar por encima del infinito. Supongamos que hemos demostrado lo anterior para una propiedad P. Es intuitivamente claro (y probablemente demostrable) que Pn es demostrable para todo n. Pero luego tenemos que [math] \ forall x \ in \ omega Px [/ math]; es decir, [math] \ forall x <\ omega Px [/ math], por lo que se deduce que [math] P \ omega [/ math] es válido. Y así, para [matemáticas] P (\ omega + 1) [/ matemáticas], y así sucesivamente …
El que generalmente atrae a las personas es el salto de la inducción transfinita a la recursión transfinita. La inducción transfinita es un medio para probar, y la recursión transfinita es un medio para definir funciones. Por ejemplo, podemos definir la secuencia de Fibonacci de forma recursiva con tres reglas: [matemática] a_0 = 1 [/ matemática], [matemática] a_1 = 1 [/ matemática] y [matemática] a_ {n + 2} = a_ {n +1} + a_n [/ matemáticas]. Esta es una función de los números naturales (los índices en los subíndices) a sí mismo (los propios números de Fibonacci).
Algo similar puede suceder con los ordinales generales. La razón por la que esto es complicado es, lamentablemente, de notación. Cuando intentamos definir algo de forma recursiva en un ordinal arbitrario, nos encontramos con el incómodo problema de que el codominio de la función que estamos tratando de definir puede no ser, de hecho, un conjunto. No se garantiza que sea un set hasta que lo hayamos demostrado. De hecho, para que el teorema de recursividad transfinita funcione, tenemos que suspender nuestra incredulidad de notación por un momento y usar “propiedades similares a funciones” (declaraciones sobre dos conjuntos que funcionan como funciones similares), hasta que podamos restringir el dominio a un conjunto razonable y obtener una función.
Dejando a un lado toda esa tontería, el teorema de recursión transfinita es el siguiente: comienza con un conjunto bien ordenado y una “definición recursiva” de una función. Reclama la existencia y la unicidad de una función que satisface la “definición recursiva”. Lo que queremos decir con una “definición recursiva” es esto:
– Tengo una regla que me dice qué es f (0).
– Para cualquier x, si sé cómo se comporta f en todo antes de x, entonces sé cómo se comporta f en x.
Lea esa segunda declaración nuevamente y vea cómo podríamos codificar eso matemáticamente. Básicamente, dado [math] f | _ {\ text {seg} x} [/ math], tenemos que saber f (x). (aquí ‘seg x’ es el conjunto de todas las cosas en A que son estrictamente menores que x)
Es un poco intuitivo, pero esto puede ser codificado por un mapa que toma una función cuyo dominio es un segmento inicial de A (como f restringido a seg x), y le da un elemento en A (como f (x)), anotado muy confusamente como:
[matemáticas] G: (A ^ {\ text {seg}} \ a A) \ a A [/ matemáticas]
Este conjunto [math] (A ^ {\ text {seg}} \ to A) [/ math] es el conjunto de todos los mapas desde los segmentos iniciales de A hasta A. El teorema de recursividad transfinita garantiza entonces que hay una función que satisface esta “definición recursiva”; es decir, si le dice a G cómo se comporta f en todo antes de x, G escupirá mágicamente f (x). Ese es el significado de esta (imo bella) pieza de truco de notación:
[matemáticas] f (x) = G (f | _ {\ text {seg} x}) [/ matemáticas]
