Segunda demostración de la infinitud de primos

Viene de aquí

Con el bagage que hemos conseguido en el post anterior, atacamos una segunda demostración de la infinitud de los números primos.

Supongamos lo contrario de lo que deseamos demostrar: Supongamos que el conjunto de primos es finito, siendo p el mayor de todos ellos.

Consideremos el número x = 2^p -1.

Está claro que x es mayor que p, por lo que no podrá ser primo. Si lo fuera ya estaría demostrada la falsedad de nuestra suposición.

Así pues, x debe ser un número compuesto (esto es: tiene divisores distintos de sí mismo y de la unidad). Llamemos q a uno de sus divisores primos. Si q divide a 2^p -1, (esto es: dividiendo 2^p -1 entre q obtenemos resto nulo) entonces al dividir 2^p ( que es una unidad más grande que 2^p -1) entre q nos dará 1 de resto. Diremos que 2^p en congruente con 1, módulo q, y lo expresaremos así:

2^p ≡1 (mod q)

Las congruencias fueron introducidas en este blog cuando hablábamos del calendario. El lector interesado puede echar una ojeada a aquel post.

Centrémonos en el conjunto Z_q de restos módulo q. Este conjunto está formado por q elementos, cada uno de los cuales es una clase de equivalencia. El [0] es el elemento nuetro de la suma definida en Z_q, y el [1] lo es en el producto.

El conjunto de las clases Z_q de restos módulo q con las operaciones suma y producto es un cuerpo, y por lo tanto el conjunto Z_q -{0} con la operación producto es un grupo. Este grupo tiene (q-1) elementos.

Volvamos a la congruencia arriba indicada, cuya trascendentalidad en la demostración está indicada por el color rojo sangre con el que ha sido escrita:

2^p ≡1 (mod q)

¿Qué quiere esto decir?

Pues traducido al lenguaje de las clases de restos módulo q quiere decir ni más ni menos que dentro de Z_q el elemento [2] operado (multiplicado) consigo mismo p veces nos da como resultado el neutro del grupo (el [1]). Además, podemos asegurar (y esto es crucial), que no existe ningún valor menor que p para el cual ocurre lo mismo.

¿Porqué?

Pues porque p es primo! Piénsenlo un poco y lo verán claro:

Si hubiera un número menor, r para el cual ocurre que 2^r ≡1 (mod q), si siguiéramos operando el 2 consigo mismo a la de 2r, 3r,...,kr veces volveríamos a la unidad, tras repetir órbitas de r pasos. Así pues, serían los múltiplos de r los que consiguen la unidad. Dada la vuelta al razonamiento, si 2^p ≡1 (mod q); entonces sólo caben dos posibilidades:

1.- El orden (número mínimo de veces necesarias para obtener la unidad) del [2] es p

2.- El orden del [2] es un divisor de p

Al ser p primo, no tiene divisores, y por tanto operando sucesivamente el 2 consigo mismo no conseguimos el 1 hasta haber repetido p veces.

Por el Teorema de Lagrange, el orden (que, recordemos, es el número mínimo de veces que debemos operar dicho elemento consigo mismo para obtener el elemento neutro) de cualquier elemento (p en este caso) es divisor del orden del grupo entero (q-1).

Así pues, p debe dividir a (q-1)

Pero para que eso ocurra, p debe ser menor que q.

Pero p era, por suposición inicial el primo más grande.

Y q es un primo divisor de 2^p -1.

Luego hemos encontrado un primo más grande que el primo más grande.

Luego p no puede ser el primo más grande.

Luego la hipótesis de partida era falsa necesariamente.

Luego el número de primos es infinito.

Espero que les haya gustado la demostración. En cierta medida es una demostración no elemental, pues necesita del auxilio de una parte de la matemática aparentemente alejada del tema central que se está tratando. Las demostraciones no elementales suelen ser más sencillas, pero requieren un precio: hay que utilizar herramientas más sofisticadas, y lo que uno se ahorra en el cálculo lo tiene que invertir en conocerlas. La matemática es una cruel amante, y exige sangre, sudor y lágrimas por un camino o por el otro...

En el próximo post veremos una demostración más elemental, pero también sorprendente de la infinitud de los números primos. Espero que me esperen...

Segunda demostración de la infinitud de primos (1)

Recordemos nuestro reto: demostrar de varias formas diferentes un mismo resultado: la infinitud del conjunto de números primos. Para la segunda demostración debemos adentrarnos un poquito en la teoría de grupos.

Un grupo no es sino un conjunto con una operación interna que cumple ciertas propiedades. La operación interna es, hablando en plata, una forma de relacionar cada par de elementos del grupo (a,b) con un elemento del grupo, c que también pertenece al grupo.

Dentro de una notación multiplicativa, escribiríamos a · b = c

Pues bien, para que un conjunto G sea un grupo hace falta que dicha operación cumpla un mínimo de tres propiedades, que son:

1.- Propiedad asociativa:

a · ( b · c ) = (a · b ) · c

2.- Existencia de elemento neutro , un elemento distinguido e del grupo que se caracteriza por que operado con cualquier otro elemento lo deja igual:

a · e = e · a = a

3.- Existencia de elemento simétrico para todo elemento del grupo:

Para todo a de G existe un b también de G tal que a · b = b · a = e

A tal elemento b lo llamaremos inverso de a, y podremos expresarlo así: b = a^-1

Siempre que una operación interna en un conjunto verifique estas propiedades estamos ante un grupo. Parece mentira que con tan poca cosa exista una teoría (la teoría de grupos, evidentemente) tan rica e impresionante.

Verán que no hemos definido la propiedad conmutativa (aquello de que el orden de los factores no altera el producto). No lo hemos hecho porque la noción de grupo se definió sin tal operación. Los grupos que la cumplen se llaman grupos abelianos, o grupos conmutativos. Existe un buen motivo para no exigir que un grupo deba cumplir esta propiedad; y es que los que la cumplen son mucho menos interesantes matemáticamente hablando que los que no lo hacen. Así pues, los grupos abelianos son, dentro de la categoría de los grupos, los más triviales y tontorrones.

Pues bien, existen grupos de infinitos elementos (el grupo de los enteros con la operación suma por ejemplo), y otros finitos (el grupo de las clases de restos módulo p). Hablamos de estos en dos post hace más de un año, aquí:

En aquellos posts comentábamos el llamado Teorema de Lagrange, que dice que:

Dado un grupo G de orden n, si H es un subgrupo de G entonces el orden de H, o(H) es divisor de n

Recordemos que el orden de un grupo finito es, simplemente, su número de elementos. Así pues, para que un subconjunto de un grupo sea a su vez un grupo, es necesario (si bien NO ES SUFICIENTE) que su orden sea divisor del orden del grupo grande. Si tenemos un grupo de 8 elementos, puede ser esperable encontrar subgrupos de 1, 2 y 4 elementos, pero jamás de 3,5,ó 7.

¿Intentamos demostrarlo?

Sea G un grupo, y sea N un subgrupo suyo. Denotaremos /G/ al orden de G y (en un alarde de originalidad) /N/ al orden de N .

Consideremos una relación binaria entre los elementos del grupo G, diciendo que los elementos a y b estarán relacionadas sí y sólo si el elemento ab^-1 pertenece al subgrupo N. No hace falta que a ó b sean de N, tan sólo hace falta que ab^-1 lo sea. Para denotar que a está relacionado con b escribiremos a ≈ b

Es fácil comprobar que ésta es una relación de equivalencia. Esto es: que cumple la propiedad reflexiva, simétrica y transitiva.

En efecto,

a ≈ a, pues a · a^-1 = e, y e debe pertenecer a T si éste último si quiere aspirar a ser grupo, porque debe poseer al elemento neutro. Luego todo elemento está relacionado consigo mismo y se cumple la propiedad reflexiva.

Por otro lado, a ≈ b implica que ab^-1 pertenece a T, pero como T es un grupo su inverso (ab^-1 )^-1 =ba^-1 también pertenererá a T, y por ello tendremos que b≈a; y se cumple la simétrica.

Para terminar, si a ≈ b y b ≈ c, entonces ab^-1 y bc^-1 pertenecen a T. Demostrar que a está necesariametne relacionado con c es sencillo de demostrar teniendo en cuenta que por ser T un grupo, el producto de ab^-1 y bc^-1 también pertenecerá a T, y (ab^-1) ·( bc^-1) = a · (b^-1 · b) · c^-1 = ac^-1. Luego cumple la transitiva y hemos demostrado que efectivamente estamos ante una relación de equivalencia.

Pues bien, como sabemos, una relación de equivalencia hace cristalizar en el seno del conjunto en el que está definida una partición del mismo en clases de equivalencia. Dentro de cada clase, todos los elementos están relacionados entre sí.

¿Cómo son estas clases de equivalencia en nuestro caso?

Dado un elemento a de G, todos los elementos relacionados con él mediante la relación arriba definida son de la forma (b · a), siendo b cualquier elemento del subconjunto T. A riesgo de ser reiterativo:

Si un elemento x pertenece a la misma clase que uno dado a, entonces x puede expresarse siempre como la operación algún elemento del interior de T con el propio a. (Querido lector, no siga adelante sin entender esto; en este paseo no tenemos prisa alguna)

Demostrar esto es sencillo: que x y a estén relacionados implica que x · a^-1 es igual a algún b de T por definición de la relación.

x · a^-1 = b

x · a^-1 · a = b · a

x · e = b · a

x = b ·a , como queríamos demostrar.

Estamos muy cerca del final: si la clase de equivalencia de cualquier elemento a del grupo G es el conjunto de los elementos de la forma b ·a, siendo b en elemento de T, entonces en cada clase habrá tantos elementos como en el propio T, y por lo tanto en número de elementos de todo G será múltiplo del número de elementos de T.

Con lo que el teorema queda demostrado.

