A Reduction in the number of the Primitive Propositions of Logic

From Wikisource
 
Jump to: navigation, search
A Reduction in the number of the Primitive Propositions of Logic  (1920) 
by Jean Nicod
Published in the Proceedings of the Cambridge Philosophical Society 19 (1917–1920), 32–41

A Reduction in the number of the Primitive Propositions of Logic. By J. G. P. Nicod, Trinity College. (Communicated by Mr G. H. Hardy.)

[Received and read 30 October 1916.]

Of the four elementary truth functions needed in logic, only two are taken as indefinables in Principia Mathematica. These two have now been defined by Mr Sheffer[1] in terms of a single new function p|q, "p stroke q." I propose to make use of Mr Sheffer's discovery in order to reduce the number of primitive propositions needed for the logical calculus.

There are two slightly different forms of the new indefinable, for we may treat p|q as meaning the same thing as either \sim p.\sim q, or \sim p\vee\sim q[2]. The definition of \sim p is the same in both cases, namely p|p, while that of p\vee q simply changes from p/q|p/q with the AND-form into p/p|q/q with the OR-form.

However, the best course is for us to define all the four truth-functions directly in terms of the new one. In so doing, we find that, while the definition of \sim p remains the same, and those of p\vee q, p.q simply permute, as we pass from the AND-form to the OR-form, the definition of p\supset q is simpler in the latter form. It is p\mathsf{I}q/q, as against p/p|q\mathsf{I}p/p|q.

The OR-form is therefore to be preferred[3].

Definitions.

\sim p .=. p|p Df. p\vee q .=. p/p|q/q Df.
p\supset q .=. p|q/q Df. p.q .=. p/q|p/q Df.

Remarks on these Definitions.

One ought not to aim at retaining before one's mind the complex translation into the ususal system, "\sim p\vee\sim q," as the "real meaning" of the stroke. For the stroke, in the stroke-system, is simpler than either \sim or \vee, and from it both of them arise. We may not be able to think otherwise than in terms of the four usual functions; it will then be more in accordance with the nature of the new system to think of the |, not as some fixed compound of \sim and \vee, but as a bare structure, out of which, in various ways, \sim and \vee will grow. The above definitions give clear expression to the symmetry between OR and AND; and this, notwithstanding the choice that we had to make between an OR-form, and an AND-form. This is of some interest, because, in general, the very symmetry forces upon us an arbitrary choice, which, in turn, quite obscures the symmetry.

I shall use \overline{q} for q|q whenever convenient. Observe that p|\overline{q}, i.e. p\supset q, forms a natural symbol ┌ for implication, allowing of permutation \overline{q|}p. We may notice in general that the new system brings the four functions into relations far closer than those in Mr Russell's system. For instance in

p/p|p/p.|.p/p
the two propositions p\vee p.\supset.p and \sim p\vee p coincide.

Every stroke-formula falls into two parts on the right and left of a central stem. It will, therefore, add to clearness to use black type[4] instead of dots to indicate the central symbol. Further, slanting strokes are covered by straight ones: thus p/q|p/q stands for (p|q)|(p|q).

The definition of the two primitive notions of the Principia in terms of a single new one tends to reduce the number of the primitive propositions needed. But how far does this reduction actually occur? Does it extend beyond the obvious substitution of "If p and q are elementary propositions, p|q is an elementary prop." (Sheffer, p. 488) for *1·7 and *1·71, stating the same for \sim p and p\vee q respectively? The reduction goes, as we shall presently find, very much farther.

It has first to be said, in order that we may be as precise as possible, that the whole amount gained in applying the stroke-definitions cannot with complete certainty be attributed to them. For Mr Russell's system, as it now stands, has not said its last word in that matter.

Incidentally I found that *1·4, p\vee q.\supset.q\vee p, can be proved by means of the other four, with the unimportant change of *1·3, q.\supset.p\vee q into q.\supset.q\vee p. In "Association," *1·5, write p for r:

p\vee(q\vee p).\supset.q\vee(p\vee p).
The left hand side, by the help of q.\supset.q\vee p and "Summation," will be found to be implied in p\vee q. The right-hand side, likewise, by p\vee p.\supset.p, and "Summation," will be found to imply q\vee p. The result then follows using "Syllogism" (obtained from "Summation" with the transformation \frac{\sim p}{p}[5]).

