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

  • $\begingroup$ 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^*$?} $\endgroup$ – YoTengoUnLCD Jan 20 '16 at 20:40
  • $\begingroup$ @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? $\endgroup$ – Noah Schweber Jan 20 '16 at 21:08
  • $\begingroup$ 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$ ? $\endgroup$ – YoTengoUnLCD Jan 20 '16 at 23:40
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Jan 20 '16 at 23:45
  • $\begingroup$ 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. $\endgroup$ – YoTengoUnLCD Jan 20 '16 at 23:51

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.