a joint project between

Department of Information Studies - University of Copenhagen

and

Department of Communication and Psychology - Aalborg University

This text has been transcribed by Martin Prior and Peter Øhrstrøm.

Download the PDF of this item Read automatically extracted version of the PDF
Please note that this text is extracted from the PDF, and is as such most likely not styled properly.

Independence-proofs without modelsBy A.N. Prior When Aristotle wishes to show that some pair of premises with a term in common do not yield any syllogistic conclusion, he selects examples to show that they are equally consistent with the relevant A conclusion and the relevant E (and so, since A implies I and E implies O, with the relevant I and O). For example, Every Y is a Z and No X is a Y yield no conclusion (with subject X and predicate Y), for every man is an animal, no horse a man and every horse an animal, but every man

is an animal, no stone a man, and no stone an animal. {2} This is substantially the procedure of

finding counter-examples to proposed inferential forms AEO is invalid, we might say, because Every man is an animal and No horse is a man are true, but the O conclusion with these terms, Some horse is not an animal is false. It has sometimes been felt that this appeal to facts outside logic in order to establish a logical point is illegitimate, and attempts have been made to by-pass it. In the field of syllogistic theory, the most ingenious of these is that of the Saccaeri whose method may be illustrated by this, for AEO in figure 1:- If every AEO Figure 1syllogism is valid, then if every syllogism in Barbara is valid, and no AEO Figure 1 syllogism is a syllogism in Barbara, then some AEO Figure 1 syllogism is not valid {3} (for every AEO Figure 1 syllogism is valid and this syllogism Every syllogism in Barbara is valid, and no AEO Figure1 syllogism is syllogism in Barbara, therefore some AEO Figure 1syllogism is not valid is valid, since it is an AEO syllogism in Figure 1). But every syllogism in Barbara is valid, and no AEO Figure 1 syllogism is in Barbara. Therefore if

every AEO Figure 1syllogism is valid, some AEO Figure 1syllogism is not valid. That is, the hypothesis that every AEO Figure 1syllogism is valid is self-refuting, and therefore false. And in all this no appeal is made to any facts but those of logic. The objection to Aristotles procedure seems to me for various reasons misplaced, but some interest does attach to other procedures when they are {4} [available, and I propose to give two further illustrations, not from syllogistic logic but from another field]. In proving that certain formulae are no derivable from the axioms of a logical calculus by its rules, what is commonly done is to find an interpretation (usually an arithmetical one) under which the axiomatic formulae will have some property, transmitted by the rules, which the formulae under consideration do not possess. For example, if interpret the variables p, q, r, etc. as integers, and interpret C as 1- 1-, the

number CCCpqrCCrpCsb will be an odd one whatever integer its contained variables may

represent, and this property attaches to any formula n if it attaches both to m and to Cmn, but does

This text has been edited by Adriane Rini, Max Cresswell and Peter Øhrstrøm. The original is kept in the Prior collection at Bodleian Library, Oxford, Box 6. The page numbers in the original are put in curly braces. Giovanni Girolamo Saccheri (September 5, 1667 October 25, 1733) The text in [] has been crossed out.

not attach to CpCpq; so CpCpq is not deducible from CCCpqrCCrpCsp by the rule of detachment.

{5} This whole procedure assumes some knowledge of arithmetic, and is essentially similar to the Aristotelian or counter-example procedure. Nor, in many cases, does it seem possible to avoid using some such procedure. Still, in some cases it is, and I append to examples. ukasiewicz has shown that no formula shorter than CCCpqrCCrpCsp shares its property of

sufficing, with substitution & detachment, for the whole classical implicational propositional calculus. He has not shown, however, that there are not other formulae of equal length with this property, so it is worth looking for others. For example, CsCCCpqrCCrpp is in this calculus; is

ukasiewiczs formula derivable from it? Let us try writing Dmn for the most general result (i.e. one with no unnecessary identifications of variables) of detaching n, or a substitution {6} in n, from m, or a substitution in m. We have these deductions: -- 1. CsCCCpqrCCrpp

D1n = 2. CCCpqrCCrpp (for any n)

D21 = 3. CC2ss

D22 = 4. CCCCrppCpqCpq

D23 = 5. CCs22

D24 = 6. CCCpqCCrppCCrpp

Putting Dmn = where no detachment is possible, we may represent further results of detachment by the following table: -- D| 1 2 3 4 5 6

1| 2 2 2 2 2 2 2| 3 4 5 6 3 4 3| 2 4 4 4| 2 5| 2 2 2 2 6| 5 5 5

