MATHEMATICAL LOGIC PHIL 305
Popular in Course
verified elite notetaker
Popular in PHIL-Philosophy
This 7 page Class Notes was uploaded by Cleve Schinner on Monday October 19, 2015. The Class Notes belongs to PHIL 305 at Rice University taught by Richard Grandy in Fall. Since its upload, it has received 8 views. For similar materials see /class/225045/phil-305-rice-university in PHIL-Philosophy at Rice University.
Reviews for MATHEMATICAL LOGIC
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/19/15
Philosophy 305505 Rice University Professor R Grandy Handout K Consequences of the Completeness Theorem We turn to re nements of the Method to obtain what are called decision procedures for sublanguages of PL A decision procedure for a language or sublanguage is a completely speci ed method that produces a correct yes or no answer in a nite amount of time A decision procedure for logical truth of SL is provided by truth tables or by the completeness proof since for that language the process always stops and gives an answer Our method of proving completeness is a little short of being a decision procedure for PL because it does not always produce an answer in a nite amount of time It can be shown that there is no decision procedure for the whole language Church s Theorem but we can show that it provides a decision procedure for some sublanguages The basic insight is that in nite loops are created by having an existential quanti er inside a universal quanti er The existential quanti er requires a new constant to be instantiated and that creates a new potential instance for the universal quanti er which then creates a new existential and so on Put more positively if the Method produces a sentence in standardized form that has only existential or only universal quanti ers then the Method will stop Moreover if in the standardized form the existentials all precede the universals then the Method will also stop For we will rst take instances of all the existentials using n constants if there are n existentials and afterwards we will instantiate the n new constants in the m universals giving nm instances But we will be done then since no more new constants will be added The general principle is that if one quanti er occurs within the scope of another then it cannot be moved in front of the other quanti er You may remember that the scope of a quanti er is the subformula of which it is the main connective We can say two quanti ers are independent if neither is in the scope of the other With this terminology we can notice that for any sentence all of whose quanti ers are independent of each other that they can be brought forward in any order Thus we have a decision procedure for such sentences One signi cant sublanguage that we can show has a decision procedure is the monadic predicate language the language with only oneplace predicates We can do this by showing that every sentence of monadic FL is equivalent to a sentence whose quanti ers are independent We do this by appeal to the reverse of our prenex moves ie by moving quanti ers inward but we use most of the same justi cations as for standard prenex since they are symmetric M First eliminate any conditionals and biconditionals then rewrite bound variables as necessary and push all negations inward Consider now the rst subformula whose quanti er includes a variable other than its own eg VxFx amp Gy Ifthe quanti er is universal and is governing a conjunction then it can be moved or distributed over the conjunction an existential can be moved or distributed over a disjunction Moreover either quanti er can be moved over either connective if the variable does not appear on the other side That is if we have xI V and x does not occur in V then that sentence is equivalent to xI W Note that the dollar sign is only conjunction or disjunction here This still leaves us with a symmetric pair of nasty cases where a universalexistential governs a disjunctionconjunction with the quanti er variable and other variables appear on both sides One instance of the form is VxFx amp Gy v Hx amp Kz which is equivalent to VxFx v Hx amp Gy v Hx amp Fx v Kz amp Gy v Kz Distributing the quanti er over the conjunctions we get VxFx v Hx amp VxGy v Hx amp VxFx v Kz amp VxGy v Kz and moving the second and third quanti ers over disjunctions where x does not occur on one side and deleting the vacuous fourth quanti er we nally get VxFx v Hx amp Gy v VxHx amp VxFx v Kz amp Gy v Kz The steps for an existential governing a conjunction are exactly the same moreover if instead of Gy we had yGy then the same steps would work Thus we can move the quanti ers successively inward sometimes multiplying the number of them but eventually having them only govern their own variable Having done that we have entirely independent quanti ers and after rewriting repeated bound variables we can prenex with all of the existentials rst The Monadic Decision Theorem The Modi ed Method just described provides a decision method for monadic quanti er logic In addition to completeness a number of other implications follow directly or indirectly from our proof For example we can note that our interpretations always use the natural numbers or a subset of them which brings us to The Lowenheim Skolem Theorem If a sentence is true in any interpretation then it is true in one whose universal domain is all or some of the natural numbers Proof If I is true in some interpretation then I is not a logical truth Thus applying the Method to I will not produce a contradiction but instead will produce an interpretation in the natural numbers that falsi es I and makes 1 true This theorem was proved in a weaker form originally by Lowenheim and the proof was improved by Skolem Notice that the theorem talks only about interpretations and we have proved it via a detour through derivations Skolem s proof was more direct Notice also that after our work on monadic logic we know that for monadic sentences the Method will stop after a nite number of steps if we arrange the preneX carefully So we can conclude that if a monadic sentence is true in any interpretation then it is true in a finite one We can also resolve a nagging question that I am sure has been bothering you for weeks Is it possible that an infinite set of sentences is intuitively contradictory but we cannot deduce the contradiction in our system because our derivations are nite This is a specific version of the more general worry that if A is an infinite set then it might be that A l Q but not A if Q We can prove that this does not occur in our language by proving the following theorem The Compactness Theorem If every finite subset of A can be made simultaneously true in some interpretation then so can all of A Proof Begin the Method with the first element of A not its negation and after ten steps add the second element of A Continue the process on the expanded set of assumptions and after twenty steps ten on each sentence add the third and so on No contradiction will ever be reached since it would have to be derived from a finite subset of A and we know that every finite subset does not entail a contradiction since it can be made true But eventually every step that is required for each sentence on the list will be carried out and we will have the ingredients to specify an interpretation that makes all of the sentences on the infinite list true To apply this to our worry about derivations suppose for indirect proof that A if Q but that there is no finite subset A for which A l Q Consider the union of A and Q By our assumption every finite subset is true in some interpretation so by compactness all of A together with Q is true in some interpretation so it is not the case that A l Q Phil 305 Rice University Professor Grandy Soundness Theorem If 1 k GSD6 then 1 k I 6 A special case of the theorem arises when there are no assumptions ie If GSD 6 then I 6 The proof is a recursive proof based on the definition of a derivation The Base Case is if we have a linejustified by quotAssumptionquot In that case the assumptions of the line include the sentence itself so it is trivial that if all the assumptions are true the sentence is true The rest of the proof proceeds through all the other possiblejustifications ie the official rules Sample of Soundness Proof Subcases Our recursive assumption in each case is that earlier lines are entailed by their assumptions We also have proved Non decreasing Assumption Principle NDAP If Am is the set of open assumptions of an open line m and Am11 the open assumptions of a later open line mn then the set Am is a subset of Amm The case of ampI If a line is justified by ampI then the line is of the form 11 amp x and there are previous open lines with 11 and x So the derivation would look something like mnh 1p amp x Let Am Amm and Amnh be the open assumptions of lines m mn and mnh respectively Suppose that all the assumptions Amnh are true in I we will show that it follows that 11 amp x is true in I Since Amnh are all true in I by NDAP all of Am and Amm are true in 1 since they are included in Amnh By our recursive hypothesis Am I 11 and Amm I x so 11 and x are true in I But we now note that 11 x I 11 amp x by definition of truth for amp so 11 amp x is true in I which is what we wanted to show End 0fPr00ff0r amp1 Almost all of the cases for other rules will follow this pattern conditional elimination and both biconditional rules follow it exactly VB is a little more complicated because it requires three previous lines while the remaining rules only use one Thejustification that was based on the definition of truth for amp in the case above will be replaced by a different justification depending on the connective The rule of D I is different because we have changed the assumptions The other two differences are that in VI and EIE the entailments depend on the rule restrictions We will do VI you should see that it is a complication of the pattern above Subproof case for V1 If a line is justified by VI then the line is of the form VX1p and there is an earlier open line with lIJCX for some 3 So the derivation would look something like m IpCX mn VX1p Let Am and Amm be the open assumptions of lines m and mn We know that if the rule was applied correctly 0 does not occur in Am nor in Amm Suppose that all the assumptions Amm are true in I we will show that it follows that VX1p is true in I Let us choose any object call it Edgar from the UD Change 1 so that it assigns Edgar to C and call the new interpretation 1 Since Amm are all true in 1 and C does not occur in any of them they will also be true in 1 By NDAP all of Am are true in 1 since they are included in Amm By our recursive hypothesis Am I 1pcX And so 1pcX is true in 1 If we let dX assign Edgar to X then dX makes 11 true in 1 iff dX makes 1pcX true in 1 by Dragnet Since 1pcX is true in 1 the iff tells us that dX makes 11 true in 1 And since we can make this same argument for every object other than Edgar too we know that all dX make 11 true in 1 So by the definition of truth for V VX1p is true in 1 Finally we argue that since c does not occur in VX1p it will also be true in 1 which is where we wanted to end up End of VI proof Philosophy 305505 Rice University Professor R Grandy Handout I PreneX Normal Form A sentence is in prenex normal form iff every quanti er is in initial position or in other words the scope of all quanti ers is greater than that of any nonquanti er Steps for putting a sentence in preneX normal form 1 Replace biconditionals by disjunctions of conjunctions 2 Rewrite any variables that occur bound by more than one quanti er 3 Move the rst quanti er not in preneX position one step toward the front by the following principles Repeat this step as often as necessary Replace By X9 amp l X9 amp l 9 amp X l0 X9 amp l X9 v HP X9 v HP 9 v X l X9 v HP 9 gt X l X9 Z l EIX9 3 l0 VX9 Z l VX9 Z l EIX9 3 l0 EIX9 VX9 VX9 EIX9 X is a generic quanti er replacement is the same for both quanti ers Prenex Normal Form Theorem For any sentence of PL there is a provably equivalent sentence in prenex normal form Proof A recursive proof using the facts above and the Replacement Theorem
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'