Let us, however, take Mr Russell's eight propositions in the form given in Principia. It is my object to reduce them to three—two non-formal and one formal—by means of the stroke-definitions given above.

It can be shown, as a first stage, that two formal propositions are enough, namely:

(1) p|p/p.
(2) p|q/q\overline{\mathsf{I}s/q\overline{|p/s}}.
The first proposition is the form of "Identity" (p\supset p) in the stroke-system. It would, at first sight, appear more natural to adopt the order q/s\overline{|p/s} in the left-hand side of (2), since
p|q/q.\supset.q/s\overline{|p/s}
is the syllogistic principle of the stroke-system, giving "Syllogism," p\supset q.\supset:q\supset s.\supset.p\supset s when s|s is written for s.

It will however be found that the inverted order, s/q\overline{|p/s}, is much more advantageous than the normal syllogistic order, q/s\overline{|p/s}. For, owing to this "twist," Identity and (2) yield "Permutation," s/p\overline{|p/s}, which now enables us to eliminate the twist in (2), and revert to the normal order. From the three propositions thus obtained, the rest follow.

This, by the way, illustrates the following fundamental fact. Which form of a given principle is the most general, and contains the maximum assertion, is a function of the symbolic system used. Thus, for instance, in Mr Russell's system,

p.\supset.q\vee p (a)
is more general than p.\supset.q\supset p (b)
since (b) is (a) with \sim q for q. In the stroke-system, on the contrary, p\overline{\mathsf{I}q/q|p/p}, meaning the same thing as (a), is less general than p\overline{\mathsf{I}q|p/p}, whose meaning is that of (b), since it is obtained from it by writing q|q for q.

A further step has to be made in order to be left with only one formal primitive proposition. It consists in adapting to better advantage the form of the primitive propositions to the properties of the stroke-symbolism where implication is concerned. We had above

p\supset q.=.p|q/q Df.
If we look for the meaning of the general form p|r/q, we find this to be \sim p\vee\sim(\sim r\vee\sim q), i.e. p.\supset.r.q. We thus come to the fundamental property that, in the new system, p\supset q is a case of p.\supset.s.q, whereas in Principia the contrary relation of course holds.

This leads us to substitute p|r/q for p|q/q in the "left-hand sides" of both the non-formal rule of implication and the syllogistic proposition (2) above. The reform may be further extended to the proposition (2) as a whole, which might be given in the form P|S/Q instead of P|Q/Q with the proviso, if the proposition is to remain true, that S must be implied in P. Now, for S, write the proposition (1) above, p|p/p; for (as we at this early stage know "unofficially") a true proposition will be implied by everything.

We then have the three primitive propositions of the stroke-system:

