引理1 若@是P中公理,则对P中任何有限公式集∑都有 ∑Na 证 a上N3→a 例13 a→(3→),a→Na→y 例13 0+xa→(月→a) 0N(a→(→)→(a→)→(a→))→+ ∑HNa→(6→a) ∑N(a→(→)→((a→3)→(a→)+ a→-3}N6→a 例15 ∑N(→a→6)→(3→a
1 α P , P Σ Σ `N α : α `N β→α 13 α→(β→γ), α→β `N α→γ 13 ∅ `N α→(β→α) → + ∅ `N (α→(β→γ))→((α→β)→(α→γ)) → + Σ `N α→(β→α) + Σ `N (α→(β→γ))→((α→β)→(α→γ)) + ¬ α→¬ β `N β→α 15 Σ `N (¬ α→¬ β)→(β→α) 5
定理14 设∑,O分别为P中有限公式集和公式 若∑Pa,则∑Na 证:设 C1,C2 是P中在前提∑下推出a的一个证明序列,(其中 只要证 对每个(1≤i<m),∑卜Na 下对归纳证之 6
14 Σ, α P . Σ `P α, Σ `N α. : α1, α2, · · · , αn P Σ α ✚ , ( : αn = α). : i (1 ≤ i ≤ n), Σ `N αi i . 6
定理14的归纳证明—奠基步骤 (1)当=1时,a1是P的一个公理,或a1∈∑ (1.1)若a1是P的一个公理,由引理1知∑卜Na1 (1.2)若a1∈∑,由N的规则(∈)知∑卜Na1
14 — (1) i = 1 , α1 P ✚ , α1 ∈ Σ. (1.1) α1 P ✚ , ✓1 Σ `N α1. (1.2) α1 ∈ Σ, ✓N (∈) Σ `N α1. 7