Relación binaria

Ajustar Compartir Imprimir Citar

Relación entre dos conjuntos, definida por un conjunto de pares ordenados

Relaciones binarias transitivas

	Simétrico	Antisymmetric	Conectado	Bien fundada	Has joineds	Has meets	Reflexivo	Irreflexivo	Asimétrica
			Total, Semiconnex					Anti- reflexivo
Equivalencia relación	Y	✗	✗	✗	✗	✗	Y	✗	✗
Preorden (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Orden parcial	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total preordenado	✗	✗	Y	✗	✗	✗	Y	✗	✗
Orden total	✗	Y	Y	✗	✗	✗	Y	✗	✗
Prewellordering	✗	✗	Y	Y	✗	✗	Y	✗	✗
Bien ordenado	✗	✗	✗	Y	✗	✗	Y	✗	✗
Bien ordenado	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Orden parcial estricta	✗	Y	✗	✗	✗	✗	✗	Y	Y
Orden débil estricto	✗	Y	✗	✗	✗	✗	✗	Y	Y
Orden total estricta	✗	Y	Y	✗	✗	✗	✗	Y	Y
	Simétrico	Antisymmetric	Conectado	Bien fundada	Has joineds	Has meets	Reflexivo	Irreflexivo	Asimétrica
Definiciones, para todos $a,b$ y ${displaystyle Sneq varnothing:}$	${displaystyle {begin{aligned}&aRb\Rightarrow {}&bRaend{aligned}}}$	${displaystyle {begin{aligned}aRb{text{ and }}&bRa\Rightarrow a={}&bend{aligned}}}$	${displaystyle {begin{aligned}aneq {}&bRightarrow \aRb{text{ or }}&bRaend{aligned}}}$	${displaystyle {begin{aligned}min S\{text{exists}}end{aligned}}}$	${displaystyle {begin{aligned}avee b\{text{exists}}end{aligned}}}$	${displaystyle {begin{aligned}awedge b\{text{exists}}end{aligned}}}$	${displaystyle aRa}$	${displaystyle {text{not }}aRa}$	${displaystyle {begin{aligned}aRbRightarrow \{text{not }}bRaend{aligned}}}$

Y indica que la propiedad de la columna es requerida por la definición del término de la fila (a la izquierda). Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. ✗ indica que la propiedad puede, o no puede retener. Todas las definiciones requieren tácitamente la relación homogénea

R

ser transitivo: para todos

a,b,c,

{displaystyle aRb}

{displaystyle bRc}

entonces

{displaystyle aRc,}

y hay propiedades adicionales que una relación homogénea puede satisfacer.

En matemáticas, a relación binaria asocia elementos de un conjunto, llamado dominio, con elementos de otro conjunto, llamado codomain. Una relación binaria sobre conjuntos $X$ y $Y$ es un nuevo conjunto de pares ordenados $() x, Sí.)$ consistentes en elementos $x$ dentro $X$ y $Sí.$ dentro $Y$ . Se trata de una generalización de la idea más ampliamente comprendida de una función invariable. Codifica el concepto común de relación: un elemento $x$ es conexas a un elemento $Sí.$ , si y sólo si el par $() x, Sí.)$ pertenece al conjunto de pares ordenados que define el relación binaria. Una relación binaria es el caso especial más estudiado $n = 2$ de una relación n-ary sobre conjuntos $X 1,... X n$ , que es un subconjunto del producto cartesiano ${displaystyle X_{1}times cdots times X_{n}.}$

Un ejemplo de relación binaria es la relación "divides" sobre el conjunto de números primos $mathbb {P}$ y el conjunto de enteros $mathbb {Z}$ , en el cual cada primo $p$ está relacionado con cada entero $z$ que es un múltiple $p$ , pero no a un entero que no es un múltiple $p$ . En esta relación, por ejemplo, el número principal 2 está relacionado con números tales como −4, 0, 6, 10, pero no a 1 o 9, así como 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:

las relaciones "es mayor que", "es igual", y "divide" en aritmética;
la relación "es congruente con" en la geometría;
la relación "está adyacente a" en la teoría del gráfico;
la relación "es ortogonal a" en álgebra lineal.

Una función puede definirse como un tipo especial de relación binaria. 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 de poder ${displaystyle Xtimes Y.}$ Puesto que este último conjunto se ordena por inclusión (⊆), cada relación tiene un lugar en la celo de subconjuntos de ${displaystyle Xtimes Y.}$ Una relación binaria se llama una relación homogénea cuando X = Y. Una relación binaria también se llama una relación heterogénea cuando no es necesario que X = Y.

