false

Class Notes
(834,669)

United States
(323,859)

Philosophy
(46)

2250
(23)

James Hildebrand
(23)

Lecture

Unlock Document

Philosophy

2250

James Hildebrand

Spring

Description

The Decidability of the Tree Method for SL
Introduction
The tree method is a decision procedure for sentential logic. It is supposed to tell us
whether or not a set of sentences of SL is truth functionally consistent. But is it a good decision
procedure? Will it always give us an answer? (That is, will the tree for any finite set of
sentences always turn into either a closed tree or a tree with a completed open branch? or
might some trees go on forever without ever reaching a conclusion?) Supposing that the tree
method does always give us an answer, will that answer always be the cor
rect one?
I have claimed that if a set is t-f inconsistent the tree for that set will always close. I have
also claimed that if a tree has a completed open branch, the truth value assignment or
assignments we can recover from this branch will always make all the set members true and so
prove the set to be t-f consistent. But how do we know this for sure? What assures us that no
truth functionally consistent set can have a closed tree and that no t-f inconsistent set can have
a tree with a completed open branch? Indeed, what assures us that the tree for a set will
always turn into either a closed tree or a tree with a completed open branch?
Unless we can be assured that the tree method will not fail in any of these ways (it will not
fail to give us an answer; it will not say “yes” when it should say “no”; it will not say “no” when it
should say “yes”) we cannot be assured that the tree method is a good decision procedure.
Proving that the tree method is good in the first of these ways (every tree will either become
a closed tree or produce a completed open branch after a finite number of steps) is
referred to
as proving that the tree method is decidable (that is, that it always gives us a yes or no decision,
regardless of whether that decision is right or wrong).
Proving that the tree method is good in the second of these ways (if the tree is closed the
set is always t-f inconsistent) is referred to as proving that the tree method is sound. If the tree
method tells us that a set is t-f inconsistent, it really is t-f inconsistent.
Proving that the tree method is good in the last of these ways (if the set is t-f inconsistent
the tree is always closed) is referred to as proving that the tree method is complete. All the t-f
inconsistent sets that there are to be found get found by the tree method.
Proof of the Decidability of the Tree Method
To say that the tree method is decidable is to say that the tree for any finite set of
sentences will always reach a verdict. The tree will either become a closed tree or a tree with a
completed open branch, rather than go on forever without reaching a decision. Tree branches
will not become infinitely long, trees will not grow infinitely bushy, and branches that are about to
close will not continually sprout new branches that will require continually more work.
The proof of this result is straightforward and consists of two parts.
Part I
First, note that if a tree were to go on forever, it would have to contain infinitely many
sentences (either infinitely many different sentences, or infinitely many repetitions of the same
sentences or sequence of sentences). But the only way a tree could contain infinitely many
sentences is if it has at least one infinitely long branch. To see why this must be the case we
make a temporary modification to the tree method: We require that on each line of a tree a
decomposition rule be applied on each open branch, even if it is not the same one — we do not
consider unfinished branches to drop down for lines at a time with no sentences simply so that
we can write a unique justification on each line. (This is a permissible modification because
justifications are not strictly part of trees.)
To return to our project of proving that a tree with infinitely many sentences on it must have
at least one infinitely long branch, note first that all the branches grow out of a common trunk at
the top of the tree. There must be at least one sentence on this trunk, at line 1, and if there are infinitely many sentences on the tree this sentence must itself have infinitely many sentences
below it (because an infinite number minus one is still an infinite number).
I now maintain that if, on any line, line k, there is at least one sentence, P, that has infinitely
many sentences below it, then on the next line, line k+1, there will also have to be at least one
sentence that has infinitely many sentences below it. This is because i) the branch P is on
cannot be a closed or completed open branch (otherwise P would not have infinitely many
sentences below it); ii) we have stipulated that on each line a tree decomposition rule must be
applied to some sentence on the branch P is on, so one must be applied on line k; and iii) the
application of a tree decomposition rule to P or to any sentence higher up on the branch that P
is on will add at most two branches below P. If P has infinitely many sentences below it, but the
sentences heading off each of these two branches do not, then P could not have infinitely many

More
Less
Related notes for 2250

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.