jueves, 7 de marzo de 2013

Ser cuadrado es divertido.

Cómo construir un cubo.

Me refiero a la figura. De hecho, en general, al politopo que generaliza al segmento, al cuadrado, al cubo, al hipercubo, y a todos los n-cubos, con n natural (me faltó nombrar al punto, de dimensión 0?). En general, todos conocemos a los primeros tres... pero, qué es un hipercubo? Cómo definimos a un cubo de más de tres dimensiones? Si los consideramos meros grafos (vértices unidos por aristas, sin considerar la posición de cada vértice), es muy sencillo; veamos que hay un patrón para construirlos:

* Un segmento es la unión de dos puntos por una arista.

* Para tener un cuadrado, debemos tomar dos segmentos A y B. Suponiendo que a1 y a2 son los vértices de A, y b1 y b2 son los vértices de B, al unir por aristas a1 con b1 y a2 con b2 tenemos un cuadrado.

* Para construir un cubo, debemos tener dos cuadrados A y B. Sean a1,a2,a3,a4 los vértices de A y b1,b2,b3,b4 los de B, al unir por aristas a1 con b1, a2 con b2, a3 con b3, a4 con b4 tenemos un cubo.


El patrón es notable en las dimensiones más bajas; podemos generalizarlo y aplicarlo a dimensiones más altas:

* Para construir un (n+1)-cubo ("cubo de dimensión n+1"), tomamos dos n-cubos A y B (dos cubos de una dimensión inmediatamente más baja). Sean a1,a2,...,a2^n los vértices de A y b1,b2,...,b2^n los vértices de B, al unir por aristas a1 con b1, a2 con b2, ... , a2^n con b2^n tenemos un (n+1)-cubo. Para quienes no conozcan la notación, "2^n" significa "dos elevado a la n-ésima potencia"; 2 multiplicado n veces. Simplificado: tomo dos cubos A y B de una dimensión inmediatamente más baja, y ligo con aristas cada vértice de A con exactamente un vértice de B.

Lo que para algunos puede no ser muy claro es que este método asume que un n-cubo tiene 2^n vértices. Pero esta cuestión es muy sencilla de demostrar:

* Claramente, un segmento tiene 2 = 2^1 vértices.
* Un cuadrado está formado por dos segmentos unidos por sus vértices. Cada segmento tiene dos vértices, por lo que tenemos 2 + 2 = 4 = 2^2 vértices.
* Un cuadrado está formado por dos cuadrados unidos por sus vértices. Cada cuadrado tiene cuatro vértices, por lo que tenemos 4 + 4 = 8 = 2^3 vértices.
* Etcétera, para dimensiones más altas.

De hecho, un punto consta de un solo vértice y su dimensión es 0; 1 = 2^0.

La lógica y los cubos.

Alguno diría "qué nexo puede llegar a haber entre un politopo, que es un elemento geométrico, y la lógica?". Otros afirmarían "pfff, por suerte todo se relaciona con la lógica, los cubos no son la excepción". Si bien no estoy seguro de la segunda afirmación (:P) sé que la primera es incorrecta. Inclusive, la correlación puede llegar a ser tan obvia (para nuestras mentes) que pocas veces la notamos.

Una proposición es una declaración que puede ser verdadera o falsa, pero no ambas al mismo tiempo (pues claro). Si es verdadera, se dice que su valor de verdad es verdadero; de lo contrario su valor de verdad es falso. Por ejemplo, "el sol es una estrella" es una proposición cuyo valor de verdad es verdadero, "dos y dos son cinco" es otra cuyo valor es falso. La declaración "qué bonito día!" NO es una proposición. Además, diremos que dos proposiciones son "independientes" si el valor de verdad de una no afecta al de la otra. Por ejemplo, podemos asumir que "yo tengo un gato" y "yo tengo un perro" son independientes, ya que podría no tener ninguno, podría tener uno de ellos, o incluso ambos (poco tiene que ver la propia rivalidad entre perros y gatos). Sin embargo, "hoy es lunes" y "mañana es martes" NO son independientes ya que si la primera es verdadera, la segunda también lo es.

Vamos a imaginar que tenemos una clase de mundo (algo así como una "plantilla") formada por una cantidad n de proposiciones independientes. Cada proposición será p1, p2, p3, ..., pn. Llamaremos a n el grado de la clase. Un mundo será una instancia de esta clase, donde cada proposición toma algún valor de verdad. Para ejemplificar, supongamos que nuestra clase está formada por n = 2 proposiciones, que son las siguientes:

p1: "Javier tiene un gato".
p2: "Javier tiene un perro".

