¿Por qué otro tutorial sobre teoría de conjuntos?

El público objetivo de este artículo es el tipo de personas a las que no les importa la matemática abstracta a menos que vean un caso de uso directo para ella. Quieren obtener las partes esenciales que necesitan y seguir adelante. Este artículo atiende a esa audiencia.

Nuestro objetivo final es entender el álgebra abstracta porque el álgebra abstracta tiene muchos conceptos que pueden llamarse propiamente “útiles”, pero el álgebra abstracta depende en gran medida de la teoría de conjuntos.

Nuestro objetivo aquí es tomar el camino más directo a través de la teoría de conjuntos hacia el álgebra abstracta, de tal manera que entendamos toda la terminología y los conceptos con los que lidiaremos.

Los ingenieros generalmente no están interesados en coleccionar abstracciones o demostrar teoremas, quieren lanzar productos teniendo una comprensión suficientemente profunda del tema para no crear errores o ineficiencias involuntariamente. Adquirir conocimientos que no ayudan directamente en esta misión se considera una pérdida de tiempo.

Para optimizar este objetivo, he omitido deliberadamente cualquier aspecto de la Teoría de Conjuntos que no sea directamente útil para comprender los aspectos relevantes del álgebra abstracta. En consecuencia, este recurso sobre teoría de conjuntos no es exhaustivo por diseño.

Motivación de la Teoría de Conjuntos para los Zero Knowledge Proofs

El propósito de este tutorial es brindarle una comprensión sólida de lo que es un operador binario en el contexto de la Teoría de Conjuntos.

El concepto de un operador binario se encuentra en el núcleo de la Teoría de Grupos, y la Teoría de Grupos se usa en todas partes en los Zero Knowledge Proofs.

Nuestro tratamiento no es riguroso

Algunos matemáticos podrían horrorizarse de que no discuta los axiomas de la teoría de conjuntos aquí. Esto es una característica, no un error. Si quieres una demostración para algo, pregúntale a Google o a un chatbot (o mejor aún, resuélvelo por tu cuenta). Los conceptos discutidos aquí han sido demostrados rigurosamente hasta el cansancio durante más de un siglo.

La teoría de conjuntos no es difícil (al menos si te saltas la redacción de demostraciones, las demostraciones de teoría de conjuntos pueden ser sorprendentemente difíciles cuando se hacen por primera vez). Probablemente ya entiendas la teoría de conjuntos de forma intuitiva, y casi con seguridad has usado conjuntos en tu código, tal vez para eliminar rápidamente duplicados en un array. Sin embargo, necesitamos ponerle lenguaje a esta intuición y hacer explícita nuestra comprensión intuitiva.

Aprender matemáticas abstractas es como aprender un lenguaje humano. Puedes aprender el vocabulario (a qué se refieren las palabras) y la gramática (cómo se combinan de manera válida). Usando esa analogía, ponemos un gran énfasis en el vocabulario sobre la gramática. Hay una buena razón para esto.

Si entras a una tienda en un país extranjero y preguntas el equivalente a “¿los panes para ser comprar para mí dónde?”, el dependiente puede ayudarte aunque tu gramática sea horriblemente incorrecta. Pero si dominas la gramática y no conoces el vocabulario, tu conocimiento se vuelve inútil. Puedes formar una oración perfecta, pero si no puedes referirte de manera sucinta a “pan” y “comprar”, tu viaje a la tienda no será un éxito (no inventé esta analogía, pero lamentablemente no recuerdo dónde la vi por primera vez).

Por lo tanto, apenas rasguñaremos la gramática (demostraciones y teoremas) y enfatizaremos el vocabulario de las matemáticas abstractas (que es muy útil para navegar en este país extranjero).

Algunos tipos de conocimiento solo pueden adquirirse por experiencia, no por explicación.

Por lo tanto, deberías hacer los ejercicios de este texto. No te preocupes, no escribirás demostraciones, solo es para asegurarte de que realmente interiorizaste lo que acabas de leer.

No dejes que la relativa brevedad de este texto te engañe. Te tomará al menos una tarde (o dos, tal vez tres) completarlo si realmente haces los ejercicios. Si una determinada sección no tiene sentido, consulta en internet o a un chatbot para obtener explicaciones alternativas de ese subtema.

