9
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ The empty set has any property you want. $\endgroup$ Commented Dec 21, 2012 at 18:29
  • $\begingroup$ @AustinMohr What if I want it to have the negation of the property that you want it to have? $\endgroup$ Commented Dec 22, 2012 at 19:19
  • $\begingroup$ @Austin: Is the empty set a reflexive relation? $\endgroup$
    – Asaf Karagila
    Commented Dec 22, 2012 at 19:46
  • $\begingroup$ @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. $\endgroup$ Commented Dec 22, 2012 at 21:00
  • 2
    $\begingroup$ @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. $\endgroup$
    – Asaf Karagila
    Commented Dec 22, 2012 at 21:02

4 Answers 4

16
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Commented Dec 21, 2012 at 18:59
7
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

It may or may not be transitive. It depends on the set and the relation.

  1. Let S={} then R={} and it is trivially transitive.
  2. Let S={a} then there are two relations R1={}, R2={(a,a)} and both are transitive trivially.
  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.
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jessica B
    Commented Oct 11, 2014 at 8:06
0
$\begingroup$

Recall the definition of transitivity : for all x,y,z in a set A with the relation R, if xRy and yRz then xRz.

Now, if we have 2 elements, just think to yourself that our condition can't be met (unless you take 2 elements to be equal), and whenever the conditions of a property can't be met then we consider the property to hold.

Mathematically, it's not entirely correct (I get that) but it's a good way to understand it simply I find.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .