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

In summary, for S∘S=S to be true, S must be both reflexive and symmetric (or reflexive and transitive).
  • #1
lemonthree
51
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
  • #2
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?
 
  • #3
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?
 
  • #4
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.
 
  • #5
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.
 
  • #6
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
 
  • #7
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.
 
  • #8
\( 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.
 

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

1. What does the equation S∘S=S mean?

This equation is known as the "satisfying equation" and it means that the composition of a function with itself is equal to the original function. In other words, when you apply a function to its own output, the result is the same as the original input.

2. What are the conditions for the equation S∘S=S to be satisfied?

The conditions for this equation to be satisfied are that the function must be associative, meaning that the order of composition does not matter, and that there exists an identity element, where applying the function to the identity element results in the identity element itself.

3. Can any type of function satisfy the equation S∘S=S?

No, not all functions can satisfy this equation. The function must meet the conditions mentioned in the previous question in order for the equation to hold true.

4. How is the satisfying equation used in mathematics?

This equation is a fundamental concept in abstract algebra and is used to define groups, which are sets of elements with a binary operation that satisfies the equation S∘S=S. It is also used to prove theorems and solve problems in various mathematical fields.

5. Are there any real-world applications of the satisfying equation?

Yes, the satisfying equation has real-world applications in computer science, particularly in programming languages and data structures. It is also used in cryptography to create secure encryption algorithms.

Similar threads

Replies
6
Views
965
Replies
35
Views
2K
Replies
10
Views
2K
Replies
8
Views
3K
Replies
7
Views
443
Replies
2
Views
1K
Back
Top