Relación binaria

Relación entre elementos de dos conjuntos

En matemáticas , una relación binaria asocia elementos de un conjunto llamado dominio con elementos de otro conjunto llamado codominio . ^[1] Precisamente, una relación binaria sobre conjuntos y es un conjunto de pares ordenados donde está en y está en . ^[2] Codifica el concepto común de relación: un elemento está relacionado con un elemento , si y solo si el par pertenece al conjunto de pares ordenados que define la relación binaria. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle y}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)}$

Un ejemplo de una relación binaria es la relación " divide " sobre el conjunto de números primos y el conjunto de números enteros , en la que cada primo está relacionado con cada entero que es múltiplo de , pero no con un entero que no es múltiplo de . En esta relación, por ejemplo, el número primo está relacionado con números como , , , , pero no con o , al igual que el número primo está relacionado con , , y , pero no con o . ${\displaystyle \mathbb {P} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle p}$ ${\displaystyle z}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle 2}$ ${\displaystyle -4}$ ${\displaystyle 0}$ ${\displaystyle 6}$ ${\displaystyle 10}$ ${\displaystyle 1}$ ${\displaystyle 9}$ ${\displaystyle 3}$ ${\displaystyle 0}$ ${\displaystyle 6}$ ${\displaystyle 9}$ ${\displaystyle 4}$ ${\displaystyle 13}$

Las relaciones binarias, y especialmente las relaciones homogéneas , se utilizan en muchas ramas de las matemáticas para modelar una amplia variedad de conceptos. Entre ellos se incluyen:

• las relaciones " es mayor que ", " es igual a " y "divide" en aritmética ;
• la relación " es congruente con " en geometría ;
• la relación "es adyacente a" en la teoría de grafos ;
• La relación "es ortogonal a" en álgebra lineal .

Una función puede definirse como una relación binaria que cumple restricciones adicionales. ^[3] Las relaciones binarias también se utilizan ampliamente en informática .

Una relación binaria sobre conjuntos y es un elemento del conjunto potencia de Dado que este último conjunto está ordenado por inclusión ( ), cada relación tiene un lugar en la red de subconjuntos de Una relación binaria se denomina relación homogénea cuando . Una relación binaria también se denomina relación heterogénea cuando no es necesario que . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\times Y.}$ ${\displaystyle \subseteq }$ ${\displaystyle X\times Y.}$ ${\displaystyle X=Y}$ ${\displaystyle X=Y}$

Dado que las relaciones son conjuntos, se pueden manipular utilizando operaciones de conjuntos, incluyendo unión , intersección y complementación , y satisfaciendo las leyes de un álgebra de conjuntos . Más allá de eso, están disponibles operaciones como el inverso de una relación y la composición de relaciones , satisfaciendo las leyes de un cálculo de relaciones , para el cual existen libros de texto de Ernst Schröder , ^[4] Clarence Lewis , ^[5] y Gunther Schmidt . ^[6] Un análisis más profundo de las relaciones implica descomponerlas en subconjuntos llamados conceptos y colocarlos en un retículo completo .

En algunos sistemas de teoría axiomática de conjuntos , las relaciones se extienden a clases , que son generalizaciones de conjuntos. Esta extensión es necesaria, entre otras cosas, para modelar los conceptos de "es un elemento de" o "es un subconjunto de" en la teoría de conjuntos, sin caer en inconsistencias lógicas como la paradoja de Russell .

Una relación binaria es el caso especial más estudiado de una relación -aria sobre conjuntos , que es un subconjunto del producto cartesiano ^[2] ${\displaystyle n=2}$ ${\displaystyle n}$ ${\displaystyle X_{1},\dots ,X_{n}}$ ${\displaystyle X_{1}\times \cdots \times X_{n}.}$

Definición

Dados los conjuntos y , el producto cartesiano se define como y sus elementos se denominan pares ordenados . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\times Y}$ ${\displaystyle \{(x,y)\mid x\in X{\text{ and }}y\in Y\},}$

Una relación binaria sobre conjuntos y es un subconjunto de ^{[2] [7]} El conjunto se denomina dominio ^[2] o conjunto de partida de , y el conjunto codominio o conjunto de destino de . Para especificar las opciones de los conjuntos y , algunos autores definen una relación o correspondencia binaria como una terna ordenada , donde es un subconjunto de llamado grafo de la relación binaria. El enunciado dice " está -relacionado con " y se denota por . ^{[4] [5] [6] [nota 1]} El dominio de definición o dominio activo ^[2] de es el conjunto de todos tales que para al menos uno . El codominio de definición , codominio activo , ^[2] imagen o rango de es el conjunto de todos tales que para al menos uno . El cuerpo de es la unión de su dominio de definición y su codominio de definición. ^{[9] [10] [11]} ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\times Y.}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle (X,Y,G)}$ ${\displaystyle G}$ ${\displaystyle X\times Y}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle xRy}$ ${\displaystyle y}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle x}$ ${\displaystyle R}$

Cuando una relación binaria se denomina relación homogénea (o endorrelación ), para enfatizar el hecho de que se permite que y sean diferentes, una relación binaria también se denomina relación heterogénea . ^{[12] [13] [14]} El prefijo hetero proviene del griego ἕτερος ( heteros , "otro, otro, diferente"). ${\displaystyle X=Y,}$ ${\displaystyle X}$ ${\displaystyle Y}$

Una relación heterogénea se ha denominado relación rectangular , ^[14] lo que sugiere que no tiene la simetría cuadrada de una relación homogénea en un conjunto donde Al comentar sobre el desarrollo de relaciones binarias más allá de las relaciones homogéneas, los investigadores escribieron, "... una variante de la teoría ha evolucionado que trata las relaciones desde el principio como heterogéneas o rectangulares , es decir, como relaciones donde el caso normal es que son relaciones entre conjuntos diferentes". ^[15] ${\displaystyle A=B.}$

Los términos correspondencia , ^[16] relación diádica y relación de dos lugares son sinónimos de relación binaria, aunque algunos autores usan el término "relación binaria" para cualquier subconjunto de un producto cartesiano sin referencia a y , y reservan el término "correspondencia" para una relación binaria con referencia a y . ^{[ cita requerida ]} ${\displaystyle X\times Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

En una relación binaria, el orden de los elementos es importante; si entonces puede ser verdadero o falso independientemente de . Por ejemplo, divide , pero no divide . ${\displaystyle x\neq y}$ ${\displaystyle yRx}$ ${\displaystyle xRy}$ ${\displaystyle 3}$ ${\displaystyle 9}$ ${\displaystyle 9}$ ${\displaystyle 3}$

Operaciones

Unión

Si y son relaciones binarias sobre conjuntos y entonces es la relación de unión de y sobre y . ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R\cup S=\{(x,y)\mid xRy{\text{ or }}xSy\}}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

El elemento de identidad es la relación vacía. Por ejemplo, es la unión de < y =, y es la unión de > y =. ${\displaystyle \leq }$ ${\displaystyle \geq }$

Intersección

Si y son relaciones binarias sobre conjuntos y entonces es la relación de intersección de y sobre y . ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R\cap S=\{(x,y)\mid xRy{\text{ and }}xSy\}}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

