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  de elementos do conxunto nunha dirección ou noutra, mentres que se chama fortemente conexa se relaciona  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  nun conxunto  chámase  cando para todos os 
  entón 
ou, de xeito equivalente, cando para todo 

Unha relación coa propiedade que para todo 

chámase ., p. 135

 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. Aqui: Cap.14. Halmos da os nomes de reflexiva, antisimétrica e transitiva, mais non de conexa. Aquí: Sec.6.3, p.878
Así,  úsase de xeito máis xeral para relacións que son conexas ou fortemente conexas., páx. 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 ,, p. 50 aínda que isto tamén pode levar a confusión: a relación universal tamén se denomina completa, e "completude" ten outros significados na teoría da orde.

As relacións conexas tamén se di que satisfán a  p. 24 (aínda que a definición máis común de tricotomía é máis forte en que  das tres opcións  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  e ,  e , páxina 29  e ,  e , ou  e , p. 86 respectivamente, como nomes alternativos para as nocións de conexa e fortemente conexa como se definiu anteriormente.

 Caracterizacións 
Sexa  unha relación homoxénea. 

Para fórtemente conexa os seguintes enunciados son equivalentes: 

  é fortemente conexa;
 ;
 ;
  é asimétrica,

onde  é a relación universal e  é a relación inversa de 

Para só conexa os seguintes enunciados son equivalentes: 

  é conexa;
 ;
 ;
  é antisimétrica ,

onde  é a relación complementaria da relación identidade  e  é a relación inversa de 

 Propiedades 

 A relación  Definida formalmente por  se unha aresta do grafo vai dun vértice  a un vértice   dun grafo de torneo  é sempre unha relación conexa no conxunto de vértices de .
 Se unha relación fortemente conexa é simétrica, é a relación universal.
 Unha relación é fortemente conexa se, e só se, é conexa e reflexiva.Para a dirección , ambas as propiedades dedúcense trivialmente. Para a dirección : cando  logo  dedúcese da propiedade conexa; cando   dedúcese da propiedade reflexiva.
 Unha relación conexa nun conxunto  non pode ser antitransitiva, sempre que  ten polo menos 4 elementos.  Nun conxunto de 3 elementos  por exemplo, a relación  ten as dúas propiedades.
 Se  é unha relación conexa sobre  entón todos, ou todos menos un, os elementos de  están no rango de  Se  daquela  e  son imposíbeis, por tanto  dedúcese da propiedade conexa. Do mesmo xeito, todos, ou todos menos un, os elementos de  están no dominio de 

 Notas 


 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, 
 Gunther Schmidt & Thomas Strohlein (2012)[1987] 

 Outros artigos 
 Orde total.
 Preorde.

Categoría:Teoría da orde