Revista "El Acertijo"

"El Acertijo" fue una revista de juegos de ingenio, pero fue también mucho más que eso. Fue lugar de encuentro de ideas, de alto ingenio y de buen humor. Para muchos de nosotros es recuerdo y es leyenda. De la mano de Marcelo Iglesias (a) Markelo "El Acertijo" ha vuelto a la vida pues Marcelo ha tomado el compromiso de llevar adelante el nada desdeñable trabajo de escanear una a una todas las páginas de los 25 números de la revista y colocarlas aquí on line.

Cierro esta entrada con las palabras que Jaime Poniachik, alma páter de "El Acertijo", escribió para la ocasión:

El Acertijo On Line es como haber muerto y resucitar. Un milagro. Vivió alegremente en el milenio pasado, de 1992 a 1997. ¿Y ahora, qué pasará? Creo que en El A. hay temas y problemas aún abiertos. Un segundo milagro, o tercero o cuarto, podrá ocurrir cuando los viejos temas y problemas den lugar a nuevos desarrollos. Y cuando aquella pequeña tribu de acertijeros vea llegar nuevos aficionados. Gracias a Markelo, cantaremos y bailaremos todos alrededor del fuego.

Jaime Poniachik

Cero elevado a la cero

Un modo perfectamente aceptable de definir los números naturales es decir que son los cardinales (o cantidades de elementos) de los conjuntos finitos. Así por ejemplo:

0 es el cardinal del conjunto vacío (pues el conjunto vacío tiene cero elementos)
1 es el cardinal del conjunto {0} (o de cualquier otro conjunto que tanga tantos elementos como él)
2 es el cardinal del conjunto {0, 1}
3 es el cardinal del conjunto {0, 1, 2}

Y así sucesivamente. (En la definición anterior hay, en aras de un lenguaje más comprensible, algunas imprecisiones, pero los conceptos son esencialmente correctos.)

Así definidos los números, las operaciones entre ellos pueden definirse apelando a las operaciones existentes entre conjuntos. En particular nos interesa aquí la operación de potenciación. Definamos primero la potenciación entre conjuntos:

Definición: si A y B son dos conjuntos, se define B^A (el símbolo ^ significa “elevado a la”) como el conjunto formado por todas las funciones de A en B.

Precisemos un poco, ¿qué es una función de A en B? Una función de A en B es cualquier conjunto F de pares ordenados (a, b) (con a en A y b en B) que cumpla las dos condiciones siguientes:

1) Si a está en A entonces existe algún b en B tal que (a, b) está en F.
2) Si (a, b) y (a, b’) están en F entonces b = b’.

(Intuitivamente, si interpretamos que el hecho de que (a, b) esté en F como que F(a) = b, entonces la primera condición diría que todo elemento de A tiene una imagen y la segunda que no tiene dos imágenes diferentes.)

Mostremos un pequeño ejemplo; supongamos que A = {0, 1} y que B = {0, 1, 2}. Una función de A en B es, por ejemplo, {(0,1), (1,2)}. Se ve fácilmente que hay exactamente nueve funciones en B^A, y no por casualidad 9 = 3^2.

Definición: si alpha es el cardinal de A y beta es el cardinal de B entonces se define beta^alpha como el cardinal de B^A.

Si alpha y beta son ambos enteros mayores que cero la definición anterior coincide con la definición escolar más conocida y, de hecho, la definición anterior puede extenderse sin cambios a cardinales infinitos.

Pero no nos interesa aquí el infinito, sino todo lo contrario. La pregunta que nos convoca es ¿qué nos dice la definición anterior si alpha = 0, o beta = 0, o ambos?

Supongamos que beta = 0 y alpha no es cero. Eso significa que B es el conjunto vacío y que A no es vacío. ¿Qué conjuntos F de pares ordenados hay en B^A? Si A es no vacío pero B sí lo es entonces la condición 1) de la definición de función falla siempre. No importa qué función intentemos definir la condición 1) nos pide que dado algún a en A exista algún b en B que cumpla algo, pero tal b no puede existir porque B es vacío.