Dado que las relaciones son conjuntos, se pueden manipular mediante operaciones de conjuntos, incluidas la unión, la intersección y la complementación, y que cumplen 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, que satisfacen las leyes de un cálculo de relaciones, para las cuales hay libros de texto de Ernst Schröder, Clarence Lewis y Gunther Schmidt. Un análisis más profundo de las relaciones implica descomponerlas en subconjuntos llamados conceptos y colocarlos en una red completa.

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.

Los términos correspondencia, dyadic relation y relación de dos puestos son sinónimos para relación binaria, aunque algunos autores utilizan el término "relación binaria" para cualquier subconjunto de un producto cartesiano $Xtimes Y$ sin referencia $X$ y $Y$ , y reservar el término "correspondence" para una relación binaria con referencia a $X$ y $Y$ .

Definición

Puestos X y Y, el producto cartesiano $Xtimes Y$ se define como ${displaystyle {(x,y):xin X{text{ and }}yin Y},}$ y sus elementos se llaman pares ordenados.

A relación binaria R sobre conjuntos X y Y es un subconjunto de ${displaystyle Xtimes Y.}$ El set X se llama dominio o Conjunto de salida de R, y el conjunto Y el codomain o conjunto de destino de R. Para especificar las opciones de los conjuntos X y Y, algunos autores definen un relación binaria o correspondencia como un triple ordenado $() X, Y, G)$ , donde G es un subconjunto de $Xtimes Y$ llamado Gráfico de la relación binaria. La declaración $(x, y) in R$ lee "x es R- relacionadas con Sí."y es denotado por x Ry. El dominio de la definición o dominio activo de R es el conjunto de todos x tales que x Ry por lo menos uno Sí.. El codomain of definition, codomain activo, imagen o rango de R es el conjunto de todos Sí. tales que x Ry por lo menos uno x. El sobre el terreno de R es la unión de su dominio de definición y su codominio de definición.

Cuando ${displaystyle X=Y,}$ una relación binaria se llama relación homogénea (o endorelación). Destacar el hecho de que X y Y se permite ser diferente, una relación binaria también se llama una relación heterogénea.

En una relación binaria, el orden de los elementos es importante; si $xneq y$ entonces YRx puede ser verdad o falso independientemente de x Ry. Por ejemplo, 3 divide 9, pero 9 no divide 3.

Ejemplos

2a relación ejemplo
$A$ $B .$	bola	coche	doll	taza
John.	+	−	−	−
Mary.	−	−	+	−
Venus	−	+	−	−

1a relación ejemplo
$A$ $B$	bola	coche	doll	taza
John.	+	−	−	−
Mary.	−	−	+	−
Ian	−	−	−	−
Venus	−	+	−	−

1) El siguiente ejemplo muestra que la elección del codominio es importante. Supongamos que hay cuatro objetos ${displaystyle A={{text{ball, car, doll, cup}}}}$ y cuatro personas ${displaystyle B={{text{John, Mary, Ian, Venus}}}.}$ Una posible relación A y B es la relación "es propiedad", dada por ${displaystyle R={({text{ball, John}}),({text{doll, Mary}}),({text{car, Venus}})}.}$ Es decir, Juan posee la pelota, María es dueña de la muñeca, y Venus posee el coche. Nadie posee la copa y Ian no posee nada; vea el primer ejemplo. Como un conjunto, R no implica a Ian, y por lo tanto R podría haber sido visto como un subconjunto ${displaystyle Atimes {{text{John, Mary, Venus}}},}$ i.e. a relation over A y ${displaystyle {{text{John, Mary, Venus}}};}$ ver el segundo ejemplo. Si bien la relación del segundo ejemplo es subjetiva (ver abajo), el primero no es.

Océanos y continentes (islas omitidas)

Continente de fronteras marítimas
	NA	SA	AF	UE	ASÍ	AU	AA
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, EU, AS, AU, AA }, los continentes. Sea aRb que el océano a limita con el continente b. Entonces la matriz lógica para esta relación es:

{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&1end{pmatrix}}.}

La conectividad del planeta Tierra se puede ver a través de R^T y R^T R, el primero es un $4 times 4$ relación A, que es la relación universal ( $Atimes A$ o una matriz lógica de todos). Esta relación universal refleja el hecho de que cada océano está separado de los otros por la mayoría de un continente. Por otro lado, R^T R es una relación $Btimes B$ que fallas ser universal porque al menos dos océanos deben ser atravesados para viajar de Europa a Australia.

3) La visualización de relaciones se basa en la teoría de grafos: para relaciones en un conjunto (relaciones homogéneas), un gráfico dirigido ilustra una relación y un gráfico 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 en un conjunto, las bicliques se usan para describir relaciones heterogéneas; de hecho, son los "conceptos" que generan un retículo asociado a una relación.

