# Completeness of Propositional Logic: Help understanding a proof.

I'm reading through wikipedia's proof of the completeness of propositional logic and I'm having trouble understanding the last parts of the proof:

At part III, why is "if $G^*$ contains $C$ and $C\implies B$ then it contains $B$" true?

At part IV, it is claimed that as $G^*$ is "truth-like" (I've never seen that term before), then there is a valuation (what does $G^*$-canonical valuation mean?) $v$ such that $v(G^*)=\{1\}$, how can we assure the existence of this valuation?

For your first question: suppose $G^*$ contains $C$ and $C\implies B$ - say, they are both in $G_{17}$. Then does $G_{17}\cup\{B\}$ prove $A$? (Basically, show that - whenever the sentence $B$ happened to show up in your enumeration of sentences - it could not be the case that adding $B$ to $G^*$ would yield a proof of $A$. So, we added $B$ to $G^*$.)

As for your second question: "truthlike" is defined in part III:

This means that it contains $C$ only if it does not contain $\neg C$; If it contains $C$ and contains "If $C$ then $B$" then it also contains $B$; and so forth.

The "and so forth" is a bit vague of course; what's really meant is that $G^*$ is complete and closed under deductions: for every $C$ either $G^*\vdash C$ or $G^*\vdash \neg C$, and if $G^*\vdash C$ then $C\in G^*$.

Now the valuation is just $$\nu(C)=1\iff C\in G^*, \quad\nu(C)=0\iff \neg C\in G^*.$$

(It's also important that $G^*$ is consistent, but this is easy to show. If $G^*$ is inconsistent, then some $G_n$ was inconsistent, but then $G_n\vdash A$ since inconsistent theories prove everything. Oops.)

• Thanks for your answer. I have a few questions, truthlike is a different notion to "complete and closed under deductions", could you explain how it follows from the construction of $G^*$ that it is complete and closed under deductions? Also, I think that if $G^*$ is closed and complete, we have that either $p$ or $\neg p$ are in $G^*$ for all the variables $p$, thus the valuation we need is the extension $v_f:\text{Form}\to\{0,1\}$ of the function $$f:\text{Var}\to \{0,1\}, f(p) = 1 \iff p\in G^*$$ But then, how do we show that $v_f$ satisfies $G^*$?} – YoTengoUnLCD Jan 20 '16 at 20:40
• @YoTengoUnLCD For completeness: suppose $C\not\in G^*$. Then by construction of $G^*$, we must have $G^*\cup\{C\}\vdash A$ (do you see why?). Similarly, if $\neg C\not\in G^*$, then $G^*\cup\{\neg C\}\vdash A$. So $G^*\cup \{C\vee\neg C\}\vdash A$, and so $G^*\vdash A$ - a contradiction. For closure under deductions, it's similar: if $G^*\vdash C$, then $G^*\cup\{C\}\not\vdash A$, so $C$ was put into $G^*$ when it was considered ($C=E_n$ for some $n$; since $G^*\cup\{C\}\not\vdash A$, certainly $G_n\cup\{C\}\not\vdash A$!). Does this help? – Noah Schweber Jan 20 '16 at 21:08
• Yes, it helped, thank you a lot. The only leap I could not complete was that $G^* \cup \{C\vee \neg C\}\vdash A\rightarrow G^*\vdash A$: I understand that $C\vee \neg C$ is a tautology, but I still don't get how to prove that implication. Oh, and also, why does $G^*\cup\{C\}\vdash A$ and $G^*\cup\{\neg C\}\vdash A$ imply that $G^*\cup\{C\vee \neg C\}\vdash A$ ? – YoTengoUnLCD Jan 20 '16 at 23:40
• @YoTengoUnLCD The details will depend on the exact way you're formalizing "$\vdash$", but for instance (using sequent calculus) the first point is cut: if $T\vdash x$ and $T\cup\{x\}\vdash y$, then $T\vdash y$. The second is e.g. $\vee L$ in en.wikipedia.org/wiki/Sequent_calculus#Inference_rules. But I guarantee whatever system you're using allows these. – Noah Schweber Jan 20 '16 at 23:45
• In my course, $A \vdash \alpha$ is defined as "there exists a proof of $\alpha$ from $A$ using 3 axioms and MP (this is an example of a proof (my question) math.stackexchange.com/questions/1620203/…), I'll try to use my system to prove those rules. – YoTengoUnLCD Jan 20 '16 at 23:51