It is clear that no further detachments can take us outside the set 16 or substitutions {7} in these, so that there ukasiewicz formula, which is not a substitution in any of them, is not deducible. And this has been shown without the use of any arithmetical or other model. [Again, ukasiewicz has shown that there are at least three formulae 11-letter formulae.] Suppose we now use C not for implication but for (material) equivalence. Under this

interpretation, there are 3 formulae, e.g. CCpqCrpCqr, which ukasiewicz has shown to suffice,

with substitution & detachment, for the whole equivalential propositional calculus. Might the formula CCCpqrCrCqp also possess this property? Let us try deducing CCpqCCrpCqr from it. We

may start thus: -- 1.CCCpqrCrCqp

D11 = 2. CCpCqrCpCrq

D12 = 3. CCpCqrCCrqp {8}

D22 = 4. CCCpqrCCqpr

These & later detachments form the following table: -- D| 1 2 3 4

1| 2 3 4 1 2| 4 3 2 1 3| 4 1 2 3 4| 2 1 4 3 There is therefore no way of getting out of the set 1-4, & substitutions in these, by detachment, so CCCpqCCrpCCqr is not provable. [This property, moreover, is preserved, if] Moreover, each of 1-4

can be seen from the table to yield the three others and nothing else. Here again no model has been used.

The text in [] has been crossed out.Numbered pages end at this point. The following are two pages of Priors notes.

[Additional notes.]Jpq = EpFqqJpq = Ep0 × In proving that a formula is not derivable from the axioms of some calculus by its rules, it is usually necessary to give the symbols of the calculus some interpretation which will verify the axioms & rules and falsify the formula under consideration. Sometimes, however, it is possible to establish independence by simply examining the structure of the relevant formulae themselves without giving them any interpretation. To take a simple example: It is clear that [that from the formula CCpCpqCpq alone we cannot deduce we] if by detachment we mean the rule to infer