Definición de un conjunto

Un conjunto es una colección bien definida de objetos. Estos objetos podrían ser cualquier cosa y las reglas que aprendemos de la teoría de conjuntos se aplican a ellos.

Los números enteros, los números racionales, los números reales, los números complejos, las matrices, los polinomios, los polígonos y muchas otras cosas tienen algo en común: todos son conjuntos.

Existe una regla bien definida que decide si algo es miembro del conjunto o no. No entraremos en detalles, pero está claro que un polígono no es un polinomio, y un polinomio no es una matriz, etc.

Se permite que los conjuntos estén vacíos. A esto lo llamamos el conjunto vacío.

Por definición, los conjuntos no contienen elementos duplicados. Por ejemplo, $\set{a, a, b}$ es en realidad solo $\set{a, b}$.

Ejercicio: Asume que tienes una definición adecuada para los números enteros. Crea un conjunto bien definido de números racionales.

Superconjuntos y subconjuntos

Cuando observamos los números enteros y los números racionales, parece haber una relación entre algunos de ellos. Específicamente, todos los números enteros son números racionales, pero no todos los números racionales son enteros. La relación entre ellos es que los números enteros son un subconjunto de los números racionales. Por otro lado, los números racionales son un superconjunto de los números enteros.

Un subconjunto no necesita ser estrictamente más pequeño que el conjunto al que pertenece. Por ejemplo, es perfectamente válido decir que el conjunto de los números enteros es un subconjunto de sí mismo.

La definición precisa para la relación entre números enteros y números racionales es un subconjunto propio, es decir, existen números racionales que no son enteros.

Ejercicio: Define la relación de subconjunto entre números enteros, números racionales, números reales y números complejos.

Ejercicio: Define la relación entre el conjunto de números trascendentales y el conjunto de números complejos en términos de subconjuntos. ¿Es un subconjunto propio?

Igualdad de conjuntos

Se define que los conjuntos son iguales si contienen los mismos elementos, independientemente del orden en que aparezcan esos elementos. Por ejemplo, $\{4, 2, 5\}$ es el mismo conjunto que $\{2, 5, 4\}$. Al hacer demostraciones formales para conjuntos, decimos que si $A$ es un subconjunto de $B$ y $B$ es un subconjunto de $A$, entonces $A = B$. O en una notación más matemática: $A = B \iff A \subseteq B$ y $B \subseteq A$. Eso se lee como $A = B$ si y solo si $A$ es un subconjunto de $B$ y $B$ es un subconjunto de $A$.

Cardinalidad

En algunos de nuestros ejemplos anteriores, hay un número infinito de enteros, números racionales y otros conjuntos similares. Sin embargo, también podemos definir conjuntos de forma finita, como los números $\set{0,1,2,3,4,5,6,7,8,9,10}$. La cardinalidad del conjunto anterior es $11$. Si $A = \set{5,9,10}$, entonces $|A| = 3$, donde las dos barras verticales alrededor de la A significan cardinalidad.

Existen diferentes niveles de infinito en la teoría de conjuntos. Por ejemplo, hay infinitamente más números reales que números enteros. Específicamente, decimos que los números enteros son infinitos numerables porque literalmente puedes contarlos. Pero no hay forma de empezar a contar los números reales, los cuales son infinitos no numerables.

Ejercicio: Usando la definición formal de igualdad anterior, argumenta que si dos conjuntos finitos tienen diferente cardinalidad, no pueden ser iguales. (Demostrar esto para conjuntos infinitos es un poco más complicado, así que lo omitiremos).

Letras elegantes de pizarra

Debido a que “los enteros como conjunto” y “los números reales como conjunto” se usan con tanta frecuencia, existe una taquigrafía matemática de aspecto intimidante para ello.

