I'm having a hard time understanding the iff part of this proof by induction (is this vacuously true?), below is my attempt:
Base Case: Let n=1, therefore A1⊨tautB↔⊨tautA1→B, from the LHS v(B)=t and is congruent with the RHS v(A1→B)=t and wlog the same can be said for RHS to LHS that v(A1)=t by definition of Γ=A1⊨tautB.
Inductive Step: Assume A1,...,Ak⊨tautB↔⊨tautA1→A2→...→Ak→B is true for all k>0
Prove that A1,...,Ak,Ak+1⊨tautB↔⊨tautA1→A2→...→Ak→Ak+1→B.
Since v(B)=t and by definition F→(v(A1→A2→...→Ak→Ak+1),t)=t and wlog v(B)=t since by definition of Γ=A1,...,Ak,Ak+1⊨tautB,
v(A1),...,v(Ak),v(Ak+1)=t
Answer
It is easier to show that Γ∪{A1,…,An}⊨B⇔Γ∖{A1,…,An}⊨A1→(…→(An→B)).
First, prove an obvious fact that Γ∪{A}⊨B⇔Γ∖{A}⊨A→B. It is your first exercise (and your induction step).
Let us (actually, it is a second easy exercise for you) now show that Γ⊨A⇔Γ′⊨A with Γ′ being some permutation of Γ.
A third and final exercise for you is to show that ⊨A1→(…→(An→B))⇔⊨An→(A1→(…→(An−1→B))) for any n
Now, we proceed as follows.
Assume Γ∪{A1,…,Ak}⊨B⇔Γ∖{A1,…,Ak}⊨A1→(…→(Ak→B))
Why then Γ∪{A1,…,Ak+1}⊨B⇔Γ∖{A1,…,Ak+1}⊨A1→(…→(Ak+1→B))
By second exercise we have
Γ∪{Ak+1,A1,…,Ak}⊨B⇔Γ∖{A1,…,Ak+1}⊨A1→(…→(Ak+1→B))
By induction hypothesis
Γ∪{Ak+1,A1,…,Ak}⊨B⇔Γ∖{A1,…,Ak}∪{Ak+1}⊨A1→(…→(Ak→B))
By induction step
Γ∪{Ak+1,A1,…,Ak}⊨B⇔Γ∖{A1,…,Ak+1}⊨Ak+1→(A1→(…→(Ak→B)))
By third exercise you obtain
Γ∪{Ak+1,A1,…,Ak}⊨B⇔Γ∖{A1,…,Ak+1}⊨A1→(…→(Ak+1→B))
By second exercise you obtain
Γ∪{A1,…,Ak+1}⊨B⇔Γ∖{A1,…,Ak+1}⊨A1→(…→(Ak+1→B))
And that's it.
No comments:
Post a Comment