Relaciones

Introducción

Las relaciones son un tema extenso e importante en matemáticas. Con ellas podemos definir algunas estructuras, como órdenes parciales, totales y buenos. La teoría acerca de estas estructura es extensa, asi que sólo veremos su definición y algunas propiedades elementales. Por otro lado, las relaciones permiten definir equivalencias y particiones. Estas serán discutidas con más detalle, ya que son parte del temario del curso. Finalmente, las relaciones se usan para definir funciones, las cuales son una parte fundamental de las matemáticas.

Ya conocemos algunos ejemplos de relaciones. Por ejemplo la igualdad, o la equivalencia lógica entre proposiciones. También conocemos, por ejemplo, el orden de los números enteros. Todas las anteriores son relaciones que nos dicen algo acerca de dos objetos. En general, una relación podrá decirnos algo acerca de cualquier cantidad de objetos. Un ejemplo, es un tetraedro en \(\mathbb{R}^3\), su definición está dada por

\[T = \{(x,y,z)\in\mathbb{R}^3\mid 0\leq x,y,z\text{ y } x+y+z=1\}.\]

Así, podemos decir que tres números reales están en la relación “tetraedro” si son positivos y suman uno.

Cuando la cantidad de objetos involucrados en la relación es dos diremos que la relación es binaria. Además, si se involucran \(n\) objetos, diremos que la relación es \(n\)-aria.

Definición

Dados dos conjuntos \(A\) y \(B\), una relación \(R\) de \(A\) en \(B\) es un subconjunto de \(A\times B\). Si \(a\in A\) y \(b\in B\), diremos que \(a\) está relacionado con \(b\) (según \(R\)) si \((a,b)\in R\). En este caso también se escribe \(aRb\) o \(R(a,b)\).

En la definición sólo se habla de las relaciones binarias. ¿Cómo es la definición de una relación \(n\)-aria?

Notemos que una relación \(R\) de \(A\) en \(B\) sólo tiene que ser un subconjunto de \(A\times B\), es decir, un elemento de \(\mathcal{P}(A\times B)\). Así, si \(A\times B\neq\emptyset\), entonces siempre hay dos posibles relaciones: la vacía y la total. Generalmente, estas no son de interés.

Un ejemplo es cuando \(A=B=\mathbb{N}\) y \(R\) es la relación de orden, es decir, \((a,b)\in R\) si y sólo si \(a\leq b\).

La definición de relación es muy poco restrictiva, por lo que es posible tener relaciones que no satisfagan nada. Sin embargo, siempre es posible distinguir algunos conjuntos.

Definición

Dada una relación \(R\) de \(A\) en \(B\), definimos el dominio de \(R\) como el conjunto

\[\text{dom}(R) = \{a\in A\mid \exists b\in B\;R(a,b)\}.\]

De manera similar, definimos la imagen de \(R\) como el conjunto

\[\text{im}(R) = \{b\in B\mid \exists a\in A\;R(a,b)\}.\]

Por definición se cumplen \(\text{dom}(R)\subseteq A\) y \(\text{im}(R)\subseteq B\). Además, habrá ejemplos en los que la contención sea una igualdad y ejemplos en los que sea una contención estricta.

Operaciones con relaciones

Dadas dos relaciones \(R\subseteq A\times B\) y \(S\subseteq B\times C\), es posible definir nuevas relaciones a partir de ellas.

Definición

La composición de las relaciones \(R\) y \(S\), denotada por \(S\circ R\), es

\[S\circ R = \{(a,c)\in A\times C\mid \exists b\in B\;(a,b)\in R\text{ y }(b,c)\in S\}.\]

La inversa de la relación \(R\), denotada por \(R^{-1}\), es

\[R^{-1} = \{(b,a)\in B\times A\mid (a,b)\in R\}.\]

Con sólo estas dos operaciones es posible hacer una serie de preguntas:

• ¿la composición es conmutativa? (\(S\circ R = R\circ S\))
• ¿la composición es asociativa? (\((T\circ S)\circ R = T\circ (S\circ R)\))
• ¿quiénes son los elementos de \(R^{-1}\circ R\) y de \(R\circ R^{-1}\)?

Relaciones especiales

Ahora consideramos un caso especial de relación, cuando \(R\subseteq A\times A\). En este caso diremos que \(R\) es una relación binaria sobre \(A\).

En este contexto es posible considerar muchas propiedades que podría tener una relación. Algunas de ellas son las siguientes:

Definición

Sea relación \(R\) sobre \(A\). Decimos que \(R\) es

