1

enter image description here

My book says the answer is B. But how. I understand that the relation is reflexive as (a,a) belongs to R for all a belonging to the given set. Furthermore I understand that the relation is not reflexive as (a,b) belongs to R does not imply that (b,a) belongs to R for all a,b belonging to the given set. What I don't understand is how is the relation transitive ? I mean they have given (1,3) and (3,2) and (1,2) in the relation which makes it transitive for one case. But doesn't transitivity mean that (a,b) belongs to R and (b,c) belongs to R implies that (a,c) belongs to R for all a,b,c belonging to the given set. Isn't the for all violated here? In transitivity? So shouldn't it be not transitive ? Or am I missing something.

EDIT

My book's statement:

enter image description here

Kunal Pawar
  • 125

2 Answers2

1

For it not to be transitive, you need an a,b,c such that (a,b) and (b,c) are in R, but (a,c) is not (a,b,c need not be different). Are seeing any instance of this? Let's see. Here are all pairs of pairs (a,b) and (b,c) in R:

(1,1) and (1,1)

(1,1) and (1,2)

(1,1) and (1,3)

(1,2) and (2,2)

(2,2) and (2,2)

(3,2) and (2,2)

(1,3) and (3,2)

(3,3) and (3,2)

(1,3) and (3,3)

(3,3) and (3,3)

Now, let's see if the (a,c) pair is in R in all those cases as well:

(1,1) and (1,1) => (1,1) Yes!

(1,1) and (1,2) => (1,2) Yes!

(1,1) and (1,3) => (1,3) Yes!

(1,2) and (2,2) => (1,2) Yes!

(2,2) and (2,2) => (2,2) Yes!

(3,2) and (2,2) => (3,2) Yes!

(1,3) and (3,2) => (1,2) Yes!

(3,3) and (3,2) => (3,2) Yes!

(1,3) and (3,3) => (1,3) Yes!

(3,3) and (3,3) => (3,3) Yes!

Yes, they all are ... so it is transitive.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • But shouldn't it be transitive for the other elements of the set as well? There is a for all isn't there? I can see that it's not not transitive. But it isn't transitive for all.. – Kunal Pawar Mar 19 '17 at 16:50
  • 1
    Transitive says "if (a,b) and (b,c) in R, then (a,c) in R" ... if the if is not satisfied, then it's ok! So, for example, we have (1,3) in R but we don't have (3,4) in R ... So, we don't need (1,4) in R either. – Bram28 Mar 19 '17 at 16:52
  • @KunalPawar So which pair(s) do you think is/are missing? And by the way, if it's not not transitive, then it is transitive. – Bram28 Mar 19 '17 at 16:54
  • I think I'm confused on the for all statement :| – Kunal Pawar Mar 19 '17 at 16:54
  • The for all has led me to believe that every element in the set on which the relation is defined should have such a pair which shows transitivity. I'm still confused. I'll edit the question to show the statement my book has. – Kunal Pawar Mar 19 '17 at 16:56
  • OK. Transitivity indeed says for all a,b,c: if (a,b) and (b,c), then (a,c). OK, so for example take a=1,b=2, and c=3. Then we get if (1,2) and (2,3), then (1,3). Well, we have (1,2), but we don't have (2,3). So, we 're ok! Repeat this for all possible values of a,b,c. If the if part is not satisfied, then we're immediately ok. If it satisfied, then we have to make sure (a,c) is in R as well. – Bram28 Mar 19 '17 at 16:59
  • @KunalPawar So you're looking at (3,2), and say: shouldn't we have something like a (2,4) here as well, and thus also a (3,4), to make it transitive? No, that is not needed. Indeed, if (3,2) was the only pair in R, it would be perfectly transitive, exactly because there is no violation of transitivity. – Bram28 Mar 19 '17 at 17:02
  • So should the statement be for all a,b,c belonging to the set which occur as an ordered pair in the relation or something. – Kunal Pawar Mar 19 '17 at 17:02
  • Yes, you can read it as: for all two pairs (a,b) and (b,c) that occur in R, (a,c) must be in R as well. That way, you can avoid the pairs of pairs that don;t occur, and thus make the statement trivially true. OK: so let me ask you this: can you identify all pairs of pairs (a,b) and (b,c) that exist in R? (and again, a,b,c need not be different) – Bram28 Mar 19 '17 at 17:04
  • Yes I can. They're (1,3) and (3,2). Wait what.. a,b,c may not be different hmm. Then you're basically asking for all ordered pairs in the relation ? But they should be three different elements while proving (or disproving) transitivity ? – Kunal Pawar Mar 19 '17 at 17:07
  • Right, you also have (1,1) and (1,2), and even (1,1) and (1,1) ... and a bunch more ... I just added all of them to my Answer. But you're right: once a=b or b=c, then transitivity automatically holds for those pairs of pairs. So the only interesting one is indeed (1,3) and (3,2) – Bram28 Mar 19 '17 at 17:09
  • An intuitive way to think of transitivity is that IF you can get from one place to another in two steps, it is always possible to go directly in one step. So if you draw a map with towns {1,2,3,4} and streets that are the ordered pairs of the relation, you can see right away from the picture whether or not a relation is transitive. – Airymouse Mar 19 '17 at 18:55
1

Your book defines transitive to be, if (a implies b) and (b implies c) then (a implies c).

It seems easy to be confused from the fact that there is no such case in the relation where the above statement occurs. In this instance the proof of transitivity is known as the vacuous proof. Also known as a vacuous truth. This occurs when we have a statement If P-->then Q, when P is known to be false.

Take for example the statement,

----"All elephants you own have rainbow stripes",

Explanation: When it is known you own no elephants. This statement is still true.

A more practical example is given by the wikipedia article on "Vacuous truth", which states,

----For example, the statement "all cell phones in the room are turned off" will be true whenever there are no cell phones in the room. In this case, the statement "all cell phones in the room are turned on" would also be vacuously true, as would the conjunction of the two: "all cell phones in the room are turned on and turned off"."

In the case of the given relation. It is known we have no (a1,a2,) in R such that (a2,a1) is in R. So the transitivity is true.

Hope that helps(:

--Link to wikipedia article on vacuous truth https://en.wikipedia.org/wiki/Vacuous_truth

Inquirer107
  • 45