Relación conectada

"Connexity" vuelve a dirigir aquí. Para conocer la empresa de comparación de precios, consulte Connexity Inc.

Relaciones binarias
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Relación de equivalencia ✓ ✗ ✗ ✗ ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Orden parcial ✗ ✓ ✗ ✗ ✗ ✗ Reserva total ✗ ✗ ✓ ✗ ✗ ✗ Orden total ✗ ✓ ✓ ✗ ✗ ✗ Ordenamiento previo ✗ ✗ ✓ ✓ ✗ ✗ Bien casi ordenado ✗ ✗ ✗ ✓ ✗ ✗ Bien ordenado ✗ ✓ ✓ ✓ ✗ ✗ Enrejado ✗ ✓ ✗ ✗ ✓ ✓ Unión-semirrejilla ✗ ✓ ✗ ✗ ✓ ✗ Encuentro-semilattice ✗ ✓ ✗ ✗ ✗ ✓
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 todo donde , ${\displaystyle x,y\in X,}$${\displaystyle x\neq y}$

${\displaystyle x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x,}$

o, de manera equivalente, cuando para todos ,${\displaystyle x,y\in X}$

${\displaystyle x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x\quad {\text{or}}\quad x=y.}$

Una relación con la propiedad que para todos , ${\displaystyle x,y\in X}$

${\displaystyle x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x}$

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 relación total en el sentido de que para todo existe un tal que (ver relación serial ).${\displaystyle x\in X}$${\displaystyle y\in X}$${\displaystyle x\mathrel {R} y}$

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 denominan completas , ^[7] aunque esto también puede generar confusión: la relación universaltambién se llama completo, ^[8] y " completo " tiene varios otros significados en la teoría del orden . Las relaciones conectados también se llaman connex ^{[9] [10]} o decir que satisfagan tricotomía ^[11] (aunque la definición más común de tricotomía es más fuerte que en exactamente una de las tres opciones , , debe ser titular).${\displaystyle x\mathrel {R} y}$${\displaystyle y\mathrel {R} x}$${\displaystyle x=y}$

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

Sea una relación homogénea. Los siguientes son equivalentes: ^[14]${\displaystyle R}$

• ${\displaystyle R}$ está fuertemente conectado;
• ${\displaystyle U\subseteq R\cup R^{\top }}$;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }}$;
• ${\displaystyle {\overline {R}}}$es asimétrico ,

donde es la relación universal y es la relación inversa de .${\displaystyle U}$${\displaystyle R^{\top }}$${\displaystyle R}$

Los siguientes son equivalentes: ^[14]

• ${\displaystyle R}$ está conectado;
• ${\displaystyle {\overline {I}}\subseteq R\cup R^{\top }}$;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }\cup I}$;
• ${\displaystyle {\overline {R}}}$es antisimétrico ,

donde es la relación complementaria de la relación de identidad y es la relación inversa de .${\displaystyle {\overline {I}}}$ ${\displaystyle I}$${\displaystyle R^{\top }}$${\displaystyle R}$

Propiedades

• El borde relación ^[16] de un torneo gráfico es siempre una relación conectado en el set de G ' vértices s.${\displaystyle E}$${\displaystyle G}$
• 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 conjunto no puede ser antitransitiva , siempre que tenga 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.${\displaystyle X}$${\displaystyle X}$
• Si es una relación conectada en , entonces todos, o todos menos uno, los elementos de están en el rango de . ^[19] De manera similar, todos, o todos menos uno, los elementos de están en el dominio de .${\displaystyle R}$${\displaystyle X}$${\displaystyle X}$${\displaystyle R}$${\displaystyle X}$${\displaystyle R}$

Referencias

1. 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 .
2. 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.
3. Causey, Robert L. (1994). Lógica, conjuntos y recursividad . Jones y Bartlett Learning. ISBN 0-86720-463-X., pag. 135
4. 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.
5. 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
6. 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
7. 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
8. Whitehead, Alfred North ; Russell, Bertrand (1910). Principia Mathematica . Cambridge: Cambridge University Press.
9. Pared, Robert E. (1974). Introducción a la lingüística matemática . Prentice Hall. página 114.
10. Carl Pollard. "Relaciones y funciones" (PDF) . Universidad Estatal de Ohio . Consultado el 28 de mayo de 2018 . Página 7.
11. Kunen, Kenneth (2009). Los fundamentos de las matemáticas . Publicaciones universitarias. ISBN 978-1-904987-14-7.pag. 24
12. 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.
13. 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
14. 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.
15. 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
16. definido formalmente porsi el borde de un gráfico va de vérticea vértice${\displaystyle vEw}$${\displaystyle v}$${\displaystyle w}$
17. Para la única dirección si , ambas propiedades siguen trivialmente. - Para ladirección if : cuandoluegosigue de la conexión; cuando, se sigue de la reflexividad.${\displaystyle x\neq y,}$${\displaystyle x\mathrel {R} y\lor y\mathrel {R} x}$${\displaystyle x=y}$${\displaystyle x\mathrel {R} y}$
18. 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.
19. Si x , y ∈ X \ ran ( R ), entoncesyson imposibles, por lo que sesigue de la conexión.${\displaystyle x\mathrel {R} y}$${\displaystyle y\mathrel {R} x}$${\displaystyle x=y}$