Class Notes (834,669)
United States (323,859)
Philosophy (46)
2250 (23)
Lecture

N06TreeDecidability - Decidability of the Tree Method.pdf

3 Pages
46 Views
Unlock Document

Department
Philosophy
Course
2250
Professor
James Hildebrand
Semester
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

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