El elemento de identidad es la relación universal. Por ejemplo, la relación "es divisible por 6" es la intersección de las relaciones "es divisible por 3" y "es divisible por 2".

Composición

Si es una relación binaria sobre conjuntos y , y es una relación binaria sobre conjuntos y entonces (también denotado por ) es la relación de composición de y sobre y . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle S\circ R=\{(x,z)\mid {\text{ there exists }}y\in Y{\text{ such that }}xRy{\text{ and }}ySz\}}$ ${\displaystyle R;S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Z}$

El elemento de identidad es la relación de identidad. El orden de y en la notación utilizada aquí concuerda con el orden de notación estándar para la composición de funciones . Por ejemplo, la composición (es padre de) (es madre de) da como resultado (es abuelo materno de), mientras que la composición (es madre de) (es padre de) da como resultado (es abuela de). Para el primer caso, si es el padre de y es la madre de , entonces es el abuelo materno de . ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S\circ R,}$ ${\displaystyle \circ }$ ${\displaystyle \circ }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$

Conversar

Si es una relación binaria sobre conjuntos y entonces es la relación inversa , ^[17] también llamada relación inversa , ^[18] de sobre y . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R^{\textsf {T}}=\{(y,x)\mid xRy\}}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle X}$

Por ejemplo, es el inverso de sí mismo, como es , y y son inversos entre sí, como lo son y . Una relación binaria es igual a su inverso si y solo si es simétrica . ${\displaystyle =}$ ${\displaystyle \neq }$ ${\displaystyle <}$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle \geq }$

Complementar

Si es una relación binaria sobre conjuntos y entonces (también denotado por ) es la relación complementaria de sobre y . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\bar {R}}=\{(x,y)\mid \neg xRy\}}$ ${\displaystyle \neg R}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$

Por ejemplo, y son complementos entre sí, como lo son y , y , y , y para órdenes totales también y , y y . ${\displaystyle =}$ ${\displaystyle \neq }$ ${\displaystyle \subseteq }$ ${\displaystyle \not \subseteq }$ ${\displaystyle \supseteq }$ ${\displaystyle \not \supseteq }$ ${\displaystyle \in }$ ${\displaystyle \not \in }$ ${\displaystyle <}$ ${\displaystyle \geq }$ ${\displaystyle >}$ ${\displaystyle \leq }$

El complemento de la relación inversa es el inverso del complemento: ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.}$

Si el complemento tiene las siguientes propiedades: ${\displaystyle X=Y,}$

• Si una relación es simétrica, entonces también lo es el complemento.
• El complemento de una relación reflexiva es irreflexiva y viceversa.
• El complemento de un orden débil estricto es un preorden total, y viceversa.

Restricción

Si es una relación homogénea binaria sobre un conjunto y es un subconjunto de entonces es ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S{\text{ and }}y\in S\}}$relación de restricción deamás de. ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$

Si es una relación binaria sobre conjuntos y y si es un subconjunto de entonces es ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S\}}$relación de restricción izquierda deasobrey.^{[ aclaración necesaria ]} ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

Si una relación es reflexiva , irreflexiva, simétrica , antisimétrica , asimétrica , transitiva , total , tricotómica , de orden parcial , de orden total , de orden débil estricto , de preorden total (orden débil) o una relación de equivalencia , entonces también lo son sus restricciones.

Sin embargo, la clausura transitiva de una restricción es un subconjunto de la restricción de la clausura transitiva, es decir, en general no es igual. Por ejemplo, restringir la relación " es padre de " a mujeres produce la relación " es madre de la mujer "; su clausura transitiva no relaciona a una mujer con su abuela paterna. Por otro lado, la clausura transitiva de "es padre de" es "es antecesor de"; su restricción a mujeres sí relaciona a una mujer con su abuela paterna. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Además, los diversos conceptos de completitud (que no deben confundirse con ser "total") no se aplican a las restricciones. Por ejemplo, sobre los números reales, una propiedad de la relación es que todo subconjunto no vacío con un límite superior en tiene un límite superior mínimo (también llamado supremo) en Sin embargo, para los números racionales, este supremo no es necesariamente racional, por lo que la misma propiedad no se cumple en la restricción de la relación a los números racionales. ${\displaystyle \leq }$ ${\displaystyle S\subseteq \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} .}$ ${\displaystyle \leq }$

Una relación binaria sobre conjuntos y se dice que es ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$contenido en una relaciónsobrey, escritosies un subconjunto de, es decir, para todosysi, entonces. Siestá contenido enyestá contenido en, entoncesyse llamanigualesescritos. Siestá contenido enperono está contenido en, entoncesse dice que es ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R\subseteq S,}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y,}$ ${\displaystyle xRy}$ ${\displaystyle xSy}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R=S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle R}$menor que, escritoPor ejemplo, en losnúmeros racionales, la relaciónes menor que, e igual a la composición. ${\displaystyle S}$ ${\displaystyle R\subsetneq S.}$ ${\displaystyle >}$ ${\displaystyle \geq }$ ${\displaystyle >\circ >}$

Representación matricial

Las relaciones binarias sobre conjuntos y pueden representarse algebraicamente mediante matrices lógicas indexadas por y con entradas en el semianillo booleano (la adición corresponde a OR y la multiplicación a AND) donde la adición de matrices corresponde a la unión de relaciones, la multiplicación de matrices corresponde a la composición de relaciones (de una relación sobre y y una relación sobre y ), ^[19] el producto de Hadamard corresponde a la intersección de relaciones, la matriz cero corresponde a la relación vacía y la matriz de unos corresponde a la relación universal. Las relaciones homogéneas (cuando ) forman un semianillo matricial (de hecho, un semiálgebra matricial sobre el semianillo booleano) donde la matriz identidad corresponde a la relación identidad. ^[20] ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle X=Y}$

Ejemplos

1. El siguiente ejemplo muestra que la elección del codominio es importante. Supongamos que hay cuatro objetos y cuatro personas. Una posible relación en y es la relación "es propiedad de", dada por Es decir, John es dueño de la pelota, Mary es dueña de la muñeca y Venus es dueña del auto. Nadie es dueño de la taza e Ian no es dueño de nada; vea el primer ejemplo. Como conjunto, no involucra a Ian y, por lo tanto, podría haber sido visto como un subconjunto de ie una relación sobre y vea el segundo ejemplo. Pero en ese segundo ejemplo, no contiene información sobre la propiedad de Ian. ${\displaystyle A=\{{\text{ball, car, doll, cup}}\}}$ ${\displaystyle B=\{{\text{John, Mary, Ian, Venus}}\}.}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R=\{({\text{ball, John}}),({\text{doll, Mary}}),({\text{car, Venus}})\}.}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle A\times \{{\text{John, Mary, Venus}}\},}$ ${\displaystyle A}$ ${\displaystyle \{{\text{John, Mary, Venus}}\};}$ ${\displaystyle R}$

   Si bien la relación del segundo ejemplo es sobreyectiva (ver más abajo), la primera no lo es.

   

   Océanos y continentes (se omiten las islas)

