Binary Relations and Transitivity: Finding the Transitive Closure

[mr_coffee]

Binary Relations--Transitivity

Hello everyone I'm not sure if I'm hitting all the ordered pairs on this because i can't seem to find a good method to figure it out. I also think the relation to itself is confusing me.

here is the question:
S is a binary relation defined on A = {0,1,2,3}

to speed up this message, I'm going to represent an ordered pair like 00 instead of (0,0).

Let S = {00, 03, 10, 12, 20, 32}

Find S^t, the transititve closure of S.
note: ... 32 .. stands for (3,2), etc


Okay i know for somthing to be transitive, if you have an arrow from point 0 to 0, then it has a relation to itself..
Also
If i had say a relation like (0,1) and (1,2) then I can make an ordered pair from (0,2).
Thats what I'm doing in this problem


So i got the following but I'm not sure if I'm right.
S^t = S UNION { 11, 33, 22, 30, 01, 02 13, 31}


Thanks.

 

[HallsofIvy]

Hello everyone I'm not sure if I'm hitting all the ordered pairs on this because i can't seem to find a good method to figure it out. I also think the relation to itself is confusing me.

here is the question:
S is a binary relation defined on A = {0,1,2,3}

to speed up this message, I'm going to represent an ordered pair like 00 instead of (0,0).

Let S = {00, 03, 10, 12, 20, 32}

Find S^t, the transititve closure of S.
note: ... 32 .. stands for (3,2), etc


Okay i know for somthing to be transitive, if you have an arrow from point 0 to 0, then it has a relation to itself..
Also
If i had say a relation like (0,1) and (1,2) then I can make an ordered pair from (0,2).
Thats what I'm doing in this problem


So i got the following but I'm not sure if I'm right.
S^t = S UNION { 11, 33, 22, 30, 01, 02 13, 31}


Thanks.

It's not a question of if you have "missed" any- you have far too many pairs in there. "Transitive" does NOT imply "reflexive"! If ab and bc are in S then ac would have to be in S^t in order for S^t to be a transitive extension of S. In order that it be the smallest such, we would have to have ac in S^t only if ab and bc are in S for some b. Okay, in order for 11 to be in S^t that would mean we must have 1b and b1 in S for some b. I see 10 but I see no "b1" for any b! Similarly, in order that 33 be in S^t, we must have 3a and a3 in S for some a. We have 32, but no 23, we have 03 but no 30. In order that 22 be in S^t, we must have 2a and a2 in S for some a. I see 12 but no 21 and I see 20 but no 02.

Her's how I would do the problem. First, do you see that we can ignore "doubles" like 00? If we also have 0a, "transitivity" tells us we must also have 0a which is obviously in the set. Starting from the left, I see 03. The only pair of the form 3a is 32 so "transitivity" says we must also have 02. Next is 10. The only pair of the form 0a is is 00 so we must have 10 which is already in the set. Next is 12. The only pair of the form 2a is 20 so we must have 10 which is already in the set. Next is 20. The only pair of the form 0a is 00 so we must have 20 which is in the set (again, 00 is a "double"). Finally, we have 32. The only pair in the set of the form 2a is 20 so we must have 30. That is, the transitive closure of S is S union {02, 30}= {00, 03, 10, 12, 20, 32, 02, 30}.

 

[mr_coffee]

Ivy,

Thanks so much! that helps a lot, I was drawing pictures and it was just very time consuming and confusing but this is a lot easier.