Saturday, December 10, 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

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...