Relaciones binarias | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de la fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Todas las definiciones requieren tácitamente transitividad y reflexividad . |
En matemáticas , una relación binaria sobre los conjuntos X e Y es un subconjunto del producto cartesiano X × Y ; es decir, que es un conjunto de pares ordenados ( x , Y ) que consisten de elementos de x en X y Y en Y . [1] Codifica el concepto común de relación: un elemento x está relacionado con un elemento y , si y solo si el par (x , y ) pertenece al conjunto de pares ordenados que define la relación binaria . Una relación binaria es el caso especial más estudiado n = 2 de una relación n -aria sobre conjuntos X 1 , ..., X n , que es un subconjunto del producto cartesiano X 1 × ... × X n . [1] [2]
Un ejemplo de una relación binaria es la relación " divide " sobre el conjunto de números primos y el conjunto de enteros , en el que cada primo p está relacionado con cada entero z que es un múltiplo de p , pero no con un entero que no es un múltiplo de p . En esta relación, por ejemplo, el número primo 2 está relacionado con números como -4, 0, 6, 10, pero no con 1 o 9, al igual que el número primo 3 está relacionado con 0, 6 y 9, pero no a 4 o 13.
Las relaciones binarias se utilizan en muchas ramas de las matemáticas para modelar una amplia variedad de conceptos. Estos incluyen, entre otros:
- el " es mayor que ", " es igual a " y "divide" las relaciones 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 un tipo especial de relación binaria. [3] Las relaciones binarias también se utilizan mucho en informática .
Una relación binaria sobre conjuntos X y Y es un elemento del conjunto potencia de X × Y . Dado que el último conjunto se ordena por inclusión (⊆), cada relación tiene un lugar en el enrejado de subconjuntos de X × Y . Una relación binaria es una relación homogénea o una relación heterogénea dependiendo de si X = Y o no.
Dado que las relaciones son conjuntos, pueden manipularse utilizando operaciones de conjuntos, incluidas la unión , la intersección y la complementación , y satisfaciendo las leyes de un álgebra de conjuntos . Más allá de eso, se encuentran disponibles operaciones como el recíproco de una relación y la composición de relaciones , satisfaciendo las leyes de un cálculo de relaciones , para lo 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 entramado 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 para, entre otras cosas, modelar los conceptos de "es un elemento de" o "es un subconjunto de" en la teoría de conjuntos, sin encontrar inconsistencias lógicas como la paradoja de Russell .
Los términos correspondencia , [7] 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 X × Y sin referencia a X e Y , y se reservan el término "correspondencia" para una relación binaria con referencia a X y y . [ cita requerida ]
Definición
Dados los conjuntos X e Y , el producto cartesiano X × Y se define como {( x , y ) | x ∈ X e y ∈ Y } , y sus elementos se denominan pares ordenados.
Una relación binaria R sobre conjuntos X y Y es un subconjunto de X × Y . [1] [8] El conjunto X se llama el dominio [1] o conjunto de salida de R , y el conjunto Y la codomain o conjunto de destino de R . Para especificar las opciones de los conjuntos X e Y , algunos autores definen una relación o correspondencia binaria como un triple ordenado ( X , Y , G ) , donde G es un subconjunto de X × Y llamado gráfico de la relación binaria. El enunciado ( x , y ) ads R dice " x está R -relacionado con y " y se denota por xRy . [4] [5] [6] [nota 1] El dominio de definición o dominio activo [1] de R es el conjunto de todo x tal que xRy para al menos una y . El codominio de definición , codominio activo , [1] imagen o rango de R es el conjunto de todo y tal que xRy para al menos una x . El campo de R es la unión de su dominio de definición y su codominio de definición. [10] [11] [12]
Cuando X = Y , una relación binaria se llama relación homogénea (o endorrelación ). De lo contrario, es una relación heterogénea . [13] [14] [15]
En una relación binaria, el orden de los elementos es importante; si x ≠ y entonces yRx puede ser verdadero o falso independientemente de xRy . Por ejemplo, 3 divide a 9, pero 9 no divide a 3.
Ejemplos de
A B ′ | bola | carro | muñeca | taza |
---|---|---|---|---|
John | + | - | - | - |
María | - | - | + | - |
Venus | - | + | - | - |
A B | bola | carro | muñeca | taza |
---|---|---|---|---|
John | + | - | - | - |
María | - | - | + | - |
Ian | - | - | - | - |
Venus | - | + | - | - |
1) El siguiente ejemplo muestra que la elección del codominio es importante. Suponga que hay cuatro objetos A = {pelota, coche, muñeca, taza} y cuatro personas B = {John, Mary, Ian, Venus} . Una posible relación entre A y B es la relación "es propiedad de", dada por R = {(pelota, Juan), (muñeca, María), (automóvil, Venus)} . 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, R no involucra a Ian y, por lo tanto, R podría haber sido visto como un subconjunto de A × {John, Mary, Venus} , es decir, una relación sobre A y {John, Mary, Venus}, ver el segundo ejemplo. Mientras que la segunda relación de ejemplo es sobreyectiva (ver más abajo ), la primera no lo es.
N / A | SA | AF | UE | COMO | jefe | Automóvil club británico | |
---|---|---|---|---|---|---|---|
indio | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
Ártico | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
atlántico | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
Pacífico | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
2) Sea A = {Índico, Ártico, Atlántico, Pacífico}, los océanos del globo y B = {NA, SA, AF, UE, AS, OC, AA}, los continentes . Deje aRb representan ese océano un fronteras continente b . Entonces la matriz lógica para esta relación es:
La conectividad del planeta Tierra se puede ver a través de RR T y R T R , siendo la primera una relación 4 × 4 sobre A , que es la relación universal ( A × A o una matriz lógica de todas unas). Esta relación universal refleja el hecho de que cada océano está separado de los demás como máximo por un continente. Por otro lado, R T R es una relación en B × B que no llega a ser universal porque se deben atravesar al menos dos océanos para viajar de Europa a Oceanía .
3) La visualización de 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 relaciones heterogéneas, un hipergráfico tiene bordes posiblemente con más de dos nodos, y puede ilustrarse mediante un gráfico bipartito .
Así como la camarilla es parte integral de las relaciones de un conjunto, los biciciclos se utilizan para describir relaciones heterogéneas; de hecho, son los "conceptos" que generan un entramado asociado a una relación.
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 t determina un hiperplano simultáneo en esa cosmología. Herman 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. Usó un producto interno indefinido y especificó que un vector de tiempo es normal a un vector espacial cuando ese producto es cero. El producto interno indefinido en un álgebra de composición está dado por
- donde la barra superior denota conjugación.
Como relación entre algunos eventos temporales y algunos eventos espaciales, la ortogonalidad hiperbólica (como se encuentra en números complejos divididos ) es una relación heterogénea. [dieciséis]
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 Steiner S ( t, k, n ) que tienen un conjunto de n elementos S y un conjunto de subconjuntos de k elementos llamados bloques , de modo que un subconjunto con t 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.
- Una estructura de incidencia es un triple D = ( V , B , I ) en la que V y B son dos conjuntos disjuntos y I es una relación binaria entre V y B , es decir, I ⊆ V × B . Los elementos de V serán llamados puntos , los de B bloques y los de I banderas . [17]
Tipos especiales de relaciones binarias
Algunos tipos importantes de relaciones binarias R sobre los conjuntos X e Y se enumeran a continuación.
- Como un set[ cita requerida ] (o local )
- para todo x ∈ X , la clase de todo y tal que yRx es un conjunto. (Esto tiene sentido sólo si se permiten relaciones sobre clases adecuadas). Por ejemplo, el orden habitual
números ordinales es una relación de tipo conjunto, mientras que su inversa> no lo es.
Propiedades de singularidad:
- Inyectivo (también llamado único por la izquierda ): [18] para todo x , z ∈ X y todo y ∈ Y , si xRy y zRy entonces x = z . Para una relación tal, { Y } se llama una clave primaria de R . [1] Por ejemplo, las relaciones binarias verde y azul en el diagrama son inyectivas, pero la roja no lo es (ya que relaciona −1 y 1 a 1), ni la negra (ya que relaciona −1 y 1 a 0).
- Funcional (también llamado único por la derecha , [18] definido por la derecha [19] o univalente ): [6] para todo x ∈ X y todo y , z ∈ Y , si xRy y xRz entonces y = z . Esta relación binaria se llama función parcial . Para una relación tal, { X } se llama una clave primaria de R . [1] Por ejemplo, las relaciones binarias rojo y verde en el diagrama son funcionales, pero la azul no lo es (ya que relaciona 1 con −1 y 1), ni la negra (ya que se relaciona 0 con −1 y 1).
- Uno a uno : inyectivo y funcional. Por ejemplo, la relación binaria verde en el diagrama es uno a uno, pero las rojas, azules y negras no lo son.
- Uno a muchos : inyectivo y no funcional. Por ejemplo, la relación binaria azul en el diagrama es de uno a muchos, pero las rojas, verdes y negras no lo son.
- Muchos a uno : funcional y no inyectable. 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 inyectable ni funcional. Por ejemplo, la relación binaria negra en el diagrama es de muchos a muchos, pero las rojas, verdes y azules no lo son.
Propiedades de totalidad (solo definibles si se especifican el dominio X y el codominio Y ):
- Serial (también llamado left-total ): [18] para todo x en X existe una y en Y tal que xRy . En otras palabras, el dominio de la definición de R es igual a X . Esta propiedad, aunque algunos autores también la denominan total , [ cita requerida ] es diferente de la definición de conectado (también llamado total por algunos autores) [ cita requerida ] en Propiedades . Esta relación binaria se denomina función multivalor . Por ejemplo, las relaciones binarias roja y verde en el diagrama son seriales, pero la azul no lo es (ya que no se relaciona −1 con ningún número real), ni la negra (ya que no se relaciona 2 con ningún número real). ). Como otro ejemplo,> es una relación serial sobre los enteros. Pero no es una relación serial sobre los enteros positivos, porque no hay y en los enteros positivos tal que 1> y . [20] Sin embargo,
Toda relación reflexiva es serial: para una x dada , elija y = x . - Sobreyectiva (también llamada derecha-total [18] o sobre ): para todo y en Y , existe una x en X tal que xRy . En otras palabras, la codomain de definición de R es igual a Y . 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 -1), ni la negra (ya que no relaciona ningún número real con 2 ).
Propiedades de unicidad y totalidad (solo definibles si se especifican el dominio X y el codominio Y ):
- Una función : una relación binaria que es funcional y serial. 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 inyectiva. Por ejemplo, la relación binaria verde en el diagrama es una inyección, pero las rojas, azules y negras no lo son.
- Una sobreyección : una función que es sobreyectiva. Por ejemplo, la relación binaria verde en el diagrama es una sobreyección, pero las rojas, azules y negras no lo son.
- Una biyección : una función inyectiva y sobreyectiva. Por ejemplo, la relación binaria verde en el diagrama es una biyección, pero las rojas, azules y negras no lo son.
Operaciones sobre relaciones binarias
Unión
Si R y S son relaciones binarias sobre los conjuntos X e Y, entonces R ∪ S = {( x , y ) | xRy o XSY } es la relación unión de R y S sobre X y Y .
El elemento de identidad es la relación vacía. Por ejemplo, ≤ es la unión de
Intersección
Si R y S son relaciones binarias sobre los conjuntos X e Y, entonces R ∩ S = {( x , y ) | xRy y XSY } es la relación de intersección de R y S sobre X y 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 R es una relación binaria sobre los conjuntos X e Y , y S es una relación binaria sobre los conjuntos Y y Z, entonces S ∘ R = {( x , z ) | existe y ∈ Y tal que xRy y YSZ } (también denotada por R ; S ) es la relación composición de R y S sobre X y Z .
El elemento de identidad es la relación de identidad. El orden de R y S en la notación S ∘ R , que se utiliza aquí, concuerda con el orden de notación estándar para la composición de funciones . Por ejemplo, la composición "es madre de" ∘ "es padre de" rendimiento "es abuelo materno de", mientras que la composición "es padre de" ∘ "es madre de" rendimiento "es abuela de". Para el primer caso, si x es el padre de y e y es la madre de z , entonces x es el abuelo materno de z .
Conversar
Si R es una relación binaria sobre los conjuntos X e Y, entonces R T = {( y , x ) | xRy } es la relación inversa de R sobre Y y X .
Por ejemplo, = es el inverso de sí mismo, al igual que ≠, y
Complemento
Si R es una relación binaria sobre los conjuntos X e Y, entonces R = {( x , y ) | no xRy } (también denotada por R o ¬ R ) es la relación complementaria de R sobre X y Y .
Por ejemplo, = y ≠ son complementarios entre sí, al igual que ⊆ y ⊈, ⊇ y ⊉, y ∈ y ∉, y, para órdenes totales , también
El complemento de la relación inversa R T es el inverso del complemento:
Si X = Y , el complemento tiene las siguientes propiedades:
- Si una relación es simétrica, también lo es el complemento.
- El complemento de una relación reflexiva es irreflexivo y viceversa.
- El complemento de una orden estrictamente débil es una preorden total, y viceversa.
Restricción
Si R es una relación binaria homogénea sobre un conjunto X y S es un subconjunto de X, entonces R | S = {( x , y ) | xRy y x ∈ S e y ∈ S } es elrelación de restricción deRaSsobreX.
Si R es una relación binaria sobre los conjuntos X e Y y si S es un subconjunto de X, entonces R | S = {( x , y ) | xRy y x ∈ S } es elrelación de restricción de la izquierda deRaSmás deXyY.
Si R es una relación binaria sobre los conjuntos X e Y y si S es un subconjunto de Y, entonces R | S = {( x , y ) | xRy y y ∈ S } es elrelación de restricción de la derecha deRaSmás deXyY.
Si una relación es reflexiva , irreflexive, simétrica , antisimétrica , asimétrica , transitiva , total de , tricotómica , un orden parcial , orden total , estricto orden débil , preorden total de (orden débil), o un relación de equivalencia , entonces también lo son sus restricciones.
Sin embargo, el cierre transitivo de una restricción es un subconjunto de la restricción del cierre transitivo, es decir, en general no es igual. Por ejemplo, al restringir la relación " x es madre de y " a las mujeres, se obtiene la relación " x es madre de la mujer y "; su cierre transitivo no relaciona a una mujer con su abuela paterna. Por otro lado, la clausura transitiva de "es padre de" es "es antepasado de"; su restricción a las mujeres relaciona a una mujer con su abuela paterna.
Además, los diversos conceptos de completitud (que no debe confundirse con ser "total") no se transfieren a las restricciones. Por ejemplo, en los números reales de una propiedad de la relación ≤ es que cada no vacío subconjunto S de R con un límite superior en R tiene un extremo superior (también llamado supremo) en R . Sin embargo, para los números racionales este supremo no es necesariamente racional, por lo que la misma propiedad no se aplica a la restricción de la relación ≤ a los números racionales.
Una relación binaria R sobre conjuntos X e Y se dice que es {{em | contenido en una relación S sobre X e Y , escritosi R es un subconjunto de S , es decir, para todos y si xRy , entonces xSy . Si R está contenido en S y S está contenido en R , entonces R y S se llaman igual escrito R = S . Si R está contenido en S pero S no está contenido en R , entonces se dice que R esmás pequeña queS, escrito R ⊊ S . Por ejemplo, en losnúmeros racionales, la relación> es menor que ≥, e igual a la composición> ∘>.
Representación matricial
Las relaciones binarias sobre los conjuntos X e Y se pueden representar algebraicamente mediante matrices lógicas indexadas por X e Y con entradas en el semirrígido booleano (la suma corresponde a OR y la multiplicación a AND) donde la suma 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 X e Y y una relación sobre Y y Z ), [21] 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 X = Y ) forman una matriz semiring (de hecho, una matriz semialgebra sobre la semiring booleana) donde la matriz identidad corresponde a la relación identidad. [22]
Conjuntos versus clases
Ciertas "relaciones" matemáticas, como "igual a", "subconjunto de" y "miembro de", no pueden entenderse como relaciones binarias como se definen anteriormente, porque sus dominios y codominios no pueden tomarse como conjuntos en los sistemas habituales. de la teoría axiomática de conjuntos . Por ejemplo, si intentamos modelar el concepto general de "igualdad" como una relación binaria =, debemos tomar el dominio y el codominio como la "clase de todos los conjuntos", que no es un conjunto en la teoría de conjuntos habitual.
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 A "suficientemente grande" , que contenga todos los objetos de interés, y trabajar con la restricción = A en lugar de =. Del mismo modo, el "subconjunto de las" necesidades de relación ⊆ estar restringida a tener dominio y codomain P ( A ) (el conjunto potencia de un conjunto específico A ): la relación conjunto resultante puede ser denotado por ⊆ A . Además, la relación "miembro de" debe restringirse para tener dominio A y codominio P ( A ) para obtener una relación binaria ∈ A que sea un conjunto. Bertrand Russell ha demostrado que suponer que be se define sobre todos los conjuntos conduce a una contradicción en la teoría de conjuntos ingenua.
Otra solución a este problema es utilizar una teoría de conjuntos con clases adecuadas, como NBG o teoría de conjuntos de Morse-Kelley , y permitir que el dominio y el codominio (y por tanto el gráfico) sean clases adecuadas : en tal teoría, igualdad, pertenencia , y subconjunto son relaciones binarias sin comentarios especiales. (Es necesario hacer una modificación menor al concepto de triple ordenado ( X , Y , G ) , ya que normalmente una clase adecuada no puede ser miembro de una tupla ordenada; o, por supuesto, se puede identificar la relación binaria con su gráfico en este contexto.) [23] Con esta definición se puede, por ejemplo, definir una relación binaria sobre cada conjunto y su conjunto de potencias.
Relación homogénea
Una relación homogénea sobre un conjunto X es una relación binaria sobre X y ella misma, es decir, es un subconjunto del producto cartesiano X × X . [15] [24] [25] es también llamado simplemente una relación (binario) sobre X .
Una relación homogénea R sobre un conjunto X puede identificarse con un gráfico simple dirigido que permite bucles , donde X es el conjunto de vértices y R es el conjunto de aristas (hay una arista desde un vértice x a un vértice y si y solo si xRy ) . El conjunto de todas las relaciones homogéneas.sobre un conjunto X está el conjunto 2 X × X que es un álgebra booleana aumentada con la involución del mapeo de una relación con su relación inversa . Considerando la composición de relaciones como una operación binaria en, forma un semigrupo con involución .
Algunas propiedades importantes que puede tener una relación homogénea R sobre un conjunto X son:
- Reflexivo : para todo x ∈ X , xRx . Por ejemplo, ≥ es una relación reflexiva pero> no lo es.
- Irreflexivo : para todo x ∈ X , no xRx . Por ejemplo,> es una relación irreflexiva, pero ≥ no lo es.
- Simétrico : para todo x , y ∈ X , si xRy entonces yRx . Por ejemplo, "es un pariente consanguíneo de" es una relación simétrica.
- Antisimétrico : para todo x , y ∈ X , si xRy y yRx entonces x = y . Por ejemplo, ≥ es una relación antisimétrica. [26]
- Asimétrico : para todo x , y ∈ X , si xRy entonces no yRx . Una relación es asimétrica si y solo si es a la vez antisimétrica e irreflexiva. [27] Por ejemplo,> es una relación asimétrica, pero ≥ no lo es.
- Transitive : para todos x , y , z ∈ X , si xRy y yRz entonces xRz . Una relación transitiva es irreflexiva si y solo si es asimétrica. [28] Por ejemplo, "es antepasado de" es una relación transitiva, mientras que "es padre de" no lo es.
- Conectado : para todo x , y ∈ X , si x ≠ y entonces xRy o yRx .
- Fuertemente conectado : para todo x , y ∈ X , xRy o yRx .
Un orden parcial es una relación reflexiva, antisimétrica y transitiva. Un orden parcial estricto es una relación irreflexiva, antisimétrica y transitiva. Un orden total es una relación reflexiva, antisimétrica, transitiva y conectada. [29] Un orden total estricto es una relación que es irreflexiva, antisimétrica, transitiva y conectada. Una relación de equivalencia es una relación reflexiva, simétrica y transitiva. Por ejemplo, " x divide y " es un orden parcial, pero no total en ℕ , " x < y " es un orden total estricto en ℕ, y " x es paralelo ay " es una relación de equivalencia en el conjunto de todos líneas en el plano euclidiano .
Todas las operaciones definidas en la sección Operaciones sobre relaciones binarias también se aplican a relaciones homogéneas. Más allá de eso, una relación homogénea sobre un conjunto X puede estar sujeta a operaciones de cierre como:
- Cierre reflexivo : la relación reflexiva (única) sobre X que contiene R ,
- Cierre transitivo : la relación transitiva más pequeña sobre X que contiene R ,
- Cierre de equivalencia : la más pequeña relación de equivalencia sobre X que contiene R .
Relación heterogénea
En matemáticas , una relación heterogénea es una relación binaria , un subconjunto de un producto cartesiano A × B , donde A y B son conjuntos distintos. [30] El prefijo hetero es del griego ἕτερος ( heteros , "otro, otro, diferente").
Una relación heterogénea se ha llamado una relación rectangular , [31] lo que sugiere que no tiene la plaza-simetría de una relación homogénea en un conjunto donde A = B . Al comentar sobre el desarrollo de las relaciones binarias más allá de las relaciones homogéneas, los investigadores escribieron: "... ha evolucionado una variante de la teoría que trata las relaciones desde el principio como heterogéneas o rectangulares , es decir, como relaciones donde el caso normal es que sean relaciones entre diferentes conjuntos ". [32]
Cálculo de relaciones
Los desarrollos en lógica algebraica han facilitado el uso de relaciones binarias. El cálculo de relaciones incluye el álgebra de conjuntos , ampliado por la composición de relaciones y el uso de relaciones recíprocas . La inclusión R ⊆ S , que significa que aRb implica aSb , establece el escenario en un entramado de relaciones. Pero desdeel símbolo de inclusión es superfluo. Sin embargo, la composición de las relaciones y la manipulación de los operadores de acuerdo con reglas Schröder , proporciona un cálculo para el trabajo en el conjunto potencia de A × B .
A diferencia de las relaciones homogéneas, la composición de la operación de relaciones es solo una función parcial . La necesidad de hacer coincidir el rango con el dominio de relaciones compuestas ha llevado a la sugerencia de que el estudio de relaciones heterogéneas es un capítulo de la teoría de categorías como en 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 ]
Celosía de concepto inducido
Las relaciones binarias se han descrito a través de sus redes de conceptos inducidos : Un concepto C ⊂ R satisface dos propiedades: (1) La matriz lógica de C es el producto externo de vectores lógicos
- vectores lógicos. [ aclaración necesaria ] (2) C es máxima, no está contenida en ningún otro producto exterior. Por tanto, C se describe como un rectángulo no ampliable.
Para una relación dada R ⊆ X × Y , el conjunto de conceptos, agrandados por sus uniones y encuentros, forma un "entramado inducido de conceptos", con inclusiónformando un pedido anticipado .
El teorema de compleción de MacNeille (1937) (que cualquier orden parcial puede estar incrustado en un retículo completo ) se cita en un artículo de encuesta de 2013 "Descomposición de relaciones en retículos de conceptos". [33] La descomposición es
- donde f y g son funciones , llamadas mapeos o relaciones univalentes de total izquierdo en este contexto. El "concepto de celosía inducida es isomorfo a la terminación del corte del orden parcial E que pertenece a la descomposición mínima ( f, g, E ) de la relación R ".
Los casos particulares se consideran a continuación: el orden total E corresponde al tipo Ferrers, y la identidad E corresponde a difuncional, una generalización de la relación de equivalencia en un conjunto.
Las relaciones pueden clasificarse según el rango de Schein, que cuenta el número de conceptos necesarios para cubrir una relación. [34] El análisis estructural de las relaciones con los conceptos proporciona un enfoque para la minería de datos . [35]
Relaciones particulares
- Proposición : si R es una relación serial y R T es su transpuesta, entonces dónde es la relación de identidad m × m .
- Proposición : si R es una relación sobreyectiva , entonces dónde es la relación de identidad n × n .
Difuncional
Entre las relaciones homogéneas de un conjunto, las relaciones de equivalencia se distinguen por su capacidad para dividir el conjunto. Con las relaciones binarias en general, la idea es dividir objetos distinguiendo atributos. Una forma de hacerlo es con un conjunto intermedio Z = { x, y, z , ...} de indicadores . La relación de partición R = FG T es una composición de relaciones utilizando univalentes relaciones F ⊆ A × Z y G ⊆ B × Z .
La matriz lógica de tal relación R se puede reorganizar como una matriz de bloques con bloques de unos a lo largo de la diagonal. En términos del cálculo de relaciones, en 1950 Jacques Riguet demostró que tales relaciones satisfacen la inclusión
- [36]
Llamó a estas relaciones difuncionales ya que la composición FG T involucra relaciones univalentes, comúnmente llamadas funciones .
Usando la notación { y : xRy } = xR , una relación difuncional también se puede caracterizar como una relación R tal que siempre que x 1 R y x 2 R tienen una intersección no vacía, estos dos conjuntos coinciden; formalmente x 1 R ∩ x 2 R ≠ ∅ implica x 1 R = x 2 R . [37]
En 1997, los investigadores encontraron "utilidad de la descomposición binaria basada en dependencias difuncionales en la gestión de bases de datos ". [38] Además, las relaciones difuncionales son fundamentales en el estudio de las bisimulaciones . [39]
En el contexto de relaciones homogéneas, una relación de equivalencia parcial es difuncional.
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 diagonal de bloques con bloques rectangulares de verdadero en la diagonal principal (asimétrica). [40]
Tipo de 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 orden de una partición de un número entero, llamado diagrama de Ferrers , para extender el orden a las relaciones binarias en general. [41]
La matriz lógica correspondiente de una relación binaria general tiene filas que terminan con una secuencia de unos. Así, los puntos de un diagrama de Ferrer se cambian a unos y se alinean a la derecha en la matriz.
Un enunciado algebraico requerido para una relación de tipo Ferrers R es
Si alguno de los parientes es del tipo Ferrers, entonces todos lo son. [30]
Contacto
Supongamos que B es el conjunto potencia de A , el conjunto de todos los subconjuntos de A . Entonces una relación g es una relación de contacto si satisface tres propiedades:
- ∀ x en A , Y = { x } implica xg Y .
- Y ⊆ Z y xg Y implica Z xg .
- ∀ y en Y , Z YG y xg Y implica Z xg .
La relación de pertenencia al conjunto , ε = "es un elemento de", satisface estas propiedades, por lo que ε es una relación de contacto. La noción de una relación de contacto general fue introducida por Georg Aumann en 1970. [42] [43]
En términos del cálculo de relaciones, las condiciones suficientes para una relación de contacto incluyen
- dónde es el inverso de la pertenencia al conjunto (∈). [44] : 280
Preordenar R \ R
Cada relación R genera un preorden R \ R que es el residuo izquierdo . [45] En términos de conversar y complementar, Formando la diagonal de , la fila correspondiente de R T y la columna deserá de valores lógicos opuestos, por lo que la diagonal es todo ceros. Luego
- de modo que R \ R es una relación reflexiva .
Para mostrar la transitividad , se requiere que ( R \ R ) ( R \ R ) ⊂ R \ R . Recordemos que X = R \ R es la mayor relación tal que RX ⊂ R . Luego
- (repetir)
- (Regla de Schröder)
- (complementación)
- (definición)
La relación de inclusión Ω en el conjunto de potencias de U se puede obtener de esta manera a partir de la relación de pertenencia ∈ en subconjuntos de U :
- [44] : 283
Fringe de una relación
Dada una relación R , una subrelación llamada su franja se define como
Cuando R es una relación parcial de identidad, difuncional, o una relación diagonal de bloques, a continuación, la franja ( R ) = R . De lo contrario, el operador de franjas selecciona una subrelación de límite descrita en términos de su matriz lógica: franja ( R ) es la diagonal lateral si R es un orden lineal triangular superior derecho o un orden estricto . Fringe ( R ) es la franja del bloque si R es irreflexivo () o bloque triangular superior derecho. Fringe ( R ) es una secuencia de rectángulos limítrofes cuando R es del tipo Ferrers.
Por otro lado, Fringe ( R ) = ∅ cuando R es un orden denso , lineal y estricto. [44]
Montones matemáticos
Dados dos conjuntos A y B , el conjunto de relaciones binarias entre ellospuede equiparse con una operación ternaria donde b T denota la relación inversa de b . En 1953, Viktor Wagner utilizó las propiedades de esta operación ternaria para definir semi-montones, montones y montones generalizados. [46] [47] El contraste de relaciones heterogéneas y homogéneas se destaca por estas definiciones:
Hay una agradable simetría en la obra de Wagner entre montones, semi montones y montones generalizados por un lado, y grupos, semigrupos y grupos generalizados por el otro. Esencialmente, los diversos tipos de semiheaps aparecen cuando consideramos relaciones binarias (y parciales uno-uno asignaciones) entre diferentes conjuntos A y B , mientras que los diversos tipos de semigroups aparecen en el caso en el que A = B .
- Christopher Hollings, "Matemáticas al otro lado del Telón de Acero: una historia de la teoría algebraica de semigrupos" [48]
Ver también
- Sistema de reescritura abstracta
- Relación aditiva , un homomorfismo multivaluado 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 los parientes , una teoría de las relaciones por Charles Sanders Peirce
- Teoría del orden , investiga las propiedades de las relaciones de orden.
Notas
- ^ Los autores que se ocupan de las relaciones binarias sólo como un caso especial derelaciones n -arias para n arbitrariossuelen escribir Rxy como un caso especial de Rx 1 ... x n ( notación de prefijo ). [9]
Referencias
- ↑ a b c d e f g h 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 . Consultado el 29 de abril de 2020 .
- ^ "El glosario definitivo de jerga matemática superior: relación" . Bóveda de matemáticas . 2019-08-01 . Consultado el 11 de diciembre de 2019 .
- ^ "Definición de relación - Perspectiva matemática" . mathinsight.org . Consultado el 11 de diciembre de 2019 .
- ↑ a b Ernst Schröder (1895) Algebra und Logic der Relative , vía Internet Archive
- ^ a b C. I. Lewis (1918) A Survey of Symbolic Logic , páginas 269 a 279, a través de Internet Archive
- ^ a b c Gunther Schmidt , 2010. Matemáticas relacionales . Prensa de la Universidad de Cambridge, ISBN 978-0-521-76268-7 , cap. 5
- ^ Jacobson, Nathan (2009), Álgebra básica II (2a ed.) § 2.1.
- ↑ Enderton 1977 , Ch 3. pág. 40
- ^ 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
- ^ Suppes, Patrick (1972) [publicado originalmente por D. van Nostrand Company en 1960]. Teoría de conjuntos axiomáticos . Dover. ISBN 0-486-61630-4.
- ^ Smullyan, Raymond M .; Fitting, Melvin (2010) [reedición revisada y corregida del trabajo publicado originalmente en 1996 por Oxford University Press, Nueva York]. Teoría de conjuntos y problema continuo . Dover. ISBN 978-0-486-47484-7.
- ^ 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.
- ^ Schmidt, Gunther ; Ströhlein, Thomas (2012). Relaciones y gráficos: matemáticas discretas para informáticos . Definición 4.1.1 .: Springer Science & Business Media. ISBN 978-3-642-77968-8.Mantenimiento de CS1: ubicación ( enlace )
- ^ Christodoulos A. Floudas ; Panos M. Pardalos (2008). Enciclopedia de optimización (2ª ed.). Springer Science & Business Media. págs. 299–300. ISBN 978-0-387-74758-3.
- ^ a b Michael Winter (2007). Categorías de Goguen: un enfoque categórico de las relaciones L-difusas . Saltador. págs. x – xi. ISBN 978-1-4020-6164-6.
- ^ Simultaneidad relativa en Wikilibros
- ^ Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986). Teoría del diseño . Prensa de la Universidad de Cambridge . pag. 15.. 2ª ed. (1999) ISBN 978-0-521-44432-3
- ↑ a b c d Kilp, Knauer y Mikhalev: pág. 3. Las mismas cuatro definiciones aparecen a continuación:
- Peter J. Pahl; Rudolf Damrath (2001). Fundamentos matemáticos de la ingeniería computacional: un manual . Springer Science & Business Media. pag. 506. ISBN 978-3-540-67995-0.
- Eike Best (1996). Semántica de programas secuenciales y paralelos . Prentice Hall. págs. 19-21. ISBN 978-0-13-460643-9.
- Robert-Christoph Riemann (1999). Modelado de sistemas concurrentes: métodos estructurales y semánticos en el cálculo de redes de Petri de alto nivel . Herbert Utz Verlag. págs. 21-22. ISBN 978-3-89675-629-9.
- ^ Mäs, Stephan (2007), "Reasoning on Spatial Semantic Integrity Constraints", Spatial Information Theory: 8th International Conference, COSIT 2007, Melbourne, Australia, 19-23 de septiembre de 2007, Proceedings , Lecture Notes in Computer Science, 4736 , Springer, págs. 285–302, doi : 10.1007 / 978-3-540-74788-8_18
- ^ Yao, YY; Wong, SKM (1995). "Generalización de conjuntos aproximados utilizando relaciones entre valores de atributo" (PDF) . Actas de la segunda conferencia conjunta anual sobre ciencias de la información : 30–33..
- ^ John C. Baez (6 de noviembre de 2001). "mecánica cuántica sobre una plataforma conmutativa" . Grupo de noticias : sci.physics.research . Usenet: [email protected] . Consultado el 25 de noviembre de 2018 .
- ^ Droste, M. y Kuich, W. (2009). Serie Semirings y Poder Formal. Manual de autómatas ponderados , 3–28. doi : 10.1007 / 978-3-642-01492-5_1 , págs. 7-10
- ^ Tarski, Alfred ; Givant, Steven (1987). Una formalización de la teoría de conjuntos sin variables . Sociedad Matemática Estadounidense. pag. 3 . ISBN 0-8218-1041-3.
- ^ ME Müller (2012). Descubrimiento del conocimiento relacional . Prensa de la Universidad de Cambridge. pag. 22. ISBN 978-0-521-19021-3.
- ^ Peter J. Pahl; Rudolf Damrath (2001). Fundamentos matemáticos de la ingeniería computacional: un manual . Springer Science & Business Media. pag. 496. ISBN 978-3-540-67995-0.
- ^ Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), A Transition to Advanced Mathematics (6a ed.), Brooks / Cole, p. 160, ISBN 0-534-39900-2
- ^ Nievergelt, Yves (2002), Fundamentos de la lógica y las matemáticas: aplicaciones a la informática y la criptografía , Springer-Verlag, p. 158.
- ^ Flaška, V .; Ježek, J .; Kepka, T .; Kortelainen, J. (2007). Cierres transitivos de relaciones binarias I (PDF) . Praga: Escuela de Matemáticas - Universidad Charles de Física. pag. 1. Archivado desde el original (PDF) en 2013-11-02.Lema 1.1 (iv). Esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
- ^ Joseph G. Rosenstein, Ordenaciones lineales , Academic Press, 1982, ISBN 0-12-597680-1 , pág. 4
- ^ a b Schmidt, Gunther ; Ströhlein, Thomas (2012). Relaciones y gráficos: matemáticas discretas para informáticos . Springer Science & Business Media. pag. 77. ISBN 978-3-642-77968-8.
- ^ Michael Winter (2007). Categorías de Goguen: un enfoque categórico de las relaciones L-difusas . Saltador. págs. x – xi. ISBN 978-1-4020-6164-6.
- ^ 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 informática , Avances en informática, libros SpringerISBN 3-211-82971-7
- ^ 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
- ^ Ki Hang Kim (1982) Teoría y aplicaciones de la matriz booleana , página 37, Marcel DekkerISBN 0-8247-1788-0
- ^ Ali Jaoua, Rehab Duwairi, Samir Elloumi y Sadok Ben Yahia (2009) "Minería de datos, razonamiento y recuperación de información incremental a través de la cobertura de relación rectangular no ampliable", páginas 199 a 210 en Relaciones y álgebras de Kleene en informática , Notas de la conferencia en Ciencias de la Computación 5827, Springer MR2781235
- ^ Jacques Riguet (1950) "Quelques proprietes des Relations difonctionelles", Comptes Rendus 230: 1999-2000
- ^ Chris Brink; Wolfram Kahl; Gunther Schmidt (1997). Métodos relacionales en informática . Springer Science & Business Media. pag. 200. ISBN 978-3-211-82971-4.
- ^ Ali Jaoua, Nadin Belkhiter, Habib Ounalli y Theodore Moukam (1997) "Bases de datos", páginas 197-210 en Métodos relacionales en informática , editado por Chris Brink, Wolfram Kahl y Gunther Schmidt , Springer Science & Business MediaISBN 978-3-211-82971-4
- ^ Gumm, HP; Zarrad, M. (2014). "Simulaciones y congruencias coalgebraicas". Métodos coalgebraicos en informática . Apuntes de conferencias en informática . 8446 . pag. 118. doi : 10.1007 / 978-3-662-44124-4_7 . ISBN 978-3-662-44123-7.
- ^ Julius Richard Büchi (1989). Autómatas finitos, sus álgebras y gramáticas: hacia una teoría de las expresiones formales . Springer Science & Business Media. págs. 35–37. ISBN 978-1-4613-8853-1.
- ^ J. Riguet (1951) "Las relaciones de Ferrers", Comptes Rendus 232: 1729,30
- ^ Georg Aumann (1971). "Kontakt-Relationen" . Sitzungsberichte der mathisch-physikalischen Klasse der Bayerischen Akademie der Wissenschaften München . 1970 (II): 67–77.
- ^ Revisión de Anne K. Steiner (1970) : Kontakt-Relationen de Mathematical Reviews
- ^ a b c Gunther Schmidt (2011) Matemáticas relacionales , páginas 211-15, Cambridge University PressISBN 978-0-521-76268-7
- ^ En este contexto, el símbolo ""no significa" establecer diferencia ".
- ^ Viktor Wagner (1953) "La teoría de montones generalizados y grupos generalizados", Matematicheskii Sbornik 32 (74): 545 a 632 MR0059267
- ^ CD Hollings y MV Lawson (2017) Teoría de montones generalizados de Wagner , libros de SpringerISBN 978-3-319-63620-7 SEÑOR3729305
- ^ Christopher Hollings (2014) Matemáticas a través del telón de acero: una historia de la teoría algebraica de semigrupos , página 265, Historia de las matemáticas 41, Sociedad matemática estadounidenseISBN 978-1-4704-1493-1
Bibliografía
- Schmidt, Gunther ; Ströhlein, Thomas (2012). "Capítulo 3: Relaciones heterogéneas" . Relaciones y gráficos: matemáticas discretas para informáticos . Springer Science & Business Media. ISBN 978-3-642-77968-8.
- Ernst Schröder (1895) Algebra der Logik, Band III , a través de 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.
- Enderton, Herbert (1977). Elementos de la teoría de conjuntos . Boston: Prensa académica . ISBN 978-0-12-238440-0.
- Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander (2000). Monoides, actos y categorías: con aplicaciones a productos de coronas y gráficos . Berlín: De Gruyter . ISBN 978-3-11-015248-7.
- Peirce, Charles Sanders (1873). "Descripción de una notación para la lógica de los parientes, resultado de una ampliación de las concepciones del cálculo de la lógica de Boole" . Memorias de la Academia Estadounidense de Artes y Ciencias . 9 (2): 317-178. 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
- Medios relacionados con las relaciones binarias en Wikimedia Commons
- "Relación binaria" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]