7.2: Propiedades de las Relaciones

Si\(R\) es una relación de\(A\) a\(A\), entonces\(R\subseteq A\times A\); decimos que\(R\) es una relación sobre\(\mathbf{A}\).

Definición

Una relación\(R\) sobre\(A\) se dice que es

• reflexivo si\((a,a)\in R\,a\) para todos\(a\in A\),
• irreflexivo si es\((a,a)\notin R\) para todos\(a\in A\),
• simétrico si es\((a,b)\in R \Rightarrow (b,a)\in R\) para todos\(a,b\in A\),
• antisimétrico si es\([(a,b)\in R\,\wedge\,(b,a)\in R] \Rightarrow a=b\) para todos\(a,b\in A\),
• transitivo si es\([(a,b)\in R\,\wedge\,(b,c)\in R] \Rightarrow (a,c)\in R\) para todos\(a,b,c\in A\).

Estas son definiciones importantes, así que vamos a repetirlas usando la notación relacional\(a\,R\,b\):

• reflexivo si\(a\,R\,a\) para todos\(a\in A\),
• irreflexivo si\(a\!\not\!R\,a\) (es decir,\(\overline{a\,R\,a}\)) para todos\(a\in A\),
• simétrico si es\(a\,R\,b \Rightarrow b\,R\,a\) para todos\(a,b\in A\),
• antisimétrico si es\([(a\,R\,b) \wedge (b\,R\,a)] \Rightarrow a=b\) para todos\(a,b\in A\),
• transitivo si es\([(a\,R\,b) \wedge (b\,R\,c)] \Rightarrow a\,R\,c\) para todos\(a,b,c\in A\).

Comentario

Una relación no puede ser tanto reflexiva como irreflexiva. De ahí que estas dos propiedades sean mutuamente excluyentes. Si es reflexiva, entonces no es irreflexiva. Si es irreflexiva, entonces no puede ser reflexiva. Sin embargo, es posible que una relación no sea ni reflexiva ni irreflexiva.

Comentario

Muchos estudiantes encuentran confuso el concepto de simetría y antisimetría. Aunque el nombre lo pueda sugerir, la antisimetría no es lo opuesto a la simetría. Es posible que una relación sea tanto simétrica como antisimétrica, y también es posible que una relación sea tanto no simétrica como no antisimétrica. Una buena manera de entender la antisimetría es mirar su contrapositiva:\[a\neq b \Rightarrow \overline{(a,b)\in R \,\wedge\, (b,a)\in R}. \nonumber\] Así, si dos elementos distintos\(a\) y\(b\) están relacionados (no todos los pares de elementos necesitan estar relacionados)\(b\), entonces o\(a\)\(b\) está relacionado con\(a\), pero no ambos. En consecuencia, si encontramos elementos distintos\(a\) y\(b\) tales que\((a,b)\in R\) y\((b,a)\in R\), entonces no\(R\) es antisimétrico.

Ejemplo\(\PageIndex{1}\label{eg:SpecRel}\)

La relación vacía es el subconjunto\(\emptyset\). Es claramente irreflexivo, por lo tanto no reflexivo. Para comprobar la simetría, queremos saber si\(a\,R\,b \Rightarrow b\,R\,a\) para todos\(a,b\in A\). Más específicamente, queremos saber si\((a,b)\in \emptyset \Rightarrow (b,a)\in \emptyset\). Ya que siempre\((a,b)\in\emptyset\) es falso, la implicación es siempre verdadera. Así, la relación es simétrica. Asimismo, es antisimétrico y transitivo.

La relación completa es el conjunto completo\(A\times A\). Es claramente reflexivo, por lo tanto no irreflexivo. También es trivial que sea simétrico y transitivo. No es antisimétrico a menos que\(|A|=1\).

La relación de identidad consiste en pares ordenados de la forma\((a,a)\), donde\(a\in A\). En otras palabras,\(a\,R\,b\) si y sólo si\(a=b\). Es reflexiva (por lo tanto, no irreflexiva), simétrica, antisimétrica y transitiva.

Ejemplo\(\PageIndex{2}\label{eg:proprelat-02}\)

Considerar la relación\(R\) sobre el conjunto\(A=\{1,2,3,4\}\) definido por\[R = \{(1,1),(2,3),(2,4),(3,3),(3,4)\}. \nonumber\]

Ya que\((2,2)\notin R\), y\((1,1)\in R\), la relación no es ni reflexiva ni irreflexiva.

Tenemos\((2,3)\in R\) pero\((3,2)\notin R\), por lo tanto no\(R\) es simétrico.