2. Sean , los océanos del globo, y , los continentes . Sea , los océanos los que limitan con los continentes . Entonces, la matriz lógica para esta relación es: ${\displaystyle A=\{{\text{Indian}},{\text{Arctic}},{\text{Atlantic}},{\text{Pacific}}\}}$ ${\displaystyle B=\{{\text{NA}},{\text{SA}},{\text{AF}},{\text{EU}},{\text{AS}},{\text{AU}},{\text{AA}}\}}$ ${\displaystyle aRb}$ ${\displaystyle a}$ ${\displaystyle b}$

   ${\displaystyle R={\begin{pmatrix}0&0&1&0&1&1&1\\1&0&0&1&1&0&0\\1&1&1&1&0&0&1\\1&1&0&0&1&1&1\end{pmatrix}}.}$

   La conectividad del planeta Tierra puede verse a través de y , siendo la primera una relación en , que es la relación universal ( o una matriz lógica de todos los unos). Esta relación universal refleja el hecho de que cada océano está separado de los demás por, como máximo, un continente. Por otro lado, es una relación en que no logra ser universal porque se deben atravesar al menos dos océanos para viajar de Europa a Australia . ${\displaystyle RR^{\mathsf {T}}}$ ${\displaystyle R^{\mathsf {T}}R}$ ${\displaystyle 4\times 4}$ ${\displaystyle A}$ ${\displaystyle A\times A}$ ${\displaystyle R^{\mathsf {T}}R}$ ${\displaystyle B\times B}$
3. La visualización de las relaciones se apoya en la teoría de grafos : para las relaciones en un conjunto (relaciones homogéneas), un grafo dirigido ilustra una relación y un grafo una relación simétrica . Para las relaciones heterogéneas, un hipergrafo tiene aristas que pueden tener más de dos nodos y puede ilustrarse mediante un grafo bipartito . Así como la clique es parte integral de las relaciones en un conjunto, las bicliques se utilizan para describir las relaciones heterogéneas; de hecho, son los "conceptos" que generan una red asociada con una relación.

   

   Los distintos ejes representan el tiempo para los observadores en movimiento, los ejes correspondientes son sus líneas de simultaneidad. ${\displaystyle t}$ ${\displaystyle x}$

4. Ortogonalidad hiperbólica : el tiempo y el espacio son categorías diferentes, y las propiedades temporales están separadas de las propiedades espaciales. La idea de eventos simultáneos es simple en tiempo y espacio absolutos , ya que cada tiempo determina un hiperplano simultáneo en esa cosmología. Hermann Minkowski cambió eso cuando articuló la noción de simultaneidad relativa , que existe cuando los eventos espaciales son "normales" a un tiempo caracterizado por una velocidad. Utilizó un producto interno indefinido y especificó que un vector de tiempo es normal a un vector de espacio cuando ese producto es cero. El producto interno indefinido en un álgebra de composición está dado por ${\displaystyle t}$

   ${\displaystyle \langle x,z\rangle =x{\bar {z}}+{\bar {x}}z\;}$donde la barra superior denota conjugación.

   Como relación entre algunos eventos temporales y algunos eventos espaciales, la ortogonalidad hiperbólica (como la que se encuentra en los números complejos divididos ) es una relación heterogénea. ^[21]
5. Una configuración geométrica puede considerarse una relación entre sus puntos y sus líneas. La relación se expresa como incidencia . Se incluyen planos proyectivos y afines finitos e infinitos. Jakob Steiner fue pionero en la catalogación de configuraciones con los sistemas de Steiner que tienen un conjunto de n elementos y un conjunto de subconjuntos de k elementos llamados bloques , de modo que un subconjunto con elementos se encuentra en un solo bloque. Estas estructuras de incidencia se han generalizado con diseños de bloques . La matriz de incidencia utilizada en estos contextos geométricos corresponde a la matriz lógica utilizada generalmente con relaciones binarias. ${\displaystyle \operatorname {S} (t,k,n)}$ ${\displaystyle \operatorname {S} }$ ${\displaystyle t}$

   Una estructura de incidencia es una tripleta donde y son dos conjuntos disjuntos y es una relación binaria entre y , es decir, los elementos de se llamarán puntos , los de bloques y los de banderas . ^[22] ${\displaystyle \mathbf {D} =(V,\mathbf {B} ,I)}$ ${\displaystyle V}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle I}$ ${\displaystyle V}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle I\subseteq V\times \mathbf {B} .}$ ${\displaystyle V}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle I}$

Tipos de relaciones binarias

Ejemplos de cuatro tipos de relaciones binarias sobre números reales : uno a uno (en verde), uno a muchos (en azul), muchos a uno (en rojo), muchos a muchos (en negro).

A continuación se enumeran algunos tipos importantes de relaciones binarias sobre conjuntos . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$

Propiedades de unicidad:

• Inyectiva ^[23] (también llamada única por la izquierda ^[24] ): para todos y todos si y entonces . En otras palabras, cada elemento del codominio tiene como máximo un elemento de preimagen . Para una relación de este tipo, se llama clave primaria de . ^[2] Por ejemplo, las relaciones binarias verde y azul en el diagrama son inyectivas, pero la roja no lo es (ya que relaciona tanto a como a ), ni tampoco la negra (ya que relaciona tanto a como a ). ${\displaystyle x,y\in X}$ ${\displaystyle z\in Y,}$ ${\displaystyle xRz}$ ${\displaystyle yRz}$ ${\displaystyle x=y}$ ${\displaystyle Y}$ ${\displaystyle R}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 0}$
• Funcional ^{[23] [25] [26]} (también llamada única por la derecha ^[24] o univalente ^[27] ): para todosy todossiyentonces. En otras palabras, cada elemento del dominio tiene como máximo un elemento de imagen . Una relación binaria de este tipo se denomina función parcial o aplicación parcial . ^[28] Para una relación de este tipo,se denomina clave primaria de. ^[2] Por ejemplo, las relaciones binarias roja y verde en el diagrama son funcionales, pero la azul no lo es (ya que se relacionacon ambosy), ni la negra (ya que se relacionacon ambosy). ${\displaystyle x\in X}$ ${\displaystyle y,z\in Y,}$ ${\displaystyle xRy}$ ${\displaystyle xRz}$ ${\displaystyle y=z}$ ${\displaystyle \{X\}}$ ${\displaystyle R}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle 0}$ ${\displaystyle -1}$ ${\displaystyle 1}$
• Uno a uno : inyectiva y funcional. Por ejemplo, la relación binaria verde en el diagrama es uno a uno, pero las roja, azul y negra no lo son.
• Uno a muchos : inyectiva y no funcional. Por ejemplo, la relación binaria azul del diagrama es uno a muchos, pero las de rojo, verde y negro no lo son.
• Muchos a uno : funcional y no inyectiva. Por ejemplo, la relación binaria roja en el diagrama es de muchos a uno, pero las verde, azul y negra no lo son.
• Muchos a muchos : no es inyectiva ni funcional. Por ejemplo, la relación binaria negra del diagrama es de muchos a muchos, pero las de rojo, verde y azul no.

