relación conectada

Propiedad de una relación en un conjunto

En matemáticas, una relación en un conjunto se llama conexa , completa o total si relaciona (o "compara") todos los pares distintos de elementos del conjunto en una dirección u otra, mientras que se llama fuertemente conexa si relaciona todos los pares de elementos. Como se describe en la sección de terminología a continuación, la terminología para estas propiedades no es uniforme. Esta noción de "total" no debe confundirse con la de relación total en el sentido de que para todos existe un tal que (ver relación serial ). ${\displaystyle x\in X}$ ${\displaystyle y\in X}$ ${\displaystyle x\mathrel {R} y}$

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 es conexa. De manera similar, un orden parcial estricto que es conexo es un orden total estricto. Una relación es de orden total si y sólo si es a la vez de orden parcial y fuertemente conexa. Una relación es de orden total estricto si, y sólo si, es de orden parcial estricto y simplemente conexa. Un orden total estricto nunca puede estar fuertemente conectado (excepto en un dominio vacío).

Definicion formal

Una relación en un conjunto se llama ${\displaystyle R}$ ${\displaystyle X}$conectado cuando para todos ${\displaystyle x,y\in X,}$

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

${\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}$$

fuertemente conectado^[1][2][3]

Terminología

El uso principal de la noción de relación conexa es en el contexto de los pedidos, donde se utiliza para definir pedidos totales o lineales. En este contexto, la propiedad a menudo no recibe un nombre específico. Más bien, los pedidos totales se definen como pedidos parciales en los que dos elementos cualesquiera son comparables. ^{[4] [5]} Por lo tanto,total se usa más generalmente 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 serserial, que también se llama total. De manera similar, las relaciones conectadas a veces se denominancompleta ,^[7]aunque esto también puede llevar a confusión: larelación universaltambién se llama completa,^[8]y "completa" tiene varios otros significados enla teoría del orden. Las relaciones conectadas también se llamanconnex ^[9][10]o se dice que satisfacela tricotomía^[11](aunque la definición más común detricotomíaes más fuerte en el sentido de queexactamente unade las tres opcionesdebe ser válida). ${\displaystyle x\mathrel {R} y,y\mathrel {R} x,x=y}$

Cuando las relaciones consideradas no son órdenes, estar conectado y estar fuertemente conectado son propiedades importantes diferentes. Las fuentes que definen ambos utilizan pares de términos comodébilmente conectado yconectado,^[12] completoyfuertemente completo,^[13] totalycompleto,^[6] semiconexion yconexión ,^[14]oconectar yestrictamente connex ,^[15]respectivamente, como nombres alternativos para las nociones de conectado y fuertemente conectado como se define 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.}$

Al presentar las progresiones, Russell invocó el axioma de conexión:

Siempre que una serie está dada originalmente por una relación asimétrica transitiva, podemos expresar conexión mediante la condición de que dos términos cualesquiera de nuestra serie tengan la relación generadora .

—  Bertrand Russell , Los principios de las matemáticas , página 239

Propiedades

• La relación de borde ^{[nota 1]} de un gráfico de torneo es siempre una relación conexa en el conjunto de los vértices. ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle G}$
• Si una relación fuertemente conexa es simétrica , es la relación universal .
• Una relación es fuertemente conexa si, y sólo si, es conexa y reflexiva. ^{[prueba 1]}
• Una relación conexa en un conjunto no puede ser antitransitiva , siempre que tenga al menos 4 elementos. ^[16] En un conjunto de 3 elementos, por ejemplo, la relación tiene ambas propiedades. ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \{a,b,c\},}$ ${\displaystyle \{(a,b),(b,c),(c,a)\}}$
• Si es una relación conexa, entonces todos, o todos menos uno, los elementos de están en el rango de ^{[prueba 2]} 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.}$

Notas

1. Definido formalmente por si un borde del gráfico va de un vértice a otro ${\displaystyle vEw}$ ${\displaystyle v}$ ${\displaystyle w}$

Pruebas

1. Para la única dirección if, ambas propiedades se siguen de manera trivial. — Para la dirección if : cuando entonces se deriva de la conexión; cuando se deriva 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}$
2. Si entonces y son imposibles, así se desprende de la conexión. ${\displaystyle x,y\in X\setminus \operatorname {ran} (R),}$ ${\displaystyle x\mathrel {R} y}$ ${\displaystyle y\mathrel {R} x}$ ${\displaystyle x=y}$

Referencias

1. Clapham, Cristóbal; Nicholson, James (18 de septiembre de 2014). "conectado". El conciso Diccionario 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 . Aprendizaje de Jones y Bartlett. 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 conectividad.
5. Patricio Cousot (1990). "Métodos y lógicas para la demostración de programas". En Jan van Leeuwen (ed.). Modelos formales y semántica . Manual de informática teórica. vol. B. Elsevier. págs. 841–993. ISBN 0-444-88074-7.Aquí: Sección 6.3, p.878
6. Aliprantis, Charalambos D.; Frontera, Kim C. (2 de mayo de 2007). Análisis dimensional infinito: una guía para el 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 Computación . Saltador. ISBN 978-1-4471-2500-6., pag. 50
8. Whitehead, Alfred Norte ; Russell, Bertrand (1910). Principia Mathematica. Cambridge: Prensa de la Universidad de Cambridge.{{cite book}}: CS1 maint: date and year (link)
9. Muro, Robert E. (1974). Introducción a la Lingüística Matemática . Prentice Hall.página 114.
10. Carl Pollard. «Relaciones y Funciones» (PDF) . Universidad del Estado 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 . Medios de ciencia y negocios de Springer. ISBN 978-3-642-59830-2.pag. 86
16. Jochen Burghardt (junio de 2018). Leyes simples sobre propiedades no prominentes de las relaciones binarias (Informe técnico). arXiv : 1806.05036 . Código Bib : 2018arXiv180605036B.Lema 8.2, p.8.