El Teorema de Keeler, permutaciones y Futurama

En la serie Futurama, el episodio 10 de la sexta temporada, El prisionero de Benda, es un poco especial. Tan especial, que merece la pena que hablemos de él en Álgebra Básica. Al fin y al cabo, no en muchas series aparecen teoremas originales, correctamente enunciados, y correctamente demostrados.

En este capítulo ocurren muchas cosas, pero el argumento esencial es que el Profesor Farnsworth y Amy construyen una máquina que les permite intercambiar sus mentes. Así, cada uno puede hacer cosas que no podría en su cuerpo original. (No haré más spoilers que éste.)

Por desgracia, la máquina no funciona dos veces sobre los mismos cuerpos. En términos de permutaciones (este sigue siendo el blog de Álgebra Básica, después de todo), si representamos el intercambio del profesor y Amy como una trasposición, tenemos que una vez que se usa la trasposición \((pa)\), ya no se puede volver a usar.

Naturalmente, como Futurama es Futurama, la cosa se desmadra bastante, y tras una muy complicada serie de acontecimientos, hay que deshacer cambios entre Amy, el Profesor Farnsworth, el Emperador Nikolai, Bender, el robot cubo de limpieza, Leela, Fry, Zoidberg, Hermes y Scrufy. ¿Cómo resolverlo?

En palabras del Profesor Farnsworth (hablando desde el cuerpo de Bender),

I’m afraid we need to use… math!
Profesor Farnsworth

El autor de este capítulo resulta ser Ken Keeler, casualmente un matemático doctorado por la Universidad de Harvard. Para reolver el capítulo, Keeler demostró el siguiente Teorema:

Teorema (Teorema de Futurama, K. Keeler)

Sea \(A\) un conjunto finito y sean \(x\) e \(y\) dos elementos que no pertenecen a \(A\). Toda permutación de \(A\) se puede reducir a la identidad mediante una sucesión de trasposiciones de \(A\cup \{x,y\}\) cada una de las cuales contiene a \(x\) o a \(y\).

En el capítulo, \(x\) e \(y\) son dos personajes nuevos, dos globertrotters que demuestran el teorema y consiguen devolver cada mente a su cuerpo (o al revés, ya no me queda claro).

El teorema, y su demostración correcta y completa, aparece en una imagen del episodio:Prisoner_of_Benda_Theorem_on_Chalkboard

Se puede seguir fácilmente la demostración escrita en la imagen, así que no haré más que un par de comentarios.

  1. En primer lugar, como toda permutación se descompone en producto de ciclos disjuntos, basta demostrar el Teorema para un ciclo \(\pi\), que se puede escribir, sin pérdida de generalidad como
    $$
    \pi =\begin{pmatrix}
    1 & 2 & \dots &k &k+1 &\dots& n \\
    2 & 3 & \dots & 1 & k+1 &\dots &n
    \end{pmatrix}.
    $$
  2. En la demostración, por comodidad se escribe el producto de permutaciones de izquierda a derecha, mientras que nosotros, en clase, usamos el producto de derecha a izquierda.

Me había planteado poner este teorema como ejercicio del primer parcial, pero en fin, me han convencido para que no lo haga, al menos este año.

¿Conocéis otros ejemplo de un teorema correctamente demostrado en una serie o película? No vale si están sólo enunciados…


Aquí tenéis un vídeo (en inglés) que comenta con bastante más detalle el capítulo y el enunciado del Teorema, aunque no cubre la demostración.

Los parias, los monstruos y otros grupos

Hace unos días, comenté en clase de pasada que existe un teorema de clasificación de grupos finitos, y dije (de cabeza) que el teorema tiene aproximadamente 15.000 páginas. No era un error, pero quizá sea interesante dar algunos detalles adicionales.

Subgrupos normales… y de los otros.

En primer lugar, hace falta definir lo que es un subgrupo normal. Dado un grupo \((G,\star)\), se dice que \(H\subset G\) es un subgrupo si para todo elemento \(g\in G\) se verifica que \(g\star H=H\star g\). Obviamente, si el grupo \(G\) es conmutativo, todos sus subgrupos son normales. Pero eso no es necesariamente cierto si \(G\) no es conmutativo.

Ejercicio: Demuestre que \(H=\{(),(12)\}\) es un subgrupo NO normal de \(S_3\). Demuestre que el grupo alternado \(A_3\) sí es un subgrupo normal de \(S_3\).

[Indicaciones: para la primera parte, calcule \((123)H\neq H(123)\). Para la segunda, observe que \(\sigma A_3\) sólo puede ser, bien\(A_3\), bien el conjunto de todas las permutaciones impares.]

Subgrupos simples… y de los otros.

