TAOCP 5,1.1 Exercise 12

Continuing the notation of the previous exercise, prove that if $\pi_1$ and $\pi_2$ are permutations and if E is the smallest transitive set containing $E(\pi_1)\cup E(\pi_2)$ then $\bar{E}$ is transitive.

反证：假设存在$(a,b) \in \bar{E}, (b,c) \in \bar{E}$但$(a,c) \in E$，显然$(a,b) \notin E(\pi_1)$，$(b,c) \notin E(\pi_1)$  ,所以$c < b < a$并且在$\pi_1$中保持顺序。同理此三个数在$\pi_2$中也保持顺序。

现在考察(a,c)，如果E中去除(a,c)传递性仍然成立，则与E为满足传递性的最小集合矛盾，所以E中必有元素(a,t)和(t,c)。(a,t)和(t,c)必然分别来自$\pi_1$和$\pi_2$，不失一般性，设
$\pi_1=\ldots c \ldots b \ldots a \ldots t \ldots$
$\pi_2=\ldots t \ldots c \ldots b \ldots a \ldots$

现在有两种情况
1） b>t, 则有 $(b,t) \in E(\pi_1), (t,c) \in E(\pi_2)$ 导致$(b,c) \in  E$ 与假设$(b,c) \in \bar{E}$矛盾。
2） b<t 则有 $(a,t) \in E(\pi_1), (t,b) \in E(\pi_2)$ 导致$(a,b) \in E$ 与假设$(a,b) \in \bar{E}$矛盾。

所以$(a,c) \in E$不成立，$(a,c) \in \bar{E}$，即$\bar{E}$具有传递性。