Relación conectada

En matemáticas, una relación en un conjunto se denomina 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 denomina 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${\displaystyle x\in X}$hay un${\displaystyle y\in X}$de modo que${\displaystyle x\mathrel {R} y}$(ver relación serial ).

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 un orden total si y solo si es a la vez un orden parcial y fuertemente conexa. Una relación es un orden total estricto si y solo si es un orden parcial estricto y simplemente conexa. Un orden total estricto nunca puede ser fuertemente conexo (excepto en un dominio vacío).

Sin embargo, algunos autores utilizan el término «conectado» con un significado mucho más amplio, que se aplica precisamente a aquellos órdenes cuyos grafos de comparabilidad son grafos conectados . Esto se aplica, por ejemplo, a las vallas , de las cuales ninguno de los ejemplos no triviales son órdenes totales.

Una relación${\displaystyle R}$en un plató${\displaystyle X}$se llamaconectado cuando para todos${\displaystyle x,y\in X,}$$${\displaystyle {\text{ si }}x\neq y{\text{ entonces }}x\mathrel {R} y\quad {\text{o}}\quad y\mathrel {R} x,}$$ o, equivalentemente, cuando para todos${\displaystyle x,y\in X,}$$${\displaystyle x\mathrel {R} y\quad {\text{o}}\quad y\mathrel {R} x\quad {\text{o}}\quad x=y.}$$

Una relación con la propiedad que para todos${\displaystyle x,y\in X,}$$${\displaystyle x\mathrel {R} y\quad {\text{o}}\quad y\mathrel {R} x}$$ se llamafuertemente conectados . ^{[ 1 ] [ 2 ] [ 3 ]}

Dejar${\displaystyle R}$sea ​​una relación homogénea . Las siguientes son equivalentes: ^{[ 14 ]}

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

dónde${\displaystyle U}$es la relación universal y${\displaystyle R^{\top }}$es la relación inversa de${\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 ,

dónde${\displaystyle {\overline {R}}}$es la relación complementaria de${\displaystyle R}$,${\displaystyle I}$es la relación de identidad y${\displaystyle R^{\top }}$es la relación inversa de${\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 cualesquiera dos términos de nuestra serie tengan la relación generadora .

• La relación de arista ^{[ nota 1 ]}${\displaystyle E}$de un gráfico de torneo${\displaystyle G}$es siempre una relación conectada en el conjunto de${\displaystyle G}$vértices de
• Si una relación fuertemente conectada es simétrica , es la relación universal .
• Una relación es fuertemente conexa si, y solo si, es conexa y reflexiva. ^{[ prueba 1 ]}
• Una relación conectada en un conjunto${\displaystyle X}$no puede ser antitransitivo , siempre que${\displaystyle X}$tiene al menos 4 elementos. ^{[ 16 ]} En un conjunto de 3 elementos${\displaystyle \{a,b,c\},}$por ejemplo, la relación${\displaystyle \{(a,b),(b,c),(c,a)\}}$tiene ambas propiedades.
• Si${\displaystyle R}$es una relación conectada en${\displaystyle X,}$entonces todos, o todos menos uno, elementos de${\displaystyle X}$están en el rango de${\displaystyle R.}$^{[ prueba 2 ]} De manera similar, todos, o todos menos uno, elementos de${\displaystyle X}$están en el dominio de${\displaystyle R.}$

Pruebas