The Answer to the Question
is below this banner.
Here's the Solution to this Question
(a) The matrix that represents R is shown below. It will be an initial matrix for the algorithm.
For every step, for some .
In other words, we can add a new pair to the relation corresponding to , if and only if there is some in corresponding to .
Answer: The resulting transitive closure is
Let's show is a poset. Let's show that satisfies the following three properties.
- Reflexivity. For every is trivially true.
- Antisymmetry. Let and .Then from the definition.
- Transitivity. Let and . Then for all we have , and therefore . Thus .
The Hasse diagram for is shown below.
(c) A chain in a poset is a subset such that any two elements are comparable (thus for every either or or both hold).
An antichain in a poset is a subset such that no two elements are comparable.