Class Notes (835,108)
United States (324,041)
Philosophy (46)
2250 (23)
Lecture

N11SDComplete - Completeness of SD.pdf

12 Pages
68 Views
Unlock Document

Department
Philosophy
Course
2250
Professor
James Hildebrand
Semester
Spring

Description
THE COMPLETENESS AND DECIDABILITY OF SD INTRODUCTION Besides proving that SD is sound, that is, that it will not allow us to derive sentences that are not t-f entailed by the assumptions they are derived from, we would also like to prove that SD is complete, that is, that if a sentence is t-f entailed by a set of sentences, there must be some way of deriving that sentence from a subset of those sentences. Completeness: If a sentence, P, of SL is truth functionally entailed by a set, Γ, of sentences of SL, then there is some way of deriving P from a subset of the sentences in Γ. Any student who has struggled with the derivations in Chapters 5.3 and 5.4 will eagerly anticipate the proof of this theorem, hoping that its demonstration will at last reveal the secret method for effortlessly and faultlessly doing any derivation. Alas, all such hopes are bitterly disappointed by Chapter 6.4. Chapter 6.4 mentions that there are “constructive” completeness proofs (that is, proofs given by providing an algorithm — a mechanical sequence of steps — for deriving the conclusion of any valid argument from its premises). However, the authors frustratingly propose to neglect that option and instead give a “non-constructive” proof. Though they do not say so, there is a good reason for this policy (other than keeping the fun in derivations by forcing students to continue to rely on their own ingenuity in coming up with answers to derivation questions). The constructive completeness proof is not “intrinsic.” That is, it has the fault of appealing to something other than features of SD to prove that SD is complete. The proof consists in arguing that there is a systematic way of converting the sentences that appear on the closed tree for any t-f inconsistent set, Γ ∪ {~P} into a derivation of P from Γ in SD. This allows us to derive the completeness of SD as a corollary of the completeness of the tree method. Whatever practical advantages such a proof might have in enabling us to program machines to do derivations, it is tantamount to abandoning the effort to prove that there is something about SD itself that makes it complete. In contrast, the non- constructive proof given in Chapter 6.4 involves a style proof (named after its inventor, Henkin) that crops up in various contexts in meta-logic. This makes it worthwhile to become acquainted with the Henkin proof for other reasons than just being satisfied that SD is complete. That having been said, the Henkin-style proof of Chapter 6.4 has some perplexing features — features that can make students balk at accepting some of its claims. Moreover, it is so intricate that it is easy to lose track of what is going on. Most frustratingly, the text omits to state the fundamental insight that guides the progress of the proof, so that even those who follow the argument can be left feeling that they have lost sight of the forest for the trees — that even though they can follow the proof step by step, they are still left without any real understanding of what it is that makes SD complete. In these notes I focus, first, on stating that fundamental insight and then on presenting a large scale overview of the proof — one that I hope will be both more intuitively appealing and easier to follow. I then turn to address some of the proof’s more perplexing features. HENKIN COMPLETENESS The fundamental insight that guided our proof of the soundness of SD was the idea that the derivation rules were designed to ensure that the property of being truth functionally entailed by the set of open assumptions gets carried down from line to line of a derivation in SD. The fundamental insight that guides the Henken completeness proof is that the derivation rules were designed in such a way as to ensure that the conditions under which sentences can be admitted into a non-contradictory set mimic the conditions under which the truth value T can be assigned to the sentences in that set. This means that any set that is non-contradictory (that is such that a contradiction cannot be derived from it using rules of SD) must also be truth functionally consistent. As it turns out, this suffices to prove that SD is complete. In fact, it is an alternative way of stating the completeness theorem. So much for the basic insight behind the proof. I now turn to describe how the proof proceeds. I just said that, rather than directly prove that if a set, Γ, t-f entails a sentence P then there is a way of deriving P from Γ in SD, Chapter 6.4 sets out to prove an equivalent result: that if a set is non-contradictory or, as the textbook puts it, “consistent in SD” (which just means that you cannot derive a contradiction from it using the rules of SD), then it must be truth-functionally consistent. Completeness (Henkin version): If a set, Γ is non-contradictory, then it is t-f consistent. The first thing we need to understand is why the Henkin version of the completeness theorem is in fact equivalent to the version stated at the outset of this set of notes. We will then turn to look at how the Henkin version is proven. The equivalence of the two versions of the completeness theorem is easily proven. Recall that a set, Γ, t-f entails as sentence, P, if and only if Γ ∪ {~P} is t-f inconsistent. (Half of this is proven in Ch. 3.6 on page 113, and the other half in the solutions manual solution to exercise 3.6E #1c.) As noted at the close of the class notes on advanced SD, a similar relation holds in SD. A sentence, P, is derivable from a set, Γ, if and only if Γ ∪ {~P} is contradictory. (Proven in the answers to exercises in the class notes on advanced SD) This means that to say “if Γ t-f entails P then Γ yields P in SD” is really the same as saying “if Γ ∪ {~P} is t-f inconsistent then Γ ∪ {~P} is contradictory.” But that in turn means that if Γ ∪ {~P} is non-contradictory, then Γ ∪ {~P} must be t-f consistent (because if it wasn’t t-f consistent — if it was t-f inconsistent — it would have to be contradictory). The Henkin version of the completeness theorem says that this holds of any set, not just for those sets consisting of a set of premises united to the unit set of the negation of a conclusion. So if this more general claim can be proven we will also have proven the more specific claim that if those sets made by uniting the premises of an argument to the negation of its conclusion are non-contradictory, then they are t-f consistent. Here is a schematic representation of the relations between these claims: 1. If Γ t-f entails P then Γ yields P in SD Ú Ú 2. If Γ ∪ {~P} is t-f inconsistent then Γ ∪ {~P} is contradictory Þ Ý ~ Ý Þ 3. If Γ ∪ {~P} is non-contradictory then Γ ∪ {~P} is t-f consistent The claims all mean the same thing. The first half of claim 1 means the same thing as the first half of claim 2, the second half of claim 1 means the same thing as the second half of claim 2, and claim 2 means the same thing as claim 3. So proving any one of the three proves the others. Chapter 6.4 sets out to prove a generalized version of the clai m 3 and thereby claim 1. BRIEF COMPLETENESS PROOF As always when you want to prove that a conditional sentence (in this case, if Γ is non- contradictory, then it is t-f consistent), you begin by supposing the antecedent and then try to show that accepting this supposition compels you to accept the consequent. So we suppose that a set, Γ, is non-contradictory and then show that this supposition compels us to accept that Γ must be t-f consistent as well. To prove that a set is t-f consistent, you have to find a truth value assignment on which all the sentences in that set are true. A truth value assignment, in turn, is defined by the way it assigns T’s and F’s to the different atomic sentences of SL. To come up with such an assignment (and this is the characteristic feature of Henkin-style proofs) we “expand” Γ into what is called a maximally non-contradictory set. We add sentences one after another into Γ, on the condition that doing so does not make the expanded set we are constructing contradictory. Sentences that would make our set contradictory do not get added in. This generates a set that contains as many sentences as it could possibly contain without becoming contradictory. (As discussed in more detail in the notes on the compactness of SL, when we expand Γ into a maximally non-contradictory set, we are careful to follow an enumerative order that gives every one of the sentences of SL a place on an infinitely long list. This ensures that we don’t miss any sentences — that we don’t pick forever from the infinitely many sentences of SL in such a way that we never pick certain sentences, as would happen if you only ever picked even numbered sentences and never picked any odd ones.) As it turns out, when we consider such a maximally non-contradictory set, Γ*, and when we consider the restrictions that the individual derivation rules place on what sorts of sentences can be excluded in and excluded from it, we are put in a position to argue that it cannot contain both an atomic sentence and the negation of that atomic sentence, that it can contain a conjunction if and only if it contains both conjuncts, that it can contain a disjunction if and only if it contains at least one of its disjuncts, that it can contain a conditional if and only if it either does not contain its antecedent or does contain its consequent, and that it can contain a biconditional if and only if it either contains both of its immediate components or does not contain either of them. In other words, the conditions concerning what sort of sentences the derivation rules allow us to admit into Γ* mimic the semantic rules for the connectives. This puts us in a position to argue by mathematical induction on the number of connectives in sentences, that the truth value assignment, α*, that assigns a T to all the atomic sentences in Γ* and an F to all the other atomic sentences must make all and only those sentences that are contained in Γ* true. This means that Γ* must be t-f consistent, from which it follows that Γ, around which Γ* was written, is t-f consistent as well. In somewhat more detail, here is a sketch of the entire argument: 1. Suppose: Aset, Γ, of sentences of SL is non-contradictory. 2. Then it is possible to take each of the infinitely many sentences of SL, P , P , 1 2 P 3 … from first on (in the order specified on pp. 268-269 and discussed in connection with the notes on the compactness of SL) and form the infinite series of sets, Γ 1 Γ 2 Γ3, … such that: - Γ1is Γ. - If Γ ∪ {P } is non-contradictory, then Γ is Γ ∪ {P }; otherwise Γ =Γ . 1 1 2 1 1 2 1 - In general, if Γk∪ {P k is non-contradictory, then Γ k+1is Γk∪ {P }k otherwise Γ k+1Γ k 3. Now, consider the union, Γ*, of all these sets. 4. Γ* is non-contradictory (so it is not possible to derive a sentence and its negation from Γ*). 5. It is also maximally non-contradictory (so there is no sentence not already in Γ* that could be added to it without making it contradictory). From (4) and (5), it is possible to argue that: - Γ* cannot contain an atomic sentence and its negation - Γ* can contain a conjunction if and only if it contains both conjuncts - Γ* can contain a disjunction if and only if it contains at least one of its disjuncts - Γ* can contain a conditional if and only if it either does not contain its antecedent or does contain its consequent - Γ* can contain a bicondtional if and only if it either contains both immediate components or does not contain either of them. 6. Now consider a tva, α*, that assigns a T to every atomic sentence in Γ* and an F to every atomic sentence not in Γ*. 7. By appeal to the clauses of (5), and to mathematical induction on the number of occurrences of connectives in sentences of SL, α* must assign a T to every sentence in Γ* and an F to every other sentence of SL. 8. Since Γ is a subset of Γ*, all the sentences in Γ are true on α*. 9. So Γ is t-f consistent. 10. Soif Γ is non-contradictory, then it is t-f consistent. 11. Soi,f Γ is t-f inconsistent, then it must be contradictory. 12. In particular, if a set, Γ ∪ {~P} is t-f inconsistent, then that set must be contradictory. 13. But this means that if Γ t-f entails P then Γ must yield P in SD. The most questionable parts of this argument are the consequences drawn from line 5 and line 7. (The clams at lines 4 and 5 also need justification, but they are intuitively plausible so their justification is postponed here.) Before getting to that, however, there is a claim made at line 2 that many students balk at accepting. This problem is discussed below, after which I return to the explanation of the proof. DETERMINING NON-CONTRADICTION IN SD We have learned that SD was designed just to prove derivability and specific special instances of derivability — derivability of a contradiction, interderivability, and derivability from the empty set. SD was not designed to prove “non-derivability.” In particular, it was not designed to prove that sets are non-contradictory, which has to do with the impossibility of deriving a contradiction from a set using rules of SD. There is no way to use SD to prove that a contradiction is not derivable. We can use SD to prove that a contradiction is derivable by deriving a contradiction. But if we cannot derive a contradiction from a set of initial assumptions, it does not prove that the set must be contradictory. That is because there may be a way to derive a contradiction from the set that we are just not clever enough to figure out. The presence of a derived contradiction demonstrates beyond any doubt that the set is contradictory. But the absence of a derived contradiction may simply be due to lack of ingenuity and not to the set actually being non-contradictory. Yet line 2 of the completeness proof presupposes that there is something that determines whether or not the addition of a sentence to a set produces a larger set that remains non- contradictory. (Line 1 does too, but there the claim is made only as an assumption.) Fortunately, our prior proof of the soundness of SD puts us in a position to say what determines whether or not a set is non-contradictory without having to appeal to the impossibility of deriving a contradiction from that set using the rules of SD. According to the soundness proof, if a sentence, P, of SL is derivable from a set of sentences of SL, Γ, then Γ truth functionally entails P. By the equivalences discussed earlier, this means that if Γ ∪ {~P} is contradictory, then Γ ∪ {~P} must be truth functionally inconsistent. And that means that if Γ ∪ {~P} is not truth functionally inconsistent — if it is t-f consistent — then there is no way that Γ ∪ {~P} could be contradictory (because if it was, it could not be t-f consistent). Γ ∪ {~P} must be non-contradictory. So if we are wondering whether a set is non-contradictory, all we need to do is a truth table, short truth table, or tree to find out whether it is t-f consistent. If it is, then our soundness proof assures that it must also be non-contradictory — that there can be no way of deriving a contradiction from it using rules of SD. Of course, if it isn’t t-f consistent, then it remains for the moment a question whether it is also contradictory. That is precisely the question of the completeness of SD which we are now trying to resolve. Going in the other direction, however, poses no problems. DETAILS OF THE COMPLETENESS PROOF Let’s turn to see how we might justify the specific claims that are taken to follow from line 5. Note that these are not semantic claims (about how truth values are assigned), even though they look very much like semantic claims. I restate the claims below, using the symbol “∈” which means “is a member of” and the symbol “∉” which means “is not a member of.” The five claims are prefaced by an initial, general claim which is used in the proof of each of the others. 1. If P is derivable from Γ in SD and Γ* is a maximally non-contradictory superset of Γ, then P ∈ Γ*. 2. ~ P ∈ Γ* if and only if P ∉ Γ*. 3. P & Q ∈ Γ* if and only if both P ∈ Γ* and Q ∈ Γ*. 4. P v Q ∈ Γ* if and only if either P ∈ Γ* or Q ∈ Γ*. 5. P ⊃ Q ∈ Γ* if and only if either P ∉ Γ* or Q ∈ Γ*. 6. P ≡ Q ∈ Γ* if and only if either P and Q are both ∈ Γ* or neither is. Of these 6 claims, 1 and 2 are the most fundamental. Once they have been established, the others follow quite readily. Proof of claim 1: Suppose some subset, Γ of a maximally non-contradictory set, Γ*, yields a sentence P in SD. And now suppose, contrary to what we want to establish, that P ∉ Γ*. In that case, since P must have some enumeration number, k, Γ ∪ {P} must have been found to k be contradictory when Γ* was constructed (that is the only way P could end up not being in Γ*). But then Γ ∪ Γ kust be contradictory as well (because if we start off a derivation with the initial assumption, first, of the sentences contained in Γ and, second, of those contained in Γ we will k be able to derive P from the initial assumptions drawn from Γ — because by hypothesis Γ yields P, and we know that once we have done that P, together with the initial assumptions drawn from Γ yield a sentence and its contradiction in SD — because as we have seen Γ ∪ {P} is k k contradictory). However, Γ ∪ Γ iska subset of Γ* (because Γ is defined to be a subset of Γ* and Γkis one of the sequence of sets whose union is Γ*, so neither of these sets can contain any sentences not in Γ*). But if a set is contradictory, any superset of that set must be contradictory as well (because adding more sentences into the set won’t change the fact that a sentence and a contradiction can be derived from it). That means that Γ* would have to be contradictory. But we know that Γ* is non-contradictory. Since we have been led into a contradiction by supposing that P ∉ Γ* we can’t make that supposition. If we suppose that some subset, Γ of a maximally non-contradictory set, Γ* yields a sentence P in SD, then we must accept that P ∈ Γ*. Proof of claim 2: (Since this is a biconditional it must be proven in both directions.) So, to begin, suppose that ~P ∈ Γ*. And suppose, contrary to what we want to prove, that P is also ∈Γ*. Then Γ* contains a finite subset, {P, ~P}. But {P, ~P} is contradictory and for the reason given in the proof of claim 1, if a set is contradictory, any superset of that set must be contradictory as well. This would mean that Γ* is contradictory, which is impossible since it is non-contradictory. So if we suppose that ~P ∈Γ* then we must accept that P ∉ Γ*. Now suppose that P ∉ Γ*. Then P must have some enumeration number, k, and Γ ∪ {P} k must have been found to be contradictory when Γ* was constructed. That is, for some sentence, Q, both Q and ~Q must be derivable from Γ ∪ {P}k But then Γ must ykeld ~P in SD, as shown by the following argument sketch (imagine the sketch to be headed off by the initial assumption of sentences in Γ . k h.+1. ~~ P h.+2. ~P h.+3. ~P h.+ 2, R h.+4. ~~ P h.+ 1, R h.+5. P h.+ 2-3&4, ~E
More Less

Related notes for 2250

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit