Operacion matematica
En las matemáticas de las relaciones binarias , la composición de las relaciones es la formación de una nueva relación binaria R ; S a partir de dos relaciones binarias dadas R y S . En el cálculo de relaciones , la composición de las relaciones se llama multiplicación relativa , [1] y su resultado se llama producto relativo . [2] : 40 La composición de funciones es el caso especial de composición de relaciones donde todas las relaciones involucradas son funciones .
La palabra tío indica una relación compuesta: para que una persona sea tío, debe ser hermano de uno de sus padres. En lógica algebraica se dice que la relación del tío ( ) es la composición de las relaciones "es hermano de" ( ) y "es padre de" ( ).![{\displaystyle xUz}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle xBy}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle yPz}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle U=BP\quad {\text{ es equivalente a: }}\quad xByPz{\text{ si y solo si }}xUz.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
A partir de Augustus De Morgan , [3] la forma tradicional de razonamiento por silogismo ha sido subsumida por expresiones lógicas relacionales y su composición. [4]
Definición
Si y son dos relaciones binarias, entonces su composición es la relación![{\displaystyle R\subseteq X\times Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S\subseteq Y\times Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R;S=\{(x,z)\in X\times Z:{\text{ existe }}y\in Y{\text{ tal que }}(x,y)\in R{ \text{ y }}(y,z)\en S\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
En otras palabras, se define por la regla que dice si y sólo si existe un elemento tal que (es decir, y ). [5] : 13 ![{\displaystyle R;S\subseteq X\times Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x,z)\en R;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle y\en Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\,R\,y\,S\,z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (x,y)\en R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (y,z)\en S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Variaciones notacionales
El punto y coma como notación infija para la composición de relaciones se remonta al libro de texto de Ernst Schroder de 1895. [6] Gunther Schmidt ha renovado el uso del punto y coma, particularmente en Matemáticas Relacionales (2011). [2] : 40 [7] El uso de punto y coma coincide con la notación para la composición de funciones utilizada (principalmente por científicos informáticos) en la teoría de categorías , [8] así como la notación para la conjunción dinámica dentro de la semántica dinámica lingüística . [9]
John M. Howie ha utilizado un círculo pequeño para la notación infija de la composición de relaciones en sus libros que consideran semigrupos de relaciones. [10] Sin embargo, el círculo pequeño se usa ampliamente para representar la composición de funciones que invierte la secuencia del texto de la secuencia de operaciones. El círculo pequeño se utilizó en las páginas introductorias de Graphs and Relations [5] : 18 hasta que se abandonó en favor de la yuxtaposición (sin notación infija). La yuxtaposición se usa comúnmente en álgebra para indicar multiplicación, por lo que también puede significar multiplicación relativa.
![{\displaystyle (RS)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Además de la notación circular, se pueden utilizar subíndices. Algunos autores [11] prefieren escribir y explícitamente cuando es necesario, dependiendo de si se aplica primero la relación izquierda o derecha. Otra variación que se encuentra en la informática es la notación Z : se utiliza para indicar la composición tradicional (derecha), mientras que la composición izquierda se indica mediante un punto y coma grueso. Los símbolos Unicode son ⨾ y ⨟. [12] [13]![{\displaystyle \circ _{l}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \circ _{r}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle\circ}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Generalizaciones matemáticas
Las relaciones binarias son morfismos en la categoría . En Rel los objetos son conjuntos , los morfismos son relaciones binarias y la composición de los morfismos es exactamente la composición de las relaciones como se definió anteriormente. La categoría Conjunto de conjuntos y funciones es una subcategoría de donde los mapas son funciones .![{\displaystyle R\subseteq X\times Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\a Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f:X\a Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Dada una categoría regular , su categoría de relaciones internas tiene los mismos objetos que , pero ahora los morfismos están dados por subobjetos en . [14] Formalmente, estos son tramos mónicos conjuntos entre y . Las categorías de relaciones internas son alegorías . En particular . Dado un campo (o más generalmente un dominio ideal principal ), la categoría de relaciones internas a matrices sobre tiene morfismos en subespacios lineales . La categoría de relaciones lineales sobre el campo finito es isomorfa a los escalares de módulo de cálculo ZX del qubit libre de fase .![{\displaystyle \mathbb {X} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}(\mathbb {X} )}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {X} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\a Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\subseteq X\times Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {X} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle k}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle k}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k))}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n\a m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {F} _ {2}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Propiedades
- La composición de las relaciones es asociativa :
![{\displaystyle R;(S;T)=(R;S);T.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- La relación inversa de es Esta propiedad hace que el conjunto de todas las relaciones binarias de un conjunto sea un semigrupo con involución .
![{\displaystyle R\,;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (R\,;S)^{\textsf {T}}=S^{\textsf {T}}\,;R^{\textsf {T}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- La composición de funciones (parciales) (es decir, relaciones funcionales) es nuevamente una función (parcial).
- Si y son inyectivos , entonces es inyectivo, lo que a la inversa implica sólo la inyectividad de
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\,;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Si y son sobreyectivos , entonces es sobreyectivo, lo que a la inversa implica sólo la sobreyectividad de
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\,;S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- El conjunto de relaciones binarias en un conjunto (es decir, relaciones de a ) junto con la composición de relaciones (izquierda o derecha) forma un monoide con cero, donde el mapa de identidad en es el elemento neutro y el conjunto vacío es el elemento cero .
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Composición en términos de matrices.
Las relaciones binarias finitas están representadas por matrices lógicas . Las entradas de estas matrices son cero o uno, dependiendo de si la relación representada es falsa o verdadera para la fila y columna correspondientes a los objetos comparados. Trabajar con tales matrices implica la aritmética booleana con y Una entrada en la matriz producto de dos matrices lógicas será 1, entonces, sólo si la fila y la columna multiplicadas tienen un correspondiente 1. Por lo tanto, se puede encontrar la matriz lógica de una composición de relaciones. calculando el producto matricial de las matrices que representan los factores de la composición. "Las matrices constituyen un método para calcular las conclusiones tradicionalmente extraídas mediante silogismos y sorites hipotéticos ". [15]![{\displaystyle 1+1=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 1\times 1=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Relaciones heterogéneas
Considere una relación heterogénea , es decir, donde y son conjuntos distintos. Luego, usando la composición de la relación con su recíproco, hay relaciones homogéneas (en ) y (en ).![{\displaystyle R\subseteq A\times B;}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RR^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Si para todos existe algo tal que (es decir, es una relación total (izquierda) ), entonces para todos tal que es una relación reflexiva o donde I es la relación de identidad De manera similar, si es una relación sobreyectiva entonces
En este caso , La inclusión opuesta ocurre para una relación difuncional .![{\displaystyle x\en A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle y\en B,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle xRy}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x,xRR^{\textsf {T}}x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RR^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle I\subseteq RR^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \{(x,x):x\en A\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R\supseteq I=\{(x,x):x\in B\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\subseteq RR^{\textsf {T}}R.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La composición se utiliza para distinguir relaciones del tipo de Ferrer, que satisfacen![{\displaystyle {\bar {R}}^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R{\bar {R}}^{\textsf {T}}R=R.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ejemplo
Sean {Francia, Alemania, Italia, Suiza} y {Francés, Alemán, Italiano} con la relación dada por cuando es un idioma nacional de
Dado que ambos y son finitos, se pueden representar mediante una matriz lógica , asumiendo filas (de arriba a abajo) y las columnas (de izquierda a derecha) están ordenadas alfabéticamente:![{\displaystyle A=}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B=}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle aRb}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle b}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La relación inversa corresponde a la matriz transpuesta , y la composición de la relación corresponde al producto de la matriz cuando la suma se implementa mediante disyunción lógica . Resulta que la matriz contiene un 1 en cada posición, mientras que el producto de la matriz invertida se calcula como:
Esta matriz es simétrica y representa una relación homogénea en![{\displaystyle R^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 3\veces 3}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\textsf {T}}R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
En consecuencia, la relación universal es que dos lenguas cualesquiera comparten una nación donde se hablan ambas (de hecho: Suiza). Viceversa, la pregunta de si dos naciones determinadas comparten un idioma se puede responder usando![{\displaystyle R^{\textsf {T}}\,;R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R\,;R^{\textsf {T}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
reglas de schröder
Para un conjunto dado, la colección de todas las relaciones binarias forma una red booleana ordenada por inclusión . Recuerde que la complementación invierte la inclusión:
En el cálculo de relaciones [16] es común representar el complemento de un conjunto mediante una barra superior:![{\displaystyle V,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (\subseteq ).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A\subseteq B{\text{ implica }}B^{\complement }\subseteq A^{\complement }.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\bar {A}}=A^{\complemento }.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Si es una relación binaria, representemos la relación inversa , también llamada transpuesta . Entonces las reglas de Schröder son
Verbalmente, se puede obtener una equivalencia de otra: seleccionar el primer o segundo factor y transponerlo; luego complemente las otras dos relaciones y permutelas. [5] : 15-19 ![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle QR\subseteq S\quad {\text{ es equivalente a }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text { es equivalente a }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Aunque Ernst Schröder detalló esta transformación de la inclusión de una composición de relaciones , de hecho, Augustus De Morgan articuló por primera vez la transformación como Teorema K en 1860. [4] Escribió [17] ![{\displaystyle LM\subseteq N{\text{ implica }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Con las reglas de Schröder y la complementación se puede resolver una relación desconocida en inclusiones de relaciones como,
por ejemplo, mediante la regla de Schröder y la complementación se obtiene lo que se denomina residual izquierdo de por No se pudo analizar (SVG (MathML se puede habilitar a través del complemento del navegador): No válido respuesta ("La extensión Math no puede conectarse a Restbase") del servidor "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle R} .![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RX\subseteq S\quad {\text{y}}\quad XR\subseteq S.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle RX\subseteq S{\text{ implica }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle S}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Cocientes
Así como la composición de relaciones es un tipo de multiplicación que da como resultado un producto, algunas operaciones se comparan con la división y producen cocientes. Aquí se exhiben tres cocientes: residual izquierdo, residual derecho y cociente simétrico. El residual izquierdo de dos relaciones se define suponiendo que tienen el mismo dominio (fuente), y el residual derecho supone el mismo codominio (rango, objetivo). El cociente simétrico supone que dos relaciones comparten un dominio y un codominio.
Definiciones:
- Residual izquierdo:
![{\displaystyle A\barra invertida B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Residual derecho:
![{\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Cociente simétrico:
![{\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Usando las reglas de Schröder, es equivalente a Por lo tanto, el residual izquierdo es la relación más satisfactoria De manera similar, la inclusión es equivalente a y el residual derecho es la relación más satisfactoria [2] : 43-6 ![{\displaystyle AX\subseteq B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X\subseteq A\barra invertida B.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle AX\subseteq B.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle YC\subseteq D}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y\subseteq D/C,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle YC\subseteq D.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Se puede practicar la lógica de los residuos con el Sudoku . [ Se necesita más explicación ]
Unirse: otra forma de composición
Se ha introducido un operador de bifurcación para fusionar dos relaciones y en La construcción depende de proyecciones y se entiende como relaciones, lo que significa que hay relaciones inversas y Luego el![{\displaystyle (<)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle c:H\a A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d:H\a B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle c\,(<)\,d:H\to A\times B.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a:A\times B\to A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle b:A\times B\to B,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle a^{\textsf {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
bifurcación deyestá dada por[18]![{\displaystyle c}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle c\,(<)\,d~\mathrel {:=} ~c;a^{\textsf {T}}\cap \ d;b^{\textsf {T}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Otra forma de composición de relaciones, que se aplica a las relaciones de lugar general, es la operación conjunta del álgebra relacional . La composición habitual de dos relaciones binarias, tal como se define aquí, se puede obtener tomando su unión, lo que lleva a una relación ternaria, seguida de una proyección que elimina el componente medio. Por ejemplo, en el lenguaje de consulta SQL existe la operación Unirse (SQL) .![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n\geq 2,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ver también
Notas
- ^ Bjarni Jónssen (1984) "Álgebras máximas de relaciones binarias", en Contribuciones a la teoría de grupos , editor de KI Appel American Mathematical Society ISBN 978-0-8218-5035-0
- ^ abc Gunther Schmidt (2011) Matemáticas relacionales , Enciclopedia de las matemáticas y sus aplicaciones, vol. 132, Prensa de la Universidad de Cambridge ISBN 978-0-521-76268-7
- ^ A. De Morgan (1860) "Sobre el silogismo: IV y sobre la lógica de las relaciones"
- ^ ab Daniel D. Merrill (1990) Augustus De Morgan y la lógica de las relaciones , página 121, Kluwer Academic ISBN 9789400920477
- ^ abc Gunther Schmidt y Thomas Ströhlein (1993) Relaciones y gráficos , libros de Springer
- ^ Ernst Schroder (1895) Álgebra und Logik der Relative
- ^ Paul Taylor (1999). Fundamentos prácticos de las matemáticas. Prensa de la Universidad de Cambridge. pag. 24.ISBN 978-0-521-63107-5.Una versión HTML gratuita del libro está disponible en http://www.cs.man.ac.uk/~pt/Practical_Foundations/
- ^ Michael Barr y Charles Wells (1998) Teoría de categorías para informáticos Archivado el 4 de marzo de 2016 en Wayback Machine , página 6, de la Universidad McGill
- ^ Rick Nouwen y otros (2016) Semántica dinámica §2.2, de la Enciclopedia de Filosofía de Stanford
- ^ John M. Howie (1995) Fundamentos de la teoría de semigrupos , página 16, monografía n.º 12 de LMS, Clarendon Press ISBN 0-19-851194-9
- ^ Kilp, Knauer y Mikhalev, pag. 7
- ^ ISO/IEC 13568:2002(E), pág. 23
- ^ Consulte U+2A3E y U+2A1F en FileFormat.info
- ^ "relaciones internas". laboratorio . Consultado el 26 de septiembre de 2023 .
- ^ Irving Copilowish (diciembre de 1948) "Desarrollo matricial del cálculo de relaciones", Journal of Symbolic Logic 13(4): 193–203 Enlace Jstor, cita de la página 203
- ^ Vaughn Pratt Los orígenes del cálculo de relaciones, de la Universidad de Stanford
- ^ De Morgan indicó los contrarios en minúsculas, conversión como M −1 e inclusión con )), por lo que su notación fue
![{\displaystyle nM^{-1}))\ l.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- ^ Gunther Schmidt y Michael Winter (2018): Topología relacional , página 26, Lecture Notes in Mathematics vol. 2208, libros de Springer , ISBN 978-3-319-74451-3
Referencias
- M. Kilp, U. Knauer, AV Mikhalev (2000) Monoides, actos y categorías con aplicaciones a productos y gráficos de coronas , De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter , ISBN 3-11-015248-7 .