• reflexiva si para todo \(a\in A\) se tiene que \((a,a)\in R\)
• simétrica si para todo \(a,b\in A\) se tiene que si \((a,b)\in R\) entonces \((b,a)\in R\)
• transitiva si para cualesquiera \(a,b,c\in A\) se tiene que si \((a,b)\in R\) y \((b,c)\in R\) entonces \((a,c)\in R\)
• de equivalencia si es reflexiva, simétrica y transitiva
• irreflexiva para todo \(a\in A\) tal que \((a,a)\notin R\).
• antisimétrica si para cualesquiera \(a,b\in A\) se tiene que si \((a,b)\in R\) y \((b,a)\in R\) entonces \(a=b\).
• asimétrica si para cualesquiera \(a,b\in A\) se tiene que si \((a,b)\in R\), entonces \((b,a)\notin R\).
• tricotómica si para cualesquiera \(a,b\in A\) se tiene que se cumple una de las siguientes condiciones: \((a,b)\in R\), \((b,a)\in R\) o \(a=b\).

Más adelante regresaremos a las relaciones de equivalencia, por lo que veremos nada más de ellas aquí.

Con todas estas propiedades es posible deducir alguna de otras. Por ejemplo, transitiva más irreflexiva implica asimétrica. Sin embargo, sólo mostraremos una que no es cierta, así que se deberá encontrar el error en la demostración.

Proposición (falsa)

Si \(R\) es una relación transitiva y simétrica, entonces reflexiva.

Demostración

Supongamos que \(R\) es transitiva y simétrica. Sea \(a\in A\) y consideramos \((a,b)\in R\). Por simetría, \((b,a)\in R\). Por transitividad, \((a,a)\in R\). Por lo tanto, \(R\) es reflexiva.

Órdenes

Si reunimos algunas de las propiedades que pueden tener las relaciones, obtenemos las primeras estructuras matemáticas que presentaremos en el curso: los órdenes. La notación para estas estructuras debería ser \(\mathcal{A}=\langle A, R\rangle\), donde \(R\) es una relación binaria sobre \(A\). Deberíamos decir que \(\mathcal{A}\) es un orden y \(A\) es su conjunto subyacente. Sin embargo, en la práctica se suele omitir la relación y decir que \(A\) es un orden.

Definición

Sea \(A\) un conjunto y \(R\) una relación binaria sobre \(A\). Diremos que \(\langle A, R\rangle\) es un

• orden parcial (reflexivo) si \(R\) es reflexiva, antisimétrica y transitiva
• orden parcial (irreflexivo) si \(R\) es irreflexiva y transitiva.

Empezamos con los órdenes más simples, notando que en realidad hay dos formas diferentes para definir un orden parcial. Aunque es raro tener dos definiciones diferentes para un mismo concepto, en este caso es útil. Por ejemplo, en algunas situaciones nos gustaría estudiar a \(\langle\mathbb{N},\leq\rangle\), mientras que en otras nos gustaría estudiar a \(\langle\mathbb{N},<\rangle\). Aunque son estructuras muy parecidas, las propiedades que satisface \(\leq\) no son las mismas que satisface \(<\). Por ejemplo, \(\leq\) es reflexiva, mientras que \(<\) es irreflexiva. Para incluir a ambas estructuras como órdenes parciales se dan dos posibilidades para dichos órdenes.

En un orden parcial \(\langle A, R\rangle\) es posible tener elementos especiales. Por ejemplo, si \(B\subseteq A\) entonces un elemento \(b\in B\) es mínimo si para todo \(x\in B\) se tiene que \((b,x)\in R\). De manera similar se define máximo. En general estos mínimos y máximos no existen, por ejemplo, ¿quién es el mínimo en \(\mathbb{Z}\)?

Es posible dar más elementos especiales en un orden parcial, como las cotas superiores e inferiores para un subconjunto dado. También se puede definir supremo e ínfimo para un subconjunto. Sin embargo, no los usaremos en este momento, por lo que no veremos su definición.

De la misma manera que con los órdenes parciales, habrá dos versiones de cada tipo de orden, uno reflexivo y otro irreflexivo.

Definición

Sea \(\langle A, R\rangle\) un orden parcial. Diremos que el orden es un

• orden total si \(R\) es tricotómica,
• buen orden si todo subconjunto no vacío de \(A\) tiene un mínimo.

Notemos que la definición de orden total y buen orden incluye ser orden parcial. Por lo tanto, si \(\langle A, R\rangle\) es orden total o buen orden, entonces es orden parcial. De hecho, las implicaciones entre estos tres tipos de orden son

\[\text{buen orden}\Rightarrow\text{orden total}\Rightarrow\text{orden parcial}.\]

No sólo tenemos esas implicaciones, sino que también tenemos que no se dan los regresos.