• El símbolo $\mathbb{N}$ es el conjunto de los números naturales $(1,2,3,…)$. Definitivamente no incluye números negativos, pero si incluye o no al cero depende de con quién estés hablando.
• El símbolo $\mathbb{Z}$ es el conjunto de todos los números enteros (porque “zahlen” significa entero en alemán)
• El símbolo $\mathbb{Q}$ es el conjunto de todos los números racionales. Los números racionales son aquellos que pueden expresarse como el cociente o fracción de $p$ sobre $q$ como $\frac{p}{q}$ de dos enteros, un numerador $p$ y un denominador no nulo $q$). A partir de esta definición, es fácil ver de dónde proviene el símbolo $\mathbb{Q}$.
• El símbolo $\mathbb{R}$ es el conjunto de todos los números reales, porque la R significa real. Obvio.
• El símbolo $\mathbb{C}$ es el conjunto de todos los números complejos por razones igualmente obvias.

A veces la gente escribe $\mathbb{R}^2$ como un vector de dos números reales, por lo que $a \in \mathbb{R}^2$ significa que $a$ es un vector 2D. Recomiendo escribirlo de la segunda forma porque es más concisa y también te hace lucir más inteligente.

Pares ordenados

Aunque los conjuntos no tienen un orden inherente, un nuevo tipo de estructura de datos llamado par ordenado puede surgir de conjuntos de conjuntos. Por ejemplo, $(a, b)$ es un par ordenado mientras que $\{a, b \}$ es un conjunto.

Los programadores solemos pensar en un par ordenado como una tupla. Decimos que dos pares ordenados son iguales en el mismo sentido en que decimos que dos tuplas son iguales.

¿Cómo creamos orden a partir de algo que es inherentemente no ordenado?

El detalle de implementación clave es que representamos $(a, b)$ en forma de conjunto como $\set{a, \set{b}}$. Podemos hacer esto porque podemos definir nuestro conjunto para que contenga letras o un conjunto de cardinalidad uno que contenga una letra. Es por esto que podemos decir que $(a, b) \neq (b, a)$ porque $\set{a, \set{b}} \neq \set{b, \set{a}}$. No nos preocuparemos más por este detalle de implementación.

Al igual que en otros lenguajes de programación, nuestro par ordenado puede ser arbitrariamente largo; por ejemplo, $(a,b,c,d)$ es válido. También podemos codificar un par ordenado que contiene un par ordenado como $((a, b), c)$, lo cual será útil más adelante.

Producto cartesiano

Debido a que los conjuntos están bien definidos, podemos definir un conjunto tal que cada elemento de un conjunto sea una parte de un par ordenado con un elemento de otro conjunto. Por ejemplo, si $A = {1,2,3}$ y $B = {x, y, z}$, entonces el producto cartesiano $A \times B$ es el conjunto $\{(1, x), (1, y), (1, z), (2, x), …, (3, z)\}$. Esto también se puede representar como una tabla:

Los productos cartesianos no son conmutativos, como demostrará el siguiente ejercicio. Conmutativo significa que $B \times A = A \times B$ en el caso general.

Ejercicio: Calcula el producto cartesiano de $B \times A$ usando las definiciones anteriores.

Los subconjuntos del producto cartesiano forman una función

¿Qué pasaría si quisiéramos decir que tenemos una función

(Elegí este ejemplo en desorden para hacerlo un poco más interesante).

Podemos definir un conjunto que defina este mapeo. Simplemente tomamos un subconjunto de nuestro producto cartesiano anterior para incluir $(1, y)$, $(2, z)$ y $(3, x)$.

En términos teóricos de conjuntos, una función es un subconjunto del producto cartesiano del conjunto dominio y el conjunto codominio.

Para nuestro ejemplo de $1$ mapeando a $y$, $2$ mapeando a $z$ y $3$ mapeando a $x$, el subconjunto del producto cartesiano se muestra en negrita a continuación:

Por lo tanto, nuestra función está definida por el conjunto $\{(1, y), (2, z), (3, x)\}$.

Para definir una función, necesitamos el conjunto desde el que comenzamos y el conjunto en el que terminamos. Tomamos el producto cartesiano de estos dos conjuntos, lo que resulta en cada asignación posible desde el conjunto de entrada al conjunto de salida. Luego tomamos el subconjunto del producto cartesiano para definir la función como queramos. Al tratar con conjuntos infinitos como los números enteros, no nos molesta no poder enumerar explícitamente todos los puntos ordenados.