Entonces, pregunto: cuántos mundos de esta clase podría haber? Respuesta: cuatro mundos.

Mundo número 1: p1 y p2 son falsos; o sea, Javier no tiene ni gato ni perro.
Mundo número 2: p1 es verdadero y p2 es falso; o sea, Javier tiene gato pero no tiene perro.
Mundo número 3: p1 es falso pero p2 es verdadero; Javier no tiene gato pero sí perro.
Mundo número 4: p1 y p2 son verdaderos; Javier tiene ambos.

En definitiva, es muy fácil enumerar los mundos para cada clase. Simplemente probamos todas las posibilidades, asignando verdadero o falso a las proposiciones. Entonces, en general, si tenemos una clase de mundo de grado n (con n proposiciones), cuántas instancias habrá? La respuesta es 2^n y el razonamiento es sencillo:

* Si n = 1, nuestra clase sólo está formada por una proposición; sea p1. Por ende, hay 2 = 2^1 mundos: en uno p1 es falso, en el otro p1 es verdadero.

* Si n = 2, la clase está hecha de dos proposiciones; sean p1 y p2. Notemos que si tomamos p1 podemos crear otra clase de grado 1; sea A. De la misma forma, podemos tomar p2 y crear otra clase de grado 1; sea B. Entonces, cualquier mundo de la clase está conformado por dos mundos, uno de A y otro de B. Cuántos mundos hay para A? Ya conocemos la respuesta por el punto anterior: 2. Y para B? Respuesta: también 2. Entonces cuántos mundos tenemos? 2*2 = 2^2 = 4.

* Si n = 3, la clase está hecha de tres proposiciones; sean p1,p2,p3. Con un razonamiento análogo al anterior, un mundo de nuestra clase está formado por tres mundos de clases de grado 1; sean A,B,C. Cuántos mundos hay para A? Ya conocemos la respuesta por el primer punto: 2. Lo mismo para B y C: 2 mundos. Entonces cuántos mundos tenemos? 2*2*2 = 2^3 = 8.

* Etcétera para grados más altos.

Se ve la relación entre clases y cubos? O entre mundos y vértices de un cubo? Notemos que dadas una clase de grado n y un n-cubo, podemos asignar un mundo a cada vértice del cubo... y viceversa: podemos asignar un vértice a cada mundo! Pero uno podría considerar esta correspondencia bastante trivial... más adelante mostraré que no es así.

Los conjuntos, la lógica y los cubos.


Pensemos en números naturales (son 0,1,2,3,4,5,... en adelante). De hecho, pensemos en conjuntos finitos de número naturales... son colecciones de números naturales, como por ejemplo {1,2,3}, o {1,3,5}, o {10}, o el conjunto vacío {} (es un conjunto con cero números naturales). Me gustan estos conjuntos ya que me gustan estos números... parecen ser "más reales que algunos reales"... esto me recuerda a una cita del matemático y lógico alemán Leopold Kronecker: "Dios sólo hizo a los naturales, todo lo demás es obra del hombre". En fin... Una "parte" de un conjunto X es un subconjunto de X. Por ejemplo, si X = {1,2,3}, entonces {2,3} es una parte de X, pero {3,5} NO es ya que 5 no está en la lista 1,2,3. Además, el conjunto vacío {} es parte de cualquier conjunto, y un conjunto siempre es parte de sí mismo. Representaremos a la colección de partes de un conjunto S como P(S). Pregunta: cuántas partes tiene X? O sea, cuántos elementos tiene P({1,2,3})? Contemos:

* Primero el conjunto vacío, 1.
* Contemos las partes de cardinal 1, {1}, {2}, {3}, son 3.
* Contemos las partes de cardinal 2, {1,2}, {1,3}, {2,3}, son 3.
* Contemos las partes de cardinal 3, {1,2, 3}, sólo 1.

En total: 1 + 3 + 3 + 1 = 2^3 = 8. Se observa la idea del planteo?

En general, supongamos que tenemos un conjunto finito S = {x1, x2, x3, ..., xn} cuyo cardinal es n (tiene n elementos). Cuántas partes tiene S? Respuesta: 2^n. La prueba es análoga a las anteriores, que demuestran que la cantidad de vértices de un cubo o la cantidad de mundos de una clase es una potencia de dos... se mantiene la naturaleza de recursividad, o de inducción...

Como existe una cantidad finita de partes, estas también pueden ser enumeradas. Vamos a usar una numeración bastante estándar, un algoritmo sencillo... para asignar un número a una parte T de S, empezamos asignando el valor 0 una variable r. Luego, recorremos todos los elementos de S, que son x1, ..., xn. Si i es tal que xi pertenece a T, le sumamos 2^i a r. Hago esto para todos los elementos xi de S. Finalmente, r será el número asignado a T. Por ejemplo, supongamos que S = {0,1,2} y T = {1,2}:

* Empezamos haciendo r = 0.
* x0 = 0 pertenece a S; pero está en T? NO, dejo r como está.
* x1 = 1 pertenece a S; pero está en T? SÍ, sumo 2^1 = 2 a r. r = 2.
* x2 = 2 pertenece a S; pero está en T? SÍ, sumo 2^2 = 4 a r. r = 6.

Resultado final: {2,3} tiene asignado el número r = 6. En general para este ejemplo tenemos 2^3 = 8 partes que se enumeran de la siguiente forma:

{} -> 0
{0} -> 1
{1} -> 2
{0, 1} -> 3
{2} -> 4
{0, 2} -> 5
{1, 2} -> 6
{0, 1, 2} -> 7

Se ve la relación entre conjuntos finitos de naturales, los cubos y las clases? Todo esto significa que dados un conjunto finito de cardinal n y un n-cubo, podemos asociar una parte a cada vértice del cubo... y podemos asociar un vértice a cada parte... y una parte a cada mundo... y un mundo a cada parte! Y aún más: podemos enumerar cada vértice, mundo o parte! En definitiva, existe la siguiente correlación:

Cubo........... Clase......... Conjunto finito
Vértice........ Mundo...... Parte (con su número natural asignado)
Dimensión... Grado....... Cardinal

Pero uno podría seguir creyendo que esta correspondencia es algo banal.

Vértices en el espacio.

No voy a profundizar en lo que es un espacio vectorial; sólo explicaré de forma sencilla qué es un vector: puede ser imaginado como un punto o vértice dentro de un espacio. En muchas ocasiones, quienes utilizamos el álgebra, nos enfrentamos a la tarea de trabajar con espacios de dimensión finita. Estos son, por ejemplo, los espacios unidimensionales, bidimensionales, tridimensionales (como lo es nuestro espacio físico), o tetradimensionales... en general, n-dimensionales, siendo n un número natural. En este artículo sólo mencionaremos espacios de dimensión finita.

Estos espacios son conjuntos de vectores (o vértices, o puntos); cada vector  ocupa un lugar distinto del espacio. Por lo tanto, si elegimos un punto de referencia, podemos concluir que cada vector tiene una posición. Esa posición puede ser representada mediante una lista (o tupla) de coordenadas, que son valores (en general numéricos) que codifican la posición del vector a lo largo de algún eje o dimensión.

Por ejemplo, supongamos que tenemos un espacio tridimensional V, formado por todos los vectores cuyas coordenadas son triplas de números enteros. Además, llamémosle "x" a la primera dimensión de V, "y" a la segunda, "z" a la tercera. Las siguientes son coordenadas de algunos vértices de V:

(1, 2, 3),
en este caso, la posición de nuestro punto a lo largo del eje x es 1, a lo largo del eje y es 2, para el eje z es 3.

(-1, 2, 3)
en este otro, la posición de nuestro punto a lo largo del eje x es -1, a lo largo del eje y es 2, para el eje z es 3. Notemos que este vector NO es el mismo que el anterior... su posición NO es la misma: que la coordenada x sea positiva o negativa significa que el punto está de un lado o del otro con respecto al plano formado por los ejes y, z.

(2, -3, 5)
este último caso representa al vector x=2, y=-3, z=5.

Notemos que, como NO puede haber dos puntos distintos en la misma posición, las coordenadas de un vector lo representan unívocamente. Por lo tanto, diremos que un vector es igual a su tupla de coordenadas. Por ejemplo, el vector (1,2,3) es el vector cuya posición es (1,2,3).

Para cerrar este apartado, observemos que un espacio de dimensión finita puede ser infinito. Por ejemplo, el espacio tridimensional conformado por "todas" las triplas de enteros es de dimensión finita (3); sin embargo hay una cantidad infinita de triplas de enteros. En los siguientes apartados, sólo nos concentraremos en espacios "totalmente" finitos.

Códigos lineales binarios.

Un código lineal binario (o para nosotros, simplemente "código") es un espacio vectorial finito (por ende, también de dimensión finita), constituido por tuplas de valores en {0, 1}. A cada vector se le llama palabra. Representaremos con Z(2,n) al código lineal binario de n dimensiones formado por todas las tuplas de valores {0, 1} y de longitud n.

Por ejemplo, las palabras (1,0,1), (0,0,1), (0,1,0), (0,0,0) pertenecen a Z(2,3), ya que son vectores de tres coordenadas {0, 1}. De hecho:

Z(2,3) = {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}.

Pudimos enumerar las palabras de Z(2,3) ya que el espacio tiene una cantidad determinada de elementos. En general, cuántas palabras hay en un código Z(2,n)? Respuesta: como siempre, 2^n. La prueba es muy sencilla: ya que Z(2,n) tiene TODAS las palabras de longitud n, una palabra w de Z(2,n) podría contener 0 ó 1 en cualquiera de sus coordenadas. O sea, podemos asignarle a w el 0 en la primera posición, o tal vez el 1; el 0 en la segunda, o quizá el 1; etc. En definitiva: podemos asignar uno de dos valores a cada coordenada. Eso nos da una cantidad 2*2*2*...*2 [n veces] = 2^n de combinaciones... por ende, 2^n palabras.

Cuando hablamos de conjuntos finitos en un apartado anterior, aprendimos que el conjunto de las partes de {0, 1, 2} (P({0,1,2})) tiene 2^3 = 8 elementos. Existirá una correlación entre P({0,1,2}) y Z(2,3)? Claro que sí: podemos asignar exactamente una palabra de Z(2,3) a cada parte de P({0,1,2}), de la siguiente manera:

sea w = (w0, w1, w2) una palabra de Z(2,3). Elegimos una parte X de P({0,1,2}) tal que X contenga 0 si y sólo si w0 = 1, que contenga 1 siempre y cuando w1 = 1 y que tenga a 2 si y sólo si w2 = 1. A esa parte X le asignamos w. Para ilustrar, damos las asignaciones de cada parte:

{} -> (0, 0, 0)
{0} -> (1, 0, 0)
{1} -> (0, 1, 0)
{2} -> (0, 0, 1)
{0, 1} -> (1, 1, 0)
{0, 2} -> (1, 0, 1)
{1, 2} -> (0, 1, 1)
{1, 2, 3} -> (1, 1, 1)

Pero, como cada parte tiene un número natural asignado, podemos asociar un número natural con cada palabra!:

  {} <-> (0, 0, 0) <-> 0
{0} <-> (1, 0, 0) <-> 1
{1} <-> (0, 1, 0) <-> 2
{2} <-> (0, 0, 1) <-> 4
{0, 1} <-> (1, 1, 0) <-> 3
{0, 2} <-> (1, 0, 1) <-> 5
{1, 2} <-> (0, 1, 1) <-> 6
{1, 2, 3} <-> (1, 1, 1) <-> 7

De hecho, para quienes conocen de la materia, las palabras y su número asociado son representaciones del mismo valor, sólo que una en binario (base 2) y la otra en decimal (base 10), respectivamente.

Estas cualidades no sólo se cumplen para n = 3, sino que para cualquier n natural! Por ende, tenemos la siguiente correlación:

Cubo........... Clase......... Conjunto finito......... Código
Vértice........ Mundo...... Parte......................... Palabra
Dimensión... Grado....... Cardinal................... Dimensión (del código)

Finalizando este artículo...

En definitiva, la tabla anterior resume íntimos paralelismos entre estructuras aparentemente distintas. Quizá en diversos ambientes sea conveniente considerar que cubos, clases, conjuntos finitos y códigos son "la misma cosa".

Por otro lado, ya que este artículo se me ha hecho algo extenso, dejaré los temas de distancia de Hamming, coloreo de grafos y ciclos de Hamilton para el futuro. Hay mucho más por descubrir detrás de la inocente traza de un discreto cubo.

Más info:
http://es.wikipedia.org/wiki/Politopo
http://es.wikipedia.org/wiki/Hipercubo
http://es.wikipedia.org/wiki/Grafo
http://es.wikipedia.org/wiki/Proposici%C3%B3n
http://es.wikipedia.org/wiki/N%C3%BAmero_natural
http://es.wikipedia.org/wiki/Leopold_Kronecker
http://es.wikipedia.org/wiki/Conjunto_enumerable
http://es.wikipedia.org/wiki/Recursividad
http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica
http://es.wikipedia.org/wiki/Algoritmo
http://es.wikipedia.org/wiki/Espacio_vectorial
http://es.wikipedia.org/wiki/V%C3%A9rtice_%28geometr%C3%ADa%29
http://en.wikipedia.org/wiki/Linear_code
http://es.wikipedia.org/wiki/Base_%28aritm%C3%A9tica%29

Mi música!

Algo de mi música (y con amigos). Lo seleccionado desde 2004 hasta 2010. ;)

Buscá...

Buscá y encontrá lo que quieras en alguno de mis espacios (La Mezcolanza, C^2 ó mi canal en Youtube) o en alguno de los sitios amigos.

Contate algo...