1.2: Relaciones. Mapeos

Relaciones

En §1, ya hemos considerado conjuntos de pares ordenados, como productos cartesianos\(A \times B\) o conjuntos de la forma\(\{(x, y) | P (x, y)\}\) (cf. §§1—3, Problema 7). Si el par\((x, y)\) es un elemento de tal conjunto\(R\), escribimos

\[(x, y) \in R \label{eq1}\]

tratando\((x, y)\) como una cosa. Tenga en cuenta que esto no implica que\(x\) y\(y\) tomados por separado sean miembros de\(R\) (en cuyo caso escribiríamos\(x, y \in R\)). Nosotros llamamos\(x\),\(y\) los términos de\((x, y)\).

En matemáticas, es costumbre llamar relación a cualquier conjunto de pares ordenados. Por ejemplo, todos los conjuntos enumerados en el Problema 7 de §§1—3 son relaciones. Dado que las relaciones son conjuntos, la igualdad\(R = S\) para las relaciones significa que consisten en los mismos elementos (pares ordenados), es decir, que

\[(x, y) \in R \iff (x, y) \in S\]

Si\((x, y) \in R\), llamamos a\(y\) un\(R\) -pariente de\(x\); también decimos que\(y\) está\(R\) relacionado con\(x\) o que la relación se\(R\) mantiene entre\(x\) y\(y\) (en este orden). En lugar de\((x, y) ∈ R\), también escribimos\(xRy\), y muchas veces reemplazamos “\(R\)” por símbolos especiales como\(<\)\(∼\),, etc. Así, en el caso (i) del Problema 7 anterior, “\(xRy\)” significa eso\(x < y\).

Sustituyendo todos los pares\((x, y) \in R\) por los pares inversos\((y, x)\), obtenemos una nueva relación, llamada inversa de\(R\) y denotada\(R^{-1}\). Claramente,\(xR^{−1}y\) iff\(yRx\); así

\[R^{-1} = \{(x, y) | yRx\} = \{(y, x) | xRy\}.\]

De ahí que\(R\), a su vez, sea la inversa de\(R^{−1}\); es decir,

\[(R^{-1})^{-1} = R.\]

Por ejemplo, las relaciones\(<\) y\(>\) entre números son inversas entre sí; así también lo son las relaciones\(\subseteq\) y\(\supseteq\) entre conjuntos. (Podemos tratar “\(\subseteq\)” como el nombre del conjunto de todos los pares\((X,Y)\) tal que\(X \subseteq Y\) en un espacio dado.)

Si\(R\) contiene los pares\((x, x′), (y, y′), (z, z′), . . . \), escribiremos

