Mostrar código-fonte de Relação transitiva

{{ver desambig|outros significados de transitividade|Transitividade}}
Na [[matemática]], '''relação transitiva''' é a que se estabelece entre três [[Elemento (matemática)|elementos]] de um mesmo [[Conjunto (matemática)|conjunto]] de tal forma que se o primeiro tem [[Relação (matemática)|relação]] com o segundo e este tem relação com um terceiro, então o primeiro elemento tem relação com o terceiro.<ref>[http://educadi.psico.ufrgs.br/cursos/ppg/textos/txlaurete1.html Relações. Universidade Federal do Rio Grande do Sul.]</ref>

Se tomarmos <math>A</math> um conjunto, e <math>R</math> uma endorrelação de <math>A</math>, (ou seja, <math>R \subseteq A \times A</math>, dizemos que <math>R</math> é transitiva se satisfazer a seguinte condição: <math>(\forall a \in A)(\forall b \in A)(\forall c \in A)</math>, se <math>(a,b) \in R \wedge (b,c) \in R \Longrightarrow (a,c) \in R</math>

Em termos de [[teoria dos conjuntos]], a relação transitiva pode ser definido como uma [[relação binária]] <math>R</math> sobre um [[conjunto]] <math>X</math> é transitiva se, sempre que um elemento de <math>a</math> está relacionado a um elemento de <math>b</math>, e <math>b</math> é relacionado a um elemento de <math>c</math>, então <math>a</math> também está relacionado com <math>c</math>. A transitividade é uma propriedade chave de ambos os [[conjunto parcialmente ordenado]] e de [[Relação de equivalência|relações de equivalência]].

Por exemplo, "é maior que", é pelo menos tão grande quanto " e "é igual a" ([[Igualdade matemática|igualdade]]) são relações transitivas:
* sempre que <math>A > B</math> e <math>B > C</math>, então a também <math>A > C</math>
* sempre que <math>A \ge B</math> e <math>B \ge C</math>, então a também <math>A \ge C</math>
* sempre que <math>A = B</math> e <math>B = C</math>, então a também <math>A = C</math>.
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 [[matrilinearidade]] ancestral". Esta ''é'' uma relação transitiva. Mais precisamente, é o [[Fecho transitivo|fechamento transitivo]] da relação "é a mãe".

Mais exemplos de relações transitivas são "é um [[subconjunto]] de" (conjunto de inclusão); "divide" ([[Divisor|divisibilidade]]); "implica" ([[Condicional material|implicação]]).

== Propriedades ==
=== Fechamento de propriedades ===
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 ===
Uma relação transitiva é assimétrica , se e somente se ela é [[relação reflexiva]].

=== Propriedades que necessitam de transitividade ===
* [[Pré-ordem]] — [[relação reflexiva]] e relação transitiva
* [[Conjunto parcialmente ordenado|Ordem parcial]] — uma [[relação antissimétrica]] pré-ordem
* Total pré-ordem — uma [[relação total]] de pré-ordem
* [[Relação de equivalência|Equivalência]] — uma relação simétrica pré-ordem
* Ordem fraca — uma ordem restrita parcialmente incompatível é uma relação de equivalência
* [[Relação de ordem|Total ordenação]] — uma [[relação total]], [[relação antissimétrica]], relação transitiva

== Contagem ==
Nenhuma fórmula geral que conta o número de relações transitivas em um conjunto finito {{OEIS|id=A006905}} é conhecido.<ref>Steven R. Finch, [http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf "Relações transitivas, topologias e ordens parcias"] {{Wayback|url=http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf |date=20160304111410 }}, 2003.</ref> 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ção de equivalência|relações de equivalência]] – {{OEIS|id=A000110}}, 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<ref>Götz Pfeiffer, "[http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html Contagem de Relações Transitivas]", ''Journal of Integer Sequências'', Vol. 7 (2004), o Artigo 04.3.2.</ref> 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.<ref>Gunnar Brinkmann e Brendan D. McKay,"[http://cs.anu.edu.au/~bdm/papers/topologies.pdf Contagem sem marcações da topologia e relações transitivas]"</ref>

{{Referências}}

== Bibliografia ==
* Ralph P. Grimaldi, ''Matemática Combinatória e Discreta'', {{ISBN|0-201-19912-2}}.
* Gunther Schmidt, 2010. ''Matemática Relacional''. Cambridge University Press, {{ISBN|978-0-521-76268-7}}.
* GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação. 3ª. edição. Editora LTC. Rio de Janeiro, 1995.
* ROSS, K. A. & WRIGHT, C. R. B.. Matemáticas Discretas. 2ª. edição. Editora. Prentice-Hall Hispanoamericana, S.A. México, 1990.

== Ligações externas ==
* {{SpringerEOM|titulo=Transitivity|id=p/t093810}}
* {{Link|en|2=http://www.cut-the-knot.org/triangle/remarkable.shtml |3=A transitividade em Ação |4=no [[Cut-the-Knot|corte-a-nó]]}}

{{Portal3|Matemática}}

[[Categoria:Teoria dos conjuntos]]