Un tipo de grupos muy especiales son los llamados grupos cíclicos que son aquellos que se generan por uno sólo de sus elementos operado consigo mismo. Hablamos de ellos en los dos posts enlazados más arriba. Sería interesante un recuerdo de lo que decíamos entonces para entender en toda su profundidad lo que seguirá.

En estos grupos cíclicos, (y esto es importante para lo que seguirá) orden del grupo es el número de veces que un elemento se puede operar consigo mismo hasta conseguir el neutro.  A veces, se necesitan tantas veces como elementos tiene el grupo. Esto quiere decir que cada vez obtenemos un elemento diferente, y cuando llegamos al neutro hemos pasado por todos. En este caso, el grupo se denomina monógeno, porque es engendrado por uno sólo de sus elementos.

Un resultado es crucial para nuestros propósitos:

1.- El orden de un elemento es siempre divisor del orden del grupo entero. 

Esto es evidente en cuanto comprobamos que el conjunto de todos los engendrados por un elemento es un subgrupo, y aplicamos el teorema de Lagrange. 

P.S. Ahora podemos acometer la segunda demostración de infinitud de la cantidad de números primos. ¿Quién iba a decir que necesitaríamos nociones de teoría de grupos para hablar de primos?

Sigue aquí

La demostración de Euclides

Viene de aquí. 

Euclides descubrió, o la tradición nos dice que Euclides descubrió que existe una infinidad de números primos hace más de 2.200 años.

La demostración, no por conocida ad nauseam es menos bella, de modo que no nos la vamos a ahorrar aquí. La belleza de esta demostración depende en parte del hecho de utilizar exclusivamente argumentos finitistas para demostrar la infinitud por reducción al absurdo.

Esto es importante, porque el manejo del infinito es un paseo extremadamente problemático en el que mil peligros acechan por doquier. Por el contrario si utilizamos como hizo Euclides, argumentos exclusivamente finitistas, y no involucramos al infinito en momento alguno, conjuramos posibles malas utilizaciones de conceptos difíciles.

Lo que Euclides demuestra exactamente es que, dado un conjunto finito de números primos, siempre podremos encontrar un número primo que no pertenece a dicho conjunto.

Veamos la prueba y luego comentamos las implicaciones, es una prueba que amalgama perfectamente simplicidad, belleza y contundencia.

DEMOSTRACION

Primero Euclides asumió que la lista de números primos es finita .

Imaginemos una lista que contiene (todos) los primos: P₁, P₂, P₃, ... P_n. Entonces se puede generar otro número Q (mucho mayor) tal que:

Q=(P₁ x P₂ x P₃ x ... x P_n) + 1

Este nuevo número Q puede ser primo o no. Si es primo, ya tenemos un nuevo primo que no pertenece a la lista original, y por tanto esa lista no era completa. En el caso de que Q no sea primo, forzosamente tendrá que ser divisible por algún número primo que no puede ser uno de los de la lista, ya que al dividir Q por cualquiera de los primos de la lista siempre obtendremos 1 como resto. Por lo tanto, tiene que existir otro primo P_n+1

En cualquiera de los dos casos hemos encontrado un número primo que NO estaba en la lista original.

La consecuencia de todo esto es que no podemos tener un conjunto finito de primos que enbloge a todos ellos, y de esto se deduce la infinitud del conjunto de los números primos.

La demostración es directa, contundente y satisfactoria. No se necesita más, y cualquier otra demostración de este hecho no añadirá evidencia alguna a la infinitud de los primos, porque la demostración de Euclides (o cualquier otra alternativa) proporciona de una vez toda la evidencia necesaria. Aún así, seguiremos visitando demostraciones diferentes de este resultado, algunas sorprendentes. Lo haremos en próximos posts.

 

Coherencia interna.

Dedicado a mi amigo Pedro V. L. Por haberme proporcionado la fuente de inspiración de esta serie de posts. Una vez más, gracias.

Una de las cosas que más satisfacción produce en la matemática es la sensación de que las cosas encajan, que son "como debieran ser". El mundo de los objetos matemáticos es coherente consigo mismo, de una forma parecida a lo que lo es el mundo de los objetos reales. No se puede demostrar una cosa y a los meses demostrar lo contrario, porque entonces algo estará equivocado en alguna parte.

A muchos profanos les extrañará saber que una vez que un teorema ha sido demostrado sigue siendo válido e interesante (y muy bien visto)  intentar demostrarlo por otras vías. Estas nuevas vías, al contrario de lo que sucede en el quehacer típico científico, no añaden certidumbre al resultado: un teorema bien demostrado es para siempre (mucho más que cualquier diamante), y no existirá revolución ni cambio de paradigma que lo haga tambalear.

Sin embargo, se considera extraordinariamente meritorio redemostrar un teorema por una vía nueva. ¿Por qué?

La respuesta no es unívoca, y tiene mucho que ver con la verdadera intención de la matemática: llegar a los más íntimos porqués de las cosas.

Toda demostración es incontrovertible si está bien hecha, pero algunas poco nos dicen sobre los porqués de lo que demuestran, como la actual para el Teorema de los cuatro colores. Hablábamos de ello hace dos años cuando repasábamos las diversas formas de demostración matemática. Una demostración espantosamente fea como la relatada aporta toda la evidencia necesaria (si está bien hecha) de la solución: cuatro colores son suficientes para colorear cualquier mapa. Pero ¿a quién puñetas le importa el número?

¿Algo cambia en nuestro conocimiento de las cosas si son cuatro y no siete los colores necesarios? Pues si la demostración es una demostración por verificación bien poco va a cambiar en nosotros. Tenemos un dato más, eso es todo. Sin embargo, otra demostración puede ayudarnos a encontrar porqués más profundos, quizás insospechados. Incluso puede que tendamos puentes entre ramas aparentemente alejadas de la matemática, adentrándonos en temas que están conceptualmente muy distantes de los de partida.

En todo caso, la sensación general cuando esto se produce es de que "el edificio esta bastante bien construido", porque las cosas encajan.

Iniciamos esta nueva andadura de Tio Petros con un intento de demostrar por múltiples vías un resultado que sabemos cierto de antemano. Cada nueva demostración nos llevará a una parcela matemática diferente, de forma bastante sorprendente acabaremos en terrenos que no parecen tener conexión con el tema original. La afirmación a demostrar es conocida por todos y no aporta novedad alguna, de manera que todo el interés del asunto está, no en el resultado sino en la forma de demostrarlo.

Se trata de la afirmación de que el número de naturales primos es infinito. Y comenzaremos con la archiconocida pero no por ello menos impresionante y pulcra demostración de Euclides. Lo haremos en el siguiente post.

Iniciamos por tanto una nueva etapa en TioPetros. Espero que les guste.

Continua aquí.

Nunca olvidaremos.

Mantendremos la memoria.

Los pueblos felices no tienen historia, pero el nuestro no es un pueblo feliz.

 

 

 

 

¿Quién puede nombrar el mayor número? (8/8)

Termina aquí la serie de ocho post dedicados a la traducción que Jorge Alonso ha realizado para este blog del trabajo de  Scott Aaronson, 1999  con permiso expreso del autor . Espero que les haya gustado tanto como a mi. Muchas gracias, Jorge.

Viene de aquí

Así que aquí estamos, en la frontera del conocimiento de los grandes números. Como se supone que el discípulo de Euclides preguntó, "¿para qué sirve todo esto?" Hemos visto que el progreso en sistemas notacionales para grandes números es un espejo del progreso en reinos más amplios: matemáticas, lógica, informática. Y todavía, aunque un espejo refleja la realidad, no necesariamente la influencia. Incluso dentro de las matemáticas, los grandes números son a menudo considerados trivialidades, su estudio un entretenimiento ocioso sin implicaciones más amplias. Quiero argumentar una visión contraria: que el entendimiento de los grandes números es una clave para entender el mundo.

Imagina intentar explicar la máquina de Turing a Arquímedes. El genio de Siracusa escucha pacientemente como discutes sobre la cinta de papiro extendiéndose infinitamente en ambas direcciones, los pasos, estados, y entradas y salidas de secuencias. Por fin explota.

"¡Tonterías!" declara (o el antiguo equivalente griego). "Todo lo que me das es una elaborada definición, sin ningún valor fuera de sí misma."

¿Cómo responder? Arquímedes nunca ha oído hablar de los ordenadores, esos quisquillosos dispositivos que, veintitrés siglos después, llevan a cabo los asuntos del mundo. Así que no puedes reclamar aplicaciones prácticas. Ni puedes apelar a Hilbert y al programa de formalismo, ya que Arquímedes no ha oído hablar de ambos. Pero entonces caes en la cuenta: la sucesión del castor atareado. Defines la secuencia para Arquímedes, convenciéndolo que B(1000) es más que 10⁶³ granos de arena llenando el universo, más incluso que 10⁶³ elevado a su propia potencia 10⁶³ veces. Le desafías a nombrar un número mayor sin invocar las máquinas de Turing o algún equivalente. Y así como él pondera este desafío, el poder del concepto de la máquina de Turing le ilumina. Aunque su intuición nunca podría aprehender los números del castor atareado, su razón lo compele a reconocer su inmensidad. Los grandes números tienen una forma de imbuir las nociones abstractas de realidad.

En verdad, uno podría definir la ciencia como el esfuerzo de la razón para compensar nuestra incapacidad para percibir grandes números. Si pudiésemos correr a 280 000 000 metros por segundo, no habría necesidad para una teoría especial de la relatividad: sería obvio para cualquiera que cuanto más rápido fuésemos, más pesados y achaparrados nos volveríamos, y más rápido pasa el tiempo en el resto del mundo. Si pudiésemos vivir durante 70 000 000 de años, no habría ninguna teoría de la evolución, y ciertamente ningún creacionismo: podríamos mirar la especiación y la adaptación con nuestros ojos, en lugar de reconstruir esmeradamente los eventos a partir de fósiles y ADN. Si pudiésemos hornear pan a 20 000 000 grados Kelvin, la fusión nuclear no sería el dominio esotérico de físicos sino el conocimiento familiar ordinario. Pero no podemos hacer ninguna de esas cosas, así que tenemos ciencia, para deducir sobre la gargantúa que nosotros, con nuestras facultades infinitesimales, jamás sentiremos. Si la gente teme a los grandes números, ¿es una sorpresa que también teman a la ciencia y giren al solaz de la confortable pequeñez del misticismo?

