Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Among all students in a classroom we have a binary relations $\mathcal {R,S}$.

Student A is in relation with student B, formally (A,B) $\in$ $\mathcal R$, iff -
"A sits in the same row as B and B is not to the left of A"

Student A is in relation with student B, formally (A,B) $\in$ $\mathcal S$, iff -
"B sits in the second row (regardless of A)"

Not all seats have to be occupied.

I have to decide whether the composition of these relations, $\mathcal S \circ \mathcal R$, is reflexive, symmetric, antisymmetric or transitive. I only need help with the composition of these relations. What will the final relation look like? How to solve composition of relations like this (howto would be appreciated). Thanks

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

I find it helpful to think of composition of relations as multiplication of Boolean matrices, where addition of truth values is disjunction and multiplication is conjunction: $(i,k)\in\mathcal S\circ\mathcal R$ if and only if there is at least one element $j$ such that both $(i,j)\in\mathcal R$ and $(j,k)\in\mathcal S$. In the present case, $(i,k)\in\mathcal S\circ\mathcal R$ if and only if there is a student $j$ such that $i$ sits in the same row as $j$ and $j$ is not to the left of $i$, and $k$ sits in the second row. Since $j$ doesn't occur in the second condition, we can choose $j=i$ to fulfill the first condition; so $(i,k)\in\mathcal S\circ\mathcal R$ if and only if $k$ sits in the second row.

This relation is not reflexive unless all students sit in the second row. It's not symmetric unless all students sit in the second row or all students don't sit in the second row. It's not antisymmetric unless at most one student sits in the second row. It's transitive since $(j,k)\in\mathcal S\circ\mathcal R$ alone implies $(i,k)\in\mathcal S\circ\mathcal R$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.