How to Prove Completeness | Logic tutorial | Attic Philosophy

The completeness theorem says that we can prove all the genuine entailments. Saying that a proof system is complete means that, if premises X logically entail some conclusion C, then you can prove that conclusion C from those premises X.

In this video, I'll show you how to prove the completeness theorem, focusing on the proof tree system. The technique focuses on how to construct a counter-model from a failed proof. This is pretty straightforward in the case of proof trees, where a failed proof will have a finished open branch.

If you're new to these ideas, you might want to watch these background videos first:

00:00 - Intro
01:08 - Completeness is holistic
02:02 - Completeness and satisfiability
04:06 - Finished open branches are satisfiable
04:52 - The overall strategy
05:50 - Building the model
07:09 - An important clarification
08:16 - The model satisfies the open branch
09:43 - The base case: atomic (and negated atomic) sentences
11:45 - The complex sentences
12:10 - Inductive hypothesis
13:22 - Case 1: conjunction
15:32 - Case 2: disjunction
18:07 - Finishing the proof
19:08 - Proof by induction?
19:36 - Wrap up

If there’s a topic you’d like to see covered, leave me a comment below.

Links:

Get in touch on Social media!

#logic #philosophy #proof

[AtticPhilosophy]

Proving the completeness theorem looks complex at first, but at its core there’s a very simple idea: use a failed proof to build a counter-model. Any questions on how this works? Leave me a comment below!

[gioi.]

The quality of your video is astonishing and your knowledge is genuienly helpful, please keep it up!

[jonc]

Limits of incompleteness would be helpful as a contextual & philosophical limit to these smaller statements.

[pfroncole]

Here's my understanding of this proof: 1) Consider an open branch, there's no Y ^ ~Y on the branch or the branch would not be open. 2) In the case of 0 -connective sentences, by 1) they all model. 3) In the cases of sentences of complexity > 0, we use substitutionally equivalent forms of conjunction or disjunction for some sentence forms in the arguments that are not expressed in conjunctions and disjunctions, but ultimately we just use disjunction and conjunction forms by translation to set up the sentences of complexity >0, and work the tree ( the point being that what we need to look at are just and and or forms between nodes) . But in both cases of V and ^, the decomposition of those forms, if both are true (conjunction) or either or both are true (disjunction) then those and or or sentences which are more complex than the sentences of decomposition model by the truth conditions of the decompositions, because if they did not, then there would be NO open branch in any such truth tree (it's easy to overlook that generality and see it as just the case of "some" tree..but it's critical to see it is true of ANY open branch). All good, so now we ask ourselves to consider what the truth of that "means" in terms of trying to show every sentence of any complexity in ANY open branch models (Inductive hypothesis). Well, in the case of a truth tree, we must decompose every sentence until the tree closes or we have decomposed every sentence of complexity > 0. So because our branch is open, it's a tree with every sentence of complexity >0 decomposed, and by that fact we have shown every sentence of complexity > 0 to be modeled by it's less complex decomposition, that, of course, means that the first line of the tree which is a set of the premises and the assumed conclusion is true, and that set gives us the proof we wanted i.e. by showing how the model is made, we showed that there's a proof that comes with it (or you can say by constructing a model of an open branch, we also construct a proof from the relevant model). With the Deduction Theorem, we get (premises ^ conclusion) > ?
Premises > conclusion..or if {X ^ Y ^ Z }> [ (X^Y) > Z ] ... (Again the critical aspect I somehow overlooked -and it is key to the whole proof to get it right-- as being true of ANY open branch is if A and B but ~A or ~B, then we have a closed branch by A^B but -A or - B but our assumption is it is open.. Similarly if X v Y but we have ~X ^ ~Y of ANY decomposition, then we close our branch, BUT the branch is assumed open. So decompositions on an open branch have to stay open, so they have to model the sentence of greater complexity they decompose from.
I think the more traditional way of saying this in terms of induction is : 0 complexity is < than 1, so any complexity of 1 (in an open branch) models, complexity 1 is < complex than complexity 2 so complexity 2 is true/models... complexity n< complexity n+1 so all complexities of the tree mosdel and the set of premises and conclusion are modeled and form a proof.

[Nicoder]

Can you also make a future video on proving completeness of natural deduction?

[seandegan]

Do you have a tip jar or any other means to show my appreciation for your videos with some sort of remuneration?

[pfroncole]

Essentially truth tree rules and their decomposions are logical equivalents, so we can build any tree upward or downward and that, of course, includes all branches. So assuming an open branch, we can build the whole branch from o complexities to premises and Ra (which is, really, just another premise. Now what do we have when we have finished reconstruction of that arbitrary branch? Well, that is by definition, a proof.

[pfroncole]

BTW, something almost never mentioned.. we hear all the time that one can assume "any" wff.. but why? Well implicit in any truth bivalent logic system is the tautology Y v -Y, so we choose either and the branching models the tautology

[pfroncole]

Here's an interesting question: having proven by the truth tree method that soundness and completeness are logically equivalent, can we then not just assume that any system based on natural deduction that, effectively uses the same rules of inference as the truth tree method, is therfore sound and complete?

[jupironnie]

Comment: You have packed 20 years of maths logic from 1900s till 1920s (from Hilbert challenge to show completeness in PL). There is a lot in here to digest. Anyway, the path have been indicated. thx
Question: The proof is basically showing a contradiction. If Induction is considered an Axiom, it shows it shows Induction is not a tautology. Or am i going into another Rabbit I still find irrationality proof of root of 2 not convincing as the lowest common factor is not a property of a ratio ( 1/2 is the same as 5/10). It is not possible to differentiate one from the other using words. Probably needs a different maths formula than a verbal statement.