Para cualquiera\(a\neq b\), sólo una de las cuatro posibilidades\((a,b)\notin R\),\((b,a)\notin R\),\((a,b)\in R\), o\((b,a)\in R\) puede ocurrir, así\(R\) es antisimétrica.

Al pasar por todos los pares ordenados en\(R\), verificamos que si\((a,b)\in R\) y\((b,c)\in R\),\((a,c)\in R\) siempre tenemos también. Esto demuestra que\(R\) es transitivo.

Por lo tanto,\(R\) es antisimétrico y transitivo.

Ejemplo\(\PageIndex{3}\label{eg:proprelat-03}\)

Definir la relación\(S\) en el conjunto de\(A=\{1,2,3,4\}\) acuerdo con\[S = \{(2,3),(3,2)\}. \nonumber\]

Ya que\((1,1),(2,2),(3,3),(4,4)\notin S\), la relación\(S\) es irreflexiva, por lo tanto, no es reflexiva.

Ya que solo tenemos dos pares ordenados, y es claro que siempre\((a,b)\in S\), también tenemos\((b,a)\in S\). De ahí,\(S\) es simétrico.

Tenemos ambos\((2,3)\in S\) y\((3,2)\in S\), pero\(2\neq3\). De ahí\(S\) que no sea antisimétrico.

Desde\((2,3)\in S\) y\((3,2)\in S\), pero\((2,2)\notin S\), la relación no\(S\) es transitiva.

Concluimos que\(S\) es irreflexivo y simétrico.

ejercicio práctico\(\PageIndex{1}\label{he:proprelat-01}\)

Definir la relación\(R\) en el conjunto\(\mathbb{R}\) como\[a\,R\,b \,\Leftrightarrow\, a\leq b. \nonumber\] Determinar si\(R\) es reflexiva, irreflexiva, simétrica, antisimétrica o transitiva.

ejercicio práctico\(\PageIndex{2}\label{he:proprelat-02}\)

La relación\(S\) en el conjunto\(\mathbb{R}^*\) se define como\[a\,S\,b \,\Leftrightarrow\, ab>0. \nonumber\] Determinar si\(S\) es reflexiva, irreflexiva, simétrica, antisimétrica o transitiva.

Ejemplo\(\PageIndex{4}\label{eg:geomrelat}\)

Aquí hay dos ejemplos de geometría. Dejar\({\cal T}\) ser el conjunto de triángulos que se pueden dibujar en un plano. Definir una relación\(S\) sobre\({\cal T}\) tal que\((T_1,T_2)\in S\) si y sólo si los dos triángulos son similares. Es fácil verificar que\(S\) sea reflexivo, simétrico y transitorio.

Dejar\({\cal L}\) ser el conjunto de todas las líneas (rectas) en un plano. Definir una relación\(P\) de\({\cal L}\) acuerdo a\((L_1,L_2)\in P\) si y sólo si\(L_1\) y\(L_2\) son líneas paralelas. Nuevamente, es obvio que\(P\) es reflexivo, simétrico y transitivo.

Ejemplo\(\PageIndex{5}\label{eg:proprelat-04}\)

La relación\(T\) sobre\(\mathbb{R}^*\) se define como\[a\,T\,b \,\Leftrightarrow\, \frac{a}{b}\in\mathbb{Q}. \nonumber\]

Ya que\(\frac{a}{a}=1\in\mathbb{Q}\), la relación\(T\) es reflexiva; de ello se deduce que no\(T\) es irreflexiva.

La relación\(T\) es simétrica, porque si se\(\frac{a}{b}\) puede escribir como\(\frac{m}{n}\) para algunos enteros\(m\) y\(n\), entonces también lo es su recíproco\(\frac{b}{a}\), porque\(\frac{b}{a}=\frac{n}{m}\).

Desde\(\sqrt{2}\;T\sqrt{18}\) y\(\sqrt{18}\;T\sqrt{2}\), sin embargo\(\sqrt{2}\neq\sqrt{18}\), concluimos que no\(T\) es antisimétrico.

Si\(\frac{a}{b}, \frac{b}{c}\in\mathbb{Q}\), entonces\(\frac{a}{b}= \frac{m}{n}\) y\(\frac{b}{c}= \frac{p}{q}\) para algunos enteros distintos de cero\(m\),\(n\),\(p\), y\(q\). Entonces\(\frac{a}{c} = \frac{a}{b}\cdot\frac{b}{c} = \frac{mp}{nq} \in\mathbb{Q}\). De ahí,\(T\) es transitivo.

