Relação conectada - Connected relation
Relações binárias transitivas | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Todas as definições exigem tacitamente que a relação homogênea seja transitiva : Um " ✓ " indica que a propriedade da coluna é necessária na definição da linha. Por exemplo, a definição de uma relação de equivalência requer que ela seja simétrica. Listadas aqui estão propriedades adicionais que uma relação homogênea pode satisfazer.
|
Em matemática, uma relação em um conjunto é chamada conectada ou total se relaciona (ou "compara") todos os pares distintos de elementos do conjunto em uma direção ou outra, enquanto é chamada fortemente conectada se relaciona todos os pares de elementos. Conforme descrito na seção de terminologia abaixo , a terminologia dessas propriedades não é uniforme. Essa noção de "total" não deve ser confundida com a de uma relação total no sentido de que para todos existe um tal que (ver relação serial ).
Conectividade aparece com destaque na definição de ordens totais : uma ordem total (ou linear) é uma ordem parcial em que quaisquer dois elementos são comparáveis; ou seja, a relação de ordem está conectada. Da mesma forma, uma ordem parcial estrita conectada é uma ordem total estrita. Uma relação é uma ordem total se e somente se for uma ordem parcial e fortemente conectada. Uma relação é uma ordem total estrita se, e somente se, for uma ordem parcial estrita e apenas conectada. Um pedido total estrito nunca pode ser fortemente conectado (exceto em um domínio vazio).
Definição formal
Uma relação em um conjunto é chamada conectado quando para todos
Uma relação com a propriedade que para todos
Terminologia
O principal uso da noção de relação conectada é no contexto de ordens, onde é usada para definir ordens totais ou lineares. Nesse contexto, muitas vezes a propriedade não é nomeada especificamente. Em vez disso, os pedidos totais são definidos como pedidos parciais em que quaisquer dois elementos são comparáveis. Assim,total é usado mais geralmente para relações que estão conectadas ou fortemente conectadas. No entanto, essa noção de "relação total" deve ser distinguida da propriedade de serserial, que também é chamada de total. Da mesma forma, as relações conectadas às vezes são chamadascompleto , embora isso também possa levar à confusão:a relação universaltambém é chamada de completo e "completo" tem vários outros significados nateoria da ordem. As relações conectadas também são chamadasconnex ou dito para satisfazer atricotomia(embora a definição mais comum detricotomiaseja mais forte porqueexatamente umadas três opçõesdeve ser válida).
Quando as relações consideradas não são ordens, estar conectado e estar fortemente conectado são propriedades significativamente diferentes. Fontes que definem ambos usam pares de termos comofracamente conectado econectado,completoefortemente completo,totalecompleto,semiconnex econnex, ouconnexeestritamente connex , respectivamente, como nomes alternativos para as noções de conectado e fortemente conectado conforme definido acima.
Caracterizações
Deixe ser uma relação homogênea. Os seguintes são equivalentes:
- está fortemente conectado;
- ;
- ;
- é assimétrico ,
onde está a relação universal e é a relação inversa de
Os seguintes são equivalentes:
onde está a relação complementar da relação de identidade e é a relação inversa de
Apresentando as progressões, Russell invocou o axioma da conexão:
Sempre que uma série é originalmente dada por uma relação transitiva assimétrica, podemos expressar conexão pela condição de que quaisquer dois termos de nossa série tenham a relação geradora .
- Bertrand Russell , The Principles of Mathematics, página 239
Propriedades
- A borda relação de um campeonato gráfico é sempre uma relação conectado sobre o conjunto de ' vértices s.
- Se uma relação fortemente conectada é simétrica , é a relação universal .
- Uma relação está fortemente conectada se, e somente se, for conectada e reflexiva.
- Uma relação conectada em um conjunto não pode ser antitransitiva , desde que tenha pelo menos 4 elementos. Em um conjunto de 3 elementos, por exemplo, a relação tem ambas as propriedades.
- Se for uma relação conectada em então todos, ou todos, exceto um, os elementos de estão na faixa de Da mesma forma, todos, ou todos, exceto um, os elementos de estão no domínio de
Notas
- Provas