\[R = \begin{pmatrix} x & y & z & \ldots \\ x' & y' & z' & \text{ } \end{pmatrix}; \hskip 5pt e.g., \hskip 5pt R = \begin{pmatrix} 1 & 4 & 1 & 3 \\ 2 & 2 & 1 & 1 \end{pmatrix}. \]

Para obtener\(R^{−1}\), simplemente cambiamos las filas superior e inferior en la Ecuación\ ref {eq1}.

Definición 1

El conjunto de todos los términos izquierdos\(x\) de pares\((x, y) \in R\) se llama el dominio de\(R\), denotado\(D_{R}\). El conjunto de todos los términos correctos de estos pares se llama el rango de\(R\), denotado\(D_{R}^{′}\). Claramente,\(x \in D_{R}\) iff\(xRy\) para algunos\(y\). En símbolos,

\[x \in D_{R} \iff (\exists y) \hskip 5pt xRy; \hskip 5pt \text{similarly,} \hskip 5pt y \in D_{R}^{'} \iff (\exists x) \hskip 5pt xRy.\]

En Ecuación\ ref {eq1},\(D_{R}\) está la fila superior, y\(D_{R}^{′}\) es la fila inferior. Claramente,

\[D_{R^{-1}} = D_{R}^{'} \hskip 5pt \text{and} \hskip 5pt D_{R^{-1}}^{'} = D_{R}.\]

Por ejemplo, si

\[R = \begin{pmatrix} 1 & 4 & 1 \\ 2 & 2 & 1 \end{pmatrix},\]

entonces

\[D_{R} = D_{R^{-1}}^{'} = \{1, 4\} \hskip 5pt \text{and} \hskip 5pt D_{R}^{'} = D_{R^{-1}} = \{1, 2\}.\]

Definición 2

La imagen de un conjunto\(A\) bajo una relación\(R\) (brevemente, la\(R-image\) de\(A\)) es el conjunto de todos\(R\) -parientes de elementos de\(A\), denotados\(R[A]\). La imagen inversa de\(A\) bajo\(R\) es la imagen de\(A\) debajo de la relación inversa, es decir,\(R^{−1}[A]\). Si A consiste en un solo elemento,\(A = {x}\), entonces\(R[A]\) y también\(R^{−1}[A]\) se escriben\(R[x]\) y\(R^{−1}[x]\), respectivamente, en lugar de\(R[{x}]\) y\(R^{−1}[{x}]\).

Ejemplo\(\PageIndex{1}\)

Let

\[R = \begin{pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 7 \\ 1 & 3 & 4 & 5 & 3 & 4 & 1 & 3 & 5 & 1 \end{pmatrix}, \hskip 5pt A = \{1, 2\}, \hskip 5pt B = \{2 , 4\}. \]

Entonces

\[\begin{array}{lll} R[1] = \{1 , 3 , 4\}; & R[2] = \{3, 5\}; & R[3] = \{1, 3, 4, 5\}; \\ R[5] = \emptyset; & R^{-1}[1] = \{1, 3, 7\}; & R^{-1}[2] = \emptyset; \\ R^{-1}[3] = \{1, 2, 3\}; & R^{-1}[4] = \{1, 3\}; & R[A] = \{1, 3, 4, 5\}; \\ R^{-1}[A] = \{1, 3, 7\}; & R[B] = \{3, 5\}. \end{array} \]

Por definición,\(R[x]\) es el conjunto de todos\(R\) -parientes de\(x\). Por lo tanto

\[y \in R[x] \hskip 5pt \text{iff} \hskip 5pt(x, y) \in R; \hskip 5pt \text{i.e.,} \hskip 5pt xRy.\]

De manera más general,\(y \in R[A]\) significa eso\((x, y) \in R\) para algunos\(x \in A\). En símbolos,

\[y \in R[A] \iff (\exists x \in A) (x, y) \in R.\]

Tenga en cuenta que siempre\(R[A]\) se define.

Mappings

Consideraremos ahora un tipo de relación especialmente importante.

Definición 3

Una relación\(R\) se llama mapeo (mapa), o una función, o una transformación, si cada elemento\(x \in D_{R}\) tiene un único\(R\) -relativo, por lo que\(R[x]\) consiste en un solo elemento. Este elemento único se denota por\(R(x)\) y se llama el valor de la función at\(x\) (bajo\(R\)). Así\(R(x)\) es el único miembro de\(R[x]\).

Si, además, diferentes elementos de\(D_{R}\) tienen diferentes imágenes,\(R\) se denomina mapa uno a uno (o uno-uno). En este caso,

\[x \neq y\left(x, y \in D_{R}\right) \text{ implies } R(x) \neq R(y);\]

equivalentemente,

\[R(x)=R(y) \text{ implies } x=y.\]

Es decir, no hay dos pares que pertenezcan a\(R\) tener los mismos términos a la izquierda, o a la misma derecha. Esto demuestra que\(R\) es uno a uno iff\(R^{−1}\), también, es un mapa. Los mapeos suelen ser denotados por las letras\(f, g, h, F, \psi\), etc.

Se dice que un mapeo\(f\) es “de\(A\) a\(B\)” iff\(D_{f} = A\) y\(D_{f}^{′} \subseteq B\); luego escribimos

\[f : A \rightarrow B \quad\left("f \text{ maps } A \text{ into } B"\right)\]

Si, en particular,\(D_{f} = A\) y\(D_{f}^{′} = B\), llamamos\(f\) un mapa de\(A\) onto\(B\), y escribimos

\[f : A \underset{\mathrm{onto}}{\longrightarrow} B \quad\left("f \text{ maps } A \text{ onto } B"\right)\]

Si\(f\) es a la vez en y uno a uno, escribimos

\[f : A \longleftrightarrow B\]

(\(f: A \longleftrightarrow B\)significa que\(f\) es uno a uno).

Todos los pares que pertenecen a un mapeo\(f\) tienen la forma\((x, f(x))\) donde\(f(x)\) está el valor de la función at\(x\), es decir, el único\(f\) -relativo de\(x, x \in D_{f}\). Por lo tanto, para definir alguna función\(f\), basta con especificar su dominio\(D_{f}\) y el valor de la función\(f(x)\) para cada una\(x \in D_{f}\). A menudo utilizaremos tales definiciones. Es costumbre decir que\(f\) se define en\(A\) (o “\(f\)es una función en\(A\)”) iff\(A = D_{f}\).

Ejemplo\(\PageIndex{2}\)

(a) La relación
\[R=\{(x, y) | x \text{ is the wife of } y\}\]
es un mapa uno a uno del conjunto de todas las esposas sobre el conjunto de todos los esposos. \(R^{-1}\)es aquí un mapa uno a uno del conjunto de todos los maridos\(\left(=D_{R}^{\prime}\right)\) en
el conjunto de todas las esposas\(\left(=D_{R}\right)\).

b) La relación
\[f=\{(x, y) | y \text{ is the father of } x\}\]

es un mapa del conjunto de todas las personas en el conjunto de sus padres. No es uno a uno ya que varias personas pueden tener el mismo padre (\(f\)-pariente), y así\(x \neq x^{\prime}\) no implica\(f(x) \neq f\left(x^{\prime}\right) .\)

c) Dejar

\[g=\left( \begin{array}{cccc}{1} & {2} & {3} & {4} \\ {2} & {2} & {3} & {8}\end{array}\right)\]

Entonces\(g\) es un mapa de\(D_{g}=\{1,2,3,4\}\) onto\(D_{g}^{\prime}=\{2,3,8\},\) con

\[g(1)=2, g(2)=2, g(3)=3, g(4)=8\]

(Como se señaló anteriormente, estas fórmulas pueden servir para definir\(g .)\) No es uno a uno ya que\(g(1)=g(2),\) así no\(g^{-1}\) es un mapa.

d) Considerar

\[f : N \rightarrow N, \text{ with } f(x)=2x \text{ for each } x \in N\]

Por lo dicho anteriormente,\(f\) está bien definido. Es uno a uno ya que\(x \neq y\) implica\(2 x \neq 2 y .\) Aquí\(D_{f}=N(\) los naturales\(),\) pero\(D_{f}^{\prime}\) consiste en incluso naturales solamente. Por lo tanto, no\(f\) está en\(N\) (está en un conjunto más pequeño, los naturales pares);\(f^{-1}\) mapea los naturales pares en todos\(N .\)

El dominio y el rango de una relación pueden ser conjuntos bastante arbitrarios. En particular, podemos considerar funciones\(f\) en las que cada elemento del dominio\(D_{f}\) es en sí mismo un par ordenado\((x, y)\) o\(n\) -tupla\(\left(x_{1}, x_{2}, \ldots, x_{n}\right) .\) Tales asignaciones se denominan funciones de dos (respectivamente,\(n )\) variables. A cualquier\(n\) -tupla\(\left(x_{1}, \ldots, x_{n}\right)\) que pertenezca a\(D_{f},\) la función le\(f\) asigna un valor de función único, denotado por\(f\left(x_{1}, \ldots, x_{n}\right) .\) Es conveniente considerar\(x_{1}, x_{2}, \ldots, x_{n}\) como ciertas variables; entonces el valor de la función, también, se convierte en una variable dependiendo de la\(x_{1}, \ldots, x_{n}\). A menudo\(D_{f}\) consiste en todas las\(n\) -tuplas ordenadas de elementos tomados de un conjunto\(A\), es decir,\(D_{f}=A^{n}\) (producto cruzado de\(n\) conjuntos, cada uno igual a\(A ) .\) El rango puede ser un conjunto arbitrario\(B ;\) así\(f : A^{n} \rightarrow B\). De igual manera,\(f : A \times B \rightarrow C\) es una función de dos variables, con\(D_{f}=A \times B, D_{f}^{\prime} \subseteq C\).

Las funciones de dos variables también se denominan operaciones (binarias). Por ejemplo, la adición de números naturales puede tratarse como un mapa\(f : N \times N \rightarrow N,\) con\(f(x, y)=x+y .\)

Definición 4

\(R\)Se dice que una relación es
(i) reflexiva si tenemos\(x R x\) para cada uno\(x \in D_{R}\);
(ii) simétrico iff\(x R y\) siempre implica\(y R x\);
(iii) transitivo iff\(x R y\) combinado con\(y R z\) siempre implica\(x R z\).

\(R\)se denomina relación de equivalencia en un conjunto\(A\) iff\(A=D_{R}\) y\(R\) tiene las tres propiedades (i), (ii) y (iii). Por ejemplo, tal es la relación de igualdad sobre\(A\) (también llamada mapa de identidad en\(A )\) denotado

\[I_{A}=\{(x, y) | x \in A, x=y\}\]

Las relaciones de equivalencia a menudo se denotan con símbolos especiales que se asemejan a la igualdad, como\(\equiv, \approx, \sim,\) etc. La fórmula\(x R y,\) donde\(R\) es tal símbolo, se lee

\["x \text{ is equivalent (or} R \text{-equivalent) to } y,"\]

y\(R[x]=\{y | x R y\}\) (es decir, la\(R\) -imagen de\(x )\) se llama la clase\(R\) -equivalencia (brevemente\(R\) -clase) de\(x\) en\(A ;\) ella consiste en todos los elementos que son\(R\) -equivalentes a\(x\) y por lo tanto a cada otro (para\(x R y\) e\(x R z\) implica primero\(y R x,\) por simetría, y\(y R z,\) por lo tanto por transitividad). Cada uno de esos elementos se llama un representante de la\(R\) clase dada, o su generador. A menudo escribimos\([x]\) para\(R[x]\).

Ejemplo\(\PageIndex{3}\)

(a') La relación de desigualdad\(<\) entre números reales es transitiva ya que

\[x<y \text{ and } y<z \text{ implies } x<z\]

no es ni reflexiva ni simétrica. (¿Por qué?)

(b') La relación de inclusión\(\subseteq\) entre conjuntos es reflexiva (para\(A \subseteq A \)) y transitiva\((\) para\(A \subseteq B\) e\(B \subseteq C\) implica\(A \subseteq C),\) pero no es simétrica.

(c') La relación de pertenencia\(\in\) entre un elemento y un conjunto no es ni reflexiva ni simétrica ni transitiva\((x \in A\) y\(A \in \mathcal{M}\) no implica\(x \in \mathcal{M} )\).

(d') Dejar\(R\) ser la relación de paralelismo entre líneas en un plano, es decir, el conjunto de todos los pares\((X, Y),\) donde\(X\) y\(Y\) son líneas paralelas. Escribir\(\|\) para\(R,\) tenemos\(X\|X, X\| Y\) implica\(Y \| X,\) y\((X \| Y\) y\(Y\)\ |\(Z)\) implica\(X \| Z,\) que así\(R\) es una relación de equivalencia. Una\(R\) clase -aquí consiste en todas las líneas paralelas a una línea dada en el plano.

(e') La congruencia de los triángulos es una relación de equivalencia. (¿Por qué?)

Teorema\(\PageIndex{1}\)

Si\(R\) (también escrito\(\equiv\)) es una relación de equivalencia en\(A,\) entonces todas las clases R- son disjuntas de cada otro, y\(A\) es su unión.

Prueba

Tomar dos\(R\) -clases,\([p] \neq[q]\). Buscando una contradicción, supongamos que no son disjuntos, entonces

\[(\exists x) \quad x \in[p] \text{ and } x \in[q];\]

es decir,\(p \equiv x \equiv q\) y por lo tanto\(p \equiv q .\) Pero entonces, por simetría y transitividad,

\[y \in[p] \Leftrightarrow y \equiv p \Leftrightarrow y \equiv q \Leftrightarrow y \in[q];\]

es decir,\([p]\) y\([q]\) constan de los mismos elementos\(y,\) contrarios a la suposición\([q] \neq[q]\). Así, en efecto, cualesquiera dos\(R\) clases (distintas) son disjuntas.

También, por reflexividad,

\[(\forall x \in A) \quad x \equiv x\]

es decir,\(x \in[x] .\) así cada uno\(x \in A\) está en alguna\(R\) clase (es decir, in\([x] ) ;\) de\(A\) está en la unión de tales clases,

\[A \subseteq \bigcup_{x} R[x]\]

Por el contrario,

\[(\forall x) \quad R[x] \subseteq A\]

desde

\[y \in R[x] \Rightarrow x R y \Rightarrow y R x \Rightarrow(y, x) \in R \Rightarrow y \in D_{R}=A\]

por definición. Así\(A\) contiene todo de\(R[x],\) ahí su unión, y así

\[A=\bigcup_{x} R[x] . \square\]