Los diversos t ejes representan tiempo para los observadores en movimiento, el correspondiente x ejes son sus líneas de simultaneidad

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 de espacio cuando ese producto es cero. El producto interior indefinido en un álgebra de composición viene dado por

<math alttext="{displaystyle = x{bar {z}}+{bar {x}}z;}" xmlns="http://www.w3.org/1998/Math/MathML">.x,z■=xz̄ ̄ +x̄ ̄ z{fnMicrosoft Sans Serif}+{bar {x}z}<img alt="{displaystyle = x{bar {z}}+{bar {x}}z;}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e68f3e2af8797c1ec681b24b217262b2944313ff" style="vertical-align: -0.671ex; width:21.793ex; height:2.343ex;"/>

donde la barra denota conjugación.

Como relación entre algunos eventos temporales y algunos eventos espaciales, la ortogonalidad hiperbólica (como se encuentra en los números complejos divididos) es una relación heterogénea.

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. Los planos finitos e infinitos y proyectivos están incluidos. Jakob Steiner fue pionero en la catalogación de configuraciones con los sistemas Steiner ${displaystyle {text{S}}(t,k,n)}$ que tienen un conjunto de n-element S y un conjunto de subconjuntos k-element llamados bloques, tal que un subconjunto con t los elementos se encuentran en una sola cuadra. 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, IDonde V y B son dos conjuntos y I es una relación binaria entre V y B, es decir.

{displaystyle Isubseteq Vtimes {textbf {B}}.}

Los elementos de V será llamado puntos, los de B bloques y los de I flags.

Tipos especiales de relaciones binarias

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

Algunos tipos importantes de relaciones binarias R sobre conjuntos X e Y se enumeran a continuación.

Propiedades de singularidad:

Inyección (también llamado izquierda-unique): para todos ${displaystyle x,zin X}$ y todos ${displaystyle yin Y,}$ si $x Ry$ y $z Ry$ entonces $x = z$ . Para tal relación, {YSe llama una clave primaria de R. Por ejemplo, las relaciones binarias verdes y azules en el diagrama son inyectables, pero el rojo no es (como se refiere tanto −1 y 1 a 1), ni el negro (como se refiere tanto −1 y 1 a 0).
Funcional (también llamado derecha-unique, derecho-definido o univalent): para todos $xin X$ y todos ${displaystyle y,zin Y,}$ si $x Ry$ y $x Rz$ entonces $Sí. = z$ . Tal relación binaria se llama función parcial. Para tal relación, ${displaystyle {X}}$ se llama una clave primaria de R. Por ejemplo, las relaciones binarias rojas y verdes en el diagrama son funcionales, pero el azul no es (como se relaciona 1 con −1 y 1), ni el negro (como se relaciona 0 con ambos −1 y 1).
Uno a uno: inyector y funcional. Por ejemplo, la relación binaria verde en el diagrama es uno a uno, pero los rojos, azules y negros no lo son.
Uno a otro: inyector y no funcional. Por ejemplo, la relación binaria azul en el diagrama es de una a otra, 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 muchas a una, pero las verdes, azules y negras no lo son.
Muchas a muchas personas: no inyector ni funcional. Por ejemplo, la relación binaria negra en el diagrama es muchas a muchas, pero las rojas, verdes y azules no lo son.

Propiedades de totalidad (solo definibles si se especifica el dominio X y el codominio Y):

Total (también llamado izquierda-total): para todos x dentro X existe Sí. dentro Y tales que $x Ry$ . En otras palabras, el dominio de la definición R es igual a X. Esta propiedad, es diferente de la definición de conectado (también llamado total por algunos autores) en Propiedades. Tal relación binaria se llama Función multivalorada. Por ejemplo, las relaciones binarias rojas y verdes en el diagrama son totales, pero el azul no es (como no se relaciona −1 con ningún número real), ni el negro (como no se relaciona 2 con ningún número real). Como otro ejemplo, es una relación total sobre los enteros. Pero no es una relación total sobre los enteros positivos, porque no hay $Sí.$ en los enteros positivos tal que $1 \pm Sí.$ . Sin embargo, es una relación total sobre los enteros positivos, los números racionales y los números reales. Cada relación reflexiva es total: para un dado $x$ , elegir $Sí. = x$ .
Surjective (también llamado derecho a o sobre): para todos Sí. dentro Y, existe un x dentro X tales que x Ry. En otras palabras, el codominio de la definición R es igual a Y. Por ejemplo, las relaciones binarias verdes y azules en el diagrama son subjetivas, pero el rojo no es (como no se relaciona ningún número real con −1), ni el negro (como no se 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):

A función: una relación binaria que es funcional y total. Por ejemplo, las relaciones binarias rojas y verdes en el diagrama son funciones, pero las azules y negras no lo son.
An inyección: una función que es inyectable. Por ejemplo, la relación binaria verde en el diagrama es una inyección, pero las rojas, azules y negras no lo son.
A surjection: una función que es subjetiva. Por ejemplo, la relación binaria verde en el diagrama es una subjeción, pero las rojas, azules y negras no lo son.
A bijeción: una función que es inyectable y subjetiva. Por ejemplo, la relación binaria verde en el diagrama es una bijeción, pero las rojas, azules y negras no lo son.

Si se permiten relaciones sobre clases adecuadas:

Como un juego (o local): para todos $x$ dentro $X$ , la clase de todos $Sí.$ dentro $Y$ tales que $YRx$ , es decir. ${displaystyle {yin Y:yRx}}$ Es un juego. Por ejemplo, la relación $in$ es algo parecido, y cada relación en dos sets es similar. El pedido habitual se hizo a través de la clase de números ordinal es una relación tipo conjunto, mientras que su inverso не no es.

Operaciones sobre relaciones binarias

Unión

Si R y S son relaciones binarias sobre conjuntos X y Y entonces ${displaystyle Rcup S={(x,y):xRy{text{ or }}xSy}}$ es relación sindical de R y S sobre X y Y.

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

Intersección

Si R y S son relaciones binarias sobre conjuntos X y Y entonces ${displaystyle Rcap S={(x,y):xRy{text{ and }}xSy}}$ es 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 conjuntos X y Y, y S es una relación binaria sobre conjuntos Y y Z entonces ${displaystyle Scirc R={(x,z):{text{ there exists }}yin Y{text{ such that }}xRy{text{ and }}ySz}}$ (también denotado por $R; S$ ) es el relación de R y S sobre X y Z.

El elemento de identidad es la relación de identidad. El orden R y S en la notación ${displaystyle Scirc R,}$ utilizado aquí está de acuerdo con el orden notacional estándar para la composición de funciones. Por ejemplo, la composición (es padre de) ${displaystyle ,circ ,}$ (es madre de) rendimientos (es abuelo materno de), mientras que la composición (es madre de) ${displaystyle ,circ ,}$ (es padre de) rendimientos (es abuela de). Para el caso anterior, si x es el padre de Sí. y Sí. es la madre de z, entonces x es el abuelo materno de z.

Conversar

Si R es una relación binaria sobre conjuntos X y Y entonces ${displaystyle R^{textsf {T}}={(y,x):xRy}}$ es relación transversal de R sobre Y y X.

Por ejemplo, = es el contrario de sí mismo, como es ${displaystyle ,neq,}$ y $<math alttext="{displaystyle ,.{displaystyle ,tratado,} <img alt="{displaystyle ,$ y $,}" xmlns="http://www.w3.org/1998/Math/MathML">■{displaystyle , titulado,},}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa4d5b016960fc5ca6be3194c6b857f2035e029" style="vertical-align: -0.338ex; width:2.582ex; height:1.843ex;"/>$ son el contrario, como son ${displaystyle ,leq ,}$ y ${displaystyle ,geq.,}$ Una relación binaria es igual a su converso si y sólo si es simétrica.

Complemento

Si R es una relación binaria sobre conjuntos X y Y entonces ${displaystyle {overline {R}}={(x,y):{text{ not }}xRy}}$ (también denotado por R o $\neg R$ ) es el Relación complementaria de R sobre X y Y.

Por ejemplo, ${displaystyle ,=,}$ y ${displaystyle ,neq ,}$ son el complemento del otro, como son ${displaystyle ,subseteq ,}$ y ${displaystyle ,not subseteq,}$ ${displaystyle ,supseteq ,}$ y ${displaystyle ,not supseteq,}$ y ${displaystyle ,in ,}$ y ${displaystyle ,not in,}$ y, para pedidos totales, también ${displaystyle ,geq,}$ y ${displaystyle ,leq.,}$

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

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

Si una relación es simétrica, entonces también es el complemento.
El complemento de una relación reflexiva es irreflexivo y viceversa.
El complemento de un estricto orden débil es un 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 ${displaystyle R_{vert S}={(x,y)mid xRy{text{ and }}xin S{text{ and }}yin S}}$ es restricción de R a S sobre X.

Si R es una relación binaria sobre conjuntos X y Y y si S es un subconjunto de X entonces ${displaystyle R_{vert S}={(x,y)mid xRy{text{ and }}xin S}}$ es relación izquierda-restricción de R a S sobre X y Y.

Si R es una relación binaria sobre conjuntos X y Y y si S es un subconjunto de Y entonces ${displaystyle R^{vert S}={(x,y)mid xRy{text{ and }}yin S}}$ es relación de restricción de derechos de R a S sobre X y 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 de equivalencia, 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 "x es padre de y" a las hembras se obtiene la relación "x es madre de la mujer y"; su clausura transitiva 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 integridad (no confundirse con ser "total") no llevan a cabo restricciones. Por ejemplo, sobre los números reales una propiedad de la relación ${displaystyle ,leq ,}$ es que cada subconjunto no vacío ${displaystyle Ssubseteq mathbb {R} }$ con un límite superior $mathbb {R}$ tiene un límite inferior (también llamado supremum) en ${displaystyle mathbb {R}.}$ Sin embargo, para los números racionales este supremum no es necesariamente racional, por lo que la misma propiedad no sostiene la restricción de la relación ${displaystyle ,leq ,}$ a los números racionales.

Una relación binaria R sobre conjuntos X y Y se dice que contenidas en a) Relación S sobre X y Y, escrito ${displaystyle Rsubseteq S,}$ si R es un subconjunto de S, es decir, para todos $xin X$ y ${displaystyle yin Y,}$ si x Ry, entonces xSy. Si R figura en S y S figura en R, entonces R y S se llaman iguales escrito R = S. Si R figura en S pero S no figura en R, entonces R se dice que más pequeño que S, escrito ${displaystyle Rsubsetneq S.}$ Por ejemplo, sobre los números racionales, la relación $,}" xmlns="http://www.w3.org/1998/Math/MathML">■{displaystyle , titulado,},}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa4d5b016960fc5ca6be3194c6b857f2035e029" style="vertical-align: -0.338ex; width:2.582ex; height:1.843ex;"/>$ es más pequeño que ${displaystyle ,geq,}$ e igual a la composición $,circ ,>.,}" xmlns="http://www.w3.org/1998/Math/MathML">■∘ ∘ ■.{displaystyle , titulado,circ , titulado.,},circ ,>.,}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5a2f306bf3adf366cb49934c07820b941fe549b6" style="vertical-align: -0.338ex; width:8.264ex; height:1.843ex;"/>$

