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}\)具有传递性。