Relación conexa

En matemáticas, unha relación nun conxunto chámase conexa ou completa ou total se relaciona (ou "compara") todos os pares distintos de elementos do conxunto nunha dirección ou noutra, mentres que se chama fortemente conexa se relaciona todos os pares de elementos. Como se describe a continuación na sección de terminoloxía, a terminoloxía destas propiedades non é uniforme.

A propiedade de conexa ocupa un lugar destacado na definición de ordes totais unha orde total (ou linear) é unha orde parcial na que dous elementos calquera son comparábeis; é dicir, a relación de orde é conexa. Do mesmo xeito, unha orde parcial estrita que é conexa é unha orde total estrita. Unha relación é unha orde total se e só se é unha orde parcial e a maiores é fortemente conexa. Unha relación é unha orde total estrita se, e só se, é unha orde parcial estrita e só conexa. Unha orde total estrita nunca pode ser fortemente conexa (agás nun dominio baleiro).

Esta noción de "relación total" debe distinguirse da propiedade de ser serial, que tamén se chama relación total.

Definición formal

Unha relación ${\displaystyle R}$ nun conxunto ${\displaystyle X}$ chámase conexa cando para todos os ${\displaystyle x,y\in X,}$

${\displaystyle {\text{ se }}x\neq y}$ entón ${\displaystyle x\mathrel {R} y\quad {\text{ou}}\quad y\mathrel {R} x,}$

ou, de xeito equivalente, cando para todo ${\displaystyle x,y\in X,}$

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

Unha relación coa propiedade que para todo ${\displaystyle x,y\in X,}$

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

chámase fortemente conexa.^[1][2][3]

Terminoloxía

O uso principal da noción de relación conexa é no contexto das ordes, onde se usa para definir ordes totais ou lineares. Neste contexto, a propiedade moitas veces non se denomina especificamente. Pola contra, as ordes totais defínense como ordes parciais nas que dous elementos calquera son comparábeis.^[4][5] Así, total úsase de xeito máis xeral para relacións que son conexas ou fortemente conexas.^[6]

Porén, esta noción de "relación total" debe distinguirse da propiedade de ser serial, que tamén se chama total.

Seguindo con distintos nomes, ás veces as relacións conexas chámanse completas,^[7] aínda que isto tamén pode levar a confusión: a relación universal tamén se denomina completa,^[8] e "completude" ten outros significados na teoría da orde.

As relacións conexas tamén se di que satisfán a tricotomía^[9] (aínda que a definición máis común de tricotomía é máis forte en que exactamente unha das tres opcións ${\displaystyle x\mathrel {R} y,\ y\mathrel {R} x,\ x=y}$ debe cumprirse).

Cando as relacións consideradas non son ordes, ser conexo e ser fortemente conexo son propiedades moi diferentes. As fontes que definen ambas as dúas usan logo pares de termos como debilmente conexa e conexa,^[10] completa e fortemente completa,^[11] total e completa,^[6] semiconexa e conexa,^[12] ou conexa e estritamente conexa ,^[13] respectivamente, como nomes alternativos para as nocións de conexa e fortemente conexa como se definiu anteriormente.

Caracterizacións

Sexa ${\displaystyle R}$ unha relación homoxénea.

Para fórtemente conexa os seguintes enunciados son equivalentes: ^[12]

• ${\displaystyle R}$ é fortemente conexa;
• ${\displaystyle U\subseteq R\cup R^{\top }}$;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }}$;
• ${\displaystyle {\overline {R}}}$ é asimétrica,

onde ${\displaystyle U}$ é a relación universal e ${\displaystyle R^{\top }}$ é a relación inversa de ${\displaystyle R.}$

Para só conexa os seguintes enunciados son equivalentes: ^[12]

• ${\displaystyle R}$ é conexa;
• ${\displaystyle {\overline {I}}\subseteq R\cup R^{\top }}$;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }\cup I}$;
• ${\displaystyle {\overline {R}}}$ é antisimétrica ,

onde ${\displaystyle {\overline {I}}}$ é a relación complementaria da relación identidade ${\displaystyle I}$ e ${\displaystyle R^{\top }}$ é a relación inversa de ${\displaystyle R.}$

Propiedades

