基于归纳法证明Γ∪Λ真值指派满足Γ所有定理及相关逻辑定义问询

先把咱们用到的定义和背景明确下来（对应Enderton《逻辑学》第115页的内容）：

前置定义与定理背景 #

• 逻辑公理集：记作Λ，是命题逻辑中预先设定的公理集合。
• 合式公式集：记作Γ，是命题逻辑中任意一组合式公式。
• 重言蕴涵：若满足Γ∪Λ中所有成员的每一个真值指派也满足公式φ，则称Γ∪Λ重言蕴涵φ。
• 可证性（记作Γ⊢φ）：若存在有限序列⟨a₀,…,aₙ⟩，使得aₙ=φ，且对每个k≤n，满足以下任一条件：
  1. aₖ∈Γ∪Λ；
  2. aₖ由序列中更早的两个公式通过假言推理得到（即存在i,j<k，使得aⱼ = aᵢ → aₖ）。

另外，Enderton书中的定理24B给出了可证性和重言蕴涵的等价关系：Γ⊢φ当且仅当Γ∪Λ重言蕴涵φ。不过咱们今天要证的是：Γ∪Λ上的任一真值指派都满足Γ中的所有定理——换句话说，只要φ是Γ的定理（即Γ⊢φ），那么任何满足Γ∪Λ的真值指派都能让φ为真。

归纳法证明过程 #

我们对Γ⊢φ的证明序列长度做数学归纳：

基例：证明序列长度为1（n=0） #

此时证明序列只有一个元素a₀=φ，根据可证性的定义，φ必然属于Γ∪Λ：

• 如果φ∈Λ：因为真值指派满足Γ∪Λ，所以φ在该指派下为真；
• 如果φ∈Γ：同理，真值指派满足Γ，所以φ为真。
  基例成立。

归纳步骤：假设长度≤k的证明序列对应的定理都满足结论 #

假设对于所有通过长度≤k的证明序列得到的公式ψ，只要Γ⊢ψ，那么满足Γ∪Λ的真值指派v都有v(ψ)=真。

现在考虑长度为k+1的证明序列，最后一个元素是a_{k+1}=φ，分两种情况讨论：

情况1：φ∈Γ∪Λ

这和基例完全一致，真值指派v满足Γ∪Λ，所以v(φ)=真，结论成立。

情况2：φ由假言推理得到

根据可证性定义，存在i,j < k+1，使得aⱼ = aᵢ → φ。
因为i和j都≤k，根据归纳假设，v(aᵢ)=真，且v(aⱼ)=真。而根据蕴含式的真值表，当aᵢ为真且aᵢ→φ为真时，φ必然为真。因此v(φ)=真，结论成立。

归纳结论 #

根据数学归纳法，对于任意Γ的定理φ（即Γ⊢φ），所有满足Γ∪Λ的真值指派都满足φ。也就是说，Γ∪Λ上的任一真值指派均满足Γ中的所有定理。

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