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