Propiedades de totalidad (sólo definibles si se especifican el dominio y el codominio ): ${\displaystyle X}$ ${\displaystyle Y}$

• Total ^[23] (también llamada total por la izquierda ^[24] ): para todoexiste untal que. En otras palabras, cada elemento del dominio tiene al menos un elemento imagen. En otras palabras, el dominio de la definición dees igual a. Esta propiedad, es diferente de la definición de conexo (también llamado total por algunos autores) ^{[ cita requerida ]} en Propiedades . Tal relación binaria se llama función multivaluada . Por ejemplo, las relaciones binarias roja y verde en el diagrama son totales, pero la azul no lo es (ya que no se relacionacon ningún número real), ni la negra (ya que no se relacionacon ningún número real). Como otro ejemplo,es una relación total sobre los números enteros . Pero no es una relación total sobre los números enteros positivos, porque no hay ningúnen los números enteros positivos tal que. ^[29] Sin embargo,es una relación total sobre los números enteros positivos, los números racionales y los números reales. Toda relación reflexiva es total: para un dado, elija. ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle -1}$ ${\displaystyle 2}$ ${\displaystyle >}$ ${\displaystyle y}$ ${\displaystyle 1>y}$ ${\displaystyle <}$ ${\displaystyle x}$ ${\displaystyle y=x}$
• Sobreyectiva ^[23] (también llamada total derecha ^[24] ): para todo , existe un tal que . En otras palabras, cada elemento del codominio tiene al menos un elemento de preimagen. En otras palabras, el codominio de definición de es igual a . Por ejemplo, las relaciones binarias verde y azul en el diagrama son sobreyectivas, pero la roja no lo es (ya que no relaciona ningún número real con ), ni la negra (ya que no relaciona ningún número real con ). ${\displaystyle y\in Y}$ ${\displaystyle x\in X}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle -1}$ ${\displaystyle 2}$

Propiedades de unicidad y totalidad (sólo definibles si se especifican el dominio y el codominio ): ${\displaystyle X}$ ${\displaystyle Y}$

• Una función (también llamada mapeo ^[24] ): una relación binaria que es funcional y total. En otras palabras, cada elemento del dominio tiene exactamente un elemento de imagen. Por ejemplo, las relaciones binarias roja y verde en el diagrama son funciones, pero las azul y negra no lo son.
• Una inyección : una función que es inyectiva. Por ejemplo, la relación verde del diagrama es una inyección, pero la roja no; la relación negra y azul ni siquiera es una función.
• Una sobreyección : una función que es sobreyectiva. Por ejemplo, la relación verde del diagrama es una sobreyección, pero la roja no.
• Una biyección : una función que es inyectiva y sobreyectiva. En otras palabras, cada elemento del dominio tiene exactamente un elemento imagen y cada elemento del codominio tiene exactamente un elemento preimagen. Por ejemplo, la relación binaria verde en el diagrama es una biyección, pero la roja no.

Si se permiten relaciones sobre clases propias:

• Conjunto-similar (también llamado local ): para todos los , la clase de todos los tales que , es decir , es un conjunto. Por ejemplo, la relación es conjunto-similar, y toda relación en dos conjuntos es conjunto-similar. ^[30] La ordenación habitual < sobre la clase de números ordinales es una relación conjunto-similar, mientras que su inversa > no lo es. ^{[ cita requerida ]} ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle yRx}$ ${\displaystyle \{y\in Y,yRx\}}$ ${\displaystyle \in }$

Conjuntos versus clases

Ciertas "relaciones" matemáticas, como "igual a", "subconjunto de" y "miembro de", no pueden entenderse como relaciones binarias según la definición anterior, porque sus dominios y codominios no pueden tomarse como conjuntos en los sistemas habituales de la teoría de conjuntos axiomática . Por ejemplo, para modelar el concepto general de "igualdad" como una relación binaria , tome el dominio y el codominio como la "clase de todos los conjuntos", que no es un conjunto en la teoría de conjuntos habitual. ${\displaystyle =}$

En la mayoría de los contextos matemáticos, las referencias a las relaciones de igualdad, pertenencia y subconjunto son inofensivas porque pueden entenderse implícitamente como restringidas a algún conjunto en el contexto. La solución habitual a este problema es seleccionar un conjunto "suficientemente grande" , que contenga todos los objetos de interés, y trabajar con la restricción en lugar de . De manera similar, la relación "subconjunto de" debe restringirse para tener dominio y codominio (el conjunto potencia de un conjunto específico ): la relación de conjunto resultante puede denotarse por Además, la relación "miembro de" debe restringirse para tener dominio y codominio para obtener una relación binaria que sea un conjunto. Bertrand Russell ha demostrado que suponer que se define sobre todos los conjuntos conduce a una contradicción en la teoría de conjuntos ingenua , consulte la paradoja de Russell . ${\displaystyle A}$ ${\displaystyle =_{A}}$ ${\displaystyle =}$ ${\displaystyle \subseteq }$ ${\displaystyle P(A)}$ ${\displaystyle A}$ ${\displaystyle \subseteq _{A}.}$ ${\displaystyle A}$ ${\displaystyle P(A)}$ ${\displaystyle \in _{A}}$ ${\displaystyle \in }$

Otra solución a este problema es utilizar una teoría de conjuntos con clases propias, como NBG o la teoría de conjuntos de Morse-Kelley , y permitir que el dominio y el codominio (y por lo tanto el grafo) sean clases propias : en dicha teoría, la igualdad, la pertenencia y el subconjunto son relaciones binarias sin comentarios especiales. (Es necesario realizar una pequeña modificación al concepto de triple ordenado , ya que normalmente una clase propia no puede ser miembro de una tupla ordenada; o, por supuesto, se puede identificar la relación binaria con su grafo en este contexto). ^[31] Con esta definición se puede, por ejemplo, definir una relación binaria sobre cada conjunto y su conjunto potencia. ${\displaystyle (X,Y,G)}$

Relación homogénea

Una relación homogénea sobre un conjunto es una relación binaria sobre y sobre sí misma, es decir, es un subconjunto del producto cartesiano ^{[14] [32] [33]} También se denomina simplemente relación (binaria) sobre . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X\times X.}$ ${\displaystyle X}$

Una relación homogénea sobre un conjunto puede identificarse con un grafo simple dirigido que permite bucles , donde es el conjunto de vértices y es el conjunto de aristas (hay una arista de un vértice a un vértice si y solo si ). El conjunto de todas las relaciones homogéneas sobre un conjunto es el conjunto potencia que es un álgebra booleana aumentada con la involución de la aplicación de una relación a su relación inversa . Considerando la composición de relaciones como una operación binaria sobre , forma un semigrupo con involución . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle {\mathcal {B}}(X)}$ ${\displaystyle X}$ ${\displaystyle 2^{X\times X}}$ ${\displaystyle {\mathcal {B}}(X)}$

Algunas propiedades importantes que puede tener una relación homogénea sobre un conjunto son: ${\displaystyle R}$ ${\displaystyle X}$

