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

  • Thread starter CartoonKid
  • Start date
  • Tags
    Relation
In summary, constructing all transitive relations on a set with 3 elements can be done by exploiting symmetry and considering subsets of the cartesian cross product. The total number of transitive relations is 35, which is much smaller than the total number of relations (171) on the set.
  • #1
CartoonKid
125
0
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.
 
Physics news on Phys.org
  • #2
The number of subsets if {1,2,3} is 8. That is not too many to list.
 
  • #3
Yes, but the total number of relations on {1,2,3} is 64. Surely you find checking 64 relations a time-consuming task.
 
  • #4
sorry, should be the number of relations.
 
Last edited:
  • #5
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.
 
  • #6
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.
 
  • #7
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.
 
  • #8
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
 
  • #9
Thanks Tenali again.
 
  • #10
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?
 
Last edited:

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

Q: What is a transitive relation?

A transitive relation is a mathematical concept that describes a relationship between three or more elements, where if element A is related to element B and element B is related to element C, then element A is also related to element C. In other words, if there is a logical connection between two elements, then there must also be a logical connection between all elements in the relationship.

Q: How do you construct all transitive relations on a given set?

To construct all transitive relations on a given set, you must first list out all possible pairs of elements within the set. Then, you can determine which pairs are related to each other and build the transitive relationships accordingly. It can be helpful to visualize the relationships using a diagram or chart.

Q: What is the purpose of constructing transitive relations on a set?

The purpose of constructing transitive relations on a set is to better understand the logical connections between different elements within the set. It can also help in solving problems or making predictions based on the given relationships.

Q: Are there any tips for constructing transitive relations on a set?

One tip for constructing transitive relations is to start by identifying any obvious relationships between elements in the set. Then, work through the remaining elements to see if any additional relationships can be formed. It can also be helpful to use visual aids or examples to better understand the concept.

Q: Can you give an example of constructing all transitive relations on a given set?

Yes, for the set A={1,2,3}, the possible pairs are (1,2), (1,3), and (2,3). Using these pairs, we can form the following transitive relationships: (1,2), (2,3), (1,3), (1,1), (2,2), (3,3), (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). This gives us all possible transitive relations on the set A={1,2,3}.

Similar threads

Replies
5
Views
3K
Replies
2
Views
1K
Replies
7
Views
196
Replies
2
Views
112
Replies
7
Views
2K
Replies
11
Views
1K
Back
Top