Por lo tanto, la relación\(T\) es reflexiva, simétrica y transitiva.

ejercicio práctico\(\PageIndex{3}\label{he:proprelat-03}\)

Considerar la relación\(T\) sobre\(\mathbb{N}\) definida por\[a\,T\,b \,\Leftrightarrow\, a\mid b. \nonumber\] Determinar si\(T\) es reflexiva, irreflexiva, simétrica, antisimétrica o transitiva.

ejercicio práctico\(\PageIndex{4}\label{he:proprelat-04}\)

La relación\(U\) en el conjunto\(\mathbb{Z}^*\) se define como\[a\,U\,b \,\Leftrightarrow\, a\mid b. \nonumber\] Determinar si\(U\) es reflexiva, irreflexiva, simétrica, antisimétrica o transitiva.

Ejemplo\(\PageIndex{6}\label{eg:proprelat-05}\)

La relación\(U\) sobre\(\mathbb{Z}\) se define como\[a\,U\,b \,\Leftrightarrow\, 5\mid(a+b). \nonumber\]

• La relación no\(U\) es reflexiva, porque\(5\nmid(1+1)\).
• Tampoco es irreflexiva, porque\(5\mid(10+10)\).
• Si\(5\mid(a+b)\), es obvio que\(5\mid(b+a)\) porque\(a+b=b+a\). Así,\(U\) es simétrico.
• Afirmamos que no\(U\) es antisimétrico. Por ejemplo,\(5\mid(2+3)\) y\(5\mid(3+2)\), todavía\(2\neq3\).
• Tampoco es transitivo. Por ejemplo,\(5\mid(1+4)\) y\(5\mid(4+6)\), pero\(5\nmid(1+6)\).
• La relación\(U\) es simétrica.

ejercicio práctico\(\PageIndex{5}\label{he:proprelat-05}\)

Determinar si la siguiente relación\(V\) en algún conjunto universal\(\cal U\) es reflexiva, irreflexiva, simétrica, antisimétrica o transitiva:\[(S,T)\in V \,\Leftrightarrow\, S\subseteq T. \nonumber\]

Ejemplo\(\PageIndex{7}\label{eg:proprelat-06}\)

Considera que la relación\(V\) en el conjunto\(A=\{0,1\}\) se define de acuerdo con\[V = \{(0,0),(1,1)\}. \nonumber\]

La relación\(V\) es reflexiva, porque\((0,0)\in V\) y\((1,1)\in V\). De ahí que no sea irreflexiva.

Es claramente simétrico, porque\((a,b)\in V\) siempre implica\((b,a)\in V\).

En efecto\((a,b)\in V\), siempre que, también debemos tener\(a=b\), porque\(V\) consiste en sólo dos pares ordenados, ambos están en forma de\((a,a)\). De ello se deduce que también\(V\) es antisimétrico.

Un argumento similar muestra que\(V\) es transitivo.

La relación es reflexiva, simétrica, antisimétrica y transitiva.

ejercicio práctico\(\PageIndex{6}\label{he:proprelat-06}\)

Determinar si la siguiente relación\(W\) en un conjunto no vacío de individuos en una comunidad es reflexiva, irreflexiva, simétrica, antisimétrica o transitiva:\[a\,W\,b \,\Leftrightarrow\, \mbox{$a$ and $b$ have the same last name}. \nonumber\]

Ejemplo\(\PageIndex{8}\label{eg:proprelat-07}\)

Definir la relación\(W\) en un conjunto no vacío de individuos en una comunidad como\[a\,W\,b \,\Leftrightarrow\, \mbox{$a$ is a child of $b$}. \nonumber\]

• Nadie puede ser hijo de sí mismo o de sí mismo, por lo tanto,\(W\) no puede ser reflexivo. En cambio, es irreflexiva.
• Es obvio que\(W\) no puede ser simétrico.
• Puede sonar raro por la definición que\(W\) es antisimétrica: ¡\[(a \mbox{ is a child of } b) \wedge (b\mbox{ is a child of } a) \Rightarrow a=b, \label{eqn:child}\]pero es verdad! La razón es, si\(a\) es hijo de\(b\), entonces\(b\) no puede ser hijo de\(a\). Esto hace que la conjunción sea\[(a \mbox{ is a child of } b) \wedge (b\mbox{ is a child of } a) \nonumber\] falsa, lo que hace que la implicación (\ ref {eqn:child}) sea verdadera.
• Un argumento similar sostiene si\(b\) es hijo de\(a\), y si ni\(a\) es hijo de\(b\) ni\(b\) es hijo de\(a\). No importa lo que pase, la implicación (\ ref {eqn:child}) siempre es cierta. Por lo tanto,\(W\) es antisimétrico.
• Puede ayudar si miramos la antisimetría desde un ángulo diferente. El contrapositivo de la definición original afirma que cuando\(a\neq b\), podrían suceder tres cosas:

1. \(a\)y\(b\) son incomparables (\(\overline{a\,W\,b}\)y\(\overline{b\,W\,a}\)), es decir,\(a\) y no\(b\) están relacionados;

y si\(a\) y\(b\) están relacionados, entonces

1. \(a\,W\,b\)pero\(\overline{b\,W\,a}\), o
2. \(b\,W\,a\)pero\(\overline{a\,W\,b}\).

Usando esta observación, es fácil ver por qué\(W\) es antisimétrico.

• Es claro que no\(W\) es transitivo.

La relación es irreflexiva y antisimétrica.

En lugar de usar dos filas de vértices en el dígrafo que representa una relación en un conjunto\(A\), podemos usar solo un conjunto de vértices para representar los elementos de\(A\). Una línea dirigida conecta vértice\(a\) a vértice\(b\) si y sólo si el elemento\(a\) está relacionado con el elemento\(b\). Si también\(b\) se relaciona con\(a\), los dos vértices se unirán por dos líneas dirigidas, una en cada dirección. Si\(a\) está relacionado consigo mismo, hay un bucle alrededor del vértice que representa\(a\). Ver Problema 10 en Ejercicios 7.1.

A partir de la representación gráfica, determinamos que la relación\(R\) es

• Reflexiva si hay un bucle en cada vértice de\(G\).
• Irreflexivo si\(G\) es desbocado.
• Simétrico si cada par de vértices está conectado por ninguna o exactamente dos líneas dirigidas en direcciones opuestas.
• Antisimétrico si cada par de vértices está conectado por ninguna o exactamente una línea dirigida.
• Transitivo si por cada trayectoria unidireccional que une tres vértices\(a,b,c\), en ese orden, también hay una línea dirigida que se une\(a\) a\(c\).

La matriz de incidencia\(M=(m_{ij})\) para una relación\(A\) es una matriz cuadrada. Nos encontramos con que\(R\) es

• Reflexiva si cada entrada en la diagonal principal de\(M\) es 1.
• Irreflexivo si cada entrada en la diagonal principal de\(M\) es 0.
• Simétrico si\(M\) es simétrico, es decir,\(m_{ij}=m_{ji}\) cuando sea\(i\neq j\).
• Antisimétrico si\(i\neq j\) implica que al menos uno de\(m_{ij}\) y\(m_{ji}\) es cero, es decir,\(m_{ij} m_{ji} = 0\).
• Transitivo si\((M^2)_{ij} > 0\) implica\(m_{ij}>0\) cuando sea\(i\neq j\).

Por ejemplo, la matriz de incidencia para la relación de identidad consiste en 1s en la diagonal principal, y 0s en todas partes. A esto se le llama la matriz de identidad. Si una relación\(R\) on\(A\) es simétrica y antisimétrica, sus entradas fuera de diagonal son todas ceros, por lo que es un subconjunto de la relación de identidad.

Es un ejercicio interesante para probar la prueba de la transitividad. Aplícalo al Ejemplo 7.2.2 para ver cómo funciona.

Resumen y revisión

• Una relación de un conjunto\(A\) a sí mismo se llama relación sobre\(A\).
• Dada cualquier relación\(R\) en un conjunto\(A\), nos interesan cinco propiedades que\(R\) pueden o no tener.
• \(R\)Se dice que la relación es reflexiva si cada elemento está relacionado consigo mismo, es decir, si\(x\,R\,x\) por cada\(x\in A\).
• \(R\)Se dice que la relación es irreflexiva si ningún elemento está relacionado consigo mismo, es decir, si\(x\not\!\!R\,x\) por cada\(x\in A\).
• La propiedad reflexiva y la propiedad irreflexiva son mutuamente excluyentes, y es posible que una relación no sea ni reflexiva ni irreflexiva.
• \(R\)Se dice que la relación es simétrica si la relación puede ir en ambas direcciones, es decir, si\(x\,R\,y\) implica\(y\,R\,x\) para alguna\(x,y\in A\).
• \(R\)Se dice que la relación es antisimétrica si se le dan dos elementos distintos\(x\) y\(y\), ya sea (i)\(x\) y no\(y\) están relacionados de ninguna manera, o (ii) si\(x\) y\(y\) están relacionados, solo pueden relacionarse en una dirección.
• Una forma compacta de definir la antisimetría es: si\(x\,R\,y\) y\(y\,R\,x\), entonces debemos tener\(x=y\).
• Finalmente, se dice que una relación es transitiva si podemos pasar a lo largo de la relación y relacionar dos elementos si están relacionados a través de un tercer elemento.
• Más precisamente,\(R\) es transitivo si\(x\,R\,y\) e\(y\,R\,z\) implica eso\(x\,R\,z\).