Pero ¿teme la gente a los grandes números? Ciertamente sí. He encontrado gente que no sabe la diferencia entre millón y mil millones (*), y no les preocupa. Jugamos una lotería con `¡seis formas de ganar!’, pasando por alto las veinte millones de formas de perder. Bostezamos a seis mil millones de toneladas de dióxido de carbono soltado en la atmósfera cada año, y hablamos de `desarrollo sostenible’ en las mandíbulas del crecimiento exponencial. Tales casos, me parece, transcienden la ignorancia aritmética y representan la poca disposición básica de agarrar lo inmenso.

Entonces ¿de dónde viene el encogerse de miedo ante los grandes números? ¿Tiene un origen biológico? En 1999, un grupo guiado por el neuropsicólogo Stanislas Dehaene reportó evidencia en Science de que dos sistemas separados del cerebro contribuyen al pensamiento matemático. El grupo entrenó a bilingües ruso-inglés en resolver un conjunto de problemas, incluyendo suma de dos dígitos, suma en base ocho, raíces cúbicas y logaritmos. Algunos sujetos fueron entrenados en ruso, otros en inglés. Cuando pidieron entonces a los sujetos resolver problemas aproximadamente (elegir la más próxima de dos estimaciones) lo hicieron igualmente bien en ambos lenguajes. Pero cuando les pidieron resolver problemas exactamente, lo hicieron mejor en el lenguaje de su entrenamiento. Lo que es más, las imágenes cerebrales mostraron que los lóbulos parietales de los sujetos, implicados en el razonamiento espacial, fueron más activos durante los problemas de cálculo aproximado; mientras que los lóbulos frontal inferior izquierdos, implicados en el razonamiento verbal, fueron más activos durante los problemas de cálculo exacto. Estudios de pacientes con lesiones cerebrales dibujan el mismo cuadro: aquellos con lesiones parietales algunas veces no pueden decidir si 9 está más próximo a 10 o a 5, pero recuerdan la tabla de multiplicación; mientras que aquellos con lesiones en el hemisferio izquierdo algunas veces no pueden decidir si 2+2 es 3 o 4, pero saben que la respuesta está más cerca de 3 que de 9. Dehaene et al. conjeturan que los humanos representamos los números de dos formas. Para cálculo aproximado usamos una `línea numérica mental’, que evolucionó hace mucho tiempo y que probablemente compartimos con otros animales. Pero para el cómputo exacto usamos símbolos numéricos, que evolucionaron recientemente y que, siendo dependientes del lenguaje, son únicos en los humanos. Esta hipótesis explica aseadamente los resultados del experimento: la razón de los sujetos se desempeñen mejor en el lenguaje de su entrenamiento para el cálculo pero no para problemas de aproximación, ya que lo primero invoca al lóbulo de orientación verbal frontal inferior izquierdo, y lo segundo al lóbulo parietal de orientación espacial.

Si la hipótesis de Dehaene et al. es correcta, entonces ¿qué representación utilizamos para los grandes números? Ciertamente la simbólica; para nadie la línea numérica mental puede ser larga suficiente para contener 9^{9^9}, 5 pentado a 5, o B(1000). Y aquí, sospecho, está el problema. Cuando pensamos sobre 3, 4 o 7, estamos guiados por nuestra intuición espacial, afilada en millones de años de percibir 3 gacelas, 4 compañeros o 7 miembros de un clan hostil. Pero cuando pensamos sobre B(1000), sólo contamos con el lenguaje, esa evolución neófita. Los caminos neurales usuales para representar números llevan a un callejón sin salida. Y esto, quizá, es por lo que la gente está temerosa de los grandes números.

¿Podría una intervención temprana mitigar nuestra fobia a los grandes números? ¿Qué pasaría si los profesores de matemáticas de segundo grado tomasen un hiato de una hora de su aburridas tareas para preguntar a sus estudiantes "cómo nombrarías un número muy, pero que muy grande"? Y entonces les contaría sobre los exponenciales y exponenciales apilados, la tretración y la sucesión de Ackermann, y quizá incluso los castores atareados: una cornucopia de números más vasta que cualquiera que ellos jamás concibieron, e ideas ensanchando los límites de su imaginación.

¿Quién puede nombrar el mayor número? Quienquiera que tenga el paradigma más profundo. ¿Estás listo? Prepárate. Ya.

(*) Entre million y billion en el original.

¿Quién puede nombrar el mayor número? (7/8)

Viene de aquí 

Podrías preguntarte porqué no podemos transcender el desfile completo de paradigmas, y nombrar números mediante un sistema que los abarque y aventaje a todos ellos. Supón que escribes lo siguiente en el desafío del mayor número:

El mayor número entero nombrable con 1000 letras.

Sin duda este número existe. Usando 1000 letras, podemos nombrar sólo una cantidad finita de números, y entre esos números tiene que haber un mayor. Y todavía no hemos hecho referencia a cómo se nombra el número. El texto podría invocar los números de Ackermann, o del castor atareado, o castores atareados de mayor nivel, o incluso un concepto todavía más radical que nadie pensó aún. Así que a menos que tu oponente utilice el mismo truco, le hemos dado una paliza. ¡Qué idea más brillante! ¿Porqué no lo pensamos antes?

Desafortunadamente esto no funciona. También podríamos haber escrito:

Uno más el mayor número entero nombrable con 1000 letras.

Este número necesita al menos 1001 letras para nombrarlo. ¡Pero lo hemos nombrado con sólo 47 letras! Como una serpiente que se traga a sí misma por entero, nuestro colosal número se disuelve en un tumulto de contradicción. ¿Qué queda?

La paradoja que acabo de describir fue primero publicada por Bertrand Russell, que la atribuyó a un bibliotecario llamado G. G. Berry. La paradoja de Berry surge no de las matemáticas, sino de la ambigüedad inherente del lenguaje. No hay manera segura de convertir una frase en el número que nombra (o para decidir si de todas formas nombra a un número), lo cual es por lo que yo invoqué a un "razonable matemático moderno" en las reglas del desafío del mayor número. Para burlar la paradoja de Berry, necesitamos nombrar números utilizando un sistema notacional matemático preciso, tal como las máquinas de Turing ...que es exactamente la idea detrás de la sucesión de los castores atareados. Así que en resumen, no hay ningún truco astuto del lenguaje con el que aventajar a Arquímes, Ackermann, Turing y Rado, ninguna escalera regia de grandes números.

También podrías preguntar porqué no podemos utilizar el infinito en el desafío. La respuesta es: por la misma razón por la que no podemos utilizar un coche-cohete en una carrera de bicicletas. El infinito es fascinante y elegante, pero no es un número entero. Tampoco podemos `restar al infinito’ para producir un número entero. Infinito menos 17 todavía es infinito, mientras que infinito menos infinito es indefinido: puede ser 0, 38, o incluso infinito de nuevo. Realmente debería hablar de infinitos, en plural. Durante el siglo diecinueve tardío, Georg Cantor probó que hay diferentes niveles de infinito: por ejemplo, el infinito de los puntos de una línea es mayor que el infinito de los números enteros. Lo que es más, así como no hay el número más grande, tampoco hay el infinito más grande. Pero la búsqueda de grandes infinitos es más abstrusa que la búsqueda de grandes números. Y envuelve, no una sucesión de paradigmas, sino esencialmente uno: el de Cantor

Quién puede nombrar el mayor número? (6/8)

Viene de aquí

Pero ¿y si tu amigo también conoce las máquinas de Turing? ¿Hay un sistema notacional para grandes números más poderosos incluso que los castores atareados?