Las funciones no son necesariamente computables

Una nota muy importante es que los matemáticos rara vez se preocupan por la computabilidad. Una función es un mapeo entre conjuntos. Cómo se calcula esa función, si es que siquiera es posible calcularla con una computadora razonable, no es una preocupación de la mayoría de los matemáticos.

Aquí es donde los programadores a veces se confunden. A menudo solo piensan en las funciones como algo que puede calcularse eficientemente con líneas de código. Aunque es útil, esto limita nuestra comprensión de las propiedades generales de las funciones.

La razón por la que enfatizo esto es que en los Zero Knowledge Proofs, vamos a tratar con funciones que son de un nivel mucho “más alto” que insertar un argumento en una función y obtener un valor de retorno. Necesitamos ser capaces de apreciar el “panorama general” de las funciones. Son un mapeo de un conjunto a otro conjunto. Y un mapeo entre conjuntos surge al tomar un subconjunto de su producto cartesiano.

Funciones con dominios y codominios disímiles

Específicamente, vamos a estar saltando entre enteros, polinomios, matrices, curvas elípticas en una dimensión, luego curvas elípticas en otra dimensión, y así sucesivamente.

Te marearás mucho intentando conceptualizar esto a menos que entiendas a un nivel fundamental que, por la Teoría de Conjuntos, ¡se nos permite definir saltos como queramos!

Por supuesto, la forma en que mapeemos el salto tendrá un fuerte efecto en su utilidad; si mapeamos todo a cero, ese es un mapa válido, pero no muy útil.

Quiero que entiendas desde el principio que no estamos haciendo nada raro cuando nos transportamos entre universos de esta manera.

Al final del día, se nos permite tomar dos conjuntos cualesquiera que queramos, crear un nuevo conjunto tomando su producto cartesiano, tomar un subconjunto de ese conjunto de pares ordenados, y boom, tenemos un mapeo.

Axioma de elección

Si estás pensando “espera un momento, ¿puedo simplemente elegir un subconjunto y definir la función como yo quiera?”, no estás solo al preguntarte esto. Si quieres adentrarte en la madriguera del conejo, en realidad hemos estado discutiendo el axioma de elección todo este tiempo, y ha sido objeto de controversia a pesar de que la definición parece no ser controvertida:

El producto cartesiano de una colección de conjuntos no vacíos es no vacío.

Los subconjuntos del producto cartesiano forman una función: ejemplo

Definamos un mapeo entre números reales no negativos (cero o mayores) y enteros no negativos (cero o mayores) usando la función piso. La función piso simplemente elimina la porción decimal de un número. No podemos mostrar todos los números reales (o enteros), pero podemos crear un boceto.

Cuando hacemos $\mathbb{R}\times\mathbb{Z}$ y tomamos un subconjunto, simplemente elegimos los pares ordenados que corresponden a tomar el piso del elemento de los números reales. Los pares ordenados que no mostramos en la tabla son pares ordenados que no están en nuestro subconjunto que define el mapeo. Por ejemplo, $2$ no es el piso de $500.3$, por lo que ese par ordenado $(500.3, 2)$ no se incluye.

Ejercicio: Define un mapeo (función) desde los enteros $\{1,2,3,4,5,6\}$ al conjunto $\{\text{even}, \text{odd}\}$.

Ejercicio: Toma el producto cartesiano de los polígonos $\{\text{triangle}, \text{square}, \text{pentagon}, \text{hexagon}, \text{heptagon}, \text{octagon}\}$ y el conjunto de enteros $\{0,1,2,…,8\}$. Define un mapeo tal que el polígono se mapee a un número entero que represente el número de lados. Por ejemplo, el par ordenado $(\Box, 4)$ debería estar en el subconjunto, pero $(\bigtriangleup, 7)$ no debería estar en el subconjunto del producto cartesiano.

Ejercicio: Define un mapeo entre enteros positivos y números racionales positivos (no la totalidad, obviamente). Es posible mapear perfectamente los enteros a los números racionales. Pista: dibuja una tabla para construir números racionales donde las columnas son los numeradores y las filas son los denominadores. Lucha con esto por al menos 15 minutos antes de buscar la respuesta.