Un grupo se llama simple si no tiene subgrupos normales. Si un grupo no es simple, se puede “romper” en dos grupos más pequeños; un subgrupo normal y el grupo cociente. A su vez, cada uno de estos grupos se pueden “romper” en grupos más pequeños y así sucesivamente. Si \(G\) es un grupo finito, es claro que en algún momento llegaremos a expresar \(G\) en función de grupos simples. El resultado preciso es más complicado de enunciar, se llama Teorema de Jordan-Hölder.

El resumen de todo esto es que para clasificar los grupos finitos, basta clasificar los grupos finitos simples. Para saber más, puede empezar por la wikipedia, o por un artículo de Richard Elwes sobre el tema.

El mega-Teorema.

Pues bien, existe un Teorema de Clasificación de grupos simples finitos, distribuido a lo largo de 15.000 páginas, que dice, esencialmente, que un grupo finito simple es isomorfo a uno de los siguientes tipos1:

  1. Grupos cíclicos de orden primo.
  2. Grupos alternados \(A_n\), con \(n\geq 5\).
  3. Grupos (de tipo Lie) de Chevalley
  4. Otros grupos (de tipo Lie): grupos de Chevalley torcidos (twisted) o grupo de Tits.
  5. Grupos esporádicos. Aquí aparecen 26 grupos “inclasificables”. Entre éstos, encontramos nombres tan curiosos como baby monster, monster, los grupos parias, etc.

El grupo monster se llama así no por la bebida energética, sino porque es el grupo simple finito más grande. Además, contiene 20 de los 26 grupos esporádicos como subcocientes. Los seis que no están contenidos son los “parias”. El grupo monster es finito, pero poco: tiene orden

\(808017424794512875886459904961710757005754368000000000.\)

¡Sí que da miedo el monster!


  1. Varias fuentes dan la clasificación de diversas formas. Por ejemplo, algunos autores consideran el grupo de Tits como esporádico, otros siguen criterios ligeramente distintos, etc. Aquí, por simplificar, los agrupo bastante groseramente. 

Ordenando monomios

Si nos dan el polinomio \(X^{12}-X+2X^3-4+3X^{10}-5X^2,\) lo normal es que antes de operar con él lo ordenemos así

\(X^{12}+3X^{10}+2X^3-5X^2-X-4,\)

o así

\(-4-X-5X^2+2X^3+3X^{10}+X^{12}.\)

De tal forma que usamos el orden natural en los enteros mayores o iguales que cero para ordenar los monomios en sentido descendente o ascendente.

Si ahora nos dan un polinomio en dos variables \(X, Y\) establecer un orden entre sus monomios debe ser equivalente a ordenar los pares de números enteros positivos. Por ejemplo, sea el polinomio

\(f(X,Y)=X^3Y^2-2X^4+3XY^4-Y^6+X^5+XY-2Y^2+Y^5-1.\)

¿Cómo ordenarías los monomios de \(f(X,Y)\)? ¿Puedes establecer una relación de orden en el conjunto de los pares de enteros mayores o iguales que cero que concuerde con el orden que has elegido para \(f(X,Y)\)?

Los comentarios están abiertos para tu respuesta

No todo es un conjunto

NPG x84663; Bertrand Arthur William Russell, 3rd Earl Russell by Bassano
Bertrand Russell

Hemos empezado Álgebra Básica por el principio: Teoría de conjuntos. La cosa es que hemos empezado con un truquillo. Más o menos, hemos definido un conjunto así:

Definición: un conjunto es una colección de objetos distintos entre sí que comparten una propiedad. Para que un conjunto esté bien definido, debe ser posible discernir si un objeto arbitrario está o no en él.

Pues bien, esto no es la definición formal de conjunto. De hecho, la definición formal lleva bastante trabajo; para darla con todos los detalles, habría que estudiar la teoría de conjuntos axiomática de Zermelo-Fraenkel (ZFC), incluyendo el axioma de elección. Esto sólo para empezar.

Nosotros usaremos conjuntos, y sólo conjuntos, desde el primer día, pero me gustaría lanzaros la siguiente pregunta: ¿hay cosas que no sean conjuntos? La respuesta es un poco elaborada; y hay que hablar de la Paradoja de Russell.

El año pasado le pedí a uno de mis víctimas ex-alumnos que escribiera la paradoja de Russell, precisamente para los alumnos de Álgebra Básica. Así que quien tenga curiosidad (que espero seáis todos), puede leerlo con calma en su blog. Después de eso, puede leer el artículo del mismo tema de gaussianos. Y después de eso podéis ir a la biblioteca y buscar un libro sobre teoría de conjuntos.

Aviso: Cuidado con la teoría de conjuntos. Puede quitaros el sueño.