[定理] 对推导归纳

设 𝑃( 𝑡,𝑡 ′ ) 是关于一对项的性质。如果对 [定义] 一步归约 的每一条规则都有:“前提里的每个 𝑡 1⟶𝑡 1 ′ 都满足 𝑃( 𝑡 1,𝑡 1 ′ )”能推出“结论满足 𝑃”,那么所有满足 𝑡⟶𝑡 ′ 的 ( 𝑡,𝑡 ′ ) 都满足 𝑃。

证明
令 𝑅={ ( 𝑡,𝑡 ′ )|𝑡⟶𝑡 ′ 且 𝑃( 𝑡,𝑡 ′ ) }。假设恰好说明 𝑅 对十条规则封闭。⟶ 是对规则封闭的最小关系,所以 ⟶⊆𝑅。
∎

References

[定义] 一步归约 [one-step-reduction]

Backlinks

Based on Typsite