Representación matricial

Las relaciones binarias entre conjuntos X e Y se pueden representar algebraicamente mediante matrices lógicas indexadas por X e Y con entradas en el semicírculo 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), 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 un semicírculo matricial (de hecho, una semiálgebra matricial sobre el semicírculo booleano) donde la matriz identidad corresponde a la relación identidad.

Conjuntos versus clases

Ciertas "relaciones" matemáticas, como "igual", "subconjunto de", y "miembro de", no pueden entenderse como relaciones binarias definidas anteriormente, porque sus dominios y codominios no pueden ser tomados para ser conjuntos en los sistemas habituales de teoría de conjuntos axiomáticos. Por ejemplo, para modelar el concepto general de "igualdad" como relación binaria ${displaystyle ,=,}$ tomar el dominio y el codomain para ser la "clase de todos los conjuntos", que no es un conjunto en la teoría de conjunto habitual.

En la mayoría de los contextos matemáticos, las referencias a las relaciones de igualdad, membresía y subconjunto son inofensivas porque pueden entenderse implícitamente a ser restringidas a algún conjunto en el contexto. El trabajo habitual en torno a este problema es seleccionar un conjunto "lo suficientemente grande" A, que contiene todos los objetos de interés, y trabajar con la restricción =_A en lugar de =. Del mismo modo, la relación "subconjunto" ${displaystyle ,subseteq ,}$ necesita ser restringido para tener dominio y codomain P(A) (el conjunto de potencia de un conjunto específico A): la relación establecida resultante puede ser denotada por ${displaystyle ,subseteq _{A}.,}$ Además, la relación "miembro de" debe ser restringida a tener dominio A y codomain P(A) para obtener una relación binaria ${displaystyle ,in _{A},}$ Eso es un juego. Bertrand Russell ha demostrado que suponiendo ${displaystyle ,in ,}$ ser definido sobre todos los conjuntos conduce a una contradicción en la teoría de conjuntos ingenuos, ver Paradoja de Russell.

Otra solución a este problema es utilizar una teoría de conjuntos con las clases adecuadas, como NBG o la teoría de conjuntos de Morse-Kelley, y permitir que el dominio y el codominio (y, por lo tanto, el gráfico) sean clases adecuadas: en tal teoría, igualdad, pertenencia y subconjunto son relaciones binarias sin comentarios especiales. (Es necesario realizar una modificación menor al concepto del triple ordenado $(X, Y, G)$ , ya que normalmente una clase adecuada no puede ser miembro de una tupla ordenada; o, por supuesto, uno puede identificar la relación binaria con su gráfico en este contexto.) Con esta definición, se puede, por ejemplo, definir una relación binaria sobre cada conjunto y su conjunto potencia.

Relación homogénea

