如何用规则归纳法证明R⁺⊆S及R⁺的传递性

咱一步步来搞定这个规则归纳法的证明，核心就是跟着$R^+$的生成逻辑拆成两种情况来验证：

先把所有给定条件和要做的事理清楚：

• 给定二元关系 $R \subseteq X \times X$，以及它的闭包 $R^+ \subseteq X \times X$，满足 $R \subseteq R^+$
• $R^+$由两条规则生成：
  • 公理（自反基础）：对任意 $x \in X$，无条件有 $(x,x) \in R^{+$（也就是所有自反序对直接属于$R}+$）
  • 推理规则（右扩展）：如果已经有 $(x,y) \in R^+$，且 $(y,z) \in R$，那么可以推出 $(x,z) \in R^+$
• 定义集合 $S = {(y,z) \in X \times X : \forall x\in X. (x,y) \in R^+ \implies (x,z) \in R^+}$
• 我们要先证 $R^+ \subseteq S$，再由此推出 $R^+$ 是传递的（即若 $(a,b) \in R^+$ 且 $(b,c) \in R^+$，则 $(a,c) \in R^+$）

规则归纳法的核心思路是：证明所有能通过$R^+$的生成规则得到的元素，都属于$S$，所以我们分「公理生成的元素」和「推理规则生成的元素」两种情况来证。

1. 基础情况：公理生成的元素 #

公理生成的是所有形如 $(x,x)$ 的序对（$x \in X$）。我们要验证 $(x,x) \in S$。

根据$S$的定义，需要确认：对任意 $a \in X$，如果 $(a,x) \in R^+$，那么 $(a,x) \in R^+$。这显然是恒成立的重言式——条件和结论完全一致，所以 $(x,x)$ 满足$S$的定义，即 $(x,x) \in S$。

2. 归纳步骤：推理规则生成的元素 #

假设我们通过推理规则得到了 $(x,z) \in R^+$：已知前提是 $(x,y) \in R^+$ 且 $(y,z) \in R$，现在要证 $(x,z) \in S$。

根据$S$的定义，我们需要证明：对任意 $a \in X$，若 $(a,x) \in R^+$，则 $(a,z) \in R^+$。

现在结合已知条件推导：

• 归纳假设：因为 $(x,y) \in R^{+$，而我们要归纳的是「所有$R}+$中的元素都属于$S$」，所以可以用归纳假设得到 $(x,y) \in S$。根据$S$的定义，这意味着：对任意 $a \in X$，若 $(a,x) \in R^+$，则 $(a,y) \in R^+$。
• 已知 $(y,z) \in R$，而题目给出 $R \subseteq R^+$，所以 $(y,z) \in R^+$。
• 现在，如果 $(a,x) \in R^+$，根据归纳假设的结论，$(a,y) \in R^+$；再结合 $(y,z) \in R$，直接套用$R^+$的推理规则，就能推出 $(a,z) \in R^+$。

这就满足了 $(x,z) \in S$ 的定义，所以推理规则生成的元素也属于$S$。

现在我们已经证得 $R^+ \subseteq S$，也就是说所有属于$R^+$的序对，都满足$S$的定义。

现在来证传递性：任取 $(a,b) \in R^+$ 和 $(b,c) \in R^+$，我们要证 $(a,c) \in R^+$。

因为 $(b,c) \in R^+ \subseteq S$，根据$S$的定义：对任意 $x \in X$，若 $(x,b) \in R^+$，则 $(x,c) \in R^+$。我们直接取 $x = a$——已知 $(a,b) \in R^+$，所以根据$S$的定义，立刻就能得到 $(a,c) \in R^+$。

这样就完成了$R^+$传递性的证明。

内容的提问来源于stack exchange，提问作者oldselflearner1959