Monday, July 2, 2018

proof verification - Use induction to show that a truth assignment on $GammacupLambda$ 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?


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...