Relation on a set containing another relation

[rooski]

Homework Statement

Let A = { 2,3,5,10,15 } and R be {(2,10),(5,10),(3,15),(5,15)}

find the smallest equivalence on A containing R

find the smallest total order on A containing R

The Attempt at a Solution

so firstly i must show that my new relation containing R is reflexive. That means for every value a in A, aRa needs to exist. So i add (2,2),(3,3), etc. to my new relation. Then i show it is symmetric so i must add (10,2),(15,3),(10,5),(15,5) to my new relation.

To show it is transitive i add (2,5), (3,5), (5,2), (5,3) .

BUT: Once i have added those last 4 pairs, can i use them in determining whether i need to add (15,2) to my new relation? Or can i only use pre-existing parts of the relation that i didn't compute just now? Basically what is going to happen is every value a in A is going to point to every value a in A if i do it the way i am doing it now. Seems wrong to me.

 

[micromass]

I think you're doing the correct thing here.

So initially, your R is {(2,10),(5,10),(3,15),(5,15)}
To make it reflexive, R becomes {(2,2),(3,3),(5,5),(10,10),(15,15),(2,10),(5,10),(3,15),(5,15)}
To make it symmetric, R becomes {(2,2),(3,3),(5,5),(10,10),(15,15),(2,10),(10,2),(5,10),(10,5),(3,15),(15,3),(5,15),(15,5)}

Unlike the previous modifications, it is in general not possible to make R transitive in one step. You'll need more steps.
The first step would be to add (2,5), (5,2), (3,5), (5,3), (10,15), (15,10).
But this would still not be transitive, in a second step, you'll need to add (2,10), (10,2) and still some other values...
Keep doing that until your relation is transitive...

It is very possible that you'll end up with R=AxA...

 

[rooski]

It is very possible that you'll end up with R=AxA...

Thanks for the help. Yeah, i ended up with R = AxA.

For question b i need my new relation to be reflexive, transitive and antisymmetric. It also needs totality (any 2 values in A will be somehow related).

So i start the same as i did in a, then show it is antisymmetric... But since there are no cases where i can show antisymmetry (or transitivity) then am i finished?

 

[micromass]

Could you describe the process that you performed in b? It's a little hard to see what you mean...

 

[rooski]

Take the initial relation R and add (2,2),(3,3)... etc. for all values of A. This makes it reflexive.

Then you must turn this relation into an antisymmetric and transitive relation. Since there are no cases where aRb ^ bRc then there really are no steps to take as far as transitivity and antisymmetry go.

But for it to be a total order set then for every value a and b in A there must be some sort of relation aRb. Take for example, 2 and 15. There is no relation between them and hence my relation is not total order. So i did something wrong with transitivity/antisymmetry i guess.

 

[micromass]

No, you did nothing wrong. What you did is correct.

The relation R is indeed a partial order. But it is not yet a total order. Thus you must add enough relations to make it a total order... There might not always be a unique way to do this, but in this case, I think there is...

 

[rooski]

No, you did nothing wrong. What you did is correct.

The relation R is indeed a partial order. But it is not yet a total order. Thus you must add enough relations to make it a total order... There might not always be a unique way to do this, but in this case, I think there is...

So i need to ensure that for every value in A there exists a relationship between it and every other value in A. So for 2 i need 2R3 or 3R2 to exist. But if 2R3 exists then 2R3 and 3R15 implies that 2 = 15. Which means it's not antisymmetric.

If 3R2 then this implies 3 = 10 which again is wrong. There must be some huge concept i am missing here.

 

[micromass]

Wow, I can't follow anymore...

Why does 2R3 and 3R15 imply that 3=15?? To me, it only says that 2R15 (by transitivity)...

 

[rooski]

Wow, I can't follow anymore...

Why does 2R3 and 3R15 imply that 3=15?? To me, it only says that 2R15 (by transitivity)...

In order for it to be total order, the relation must be reflexive (which we proved already), transitive, and antisymmetric. For any 2 values in A there must exist a relation between them in my relation as well.

Antisymmetry means that if aRb and bRc then a = c. So if 2R3 and 3R15 that means 2 must be equal to 15. Which it is not... So i can't possibly have a total order relation, can i?

edit: Oh crap. That isn't antisymmetry.

Antisymmetry means that if aRb and bRa then a = b. D'oh!

Since there are no cases where aRb and bRa then i just need to be careful not to create any cases where it might break the rules of antisymmetry right? But i cannot create any relationships between 3 and 2 without either causing problems with transitivity or antisymmetry. :(

 

[micromass]

Antisymmetry means that if aRb and bRc then a = c.

No, this is not what antisymmetry says. Antisymmetry means that aRb and bRa then a=b.

 

[rooski]

No matter how many times i try to make it transitive i can't seem to do it without breaking the rule of antisymmetry. Is there a method i should use?

 

[micromass]

No matter how many times i try to make it transitive i can't seem to do it without breaking the rule of antisymmetry. Is there a method i should use?

I don't understand...
You can easily add (2,5) to your relation, can't you?

 

[rooski]

Yes, but my goal is to make a relation that is total order (that is, every value is somehow related to every other value.

Problem is, eventually i get a case where i need to make sure my relation is transitive which forces me to make some connections which cause the rule of antisymmetry to be broken.

Starting with 2, we note that 2 needs to relate to 3, 5 and 15. So without problems we add 2R5, 2R15 and 2R3.

Next, 3 must relate to 5 and 10. We add 3R10 and 3R5.

Next, we add 10R15.

Wait, did i just solve it?

 

[micromass]

Yes, you just solved it...