• Reflexiva : para todos. Por ejemplo,es una relación reflexiva pero > no lo es. ${\displaystyle x\in X,}$ ${\displaystyle xRx}$ ${\displaystyle \geq }$
• Irreflexiva : para todo loque no es. Por ejemplo,es una relación irreflexiva, perono lo es. ${\displaystyle x\in X,}$ ${\displaystyle xRx}$ ${\displaystyle >}$ ${\displaystyle \geq }$
• Simétrica : para todos los casossientonces. Por ejemplo, "es pariente consanguíneo de" es una relación simétrica. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$
• Antisimétrica : para todosiyentoncesPor ejemplo,es una relación antisimétrica. ^[34] ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle x=y.}$ ${\displaystyle \geq }$
• Asimétrica : para todossientonces no. Una relación es asimétrica si y solo si es antisimétrica e irreflexiva. ^[35] Por ejemplo, > es una relación asimétrica, perono lo es. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle \geq }$
• Transitiva : para todosiyentonces. Una relación transitiva es irreflexiva si y solo si es asimétrica. ^[36] Por ejemplo, "es ancestro de" es una relación transitiva, mientras que "es padre de" no lo es. ${\displaystyle x,y,z\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRz}$ ${\displaystyle xRz}$
• Conectado : para todossientonceso. ${\displaystyle x,y\in X,}$ ${\displaystyle x\neq y}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$
• Fuertemente conectado : para todoso. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$
• Denso : para todosiexistealgunoy. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy,}$ ${\displaystyle z\in X}$ ${\displaystyle xRz}$ ${\displaystyle zRy}$

Un orden parcial es una relación que es reflexiva, antisimétrica y transitiva. Un orden parcial estricto es una relación que es irreflexiva, asimétrica y transitiva. Un orden total es una relación que es reflexiva, antisimétrica, transitiva y conexa. ^[37] Un orden total estricto es una relación que es irreflexiva, asimétrica, transitiva y conexa. Una relación de equivalencia es una relación que es reflexiva, simétrica y transitiva. Por ejemplo, " divide " es un orden parcial, pero no total en números naturales " " es un orden total estricto en y " es paralelo a " es una relación de equivalencia en el conjunto de todas las líneas en el plano euclidiano . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \mathbb {N} ,}$ ${\displaystyle x<y}$ ${\displaystyle \mathbb {N} ,}$ ${\displaystyle x}$ ${\displaystyle y}$

Todas las operaciones definidas en la sección § Operaciones también se aplican a las relaciones homogéneas. Además, una relación homogénea sobre un conjunto puede estar sujeta a operaciones de cierre como: ${\displaystyle X}$

Cierre reflexivo

la relación reflexiva más pequeña sobre que contiene , ${\displaystyle X}$ ${\displaystyle R}$

Cierre transitivo

la relación transitiva más pequeña sobre que contiene , ${\displaystyle X}$ ${\displaystyle R}$

Cierre de equivalencia

la relación de equivalencia más pequeña sobre que contiene . ${\displaystyle X}$ ${\displaystyle R}$

Cálculo de relaciones

Los avances en lógica algebraica han facilitado el uso de relaciones binarias. El cálculo de relaciones incluye el álgebra de conjuntos , ampliada mediante la composición de relaciones y el uso de relaciones inversas . El significado de inclusión que implica , establece el escenario en una red de relaciones. Pero dado que el símbolo de inclusión es superfluo. Sin embargo, la composición de relaciones y la manipulación de los operadores según las reglas de Schröder , proporciona un cálculo para trabajar en el conjunto potencia de ${\displaystyle R\subseteq S,}$ ${\displaystyle aRb}$ ${\displaystyle aSb}$ ${\displaystyle P\subseteq Q\equiv (P\cap {\bar {Q}}=\varnothing )\equiv (P\cap Q=P),}$ ${\displaystyle A\times B.}$

A diferencia de las relaciones homogéneas, la composición de relaciones es sólo una función parcial . La necesidad de hacer coincidir el objetivo con la fuente de las relaciones compuestas ha llevado a sugerir que el estudio de las relaciones heterogéneas es un capítulo de la teoría de categorías, como en el caso de la categoría de conjuntos , excepto que los morfismos de esta categoría son relaciones. Los objetos de la categoría Rel son conjuntos, y los morfismos de relación se componen como se requiere en una categoría . ^{[ cita requerida ]}

Red conceptual inducida

Las relaciones binarias se han descrito a través de sus redes de conceptos inducidos : Un concepto satisface dos propiedades: ${\displaystyle C\subset R}$

• La matriz lógica de es el producto externo de los vectores lógicos vectores lógicos . ^{[ aclaración necesaria ]} ${\displaystyle C}$ ${\displaystyle C_{ij}=u_{i}v_{j},\quad u,v}$
• ${\displaystyle C}$es máxima, no está contenida en ningún otro producto exterior. Por lo tanto, se describe como un rectángulo no ampliable . ${\displaystyle C}$

Para una relación dada, el conjunto de conceptos, ampliado por sus uniones y encuentros, forma una "red inducida de conceptos", en la que la inclusión forma un preorden . ${\displaystyle R\subseteq X\times Y,}$ ${\displaystyle \sqsubseteq }$

El teorema de completitud de MacNeille (1937) (que establece que cualquier orden parcial puede estar incluido en una red completa ) se cita en un artículo de investigación de 2013 "Descomposición de relaciones en redes de conceptos". ^[38] La descomposición es

${\displaystyle R=fEg^{\textsf {T}}}$, donde y son funciones , llamadas aplicaciones o relaciones funcionales totales izquierdas en este contexto. El "concepto inducido de red es isomorfo a la terminación de corte del orden parcial que pertenece a la descomposición mínima de la relación ". ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle E}$ ${\displaystyle (f,g,E)}$ ${\displaystyle R}$

A continuación se consideran casos particulares: el orden total corresponde al tipo de Ferrers y la identidad corresponde a difuncional, una generalización de la relación de equivalencia en un conjunto. ${\displaystyle E}$ ${\displaystyle E}$

Las relaciones se pueden clasificar según el rango de Schein , que cuenta la cantidad de conceptos necesarios para cubrir una relación. ^[39] El análisis estructural de las relaciones con conceptos proporciona un enfoque para la minería de datos . ^[40]

Relaciones particulares

• Proposición : Si es una relación sobreyectiva y es su transpuesta, entonces donde es la relación identidad. ${\displaystyle R}$ ${\displaystyle R^{\mathsf {T}}}$ ${\displaystyle I\subseteq R^{\textsf {T}}R}$ ${\displaystyle I}$ ${\displaystyle m\times m}$
• Proposición : Si es una relación serial , entonces donde es la relación identidad. ${\displaystyle R}$ ${\displaystyle I\subseteq RR^{\textsf {T}}}$ ${\displaystyle I}$ ${\displaystyle n\times n}$

Difuncional

