2.7: Operaciones en Relaciones
- Page ID
- 103813
A menudo es útil modificar o combinar relaciones. En la Proposición 2.5.1, consideramos la unión de relaciones, que es solo la unión de dos relaciones consideradas como conjuntos de pares. De igual manera, en la Proposición 2.5.2, se consideró la diferencia relativa de relaciones. Aquí hay algunas otras operaciones que podemos realizar en las relaciones.
Definición\(\PageIndex{1}\)
Dejemos\(R\),\(S\) sean relaciones, y\(A\) sean cualquier conjunto.
La inversa de\(R\) es\(R^{-1} = \Setabs{\tuple{y, x}}{\tuple{x, y} \in R}\).
El producto relativo de\(R\) y\(S\) es\((R \mid S) = \{\tuple{x, z} : \exists y(Rxy \land Syz)\}\).
La restricción de\(R\) a\(A\) es\(\funrestrictionto{R}{A}= R \cap A^2\).
La aplicación de\(R\) to\(A\) es\(\funimage{R}{A} = \{y : (\exists x \in A)Rxy\}\)
Ejemplo\(\PageIndex{1}\)
\(S \subseteq \Int^2\)Sea la relación sucesora sobre\(\Int\), es decir,\(S = \Setabs{\tuple{x, y} \in \Int^2}{x + 1 = y}\), para que\(Sxy\) iff\(x + 1 = y\).
\(S^{-1}\)es la relación predecesora sobre\(\Int\), es decir,\(\Setabs{\tuple{x,y}\in\Int^2}{x -1 =y}\).
\(S\mid S\)es\(\Setabs{\tuple{x,y}\in\Int^2}{x + 2 =y}\)
\(\funrestrictionto{S}{\Nat}\)es la relación sucesora en\(\Nat\).
\(\funimage{S}{\{1,2,3\}}\)es\(\{2, 3, 4\}\).
Definición\(\PageIndex{2}\): Transitive closure
Dejar\(R \subseteq A^2\) ser una relación binaria.
El cierre transitivo de\(R\) is\(R^+ = \bigcup_{0 < n \in \Nat} R^n\), donde definimos recursivamente\(R^1 = R\) y\(R^{n+1} = R^n \mid R\).
El cierre transitivo reflexivo de\(R\) es\(R^* = R^+ \cup \Id{X}\).
Ejemplo\(\PageIndex{2}\)
Toma la relación sucesora\(S \subseteq \Int^2\). \(S^2xy\)iff\(x + 2 = y\),\(S^3xy\) iff\(x + 3 = y\), etc. así que\(S^+xy\) iff\(x + n = y\) para algunos\(n > 1\). En otras palabras,\(S^+xy\) iff\(x < y\) e\(S^*xy\) iff\(x \le y\).
Problema\(\PageIndex{1}\)
Demostrar que el cierre transitivo de\(R\) es de hecho transitivo.