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

  • Context: MHB 
  • Thread starter Thread starter lemonthree
  • Start date Start date
  • Tags Tags
    Composition Relation
Click For Summary

Discussion Overview

The discussion revolves around the conditions under which the composition of a relation \( S \) with itself, denoted \( S \circ S \), is equal to \( S \). Participants explore various properties of relations, including reflexivity, symmetry, and transitivity, and how these properties relate to the equality \( S \circ S = S \). The scope includes theoretical reasoning and mathematical exploration.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested, Mathematical reasoning

Main Points Raised

  • Some participants propose that for \( S \circ S = S \), \( S \) must be reflexive, symmetric, and transitive, citing definitions of these properties.
  • Others argue that reflexivity alone does not guarantee \( S \circ S = S \), providing counterexamples where reflexive relations do not satisfy the condition.
  • A participant suggests that the composition \( S \circ S \) can be understood as a relation on set \( A \) where specific pairs must exist for the equality to hold.
  • Another participant notes that \( S \) being reflexive and symmetric does not imply \( S \circ S = S \), using a specific example to illustrate this point.
  • One participant claims that \( S \circ S = S \) is equivalent to \( S \) being transitive, suggesting a direct relationship between transitivity and the composition of the relation.

Areas of Agreement / Disagreement

Participants express differing views on which properties are necessary for \( S \circ S = S \). There is no consensus on a definitive answer, as some argue for combinations of properties while others provide counterexamples that challenge these claims.

Contextual Notes

Limitations include the lack of clarity on how certain properties interact and the dependence on specific definitions of relations. Some participants' examples demonstrate that reflexivity and symmetry do not suffice for the equality, indicating unresolved aspects of the discussion.

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.
 

Similar threads

MHB Relation Algebra - Relational Calculus
  • · Replies 6 ·
Replies
6
Views
1K
Undergrad Supremum of a set, relations and order
  • · Replies 35 ·
2
Replies
35
Views
5K
MHB Give a set and a relation that satisfies the properties
  • · Replies 10 ·
Replies
10
Views
2K
MHB Proving Binary Relations: R & S
  • · Replies 8 ·
Replies
8
Views
3K
Equality sign and equivalence relations
  • · Replies 7 ·
Replies
7
Views
1K
MHB Equivalence Relations: Solving & Proving Reflexivity, Symmetry & Transitivity
  • · Replies 2 ·
Replies
2
Views
2K
MHB Please help with bool algebra and logic things
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Prove that points which are indistinguishable from 0 exist (using logic)
  • · Replies 17 ·
Replies
17
Views
2K
Graduate Probability distributions in an ordered set of extracted elements
  • · Replies 2 ·
Replies
2
Views
2K
MHB Proving Reflexive, Symmetric and Transitive Properties of Relation R on P(U)
  • · Replies 3 ·
Replies
3
Views
2K