1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I can't read the last paragraph, there is a typo in some LaTeX command. Please, fix it. $\endgroup$ – Taroccoesbrocco Feb 1 '18 at 13:48
  • 1
    $\begingroup$ 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$. $\endgroup$ – Mauro ALLEGRANZA Feb 1 '18 at 14:01
  • $\begingroup$ 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) $\endgroup$ – Taroccoesbrocco Feb 1 '18 at 14:38
2
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Idonknow Feb 1 '18 at 14:31
  • $\begingroup$ 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$. $\endgroup$ – Taroccoesbrocco Feb 1 '18 at 14:43
  • $\begingroup$ 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?$ $\endgroup$ – Idonknow Feb 1 '18 at 14:51
  • $\begingroup$ @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. $\endgroup$ – Taroccoesbrocco Feb 2 '18 at 15:26

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.