Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The generalize rule for a transitive relation is

a -> b
b -> c
therefor
a -> c

If an element has less than 3 elements, can it still be transitive? If so, does that provide any useful information?

share|improve this question
    
The empty set has any property you want. –  Austin Mohr Dec 21 '12 at 18:29
    
@AustinMohr What if I want it to have the negation of the property that you want it to have? –  Trevor Wilson Dec 22 '12 at 19:19
    
@Austin: Is the empty set a reflexive relation? –  Asaf Karagila Dec 22 '12 at 19:46
    
@AsafKaragila I would say yes on the grounds that one cannot produce a counterexample to reflexivity, but I am all too ready to defer to your expertise. –  Austin Mohr Dec 22 '12 at 21:00
1  
@Austin: Well, that was a trick question actually. Reflexivity is an external property, it refers to a set which is external to the relation. This is in contrast to transitivity and symmetry which are internal properties of a relation, which only refer to what sort of ordered pairs are members of the relation. We say that $R$ is a reflexive relation on $A$ if $(1) R\subseteq A\times A$; and $(2)\forall a\in A:\langle a,a\rangle\in R$. So if $\varnothing$ is considered a relation over the empty set it is indeed reflexive, but over any other set - it's not a reflexive relation. –  Asaf Karagila Dec 22 '12 at 21:02

2 Answers 2

up vote 10 down vote accepted

The general rule for a relation $\;\sim\;$ to be a transitive relation on a set $S$, we must have that for all $a, b, c \in S$, with $a, b, c$ NOT NECESSARILY DISTINCT:

  • IF $\;a \sim b\;$ AND IF $\;b \sim c,$
  • THEN we MUST have that $a \sim c$

If there happens to be less than three elements, then provided reflexivity holds for all $a \in S$, and symmetry holds for all $a, b \in S$, then transitivity follows.

Say we have the relation $R$ denoted by $\sim$ on the set $\{a, b\}$.$\,\,\,$

Then provided $a \sim a$, $b \sim b$, $a \sim b$ AND $b \sim a$, so that $R =\{(a, a),(b, b), (a, b), (b, a)\}$, then $R$ is reflexive, and symmetric, and must therefore be transitive, given there are only two elements.

If $S = \{a\}$, then any relation that is reflexive, i.e. any relation for which $R = \{(a, a)\}$ happens also to be (trivially) symmetric and transitive.


The only time transitivity fails is when there exists a, b, c such that

$a \sim b$ and $b \sim c$, BUT NOT $a \sim c$.

Sometimes it's easier to understand that a relation is transitive, UNLESS there exists a counterexample as described immediately above.

share|improve this answer
    
Say we have the relation R on the set {a,b}. Then provided aRa, bRb, aRb AND bRa, so that R{(a,a),(b,b),(a,b),(b,a)}, then R is reflexive, and symmetric, and must therefore be transitive, given there are only two elements. This is what really clarified it for me! Thanks! –  Christopher Lates Dec 21 '12 at 18:59
    
+ $$$$$$$$$$$$+ –  B. S. Feb 2 '13 at 6:26

Yes, and yes, respectively. For example, the relation $\{(a,b),(b,a)\}$ is not transitive; its transitive closure is $\{(a,a),(a,b),(b,a),(b,b)\}$. So the useful information you get from knowing that you have a transitive relation containing $(a,b)$ and $(b,a)$ is that you must also have $(a,a)$ and $(b,b)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.