A relación homogénea sobre un conjunto X es una relación binaria sobre X es un subconjunto del producto cartesiano ${displaystyle Xtimes X.}$ También se llama simplemente una relación (binaria) sobre X.

Una relación homogénea R sobre un conjunto X se puede identificar con un gráfico sencillo dirigido que permite bucles, donde X es el vertex fijado y R es el filo fijado (hay un borde de un vértice x a un vértice Sí. si $x Ry$ ). El conjunto de todas las relaciones homogéneas ${displaystyle {mathcal {B}}(X)}$ sobre un conjunto X es el sistema de poder ${displaystyle 2^{Xtimes X}}$ que es un álgebra booleana aumentada con la involución de mapeo de una relación a su relación conversa. Considerando la composición de las relaciones como operación binaria en ${displaystyle {mathcal {B}}(X)}$ , forma un semigrupo con involución.

Algunas propiedades importantes que una relación homogénea $R$ sobre un conjunto $X$ pueden tener son:

Reflexivo: para todos ${displaystyle xin X,}$ $x Rx$ . Por ejemplo, ${displaystyle ,geq ,}$ es una relación reflexiva pero no lo es.
Irreflexivo: para todos ${displaystyle xin X,}$ no $x Rx$ . Por ejemplo, $,}" xmlns="http://www.w3.org/1998/Math/MathML">■{displaystyle , titulado,},}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa4d5b016960fc5ca6be3194c6b857f2035e029" style="vertical-align: -0.338ex; width:2.582ex; height:1.843ex;"/>$ es una relación irreflexiva, pero ${displaystyle ,geq ,}$ No lo es.
Simétrico: para todos ${displaystyle x,yin X,}$ si $x Ry$ entonces $YRx$ . Por ejemplo, "es un pariente de sangre" es una relación simétrica.
Antisymmetric: para todos ${displaystyle x,yin X,}$ si $x Ry$ y $YRx$ entonces ${displaystyle x=y.}$ Por ejemplo, ${displaystyle ,geq ,}$ es una relación antisimétrica.
Asimétrica: para todos ${displaystyle x,yin X,}$ si $x Ry$ entonces no $YRx$ . Una relación es asimétrica si y sólo si es antisimétrica e irreflexiva. Por ejemplo, es una relación asimétrica, pero ${displaystyle ,geq ,}$ No lo es.
Transitive: para todos ${displaystyle x,y,zin X,}$ si $x Ry$ y $YRz$ entonces $x Rz$ . Una relación transitiva es irreflexiva si y sólo si es asimétrica. Por ejemplo, "es ancestro de" es una relación transitiva, mientras que "es padre de" no es.
Conectado: para todos ${displaystyle x,yin X,}$ si $xneq y$ entonces $x Ry$ o $YRx$ .
Fuertemente conectado: para todos ${displaystyle x,yin X,}$ $x Ry$ o $YRx$ .
Dense: para todos ${displaystyle x,yin X,}$ si ${displaystyle xRy,}$ entonces algunos $zin X$ existe tal ${displaystyle xRz}$ y $zRy$ .

A Orden parcial es una relación reflexiva, antisimétrica y transitiva. A estricto orden parcial es una relación irreflexiva, antisimétrica y transitiva. A total es una relación reflexiva, antisimétrica, transitiva y conectada. A estricto orden total es una relación irreflexiva, antisimétrica, transitiva y conectada. An Relación de equivalencia es una relación reflexiva, simétrica y transitiva. Por ejemplo, "x divideciones Sí." es un orden parcial, pero no un orden total en números naturales ${displaystyle mathbb {N}}$ "x. Sí."es un orden total estricto ${displaystyle mathbb {N}}$ y "x es paralelo a Sí." es una relación de equivalencia en el conjunto de todas las líneas en el plano Euclideano.

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 flexible: la relación reflexiva más pequeña sobre X que contiene R,
Cierre transitorio: la relación transitiva más pequeña X que contiene R,
Cierre de la equidad: la relación de equivalencia más pequeña sobre X que contiene R.

Relación heterogénea

En matemáticas, a relación heterogénea es una relación binaria, un subconjunto de un producto cartesiano ${displaystyle Atimes B,}$ Donde A y B son grupos posiblemente distintos. El prefijo hetero es del griego ἕτερος (heteros, "otro, otro, diferente").

Una relación heterogénea se ha llamado relación rectangular, sugiriendo que no tiene la simetría cuadrada de una relación homogénea en un conjunto donde ${displaystyle A=B.}$ Comentando 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énea o rectangular, es decir, como relaciones donde el caso normal es que son relaciones entre diferentes conjuntos."

Cálculo de relaciones

