false

Class Notes
(836,221)

United States
(324,393)

Philosophy
(46)

1002
(23)

James Hildebrand
(23)

Lecture

Unlock Document

Philosophy

1002

James Hildebrand

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 1002

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.