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 u otra dirección, 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 una 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}$

La conexidad 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á conexa. De manera similar, un orden parcial estricto que está conexo es un orden total estricto. Una relación es un orden total si y solo si es un orden parcial y fuertemente conexo. Una relación es un orden total estricto si, y solo si, es un orden parcial estricto y simplemente conexo. Un orden total estricto nunca puede estar fuertemente conexo (excepto en un dominio vacío).

Definición formal

Una relación en un conjunto se llama ${\displaystyle R}$ ${\displaystyle X}$conectado cuando para todos o, equivalentemente, 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 se llama ${\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 órdenes, donde se utiliza para definir órdenes totales o lineales. En este contexto, la propiedad a menudo no se nombra específicamente. Más bien, los órdenes totales se definen como órdenes parciales en los que dos elementos cualesquiera son comparables. ^{[4] [5]} Por lo tanto,El término total se utiliza de manera más general para las 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 denomina 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 contundente en el sentido de queexactamente unade las tres opciones). ${\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 diferentes y significativas. Las fuentes que definen ambas utilizan pares de términos comodébilmente conectado yconectado,^[12] completoyfuertemente completo,^[13] totalycompleto,^[6] Semiconnex yconectar ,^[14]oConectar yestrictamente conexo ,^[15]respectivamente, como nombres alternativos para las nociones de conectado y fuertemente conectado como se definió anteriormente.

Caracterizaciones

Sea una relación homogénea . Las 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 identidad y es la relación inversa de ${\displaystyle {\overline {I}}}$ ${\displaystyle I}$ ${\displaystyle R^{\top }}$ ${\displaystyle R.}$

Al introducir 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 la 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 arista ^{[nota 1]} de un gráfico de torneo es siempre una relación conectada en el conjunto de vértices de . ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle G}$
• Si una relación fuertemente conexa es simétrica , es la relación universal .
• Una relación está fuertemente conectada si, y sólo si, es conectada 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 en 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. Se define formalmente como si una arista de un gráfico va de vértice a vértice. ${\displaystyle vEw}$ ${\displaystyle v}$ ${\displaystyle w}$

Pruebas

1. Para la única dirección if, ambas propiedades se siguen trivialmente. — Para la dirección if : cuando entonces se sigue de la conexidad; 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}$
2. Si entonces y son imposibles, entonces se sigue de la conexidad. ${\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, Christopher; Nicholson, James (18 de septiembre de 2014). "conectado". Diccionario Oxford conciso de matemáticas. Oxford University Press. ISBN 978-0-19-967959-1. Recuperado el 12 de abril de 2021 .
2. Nievergelt, Yves (13 de octubre de 2015). Lógica, matemáticas y ciencias de la computación: fundamentos modernos con aplicaciones prácticas. Springer. pág. 182. ISBN 978-1-4939-3223-8.
3. Causey, Robert L. (1994). Lógica, conjuntos y recursión . Jones & Bartlett Learning. ISBN 0-86720-463-X., pág. 135
4. Paul R. Halmos (1968). Teoría de conjuntos ingenua . Princeton: Nostrand.Aquí: Cap. 14. Halmos da los nombres de reflexividad, antisimetría y transitividad, pero no de conectividad.
5. Patrick Cousot (1990). "Métodos y lógica para probar 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í: Secc.6.3, p.878
6. Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Análisis de dimensión infinita: una guía para el autoestopista . Springer. ISBN 978-3-540-32696-0., pág. 6
7. Makinson, David (27 de febrero de 2012). Conjuntos, lógica y matemáticas para la informática . Springer. ISBN 978-1-4471-2500-6., pág. 50
8. Whitehead, Alfred North ; Russell, Bertrand (1910). Principia Mathematica. Cambridge: Cambridge University Press.{{cite book}}: CS1 maint: date and year (link)
9. Wall, 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). Fundamentos de las matemáticas . Publicaciones universitarias. ISBN 978-1-904987-14-7.pág. 24
12. Fishburn, Peter C. (8 de marzo de 2015). La teoría de la elección social. Princeton University Press. pág. 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 . Cambridge University Press. ISBN 978-0-521-10243-8.página 29
14. Schmidt, Gunther ; Ströhlein, Thomas (1993). Relaciones y gráficos: matemáticas discretas para científicos 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.pág. 86
16. Jochen Burghardt (junio de 2018). Leyes simples sobre propiedades no prominentes de relaciones binarias (informe técnico). arXiv : 1806.05036 . Código Bibliográfico :2018arXiv180605036B.Lema 8.2, p.8.