Binary Relations and Transitivity: Finding the Transitive Closure

  • Thread starter mr_coffee
  • Start date
  • Tags
    Binary
In summary, the binary relation S is defined on a set A = {0,1,2,3}. The relation is represented by ordered pairs, and the question is to find the transitive closure of S. Transitivity means that if ab and bc are in S, then ac must be in the transitive closure of S. The smallest transitive extension of S includes pairs from S as well as additional pairs that follow the transitive rule. In this problem, we can ignore "doubles" like 00 and focus on pairs like 03 and 32. By following the transitive rule, we can find that the transitive closure of S is S union {02, 30} which includes pairs like 03,
  • #1
mr_coffee
1,629
1
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.
 
Physics news on Phys.org
  • #2
mr_coffee said:
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}.
 
  • #3
Ivy,

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

Related to Binary Relations and Transitivity: Finding the Transitive Closure

What is transitivity in binary relations?

Transitivity in binary relations refers to the property 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, a transitive relation means that if there is a connection between two elements, there is also a connection between any other elements that are related to those two elements.

How is transitivity represented in a binary relation?

Transitivity is represented in a binary relation by using a directed graph. In this graph, the elements are represented as vertices, and the relation between the elements is represented as edges. If the relation is transitive, there will be a path from one element to another through the intermediate elements.

What is an example of a transitive binary relation?

An example of a transitive binary relation is the "is a subset of" relation. If set A is a subset of set B, and set B is a subset of set C, then set A is also a subset of set C. This relation follows the transitive property as the elements (sets) are related to each other in a chain-like manner.

What are the benefits of transitivity in binary relations?

The benefits of transitivity in binary relations include simplifying complex relationships between elements, allowing for efficient data retrieval and processing, and aiding in the understanding and analysis of data. Additionally, transitivity can help in identifying patterns and predicting future relationships between elements.

What are some real-life applications of transitive binary relations?

Transitive binary relations have various real-life applications, such as in social networks, where the "friend of a friend" relation follows the transitive property. In transportation systems, transitive relations can be used to determine the most efficient routes between destinations. In mathematics, transitive relations are essential in algebraic structures and in defining mathematical operations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
11
Views
3K
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
6K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
Replies
11
Views
2K
Back
Top