Restore indirect relations within a transitive relation

mm84010
Messages
4
Reaction score
0
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?

Thanks in advance.
 
Physics news on Phys.org
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?
 
  • Like
Likes 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.
 
Namaste & G'day Postulate: A strongly-knit team wins on average over a less knit one Fundamentals: - Two teams face off with 4 players each - A polo team consists of players that each have assigned to them a measure of their ability (called a "Handicap" - 10 is highest, -2 lowest) I attempted to measure close-knitness of a team in terms of standard deviation (SD) of handicaps of the players. Failure: It turns out that, more often than, a team with a higher SD wins. In my language, that...
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...

Similar threads

Back
Top