Show that $A_1,...,A_n\vDash_{taut} B \leftrightarrow \vDash_{taut} A_1 \to A_2\to ...\to A_n\to B$

67 Views Asked by At

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}$

1

There are 1 best solutions below

0
On BEST 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.