Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The generalize rule for a transitive relation is

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

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

share|cite|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
@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
up vote 12 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|cite|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

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|cite|improve this answer

It may or may not be transitive. It depends on the set and the relation. eg 1: Let S={} then R={} and it is trivially transitive. eg 2: Let S={a} then there are two relations R1={}, R2={(a,a)} and both are transitive trivially. eg 3: Let S={a,b} then there are 16 relations R1={} --> Transitive R2={(a,a)} --> Transitive R3={(b,b)} --> Transitive -------- -------- R6={(a,a),(a,b)} --> Transitive R7={(a,b),(b,a)} --> Not Transitive

and so on.

share|cite|improve this answer
Welcome to Math.SE. Just to let you know: if you enclose Latex commands in dollar signs, they will display the maths properly, making you answer more readable. – Jessica B Oct 11 '14 at 8:06

Your Answer


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.