B^A entonces no contiene nada, B^A es en sí mismo el conjunto vacío y por ende beta^alpha = 0. Hemos probado así que 0^alpha = 0 si alpha es mayor que cero.

Supongamos ahora que A es vacío. ¿Qué conjuntos F de pares ordenados hay en B^A? Ahora sí hay un conjunto F que cumple la definición de función: el conjunto vacío. Una implicación cuyo antecedente es falso resulta ser siempre verdadera, por lo tanto si A y F son vacíos ambas condiciones de la definición de función se cumplen. Por otra parte, dado que A es vacío, no hay otras funciones posibles. Nótese que en el caso anterior ni siquiera el vacío servía como función, no había ninguna, pero en esta caso sí hay una (la “función vacía”) y por lo tanto B^A tiene un elemento. Hemos probado que beta^0 = 1.

¿Qué pasa si alpha = 0 y beta = 0? Si se observa la demostración anterior, en ningún momento aparece mencionado el hecho B sea no vacío (en cambio en la demostración de que 0^alpha = 0 sí se usa el hecho de que alpha no es cero). La demostración anterior vale textualmente sin cambios si beta = 0 y por lo tanto ese mismo razonamiento prueba que 0^0 = 1.

Por lo tanto queda probado que 0^0 = 1.

Addenda: por motivos que, confieso, me resultan difíciles de entender existe la idea muy extendida (y en general muy arraigada en quienes la sostienen) de que 0^0 es una operación “prohibida”. Sin embargo, no sólo acabamos de probar que 0^0 = 1 sino que este valor es perfectamente coherente con diversas fórmulas matemáticas, entre ellas la que dice que la sumatoria de a_ix^i (con i entre 0 y n) vale a_0 si x = 0 (esto sólo es posible decirlo si 0^0 = 1).

Addenda 2: es posible dar definiciones diferentes de la potenciación y en ese caso que alpha^beta es el cardinal de A^B deja de ser una definición y pasa a ser un teorema. Bajo estas circunstancias el razonamiento de más arriba demustra que es perfectamente consistente desde el punto de vista lógico e inclusive conveniente y necesario desde el punto de vista de la coherencia matemática que, cualquiera sea la definición que se adopte, sea 0^0 = 1.

Addenda 3: otra definición posible para ^ (con exponente entero no negativo) es decir que a^0 = 1 para todo a (incluyendo, claro está, a = 0) y que a^(n + 1) = a*a^n (donde * es la multiplicación). Nótese que según esta definición 0^0 = 1, como debe ser, y que si n>0, n = k + 1, entonces 0^n = 0^1*0^k = 0*0^k = 0, como también debe ser. En particular: 0^1 = 0*0^0 = 0*1 = 0. Esta definición resulta así totalmente equivalente a la que hemos dado en el cuerpo principal de la entrada.

El Omegón y todo eso... (Parte 9)

(A la parte 8 – A la parte 10)

Buena ordenación de los ordinales

Recordemos que si A y B son conjuntos bien ordenados entonces decimos que A > B si B es equivalente a un segmento inicial de A. En la parte anterior hemos probado (siguiendo a Cantor) que si A y B son dos conjuntos bien ordenados entonces siempre vale que A > B, o bien B > A o bien A es equivalente a B (una y sólo una de las tres alternativas).

Por otra parte, por definición, el ordinal alpha es mayor que el ordinal beta si A > B donde A es cualquier conjunto cuyo ordinal sea alpha y B es cualquier conjunto cuyo ordinal sea beta.

Si alpha y beta son dos ordinales entonces siempre sucede que alpha > beta, o beta > alpha o alpha = beta (una y sólo una de las tres alternativas).