Supón que podemos dotar a una máquina de Turing con la habilidad mágica de resolver el problema de la detención. ¿Qué podríamos conseguir? Tendríamos una `super-máquina de Turing’: una con habilidades más allá de cualquier máquina ordinaria. Pero ahora, ¿cómo de difícil es decidir si una super-máquina se detiene? Hmm. Produce que incluso las super-máquinas no pueden resolver su `super-problema de la detención’, por la misma razón que las máquinas ordinarias no pueden resolver el problema ordinario de la detención. Para resolver el problema de la detención para las super-máquinas, necesitamos una máquina incluso más poderosa: una `super-hiper-máquina’. Y para resolver el problema de la detención para la super-hiper-máquina, necesitamos una `super-hiper-mega-máquina’. Y así sucesivamente sin fin. Esta jerarquía infinita fue formalizada por el lógico Stephen Kleene en 1943 (aunque él no usó el término `super-hiper-mega’).

Imagina una novela, la cual está encajada en una novela mayor, la cual está encajada en una novela incluso mayor, y así hasta el infinito. Dentro de cada novela, los personajes pueden debatir los méritos literarios de cualquier subnovela. Pero, por analogía con las categorías de máquinas que no pueden analizarse a sí mismas, los personajes nunca podrían criticar la novela en la que ellos mismos están. (Esto, pienso, hace mofa de nuestra experiencia ordinaria de las novelas.) Para entender completamente algo de la realidad, necesitamos salir de esa realidad. Esa es la esencia de la jerarquía de Kleene: que para resolver el problema de la detención para alguna categoría de máquinas, todavía necesitamos una categoría más poderosa de máquinas.

Y no hay escapatoria. Supón una máquina de Turing con una habilidad mágica de resolver el problema de la detención, y el super-problema de la detención, y el super-hiper-problema de la detención, y el super-hiper-mega-problema de la detención, y así sucesivamente sin fin. ¿Sin duda ésta será la reina de las máquinas de Turing? No realmente. Tan pronto como queramos decidir si una `reina de las máquinas de Turing’ para, necesitaremos una máquina todavía más poderosa: una `emperatriz de las máquinas de Turing’. Y la jerarquía de Kleene continúa.

Pero ¿cómo es esto relevante para los grandes números? Bueno, cada nivel de la jerarquía de Kleene genera una sucesión de castores atareados de crecimiento más rápido que todos los niveles previos. Verdaderamente, cada nivel de la sucesión crece tan rápidamente que sólo puede ser computada por una de mayor nivel. Por ejemplo, define B₂(n) como el máximo número de pasos que una super-máquina con n reglas puede hacer antes de parar. Si esta super-sucesión de castores atareados fuese computable por super-máquinas, entonces esas máquinas podrían resolver el super-problema de la detención. Así que los super-números de los castores atareados crecen demasiado rápidamente para ser computados, incluso si pudiésemos computar los números ordinarios de los castores atareados.

Podrías pensar que ahora, en el desafío del mayor número, podrías borrar del mapa incluso a un oponente que usase la sucesión del castor atareado escribiendo algo como esto:

B₂(11111)

Pero no realmente. El problema es que nunca he visto esos “castores atareados de mayor nivel” definidos en ningún lado, probablemente porque, para la gente que conoce la teoría de computabilidad, son una bastante obvia extensión de los números ordinarios del castor atareado. Así que nuestro razonable matemático moderno no sabría qué número estás nombrando. Si quieres usar los números del castor atareado de mayor nivel en el desafío del mayor número, aquí está lo que sugiero. Primero, publica un artículo formalizando el concepto en algún periódico oscuro de bajo prestigio. Entonces, durante el desafío, cita el artículo en tu tarjeta.

Para exceder los castores atareados de mayor nivel, necesitamos presumiblemente algún modelo informático superior incluso a las máquinas de Turing. No puedo imaginar a qué se parecería ese modelo. Todavía de algún modo dudo que la historia de los sistemas notacionales para los grandes números esté acabada. Quizá algún día los humanos seamos capaces de nombrar concisamente números que hagan parecer al castor atareado 100 tan pueril y divertidamente pequeño como nuestro ochenta y tres del noble. O si jamás nombramos tales números, quizás otras civilizaciones lo hagan. ¿Está en marcha un desafío del mayor número por toda la galaxia?

Continua aquí

¿Quién puede nombrar el mayor número? (5/8)

Viene de aquí

“Muy bien”, dices (o quizá dices “no muy bien”). “¿Pero qué tiene todo esto que ver con los grandes números?” ¡Ajá! La conexión no fue publicada hasta mayo de 1962. Entonces, en el Bell System Technical Journal, acurrucado entre artículos dispuestos pragmáticamente sobre “Estructuras multipuerto” y “Sellos de presión dirigidos por ondas”, aparecía el modestamente titulado “Sobre funciones no computables” por Tibor Rado. En este artículo, Rado presentaba los mayores números que nadie jamás había imaginado.

Su idea era simple. Como nosotros clasificamos las palabras según cuantas letras contengan, podemos clasificar las máquinas de Turing mediante cuántas reglas tienen en su cabezal. Algunas máquinas tienen sólo una regla, otras tienen dos reglas, todavía otras tienen tres reglas, y así sucesivamente. Pero por cada número entero fijo n, así como hay sólo un número finito de palabras con n letras, así también hay sólo un número finito de máquinas con n reglas. Entre estas máquinas, algunas pararán y otras funcionarán por siempre cuando comiencen con una cinta en blanco. De las que paran, pregunta Rado, ¿cuál es el máximo número de pasos que cualquier máquina hace antes de que pare? (Realmente, Rado preguntaba principalmente sobre el máximo número de símbolos que cualquier máquina puede escribir en la cinta antes de pararse. Pero el máximo número de pasos, que Rado llamaba S(n), tiene la mismas propiedades básicas y es más fácil razonar sobre él.)

Rado llamó a este máximo el n-ésimo número del “castor atareado”. (Ah sí, los tempranos 1960 eran una edad más inocente.) Él visualizó cada máquina de Turing como un castor bullendo ocupadamente a lo largo de la cinta, escribiendo y borrando símbolos. El desafío, entonces, es encontrar el castor más ocupado con exactamente n reglas, aunque no uno infinitamente ocupado. Podemos interpretar este desafío como la búsqueda del “más complicado” programa de ordenador de n bits de tamaño: el que hace la mayor cantidad de material, pero no una infinita cantidad.

Ahora, supón que conocemos el n-ésimo número del castor ocupado, que llamaremos B(n). Entonces podríamos decidir si cualquier máquina de Turing con n reglas se para partiendo una cinta en blanco. Sólo tenemos que ejecutar la máquina: si se para, bien; pero si no se para en B(n) pasos, entonces sabemos que nunca se parará, puesto que B(n) es el máximo número de pasos que podría hacer antes de parar. De igual manera, si sabes que todos los mortales murieron antes de cumplir 200 años, entonces si Sally vivió para cumplir 200, podrías concluir que Sally era inmortal. Así que ninguna máquina de Turing puede listar los números del castor atareado... porque si pudiese, podría resolver el problema de la detención, que ya sabemos que es imposible.

Pero hay un hecho curioso. Supón que podemos nombrar un número mayor que el n-ésimo castor atareado B(n). Llamémosle a este número d de dique, ya que como un dique de castor, es un techo para el castor atareado que está debajo. Con d en mano, computar el propio B(n) se vuelve fácil: sólo necesitamos simular todas las máquinas de Turing con n reglas. Las que no se hayan parado en d pasos (las que quiebran el tejado del dique) nunca pararán. Así que podemos listar exactamente qué máquinas paran, y entre ellas, el máximo número de pasos que cualquier máquina emplea antes de parar es B(n).

¿Conclusión? La secuencia de números del castor atareado, B(1), B(2), y sucesivos, crece más rápido que cualquier secuencia computable. Más rápido que los exponenciales, los exponenciales apilados, y la sucesión de Ackermann, ya que la nombras. Porque si una máquina de Turing pudiese computar una sucesión que crece más rápido que el castor atareado, entonces podríamos usar esa secuencia para obtener las d, el dique del castor. Y con esas d, se podría listar los números del castor atareado, lo cual (¿te suena familiar?) ya sabemos que es imposible. La sucesión del castor atareado es no computable, exclusivamente porque crece estupendamente rápido ...demasiado rápido para que cualquier ordenador pueda seguir con ella, incluso en principio.

Esto significa que ningún programa de ordenador puede listar todos los castores atareados uno por uno. Esto no significa que castores atareados específicos necesiten permanecer eternamente desconocidos. Y de hecho, fijarlos ha sido un pasatiempo de la informática desde que Rado publicó entonces su artículo. Es fácil verificar que B(1), el primer número del castor atareado, es 1. Eso es porque si una máquina de Turing de una regla no para después del primer paso, continuará moviéndose a lo largo de la cinta interminablemente. No hay lugar para cualquier otro comportamiento más complejo. Con dos reglas podemos hacer más, y un pequeño trabajo determinó que B(2) es 6. Seis pasos. ¿Y sobre el tercer castor atareado? En 1965 Rado, junto con Shen Lin, provó que B(3) es 21. La tarea fue ardua, requiriendo análisis humano de muchas máquinas para probar que no paraban... ya que, recuérdese, no hay algoritmo para listar los número del castor atareado. Después, en 1983, Allan Brady probó que B(4) es 107. ¿Poco impresionante hasta ahora? Bueno, como con la sucesión de Ackermann, no nos dejemos engañar por los primeros números.

En 1984, A. K. Dewdney, dedicó una columna de Scientific American a los castores atareados, los cuales inspiraron al matemático aficionado George Uhing a construir un dispositivo especial para simular las máquinas de Turing. El dispositivo, que le costó a Uhing menos de 100$, encontró una máquina de cinco reglas que ejecutaba 2 133 492 de pasos antes de parar... estableciendo que B(5) debe ser al menos tan grande. Entonces, en 1989, Heiner Marxen y Jürgen Buntrock descubrieron que B(5) es al menos 47 176 870. Hasta hoy, B(5) no ha sido fijado con precisión, y podría resultar ser todavía mucho mayor. Para B(6), Marxen y Buntrock establecieron otro récord en 1997 probando que es al menos 8 690 333 381 690 951. Una conclusión formidable, todavía Marxen, Buntrock, y los otros cazadores de castores atareados meramente vadean en las orillas de lo desconocido. La humanidad nunca podrá saber el valor de B(6) con certeza, dejemos en paz a B(7) o cualquier otro número mayor de la sucesión.

Verdaderamente, ya los primeros competidores de cinco y seis reglas nos eluden: no podemos explicar como `trabajan’ en términos humanos. Si la creatividad imbuye su diseño, no es porque los humanos la pusieran ahí. Una manera de entender esto es que incluso pequeñas máquinas de Turing pueden codificar profundos problemas matemáticos. Tomemos la conjetura de Goldbach, de que todo número par mayor o igual a 4 es la suma de dos números primos: 10=7+3, 18=13+5. La conjetura ha resistido demostración desde 1742. Todavía podríamos diseñar una máquina de Turing con, oh, digamos 100 reglas, que prueben cada número par para ver si es una suma de dos primos, y parase sólo si encuentra un contraejemplo a la conjetura. Entonces conociendo B(100), podríamos en principio ejecutar este máquina durante B(100) pasos, viendo si para, y así resolver la conjetura de Goldbach. No necesitamos aventurarnos lejos en la sucesión para entrar en la guarida del basilisco.

Pero como Rado acentúa, incluso si no podemos listar los números del castor atareado, ellos están perfectamente bien definidos matemáticamente. Si alguna vez retas a un amigo al desafío del mayor número, te sugiero que escribas algo como esto:

B(11111), suc. castor atareado, 1, 6, 21, etc.

Si tu amigo no conoce las máquinas de Turing o similares, pero sólo conoce, digamos, los números de Ackermann, entonces tú ganas el desafío. Tu incluso ganarías si concedes a tu amigo un handicap, y le permites todo el tiempo de existencia del universo para escribir su número. La clave al desafío del mayor número es un potente paradigma, y la teoría de Turing de computación es en verdad potente.

¿Quién puede nombrar el mayor número? (4/8)

Viene de aquí

Los números de Ackermann son bastante grandes, pero no son todavía lo suficientemente grandes. La búsqueda por todavía mayores números nos lleva de vuelta a los formalismos. Después de que Ackermann demostrase que `recursiva primitiva’ no es lo que queremos decir con `computable’, la pregunta todavía permanece: ¿Qué queremos decir con `computable’? En 1936, Alonzo Church y Alan Turing respondieron independientemente esta pregunta. Mientras Church respondió utilizando un formalismo lógico llamado el cálculo lambda, Turing respondió utilizando una máquina de cómputo idealizada (la máquina de Turing) que, en esencia, es equivalente a cada Compaq, Dell, Macintosh y Cray del mundo moderno. El artículo de Turing que describía su máquina, "Sobre los números computables", es debidamente celebrado como el documento fundador de la informática.

"Computar," dice Turing,

es hecho normalmente escribiendo ciertos símbolos en un papel. Podemos suponer este papel dividido en cuadrados como un libro infantil de aritmética. En la aritmética elemental el carácter bidimensional del papel es algunas veces útil. Pero tal uso es siempre evitable, y pienso que se estará de acuerdo en que el carácter bidimensional del papel no es indispensable en la computación. Asumo entonces que la computación se lleva a cabo en un papel unidimensional, en una cinta dividida en cuadrados."

Turing continúa explicando su máquina utilizando ingeniosos razonamientos desde los primeros principios. La cinta, dice Turing, se extiendo infinitamente en ambas direcciones, para que la máquina teórica no esté restringida por limitaciones físicas de recursos. Además, hay un símbolo escrito en cada cuadrado de la cinta, como el `1’ y el `0’ en la memoria de los ordenadores modernos. Pero ¿cómo son manipulados los símbolos? Bueno, hay un `cabezal’ moviéndose adelante y atrás a lo largo de la cinta, examinando un cuadrado de cada vez, escribiendo y borrando símbolos de acuerdo a reglas definidas. Las reglas están en el programa del cabezal: cámbialos, y cambiarás lo que hace el cabezal.

La augusta perspicacia de Turing fue que podemos programar el cabezal para llevar a cabo cualquier computación. Las máquinas de Turing pueden sumar, multiplicar, extraer raíces cúbicas, ordenar, buscar, comprobar la ortografía, analizar, jugar al tres en raya, listar la sucesión de Ackermann... Si representamos la entrada de datos por el teclado, la salida de datos por la pantalla, y demás como símbolos en la cinta, incluso podríamos ejecutar Windows en una máquina de Turing. Pero hay un problema. Dispón un cabezal sobre una secuencia de símbolos, y eventualmente podría parar, o podría ejecutarse para siempre... como el legendario programador que se queda atrancado en la ducha porque las instrucciones del bote de champú dicen "enjabonar, enjuagar, repetir". Si la máquina va a funcionar por siempre, estaría bien saberlo de antemano, para que no gastemos una eternidad esperando que acabe. Pero ¿cómo podemos determinar, en una cantidad de tiempo finita, si algo va a continuar indefinidamente? Si apuestas con un amigo que tu reloj nunca parará de hacer tic-tac, ¿cuándo declararás victoria? Pero quizá haya algún ingenioso programa que pueda examinar a otros programas y decirnos, infaliblemente, si pararán alguna vez de funcionar. No lo habíamos pensado todavía.

No hay. Turing probó que este problema, llamado el problema de la detención, es irresoluble por las máquinas de Turing. La demostración es un bello ejemplo de autoreferencia. Formaliza un viejo argumento sobre por qué nunca puedes tener una introspección perfecta: porque si pudieses, entonces podrías determinar qué estarías haciendo diez segundos después, y entonces hacer otra cosa distinta. Turing imaginó que hay una máquina especial que podría resolver el problema de la detención. Entonces mostró cómo podemos tener a esta máquina analizándose a sí misma, de tal forma que tiene que parar si se ejecutaría para siempre, y se ejecutaría para siempre si se para. Como un sabueso que finalmente se coge su cola y se devora a sí mismo, la mítica máquina se desvanece en una furia de contradicción. (Que es la clase de cosas que nunca dirías en un artículo de investigación.)

Continua aquí  

¿Quién puede nombrar el mayor número? (3/8)

Viene de aquí 

 

Los exponenciales son familiares, relevantes, íntimamente conectados con el mundo físico y los miedos y esperanzas humanos. Usando el sistema notacional que discutiré a continuación, podremos nombrar concisamente números que hacen insignificantes por comparación a los exponenciales, que subjetivamente hablando exceden 9^{9^9^9} tanto como éste excede al 9. Pero estos nuevos sistemas podrían pareces más abstrusos que los exponenciales. En su ensayo Sobre el entumecimiento numérico, Douglas Hofstadter lleva a sus lectores al precipicio de esos sistemas, pero entonces asegura que:

Si continuásemos nuestra discusión sólo un milisegundo más, nos encontraríamos justo en medio de la teoría de funciones recursivas y complejidad algorítmica, y eso sería demasiado abstracto. Así que dejemos el tema aquí mismo.

Pero dejar el tema es abandonar, no sólo el desafío del mayor número, sino cualquier esperanza de entender cómo los más fuertes paradigmas llevan a los más vastos números. Y así llegamos al temprano siglo veinte, cuando una escuela de matemáticos llamados formalistas buscan colocar toda la matemática sobre rigurosas bases axiomáticas. La pregunta clave para los formalistas fue qué significa la palabra `computable’. Es decir, ¿cómo podemos decir si una secuencia de números puede ser listada por un procedimiento mecánico definido? Algunos matemáticos pensaban que `computable’ coincidía con una noción técnica llamada `recursiva primitiva’. Pero en 1928 Wilhelm Ackermann los refutó construyendo una sucesión de números que es claramente computable, aunque crece demasiado rápidamente para ser una recursiva primitiva.

La idea de Ackermann fue crear una procesión sin fin de operaciones aritméticas, cada una más potente que la anterior. Primero viene la suma. Segundo viene la multiplicación, que podemos pensarla como una suma repetida: por ejemplo, 5×3 significa 5 sumado a sí mismo 3 veces, o 5+5+5=15. Tercero viene la potenciación, que podemos pensarla como una multiplicación repetida. Cuarto viene... ¿qué? Bueno, tenemos que inventar una rara operación nueva, para la potenciación repetida. El matemático Rudy Rucker la llama `tetración’. Por ejemplo, `5 tetrado a 3’ significa 5 elevado a su propia potencia 3 veces, o 5^{5^5}, un número con 2185 dígitos. Podemos continuar. Quinto llega la tetración repetida: ¿podemos llamarla `pentación’? Sexto llega la pentación repetida: ¿`hexación’? Las operaciones continúan infinitamente, con cada una soportada por su predecesora para asomarse incluso más alta hacia el firmamento de los grandes números.

Si cada operación fuese un sabor dulce, entonces la sucesión de Ackermann sería el catálogo de muestras, mezclando un número de cada sabor. Primero en la secuencia está 1+1, o (no contengas la respiración) 2. Segundo está 2×2, o 4. Tercero es 3 elevado a la tercera potencia, o 27. ¡Eh, estos números no son tan grandes!

Cuarto es 4 tetrado a 4, o 4^{4^4^4}, que tiene 10¹⁵⁴ dígitos. Si estás planeando escribir este número, mejor que empieces ahora. Quinto es 5 pentado a 5, o 5^{5^...^5} con `5 tetrado a 4’ numerales en la pila. Este número es demasiado colosal para describirlo en cualquier término ordinario. Y los números se vuelven mucho mayores a partir de aquí.

Esgrimiendo la sucesión de Ackermann, podemos dar palizas a oponentes sin estudios en el desafío de los mayores números. Pero necesitamos ser cuidadosos, dado que hay varias definiciones de la sucesión de Ackermann, no todas idénticas. Bajo el límite de tiempo de quince segundos, aquí está lo que yo podría escribir para evitar la ambigüedad:

A(111), suc. Ackermann, A(1)=1+1, A(2)=2x2, A(3)=3^3, etc.

Profunda como parece, la sucesión de Ackermann tiene algunas aplicaciones. Un problema en un área llamada la teoría de Ramsey pregunta por la mínima dimensión de un hipercubo que satisface una cierta propiedad. La dimensión correcta se piensa que es 6, pero la más baja dimensión que nadie ha sido capaz de probar es tan enorme que sólo puede ser expresada utilizando la misma `aritmética rara’ que fundamenta la sucesión de Ackermann. En verdad, el Libro Guinness de los récords una vez listó esta dimensión como el mayor número jamás usado en una demostración matemática. (Otro contendiente para el título fue una vez el número de Skewes, sobre 10<sup>10^10^10^3</sup>, que surge en el estudio de cómo los números primos están distribuidos. El famoso matemático G. H. Hardy dijo sarcásticamente que el número de Skewes era "el mayor número que jamás ha servido para algún propósito definido en matemáticas".) Lo que es más, la cabalgata vivamente ascendente de Ackermann hace un cameo ocasional en la ciencia computacional. Por ejemplo, en el análisis de una estructura de datos llamada `Union-Find’, un término se multiplica por la inversa de la sucesión de Ackermann, significando, para cada número entero x, el primer número n tal que el n-ésimo número de Ackermann es mayor que x. La inversa crece tan lentamente como la sucesión de Ackermann original crece rápidamente; para todos los propósitos prácticos, la inversa es como máximo 4.

Continua aquí

¿Quién puede nombrar el mayor número? (2/8)

Viene de aquí 

 

Pero la arena no escapa de ser contada, como Arquímedes reconoció en el tercer siglo A.C. Así es como él empezó El contador de arena, una especie de artículo de ciencia popular enviado al rey de Siracusa:

Hay algunos... que piensan que el número de arenas es infinito en multitud... y hay algunos otros que, sin considerarlo infinito, todavía piensan que ningún número ha sido nombrado que sea suficientemente grande para exceder su multitud... Pero yo intentaré mostraros [números que] exceden no sólo el número de la masa de arena igual en magnitud a la Tierra... sino también en una masa igual en magnitud al universo.

Este Arquímedes procedió a hacer, esencialmente mediante el uso del antiguo término griego miríada, que significa diez mil, la base de los exponenciales. Adoptando el presciente modelo cosmológico de Aristarco, en el cual la "esfera de las estrellas fijas" es inmensamente mayor que la esfera en la que la Tierra gira alrededor del sol, Arquímedes obtuvo un límite superior de 10⁶³ del número de granos de arena necesarios para llenar el universo. (Supuestamente 10⁶³ es el mayor número con un nombre lexicográfico estándar americano: vigintillion (*). Pero el serio vigintillion tiene que velar para no ser usurpado por el más caprichosamente nombrado googol, o 10¹⁰⁰, y googolplex, o 10^{10^100}.) Vasto es, por supuesto, pero 10⁶³ no es elevado a los altares del mayor número de todos los tiempos. Seis siglos después, Diofanto desarrolló una notación más simple para los exponenciales, permitiéndole sobrepasar 10^{10^10^10^10}. Entonces, en la edad media, el alzamiento de los numerales árabes y el posicionamiento decimal hicieron fácil apilar exponenciales todavía mayores. Pero el paradigma de Arquímedes para expresar grandes números no fue fundamentalmente superado hasta el siglo veinte. E incluso hoy, los exponenciales dominan la discusión popular de lo inmenso.

 

Considera, por ejemplo, la a menudo repetida leyenda del gran visir de Persia que inventó el ajedrez. El rey, como dice la leyenda, quedó encantado con el nuevo juego, e invitó al visir a pedir su propia recompensa. El visir replicó que, siendo un hombre modesto, sólo deseaba un grano de trigo por el primer cuadro del tablero, dos granos por el segundo, cuatro por el tercero, y así sucesivamente, con dos veces más granos por cuadro que el anterior. El anumérico rey consintió, sin darse cuenta que el número total de granos por todas las 64 casillas sería 2⁶⁴-1, or 18,4 trillones... equivalente a la actual producción mundial de trigo durante 150 años.

 

Apropiadamente, es este crecimiento exponencial lo que hace al propio ajedrez tan difícil. Hay solamente sobre 35 elecciones lícitas en cada movimiento ajedrecístico, pero las elecciones se multiplican exponencialmente hasta producir sobre 10⁵⁰ posibles posiciones en el tablero... demasiados incluso para que un ordenador las busque exhaustivamente. Eso es por lo que se tardó hasta 1997 que un ordenador, Deep Blue, derrotase al campeón mundial humano de ajedrez. Y en el Go, que tiene un tablero de 19×19 y sobre 10¹⁵⁰ posibles posiciones, incluso un humano aficionado todavía puede derrotar los programas número uno del mundo. El crecimiento exponencial infecta los ordenadores también en otras guisas. El problema del viajero pregunta por la ruta más corta que conecte un conjunto de ciudades, dada la distancia entre cada par de ciudades. Lo irritante es que el número de rutas posibles crece exponencialmente según el número de ciudades. Cuando hay, digamos, un ciento de ciudades, hay sobre 10¹⁵⁸ rutas posibles, y, aunque son posibles varios atajos, ningún algoritmo computacional conocido es fundamentalmente mejor que probar una a una cada ruta. El problema del viajero pertenece a una clase llamada NP-completa, que incluye cientos de otros problemas de interés práctico. (NP representa el término técnico `tiempo polinomial no determinístico’.) Es sabido que si hay un algoritmo eficiente para cualquier problema NP-completo, entonces hay algoritmos eficientes para todos ellos. Aquí `eficiente’ significa usando una cantidad de tiempo proporcional al tamaño máximo del problema elevado a alguna potencia fija, por ejemplo, el número de ciudades al cubo. Sin embargo, se conjetura que no existe ningún algoritmo eficiente para los problemas NP-completos. La prueba de esta conjetura, llamada P≠NP, ha sido un gran problema irresuelto de la ciencia computacional durante treinta años.

 

Aunque los ordenadores probablemente nunca resolverán los problemas NP-completos eficientemente, hay más esperanza por otro grial de la ciencia computacional: la replicación de la inteligencia humana. El cerebro humano tiene aproximadamente cien mil millones de neuronas conectadas mediante cien billones de sinapsis. Y aunque la función de una neurona individual es sólo parcialmente entendida, se piensa que cada neurona despide impulsos eléctricos según reglas relativamente simples hasta mil veces por segundo. Así que lo que tenemos es un ordenador altamente interconectado capaz de quizá 10¹⁴ operaciones por segundo; en comparación, el más rápido superordenador paralelo del mundo, el 9200-Pentium Pro teraflops machine en Sandia National Labs, puede ejecutar 10¹² operaciones por segundo. Contrariamente a la creencia popular, la materia gris no sólo está cableada para la inteligencia: sobrepasa al silicio incluso en puro poder computacional. Pero es improbable que esto permanezca cierto durante mucho tiempo. La razón es la ley de Moore, que, en su formulación de 1990, expresa que la cantidad de información almacenable en un chip de silicio crece exponencialmente, doblándose aproximadamente una vez cada dos años. La ley de Moore finalmente quedará fuera de juego, cuando los componentes del microchip alcancen la escala atómica y la litografía convencional vacile. Pero radicales nuevas tecnologías, tales como ordenadores ópticos, ordenadores de ADN, o incluso ordenadores cuánticos, podrían concebiblemente usurpar el lugar del silicio. El crecimiento exponencial en la potencia computacional no puede continuar para siempre, pero podría durar lo suficiente para que los ordenadores (al menos en poder de procesamiento) sobrepasen al cerebro humano.

Para los pronosticadores de la inteligencia artificial, la ley de Moore es un glorioso heraldo del crecimiento exponencial. Pero los exponenciales también tienen su lado más sombrío. Recientemente la población humana pasó de los seis mil millones y se duplica cada cuarenta años aproximadamente. A esta razón exponencial, si una persona media pesa setenta kilos, entonces en el año 3750 la Tierra entera estará compuesta de carne humana. Pero antes de que inviertas en desodorantes, date cuenta de que la población parará de incrementarse mucho antes de esto ocurra, ya sea por hambrunas, epidemias, calentamiento global, extinciones en masa de especies, aire irrespirable, o, entrando en el reino de la especulación, control de natalidad. No es difícil comprender porqué el físico Albert Bartlett afirma que "la mayor limitación de la raza humana" es "nuestra incapacidad de entender la función exponencial". O porqué Carl Sagan nos aconseja "nunca subestimar una exponencial". En su libro Miles de millones, Sagan da otras deprimentes consecuencias del crecimiento exponencial. Al porcentaje inflacionario del cinco por ciento al año, un dólar valdría sólo 37 centavos después de veinte años. Si un núcleo de uranio emite dos neutrones, y ambos colisionan con otros dos núcleos de uranio, haciéndoles emitir dos neutrones, y así en adelante... bueno, ¿mencioné el holocausto nuclear como un posible fin del crecimiento poblacional?

(*) En inglés americano un m-illón, en vez de ser 10^6m, es 10^3m+3.

Sigue aquí

¿Quién puede nombrar el mayor número? (1/8)

Les presento una serie de unos ocho posts sobre un tema especialmente querido entre los amigos de las matemáticas, y varias veces mencionados en Tio Petros: el tema de los números grandes. El autor del texto es Scott Aaronson, 1999 y la traducción al castellano ha sido realizada con permiso expreso del autor por un habitual colaborador de Tio Petros: Jorge Alonso.

En un viejo chiste, dos nobles compiten en nombrar el mayor número. El primero, después de rumiar durante horas, proclamó triunfantemente “¡Ochenta y tres!”. El segundo, poderosamente impresionado, contestó “Tú ganas”. El desafío por el mayor número claramente no tiene sentido cuando los contendientes lo hacen por turnos. Pero ¿qué pasaría si los contendientes escribiesen sus números simultáneamente, ninguno conociendo el del otro? Para presentar una charla sobre “números grandes”, invité a dos voluntarios de la audiencia a intentar precisamente eso. Les dije las reglas:

Tenéis quince segundos. Utilizando la notación matemática normal, palabras inglesas, o ambas, nombrar un sólo número entero, no un infinito, en una tarjeta en blanco. Ser lo suficientemente precisos para que cualquier matemático moderno pueda determinar exactamente qué número habéis nombrado, consultando únicamente tu tarjeta y, si es necesario, la literatura publicada.

Así que los contendientes no pueden decir “el número de granos de arena en el Sahara”, porque la arena fluctúa hacia dentro y hacia fuera del Sahara con regularidad. Tampoco pueden decir “el número de mi oponente más uno”, o “el mayor número que nadie jamás pensó más uno”; de nuevo, están mal definidos, dado lo que nuestro razonable matemático tiene disponible. Dentro de las reglas, el contendiente que nombre el mayor número gana. ¿Estáis listos? Preparados. Ya. Los resultados de la contienda nunca son lo que yo esperaría.

Una vez, un chico de séptimo grado llenó su tarjeta con una cadena de sucesivos nueves. Como muchos otros principiantes de los grandes números, buscó maximizar su número poniendo un 9 en cada posición decimal. Si hubiera elegido el 1, más fácil de escribir que el curvado 9, su número podría haber sido millones de veces mayor. Sin embargo, todavía sería diezmado por la chica con la que se enfrentaba, que escribió una cadena de nueves seguida por un superíndice ⁹⁹⁹. ¡Ajá! Una potencia: un número multiplicado por sí mismo 999 veces. Dándome cuenta de su innovación, declaré la victoria de la chica sin preocuparme en contar los nueves de las tarjetas. E incluso el número de la chica podría haber sido mucho mayor todavía, si ella apilase el poderoso exponencial más de una vez. Coge 9^{9^9}, por ejemplo. Este behemot, igual a 9^{387 420 489}, tiene 369 693 100 dígitos. Por comparación, el número de partículas elementales en el universo observable tiene escasamente 85 dígitos, más o menos. Tres nueves, cuando se apilan exponencialmente, ya nos elevan incomprensiblemente más allá de toda la materia que podemos observar... en un factor de aproximadamente 10^{369 693 015}.

Notación decimal, potencias, exponenciales apilados: cada uno puede expresar los ilimitados grandes números, y en este sentido son todos ellos equivalentes. Pero los sistemas de notación difieren dramáticamente en los números que pueden expresar concisamente. Eso es lo que los quince segundos de tiempo límite ilustran. Lleva la misma cantidad de tiempo escribir 9999, 99⁹⁹ y 9^{9^9^9}... todavía el primer número es cotidiano, el segundo astronómico, y el tercero hiper-mega astronómico. La clave al desafío de los mayores números no una rápida escritura, sino más bien un potente paradigma para la captura concisa de la gargantúa. Tales paradigmas son rarezas históricas. Encontramos agitación en la antigüedad, otra agitación en el siglo veinte, y no mucho en medio. Pero cuando una nueva forma de expresar concisamente grandes números emerge, es a menudo como un subproducto de una revolución científica mayor: matemáticas sistematizadas, lógica formal, ciencia computacional.

Revoluciones importantes, como cualquier partidario de Kuhn puede decirte, sólo ocurren bajo las correctas condiciones sociales. Así, la historia de los grandes números es la historia del progreso humano. Y aquí yace un paralelismo con otra historia matemática. En su notable e infravalorado libro Una historia de π, Petr Beckmann argumenta que la razón entre la circunferencia y el diámetro es “un singular espejo de la historia del hombre”. En las raras sociedades donde la ciencia y la razón encontraron refugio (la temprana Atenas de Anaxágoras e Hippias, la Alejandría de Eratóstenes y Euclides, la Inglaterra del siglo diecisiete de Newton y Wallis) los matemáticos dieron tremendos pasos en el cálculo de π. En Roma y en la Europa medieval, por constraste, el conocimiento de π se estancó. Rudas aproximaciones como el 25/8 de los babilónicos y el 3 de la biblia se mantenían alternantes.

Pienso que este mismo patrón se aplica a los grandes números. La curiosidad y la franqueza llevan a la fascinación por los grandes números, y al boyante punto de vista de que ninguna cantidad, sea el número de estrellas en la galaxia o el número de manos posibles en el bridge, es demasiado inmensa para que la mente lo enumere. Recíprocamente, la ignorancia y la irracionalidad llevan al fatalismo respecto a los grandes números. La biblia, por ejemplo, se refiere veintiuna veces a la supuesta incontabilidad de la arena. Mira en génesis 32:13 “Sin embargo tú me dijiste: Yo te haré el bien y haré tu descendencia como la arena del mar, tan numerosa que no se puede contar.” O hebreos 11:12 “numerosa como las estrellas del cielo e incontable como la arena de la orilla del mar”. Esta noción de que la multitud de granos de arena bien podría ser infinita, que es para la pasmada estupefacción pero no para la cuantificación, es antigua. El historiador Ilan Vardi cita la antigua palabra griega ψαμμκoσιoι, o ciento-arena, de significado coloquial tropecientos millones; así como un pasaje de la Oda olímpica II de Píndaro afirmando que “la arena escapa de ser contada”.

Sigue aquí

Rompiendo el plácido silencio en Tio Petros

Tan sólo dos párrafos rompiendo el plácido silencio de este blog en el ciberlimbo , ahora tan sólo interrumpido con las visitas y los comentarios de los lectores, para alegría y contento del autor.

El primero para agradecer los ya más de cincuenta comentarios al cierre temporal del mismo. Siempre he dicho que los comentarios son la sal del blog, pero son mucho más: son el único feedback con el que cuenta el autor para saber si su trabajo está teniendo algún interés para los lectores, mucho más allá de la vaga pero también válida referencia de los contadores de visitas. Muchas gracias a todos por unos comentarios tan inmerecidamente positivos.

El segundo para recomendarles el post que Vailima , ese pedazo de mujer con la que uno, sin mayor mérito por su parte, tiene la suerte y el gusto de compartir su vida; ha dedicado al escritor norteamericano Dan Brown.

Pocas veces un autor ha merecido, en mi humilde opinión, un post de este calibre.

Hasta pronto.

Esto es todo, amigos.

Me da pena ver el blog sin posts sobre matemáticas desde hace un mes.

Llevo semanas demorando la decisión de hacer algo al respecto, y creo que lo mejor será explicar que recientes cambios en mi disponibilidad de tiempo libre, así como en mi trabajo me hacen muy difícil continuar el blog, al menos hacerlo como hasta ahora.

Tio Petros se ha estabilizado en orden a las 500 visitas diarias, de forma bastante independiente del ritmo de publicación de nuevos posts.

Este dato, y el hecho de que me siguen llegando comentarios en posts pretéritos me hacen deducir que existe cierto interés en seguir leyendo las historias matemáticas del blog. Aquí quedan varios centenares de ellas, lanzadas al cibermundo para quien quiera pasar un rato leyéndolas.

Así pues, TioPetros no se actualizará a partir de hoy.

Ha sido un placer pasear juntos por los más variados paisajes matemáticos, en busca de la belleza y de la verdad.

Hasta pronto.

Jesús M. Landart

Lo mejor de la web no está en la web.

Lo sabíamos desde siempre, pero cada ocasión de comprobarlo nos llena de satisfacción. Lo mejor de internet son las personas, y la posibilidad que nos da la web de encontrarnos en carne y hueso tras mil encuentros virtuales.

Ayer lo volvimos a comprobar Vailima y yo con Palimp , Mariajo y Carlos. Como tiempo atrás ya lo comprobáramos con Akin , con Blagdaros , con Unanada , con Alberto, con Marta, pjorge , con Canopus , con Luis Miguel , con Carl Philips , con Crystal , con Abdul, con Ranxo, con Toy... lo importante son las personas y la amistad que nos une. Sin la web no hubiéra sido posible.

Y si el encuentro se produce en navidad, pues mejor que mejor. Aunque la climatología no acompañara, volvimos a comprobar cómo se produce el milagro del encuentro entre cinco personas, a tres de ellas Vailima y yo no habíamos visto nunca; y sin embargo desde el primer instante fluía la conversación, la camaradería y un cúmulo de vivencias comunes cuya virtualidad hipertextual desaparecía dando paso al calor del encuentro directo. Como si nos conociéramos de toda la vida.

Cuando nos echaron del último bar no hubo más remedio que despedirse en un Donostia lluvioso y frío a altas horas de la madrugada.

No importaba. El calor lo llevábamos dentro.

Feliz cambio de año, amigos.

Integral de Lebesgue de funciones simples

Viene de aquí.

Según hemos visto aquí existe una definición muy clara de le integral de Lebesgue para las funciones simples. Tanto que parece muy poca cosa después de tanta introducción. Sin embargo, es notable el hecho de que tan poca cosa consigue vencer a la indomable función de Dirichlet.

Repetiremos aquí que la idea de Lebesgue es dividir el dominio de integración en particiones relativas a los valores de la propia función. En las siguientes ilustraciones veremos una vez más la diferencia entre la integral de Riemann y la de Lebesgue para una función simple general

Sea la función simple:

f= 2 · I_(0,1]U(6,8] + 3 · I_(1,6)]

Espero que la nomenclatura esté clara: la función vale 2 para los puntos del conjunto (0,1]U(6,8] y vale tres para los del conjunto (1,6] , valiendo cero en el resto.

La tenemos aquí:

La integración de Riemann dividirá el intervalo de intergración en rectángulos cada ver más finos, evaluando el área de cada uno, de la siguiente forma:

La integraciónde Legesgue, en cambio dividirá el intervalo de integración en sólo dos partes, una para los puntos en los que la función vale 2 y otra para los puntos en los que la función vale 3, sumando los productos de las medidas respectivas de los dos trozos por 2 y por 3 respectivamente:

Es obvio que en ambos casos la integral va a a valer 21: el área bajo la función.

En el caso de la función de Dirichlet (circunscrita al intervalo [0,1], por muy complicada que nos pareciera desde el punto de vista de la continuidad o de cualquier propiedad topológica, a la luz de "lo que verdaderamente importa" para Lebesgue, es una función muy sencilla: es una función simple. Más aún: es una sencilla función indicatriz que toma valor uno para los puntos irracionales y valor cero para los racionales.

Así pues, la integral valdrá:

I=1·m(R-Q) + 0.m(Q)

Dado que el conjunto de los racionales del intervalo [0,1] tiene medida cero, el conjunto de los irracionales del mismo intervalo tendrá medida uno, y la integral valdrá I = 1·1+0·0 = 1. El valor de la integral es el mismo que para la función unidad, de lo que se deduce que para la integración de Lebesgue, todo conjunto de medida nula no aporta absolutamente nada al valor de la integral. Esto es una simplificación extraordinaria, porque de un plumazo evitamos todos los comportamientos patológicos de funciones extrañas cuyas irregularidades no nos hacen más que molestar.

Aunque esto parece cosa de niños, las buenísimas propiedades en el límite de esta integral así definida nos habilitarán extrapolarla sin demasiados problemas a toda función medible. Entonces comprenderemos la potencia de la nueva herramienta, y lo que más nos importa: el porqué de la misma. Lo haremos lentamente porque no tenemos prisa.

Manifiesto por una cultura veraz

La Sociedad para el avance del Pensamiento Crítico, ARP-SAPC ha propuesto un manifiesto a favor de una cultura veraz, que será enviado a numerosos medios de comunicación.

El motivo de tal lanzamiento coincide con el estreno de un nuevo canal de televisión en España, Canal Cuatro y concretamente con la puesta en marcha de un programa sobre supercherías paranormales dirigido por Iker Jiménez, conocido divulgador de lo paranormal en España, plagados de mentiras, datos falsos o especulaciones surrealistas que se cuentan como ciertas.

En realidad, pienso yo, ese no es el motivo, sino el detonante. El citado manifiesto es una reflexión sobre el papel de los medios de comunicación en una sociedad libre y democrática, sobre el tratamiento informativo de la verdad, y sobre la calidad de la información científica que llega a las personas de nuestro país. Las paraciencias en sus vertientes más populacheras, ya sea ufología, ya sea astrología, ya sea proctomancia no son sino lo más vistoso y quizás inofensivo del fenómeno. La necesidad de reivindicar una cultura respetuosa con la verdad nace de la facilidad de manipulación de las personas mal informadas, engañadas o radicalizadas en esquemas mentales irracionales o alienadas con basura televisiva.

Favorecer una cultura veraz, entre otras cosas es luchar por que no lleguen al ciudadano versiones sesgadas de los hechos, historias creativas de acontecimientos históricos o mentiras descaradas que hagan aumentar la share de un programa televisivo a base de vomitar mierda sobre las sinapsis de los televidentes. Como no podía ser de otra forma, se han levantado voces contra este manifiesto explicando que es un atentado contra la libertad de expresión. Yo pudiera estar perfectamente equivocado, pero me parece que este argumento no se sostiene. No se pide nada que no esté implícito en la ética deontológica periodística. Solicitar, o exigir veracidad en las informaciones y pedir o exigir que se controlen las emisiones mentirosas es una utopía perfectamente lícita. De mínimos, diría yo.

Lo que ocurre es que, a lo mejor, nos estamos centrando en las tonterías paranormales, como si estas fueran el compendio de todos los males informativos españoles. Pero no debemos olvidar que mala divulgación científica puede hacer más daño que paraciencia, y que Rappel, Paco Porras o Carlos Jesús no son sino iconos visibles del cutrerío patrio, relativamente intrascendentes, e inofensivos . La manipulación de la verdad y su puesta en escena mediática al interés de corrientes, partidos e ideologías es más preocupante, y  la reivindicación dura y exigente de una cultura veraz no es sino una llamada de atención sobre este punto. 

Cualquier lector que quiera añadir su firma a la ya larga lista de firmantes puede hacerlo cliqueando en la imagen inferior. Yo ya lo he hecho.

 

Funciones simples

Viene de aquí.

Seguimos en nuestra intención de difinir un número cada vez más amplio de funciones que caigan dentro de lo que hemos definido como funciones medibles. Hemos visto que las funciones indicatrices son funciones medibles. Ahora utilizaremos aquellas para definir unas funciones, también medibles, que serán un poco más complejas que las indicatrices: las funciones simples.

Llamaremos función simple a toda función que tome un número finito de valores diferentes. Es fácil de comprender que las funciones simples se pueden expresar como combinación lineal de funciones indicatrices, por lo que adoptarán la siguiente forma general:

En la definición anterior no hemos especificado que los conjuntos A_i deban ser disjuntos, pero aunque no lo sean, toda función simple se puede poner como combinación lineal de funciones indicatrices de subconjuntos disjuntos, de modo que supondremos que lo son, sin pérdida de generalidad, y que forman un recubrimiento del espacio origen en su totalidad.

No demostraremos aquí, pero un resultado crucial que atañe a funciones medibles es que si f y g son dos funciones medibles, y c es una constante, entonces las funciones c.f, f+c, f+g, f.g, 1/f, max(f,g), min(f,g) y /f/ también son medibles.

En función de este resultado, las funciones simples serán medibles.

Será para estas funciones para las que definamos en primer lugar la integral de Legesgue, de la forma siguiente:

Así pues, definimos la integral de una función como una suma de productos. Cada producto está formado por el coeficiente correspondiente a cada subconjunto en la definición de la función y por la medida del mismo. Esto tiene enormes consecuencias: cualquier conjunto de medida cero, que influirá en las propiedades topológicas de la función y que incordiará mucho a la hora de integrar en el sentido de Riemann, aquí tiene un peso nulo en la integral, por lo que simplemente no será considerado. ¿Para qué íbamos a considerarlo, si está definido sobre un conjunto de medida nula?

Estaría bien reflexionar un poco sobre esta definición. Para empezar, la función de Dirichlet se convierte en integrable con ella, sin necesidad de mayor aparato matemático. Lo veremos en el siguiente post.

Posteriormente, como habíamos anunciado, veremos las excelentes propiedades de las funciones medibles, y la forma en que la definicion de la integral de Lebesgue se extiende a todas ellas.

¿Qué es una función medible?

Viene de aquí. 

Vamos a fijar un poco la nomenclatura para entendernos. Hemos afirmado que la integral de Lebesgue es aplicable a un mayor número de funciones que la de Riemann. Este conjunto de funciones es el de las funciones medibles.  Una función medible está definida en un espacio de medida, en el que "todos"  los subconjuntos tienen asociado un número, que es la medida del mismo. La palabra todos aparece entrecomillada porque en realidad no son todos , sino un número muy grande de ellos, que forman una estructura denominada sigma-algebra de los conjuntos medibles del espacio dado. Una sigma-algebra no es sino una colección de subconjuntos tales que toda unión, intersección o paso al complementario así como uniones numerables de subconjuntos es un nuevo subconjunto que también de la misma pertenece a ella, .

Cuando estuvimos hablando de variables aleatorias mencionamos el concepto, que no vendrá mal recordar aquí. Allí venía a cuento porque los espacios probabilísticos son espacios medibles, y las variables aleatorias son precisamente funciones medibles en dichos espacios. Ahora hablaremos con toda generalidad, sin mencionar qué tipo de espacio medible es en el que estamos trabajando. 

Un espacio de medida, recordamos, es una tríada (X,A,M), donde X es un conjunto cualquiera, A es una sigma-álgebra (la de los subconjuntos medibles) subre X y M es una medida definida en A.

Supongamos que tenemos dos espacios de medida: (X,A,M_X) y (Y,B,M_Y); y una aplicación f de X a Y. Diremos que f es una función medible cuando la antiimagen de todo subconjunto de Y que sea elemento de B es un subconjunto de X que es a su vez elemento de A.

De esta forma, la función “es respetuosa” con las sigma-álgebras de partida y de llegada.

Este aparente galimatías esconde una idea extremadamente sencilla: los elementos de las respectivas sigma-álgebras son simplemente aquellos subconjuntos para los cuales tiene sentido aplicar el concepto de medida, y por ello se denominan conjuntos medibles . La propiedad pedida a las funciones medibles exige que cada medible del conjunto de llegada tenga un alter ego medible en el conjunto de partida del cual es imagen por dicha aplicación.

Fijémonos en la figura: un punto p del espacio de partida tiene su imagen por la función f en el punto f(p) del espacio imagen. Dado un sunconjunto medible (con la medible definida en la imagen), existe otro medible en el origen (ahora con la medida definida en el espacio de origen) tal que es la contraimagen por la función f del primero.

Es fácil comprender que este tipo de funciones son las interesantes entre espacios medibles.  Nuestra meta será definir una integral que sirva para todas las funciones medibles que se puedan construir en un espacio de medida.

El tipo más sencillo de funciones medibles es el de las funciones indicatrices.

Una función indicatriz de un subconjunto no es sino una función que vale uno para todos los puntos de un subconjunto dado, valiendo cero para el resto. Es indicatriz de este subconjunto dado. Es importante señalar que la función no está definida sólo en dicho conjunto, sino en todo el espacio de partida.

Dado un subconjunto medible  A de un conjunto medible X, la función indicatriz de A es:

I_A(x)= 1 si x pertenece a A

I_A(x)= 0 si x no pertenece a A

Demostremos que toda función indicatriz es medible:

La función indicatriz sólo toma dos valores, uno o cero. Dado un subconjunto B medible de R , que es el espacio de llegada, sólo pueden darse tres casos: 

1.- que B contenga al uno y  no al cero,

2.- que contenga al cero y no al uno,

3.- que contenga a ambos y

4.- que no contenga a ninguno.

En el primer caso, la contraimagen de B es precisamente A, porque por definición la contraimagen de B será el conjunto de todos aquellos puntos que toman valores en B, y de todos los posibles valores de B, sólo el uno tiene posibilidad de ser el valor asignado a puntos del origen. Como por definicion de la función indicatriz, los puntos que tienen asociado el valor unidad son los pertenecientes a A, tenemos el resultado. Razonando de la misma manera llegaremos a la conclusión de que en el segundo caso, la contraimagen de B es el complementario de A, en el tercero es el conjunto de origen entero y en el cuarto es el conjunto vacío. Todos ellos son conjuntos medibles por ser medible A, por lo que ya tenemos demostrado el resultado.

Continuaremos construyendo funciones más complicadas a partir de las indicatrices manteniendo la medibilidad de las mismas y definiendo la integral de Lebesgue enseguida.

Seguimos en breve.