Los desarrollos en la lógica algebraica han facilitado el uso de relaciones binarias. El cálculo de las relaciones incluye el álgebra de conjuntos, extendido por la composición de las relaciones y el uso de las relaciones conversas. La inclusión ${displaystyle Rsubseteq S,}$ significa que aRb implicación aSb, pone la escena en una celosa de las relaciones. Pero... ${displaystyle Psubseteq Qequiv (Pcap {bar {Q}}=varnothing)equiv (Pcap Q=P),}$ el símbolo de inclusión es superfluo. Sin embargo, la composición de las relaciones y la manipulación de los operadores según las reglas de Schröder, proporciona un cálculo para trabajar en el conjunto de poder ${displaystyle Atimes B.}$

A diferencia de las relaciones homogéneas, la operación de composición de relaciones es sólo una función parcial. La necesidad de hacer coincidir el rango con el dominio 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 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.

Retícula conceptual inducida

Las relaciones binarias se han descrito a través de sus retículas de conceptos inducidos: Un concepto C ⊂ R satisface dos propiedades: (1) La matriz lógica de C es el producto exterior de Vectores lógicos

{displaystyle C_{ij} = u_{i}v_{j},quad u,v}

vectores lógicos. 2) C es maximal, no contenido en ningún otro producto externo. Así C se describe como un rectángulo no ampliable.

Para una relación dada ${displaystyle Rsubseteq Xtimes Y,}$ el conjunto de conceptos, agrandados por sus afiliados y encuentros, forma una "rejilla inducida de conceptos", con inclusión $sqsubseteq$ formando un preorden.

El teorema de compleción de MacNeille (1937) (que cualquier orden parcial puede estar incrustado en una red completa) se cita en un artículo de encuesta de 2013 "Descomposición de relaciones en redes conceptuales". la descomposición es

{displaystyle R = f E g^{textsf {T}},}

Donde f y g son funciones, llamadas cartografías o relaciones izquierd-total, univalentas en este contexto. La vestimenta de concepto inducida es isomorfa a la terminación cortada del orden parcial E que pertenece a la mínima descomposición (f, g, E) de la relación R."

Los casos particulares se consideran a continuación: E orden total corresponde al tipo de Ferrers, y E identidad 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. El análisis estructural de las relaciones con los conceptos proporciona un enfoque para la minería de datos.

Relaciones particulares

ProposiciónSi R es una relación serie y R^T es su transpose, entonces ${displaystyle Isubseteq R^{textsf {T}}R}$ Donde $I$ es m × m relación de identidad.
ProposiciónSi R es una relación subjetiva, entonces ${displaystyle Isubseteq RR^{textsf {T}}}$ Donde $I$ es $ntimes n$ relación de identidad.

Difuncional

La idea de una relación difuncional es dividir objetos mediante atributos diferenciadores, como una generalización del concepto de una relación de equivalencia. Una manera de que esto se puede hacer es con un conjunto interveniente ${displaystyle Z={x,y,z,ldots }}$ de indicadores. La relación de partición ${displaystyle R=FG^{textsf {T}}}$ es una composición de relaciones usando univalent relaciones ${displaystyle Fsubseteq Atimes Z{text{ and }}Gsubseteq Btimes Z.}$ Jacques Riguet nombró estas relaciones difunctional desde la composición F G^T implica relaciones univales, comúnmente llamadas Funciones parciales.

En 1950 Rigeut demostró que tales relaciones satisfacen la inclusión:

{displaystyle R R^{textsf {T}} R subseteq R}

En la teoría de la automata, 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 pueden ser arregladas como una matriz de bloques con bloques rectangulares de uno en la diagonal principal (asimétrica). Más formalmente, una relación $R$ on $Xtimes Y$ es difuncional si y sólo si puede ser escrito como la unión de productos cartesianos ${displaystyle A_{i}times B_{i}}$ , donde el $A_{i}$ son una partición de un subconjunto de $X$ y el $B_{i}$ también una partición de un subconjunto de $Y$ .

