# Binary Relations

1. Nov 8, 2009

### hansel13

1. The problem statement, all variables and given/known data
T is a binary relation defined on A = {0, 1, 2, 3}.

Let T = {(0,2), (1,0), (2,3), (3,1)}

Find T^t, the transitive closure of T.

3. The attempt at a solution
I'm gonna skip using commas cause it takes to long

02 23 = 03
31 10 = 30
23 31 = 21
10 02 = 12
12 23 = 13
02 21 = 01
23 30 = 20
31 12 = 32

So, T^t = {(0,2), (1,0), (2,3), (3,1), (0,3), (3,0), (2,1), (1,2), (1,3), (0,1), (2,0), (3,2)}

Pretty sure this is right, if someone could let me know if I did anything wrong, I'd appreciate it.

2. Nov 8, 2009

### tiny-tim

Hi hansel13!

(try using the X2 tag just above the Reply box )

Hint: how many pairs are there in A? And how many are there in Tt?

3. Nov 8, 2009

### hansel13

4 pairs in A. So 8 in Tt? I still fail to follow...

4. Nov 8, 2009

### lanedance

i dont totally understand the question, but looking at your equivalence realtion, along with Tiny Tim's comments:

first, there's more than 4 pairs that can be made from A, & more than 8 in T^t

Let T = {(0,2), (1,0), (2,3), (3,1)}
then the way i read it, following through T gives: 0~2~3~1, so everything is equivalant in the transitive closure (ie contains all binary pairs)...?

5. Nov 9, 2009

### tiny-tim

uhh? you found 12 in Tt.

And A has 4 elements, so how many different pairs of elements are there (counting, for example, {0,3} and {3,0} as the same pair).

(if you can't calculate it, then just list them )

6. Nov 10, 2009

### hansel13

Sorry, meant 12 elements in Tt

I still don't follow. Why would {0,3} and {3,0} be the same?

OK By defintion:
The transitive closure of T is the binary relation Tt on A that satisfies the following three properties:
1. Tt is transitive.
2. T is a subset of Tt.
3. If S is any other transitive relation that contains T, then Tt is a subset of S.

So doesn't T^t = {(0,2), (1,0), (2,3), (3,1), (0,3), (3,0), (2,1), (1,2), (1,3), (0,1), (2,0), (3,2)}?

7. Nov 10, 2009

### lanedance

if T is a symmetric binary relation then it satisfies
a~b iff b~a
so in that case (0,3) = (3,0)

8. Nov 10, 2009

### tiny-tim

What about (0,0), (1,1), (2,2) and (3,3)?

(remember, a relation can be something like "=")
Sorry, I shouldn't have added that …

when you didn't answer my original question, I got confused and thought this was defined as a symmetric relation (which it wasn't).

Let's start again …

How many elements are there in Tt? And how many in A x A?

9. Nov 10, 2009

### hansel13

Well I thought there are 12 elements in Tt. And 16 in A x A.

But I guess if we add (0,0),(1,1),(2,2),(3,3) then Tt would have 16 elements as well?

10. Nov 12, 2009

### hansel13

So there are 16 elements in Tt?

11. Nov 12, 2009

### tiny-tim

Yup!

So Tt is the whole of AxA …

now can you see a way of proving that, quicker than just listing all the elements?

12. Nov 13, 2009

### hansel13

I guess since there's 4 pairs in T^t and 4 pairs in A, we'd need 16 pairs to have full closure.

thanks