How would you make a transitive closure on something like this:

Among all students in a classroom we have a binary relation $\mathcal R$. Student A is in relation with student B, formally (A,B) $\in$ $\mathcal R$ iff -

"A sits in a row in front of B (there is no row between them)."
"A and B sit behind each other in the same column (A behind B or B behind A) ."

I have to make a transitive closure on relations like this and haven't found a easy way to do it yet.


We assume that the classroom has the traditional rectangular array of seats. We also assume that every seat is occupied. The problem becomes much more complicated if some seats are empty.

There is a special case to consider: If the classroom is a single row classroom, then no one is $\mathcal{R}$-related to anybody else, and the same is true of the transitive closure.

We suppose from now that there is more than one row. We will think about the transitive closure $\mathcal{C}$ of $\mathcal{R}$.

Imagine a monkey that is allowed to jump from any person $A$ to any person $B$ in the row directly in front of $A$. The monkey can also jump directly forward or backward in any column. Then $(A,B)\in\mathcal{C}$ if the monkey can get from $A$ to $B$ by a possibly long series of jumps.

Imagine $A$ and $B$ in the same row. We show the monkey can get from $A$ to $B$. If this row is not the back row, the monkey jumps directly backwards, and then forward to $A$. If the row is the back row, the monkey jumps forward to the person directly in front of $B$, and then backwards to $B$.

So the monkey can move freely in a row. It can move freely in a column by definition, so it can get from anywhere to anywhere.

Conclusion: If there is a single row, then $\mathcal{R}$, and its transitive closure, are both the empty relation.

If there is more than one row, the transitive closure of $\mathcal{R}$ is the set $\mathcal{C}$ consisting of all ordered pairs $(A, B)$, including pairs of type $(X,X)$.

Remark: The monkey was not introduced for fun. It plays a very large role in solving the problem. After having thought about the problem with the help of the monkey, we can write out things in set-theoretic language. But the monkey is essential in figuring out what is going on.

You asked how to deal with "relations like this." It is not possible to describe what to do in a general unspecified situation. But feel free to borrow the monkey.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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