2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.