from and C, we cannot infer anything by substitution & detachment from the formula CCpCpqCpq [as sole axion, except what we obtain by substitution alone. For in order to turn the

antecedent CpCpq into CCpCpqCpq (or a substitution] as sole axiom, except what we obtain by

substitution alone. For if this is our sole axiom, our first detachment must be a self-detachment: but in order to turn the antecedent CpCpq into CCpCpqCpq (or into a substitution in this) we would

have to replace the first p by something of the form C & the second by the plain

corresponding to this, & no one substitution can play both of these roles. So all formulae except

Additional notes. Inserted by the editors. Editors note: it might be Jpq = EpEqq.New page. Page ends.

is an animal, no stone a man, and no stone an animal. {2} This is substantially the procedure of

finding counter-examples to proposed inferential forms AEO is invalid, we might say, because Every man is an animal and No horse is a man are true, but the O conclusion with these terms, Some horse is not an animal is false. It has sometimes been felt that this appeal to facts outside logic in order to establish a logical point is illegitimate, and attempts have been made to by-pass it. In the field of syllogistic theory, the most ingenious of these is that of the Saccaeri whose method may be illustrated by this, for AEO in figure 1:- If every AEO Figure 1syllogism is valid, then if every syllogism in Barbara is valid, and no AEO Figure 1 syllogism is a syllogism in Barbara, then some AEO Figure 1 syllogism is not valid {3} (for every AEO Figure 1 syllogism is valid and this syllogism Every syllogism in Barbara is valid, and no AEO Figure1 syllogism is syllogism in Barbara, therefore some AEO Figure 1syllogism is not valid is valid, since it is an AEO syllogism in Figure 1). But every syllogism in Barbara is valid, and no AEO Figure 1 syllogism is in Barbara. Therefore if

every AEO Figure 1syllogism is valid, some AEO Figure 1syllogism is not valid. That is, the hypothesis that every AEO Figure 1syllogism is valid is self-refuting, and therefore false. And in all this no appeal is made to any facts but those of logic. The objection to Aristotles procedure seems to me for various reasons misplaced, but some interest does attach to other procedures when they are {4} [available, and I propose to give two further illustrations, not from syllogistic logic but from another field]. In proving that certain formulae are no derivable from the axioms of a logical calculus by its rules, what is commonly done is to find an interpretation (usually an arithmetical one) under which the axiomatic formulae will have some property, transmitted by the rules, which the formulae under consideration do not possess. For example, if interpret the variables p, q, r, etc. as integers, and interpret C as 1- 1-, the

number CCCpqrCCrpCsb will be an odd one whatever integer its contained variables may

represent, and this property attaches to any formula n if it attaches both to m and to Cmn, but does

This text has been edited by Adriane Rini, Max Cresswell and Peter Øhrstrøm. The original is kept in the Prior collection at Bodleian Library, Oxford, Box 6. The page numbers in the original are put in curly braces. Giovanni Girolamo Saccheri (September 5, 1667 October 25, 1733) The text in [] has been crossed out.

not attach to CpCpq; so CpCpq is not deducible from CCCpqrCCrpCsp by the rule of detachment.

{5} This whole procedure assumes some knowledge of arithmetic, and is essentially similar to the Aristotelian or counter-example procedure. Nor, in many cases, does it seem possible to avoid using some such procedure. Still, in some cases it is, and I append to examples. ukasiewicz has shown that no formula shorter than CCCpqrCCrpCsp shares its property of

sufficing, with substitution & detachment, for the whole classical implicational propositional calculus. He has not shown, however, that there are not other formulae of equal length with this property, so it is worth looking for others. For example, CsCCCpqrCCrpp is in this calculus; is

ukasiewiczs formula derivable from it? Let us try writing Dmn for the most general result (i.e. one with no unnecessary identifications of variables) of detaching n, or a substitution {6} in n, from m, or a substitution in m. We have these deductions: -- 1. CsCCCpqrCCrpp

D1n = 2. CCCpqrCCrpp (for any n)

D21 = 3. CC2ss

D22 = 4. CCCCrppCpqCpq

D23 = 5. CCs22

D24 = 6. CCCpqCCrppCCrpp

Putting Dmn = where no detachment is possible, we may represent further results of detachment by the following table: -- D| 1 2 3 4 5 6

1| 2 2 2 2 2 2 2| 3 4 5 6 3 4 3| 2 4 4 4| 2 5| 2 2 2 2 6| 5 5 5

It is clear that no further detachments can take us outside the set 16 or substitutions {7} in these, so that there ukasiewicz formula, which is not a substitution in any of them, is not deducible. And this has been shown without the use of any arithmetical or other model. [Again, ukasiewicz has shown that there are at least three formulae 11-letter formulae.] Suppose we now use C not for implication but for (material) equivalence. Under this

interpretation, there are 3 formulae, e.g. CCpqCrpCqr, which ukasiewicz has shown to suffice,

with substitution & detachment, for the whole equivalential propositional calculus. Might the formula CCCpqrCrCqp also possess this property? Let us try deducing CCpqCCrpCqr from it. We

may start thus: -- 1.CCCpqrCrCqp

D11 = 2. CCpCqrCpCrq

D12 = 3. CCpCqrCCrqp {8}

D22 = 4. CCCpqrCCqpr

These & later detachments form the following table: -- D| 1 2 3 4

1| 2 3 4 1 2| 4 3 2 1 3| 4 1 2 3 4| 2 1 4 3 There is therefore no way of getting out of the set 1-4, & substitutions in these, by detachment, so CCCpqCCrpCCqr is not provable. [This property, moreover, is preserved, if] Moreover, each of 1-4

can be seen from the table to yield the three others and nothing else. Here again no model has been used.

The text in [] has been crossed out.Numbered pages end at this point. The following are two pages of Priors notes.

[Additional notes.]Jpq = EpFqqJpq = Ep0 × In proving that a formula is not derivable from the axioms of some calculus by its rules, it is usually necessary to give the symbols of the calculus some interpretation which will verify the axioms & rules and falsify the formula under consideration. Sometimes, however, it is possible to establish independence by simply examining the structure of the relevant formulae themselves without giving them any interpretation. To take a simple example: It is clear that [that from the formula CCpCpqCpq alone we cannot deduce we] if by detachment we mean the rule to infer

from and C, we cannot infer anything by substitution & detachment from the formula CCpCpqCpq [as sole axion, except what we obtain by substitution alone. For in order to turn the

antecedent CpCpq into CCpCpqCpq (or a substitution] as sole axiom, except what we obtain by

substitution alone. For if this is our sole axiom, our first detachment must be a self-detachment: but in order to turn the antecedent CpCpq into CCpCpqCpq (or into a substitution in this) we would

have to replace the first p by something of the form C & the second by the plain

corresponding to this, & no one substitution can play both of these roles. So all formulae except

Additional notes. Inserted by the editors. Editors note: it might be Jpq = EpEqq.New page. Page ends.

18-12-2018 13:49:23 (GMT+1) |