# Restore indirect relations within a transitive relation

• mm84010
In summary: I am not sure if I am the first one did this algorithm, I just did it because I need it and it is a very intuitive algorithm.I am not asking for a proof of my algorithm, but I am looking for a way to represent it in a mathematical formula or notation. In summary, the speaker is seeking help with deriving a formula in set theory to reflect an algorithm they have created. The algorithm is used to generate the smallest transitive relation containing a given finite set. The speaker is not asking for a proof of the algorithm, but rather a way to represent it in a formal mathematical notation.
mm84010
Hi,

I have a transitive relation and wana build a complete set of pairs that reflect all (direct/indirect) relations among the pairs.

Ex.: suppose I have this relation R = { (1,2), (2,3), (3,5), (5,7), (3,4) }

I wana to produce this relation R oper R = { (1,2), (1,3), (1,4), (1,5), (1,7), (2,3), (2,4), (2,5), (2,7), (3,4), (3,5), (3,7), (5,7) }

I tried to use the composite operator (°), but I got this R U (R ° R) = { (1,2), (2,3), (3,5), (5,7), (3,4), (1,3), (2,4), (2,5), (3,7) } which is not complete. In this case I need a loop operator until all pairs are restored.

Is there an operator that I can used to reflect that?

mm84010 said:
I have a transitive relation

Ex.: suppose I have this relation R = { (1,2), (2,3), (3,5), (5,7), (3,4) }

That isn't a transitive relation. How does this example illustrate your question?

Sorry, Math is not my suppject, but this is how I understand transitive relation:
if A > B and B > C then A > C.

In my example I have , e.g.,
- (1,2) = 1 > 2
- (2,3) = 2 > 3
which conclude that 1 > 3 ==or==> (1,3)

from this new pair I can create another two pairs
- (1,3)
- (3,5) & (3,4) from the relation
I can produce two new pairs (1,5) & (1,4)
an so on

In my research, I have two relations , based on partial order, build independently and I have to compare them.
suppose I have these two
R1 = { (1,2), (2,4) }
R2 = { (1,2), (2,4), (1,4) }
For me, they are equivalent. but How I can use math to prove my case. I am trying to generate/expand the total/all relations among the existing pairs.

Hi,

I am seeking help to derive my formula in set theory.

I will explain my request through the following example:

suppose I have this transitive relation R = { (1,2), (2,3), (3,5), (5,7), (3,4) }

I mean by transitive that since
(1,2) ==> 1 > 2, and
(2,3) ==> 2 > 3
then I can conclude that
1 > 3 or (1,3)
Hence, I can add this pair explicitly to R.

I wana to add all these implicit relations to reach the final relation:
R` = { (1,2), (1,3), (1,4), (1,5), (1,7), (2,3), (2,4), (2,5), (2,7), (3,4), (3,5), (3,7), (5,7) }

Currently, here are the steps I used to build my case

s1 = R ° R = { (1,3), (2,4), (2,5), (3,7) } // compsite operator

s2 = R U s1 = { (1,2), (2,3), (3,5), (5,7), (3,4), (1,3), (2,4), (2,5), (3,7) } // union operator

s1 = s2 ° R = { (1,3), (2,4), (2,5), (3,7), (1,5), (1,4), (2,7) }

s2 = s2 U s1 = { (1,2), (2,3), (3,5), (5,7), (3,4), (1,3), (2,4), (2,5), (3,7), (1,5), (1,4), (2,7) }

s1 = s2 ° R = { (1,3), (2,4), (2,5), (3,7), (1,5), (1,4), (2,7), (1,7) }

s2 = s2 U s1 = { (1,2), (2,3), (3,5), (5,7), (3,4), (1,3), (2,4), (2,5), (3,7), (1,5), (1,4), (2,7), (1,7) }

s1 = s2 ° R = { (1,3), (2,4), (2,5), (3,7), (1,5), (1,4), (2,7), (1,7) }

I stop when s1 produce the same previous relation, and my result is in s2.

I built a computer algorithm for that, but I want a math formula to report my work in formal way.

I don't know if there is an operator reflect the generation of all implicit indirect relations among the elements of set (I read three discrete math books and browsed several math pages), or there is a loop operator that reflect a recursiveness based on a condition (not number of occurrences).

Thanks for any hint,
Reference to papers/books/tutorials are appreciated

I think the correct statement statement of your question is:

If I am given a relation S as a finite set, what algorithm can be used to generate the smallest set R that is a transitive relation and that contains S as a subset?

You have proposed an algorithm. Are you asking for a proof that your algorithm terminates in a finite number of steps and that it produces the desired R?

1 person
Thanks Stephen,

I had implemented the algorithm and it works fine.

I am trying to put a nice formula in my report to reflect this algorithm.

## What is a transitive relation?

A transitive relation is a type of mathematical 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.

## How does indirect relation occur within a transitive relation?

Indirect relation within a transitive relation occurs when there is a chain of two or more related elements between two given elements. This means that there is at least one intermediary element that connects the two given elements.

## Why is it important to restore indirect relations within a transitive relation?

Restoring indirect relations within a transitive relation is important because it allows for a more comprehensive understanding of the relationship between elements. It can also help to identify any missing or incorrect information within the relation.

## What are some techniques for restoring indirect relations within a transitive relation?

One technique for restoring indirect relations within a transitive relation is to use a transitive closure algorithm, which identifies and adds any missing indirect relations between elements. Another technique is to manually analyze the transitive relation and identify any missing or incorrect indirect relations.

## Can indirect relations within a transitive relation change over time?

Yes, indirect relations within a transitive relation can change over time. This can occur when new elements are added to the relation or when existing elements are updated or deleted. It is important to regularly review and update transitive relations to ensure that all indirect relations are accurate and up-to-date.

• Linear and Abstract Algebra
Replies
3
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Precalculus Mathematics Homework Help
Replies
14
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
17
Views
10K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• General Math
Replies
20
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
57
Views
6K
• Programming and Computer Science
Replies
1
Views
3K
• Precalculus Mathematics Homework Help
Replies
6
Views
2K