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!
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.
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
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?
Well, we can't assume it. Natural deduction rules will always look quite different than proof tree rules - the systems handle disjunction and the arrow very differently, for example. What we can do is prove that any proof in one system can be done in the other, and vice versa. To do that, you'd use proof by induction on the length of the proof (in one system), assuming that shorter proofs can be done in the other, and showing that, whatever you achieve by adding a step in the 1st system can also be done in the 2nd system.
@@AtticPhilosophy Fair enough, it just occurred to me that there might be a way of showing equivalence of rules which seems doable in some cases ( like reiteration in ttree premises; reitieration we can get by tautology of "A and A" for any sentence in the premises.. and then with decomposition, we have reiteration..) but very difficult or impossible in others- as in the case of disjunction introduction for example. Also, to assume anything that can be proven in a ttree system can be proven in a natural deduction system and vice-versa would also assume completeness and soundness and expressive equivalence (ability to build all the equivant sentences) of both systems?
@@pfroncole1 You don't need to assume soundness or completeness to show 2 deductive systems are equivalent. If they're close systems, it's probably quicker to show they're equivalent (ie anything provable in one is provable in the other), then show soundness & completeness for one. Then you get soundness & completeness for the other for free.
If that is the assumption of "close" (1 rule of difference) , then all we need do is to show/work with the situation of exactly 1 difference in rules of inference between the Ttree method and some system of natural deduction?
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 hole......ps: 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.
I'm not quite sure what you're asking. There's no contradiction here. We typically prove completeness by contraposition: consistent sets of sentences have a model.
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.
If Fa is not in a proof by assumption, premises or EI, how else can it have appeared except by UI? Barring those 3 possibilities, it seems XFx and Fa are logically equivalent ?
@@pfroncole1 The point is, those conditions needn't hold, which is why they aren't equivalent. Equivalent sentences take the same value, whatever the conditions.
Right, there are various counter examples to Fa > XFx.. so no equivalence.. but still, how is it possible then for the modeling of Fa to model XFx? Well, unless Fa can be shown to be completely arbitrary? And coming up a tree, how to do it? If Fa and Xfx were equivalent, then it's a matter of complexity as in proposition logjc..
![[Gegagedigedagedago] NEW Help Gegagedigedagedago Nugget escape from Nikocado Avocado Challenge](http://i.ytimg.com/vi/hJWnwRC2Fz8/mqdefault.jpg)
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!
The quality of your video is astonishing and your knowledge is genuienly helpful, please keep it up!
Thanks, I'll try!
Limits of incompleteness would be helpful as a contextual & philosophical limit to these smaller statements.
Do you have a tip jar or any other means to show my appreciation for your videos with some sort of remuneration?
I do, ko-fi.com/atticphilosophy, thanks for considering! (I should add this link to old videos, thanks for the reminder!)
Can you also make a future video on proving completeness of natural deduction?
Completeness in natural deduction is a real pain! I can have a go at a video, but it's something I hate teaching (and the poor students ...) !
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.
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
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?
Well, we can't assume it. Natural deduction rules will always look quite different than proof tree rules - the systems handle disjunction and the arrow very differently, for example. What we can do is prove that any proof in one system can be done in the other, and vice versa. To do that, you'd use proof by induction on the length of the proof (in one system), assuming that shorter proofs can be done in the other, and showing that, whatever you achieve by adding a step in the 1st system can also be done in the 2nd system.
@@AtticPhilosophy Fair enough, it just occurred to me that there might be a way of showing equivalence of rules which seems doable in some cases ( like reiteration in ttree premises; reitieration we can get by tautology of "A and A" for any sentence in the premises.. and then with decomposition, we have reiteration..) but very difficult or impossible in others- as in the case of disjunction introduction for example.
Also, to assume anything that can be proven in a ttree system can be proven in a natural deduction system and vice-versa would also assume completeness and soundness and expressive equivalence (ability to build all the equivant sentences) of both systems?
@@pfroncole1 You don't need to assume soundness or completeness to show 2 deductive systems are equivalent. If they're close systems, it's probably quicker to show they're equivalent (ie anything provable in one is provable in the other), then show soundness & completeness for one. Then you get soundness & completeness for the other for free.
@@AtticPhilosophy I assume "close" means the 2 systems share, effectively, most rules of inference?
If that is the assumption of "close" (1 rule of difference) , then all we need do is to show/work with the situation of exactly 1 difference in rules of inference between the Ttree method and some system of natural deduction?
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 hole......ps: 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.
I'm not quite sure what you're asking. There's no contradiction here. We typically prove completeness by contraposition: consistent sets of sentences have a model.
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.
Sort of, in propositional logic, if you read branching as disjunction. But not in FOL trees: eg AxFx isn’t equivalent to Fa.
But under very specific conditions AxFx can be inferred from Fa, so under those restrictions, they would be equivalent it seems
If Fa is not in a proof by assumption, premises or EI, how else can it have appeared except by UI? Barring those 3 possibilities, it seems XFx and Fa are logically equivalent ?
@@pfroncole1 The point is, those conditions needn't hold, which is why they aren't equivalent. Equivalent sentences take the same value, whatever the conditions.
Right, there are various counter examples to Fa > XFx.. so no equivalence.. but still, how is it possible then for the modeling of Fa to model XFx? Well, unless Fa can be shown to be completely arbitrary? And coming up a tree, how to do it? If Fa and Xfx were equivalent, then it's a matter of complexity as in proposition logjc..