Saturday, December 10, 2016

logic - Show that $A_1,...,A_nvDash_{taut} B leftrightarrow vDash_{taut} A_1 to A_2to ...to A_nto B$



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 $A_1\vDash_{taut} B \leftrightarrow \vDash_{taut}A_1\to B$, from the LHS $v(B)=t$ and is congruent with the RHS $v(A_1\to B) = \textbf{t}$ and wlog the same can be said for RHS to LHS that $v(A_1)=\textbf{t}$ by definition of $\Gamma = A_1 \vDash_{taut}B$.




Inductive Step: Assume $A_1,...,A_k\vDash_{taut} B \leftrightarrow \vDash_{taut} A_1 \to A_2\to ...\to A_k\to B$ is true for all $k > 0$



Prove that $A_1,...,A_k, A_{k+1}\vDash_{taut} B \leftrightarrow \vDash_{taut} A_1 \to A_2\to ...\to A_k\to A_{k+1}\to B$.



Since $v(B)=\textbf{t}$ and by definition $F_{\to}(v(A_1\to A_2\to ... \to A_k\to A_{k+1}),\textbf{t})=\textbf{t}$ and wlog $v(B)=\textbf{t}$ since by definition of $\Gamma = A_1,...,A_k, A_{k+1}\vDash_{taut} B$,
$v(A_1),...,v(A_k), v(A_{k+1}) = \textbf{t}$


Answer



It is easier to show that $\Gamma\cup\{A_1,\ldots,A_n\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_n\}\vDash A_1\rightarrow(\ldots\rightarrow(A_n\rightarrow B))$.




First, prove an obvious fact that $\Gamma\cup\{A\}\vDash B\Leftrightarrow\Gamma\setminus\{A\}\vDash A\rightarrow B$. It is your first exercise (and your induction step).



Let us (actually, it is a second easy exercise for you) now show that $\Gamma\vDash A\Leftrightarrow\Gamma'\vDash A$ with $\Gamma'$ being some permutation of $\Gamma$.



A third and final exercise for you is to show that $$\vDash A_1\rightarrow(\ldots\rightarrow(A_n\rightarrow B))\Leftrightarrow\vDash A_{n}\rightarrow(A_1\rightarrow(\ldots\rightarrow(A_{n-1}\rightarrow B)))$$ for any $n$



Now, we proceed as follows.



Assume $$\Gamma\cup\{A_1,\ldots,A_k\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_k\}\vDash A_1\rightarrow(\ldots\rightarrow(A_k\rightarrow B))$$




Why then $$\Gamma\cup\{A_1,\ldots,A_{k+1}\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_{k+1}\}\vDash A_1\rightarrow(\ldots\rightarrow(A_{k+1}\rightarrow B))$$



By second exercise we have
$$\Gamma\cup\{A_{k+1},A_1,\ldots,A_k\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_{k+1}\}\vDash A_1\rightarrow(\ldots\rightarrow(A_{k+1}\rightarrow B))$$



By induction hypothesis
$$\Gamma\cup\{A_{k+1},A_1,\ldots,A_k\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_{k}\}\cup\{A_{k+1}\}\vDash A_1\rightarrow(\ldots\rightarrow(A_{k}\rightarrow B))$$



By induction step
$$\Gamma\cup\{A_{k+1},A_1,\ldots,A_k\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_{k+1}\}\vDash A_{k+1}\rightarrow(A_1\rightarrow(\ldots\rightarrow(A_{k}\rightarrow B)))$$




By third exercise you obtain
$$\Gamma\cup\{A_{k+1},A_1,\ldots,A_k\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_{k+1}\}\vDash A_1\rightarrow(\ldots\rightarrow(A_{k+1}\rightarrow B))$$



By second exercise you obtain
$$\Gamma\cup\{A_1,\ldots,A_{k+1}\}\vDash B\Leftrightarrow\Gamma\setminus\{A_1,\ldots,A_{k+1}\}\vDash A_1\rightarrow(\ldots\rightarrow(A_{k+1}\rightarrow B))$$



And that's it.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...