Thursday, 14 July 2016

logic - Show that A1,...,AnvDashtautBleftrightarrowvDashtautA1toA2to...toAntoB



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 A1tautBtautA1B, from the LHS v(B)=t and is congruent with the RHS v(A1B)=t and wlog the same can be said for RHS to LHS that v(A1)=t by definition of Γ=A1tautB.



Inductive Step: Assume A1,...,AktautBtautA1A2...AkB is true for all k>0




Prove that A1,...,Ak,Ak+1tautBtautA1A2...AkAk+1B.



Since v(B)=t and by definition F(v(A1A2...AkAk+1),t)=t and wlog v(B)=t since by definition of Γ=A1,...,Ak,Ak+1tautB,
v(A1),...,v(Ak),v(Ak+1)=t


Answer



It is easier to show that Γ{A1,,An}BΓ{A1,,An}A1((AnB)).



First, prove an obvious fact that Γ{A}BΓ{A}AB. 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((AnB))⇔⊨An(A1((An1B))) for any n



Now, we proceed as follows.



Assume Γ{A1,,Ak}BΓ{A1,,Ak}A1((AkB))



Why then Γ{A1,,Ak+1}BΓ{A1,,Ak+1}A1((Ak+1B))



By second exercise we have

Γ{Ak+1,A1,,Ak}BΓ{A1,,Ak+1}A1((Ak+1B))



By induction hypothesis
Γ{Ak+1,A1,,Ak}BΓ{A1,,Ak}{Ak+1}A1((AkB))



By induction step
Γ{Ak+1,A1,,Ak}BΓ{A1,,Ak+1}Ak+1(A1((AkB)))



By third exercise you obtain
Γ{Ak+1,A1,,Ak}BΓ{A1,,Ak+1}A1((Ak+1B))




By second exercise you obtain
Γ{A1,,Ak+1}BΓ{A1,,Ak+1}A1((Ak+1B))



And that's it.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...