Construct All Transitive Relations on A={1,2,3}: Tips for Students

[CartoonKid]

My lecturer asked our class to construct all transitive relations on A={1,2,3}. Is there a brilliant way to do this? Because number of subsets is too big for us to list out one by one. Thanks.

 

[matt grime]

The number of subsets if {1,2,3} is 8. That is not too many to list.

 

[e(ho0n3]

Yes, but the total number of relations on {1,2,3} is 64. Surely you find checking 64 relations a time-consuming task.

 

[CartoonKid]

sorry, should be the number of relations.

 

[matt grime]

since there are only three elements it is still doable since we only care about transitive ones, and we can exploit symmetry.

suppose 1 is not related to any of 1,2,3, then we need only classify those trans relations on 2,3

then suppose 1R2, and doesn't relate to 3.

then suppose 1R2 and 1R3

now i could have picked anything apart from 1, so acutally by symmetry you've got them all.

 

[shmoe]

There's more than 64,. Relations are exactly the subsets of the cartesian cross product AXA, which has 9 members, so 2^9=512 subsets.

Matt's suggestion of using symmetry is the way to go. It shouldn't be too time consuming wth only 3 elements.

 

[CartoonKid]

Thanks for the suggestion. I'm having problem understanding this transitive relation.

Here are some examples in my lecture notes:

Let A={1,2,3}. Let

R={(1,1),(1,2),(2,1),(2,2)}
S={(1,1),(2,2),(3,3),(1,2)}
T={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)}

Given the above relations, then
R is symmetric and transitive
S is reflexive and transitive
T is reflexive and symmetric

I know how to see symmetric and reflexive. But I don't know how to figure out which one is transitive. Why T is not transitive? It has all the elements of R, but it is not transitive as R is. My lecturer told us that because (1,2),(2,1) in T are not transitive? Can somebody please explain it to me. I am new to this relation topic. Thanks a thousand.

 

[TenaliRaman]

Well T is not transitive but i don't really understand ur lecturer's clarification ...

Why is T not transitive?
we have (1,2) in the set
we also have (2,3) in the set
but do we have (1,3) ??

-- AI

 

[CartoonKid]

Thanks Tenali again.

 

[CartoonKid]

Here are the transitive relations I got:

{(2,2)},{(2,3),(3,3)},{(2,2),(3,2)},{(2,2),(2,3)},{(3,2),(3,3)},{(2,2),(3,3),(2,3)},{(2,2),(3,3),(3,2)},{(2,2),(3,3)},{(2,2),(2,3),(3,2),(3,3)}

{(1,1)},{(3,3)},{(1,3),(3,3)},{(1,1),(3,1)},{(1,1),(1,3)},{(3,1),(3,3)},{(1,1),(3,3),(1,3)},{(1,1),(3,3),(3,1)},{(1,1),(3,3)},{(1,1),(1,3),(3,1),(3,3)}

{(2,1),(1,1)},{(2,2),(1,2)},{(2,2),(2,1)},{(1,2),(1,1)},{(2,2),(1,1),(2,1)},{(2,2),(1,1),(1,2)},{(2,2),(1,1)},{(2,2),(2,1),(1,2),(1,1)}

{(1,1),(2,2),(3,3)},{(1,2)},{(1,3)},{(2,1)},{(2,3)},{(3,1)},{(3,2)},{ }

Altogether I found 35 transitive relations. Is there anymore? I heard the total number is 171, is it?