Guía de Estudio: Relaciones

Este documento sirve como una introducción didáctica al concepto de relaciones en matemáticas discretas, sus propiedades y las estructuras que forman, como las relaciones de equivalencia y de orden.

¿Qué es una Relación Binaria?

Definición Inicial

Una relación es, simplemente, una regla que describe cómo dos (o más) objetos están conectados o asociados entre sí. En nuestra vida diaria, usamos relaciones constantemente: “es amigo de”, “es mayor que”, “es familiar de” o “está en la misma ciudad que”. En matemáticas, formalizamos esta idea de “conexión”.

Explicación Didáctica

Imagina que tienes dos cajas. La Caja A contiene nombres de personas: {Ana, Beto, Carla}, y la Caja B contiene nombres de mascotas: {Fido, Miau, Nube}. Queremos describir la relación “es dueño de”.

Esta relación no es más que un conjunto de “cables” que conectan a una persona con su mascota. Si Ana es dueña de Miau, y Beto es dueño de Fido y Nube, la relación R (“es dueño de”) es el conjunto de esos cables:

$R = \{(\text{Ana, Miau}), (\text{Beto, Fido}), (\text{Beto, Nube})\}$

Cada cable es un par ordenado. El primer elemento viene de la Caja A y el segundo de la Caja B. El conjunto de todos los pares posibles (Ana con Fido, Ana con Miau, Ana con Nube, Beto con Fido, etc.) se llama el producto cartesiano ($A \times B$), y nuestra relación R es simplemente un subconjunto de ese producto cartesiano.

Muchas veces, relacionamos elementos del mismo conjunto. Por ejemplo, si $A = \{1, 2, 3\}$, la relación “es menor que” dentro de este conjunto sería $R_{<} = \{(1, 2), (1, 3), (2, 3)\}$.

Definición Formal

Dados dos conjuntos A y B, una relación binaria R de A en B es un subconjunto del producto cartesiano $A \times B$. Es decir, $R \subseteq A \times B$.

Si $A = B$, decimos que R es una relación sobre A , y por lo tanto, $R \subseteq A \times A$.

Para indicar que un elemento $a \in A$ está relacionado con un elemento $b \in B$ a través de R, podemos usar varias notaciones:

• $(a, b) \in R$ (El par (a, b) pertenece al conjunto R)
• $aRb$ (a está relacionado con b)
• $R(a, b)$ (La relación R es verdadera para a y b)

Ejemplo Resuelto

Sea $A = \{1, 2, 3, 4\}$. Definamos la relación $R$ sobre $A$ como ”$a$ divide a $b$”.

Para encontrar el conjunto R, probamos todos los pares posibles $(a, b)$ de $A \times A$:

• ¿1 divide a 1? Sí. (1, 1)
• ¿1 divide a 2? Sí. (1, 2)
• … (1 divide a todos) $\rightarrow$ (1, 1), (1, 2), (1, 3), (1, 4)
• ¿2 divide a 1? No.
• ¿2 divide a 2? Sí. (2, 2)
• ¿2 divide a 3? No.
• ¿2 divide a 4? Sí. (2, 4)
• … y así sucesivamente.

El conjunto R es: $R = \{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)\}$

Resumen Rápido

Una relación es un conjunto de pares ordenados que formaliza una conexión entre elementos. Nos permite tomar el concepto vago de “relación” y tratarlo con el rigor de la teoría de conjuntos, lo que nos permite analizar sus propiedades.

---

Propiedades Clave de las Relaciones

Las relaciones pueden tener diferentes “personalidades” o propiedades. Estas propiedades nos ayudan a clasificarlas y entender qué tipo de estructura crean. Las más importantes se definen sobre una relación R sobre un conjunto A (es decir, de A en A).

1. Reflexividad

• Definición Inicial: ¿Cada elemento está relacionado consigo mismo?
• Explicación Didáctica: Piensa en la relación “es igual a” (=) sobre los números. ¿Todo número es igual a sí mismo? $5 = 5$, $10 = 10$. Sí. Esta relación es refleja. Ahora piensa en “es mayor que” (>). ¿Es $5 > 5$? No. Esta relación es irrefleja.
• Definición Formal:
  • Refleja: Para cada $a \in A$, se tiene $R(a, a)$.
  • Irrefleja: Para cada $a \in A$, no se tiene $R(a, a)$.

2. Simetría y sus Variaciones