La idea de una relación difuncional es dividir objetos mediante la distinción de atributos, como una generalización del concepto de una relación de equivalencia . Una forma de hacerlo es con un conjunto de indicadores intermedios . La relación de partición es una composición de relaciones que utiliza relaciones funcionales . Jacques Riguet denominó a estas relaciones difuncionales , ya que la composición implica relaciones funcionales, comúnmente llamadas funciones parciales . ${\displaystyle Z=\{x,y,z,\ldots \}}$ ${\displaystyle R=FG^{\textsf {T}}}$ ${\displaystyle F\subseteq A\times Z{\text{ and }}G\subseteq B\times Z.}$ ${\displaystyle FG^{\mathsf {T}}}$

En 1950 Riguet demostró que tales relaciones satisfacen la inclusión: ^[41]

$${\displaystyle RR^{\textsf {T}}R\subseteq R}$$

En la teoría de autómatas , el término relación rectangular también se ha utilizado para denotar una relación difuncional. Esta terminología recuerda el hecho de que, cuando se representa como una matriz lógica , las columnas y filas de una relación difuncional se pueden organizar como una matriz de bloques con bloques rectangulares de unos en la diagonal principal (asimétrica). ^[42] Más formalmente, una relación en es difuncional si y solo si se puede escribir como la unión de productos cartesianos , donde los son una partición de un subconjunto de y los también una partición de un subconjunto de . ^[43] ${\displaystyle R}$ ${\displaystyle X\times Y}$ ${\displaystyle A_{i}\times B_{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle X}$ ${\displaystyle B_{i}}$ ${\displaystyle Y}$

Usando la notación , una relación difuncional también puede caracterizarse como una relación tal que dondequiera que y tengan una intersección no vacía, entonces estos dos conjuntos coinciden; formalmente implica ^[44] ${\displaystyle \{y\mid xRy\}=xR}$ ${\displaystyle R}$ ${\displaystyle x_{1}R}$ ${\displaystyle x_{2}R}$ ${\displaystyle x_{1}\cap x_{2}\neq \varnothing }$ ${\displaystyle x_{1}R=x_{2}R.}$

En 1997, los investigadores encontraron "la utilidad de la descomposición binaria basada en dependencias difuncionales en la gestión de bases de datos ". ^[45] Además, las relaciones difuncionales son fundamentales en el estudio de las bisimulaciones . ^[46]

En el contexto de relaciones homogéneas, una relación de equivalencia parcial es difuncional.

Tipo Ferrers

Un orden estricto en un conjunto es una relación homogénea que surge en la teoría del orden . En 1951, Jacques Riguet adoptó el ordenamiento de una partición entera , llamada diagrama de Ferrers , para extender el ordenamiento a las relaciones binarias en general. ^[47]

La matriz lógica correspondiente de una relación binaria general tiene filas que terminan con una secuencia de unos. Por lo tanto, los puntos de un diagrama de Ferrer se cambian por unos y se alinean a la derecha de la matriz.

Una declaración algebraica requerida para una relación de tipo Ferrers R es $${\displaystyle R{\bar {R}}^{\textsf {T}}R\subseteq R.}$$

Si alguna de las relaciones es del tipo Ferrers, entonces todas lo son. ^[48] ${\displaystyle R,{\bar {R}},R^{\textsf {T}}}$

Contacto

Supongamos que es el conjunto potencia de , el conjunto de todos los subconjuntos de . Entonces una relación es una relación de contacto si satisface tres propiedades: ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle g}$

1. ${\displaystyle {\text{for all }}x\in A,Y=\{x\}{\text{ implies }}xgY.}$
2. ${\displaystyle Y\subseteq Z{\text{ and }}xgY{\text{ implies }}xgZ.}$
3. ${\displaystyle {\text{for all }}y\in Y,ygZ{\text{ and }}xgY{\text{ implies }}xgZ.}$

La relación de pertenencia al conjunto , "es un elemento de", satisface estas propiedades, por lo que es una relación de contacto. El concepto de relación de contacto general fue introducido por Georg Aumann en 1970. ^{[49] [50]} ${\displaystyle \epsilon =}$ ${\displaystyle \epsilon }$

En términos del cálculo de relaciones, las condiciones suficientes para una relación de contacto incluyen donde es el inverso de la pertenencia al conjunto ( ). ^{[51] : 280} $${\displaystyle C^{\textsf {T}}{\bar {C}}\subseteq \ni {\bar {C}}\equiv C{\overline {\ni {\bar {C}}}}\subseteq C,}$$ ${\displaystyle \ni }$ ${\displaystyle \in }$

Reserva R\R

Toda relación genera un preorden que es el residuo izquierdo . ^[52] En términos de recíprocos y complementos, Al formar la diagonal de , la fila de y la columna correspondientes serán de valores lógicos opuestos, por lo que la diagonal es toda ceros. Entonces ${\displaystyle R}$ ${\displaystyle R\backslash R}$ ${\displaystyle R\backslash R\equiv {\overline {R^{\textsf {T}}{\bar {R}}}}.}$ ${\displaystyle R^{\textsf {T}}{\bar {R}}}$ ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle {\bar {R}}}$

${\displaystyle R^{\textsf {T}}{\bar {R}}\subseteq {\bar {I}}\implies I\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}=R\backslash R}$, por lo que se trata de una relación reflexiva . ${\displaystyle R\backslash R}$

Para demostrar la transitividad , se requiere que Recordemos que es la relación más grande tal que Entonces ${\displaystyle (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$ ${\displaystyle X=R\backslash R}$ ${\displaystyle RX\subseteq R.}$

${\displaystyle R(R\backslash R)\subseteq R}$

${\displaystyle R(R\backslash R)(R\backslash R)\subseteq R}$(repetir)

${\displaystyle \equiv R^{\textsf {T}}{\bar {R}}\subseteq {\overline {(R\backslash R)(R\backslash R)}}}$(Regla de Schröder)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}}$(complementación)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$(definición)

La relación de inclusión Ω en el conjunto potencia de se puede obtener de esta manera a partir de la relación de pertenencia en los subconjuntos de : ${\displaystyle U}$ ${\displaystyle \in }$ ${\displaystyle U}$

${\displaystyle \Omega ={\overline {\ni {\bar {\in }}}}=\in \backslash \in .}$^{[51] : 283}

Franja de una relación

Dada una relación , su franja es la subrelación definida como ${\displaystyle R}$ $${\displaystyle \operatorname {fringe} (R)=R\cap {\overline {R{\bar {R}}^{\textsf {T}}R}}.}$$

Cuando es una relación de identidad parcial, difuncional o diagonal en bloque, entonces . En caso contrario, el operador selecciona una subrelación de contorno descrita en términos de su matriz lógica: es la diagonal lateral si es un orden lineal triangular superior derecho o un orden estricto . es la franja en bloque si es irreflexiva ( ) o triangular superior derecho en bloque. es una secuencia de rectángulos de contorno cuando es de tipo Ferrers. ${\displaystyle R}$ ${\displaystyle \operatorname {fringe} (R)=R}$ ${\displaystyle \operatorname {fringe} }$ ${\displaystyle \operatorname {fringe} (R)}$ ${\displaystyle R}$ ${\displaystyle \operatorname {fringe} (R)}$ ${\displaystyle R}$ ${\displaystyle R\subseteq {\bar {I}}}$ ${\displaystyle \operatorname {fringe} (R)}$ ${\displaystyle R}$

