Question

a) Let A = (1,2,3,4) and R = ((1 ,2),(2,4),( 1,3 ),(3 ,2)}. Find the transitive closure of R by Warshall’s algorithm.
b) Let A = {a,b,c}. show that (P(A),c ) is a poset and draw its Hasse diagram.
c) Define Chains and Antichains.

Answer 1

(a) The matrix that represents R is shown below. It will be an initial matrix for the algorithm.

$W^0=\begin{bmatrix} 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}$

For every step, $W^n_{i,j} := W^{n-1}_{i,j} \vee (W^{n-1}_{i,k} \wedge W^{n-1}_{k,j})$ for some $k$.

In other words, we can add a new pair $(i, j)$ to the relation $R^i$ corresponding to $W^i$, if and only if there is some $k$ in $R^{i-1}$ corresponding to $W^{i-1}$.

$W^1=\begin{bmatrix} 0 & 1 & 1 & \color{red}1\\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & \color{red}1\\ 0 & 0 & 0 & 0 \end{bmatrix}$

$(1, 2) \in R^0 \wedge (2, 4) \in R^0 \implies (1, 4) \in R^1$

$(3, 2) \in R^0 \wedge (2, 4) \in R^0 \implies (3, 4) \in R^1$

$W^1=W^2 =W$.

Answer: The resulting transitive closure is

$$R^+ = \{(1,2),(1,3), (1,4), (2,4), (3,2), (3,4)\}.$$

(b) $P(A) = \big \{ \varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{a,c\}, \{a, b,c\} \big \}.$

Let's show $S=(P(A), \subseteq)$ is a poset. Let's show that $S$ satisfies the following three properties.

1. Reflexivity. For every $x \in P(A) \ x \subseteq x$ is trivially true.
2. Antisymmetry. Let $x, y \in P(A)$ and $x \subseteq y \wedge y \subseteq z$.Then $x=y$ from the definition.
3. Transitivity. Let $x, y,z \in P(A)$ and $x \subseteq y \wedge y \subseteq x$. Then for all$a \in x$ we have $a \in y$, and therefore $a \in z$. Thus $x \subseteq z$.

The Hasse diagram for $(P(A), \subseteq)$ is shown below.

(c) A chain in a poset $(P, \le)$ is a subset $A \subseteq P$ such that any two elements $x, y\in A$ are comparable (thus for every $x, y \in A$ either $x \le y$ or $y \le x$ or both hold).

An antichain in a poset $(P, \le)$ is a subset $A \subseteq P$ such that no two elements $x,y\in A$ are comparable.