Transitive Closure of Binary Relation T on A={0,1,2,3}

[hansel13]

Homework Statement

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.

The Attempt at a Solution

I'm going to 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.

 

[tiny-tim]

Hi hansel13!

(try using the X² tag just above the Reply box )

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

You've made it really long.

Hint: how many pairs are there in A? And how many are there in T^t?

 

[hansel13]

Hi hansel13!

(try using the X² tag just above the Reply box )


You've made it really long.

Hint: how many pairs are there in A? And how many are there in T^t?

4 pairs in A. So 8 in T^t? I still fail to follow...

 

[lanedance]

i don't 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 equivalent in the transitive closure (ie contains all binary pairs)...?

 

[tiny-tim]

4 pairs in A. So 8 in T^t? I still fail to follow...

uhh? you found 12 in T^t.

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 )

 

[hansel13]

uhh? you found 12 in T^t.

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 )

Sorry, meant 12 elements in T^t

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 T^t on A that satisfies the following three properties:
1. T^t is transitive.
2. T is a subset of T^t.
3. If S is any other transitive relation that contains T, then T^t 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)}?

 

[lanedance]

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

 

[tiny-tim]

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)}?

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

(remember, a relation can be something like "=")

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

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 T^t? And how many in A x A?

 

[hansel13]

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 T^t? And how many in A x A?

Well I thought there are 12 elements in T^t. And 16 in A x A.

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

 

[hansel13]

So there are 16 elements in T^t?

 

[tiny-tim]

So there are 16 elements in T^t?

Yup!

So T^t is the whole of AxA …

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

 

[hansel13]

Yup!

So T^t is the whole of AxA …

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

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