Por otra parte, cuando se trata de un orden denso , lineal y estricto. ^[51] ${\displaystyle \operatorname {fringe} (R)=\emptyset }$ ${\displaystyle R}$

Montones de matemáticas

Dados dos conjuntos y , el conjunto de relaciones binarias entre ellos puede equiparse con una operación ternaria donde denota la relación inversa de . En 1953, Viktor Wagner utilizó propiedades de esta operación ternaria para definir semimontones , montículos y montículos generalizados. ^{[53] [54]} El contraste entre relaciones heterogéneas y homogéneas se destaca con estas definiciones: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {B}}(A,B)}$ ${\displaystyle [a,b,c]=ab^{\textsf {T}}c}$ ${\displaystyle b^{\mathsf {T}}}$ ${\displaystyle b}$

En la obra de Wagner hay una simetría agradable entre montones, semimontones y montones generalizados por un lado, y grupos, semigrupos y grupos generalizados por el otro. Esencialmente, los diversos tipos de semimontones aparecen siempre que consideramos relaciones binarias (y aplicaciones biunívocas parciales) entre diferentes conjuntos y , mientras que los diversos tipos de semigrupos aparecen en el caso en que . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A=B}$

—  Christopher Hollings, "Matemáticas al otro lado de la Cortina de Hierro: una historia de la teoría algebraica de semigrupos" ^[55]

Véase también

• Sistema de reescritura de resúmenes
• Relación aditiva , un homomorfismo de múltiples valores entre módulos
• Alegoría (teoría de categorías)
• Categoría de relaciones , una categoría que tiene conjuntos como objetos y relaciones binarias como morfismos
• Confluencia (reescritura de términos) analiza varias propiedades inusuales pero fundamentales de las relaciones binarias.
• Correspondencia (geometría algebraica) , una relación binaria definida por ecuaciones algebraicas
• Diagrama de Hasse , un medio gráfico para mostrar una relación de orden
• Estructura de incidencia , una relación heterogénea entre un conjunto de puntos y líneas.
• Lógica de relativos , una teoría de relaciones de Charles Sanders Peirce
• La teoría del orden investiga las propiedades de las relaciones de orden.

Notas

1. Los autores que tratan las relaciones binarias sólo como un caso especial de relaciones -arias para arbitrarios suelen escribir como un caso especial de ( notación de prefijo ). ^[8] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle Rxy}$ ${\displaystyle Rx_{1}\dots x_{n}}$

Referencias

