# Use induction to show that a truth assignment on $\Gamma\cup\Lambda$ satisfies all theorem from $\Gamma$

Definitions: Let $$\Lambda$$ be a set of logical axioms and $$\Gamma$$ be a sets of well-formed formulas (in propositional logic). We say that $$\Gamma\cup\Lambda$$ tautologically implies $$\varphi$$ if for every truth assignment satisfying every member of $$\Gamma\cup\Lambda$$ also satisfies $$\varphi.$$

We say that $$\Gamma\vdash \varphi$$ if there exists a finite sequence $$\langle a_0,\dots,a_n\rangle$$ in $$\Gamma$$ such that $$a_n=\varphi$$ and for each $$k\leq n,$$ either

$$(1)$$ $$a_k$$ is in $$\Gamma\cup\Lambda,$$ or

$$(2)$$ $$a_k$$ is obtained by modus ponens from two earlier formulas in the sequence, that is, for some $$i$$ and $$j$$ less than $$k,$$ $$a_j$$ is $$a_i\to a_k.$$

I'm reading Enderton's logic book. In page $$115,$$ he stated the following theorem.

Theorem $$24$$B: $$\Gamma\vdash \varphi$$ iff $$\Gamma\cup \Lambda$$ tautologically implies $$\varphi$$.

The author provided the following proof to $$(\Rightarrow)$$ direction:

This depends on the obvious fact that $$\{\alpha,\alpha\to\beta\}$$ tautologically implies $$\beta.$$ Suppose that we have a truth assignment $$v$$ satisfies every member of $$\Gamma\cup \Lambda.$$ By induction we can see that $$v$$ satisfies any theorem of $$\Gamma.$$ The inductive step uses exactly the above-mentioned fact obvious fact.

Question: I fail to prove the bolded sentence. In particular, I do not see how to use induction.

My attempt: Let $$v$$ be a truth assignment that satisfies all members of $$\Gamma\cup\Lambda.$$ By assumption, let $$\langle a_0,...,a_n\rangle$$ be a finite sequence in $$\Gamma$$ such that $$a_n=\varphi.$$

For each $$k\leq n,$$ if $$a_k$$ is in $$\Gamma\cup\Lambda,$$ then $$v$$ will satisfy $$a_k.$$

We use induction to show that if $$a_k$$ is obtained by modus ponens from two earlier formulas, say $$a_i$$ and $$a_j$$ for $$i$$ and $$j$$ less than $$k,$$ then $$v$$ will satisfy $$a_k.$$

Let $$a_k$$ be the first formula that is obtained by modus ponens from $$a_i$$ and $$a_j$$ where $$i$$ and $$j$$ are less than $$k.$$ Then $$a_i$$ and $$a_j$$ are elements of $$\Gamma\cup\Lambda.$$ Therefore, $$v$$ will satisfy $$a_i$$ and $$a_j.$$ By modus ponen, $$v$$ will satisfy $$a_k.$$

Our inductive hypothesis is that if $$a_k$$ is obtained by modus ponens from two earlier formulas, then $$v$$ will satisfy $$a_k.$$

Suppose that $$a_{k+1}$$ is the next formula obtained by modus ponens from two earlier formulas, say $$a_i$$ and $$a_j$$, where $$i$$ and $$j$$ are less than $$k+1.$$ By inductive hypothesis, $$v$$ will satisfy both $$a_i$$ and $$a_j.$$ Therefore, $$v$$ will satisfy $$a_{k+1}.$$

Is my proof correct?

• I can't read the last paragraph, there is a typo in some LaTeX command. Please, fix it. – Taroccoesbrocco Feb 1 '18 at 13:48
• Not exaclty; consider $v$ that satisfies $\Gamma \cup \Lambda$, and assume that it also satisfies $a_k$, for $k <n$. Thus, you have to prove that $v$ satisfies also $a_n$. Three cases: (i) $a_n \in \Gamma$: obvious; (ii) $a_n \in \Lambda$: obvious; (iii) $a_n$ is obtained by modus ponens from $a_i$ and $a_j$ ($i,j < n$) and $a_j$ is $a_i \to a_n$. – Mauro ALLEGRANZA Feb 1 '18 at 14:01
• Your proof in the OP is not completely clear, but there are good ideas. Your induction is on what? What is your hypothesis? An your thesis? See my answer for a rigorous proof (actually, my proof is just an expansion of Mauro ALLEGRANZA's comment, we wrote in the same time) – Taroccoesbrocco Feb 1 '18 at 14:38

You want to prove that, given a sequence $\langle a_0, \dots, a_n \rangle$ obtained as you have described (let us call it a derivation) and a truth assignment $v$ that satisfies every member of $\Gamma \cup \Lambda$, then $v$ satisfies $a_n$. The proof is by (strong) induction on $n \in \mathbb{N}$.
So, $n \in \mathbb{N}$ and by induction hypothesis we suppose that $v$ satisfies $a_k$ for all $0 \leq k < n$. There are two cases, according to the definition of derivation:
1. either $a_n \in \Gamma$ and then $v$ satisfies $a_n$ by hypothesis;
2. or $a_n \in \Lambda$ and then $a_n$ is a logical axiom, that is a tautology, hence every truth assignment satisfies $a_n$, in particular $v$ does it;
3. or $a_n$ is obtained by modus ponens from two earlier formulas in the sequence, that is, for some $0 \leq i, j < n$, we have $a_j = a_i \to a_n$; by induction hypothesis, $v$ satisfies $a_i$ and $a_j$. According to the truth table of $\to$, when $a_i$ and $a_i \to a_n$ are both true, by necessity $a_n$ is true. Therefore, $v$ satisfies $a_n$.
• For second case when $a_n\in\Lambda,$ can't we say that since $v$ satisfies every member of $\Lambda$ and $a_n\in \Lambda,$ therefore $v$ satisfies $a_n$? – Idonknow Feb 1 '18 at 14:31
• Yes, this is correct and this is what I wrote. Actually, I gave a little bit more information: I also explained why $v$ satisfies any member of $\Lambda$. Note that your hypothesis does not say that $v$ satisfies $\Lambda$, so you should explain in the proof why $v$ satisfies $\Lambda$. – Taroccoesbrocco Feb 1 '18 at 14:43
• I thought my hypothesis is $v$ satisfies every member of $\Gamma\cup\Lambda?$ Since $\Lambda\subseteq \Gamma\cup\Lambda,$ wouldn't this imply that $v$ satisfies every member of $\lambda?$ – Idonknow Feb 1 '18 at 14:51
• @Idonknow - Since $\Lambda$ is a set of tautologies, it is useless (but not wrong) to suppose that the assignment $v$ satisfies every member of $\Lambda$, because by definition of tautology all the assignments (in particular, $v$) satisfy every member of $\Lambda$. You are supposing something that is true by definition: there is no in doing that, it is correct and it will work but there won't be any benefit from it. Anyway, it is just a detail in the proof. – Taroccoesbrocco Feb 2 '18 at 15:26