La pregunta es ahora: ¿es posible hallar una familia infinita de conjuntos bien ordenados A1, A2, A3,... tal que A1 > A2 > A3 >....? Es decir ¿existe una cadena descendente infinita de conjuntos bien ordenados?

Veamos, si A1 > A2 entonces A2 es equivalente a un segmento inicial de A1. Podemos asumir, para simplificar la escritura, que A2 es un segmento inicial de A1. Digamos que A2 es el conjunto de todos los elementos menores que algún a2. Del mismo modo si A2 > A3 entonces A3 es el conjunto de todos los elementos que son menores que algún a3 perteneciente a A2 (y si a3 pertenece a A2 entonces a2 > a3). Del mismo modo, como A4 es un segmento inicial de A3 entonces hay un a4 tal que a2 > a3 > a4, todos ellos, en particular, elementos de A1

Así siguiendo, concluimos que existen en A1 infinitos elementos tales que a2 > a3 > a4 > a5 > a6 >..., pero entonces {a1, a2, a3,...} es un subconjunto de A1 que no tiene mínimo. Esto contradice que A1 sea bien ordenado. Por lo tanto no puede existir una cadena infinita descendente de conjuntos bien ordenados.

De lo que acabamos de probar se deduce inmediatamente que no puede existir una cadena descendente infinita de ordinales y una consecuencia de ello, de gran importancia como ya veremos, es que los ordinales están bien ordenados. Es decir, toda familia no vacía de ordinales tiene un primer elemento.

Demostremos esta última afirmación. Si la afirmación fuera falsa, habría una familia de ordinales sin primer elemento. Sea alpha_1 un elemento cualquiera de esa familia; como alpha_1 no es su primer elemento, existe entonces un alpha_2 tal que alpha_1 > alpha_2. Como alpha_2 tampoco es el primer elemento de la familia, existe un alpha_3 tal que alpha_1 > alpha_2 > alpha_3. Así siguiendo habría entonces una cadena infinita descendente de ordinales, lo cual es imposible. Por lo tanto no puede haber una familia de ordinales que no tenga primer elemento. Los ordinales están bien ordenados.

Veremos en las partes siguientes las consecuencias de la buena ordenación de los ordinales, consecuencias que, como dijimos más arriba, son de gran importancia. Para que el lector vaya entrando en tema planteemos la siguiente pregunta: a todo conjunto bien ordenado le corresponde un ordinal, entonces ¿qué tan grande es el ordinal que le corresponde a la familia de todos los ordinales?

(A la parte 8 – A la parte 10)

El Omegón y todo eso... (Parte 8)

(A la parte 7 1/2 – A la parte 9)

¿Quién ordena a los ordinales?

Decíamos en la parte anterior que uno de los aspectos más interesante de los ordinales es, precisamente, que pueden ordenarse. Pero ¿cómo se define este orden?

Comencemos definiendo el siguiente concepto, que es central en el estudio de los conjuntos bien ordenados: si A es un conjunto bien ordenado y “x” es un elemento de A llamaremos S(x), el segmento inicial correspondiente a “x”, al conjunto de todos los elementos que son estrictamente menores que x.

A modo de ejemplo tomemos el conjunto {0, 1, 2, 3,..., 1’, 2’}. Entonces:

S(0) es el conjunto vacío
S(1) = {0}
S(2) = {0, 1}
S(3) = {0, 1, 2}
...
S(2’) = {0, 1, 2, 3,..., 1’}

Definición: si A y B son dos conjuntos bien ordenados cualesquiera, decimos que A > B si existe algún elemento x de A tal que S(x) es equivalente a B. O sea, esencialmente, si B es un segmento inicial de A. Más fácil: A > B si hay una copia de B al comienzo de A.

Por ejemplo: {0, 1, 2, 3,..., 1’, 2’, 3’, 4’} > {(0,0), (1,0), (2,0), (3,0),..., (1,1)}.

