Relação de transitividade

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática, uma relação binária R sobre um conjunto X é transitiva se, sempre que um elemento de a está relacionado a um elemento de b, e b é relacionado a um elemento de c, então a também está relacionado com c. A transitividade é uma propriedade chave de ambos os conjunto parcialmente ordenado e de relações de equivalência.

Definição Formal[editar | editar código-fonte]

Em termos de teoria dos conjuntos, a relação transitiva pode ser definido como:

Exemplos[editar | editar código-fonte]

Por exemplo, "é maior que", é pelo menos tão grande quanto " e "é igual a" (igualdade) são relações transitivas:

sempre que A > B e B > C, então a também A > C
sempre que A ≥ B e B ≥ C, então a também A ≥ C
sempre que A = B e B = C, então a também A = C.

Por outro lado, "é a mãe de" não é uma relação transitiva, porque se Alice é a mãe de Brenda, Brenda é a mãe de Claire, em seguida, Alice não é a mãe de Claire. Na verdade é não transitivo: Alice pode nunca ser a mãe de Claire.

Então, novamente, em biologia, muitas vezes precisamos considerar a maternidade através de um número arbitrário de gerações: a relação "é um atrilinearidade ancestral". Esta é uma relação transitiva. Mais precisamente, é o fechamento transitivo da relação "é a mãe".

Mais exemplos de relações transitivas:

Propriedades[editar | editar código-fonte]

Fechamento de propriedades[editar | editar código-fonte]

O inverso de uma relação transitiva é sempre transitivo: por exemplo, sabendo que "é um subconjunto de" é transitiva e "é um superconjunto de" é o inverso, pode-se concluir que o último é transitiva.

A intersecção de duas relações transitivas é sempre transitivo: sabendo que "nasceu antes" e "tem o mesmo primeiro nome como" são transitórias, podemos concluir que "nasceu antes e também tem o mesmo primeiro nome que" é também transitória.

A união de duas relações transitivas não é sempre transitória. Por exemplo, "nasceu antes ou tem o mesmo primeiro nome como" geralmente não é uma relação transitiva.

O complemento de uma relação transitiva não é sempre transitória. Por exemplo, enquanto "igual a" é transitiva, "não é igual a" é apenas transitória em conjuntos com mais de um elemento.

Outras propriedades[editar | editar código-fonte]

Uma relação transitiva é assimétrica , se e somente se ela é Relação reflexiva.

Propriedades que necessitam de transitividade[editar | editar código-fonte]

Contagem de relações transitivas[editar | editar código-fonte]

Nenhuma fórmula geral que conta o número de relações transitivas em um conjunto finito (sequência A006905 na OEIS) é conhecido.[1] No entanto, não existe uma fórmula para achar o número de relações que são, simultaneamente, reflexiva, simétrica e transitiva – em outras palavras, relações de equivalência – (sequência A000110 na OEIS), aqueles que são simétricas e transitivas, aqueles que são simétricas, transitivas, e anti simétrica, e aqueles que são total, transitória, e anti simétrica. Pfeiffer[2] tem feito alguns progressos neste sentido, expressando relações com combinações dessas propriedades em termos de cada um dos outros, mas ainda calcular é bastante difícil. Consulte também.[3]

Veja também[editar | editar código-fonte]

Fontes[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Steven R. Finch, "Relações transitivas, topologias e ordens parcias", 2003.
  2. Götz Pfeiffer, "Contagem de Relações Transitivas", Journal of Integer Sequências, Vol. 7 (2004), o Artigo 04.3.2.
  3. Gunnar Brinkmann e Brendan D. McKay,"Contagem sem marcações da topologia e relações transitivas"

Bibliografia[editar | editar código-fonte]

Links externos[editar | editar código-fonte]