Find the composition of S with itself, as a relation on...

[stiffy]

Q: Consider the relation S=? on R (real numbers), namely xSy iff x?y (the usual "less or equal" relation). Find S o S, the composition of S with itself, as a relation R.

I don't really know how to approach this problem. But, here is what I think:

I’m trying to find xSySx. So, I need to find an intermediate y such that I end up back at x. Keeping in mind the relation is "less or equal" I can set up a set S where S is every possible relation such that x?y. Since we are dealing with the real number system and x must be equal or less than y, there are infinitely many y's that are greater than or equal to an infinite set of x's. So my set S = { (-?,-?),(?,?)}. So, S o S will give me back the same set, because for the equal to part of the relation S, I will get back the identity Relation ( (a,a),(b,b),...etc) which will give me the set S = { (-?,-?),(?,?)}. The less than part of relation S will also include all real numbers...(right?).

So,

S o S = { (-?,-?),(?,?)}
I don't really know if that relation I wrote above is correct or makes sense really.

Thank you for your help,

--Dan

 

[daon]

Q: Consider the relation S=? on R (real numbers), namely xSy iff x?y (the usual "less or equal" relation). Find S o S, the composition of S with itself, as a relation R.

I don't really know how to approach this problem. But, here is what I think:

I’m trying to find xSySx. So, I need to find an intermediate y such that I end up back at x. Keeping in mind the relation is "less or equal" I can set up a set S where S is every possible relation such that x?y. Since we are dealing with the real number system and x must be equal or less than y, there are infinitely many y's that are greater than or equal to an infinite set of x's. So my set S = { (-?,-?),(?,?)}. So, S o S will give me back the same set, because for the equal to part of the relation S, I will get back the identity Relation ( (a,a),(b,b),...etc) which will give me the set S = { (-?,-?),(?,?)}. The less than part of relation S will also include all real numbers...(right?).

So,

S o S = { (-?,-?),(?,?)}
I don't really know if that relation I wrote above is correct or makes sense really.

Thank you for your help,

--Dan

We know if (x,y) belongs to S then x<=y. But (y,y) also belongs to S. So (x,y) belongs to the composition:

\(\displaystyle (x,y) \in S \Rightarrow (x,y) \in S \circ S\)

Also, If (x,z) belongs to SoS then for some y in R, x<=y<=z which means x<=z. So,

\(\displaystyle (x,z) \in S \circ S \Rightarrow (x,z)\in S\)

Therefore, \(\displaystyle S = S \circ S\)

This is not true for strict <.

 

[pka]

Suppose that \(\displaystyle \left( {a,b} \right) \in S \circ S\).
The relation is transitive so this means that \(\displaystyle \left( {\exists c} \right)\left[ {\left( {a,c} \right) \in S \wedge \left( {c,b} \right) \in S} \right]\, \Rightarrow \,\left( {a,b} \right) \in S\).

Now suppose that \(\displaystyle \left( {e,f} \right) \in S\).
Because the relation is reflexive \(\displaystyle \left[ {\left( {e,e} \right) \in S \wedge \left( {e,f} \right) \in S} \right]\, \Rightarrow \,\left( {e,f} \right) \in S \circ S\).

Done. WHY?

 

[DrMike]

I’m trying to find xSySx

Why?

Check your notes - what is the composition of two relations? If R = SoT, doesn't that just mean xRy if there exists z with xSz and zTy?

Now, you want R=?o?. Sub ? into the S and T above, and you'll get

xRy if and only.... Hmm, I'll stop here, and let you carry on...

 

[pka]

Check your notes - what is the composition of two relations?
If R = SoT, doesn't that just mean xRy if there exists z with xSz and zTy?

Actually it does not mean that, unless you are using a very old textbook.
It means this \(\displaystyle \left( {x,y} \right) \in S \circ T\, \Leftrightarrow \,\left( {\exists z} \right)\left[ {\left( {x,z} \right) \in T \wedge \left( {z,y} \right) \in S} \right]\).
Relation composition give rise to function composition: action is “from the inside out”.
That is T acts first.

 

[DrMike]

Check your notes - what is the composition of two relations?
If R = SoT, doesn't that just mean xRy if there exists z with xSz and zTy?

Actually it does not mean that, unless you are using a very old textbook.
It means this \(\displaystyle \left( {x,y} \right) \in S \circ T\, \Leftrightarrow \,\left( {\exists z} \right)\left[ {\left( {x,z} \right) \in T \wedge \left( {z,y} \right) \in S} \right]\).
Relation composition give rise to function composition: action is “from the inside out”.
That is T acts first.

Ok.