# binary relations

• Dec 15th 2007, 11:34 AM
ff4930
binary relations
Consider the following four relations on the set {1,2,3}
R1 = {(1,1), (1,3), (2,2), (3,1)}
R2 = {(1,1), (2,2), (3,1), (3,3)}
R3 = {(1,2), (2,1), (3,3)}
R4 = {(1,3),(2,3)}

Which one's are transitive? Im not getting the idea behind it.
Is if A,B and B,A then A,C

R2 and R4 is transitive in the book but I do not see why.
Isn't R1 transitive? the book says no.
(1,3) = A,B (3,1) = B,C then (1,1) = A,C?? Please explain. Thanks in advance.
• Dec 15th 2007, 12:54 PM
Jhevon
Quote:

Originally Posted by ff4930
Consider the following four relations on the set {1,2,3}
R1 = {(1,1), (1,3), (2,2), (3,1)}
R2 = {(1,1), (2,2), (3,1), (3,3)}
R3 = {(1,2), (2,1), (3,3)}
R4 = {(1,3),(2,3)}

Which one's are transitive? Im not getting the idea behind it.
Is if A,B and B,A then A,C

no, let A = {1,2,3}. we say a relation R on A is transitive when for all $\displaystyle a,b,c \in A$, if $\displaystyle aRb$ and $\displaystyle bRc$ then $\displaystyle aRc$

you must check EVERY such pair in the relation and show that the implication holds. (note that an implication is true if the first statement is false, the empty set is transitive for instance, because it fulfils the conditions of transitivity vacuously)

Quote:

R2 and R4 is transitive in the book but I do not see why.
like i said, check every such pair where you have $\displaystyle aRb$ and $\displaystyle bRc$, (and note that a can equal c, and you can also have a = b = c)

Quote:

Isn't R1 transitive? the book says no.
(1,3) = A,B (3,1) = B,C then (1,1) = A,C?? Please explain. Thanks in advance.
no it is not. here's one pair that doesn't work:

we have (3,1) and (1,3) but there is no (3,3)
• Dec 15th 2007, 12:56 PM
Plato
Quote:

Originally Posted by ff4930
Consider the following four relations on the set {1,2,3}
R1 = {(1,1), (1,3), (2,2), (3,1)}
R2 = {(1,1), (2,2), (3,1), (3,3)}
R3 = {(1,2), (2,1), (3,3)}
R4 = {(1,3),(2,3)}
Isn't R1 transitive? the book says no.

R3 is not transitive because (1,2) & (2,1) but no (1,1).

Here a way of thinking about it.
If you have (g,f) & (f,g) you must have (g,g).
If you have (x,y) & (y,z) you must have (x,z).
If you have (h,_) & (_,j) you must have (h,j) if the blanks match.
If you have (h,k) & (j,h) you must have (j,k) because we really have (j,h) & (h,k) where h is in the blank.