• Definición Inicial: Si la relación va de A a B, ¿puede ir también de B a A?
• Explicación Didáctica:
  • Simétrica: Es una relación “de dos vías”. Si A “es primo de” B, entonces B “es primo de” A. La relación es mutua.
  • Asimétrica: Es una relación estrictamente “de una vía”. Si A “es el padre de” B, entonces B no puede ser el padre de A.
  • Antisimétrica: Esta es la más sutil. Permite que la relación vaya en ambos sentidos solo si A y B son, en realidad, la misma cosa. La relación “menor o igual que” ($\le$) es el mejor ejemplo: Si $a \le b$ y $b \le a$, la única forma de que ambas sean ciertas es que $a = b$. Prohíbe la mutualidad entre elementos distintos.
• Definición Formal:
  • Simétrica: Para cada $a, b \in A$, si $R(a, b)$ entonces $R(b, a)$.
  • Asimétrica: Para cada $a, b \in A$, si $R(a, b)$ entonces no es cierto $R(b, a)$.
  • Antisimétrica: Para cada $a, b \in A$, si $R(a, b)$ y $R(b, a)$, entonces $a = b$.

3. Transitividad

• Definición Inicial: Si A está conectado a B, y B está conectado a C, ¿está A conectado a C?
• Explicación Didáctica: Piensa en la relación “es un ancestro de”. Si Ana es ancestro de Beto, y Beto es ancestro de Carla, entonces Ana también es ancestro de Carla. La propiedad se “transfiere” a través del intermediario. La relación “es amigo de” no es necesariamente transitiva (el amigo de mi amigo no es siempre mi amigo).
• Definición Formal:
  • Transitiva: Para cada $a, b, c \in A$, si $R(a, b)$ y $R(b, c)$, entonces $R(a, c)$.

Resumen Rápido

Estas propiedades son los bloques de construcción para clasificar relaciones. La reflexividad se pregunta por los bucles (A $\rightarrow$ A), la simetría por la direccionalidad (A $\leftrightarrow$ B), y la transitividad por los atajos (A $\rightarrow$ C).

---

Relaciones de Equivalencia

Definición Inicial

Una relación de equivalencia es una forma de agrupar elementos que son “iguales” en algún sentido. Es una relación que formaliza el concepto de “tener la misma propiedad”.

Explicación Didáctica

Imagina una caja llena de fichas de colores (Rojas, Verdes, Azules). La relación “tiene el mismo color que” es una relación de equivalencia.

1. ¿Es Reflexiva? ¿La Ficha A tiene el mismo color que la Ficha A? Sí.
2. ¿Es Simétrica? Si la Ficha A tiene el mismo color que la Ficha B, ¿la B tiene el mismo color que la A? Sí.
3. ¿Es Transitiva? Si A tiene el mismo color que B, y B tiene el mismo color que C, ¿A tiene el mismo color que C? Sí.

Como cumple las tres propiedades, esta relación “equivale” a todas las fichas del mismo color. Nos permite “particionar” o “dividir” el conjunto de fichas en tres grupos: un grupo de Rojas, uno de Verdes y uno de Azules.

Definición Formal

Una relación R sobre un conjunto A es una relación de equivalencia si es:

1. Refleja
2. Simétrica
3. Transitiva

Clases de Equivalencia y Conjunto Cociente

Cuando tenemos una relación de equivalencia (que usualmente se denota con $\sim$), podemos hablar de los “grupos” que forma.

• Clase de Equivalencia: Es el “grupo” o “contenedor” de todos los elementos que están relacionados entre sí. La clase de un elemento $b$, denotada $[b]$, es el conjunto de todos los elementos $c$ tales que $b \sim c$. En nuestro ejemplo, la clase de una ficha roja, $[\text{Ficha Roja}]$, es el conjunto de todas las fichas rojas.
• Conjunto Cociente: Es el conjunto de todos los grupos. No es el conjunto de fichas, sino el conjunto de los contenedores. En nuestro ejemplo, el conjunto cociente $A/\sim$ sería $\{[\text{Rojas}], [\text{Verdes}], [\text{Azules}]\}$. Agrupa a los elementos indistinguibles.

Ejemplo Resuelto

Consideremos la relación $\sim_n$ sobre los enteros $\mathbb{Z}$ definida como: $a \sim_n b$ si y sólo si $(a-b)$ es divisible por $n$. Tomemos $n=3$.

