El Álgebra Abstracta es el estudio de los conjuntos que tienen uno o más operadores definidos sobre ese conjunto. Para nuestros propósitos, solo nos interesan los conjuntos donde el operador es un operador binario.
Dado un conjunto con un operador binario, podemos categorizar esos conjuntos basándonos en cómo se comporta el operador binario y qué elementos están permitidos (o se espera) que estén en el conjunto.
Los matemáticos tienen una terminología para cada posible comportamiento del operador binario en el conjunto. Como programadores aplicados, nuestra principal preocupación es el Grupo (de la Teoría de Grupos) en particular, pero avancemos hacia allí gradualmente. El grupo es solo un tipo de animal en este enorme zoológico. Así que en lugar de estudiar el grupo de forma aislada, estudiemos el grupo en su contexto más amplio de estructuras algebraicas relacionadas (es decir, conjuntos con un operador binario).
El álgebra abstracta es un campo enorme, pero nuestro objetivo aquí es entender claramente qué es un Grupo porque se usa en todas partes en las Pruebas de Conocimiento Cero (Zero Knowledge Proofs). Podríamos simplemente dar una definición ahora mismo:
Un Grupo es un conjunto con un operador binario que es cerrado, asociativo, tiene un elemento identidad, y donde cada elemento tiene un inverso.
Pero esa definición tan concisa no es muy esclarecedora. Es más útil entender los Grupos en su relación con el campo más amplio del Álgebra Abstracta.
Magma
Un Magma es un conjunto con un operador binario cerrado. Eso es todo.
Un Magma es definitivamente algo que entiendes de forma intuitiva como programador. Ahora tienes una palabra para ello.
Por ejemplo, considera el conjunto de todos los enteros positivos y que nuestro operador binario sea . Ten en cuenta que no permitimos números negativos porque si es negativo, obtenemos una fracción.
Claramente, el resultado estará en el espacio de los enteros. Nuestra función es un subconjunto del producto cartesiano (relación) de y . Específicamente, es una función de a .
Curiosamente, este ejemplo no es conmutativo ni asociativo. Puedes convencerte de esto eligiendo valores para a, b y c en el código Python a continuación.
assert a ** (b ** c) != (a ** b) ** c
assert a ** b != b ** a
Pero no nos importa. Un Magma es uno de los tipos de estructuras algebraicas menos restrictivos. Todo lo que importa es que el operador binario sea cerrado. Todo lo demás está permitido.
Una estructura algebraica es un conjunto con una colección de operaciones sobre ese conjunto. Para nuestros propósitos, la única operación que nos importa es un operador binario.
Semigrupo
Un Semigrupo es un Magma donde el operador binario debe ser asociativo.
Todos los Semigrupos son Magmas, pero no todos los Magmas son Semigrupos.
En otras palabras, un Semigrupo es un conjunto con un operador binario que es cerrado y asociativo.
Sea nuestro conjunto (infinito) el conjunto de todas las cadenas de texto no vacías posibles del alfabeto tradicional a, b, c,…, x, y, z. Por ejemplo, “az”, “programmer”, “zero”, “asdfghjk”, “foo” y “bar” están en este conjunto.
Sea nuestro operador binario la concatenación de cadenas. Esto es cerrado, porque produce otra cadena de texto en el conjunto.
Nota que si conmutamos “foo” y “bar”, la cadena de salida no será la misma, es decir, “foobar” y “barfoo”. Sin embargo, eso no importa. Tanto “foobar” como “barfoo” son miembros del conjunto, por lo que el operador binario “concatenar” es cerrado. Como tenemos un conjunto con un operador binario cerrado y asociativo, el conjunto de todas las cadenas bajo concatenación es un Semigrupo.
Ejercicio: Comprueba por ti mismo que concatenar “foo”, “bar”, “baz” en ese orden es asociativo. Recuerda, asociativo significa , donde es el operador binario del Semigrupo.
Ejercicio: Da un ejemplo de un Magma y de un Semigrupo. El Magma no debe ser un Semigrupo. No uses los ejemplos anteriores. Esto significa que debes pensar en un operador binario que sea cerrado pero no asociativo para el Magma, y para el Semigrupo, el operador binario debe ser cerrado y asociativo.
Monoide
Un Monoide es un Semigrupo con un elemento identidad.
Ah, sí, este es el mismo Monoide de “A monad is a monoid in the category of endofunctors.”
Si miramos la documentación de monoide en la biblioteca Cats para Scala, vemos estas definiciones explícitamente:
trait Semigroup[A] {
def combine(x: A, y: A): A
}
trait Monoid[A] extends Semigroup[A] {
def empty: A
}
La biblioteca Cats simplemente se refiere a la identidad como empty y al operador binario como combine. El hecho de que Monoid extienda a Semigroup muestra que un Monoide es un Semigrupo con el requisito de que tiene un “vacío” (identidad).
El fragmento de código anterior no lo muestra, pero efectivamente se requiere que combine sea asociativo.
Un Semigrupo solo tiene un operador binario sin restricciones sobre él, excepto que devuelve el mismo tipo (A) que las entradas (x e y).
Por ejemplo, la suma sobre enteros positivos sin incluir el cero es un Semigrupo, pero si incluyes el cero, se convierte en un Monoide.
Un elemento identidad significa que si aplicas un operador binario con el elemento identidad y otro elemento , obtienes . En el ejemplo de la suma , donde es el elemento identidad. Si tu operador binario es la multiplicación, entonces el elemento identidad sería , ya que multiplicar por devuelve el mismo número.
Si nuestro conjunto es el conjunto de todas las matrices de y nuestro operador binario es la multiplicación de matrices, el elemento identidad sería la matriz identidad
Conjuntos de conjuntos bajo unión e intersección
Algo extrañamente ausente en nuestra discusión anterior sobre conjuntos fue la mención de la unión y la intersección de conjuntos. Estos son operadores binarios, y ahora es un buen momento para introducirlos.
Si tomas la unión de dos conjuntos y , obtienes . Si tomas la intersección de y , obtienes .
Debería ser evidente que ambos de estos operadores son asociativos.
Si definimos nuestro dominio como el conjunto de todos los conjuntos finitos de enteros, entonces los operadores binarios de unión e intersección son cerrados porque su resultado es un conjunto de enteros.
La unión de conjuntos tiene un elemento identidad en este dominio: el conjunto vacío . Toma la unión de un conjunto con el conjunto vacío y obtienes el conjunto original, es decir, .
Por lo tanto, el conjunto de todos los conjuntos finitos de enteros bajo la unión es un Monoide.
Sin embargo, el conjunto de todos los posibles conjuntos finitos de enteros bajo la intersección (), es un Semigrupo: ningún conjunto finito funcionará como identidad. Pero si expandimos este conjunto para incluir el propio —es decir, nuestro conjunto es bajo la intersección— entonces se convierte en un Monoide, ya que es el elemento identidad.
Si parece que introdujimos el elemento identidad con un “hack”, es porque lo hicimos.
Veremos más adelante que las curvas elípticas usan un truco como este e incluyen un punto especial llamado el “punto en el infinito” para mantenerse consistentes con las leyes algebraicas. El punto es que necesitamos tener muy claro cuál es nuestro elemento identidad si decimos que un conjunto es un Monoide bajo algún operador binario.
Como otro ejemplo, podríamos decir que nuestro conjunto son todos los enteros positivos bajo la suma, con el elemento adicional . Definimos y . Como arquitectos de los sistemas, tenemos permitido hacer que nuestro conjunto consista de lo que queramos, y que el operador binario se comporte como queramos. Sin embargo, el operador binario debe ser cerrado, asociativo y el conjunto debe tener un elemento identidad para que esa estructura de datos algebraica sea un Monoide.
Si restringimos el dominio para que sean todos los subconjuntos de , entonces la intersección claramente se convierte en un Monoide porque el elemento identidad sería , ya que cualquier conjunto de enteros que intersectes con él producirá el otro conjunto, es decir, . Por ejemplo, .
Llegados a este punto debería estar claro que la categoría de una estructura algebraica para un operador binario dado es muy sensible al dominio del conjunto.
Ejercicio: Sea nuestro operador binario la función min(a,b) sobre los enteros. ¿Es un Magma, Semigrupo o Monoide? ¿Qué pasa si restringimos el dominio para que sean los enteros positivos (cero o mayores)? ¿Qué pasa con el operador binario max(a,b) sobre esos dos dominios?
Ejercicio: Sea nuestro conjunto todos los números binarios de 3 bits (un conjunto de cardinalidad 8). Sean nuestros posibles operadores binarios bit-wise and, bit-wise or, bit-wise xor, bit-wise nor, bit-wise xnor, y bit-wise nand. Claramente esto es cerrado porque la salida es un número binario de 3 bits. Para cada operador binario, determina si el conjunto bajo ese operador binario es un Magma, Semigrupo o Monoide.
Grupo - La Estrella del Espectáculo
Un Grupo es un Monoide en el que cada elemento tiene un inverso.
O para ser explícitos, es un conjunto con cuatro propiedades:
- El operador binario es cerrado (Magma)
- El operador binario es asociativo (Semigrupo)
- El conjunto tiene un elemento identidad (Monoide)
- Cada elemento tiene un inverso
Es decir, para cualquier elemento en el conjunto , existe un tal que donde es el elemento identidad y es el operador binario. Dicho de forma más matemática, esto sería:
Aquí, es el operador binario del conjunto.
Es bastante incorrecto decir “el conjunto tiene un inverso”. Para ser precisos, cada elemento tiene otro elemento en el conjunto que es el inverso de ese elemento.
Usando los enteros con la suma, el elemento identidad es el cero (porque si sumas cero, obtienes el mismo número de vuelta), y el inverso de un entero es ese entero con el signo invertido (por ejemplo, el inverso de es y el inverso de es ).
Volviendo a la sensibilidad del dominio, la suma sobre los enteros positivos no es un grupo porque no puede haber elementos inversos.
Aquí tienes una tabla para dejar el punto claro:
| dominio del conjunto | operador binario | estructura algebraica | razón |
|---|---|---|---|
| enteros positivos distintos de cero | suma | Semigrupo | sin identidad |
| enteros positivos incluyendo el cero | suma | Monoide | tiene identidad, sin inversos |
| todos los enteros | suma | Grupo | cada elemento tiene un inverso |
Nota que “inverso” no tiene sentido si el conjunto no tiene una identidad. Por definición, aplicar el operador binario a un elemento y al inverso de ese elemento da como resultado el elemento identidad.
Ejercicio: ¿Por qué las cadenas de texto bajo concatenación no pueden ser un grupo?
Ejercicio: Los polinomios bajo la suma satisfacen las propiedades de un grupo. Demuestra que este es el caso comprobando que cumplen con todas las propiedades que definen a un grupo.
Lamentablemente, nuestro tutorial debe terminar aquí, porque la teoría de grupos elemental es el tema de otro capítulo.
Pero ¡ahora tienes mucho contexto para entender qué es un grupo a pesar de que apenas lo hayamos discutido aquí!
Unas palabras sobre la conmutatividad
No se requiere que ninguna de las estructuras de datos algebraicas anteriores sea conmutativa. Si lo son, decimos que son abelianas bajo su operador binario. En este contexto, “abeliano” significa que el operador binario es conmutativo, lo que significa que el orden de los operandos no afecta al resultado.
Abeliano significa que el operador binario es conmutativo.
Pero di abeliano, sonarás más inteligente.
El tecnicismo es que normalmente no decimos “la suma es abeliana” sino “el grupo es abeliano bajo la suma”.
Subconjuntos de nuevo
Enlacemos todo esto con lo que aprendimos al principio. Los Magmas, Semigrupos, Monoides y Grupos son todos conjuntos que tienen un operador binario cerrado. Un operador binario es simplemente una aplicación (map) desde todos los pares ordenados del producto cartesiano del conjunto consigo mismo, de vuelta hacia sí mismo.
Los Grupos son un subconjunto de los Monoides, los Monoides son un subconjunto de los Semigrupos, los Semigrupos son un subconjunto de los Magmas y los Magmas son un subconjunto de los conjuntos en general. Todo Grupo es también un Magma o un conjunto, pero un Magma no es necesariamente un Grupo.
Los “conjuntos” son fáciles de conceptualizar, pero cuando empezamos a hablar de grupos y otras estructuras algebraicas, es fácil empezar a perderse. Los Grupos son muy importantes en nuestro estudio de la criptografía. Solo recuerda:
Los Grupos son conjuntos con un operador binario que sigue cuatro reglas.
Además, es hora de liberar tu mente de que “la suma” y “la multiplicación” sean la principal forma de combinar cosas.
Tenemos permitido tomar un producto cartesiano de un conjunto (que podría ser cualquier cosa) consigo mismo y luego aplicar (map) ese conjunto de pares ordenados de vuelta al conjunto. Esto es un operador binario. Si sigue la construcción anterior, entonces es cerrado.
El vocabulario matemático no tiene por qué asustarnos
Antes de que comenzaras este tutorial, la frase
“El conjunto de cadenas de texto bajo el operador binario de concatenación de cadenas es un Semigrupo o un Monoide dependiendo de la presencia o ausencia de la cadena vacía en el conjunto”
probablemente no tenía sentido.
Puede que aún tengas que traducir eso en tu cabeza como la mayoría de los estudiantes de un segundo idioma, pero te das cuenta de que en realidad está comprimiendo mucha información en un espacio muy pequeño.
¿Podría decir esa frase sin tantos términos matemáticos? Por supuesto que sí, pero me tomaría al menos 500 palabras hacerlo claramente. Realmente vale la pena entender lo que significan esos términos. Esto nos ahorrará muchos problemas a largo plazo.
Lo que lo hace genial es que hay una plétora de teoremas sobre los Grupos que nos permiten hacer afirmaciones sobre el grupo sin entender cómo funciona internamente el operador binario del grupo. Esto es en cierta forma análogo al polimorfismo en la programación orientada a objetos o a los traits en los lenguajes funcionales. Ocultan los detalles de implementación y te permiten centrarte en el nivel alto. Eso es poderoso.
En el próximo capítulo, aprenderás cómo los grupos pueden estar “relacionados” entre sí a través de homomorfismos.
Aprende más con RareSkills
Consulta nuestro Zero Knowledge Course para aprender con nuestra comunidad.
Nuestro ZK Book contiene el resto de los tutoriales de ZK en esta serie.
Publicado originalmente el 25 de julio de 2023