En lo que sigue, la intención es mostrar que, dados dos conjuntos bien ordenados A y B, entonces A > B, o bien B > A, o bien A y B son equivalentes. La demostración sigue casi textualmente el razonamiento de Cantor en su artículo de 1897.

Vayamos paso a paso, en lo que sigue A y B so conjuntos bien ordenados:

1) El conjunto A no puede ser equivalente a alguno de sus segmentos iniciales.

Demostración: supongamos que sí fuera A equivalente a algún segmento S(x) con x en A. Entonces S(x) es una copia de A y como A es equivalente a uno de sus segmentos entonces lo mismo sucede con S(x). Es decir S(x) es equivalente a S(x’) con x’ en S(x). En particular x > x’.

Pero como S(x’) es una copia de S(x) y S(x) es equivalente a uno de sus segmentos entonces S(x’) también es equivalente a uno de sus segmentos, digamos S(x”), con x’ > x”. Así siguiendo, construimos una cadena descendente infinita: x > x’ > x” >..., luego el conjunto {x, x’, x”,...} no tiene primer elemento y esto contradice que A sea bien ordenado. La contradicción prueba que A no puede ser equivalente a uno de sus segmentos.

2) Por definición, si A y B son equivalentes entonces existe una biyección f: A -> B que preserva el orden. Vamos a probar que si ése es el caso, entonces sólo existe una única biyección.

Demostración: supongamos que hubiera dos bisecciones diferentes, f y g. Sea “a” un elemento de A tal que f(a) y g(a) son diferentes. Digamos que f(a) = x y g(a) = x’. Podemos suponer además que x > x’ por lo que S(x’) es un segmento inicial de S(x).

Por otra parte es fácil ver que S(a) en cuanto segmento inicial de A es equivalente a S(x) (la biyección la da la propia función f) y que S(a) es también equivalente a S(x’). Por transitividad, S(x) es equivalente a S(x’). Luego S(x) es equivalente a uno de sus segmentos iniciales, esto contradice la afirmación 1). Esta contradicción demuestra que no puede haber dos biyecciones.

3) Si todo segmento S de A es equivalente a un segmento S’ de B y, recíprocamente, todo segmento T de B es equivalente a un segmento T’ de A, entonces A y B son equivalentes.

Demostración: vamos a definir una biyección f : A -> B que preserve el orden. Si x1 es el primer elemento de A e y1 es el primer elemento de B, definimos f(x1) = y1. Sea ahora “x” un elemento de A diferente de x1. Por hipótesis existe un elemento “y” en B tal que S(x) es equivalente a S(y). Definimos entonces f(x) = y. Los puntos anteriores permiten demostrar que f está bien definida y que es, en efecto, una biyección (los detalles quedan como ejercicio para el lector interesado).

4) Si existe al menos un segmento de A que no es equivalente a ningún segmento de B entonces todo segmento de B es equivalente a algún segmento de A.

Demostración: sea x el menor de los elementos de A tal que S(x) no es equivalente a ningún segmento de B.

Queremos probar que todo segmento de B es equivalente a alguno de A. Supongamos, por el contrario, que hubiera algún segmento de B que no es equivalente a ningún segmento de A. Sea “y” el menor de los elementos de B tal que S(y) no es equivalente a ningún segmento de A.

Sea S(x’) un segmento inicial de S(x), como x > x’ entonces S(x’) es equivalente a algún segmento S(y’) de B. Si y’ > y entonces S(y) es un segmento de S(y’) y sería equivalente a un segmento de S(x’), lo cual contradice la elección de “y”. Luego y > y’, en ese caso S(y’) es un segmento de S(y). Es decir, todo segmento inicial de S(x) es equivalente a un segmento inicial de S(y).

Del mismo modo se puede probar que todo segmento inicial de S(y) es equivalente a un segmento de S(x). Por el punto 3) S(x) y S(y) son equivalentes. Esto contradice la elección de x e y. Queda así probada la afirmación 4).