Ejercicio\(\PageIndex{1}\label{ex:proprelat-01}\)

Para cada relación en el Problema 1 en los Ejercicios 1.1, determinar cuál de las cinco propiedades se satisface.

Ejercicio\(\PageIndex{2}\label{ex:proprelat-02}\)

Para cada relación en Problema 3 en Ejercicios 1.1, determinar cuál de las cinco propiedades se satisface.

Ejercicio\(\PageIndex{3}\label{ex:proprelat-03}\)

Para la relación en Problema 6 en Ejercicios 1.1, determinar cuál de las cinco propiedades se satisface.

Ejercicio\(\PageIndex{4}\label{ex:proprelat-04}\)

Para la relación en Problema 7 en Ejercicios 1.1, determinar cuál de las cinco propiedades se satisface.

Ejercicio\(\PageIndex{5}\label{ex:proprelat-05}\)

Para la relación en Problema 8 en Ejercicios 1.1, determinar cuál de las cinco propiedades se satisface.

Ejercicio\(\PageIndex{6}\label{ex:proprelat-06}\)

Para la relación en Problema 9 en Ejercicios 1.1, determinar cuál de las cinco propiedades se satisface.

Ejercicio\(\PageIndex{7}\label{ex:proprelat-07}\)

Dejar\(S\) ser un conjunto no vacío y definir la relación\(A\) on\(\wp(S)\) by\[(X,Y)\in A \Leftrightarrow X\cap Y=\emptyset. \nonumber\] Está claro que\(A\) es simétrico.

1. \(A\)Explique por qué no es reflexivo.
2. \(A\)Explique por qué no es irreflexivo.
3. ¿Es\(A\) transitivo?
4. Vamos\(S=\{a,b,c\}\). Dibuja la gráfica dirigida para\(A\), y encuentra la matriz de incidencia que representa\(A\).

Ejercicio\(\PageIndex{8}\label{ex:proprelat-08}\)

Para cada una de estas relaciones en\(\mathbb{N}-\{1\}\), determinar cuál de las cinco propiedades están satisfechas.

1. \(A_1=\{(x,y)\mid x\)y\(y\) son relativamente primos\(\}\)
2. \(A_2=\{(x,y)\mid x\)y no\(y\) son relativamente primos\(\}\)

Ejercicio\(\PageIndex{9}\label{ex:proprelat-09}\)

Para cada una de las siguientes relaciones sobre\(\mathbb{N}\), determinar cuál de las cinco propiedades están satisfechas.

1. \(R_1=\{(x,y)\mid x\)divide\(y\}\)
2. \(R_2=\{(x,y)\mid x+y\)es parejo\(\}\)
3. \(R_3=\{(x,y)\mid xy\)es parejo\(\}\)

Ejercicio\(\PageIndex{10}\label{ex:proprelat-10}\)

Para cada una de las siguientes relaciones sobre\(\mathbb{N}\), determinar cuál de las cinco propiedades están satisfechas.

1. \(S_1=\{(x,y)\mid y\)divide\(x\}\)
2. \(S_2=\{(x,y)\mid x+y\)es impar\(\}\)
3. \(S_3=\{(x,y)\mid xy\)es impar\(\}\)

Ejercicio\(\PageIndex{11}\label{ex:proprelat-11}\)

Para cada una de las siguientes relaciones sobre\(\mathbb{Z}\), determinar cuál de las cinco propiedades están satisfechas.

1. \(U_1=\{(x,y)\mid x \leq y\}\)
2. \(U_2=\{(x,y)\mid x-y\)es impar}\(\}\)
3. \(U_3=\{(x,y)\mid 3\)divide\(x+2y\}\)

Ejercicio\(\PageIndex{12}\label{ex:proprelat-12}\)

Para cada una de las siguientes relaciones sobre\(\mathbb{Z}\), determinar cuál de las cinco propiedades están satisfechas.

1. \(V_1=\{(x,y)\mid xy>0\}\)
2. \(V_2=\{(x,y)\mid x-y\)es parejo\(\}\)
3. \(V_3=\{(x,y)\mid x\)es un múltiplo de\(y\}\)