10
$\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$
  • $\begingroup$ The empty set has any property you want. $\endgroup$ – Austin Mohr Dec 21 '12 at 18:29
  • $\begingroup$ @AustinMohr What if I want it to have the negation of the property that you want it to have? $\endgroup$ – Trevor Wilson Dec 22 '12 at 19:19
  • $\begingroup$ @Austin: Is the empty set a reflexive relation? $\endgroup$ – Asaf Karagila Dec 22 '12 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$ – Austin Mohr Dec 22 '12 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 Dec 22 '12 at 21:02
14
$\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$
  • $\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$ – Christopher Lates Dec 21 '12 at 18:59
6
$\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$
0
$\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
    $\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 Oct 11 '14 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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