5) Dados A y B sucede una y sólo una de las siguientes relaciones: A > B, B > A, o bien A es equivalente a B.

Demostración: si A no es equivalente a B entonces, o bien existe algún segmento inicial de A que no es equivalente a ninguno de B, o bien existe algún segmento inicial de B que no es equivalente a ninguno de A. En el primer caso es A > B y en el segundo es B > A.

Estamos ahora en condiciones de definir el orden de los ordinales: si A y B son conjuntos bien ordenados entonces el ordinal de A es mayor que el ordinal de B si y sólo si A > B.

El punto 5) se traduce en que si alpha y beta son dos ordinales entonces sucede una y sólo una de las siguientes relaciones: alpha > beta, beta > alpha, o bien alpha = beta.

Ejercicio para el lector interesado: demuestre que si alpha > beta entonces alpha + gamma > beta + gamma.

(A la parte 7 1/2 – A la parte 9)

Dos problemas de lógica

Todos los nativos del planeta Verdalia son veraces o mentirosos. Los veraces, como su nombre sugiere, hacen exclusivamente afirmaciones verdaderas. Los mentirosos, por su parte, hacen exclusivamente afirmaciones falsas.

Problema 1: Aldo y Bruno son ambos nativos de Verdalia. Cada uno sabe a qué grupo pertenece el otro.

Aldo dice: Si yo soy veraz entonces Bruno es mentiroso.

Basado en esta información ¿se puede deducir a qué grupo pertenece Aldo o a qué grupo pertenece Bruno?

Problema 2: Carlos y Diego son también nativos de Verdalia y, como antes, cada uno sabe a qué grupo pertenece el otro.

Carlos dice: Si yo soy mentiroso entonces Diego es mentiroso.

Basado en esta información ¿se puede deducir a qué grupo pertenece Carlos o a qué grupo pertenece Diego?

El Omegón y todo eso... (Parte 7 1/2)

(A la parte 7 – A la parte 8)

Breve interregno

Hemos visto la definición de los ordinales y el modo en que estos se suman y se multiplican. Ahora bien, uno podría preguntarse ¿para qué sirve sumar y multiplicar ordinales? Más allá de la importancia intrínseca de las operaciones en sí, para Cantor la posibilidad de realizar estas operaciones tenía una importancia crucial, menos matemática que ideológica.

Como ya se dijo, Cantor veía a los ordinales como una extensión del sistema de los números naturales, como una forma de seguir contando más allá del infinito. De hecho es así como los presenta en su artículo de 1883, donde los llama, de hecho, “números ordinales”. Y es para defender esta naturaleza “numeral” que Cantor define la suma y el producto (tanto son números que hasta se los puede sumar y multiplicar).

Pero antes que sumados o multiplicados, la característica esencial de los ordinales es que pueden ser ordenados. Sin hacerlo explícito esta idea quedó de manifiesto cuando hemos escrito 0, 1, 2, 3,..., w, w + 1, w + 2,..., w + w, w + w + 1,... Pero, dados dos ordinales ¿cómo se determina cuál es mayor? ¿Están bien ordenados los ordinales? En las siguientes entradas responderemos estas preguntas y veremos cómo las respuestas nos llevan directamente a la (mal) llamada Paradoja de Burali-Forti.

Por otra parte ¿por qué Cantor quería contar “más allá del infinito”? Especialmente en un contexto histórico que era fuertemente reacio a ese tipo de pensamiento. Veremos también esto en las sucesivas entradas.

Por el momento, en la próxima parte, aunque no podremos decir quién vigila a los vigilantes sí podremos hablar de cómo se ordenan los ordinales.

(A la parte 7 – A la parte 8)

El Omegón y todo eso... (Parte 7)

(A la parte 6 – A la parte 7 1/2)

Producto de ordinales

A todo conjunto bien ordenado le corresponde un ordinal. A dos conjuntos equivalentes les corresponde el mismo ordinal.

Para definir la suma de ordinales, es decir para definir alfa + beta, hemos tomado un conjunto A que corresponde al ordinal alfa, un conjunto B que corresponde al ordinal beta y con ellos hemos construido un nuevo conjunto bien ordenado, que hemos llamado (AB), y que consiste esencialmente en colocar una copia de B a continuación de A. Convinimos en definir entonces que alfa + beta es el ordinal que corresponde a (AB).

Con más precisión, (AB) es un conjunto de pares, todos ellos de la forma (a,0) con a un elemento de A, o (b,1) con b un elemento de B. Para comparar dos pares, primero se comparan sus segundas coordenadas y, en caso de que éstas sean iguales, se comparan entonces las primeras.

Para definir el producto alfa x beta se procede de manera similar. Tomamos un conjunto A correspondiente al ordinal alfa, un conjunto B correspondiente al ordinal beta, y con ellos construimos un nuevo conjunto cuyo ordinal será, por definición, alfa x beta.

Si A y B son dos conjuntos, su producto cartesiano A x B es el conjunto formado por todos los pares (a,b) tales que a es un elemento de A y b es un elemento de B. Por ejemplo, N x {0,1} es el conjunto de los pares (n,0) y (n,1) con n natural. Tomamos en A x B el mismo orden que antes definimos para pares: primero se comparan las segundas coordenadas y, si éstas son iguales, se comparan entonces las primeras coordenadas.

Ejercicio para el lector: demuestre que si A y B son bien ordenados entonces A x B también lo es.

Definición: si A corresponde al ordinal alfa y B corresponde al ordinal beta entonces alfa x beta es el ordinal de A x B.

Ejemplos:

1) Afortunadamente alfa x 1 = 1 x alfa = alfa. También alfa x 0 = 0 x alfa = 0.

2) Resulta claro de las definiciones que (AA) = A x {0,1}, por lo tanto alfa + alfa = alfa x 2. En particular w + w = w x 2.

3) El ordenamiento de N x {0,1} es así: (0,0), (1,0), (2,0),...., (0,1), (1,1,), (2,1),... (primero van todos los pares que tienen segunda coordenada igual a 0 y luego todos los que tienen segunda coordenada igual a 1). Este ordenamiento corresponde a w + w, tal como se dijo en el ejemplo anterior.

El ordenamiento de {0,1} x N es así: (0,0), (1,0), (0,1), (1,1), (0,2), (1,2),... (primero van todos los pares que tienen segunda coordenada igual a 0, luego todos los que tienen segunda coordenada igual a 1, etc.) que es equivalente al ordenamiento de N.

Luego w x 2 = w + w, pero 2 x w = w. Es decir, el producto de ordinales no es conmutativo.

4) El ordenamiento de N x N es así: (0,0), (1,0), (2,0), (3,0),..., (0,1), (1,1), (2,1), (3,1),... , (0,2), (1,2), (2,2), (3,2),..., (0,3), (1,3), (2,3), (3,3),..., (0,4), (1,4), (2,4), (3,4),...,...,...,..., (0,n), (1,n), (2,n), (3,n),...,... que corresponde a lo que podría llamarse w + w + w +... (“w” veces). Esto corresponde con la idea intuitiva de de w + w + w +... (w veces) = w x w.

Observaciones:

1) El producto de ordinales es asociativo: (alfa x beta) x gamma = alfa x (beta x gamma).

2) No es cierto que (alfa + beta) x gamma sea igual a (alfa x gamma) + (beta x gamma), ya que como vimos (1 + 1) x w no es igual a (1 x w) + (1 x w).

3) ¿Será cierto que gamma x (alfa + beta) es igual a (gamma x alfa) + (gamma x beta)?

(A la parte 6 – A la parte 7 1/2)