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 en un conjunto se llama conectada o total si relaciona todos los pares distintos de elementos del conjunto en una dirección u otra, es decir, si se pueden comparar dos elementos cualesquiera. Más formalmente, una relación R en un conjunto X está conectada cuando para todos dónde ,
o, de manera equivalente, cuando para todos ,
Una relación con la propiedad que para todos ,
se llama fuertemente conectado . [1] [2] [3]
La terminología para estas propiedades no es uniforme, ver más abajo . La noción no debe confundirse con la de una relación total en el sentido de que para todos hay un así que eso (ver relación serial ).
Conectividad y pedidos totales
La conectividad ocupa un lugar destacado en la definición de órdenes totales : un orden total (o lineal) es un orden parcial en el que dos elementos cualesquiera son comparables, es decir, la relación de orden está conectada. De manera similar, un orden parcial estricto que está conectado es un orden total estricto.
Una relación es un orden total si, y solo si , es un orden parcial y está fuertemente conectado. Una relación es un orden total estricto si, y solo si, es un orden parcial estricto y solo está conectado. Un orden total estricto nunca puede estar fuertemente conectado (excepto en un dominio vacío).
Terminología
El uso principal de la noción de relación conectada es en el contexto de órdenes, donde se usa para definir órdenes totales o lineales. En este contexto, la propiedad a menudo no se nombra específicamente. Más bien, los pedidos totales se definen como pedidos parciales en los que dos elementos son comparables. [4] [5] Por lo tanto, total se usa de manera más general para relaciones que están conectadas o fuertemente conectadas. [6] Sin embargo, esta noción de "relación total" debe distinguirse de la propiedad de ser serial , que también se llama total. De manera similar, las relaciones conectadas a veces se llaman completas , [7] aunque esto también puede llevar a confusión: la relación universal también se llama completa, [8] y " completa " tiene varios otros significados en la teoría del orden . Las relaciones conectadas también se denominan connex [9] [10] o se dice que satisfacen la tricotomía [11] (aunque la definición más común de tricotomía es más fuerte porque exactamente una de las tres opciones, , debe aguantar).
Cuando las relaciones consideradas no son órdenes, estar conectado y estar fuertemente conectado son propiedades muy diferentes. Las fuentes que definen ambos utilizan pares de términos como débilmente conectado y conectado , [12] completo y fuertemente completo , [13] total y completo , [6] semiconnex y connex , [14] o connex y estrictamente connex , [15] respectivamente, como nombres alternativos para las nociones de conectado y fuertemente conectado como se definió anteriormente.
Caracterizaciones
Dejar ser una relación homogénea. Los siguientes son equivalentes: [14]
- está fuertemente conectado;
- ;
- ;
- es asimétrico ,
dónde es la relación universal yes la relación inversa de.
Los siguientes son equivalentes: [14]
- está conectado;
- ;
- ;
- es antisimétrico ,
dónde es la relación complementaria de la relación de identidad y es la relación inversa de.
Propiedades
- La relación de borde [16] de un gráfico de torneoes siempre una relación conectado en el set de G ' vértices s.
- Si una fuertemente conectada es simétrica , es la relación universal .
- Una relación está fuertemente conectada si, y solo si, está conectada y es reflexiva. [17]
- Una relación conectada en un set no puede ser antitransitivo , siempre quetiene al menos 4 elementos. [18] En un conjunto de 3 elementos { a , b , c } , por ejemplo, la relación {( a , b ), ( b , c ), ( c , a )} tiene ambas propiedades.
- Si es una relación conectada en , entonces todos, o todos menos uno, elementos de están en el rango de. [19] Del mismo modo, todos, o todos menos uno, los elementos de están en el dominio de .
Referencias
- ^ Clapham, Christopher; Nicholson, James (18 de septiembre de 2014). "conectado". El Diccionario Conciso de Oxford de Matemáticas . Prensa de la Universidad de Oxford. ISBN 978-0-19-967959-1. Consultado el 12 de abril de 2021 .
- ^ Nievergelt, Yves (13 de octubre de 2015). Lógica, matemáticas e informática: fundamentos modernos con aplicaciones prácticas . Saltador. pag. 182. ISBN 978-1-4939-3223-8.
- ^ Causey, Robert L. (1994). Lógica, conjuntos y recursividad . Jones y Bartlett Learning. ISBN 0-86720-463-X., pag. 135
- ^ Paul R. Halmos (1968). Teoría de conjuntos ingenua . Princeton: Nostrand.Aquí: Capítulo 14. Halmos da los nombres de reflexividad, antisimetría y transitividad, pero no de conexión.
- ^ Patrick Cousot (1990). "Métodos y lógicas para probar programas". En Jan van Leeuwen (ed.). Modelos formales y semántica . Manual de Informática Teórica. B . Elsevier. págs. 841–993. ISBN 0-444-88074-7. Aquí: Sección 6.3, p.878
- ^ a b Aliprantis, Charalambos D .; Border, Kim C. (2 de mayo de 2007). Análisis dimensional infinito: una guía del autoestopista . Saltador. ISBN 978-3-540-32696-0., pag. 6
- ^ Makinson, David (27 de febrero de 2012). Conjuntos, lógica y matemáticas para la informática . Saltador. ISBN 978-1-4471-2500-6., pag. 50
- ^ Whitehead, Alfred North ; Russell, Bertrand (1910). Principia Mathematica . Cambridge: Cambridge University Press.Mantenimiento CS1: fecha y año ( enlace )
- ^ Wall, Robert E. (1974). Introducción a la lingüística matemática . Prentice Hall. página 114.
- ^ Carl Pollard. "Relaciones y funciones" (PDF) . Universidad Estatal de Ohio . Consultado el 28 de mayo de 2018 . Página 7.
- ^ Kunen, Kenneth (2009). Los fundamentos de las matemáticas . Publicaciones universitarias. ISBN 978-1-904987-14-7.pag. 24
- ^ Fishburn, Peter C. (8 de marzo de 2015). La teoría de la elección social . Prensa de la Universidad de Princeton. pag. 72. ISBN 978-1-4008-6833-9.
- ^ Roberts, Fred S. (12 de marzo de 2009). Teoría de la medición: Volumen 7: con aplicaciones a la toma de decisiones, la utilidad y las ciencias sociales . Prensa de la Universidad de Cambridge. ISBN 978-0-521-10243-8. página 29
- ^ a b c Schmidt, Gunther ; Ströhlein, Thomas (1993). Relaciones y gráficos: matemáticas discretas para informáticos . Berlín: Springer. ISBN 978-3-642-77970-1.
- ^ Ganter, Bernhard; Wille, Rudolf (6 de diciembre de 2012). Análisis de conceptos formales: fundamentos matemáticos . Springer Science & Business Media. ISBN 978-3-642-59830-2.pag. 86
- ^ definido formalmente por si el borde de un gráfico sale del vértice al vértice
- ^ Para la única dirección si , ambas propiedades siguen trivialmente. - Para ladirección if : cuando luego se sigue de la conectividad; Cuándo, se sigue de la reflexividad.
- ^ Jochen Burghardt (junio de 2018). Leyes simples sobre propiedades no prominentes de las relaciones binarias (Informe técnico). arXiv : 1806.05036 . Código bibliográfico : 2018arXiv180605036B . Lema 8.2, página 8.
- ^ Si x , y ∈ X \ ran ( R ), entonces y son imposibles, entonces se sigue de la conectividad.