Usando la notación {Sí.: x Ry} = xR, una relación difuncional también se puede caracterizar como una relación R tal como sea x₁R y x₂R tienen una intersección no vacía, entonces estos dos conjuntos coinciden; formalmente ${displaystyle x_{1}cap x_{2}neq varnothing }$ implicación ${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." Además, las relaciones difuncionales son fundamentales en el estudio de las bisimulaciones.

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

Tipo de hurones

Un orden estricto sobre 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 de un número entero, llamado diagrama de Ferrers, para extender el ordenamiento a las relaciones binarias en general.

La matriz lógica correspondiente de una relación binaria general tiene filas que terminan con una secuencia de unos. Así, los puntos del 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

{displaystyle R{bar {R}}^{textsf {T}}Rsubseteq R.}

Si alguna de las relaciones ${displaystyle R, {bar {R}}, R^{textsf {T}}}$ es de tipo Ferrers, entonces todos ellos lo son.

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 cumple tres propiedades:

${displaystyle {text{for all }}xin A,Y={x}{text{ implies }}xgY.}$
${displaystyle Ysubseteq Z{text{ and }}xgY{text{ implies }}xgZ.}$
${displaystyle {text{for all }}yin Y,ygZ{text{ and }}xgY{text{ implies }}xgZ.}$

La relación de pertenencia del 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.

En términos del cálculo de relaciones, las condiciones suficientes para una relación de contacto incluyen

{displaystyle C^{textsf {T}}{bar {C}} subseteq ni {bar {C}} equiv C {overline {ni {bar {C}}}} subseteq C,}

ni

Reserva RR

Cada relación R genera un preorden ${displaystyle Rbackslash R}$ que es el residual izquierdo. En términos de converso y complementos, ${displaystyle Rbackslash R equiv {overline {R^{textsf {T}}{bar {R}}}}.}$ Formando la diagonal de ${displaystyle R^{textsf {T}}{bar {R}}}$ , la fila correspondiente ${displaystyle R^{text{T}}}$ and column of ${bar {R}}$ será de valores lógicos opuestos, por lo que la diagonal es todos ceros. Entonces...

{displaystyle R^{textsf {T}}{bar {R}}subseteq {bar {I}} implies Isubseteq {overline {R^{textsf {T}}{bar {R}}}} = Rbackslash R,}

así

{displaystyle Rbackslash R}

es una relación reflexiva.

Para mostrar transitividad, se requiere que ${displaystyle (Rbackslash R)(Rbackslash R)subseteq Rbackslash R.}$ Recordad que ${displaystyle X=Rbackslash R}$ es la relación más grande tal que ${displaystyle RXsubseteq R.}$ Entonces...

{displaystyle R(Rbackslash R)subseteq R}

{displaystyle R(Rbackslash R)(Rbackslash R)subseteq R}

(repetir)

{displaystyle equiv R^{textsf {T}}{bar {R}}subseteq {overline {(Rbackslash R)(Rbackslash R)}}}

(La regla de Schröder)

{displaystyle equiv (Rbackslash R)(Rbackslash R)subseteq {overline {R^{textsf {T}}{bar {R}}}}}

(complementación)

{displaystyle equiv (Rbackslash R)(Rbackslash R)subseteq Rbackslash R.}

(definición)

La relación de inclusión Ω en el conjunto de potencia U puede obtenerse de esta manera de la relación de membresía ${displaystyle ,in ,}$ on subsets of U:

{displaystyle Omega = {overline {ni {bar {in }}}} = in backslash in.}

Margen de una relación

Dada una relación R, una sub-relación llamada su margen se define como

{displaystyle operatorname {fringe} (R)=Rcap {overline {R{bar {R}}^{textsf {T}}R}}.}

Cuando R es una relación de identidad parcial, difuncional o una relación diagonal de bloque, luego frange(R) R. De lo contrario, el operador de franja selecciona una subrelación de límites descrita en términos de su matriz lógica: fringe(R) es el lado diagonal si R es una orden lineal triangular superior derecha o un orden estricto. FringeR) es la franja de bloque si R es irreflexivo ( ${displaystyle Rsubseteq {bar {I}}}$ ) o de bloque superior derecho triangular. FringeR) es una secuencia de rectángulos de límites cuando R es de tipo Ferrers.

Por otro lado, Fringe(R) = ∅ cuando R es un orden denso, lineal y estricto.

Montones matemáticos

Dados dos sets A y B, el conjunto de relaciones binarias entre ellos ${displaystyle {mathcal {B}}(A,B)}$ se puede equipar con una operación ternaria ${displaystyle [a, b, c] = ab^{textsf {T}}c}$ Donde b^T denota la relación conversa b. En 1953 Viktor Wagner utilizó propiedades de esta operación ternaria para definir semiheaps, montones y montones generalizados. El contraste de las relaciones heterogéneas y homogéneas se destaca por estas definiciones:

Hay una simetría agradable en el trabajo de Wagner entre montones, semiheaps y montones generalizados por un lado, y grupos, semigrupos y grupos generalizados por otro. Esencialmente, los diversos tipos de semiheaps aparecen cada vez que consideramos relaciones binarias (y mapas parciales uno-uno) entre diferentes sets A y B, mientras que los diversos tipos de semigrupos aparecen en el caso A = B.
—Christopher Hollings, "Mathematics across the Iron Curtain: a history of the algebraic theory of semigroups"

Te puede interesar
Johann Friedrich Endersch
(leer más)
Te puede interesar
El dilema del prisionero
(leer más)
Te puede interesar
Franz mertens
(leer más)
Más resultados...