• A relación aresta ^{[note 1]} ${\displaystyle E}$ dun grafo de torneo ${\displaystyle G}$ é sempre unha relación conexa no conxunto de vértices de ${\displaystyle G}$.
• Se unha relación fortemente conexa é simétrica, é a relación universal.
• Unha relación é fortemente conexa se, e só se, é conexa e reflexiva.^{[proof 1]}
• Unha relación conexa nun conxunto ${\displaystyle X}$ non pode ser antitransitiva, sempre que ${\displaystyle X}$ ten polo menos 4 elementos. Nun conxunto de 3 elementos ${\displaystyle \{a,b,c\},}$ por exemplo, a relación ${\displaystyle \{(a,b),(b,c),(c,a)\}}$ ten as dúas propiedades.
• Se ${\displaystyle R}$ é unha relación conexa sobre ${\displaystyle X,}$ entón todos, ou todos menos un, os elementos de ${\displaystyle X}$ están no rango de ${\displaystyle R.}$ ^{[proof 2]} Do mesmo xeito, todos, ou todos menos un, os elementos de ${\displaystyle X}$ están no dominio de ${\displaystyle R.}$

Notas

1. Clapham, Christopher; Nicholson, James (2014-09-18). "connected". En Oxford University Press. The Concise Oxford Dictionary of Mathematics. ISBN 978-0-19- 967959-1. Consultado o 2021-04-12.
2. Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations Practical Applications. p. 182. ISBN 978-1-4939-3223-8.
3. Causey, Robert L. (1994). Logic, Sets, and Recursion. Jones & Bartlett Learning. ISBN 0-86720-463-X., p. 135
4. Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. Aqui: Cap.14. Halmos da os nomes de reflexiva, antisimétrica e transitiva, mais non de conexa.
5. Patrick Cousot (1990). "Methods and Logics for Proving Programs". En Jan van Leeuwen. Formal Models and Semantics. Handbook of Theoretical Computer Science B. Elsevier. pp. 841–993. ISBN 0-444-88074-7. Aquí: Sec.6.3, p.878
6. Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer. ISBN 978-3-540-32696-0., páx. 6
7. Makinson, David (2012-02-27). Sets, Logic and Maths for Computing. Springer. ISBN 978-1-4471-2500-6., p. 50
8. Whitehead, Alfred North; Russell, Bertrand (1910). Principia Mathematica. Cambridge: Cambridge University Press.
9. Kunen, Kenneth (2009). The Foundations of Mathematics. College Publications. ISBN 978-1-904987-14-7. p. 24
10. Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9.
11. Roberts, Fred S. (2009-03-12). Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences. Cambridge University Press. ISBN 978-0-521-10243-8. páxina 29
12. Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970- 1.
13. Ganter, Bernhard; Wille, Rudolf (2012-12-06). Formal Análise de conceptos: fundamentos matemáticos. Springer Science & Business Media. ISBN 978-3-642-59830-2. p. 86

1. Definida formalmente por ${\displaystyle vEw}$ se unha aresta do grafo vai dun vértice ${\displaystyle v}$ a un vértice ${\displaystyle w}$

1. Para a dirección só se, ambas as propiedades dedúcense trivialmente. Para a dirección se: cando ${\displaystyle x\neq y,}$ logo ${\displaystyle x\mathrel {R} y\lor y\mathrel {R} x}$ dedúcese da propiedade conexa; cando ${\displaystyle x=y,}$ ${\displaystyle x\mathrel {R} y}$ dedúcese da propiedade reflexiva.
2. Se ${\displaystyle x,y\in X\setminus \operatorname {ran} (R),}$ daquela ${\displaystyle x\mathrel {R} y}$ e ${\displaystyle y\mathrel {R} x}$ son imposíbeis, por tanto ${\displaystyle x=y}$ dedúcese da propiedade conexa.

Véxase tamén

Bibliografía

• Gunther Schmidt & Michael Winter (2018) Relational Topology
• C. Brink, W. Kahl, and G. Schmidt (1997) Relational Methods in Computer Science, Advances in Computer Science, page 5, ISBN 3-211-82971-7
• Gunther Schmidt & Thomas Strohlein (2012)[1987] Relations and Graphs en Google Books.

Outros artigos

• Orde total.
• Preorde.