Non-
formal
{  I. If p is an elementary proposition, and q is an elementary proposition, then p|q is an elementary proposition[6].
II. If p|r/q is true, and p is true, then q is true.
This is the non-formal rule of implication, *1·1, with the modification just explained.
Formal III. p|q/r\mathsf{I}t|t/t.|.s/q\overline{|p/s.}
I shall call II "the Rule," and III "the Prop."

Remarks on these Primitive Propositions.

Observe p|r/q in II, while p|q/r in III. This alternance will prove essential for the working of the calculus.

In III, I shall use \pi for t|t/t, P for p|q/r, Q for s/q\overline{|p/s,} and shall speak of III as P|\pi/Q.

P|\pi/Q, by the Rule, yields the same result as the syllogistic proposition (2) above, when the left-hand side P is a truth of logic. This restriction of the syllogistic form to its categorical use with an asserted premiss is a peculiar character of the first proofs to follow, and is of some philosophical interest.

One feels inclined to think that III merely asserts together (1) and (2) above. This, view, whatever may be the amount of truth it contains, takes AND too much as a matter of course, and tends to lose sight of (α) the fact that III, as a structure, ist simpler than (2) alone: for III is (2) with t|t/t instead of s/q\overline{|p/s}; and (β) the very real step from p.q to q, together with the philosophical difference between two assertions and only one.

The main steps in the formal deduction are:

1. Proof of "Identity," t|t/t.

2. Passage from P|\pi/Q to the usual implicative form P|Q/Q.

3. Elimination of the twist s/q\overline{|p/s} in Q, and return to the normal order q/s\overline{|p/s}. 4. Proof of "Association," p\overline{|q/r}.\supset.q\overline{|p/s}.

5. Theorems equivalent to the definitions of p.q, p\supset q in Principia.

Proof of Identity, t\mathsf{I}t|t.

As this first proof from a single formal premiss stands in a unique position I shall, without in any way obscuring the precise play of the symbols, expound it after a more heuristic order than is usually followed.

We start with the Prop. P\mathsf{I}\pi|Q, and the Rule enabling us to pass from the truth of P to that of Q; and we have to prove \pi. This can only be reached through some proposition of the form A\mathsf{I}B|\pi, where A is a truth of logic[7]. The proof will thus consist in passing from P\mathsf{I}\pi|Q to A\mathsf{I}B|\pi by some permutative process.

A simple two-terms permutative law s|q\overline{\mathsf{I}q|s,} we do not yet possess. Our Prop. yields only a roundabout three-terms permutation, s|q\overline{\mathsf{I}p|s,} subject to the condition of p\mathsf{I}q|r being a truth of logic[7]. This, however, is enough for our purpose.

In the Prop., write t for p, q, r:

(a) \pi\mathsf{I}\pi|Q_1,
Q_1 being s|t\overline{\mathsf{I}t|s.} Write now \pi for p, q; Q_1 for r: then by (a) and the Rule,
(b) s|\pi\overline{\mathsf{I}\pi|s.}

From (b) in the same manner,

(c) u|\pi/s\overline{\mathsf{I}s/\pi|u.}

This enables us to pass, by the Rule, from P\mathsf{I}\pi|Q to

(d) Q|\pi\mathsf{I}P.

In order to complete the proof of \pi, we need only find some expression which: (α) can be a value for P, i.e. is a case of p\mathsf{I}q|r, and (β) is implied in some truth of logic, say T. For, by T\mathsf{I}P|P, the Prop., and the Rule, as above,

(e) s|P\overline{\mathsf{I}T|s.}

In (e), write Q|\pi for s: first by (d) and the Rule, then by T and the Rule, we obtain T\mathsf{I}Q|\pi, and so

(f) \pi.

Now, Q_1|\pi\mathsf{I}\pi fulfils (α) and (β). For (α) \pi being the complex expression t\mathsf{I}t|t, is a case of the form q|r, and (β) we have, by (c) above, \pi|\pi/Q_1\overline{\mathsf{I}Q_1/\pi|\pi,} and by (a) \pi\mathsf{I}\pi|Q_1.

To obtain the strictest development of the proof we have only to write Q_1/\pi|\pi for P and \pi|\pi/Q_1 for T all through the preceding argument.

Permutation, s|p\overline{\mathsf{I}p|s}

[Gives s\vee p.\supset.p\vee s by \frac{p|p\quad s|s}{p\qquad s}.]

Dem.: Prop.\frac{p\quad p\quad p}{p\quad q\quad r}, Id., and Rule.

Tautology, p/p|p/p\mathsf{I}p/p
i.e. p\vee p.\supset.p

Dem.: Id.\frac{p/p}{p}, Perm., and Rule.

Addition, s\overline{\mathsf{I}p|s/s}

[Gives s.\supset.p\vee s by \frac{p/p}{p}.]

Dem.: By Perm. (twice), \overline{p|s/s\mathsf{I}}s/s|p (a)

By Prop.\frac{\overline{p|s/s}\quad s/s\quad p\quad s}{\;\;p\qquad\;\,q\quad\;\;r\quad s}, ⊢(a), ⊢Id.[8], \overline{p|s/s\mathsf{I}}s

By Perm., result.

Return from Generalised Implication P|\pi/Q to P|Q/Q.

Lemma, p/p\overline{|s/p}

Dem.: By Perm. (twice), \overline{s/p|}p/s (a)

By Prop.\frac{\overline{s/p}\quad p\quad s\quad u}{\;p\quad\;\,q\quad r\quad s}, ⊢(a),

u|p\overline{\mathsf{I}\overline{s/p|}u}

Write p/p for u: by Id. and Perm. (twice), result.

Theorem, P|\pi/Q\overline{\mathsf{I}Q/Q|P}

Dem.: Prop.\frac{Q|Q\quad\pi/Q\quad P}{\;p\qquad q,r\quad s}, ⊢ Lemma, result.

Hence, by Perm., P|Q/Q, i.e.

p|q/r\overline{\mathsf{I}s/q\overline{|p/s}} (S')

Syllogism, p|q/r\overline{\mathsf{I}q/s\overline{|p/s}}

[Gives p\supset q.\supset:q\supset s.\supset.p\supset s for \frac{q\quad s/s}{r\quad\;s\;}.]

Dem.: In this Dem., Permutation is used to correct the twisting action of S', much as handwriting has first to be inverted, if it is to be seen right in a mirror.

By S'\frac{q/s\quad s/q\quad u}{\; p\quad\;\;q,r\quad s}, ⊢ Perm., and Perm.,

\overline{q/s|u\mathsf{I}}u|s/q (a)

By S'\frac{s/q|u\quad u|s/q\quad\overline{q/s|u}}{\;p\qquad q,r\qquad s}, ⊢ Perm., ⊢ a, and Perm.,

\overline{q/s|u\mathsf{I}}s/q|u (b)

By S'\frac{p|q/r\quad s/q\overline{|p/s}\quad\overline{q/s\overline{|p/s}}}{p\qquad\quad q,r\qquad\quad s}, ⊢S', ⊢b, result.

Association, p\overline{|q/r} \overline{\mathsf{I}q\overline{|p/r}}

The structure of the proof is this:

Syll.\frac{p\quad q/r\quad r}{p\quad q,r\quad s}

gives p\overline{|q/r}.\supset:q/r|r.\overline{|p/r.}

We now need only the Lemma q\overline{|q/r|r} for our result to follow by Syll. twice.

Lemma, q\overline{|q/p|p}

The proof of this lemma—call it L—is as follows: We prove (aq|L/L, (bL/L|q/q. From this, by Syll. and Tautol., the result follows.

Dem.: (a) By Syll.\frac{q,p}{r,s},

p|q/q.\supset.q/p\overline{|p/p} (1)

By Add., Syll., ⊢(1),

q.\supset:q/p\overline{|p/p} (2)

The right side of (2) implies, by Syll.,

p/p|p.\supset.q/p|p (3)

By Id., Perm., Add.\frac{p/p|p,\quad q}{\quad p,\qquad q},

q.\supset:p/p|p (4)

By Syll. twice, ⊢(2), ⊢(3), ⊢(4),

q\supset:q.\supset.q/p|p, i.e. q|L/L.

(b) By lemma to Syll., q/q\overline{\mathsf{I}s/q}; by Perm. and Syll., q/q\overline{|q/s.} Hence, q/q|L/L; by Perm., L/L|q/q.

Now, by Syll.:

L/L|q/q.\supset:q|L/L.\supset.L/L|L/L.

By ⊢b, ⊢a, and Taut.\frac{L}{p}, result. We can now complete the proof of 'Association.'
Association, p\overline{|q/r}\overline{\mathsf{I}q\overline{|p/r}}

Dem: By Syll., p\overline{|q/r}.\supset:q/r|r.\overline{|.p/r}
By Syll. twice, ⊢ Lemma, result.

Summation, q\supset r.\supset:p\vee q.\supset.p\vee r
Dem.: By Syll., Assoc.,

q|s.\supset:p|q/r.\supset.p|s (1)

By (1)\frac{s/s,\quad q,\quad p/p}{s,\quad\;\;r,\quad p\,}, result.

Theorems Equivalent to the Definitions of p\supset q, p.q, in Principia.

p\supset q.\supset.\sim p\vee q, and reciprocal theorem.

That is, p|q/q.\supset.\overline{p/p|}q/q.

Dem.: Taut., and Syll.

Reciprocal theorem by Add.\frac{s/s,\quad p}{\;s,\;\quad p}, and Syll.

p|q.\supset.\sim p\vee\sim q, and reciprocal theorem.

That is, p|q.\supset.\overline{p/p}\,\overline{|q/q}.

Dem.: Taut. Syll.; then, Perm., Taut., and Syll., or S'.

Reciprocal theorem by Add.\frac{p/p}{p,s} instead of Taut.

p.q.\supset.\sim(\sim p\vee\sim q) and reciprocal theorem.

That is, p.q.\supset.p/q|p/q.

Dem.: Id., Def. of \sim, preceding theorem, and Syll.

Reciprocal theorem in the same manner.


Appendix.

After the substance of this paper had been written, I was given the opportunity of seeing Mr Van Horn's very interesting and original paper[9] dealing with what is practically the same subject. Mr Van Horn recognises clearly the superiority of what has been called above the OR-form over the AND-form chosen in Sheffer's text. This deserves the more notice, as Mr Van Horn, I understand, had not Sheffer's article at hand in the time he was writing his own paper. His \triangle, as will be seen from the definition he gives, is indistinguishable from \mathsf{I}. I was much attracted by the harmonious character of Mr Van Horn's third Axiom. It seems to me therefore all the more desirable that certain objections, which Mr Van Horn's proofs in their present form naturally suggest to the reader, should be dealt with.

(α) It is not quite plain to me whether "of the same truth-value" (say S for short), "of opposite truth-values" (say O), are used as indefinables, or as abbreviations. If the former, we have no right to go, e.g., from pOq and \sim p, to q, etc., without some axiom to that effect, connecting O and S with \triangle. If, on the other hand, S and O are abbreviations—as it seems to me they are—the two parts of Axiom 3 stand for not less than four propositions:

1. If p and q, \sim(p\triangle q).
2. If \sim p and \sim q, p\triangle q.
3. If p and \sim q, p\triangle q.
4. If \sim p and q, p\triangle q.
We cannot assert the first two, or the last two, or all four, propositions together, because we should then need p.q.\supset.p, p.q.\supset.q, before we could make any use of such a synthetic Axiom.

This uncertainty as to the status of S and O is not without its effect upon the proofs. Consider, for instance, Th. 3. In the proof, "1°: p true. By Axiom 3, p\triangle p false" will be seen to require pSp, concerning the origin of which, and the relation it has to p\supset p (Th. 4), which it indirectly serves to prove, Mr Van Horn says nothing.

(β) In his extensive use of the Principle of Excluded Middle, Mr Van Horn makes no explicit mention of the last steps, that lead from p\supset q,\sim p\supset q to q. These steps would seem to require several propositions: (1) those carrying us from \sim p\vee p to q\vee q—"Summation," plus "Permutation," presumably—and (2) "Tautology" q\vee q.\supset.q. As Mr Van Horn uses the principle of Excluded Middle in this particular way in the first formal proof given—that of Th. 3—both the principle itself and the propositions required for its use ought, I think, to be deduced immediately from Axiom 3; and I do not see how this is possible.


  1. Sheffer, Trans. Amer. Math. Soc. Vol. XIV. pp. 481–488.
  2. Sheffer, loc. cit., footnote 1, p. 488.
  3. p|q thus corresponds to what is termed the Disjunctive relation in Mr W. E. Johnson's writings.
  4. Wikisource editorial remark: due to current limitations of the MediaWiki software the black type stroke will be (semantically somewhat unsound) rendered \mathsf{I} in formulas.
  5. By\frac{p}{q} or \frac{p,p'}{q,q'} I mean (following Mr Russell) the substitution of p for q or p, p' for q, q'. By (e.g.) P\frac{p}{q} I mean the result of effecting the substitution in P.
  6. This is the proposition shown by Sheffer to imply the analogous propositions *1·7 and *1·71 in Principia.
  7. 7.0 7.1 This use of the Rule by anticipation, with still undetermined P's and Q's, is in truth contrary to the nature of a non-formal rule, which must never be used to build up the structure of an argument. It must always be possible to dispense with all such 'anticipated' assertions in the final form of a proof. This will be seen to be very easy in the present case.
  8. ⊢(a) means the use of the Rule to pass from a to b in a|s/b.
  9. Wikisource editorial remark: the author is referring to C. E. Van Horn, An axiom in symbolic logic, Proceedings of the Cambridge Philosophical Society 19 (1917–20), 22–31.


This work is in the public domain in the United States because it was published before January 1, 1923.

The author died in 1924, so this work is also in the public domain in countries and areas where the copyright term is the author's life plus 80 years or less. This work may also be in the public domain in countries and areas with longer native copyright terms that apply the rule of the shorter term to foreign works.