Subconjuntos válidos e inválidos del producto cartesiano.

Hay una restricción importante sobre cómo elegimos nuestro subconjunto. Por ejemplo, el siguiente subconjunto del producto cartesiano $\{1,2,3\}$, $\{p,q,r\}$ no es válido porque $1$ mapea a $p$ y $1$ mapea a $q$. Al definir una función con un producto cartesiano, el mismo elemento del dominio no puede mapearse a dos elementos diferentes del codominio.

Un producto cartesiano de un conjunto consigo mismo

No debería sorprender que en lugar de hacer un producto cartesiano entre $A$ y $B$, puedas hacer un producto cartesiano entre $A$ y $A$. Esto es simplemente mapear un conjunto a sí mismo.

Este es el primer paso de una forma más abstracta de lo que tradicionalmente pensamos como funciones sobre enteros.

Por ejemplo, $y=x^2$ (sobre enteros positivos) puede visualizarse en términos teóricos de conjuntos como el subconjunto de $\mathbb{Z}\times\mathbb{Z}$:

Relaciones de conjuntos

La frase “tomar un subconjunto del producto cartesiano” es tan común que tenemos una palabra para ello. Es una relación.

Una relación puede ser desde un producto cartesiano de un conjunto consigo mismo o de un conjunto con otro conjunto. Si tenemos dos conjuntos $A$ y $B$ ($B$ puede o no ser igual a $A$ sin pérdida de generalidad), y tomamos un subconjunto de $A \times B$, entonces decimos que un elemento $a$ de $A$ está relacionado con un elemento $b$ de $B$ si hay un par ordenado $(a, b)$ en el subconjunto de $A \times B$.

En el ejemplo de $y=x^2$, $2$ de $X$ está relacionado con $4$ de $Y$, pero $3$ en $X$ no está relacionado con $6$ de $Y$.

Un “operador binario” en términos teóricos de conjuntos

Un operador binario es una función de $A \times A \rightarrow A$. Básicamente, tomamos cada par posible de $A \times A$ (el producto cartesiano de $A$ consigo mismo) y lo mapeamos a un elemento en $A$. En otras palabras, es una relación de conjuntos entre $A \times A$ y $A$.

Aquí hay algunos ejemplos básicos de operadores binarios:

• suma de enteros toma dos elementos cualesquiera del conjunto de números enteros y súmalos, obtienes otro elemento del conjunto de números enteros. Aquí, hemos mapeado un par de enteros a otro entero. Por ejemplo, $(1, 3)$ mapea a $4$.
• multiplicación de racionales toma dos números racionales cualesquiera, multiplícalos, obtienes otro número racional. Por ejemplo, $(3.5, 2.0)$ mapea a $7.0$.
• concatenación de cadenas toma cualquier par de cadenas del conjunto de cadenas, concaténalas, y el resultado es otra cadena. Por ejemplo, $(\text{Rare},\text{Skills})$ mapea a $\text{RareSkills}$. A diferencia de los dos ejemplos anteriores, el orden de las cadenas en el par cambia la cadena final a la que se mapea el par. Por ejemplo, $(\text{Rare},\text{Skills})$ mapea a la cadena $\text{RareSkills}$ pero $(\text{Skills},\text{Rare})$ mapea a la cadena $\text{SkillsRare}$

Construyendo un Operador Binario en la Teoría de Conjuntos

Usemos un ejemplo del conjunto $\set{0,1,2}$ con operador binario adición módulo $3$. Primero tomamos el producto cartesiano del conjunto consigo mismo (es decir, $A \times A$):

Luego tomamos el producto cartesiano de este nuevo conjunto de pares con el conjunto original

Y luego tomamos el subconjunto de eso que define nuestro operador binario adición módulo $3$:

Observa que si sumamos los valores dentro de la “tupla interna” módulo $3$ obtenemos el tercer número en la tupla. Por ejemplo, en la fila inferior, vemos que $2 + 2 = 1 \pmod 3$.