1. Meyer, Albert (17 de noviembre de 2021). "MIT 6.042J Math for Computer Science, Lecture 3T, Slide 2" (PDF) . Archivado (PDF) del original el 17 de noviembre de 2021.
2. Codd, Edgar Frank (junio de 1970). "Un modelo relacional de datos para grandes bancos de datos compartidos" (PDF) . Comunicaciones de la ACM . 13 (6): 377–387. doi :10.1145/362384.362685. S2CID  207549016. Archivado (PDF) desde el original el 8 de septiembre de 2004 . Consultado el 29 de abril de 2020 .
3. "Definición de relación – Math Insight". mathinsight.org . Consultado el 11 de diciembre de 2019 .
4. Ernst Schröder (1895) Álgebra und Logic der Relative, vía Internet Archive
5. CI Lewis (1918) A Survey of Symbolic Logic, páginas 269-279, vía Internet Archive
6. Gunther Schmidt , 2010. Matemáticas relacionales . Cambridge University Press, ISBN 978-0-521-76268-7 , cap. 5 
7. Enderton 1977, cap. 3, pág. 40
8. Hans Hermes (1973). Introducción a la lógica matemática . Hochschultext (Springer-Verlag). Londres: Springer. ISBN 3540058192. ISSN  1431-4657.Sección II.§1.1.4
9. Suppes, Patrick (1972) [publicado originalmente por D. van Nostrand Company en 1960]. Teoría de conjuntos axiomáticos . Dover. ISBN 0-486-61630-4.
10. Smullyan, Raymond M. ; Fitting, Melvin (2010) [reedición revisada y corregida de la obra publicada originalmente en 1996 por Oxford University Press, Nueva York]. Teoría de conjuntos y el problema del continuo . Dover. ISBN 978-0-486-47484-7.
11. Levy, Azriel (2002) [reedición de la obra publicada por Springer-Verlag, Berlín, Heidelberg y Nueva York en 1979]. Teoría básica de conjuntos . Dover. ISBN 0-486-42079-5.
12. Schmidt, Gunther ; Ströhlein, Thomas (2012). Relaciones y gráficos: matemáticas discretas para científicos informáticos. Springer Science & Business Media. Definición 4.1.1. ISBN 978-3-642-77968-8.
13. Christodoulos A. Floudas ; Panos M. Pardalos (2008). Enciclopedia de optimización (2ª ed.). Medios de ciencia y negocios de Springer. págs. 299–300. ISBN 978-0-387-74758-3.
14. Michael Winter (2007). Categorías de Goguen: un enfoque categórico de las relaciones L-difusas . Springer. pp. x–xi. ISBN 978-1-4020-6164-6.
15. G. Schmidt, Claudia Haltensperger y Michael Winter (1997) "Álgebra de relaciones heterogéneas", capítulo 3 (páginas 37 a 53) en Métodos relacionales en ciencias de la computación , Avances en ciencias de la computación, Springer books ISBN 3-211-82971-7 
16. Jacobson, Nathan (2009), Álgebra básica II (2.ª ed.) § 2.1.
17. Garrett Birkhoff y Thomas Bartee (1970) Álgebra aplicada moderna , página 35, McGraw-Hill
18. Mary P. Dolciani (1962) Álgebra moderna: estructura y método , libro 2, página 339, Houghton Mifflin
19. John C. Baez (6 de noviembre de 2001). "Mecánica cuántica sobre un sistema conmutativo". Grupo de noticias : sci.physics.research. Usenet:  [email protected] . Consultado el 25 de noviembre de 2018 .
20. Droste, M. y Kuich, W. (2009). Semirings and Formal Power Series. Handbook of Weighted Automata , 3–28. doi :10.1007/978-3-642-01492-5_1, págs. 7-10
21. Simultaneidad relativa en Wikilibros
22. Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986). Teoría del diseño . Cambridge University Press . pág. 15.. 2da ed. (1999) ISBN 978-0-521-44432-3 
23. Van Gasteren 1990, pag. 45.
24. Kilp, Knauer, Mikhalev 2000, pág. 3.
25. "Relación funcional - Enciclopedia de Matemáticas". encyclopediaofmath.org . Consultado el 13 de junio de 2024 .
26. "Relación funcional en nLab". ncatlab.org . Consultado el 13 de junio de 2024 .
27. Schmidt 2010, pág. 49.
28. Kilp, Knauer, Mikhalev 2000, pág. 4.
29. Yao, YY; Wong, SKM (1995). "Generalización de conjuntos aproximados utilizando relaciones entre valores de atributos" (PDF) . Actas de la 2.ª Conferencia conjunta anual sobre ciencias de la información : 30–33..
30. Kunen, Kenneth (1980). Teoría de conjuntos: una introducción a las pruebas de independencia . Holanda Septentrional. p. 102. ISBN 0-444-85401-0.Zbl 0443.03021  .
31. Tarski, Alfred ; Givant, Steven (1987). Una formalización de la teoría de conjuntos sin variables. American Mathematical Society. p. 3. ISBN 0-8218-1041-3.
32. ME Müller (2012). Descubrimiento del conocimiento relacional . Cambridge University Press. pág. 22. ISBN 978-0-521-19021-3.
33. Peter J. Pahl; Rudolf Damrath (2001). Fundamentos matemáticos de la ingeniería computacional: un manual . Springer Science & Business Media. pág. 496. ISBN 978-3-540-67995-0.
34. Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), Una transición a las matemáticas avanzadas (6.ª ed.), Brooks/Cole, pág. 160, ISBN 0-534-39900-2
35. Nievergelt, Yves (2002), Fundamentos de lógica y matemáticas: aplicaciones a la informática y la criptografía , Springer-Verlag, pág. 158.
36. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Cierres transitivos de relaciones binarias I (PDF) . Praga: Facultad de Matemáticas – Física de la Universidad Charles. p. 1. Archivado desde el original (PDF) el 2 de noviembre de 2013.Lema 1.1 (iv). Esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
37. Joseph G. Rosenstein, Ordenamientos lineales , Academic Press, 1982, ISBN 0-12-597680-1 , pág. 4 
38. R. Berghammer y M. Winter (2013) "Descomposición de relaciones en redes de conceptos", Fundamenta Informaticae 126(1): 37–82 doi :10.3233/FI-2013-871
39. Ki-Hang Kim (1982) Teoría de matrices booleanas y aplicaciones , página 37, Marcel Dekker ISBN 0-8247-1788-0 
40. Ali Jaoua, Rehab Duwairi, Samir Elloumi y Sadok Ben Yahia (2009) "Minería de datos, razonamiento y recuperación incremental de información a través de una cobertura de relaciones rectangulares no ampliables", páginas 199 a 210 en Relaciones y álgebras de Kleene en informática , Lecture Notes in Computer Science 5827, Springer MR 2781235
41. Riguet, Jacques (enero de 1950). "Quelques proprietes des Relations difonctionelles". Comptes rendus (en francés). 230 : 1999-2000.
42. Julius Richard Büchi (1989). Autómatas finitos, sus álgebras y gramáticas: hacia una teoría de expresiones formales . Springer Science & Business Media. pp. 35–37. ISBN 978-1-4613-8853-1.
43. East, James; Vernitski, Alexei (febrero de 2018). "Rangos de ideales en semigrupos inversos de relaciones binarias difuncionales". Semigroup Forum . 96 (1): 21–30. arXiv : 1612.04935 . doi :10.1007/s00233-017-9846-9. S2CID  54527913.
44. Chris Brink; Wolfram Kahl; Günther Schmidt (1997). Métodos relacionales en informática . Medios de ciencia y negocios de Springer. pag. 200.ISBN​ 978-3-211-82971-4.
45. Ali Jaoua, Nadin Belkhiter, Habib Ounalli y Theodore Moukam (1997) "Bases de datos", páginas 197-210 en Métodos relacionales en ciencias de la computación , editado por Chris Brink, Wolfram Kahl y Gunther Schmidt , Springer Science & Business Media ISBN 978-3-211-82971-4 
46. Gumm, HP; Zarrad, M. (2014). "Simulaciones coalgebraicas y congruencias". Métodos coalgebraicos en informática . Apuntes de clase en informática . Vol. 8446. pág. 118. doi :10.1007/978-3-662-44124-4_7. ISBN 978-3-662-44123-7.
47. J. Riguet (1951) "Les Relations de Ferrers", Comptes Rendus 232: 1729,30
48. Schmidt, Gunther ; Ströhlein, Thomas (2012). Relaciones y gráficos: matemáticas discretas para científicos informáticos. Springer Science & Business Media. pág. 77. ISBN 978-3-642-77968-8.
49. Georg Aumann (1971). "Relaciones de contacto". Sitzungsberichte der mathematisch-physikalischen Klasse der Bayerischen Akademie der Wissenschaften München . 1970 (II): 67–77.
50. Revisión de Anne K. Steiner (1970): Kontakt-Relationen de Mathematical Reviews
51. Gunther Schmidt (2011) Matemáticas relacionales , páginas 211−15, Cambridge University Press ISBN 978-0-521-76268-7 
52. En este contexto, el símbolo no significa " diferencia de conjunto ". ${\displaystyle \backslash }$
53. Viktor Wagner (1953) "La teoría de los montones generalizados y los grupos generalizados", Matematicheskii Sbornik 32(74): 545 a 632 MR 0059267
54. CD Hollings y MV Lawson (2017) Teoría de los montones generalizados de Wagner , Springer books ISBN 978-3-319-63620-7 MR 3729305 
55. Christopher Hollings (2014) Matemáticas al otro lado de la Cortina de Hierro: una historia de la teoría algebraica de semigrupos , página 265, Historia de las Matemáticas 41, American Mathematical Society ISBN 978-1-4704-1493-1 

Bibliografía

• Schmidt, Gunther (2010). Matemáticas relacionales . Berlín: Cambridge University Press. ISBN 9780511778810.
• Schmidt, Gunther ; Ströhlein, Thomas (2012). "Capítulo 3: Relaciones heterogéneas". Relaciones y gráficos: matemáticas discretas para científicos informáticos . Springer Science & Business Media. ISBN 978-3-642-77968-8.
• Ernst Schröder (1895) Algebra der Logik, Banda III, vía Internet Archive
• Codd, Edgar Frank (1990). El modelo relacional para la gestión de bases de datos: versión 2 (PDF) . Boston: Addison-Wesley . ISBN. 978-0201141924. Archivado (PDF) del original el 9 de octubre de 2022.
• Enderton, Herbert (1977). Elementos de la teoría de conjuntos . Boston: Academic Press . ISBN. 978-0-12-238440-0.
• Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander (2000). Monoides, actos y categorías: con aplicaciones a productos de corona y gráficos . Berlín: De Gruyter . ISBN 978-3-11-015248-7.
• Van Gasteren, Antonetta (1990). Sobre la forma de los argumentos matemáticos . Berlín: Springer. ISBN 9783540528494.
• Peirce, Charles Sanders (1873). "Descripción de una notación para la lógica de relativos, resultante de una ampliación de las concepciones del cálculo lógico de Boole". Memorias de la Academia Estadounidense de Artes y Ciencias . 9 (2): 317–178. Bibcode :1873MAAAS...9..317P. doi :10.2307/25058006. hdl : 2027/hvd.32044019561034 . JSTOR  25058006 . Consultado el 5 de mayo de 2020 .
• Schmidt, Gunther (2010). Matemáticas relacionales. Cambridge: Cambridge University Press . ISBN 978-0-521-76268-7.

Enlaces externos

• "Relación binaria", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]