MHB Satisfying S∘S=S: What Are The Conditions?

lemonthree
Messages
47
Reaction score
0
Which of the following implies that S∘S=S? There are 5 options, select all that are right.

S is reflexive
S is symmetric
S is transitive
S is reflexive and symmetric
S is reflexive and transitive

I assume that S acts on a set A. So let a,b,c be elements of A.
For S to be reflexive, for all a in A, a S a.
For S to be symmetric, for all a,b in A, if a S b, then b S a.
For S to be transitive, for all a,b,c in A, if a S b and b S c, then a S c.

Now I got to compose S with S, and I know that the standard definition of R∘S = the relation of A to C, where (a,c) is an element of A x C such that there exists b in B s.t. (a,b) in R and (b,c) in S.

So I have to adapt this standard definition of R∘S to S∘S? I assume that S∘S is the relation of A to A, where (a,c) is an element of A x A such that there exists b in A s.t. (a,b) in S and (b,c) in S.

Therefore, I think S∘S=S implies S is reflexive, symmetric and transitive?
1. For all a in A, a S a.
2. For all a,b in A, if a S b, then b S a. Likewise, if b S a, then a S b.
3. For all a,b,c in A, if a S b and b S c, then a S c. Likewise, if c S b and b S a, then c S a.

So with that, S should be reflexive and symmetric / reflexive and transitive too? Have I misunderstood any parts?
 
Physics news on Phys.org
lemonthree said:
Which of the following implies that S∘S=S? There are 5 options, select all that are right.

S is reflexive
S is symmetric
S is transitive
S is reflexive and symmetric
S is reflexive and transitive

I assume that S acts on a set A. So let a,b,c be elements of A.
For S to be reflexive, for all a in A, a S a.
For S to be symmetric, for all a,b in A, if a S b, then b S a.
For S to be transitive, for all a,b,c in A, if a S b and b S c, then a S c.

Now I got to compose S with S, and I know that the standard definition of R∘S = the relation of A to C, where (a,c) is an element of A x C such that there exists b in B s.t. (a,b) in R and (b,c) in S.

So I have to adapt this standard definition of R∘S to S∘S? I assume that S∘S is the relation of A to A, where (a,c) is an element of A x A such that there exists b in A s.t. (a,b) in S and (b,c) in S.

Therefore, I think S∘S=S implies S is reflexive, symmetric and transitive?
But that is not what was asked!
The question was the other way around- which of those are necessary to show that S∘S=S.

1. For all a in A, a S a.
2. For all a,b in A, if a S b, then b S a. Likewise, if b S a, then a S b.
3. For all a,b,c in A, if a S b and b S c, then a S c. Likewise, if c S b and b S a, then c S a.

So with that, S should be reflexive and symmetric / reflexive and transitive too? Have I misunderstood any parts?
 
Oops :(

I don't really know how to compose S by itself though, so let me try one and see whether I am correct?

S∘S: a S a S a = a S a = S
So S is reflexive would imply that S∘S = S?
 
If S, a relation on set X, is reflexive then S contains (a, a) for every a in X. But that does not say anything about other pairs in S.

For example, let S, a relation on X= {a, b, c}, be {(a, a), (b, b), (c, c), (a, b), (b, c)}. S is reflexive and S∘S= {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)} which is NOT S.
 
Thank you so much @Country Boy :D

I finally understood it! I could see it better with a diagram, so that's what I did for testing symmetry and transitivity.

SxS=S.jpg


Just as in the reflexivity case, S∘S is not S. So that means the first 3 options are out. Again, looking at the diagram, once S is reflexive and transitive (or reflexive and symmetric), there will be 9 lines "connecting" the elements together, so S∘S = S for the last 2 options.
 
I selected the 2 options

S is reflexive and symmetric
S is reflexive and transitive

and I'm wrong...I don't understand why o_O
 
Let S on X be {(a,b), (a,c), (a,a), (b,a), (b,b), (c,a), (c,c)}. S is reflexive and symmetric, and S∘S= {(a,a), (a,b), (a,c), (b,b), (b,a), (b,c), (c,c), (c,a), (c,b)}
So S has 7 elements while S∘S has 9 elements, so S is reflexive and symmetric is not true.
 
\( S\circ S=S \) is equivalent to the fact that $S$ is transitive. Both mean that if one can go from $a$ to $c$ using two steps according to $S$, then one can go from $a$ to $c$ using one step.
 
Back
Top