Las funciones generalmente “existen” – pero la computabilidad es otra historia

Pensar en las funciones como un subconjunto de un producto cartesiano puede resultar un poco raro al principio, especialmente porque tales definiciones no se traducen fácilmente en código.

Pero el ZK está fuertemente influenciado por las definiciones matemáticas, por lo que es útil tener este vocabulario en nuestro arsenal.

Es útil conceptualizar las funciones como un mapa que toma un elemento de un conjunto y devuelve un elemento en otro conjunto.

Ejercicio: Elige un subconjunto de pares ordenados que defina $a \times b \pmod 3$.

Ejercicio: Define nuestro conjunto $A$ como los números $\set{0,1,2,3,4}$ y nuestro operador binario como la resta módulo $5$. Define todos los pares ordenados de $A \times A$ en una tabla, luego mapea ese conjunto de pares ordenados a $A$.

Un operador binario cerrado toma dos elementos cualesquiera de un conjunto y emite otro elemento del mismo conjunto. La parte de cerrado es importante, ya que restringe la salida a estar en el mismo conjunto.

Específicamente, comienza con un conjunto $A$ y construye un operador binario de la siguiente manera:

Toma un producto cartesiano de un conjunto consigo mismo, $A \times A$ y llama a este conjunto de pares ordenados $P$.

Toma el producto cartesiano de $P$ con $A$ y toma un subconjunto de eso tal que $P\times A$ esté bien definido.

La división sobre los números enteros no es un operador binario porque lo que realmente sucede es que hacemos el $P = (\mathbb{Z} \times \mathbb{Z})$ y luego tomamos un subconjunto de $P \times \mathbb{Q}$ para obtener nuestra relación. La división sobre enteros no es cerrada porque puede producir números racionales.

Vamos a lidiar mucho con operadores binarios en curvas elípticas, números enteros, polinomios, matrices, etc.

Cuando podemos confiar en que el operador binario tendrá ciertas propiedades, entonces podemos abstraer muchos detalles de implementación.

Por ejemplo, “sumar” puntos de una curva elíptica no es exactamente trivial, y las matemáticas no son obvias desde el principio.

Sin embargo, si sabes que el operador binario es cerrado y sigue ciertas propiedades, ¡entonces no importa cómo esté implementada la “suma”! ¡Es un mapa que sigue ciertas reglas!

Usemos un ejemplo un poco más cercano. Si multiplicas dos matrices cuadradas de determinante $1$, el determinante de la matriz producto también será $1$. La demostración no es algo que puedas resolver rápidamente en tu cabeza. Pero si modelas esto como un “conjunto de matrices de $3\times 3$ con determinante $1$ y un operador binario multiplicar, y el multiplicar es cerrado”, entonces de repente tienes un gran conocimiento funcional de un sistema del que no conoces los detalles de implementación. Sabes que no importa lo que hagas, obtendrás una matriz de determinante $1$ sin tener que saber por qué.

Tener el lenguaje para describir un operador binario como “cerrado” te permite operar a un nivel más alto y comprender el panorama general de las transformaciones sin empantanarte en los detalles de implementación.

¡Puedes razonar sobre operaciones sin entender cómo funcionan! Esto es extremadamente útil cuando se trata de matemáticas muy esotéricas como los emparejamientos bilineales de curvas elípticas.

Construyendo operaciones binarias válidas

Cuando se trata de operadores binarios, no se nos permite tomar un subconjunto de $A \times A$ antes de mapearlo a $A$. Los operadores binarios deben aceptar todos los miembros del conjunto $A$ como sus entradas. Por supuesto, debemos tomar un subconjunto de los pares ordenados entre $A \times A$ y $A$ porque cada par de $A \times A$ debe mapearse exactamente a un $A$. El resultado de una operación binaria debe tener una respuesta inequívoca.

Aprende más con RareSkills

La utilidad del vocabulario del álgebra abstracta es la razón por la que nuestro curso de Zero Knowledge no esquiva las matemáticas. Simplemente nos aseguramos de dominar nuestro vocabulario esencial antes de comenzar a usarlo.

Publicado originalmente el 25 de julio de 2023