Given two posets $\preccurlyeq$, prove that the following relation $R$ using both of them is transitive

47 Views Asked by At

We're given the following relation $R$ for two posets $(S_1, \preccurlyeq_1)$ and $(S_2, \preccurlyeq_2)$:

For $a_1,b_1 \in S_1$ and $a_2, b_2 \in S_2$:

$(a_1, a_2)R(b_1,b_2) \Leftrightarrow (a_1 \preccurlyeq_1 b_1 \land a_1 \neq b_1) \lor (a_2 \preccurlyeq_2 b_2 \land a_1 = b_1)$

I can see that this relation is both reflexive and antisymmetric, but what about transitivity?

1

There are 1 best solutions below

4
On BEST ANSWER

Let's suppose $(a_1,a_2)R(b_1,b_2)$ and $(b_1,b_2)R(c_1,c_2)$ for some $a_1, b_1, c_1 \in S_1$ and $a_2,b_2,c_2 \in S_2$. Now we have four possible cases:
$1)$ We have $(a_1 \preccurlyeq_1 b_1 \land a_1 \neq b_1)$ and $(b_1 \preccurlyeq_1 c_1 \land b_1 \neq c_1)$, hence it follows by the transitivity of $\preccurlyeq_1$ that $(a_1 \preccurlyeq_1 c_1 \land a_1 \neq c_1)$, i.e. $(a_1,a_2)R(c_1,c_2)$.
$2)$ We have $(a_1 \preccurlyeq_1 b_1 \land a_1 \neq b_1)$ and $(b_2 \preccurlyeq_2 c_2 \land b_1 = c_1)$, hence it follows $(a_1 \preccurlyeq_1 c_1 \land a_1 \neq c_1)$ since $b_1=c_1$ i.e. $(a_1,a_2)R(c_1,c_2)$.
$3)$ We have $(a_2 \preccurlyeq_2 b_2 \land a_1 = b_1)$ and $(b_1 \preccurlyeq_1 c_1 \land b_1 \neq c_1)$, hence it follows $(a_1 \preccurlyeq_1 c_1 \land a_1 \neq c_1)$ since $a_1=b_1$, i.e. $(a_1,a_2)R(c_1,c_2)$.
$4)$ We have $(a_2 \preccurlyeq_2 b_2 \land a_1 = b_1)$ and $(b_2 \preccurlyeq_2 c_2 \land b_1 = c_1)$, hence by transitivity of $\preccurlyeq_2$ and $a_1=b_1=c_1$ we have $(a_2 \preccurlyeq_2 c_2 \land a_1 = c_1)$, i.e. $(a_1,a_2)R(c_1,c_2)$.
This proves that $R$ is transitive.