PHIL 411 Advanced Logic

LARKIN

__________________________

Metalogic

[For: Richard Jeffrey, Formal Logic: Its Scope and Limits]

I. Formal Logic

A. A system of formal (deductive) logic aims at developing a method for testing whether arguments are valid.

B. As validity is a property of logical structure (not content), the system should provide first a language into which one can translate arguments in ordinary language so as to reveal the relevant level of logical structure. This language is essentially specified by providing:

1. An alphabet—a list of symbols that can be used

2. Rules of formation—rules that determine which strings of symbols count as well-formed formulas (wffs).

3. Rules of Interpretation—rules that determine the allowable ways symbols can be interpreted and under what conditions a wff will be true in an interpretation. These semantic rules determine when a conclusion validly follows from some set of premises.

C. Proof Procedure—Constituted by Rules of Inference, which essentially determine the allowable ways wffs can be manipulated. These syntactic rules determine when some conclusion can be derived from some set of premises.

D. Desiderata

1. In a good system of formal logic, there should be certain relationships between the semantic rules of interpretation and the syntactic rules of inference:

a. Soundness: If some conclusion is derivable from some set of premises, then that conclusion validly follows from that set of premises.

b. Completeness: If some conclusion validly follows from some set of premises, then that conclusion is derivable from that set of premises.

2. In a good system of formal logic the inference rules should provide a method that will pronounce correctly on the validity of any finite argument.

a. Decidability: The method will pronounce on the validity of any finite argument.

b. Soundness: The pronouncements of ‘valid’ will be correct.

c. Completeness: The pronouncements of ‘invalid’ will be correct.

II. Decidability

A. Definitions:

1. A system S decides validity =df For any finite argument A: S will pronounce either that A is or is not valid after a finite number of finitely long mechanical steps.

2. The tree method T decides validity =df For any finite argument A: T will claim either that A is valid or not after a finite number of mechanical (and finitely long) steps.

B. Exhaustive Rules

An inference rule is exhaustive iff applying the rule to a line (input) yields a finite number of smaller lines (output).

C. Basic Decidability Proof

P1: If a tree corresponding to any finite argument A is finished, then it either has an open path or it does not.

P2: If the tree has an open path, then T pronounces A ‘not valid’.

P3: If the tree has no open paths, then T pronounces A ‘valid’.

C1: So if the corresponding tree for A finishes, then T pronounces on the validity of A.

P4: If every rule is exhaustive, then every tree will finish.

P5: Every rule is exhaustive.

C2: So every tree will finish.

C3: So T pronounces on the validity of every finite argument A.

D. Propositional Logic (Ch. 2)

1. Every truth-functional rule of inference is exhaustive.

E. Predicate Logic

1. Generality (Ch. 3):

a. We add QN rules, EI and UI.

b. UI is not exhaustive. Applying UI to a single finite line can yield an infinite number of new lines. So P5 of the basic decidability proof is false for our system of predicate logic.

c. But UI is effectively exhaustive if there are only a finite number of names that can appear in a tree. For then we can instantiate any universal claim to all relevant names in a finite number of applications of UI. All relevant applications of UI to a line will yield a finite number of smaller lines.

d. We can then make the following changes to our basic decidability proof:

P1*: If a tree for A is finished or effectively finished, then it either has an open path or it does not.

C1*: If a tree for A finishes or effectively finishes, then T pronounces on the validity of A.

P4*: If every rule is either exhaustive or effectively exhaustive, then every tree will finish or effectively finish.

P5*: Every rule is either exhaustive or effectively exhaustive.

C2*: So every tree will finish or effectively finish.

2. Multiple Generality (Ch. 4):

a. An existential quantifier within the scope of a universal quantifier can generate an infinite number of names.

b. So when we can have existential quantifiers within the scope of universal quantifiers, UI ceases to be even effectively exhaustive.

c. Thus when we expand our tree system to allow for multiple generality, the system ceases to be able to decide validity. Some finite arguments will be such that the corresponding tree never finishes or effectively finishes. And so some finite arguments will be such that T never pronounces on their validity.

III. Soundness

A. Definition:

1. A system S is sound =df For any finite argument A: if S pronounces A ‘valid’, then A is valid.

2. The tree method T is sound =df For any finite argument A (P1…Pn/\C): if T pronounces a corresponding initial list of claims L (P1…Pn, ~C) ‘inconsistent’ by there being no open paths through a finished tree constructed from L, then L really is inconsistent.

B. Sound Rules

1. An inference rule is sound =df If the input line of the rule is true in some interpretation C, then all of the lines along some output branch are true in C as well.

2. An inference rule is constructively sound =df If the input line of the rule is true in some interpretation C, then we can construct a new interpretation C* such that everything true-in-C is still true-in-C* and all of the lines along some output branch are true-in-C* as well.

C. Basic Soundness Proof

P1: Assume that L is consistent.

P2: Then there is an interpretation C in which all the member of L are true.

P3: If all of our rules are sound, then truth-in-C will ‘trickle down’ along at least one branch every time a rule is applied and so there will be a path P along which all lines are true-in-C.

P4: All of our inference rules are sound.

C1: So, there is a path P along which all lines are true-in-C.

P5: If all lines along P are true in some interpretation C, then P is open (does not contain and formula and its denial).

C2: So, if L is consistent, then there is a path P through a tree constructed from L that is open.

C3: So, if there is no open path P through a tree constructed from L, then L is inconsistent.

D. Propositional Logic: All of our propositional rules of inference are sound.

E. Predicate Logic

1. Our QN rules and UI are sound.

2. EI is not sound.

3. EI is constructively sound.

4. All of the rules that are sound are also constructively sound.

IV. Completeness

A. Definitions

1. A system S is complete =df For any finite argument A: if A is valid, then S will pronounce A ‘valid’.

2. A system S is complete =df For any finite argument A: if S pronounces A ‘not valid’, then A is not valid.

3. The tree method T is complete =df For any finite argument A (P1…Pn/\C): if T pronounces a corresponding initial list of claims L (P1…Pn, ~C) ‘consistent’ by there being some open path P through a finished (or effectively finished) tree constructed from L, then L is consistent.

B. Complete Rules

1. An inference rule is complete =df If all of the lines along some output branch are true in some interpretation C, then the input line is true-in-C as well.

2. An inference rule is path complete =df If all of the lines along some output branch on an open (or infinite) path P are true in some interpretation C determined by P, then the input line on P is true in C as well.

3.

C. Basic Completeness Proof

P1: Assume that there is some open path P through a finished tree constructed from L.

P2: Since P does not contain both a formula and its denial, there is some interpretation C where all atomic formulas and denials of atomic formulas along P are true. (This is an interpretation C determined by P.)

P3: If all of our rules are complete, then truth-in-C will be ‘drawn up’ through all of the lines along P.

P4: All of our rules are complete.

C1: So there is some interpretation C that makes all of the lines along P true.

C2: So if there is some open path P through a tree constructed from L, then there will be an interpretation C that makes all lines along P true.

P5: All the claims of L will lie along P.

C3: So if there is some open path P through a tree constructed from L, then there will be an interpretation C that makes all the lines in L true.

P6: If there is an interpretation that makes all the lines in L true, then L is consistent.

C4: So if there is some open path P through a finished tree constructed from L, then L is consistent.

D. Propositional Logic: All of our propositional rules of inference are complete.

E. Predicate Logic

1. Our QN rules and EI are complete.

2. UI is not complete.

3. UI is path complete.

4. Any rule that is complete is also path complete.

5.

V.