# Need newbie help on Relations

• Dec 8th 2007, 09:28 PM
Salle79
Need newbie help on Relations
I'm stuck on relations, more specific on how to determine if something is reflexive, symmetric, antisemmetric and transitive

I understand everyone but transitive, Yea, I've read and re-read the explanation (definition and i can come up with easy examples:

If (145)R(215) and (215)R(585) then (145)R(585)

What i don't get are how the examples and questions in the book can be transitive, if someone please could explain to me how in H*** these can be transitive, like point out the parts in bold and explain it to me like i'm a 3 year old would be great!

Here are the examples according to the book that are transitive:

--Example one---
A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)}

--Example two---
A={1,2,3,4}
R2 = {(1,1),(2,2),(3,3),(4,4),(1,2)}

Example three
A={1,2,3,4}
R2 = {(1,1),(2,2),(1,2),(2,1)}
• Dec 8th 2007, 09:46 PM
Jhevon
Quote:

Originally Posted by Salle79
--Example one---
A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)}

This is not transitive, since we have 3R2 and 2R3 but not 3R3

in short, here's what you need to know.

Implications are false only when the first statement is true and the second is false. that is, \$\displaystyle P \implies Q\$ is false ONLY if P is true and at the same time Q is false.

based on that, we can have something being transitive "vacuously"

e.g. the empty set is vacuously transitive. but you might say, how can that be, there are no elements to relate to the definition. but that is exactly it, that would mean we have no two element to compare for the statement "If aRb and bRc", so the first statement of the implication is false, and so the whole implication "if aRb and bRc then aRc" is true

another thing you need to note is that you can reuse elements. for instance, the relation defined by R = {(1,1)} IS transitive. How? we have 1R1 and 1R1 implies 1R1. which clearly conforms to our definition.

so look at the relations again and check if they conform to the definition
• Dec 8th 2007, 10:17 PM
Salle79
Okay, so my book has an typ then and it should say:

A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)(3,3)}

A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)}

So, the relation {(1,1)} by itself is transitive?

since we have (3R2) and (2R3) this makes (3R3) transitive?
• Dec 8th 2007, 10:24 PM
Jhevon
Quote:

Originally Posted by Salle79
Okay, so my book has an typ then and it should say:

A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)(3,3)}

A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)}

i spotted that (3,3) was missing on a whim, but there might be something else wrong. have you checked?

Quote:

So, the relation {(1,1)} by itself is transitive?
yes

Quote:

since we have (3R2) and (2R3) this makes (3R3) transitive?
no. we need to show that this happens for EVERY two pairs where the second element of the first pair is the same as the first element of the second pair. so just verifying transitivity for 3R2 and 2R3 is not enough. you must do it for every pair aRb and bRc (and remember, a and c can be the same thing, and so can b be the same as a and c)

and we do not say a single element is transitive, so it is wrong to say that "makes (3,3) transitive". when we use the term transitive, we are talking about the whole relation
• Dec 8th 2007, 10:38 PM
Salle79
Okay, I think i understand now.

A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)(3,3)}

since elements can be re-used (1R1) (2R2) and 3R3) are given.
(2R2) and (1R2) gives (2R2)
(3R2) and (2R3) gives (3R3)
(1R3) and (3R2) gives (1R2)

and thus the entire relation is transitive!

right/wrong?
• Dec 8th 2007, 11:00 PM
Jhevon
Quote:

Originally Posted by Salle79
Okay, I think i understand now.

A ={1,2,3}
R1 = {(1,1),(1,2),(1,3),(2,2),(2,3)(3,2)(3,3)}

since elements can be re-used (1R1) (2R2) and 3R3) are given.
(2R2) and (1R2) gives (2R2)
(3R2) and (2R3) gives (3R3)
(1R3) and (3R2) gives (1R2)

and thus the entire relation is transitive!

right/wrong?

you did not check what 1R1 and 1R2 gives...

or what 1R1 and 1R3 gives...

or what 1R2 and 2R2 gives...

or what 1R2 and 2R3 gives...

or what 1R3 and 3R3 gives...

or what 2R2 and 2R3 gives...

or what 2R3 and 3R2 gives...

or what 2R3 and 3R3 gives...

or what 3R2 and 2R2 gives...

or what 3R3 and 3R2 gives...

when i said check EVERY pair, i literally meant EVERY pair. otherwise, you have not proven anything
• Dec 8th 2007, 11:08 PM
Salle79
Great. I understand now, thnx!