• ¿Es de equivalencia?
  • Refleja: $a \sim_3 a$ porque $(a-a) = 0$, y 0 es divisible por 3. Sí.
  • Simétrica: Si $a \sim_3 b$, entonces $(a-b)$ es divisible por 3 (ej: $a-b = 3k$). Entonces $(b-a) = -3k$, que también es divisible por 3. Así que $b \sim_3 a$. Sí.
  • Transitiva: Si $a \sim_3 b$ (entonces $a-b=3k$) y $b \sim_3 c$ (entonces $b-c=3j$), ¿qué pasa con $a-c$? Sumamos las ecuaciones: $(a-b) + (b-c) = 3k + 3j \Rightarrow a-c = 3(k+j)$. Por lo tanto, $(a-c)$ es divisible por 3. Así que $a \sim_3 c$. Sí.
• Conclusión: $\sim_3$ es una relación de equivalencia.
• Clases de equivalencia:
  • $[0] = \{... -3, 0, 3, 6, ...\}$ (Todos los que tienen resto 0 al dividir por 3)
  • $[1] = \{... -2, 1, 4, 7, ...\}$ (Todos los que tienen resto 1)
  • $[2] = \{... -1, 2, 5, 8, ...\}$ (Todos los que tienen resto 2)
  • $[3] = \{... 0, 3, 6, 9, ...\}$ (Es la misma clase que $[0]$ )
• Conjunto Cociente: $A/\sim_3 = \{[0], [1], [2]\}$. Este conjunto es la base de la aritmética modular.

Resumen Rápido

Una relación de equivalencia usa las propiedades de reflexividad, simetría y transitividad para clasificar elementos en grupos llamados “clases de equivalencia”. El conjunto de estos grupos se llama conjunto cociente.

---

Relaciones de Orden

Definición Inicial

Mientras que las relaciones de equivalencia tratan sobre la “igualdad”, las relaciones de orden tratan sobre la “jerarquía” o el “ranking”. Son las que nos permiten decir que algo va “antes”, “después”, “debajo” o “encima” de otra cosa.

Explicación Didáctica

Pensemos en dos tipos de orden:

1. Orden Total: Imagina los números en una recta numérica. Para cualquier par de números distintos que elijas (ej: 3 y 7), siempre puedes decir que uno es menor que el otro (3 < 7). No hay ambigüedad. Esta es una relación de orden total o lineal.
2. Orden Parcial: Ahora imagina un conjunto de tareas para construir una casa. $T = \{\text{Cimientos, Paredes, Techo, Pintura, Plomería}\}$. La relación es “debe hacerse antes que”.
   • Cimientos $\rightarrow$ Paredes $\rightarrow$ Techo $\rightarrow$ Pintura.
   • Cimientos $\rightarrow$ Plomería.
   • Esta relación es un orden, pero es parcial. ¿Qué va primero, Pintura o Plomería? No podemos compararlas. No tienen una relación de precedencia directa.

Definición Formal

Una relación R sobre un conjunto A es un orden parcial si es:

1. Refleja
2. Antisimétrica
3. Transitiva

(Nota la diferencia con la equivalencia: cambiamos Simétrica por Antisimétrica).

Un orden total (u orden lineal) es un orden parcial que además es Conexo. Una relación es conexa si para cada $a, b \in A$, se tiene $R(a, b)$ o $R(b, a)$. Esto es lo que fuerza a que todos los elementos sean comparables.

Ejemplo Resuelto

1. Relación $\le$ (menor o igual que) sobre $\mathbb{N}$:

   • Refleja: $a \le a$. Sí.
   • Antisimétrica: Si $a \le b$ y $b \le a$, entonces $a=b$. Sí.
   • Transitiva: Si $a \le b$ y $b \le c$, entonces $a \le c$. Sí.
   • Conexa: Para cualquier $a, b$, ¿es $a \le b$ o $b \le a$? Sí.
   • Conclusión: $\le$ sobre $\mathbb{N}$ es un orden total.

2. Relación $\subseteq$ (subconjunto de) sobre $\mathcal{P}(A)$ (el conjunto de todos los subconjuntos de A), donde $A = \{1, 2\}$:

   • Los elementos son: $\emptyset, \{1\}, \{2\}, \{1, 2\}$.
   • Refleja: $X \subseteq X$. Sí.
   • Antisimétrica: Si $X \subseteq Y$ y $Y \subseteq X$, entonces $X=Y$. Sí.
   • Transitiva: Si $X \subseteq Y$ y $Y \subseteq Z$, entonces $X \subseteq Z$. Sí.
   • Conexa: ¿Son todos comparables? Tomemos $X = \{1\}$ y $Y = \{2\}$. ¿Es $\{1\} \subseteq \{2\}$? No. ¿Es $\{2\} \subseteq \{1\}$? No.
   • Conclusión: Como no es conexa, $\subseteq$ es un orden parcial.

Resumen Rápido

Un orden parcial (reflexivo, antisimétrico, transitivo) nos permite crear jerarquías donde algunos elementos pueden ser incomparables. Si además todos los elementos son comparables entre sí (propiedad conexa), tenemos un orden total.

---

Elementos Mínimos y Minimales

En un conjunto ordenado, nos interesa encontrar los elementos que están “al fondo” de la jerarquía. Pero “al fondo” puede significar dos cosas distintas.

Definición Inicial

Un elemento “minimal” es uno que no tiene nada antes que él. Un elemento “mínimo” es uno que está antes que todos los demás.

Explicación Didáctica

Volvamos al ejemplo de las tareas de la casa, ordenadas por “debe hacerse antes que”: $T = \{\text{Cimientos, Paredes, Techo, Pintura, Plomería}\}$ Las relaciones eran: Cimientos $\rightarrow$ Paredes $\rightarrow$ Techo $\rightarrow$ Pintura, y Cimientos $\rightarrow$ Plomería.

• Elemento Mínimo: ¿Hay alguna tarea que deba hacerse antes que todas las demás? Sí, Cimientos. Cimientos es el elemento mínimo.
• Elemento Minimal: ¿Hay tareas que no tengan nada antes que ellas?
  • ¿Paredes? No, Cimientos va antes.
  • ¿Plomería? No, Cimientos va antes.
  • ¿Cimientos? Sí, nada va antes que Cimientos.
  • En este caso, Cimientos es tanto mínimo como minimal.

Ahora, ¿qué pasa si modificamos el proyecto y la Plomería se puede hacer al mismo tiempo que los Cimientos? $T = \{\text{Cimientos, Paredes, ..., Plomería}\}$ Relaciones: Cimientos $\rightarrow$ Paredes… y no hay relación para Plomería.

• Elemento Mínimo: ¿Hay una tarea antes que todas? No. No hay una tarea que vaya antes que Cimientos y antes que Plomería. No hay elemento mínimo.
• Elemento Minimal: ¿Qué tareas no tienen nada antes? Cimientos (nada va antes) y Plomería (nada va antes).
• En este caso, tenemos dos elementos minimales: {Cimientos, Plomería}.

Definición Formal

Sea R un orden parcial sobre un conjunto A.

• Un elemento $a \in A$ es un elemento mínimo de R si para todo $b \in A$ se tiene que $aRb$.
• Un elemento $a \in A$ es un elemento minimal de R si no existe un elemento $b \in A$ tal que $b \ne a$ y $bRa$ .

Propiedades Importantes

1. Un elemento mínimo, si existe, es único.
2. Si un elemento $a$ es mínimo, entonces también es minimal.
3. Si la relación es un orden total (como $\le$ en $\mathbb{N}$), ser minimal es lo mismo que ser mínimo.

Ejemplo Resuelto

Consideremos $A = \{2, 3, 4, 5, 6\}$ con la relación de orden parcial ”|” (divide a).

• Elementos Minimales: Buscamos números $a$ en A tales que ningún otro número $b$ en A los divida.
  • ¿Es 2 minimal? Ningún otro número en A (3, 4, 5, 6) divide a 2. Sí.
  • ¿Es 3 minimal? Ningún otro número en A divide a 3. Sí.
  • ¿Es 4 minimal? No, $2|4$.
  • ¿Es 5 minimal? Ningún otro número en A divide a 5. Sí.
  • ¿Es 6 minimal? No, $2|6$ y $3|6$.
  • El conjunto de elementos minimales es $\{2, 3, 5\}$.
• Elemento Mínimo: Buscamos un número $a$ en A que divida a todos los demás en A.
  • ¿Es 2? No, 2 no divide a 3 ni a 5.
  • ¿Es 3? No, 3 no divide a 2, 4, 5.
  • ¿Es 5? No.
  • No existe un elemento mínimo en este conjunto bajo la relación “divide a”.

Resumen Rápido

En un orden parcial, un elemento minimal es un “punto de partida” (nada viene antes que él), y puede haber varios. Un elemento mínimo es el “origen absoluto” (viene antes que todo lo demás), y solo puede haber uno. En un orden total, ambos conceptos son idénticos.