H. P. Grice consults Sheffer's essay in the Transactions for The American Mathematical Society. "Was it a stroke?"

A SET OF FIVE INDEPENDENT POSTULATES FOR BOOLEAN ALGEBRAS, WITH APPLICATION TO LOGICAL CONSTANTS* 

BY HENRY MAURICE SHEFFER 

or H. M. Sheffer, as H. P. Grice has him. 

Introduction. 

Postulate-sets for determining the class of Boolean algebrasf have been given by Schröder,^ Whttehead,§ and Huntington.|| Schroder's set of ten postulates assumes—in addition to an undefined class K, common to all these postulate-sets—an undefined dyadic relation, 4 > and Boole's 1f undefined binary AT-rules** of combination, + and X ; Whitehead's two sets, the first of thirteen, and the second of fifteen, postulates, and Huntington's first set, of ten postulates, assume the same undefined AT-rules of combination, + and X , which Huntington writes respectively © and o ; Huntington's second set, of nine postulates, assumes Schroder's undefined relation 4 > * Presented to the Society, December 31, 1912. f We employ the term Boolean algebras in its plural form for the following reasons: (1) none of the equivalent postulate-sets here referred to is in terms of its undefined entities onevalued ("categorical")—that is, each determines not a single algebra but a class of algebras; one should not speak, therefore, of "der identische Kalkül" (Schröder), "the Algebra of Symbolic Logic" (Whitehead), or "the algebra of logic" (Huntington); (2) Peano's Formulario Mathematico and Whitehead and Russell's Principia Mathematica, each of which includes, as a part, the algebras under consideration, have a far stronger title to the name "algebra of logic"; (3) "The Algebra of Symbolic Logic, viewed as a distinct algebra, is due to Boole" (Whitehead, loc. cit., p. 115). "This algebra in all its essential particulars was invented and perfected by Boole" (ib., p. 35, footnote). i Ernst Schröder: Vorlesungen über die Algebra der Logik (Exakte Logik), Erster Band, 1890. The postulates, under various names, are scattered throughout the volume; collected into one list by E. Müller: Abriss der Algebra der Logik, Erster Teil (1909), pp. 20, 21. § A. N. Whitehead: A Treatise on Universal Algebra, Vol. I, 1898, pp. 35-37. || E. V. Huntington: Sets of Independent Postulates for the Algebra of Logic. These Transactions, vol. 5 (1904), pp. 288-309. If G. Boole: An Investigation of the Laws of Thought. London, 1854. ** An n-ary rule of combination , is an agreement according to which any n (distinct or non-distinct) logical entities, ah a,, a,, • • -, in a definite order, determine a unique logical entity (oi, a,, at, •■• ); in other words, a rule of combination is a one-valued logical function. If the entity (a¡, a,, a,, ■ ■ ■ ) is defined for all those and only those cases where all the n entities ai, a,, at, • • • are elements of some class K , then is a K-rule of combination; for a binary X-rule of combination, ( a, b) is also conveniently written a°b . If, for a X-rule of combination $ , the entity 4> (ai, a,, a¡, ■ ■ ■ ) is always a K-element, then 

'). E. [ ( a | 6' ) | ( a' | & ) 1' = ( « I & ) I ( a' | 6' ) - F. a\[a\(b\c)]=b\[b\(c\a)] =c|[c|(a|6)] = a|(6|c)' =6|(c|a)' =c|(a|6)'. G. (a'|o)|[(6'|a)l(C|o)]-a(6|c). License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 1918] POSTULATES FOR BOOLEAN ALGEBRAS 485 Proof of lia. There is a iT-element—say, x [by 1]. There is a üT-element, x | x', which we call z [by 2, used twice]. (a | z)' = (a')' [by 4, b replaced by x ] = a . [by 3]. Proof of lib. There is a TT-element, z', which we call u [by lia and 2]. a'\u' = a'\ (z'Y = a' | z [by 3] = (a')' [by 4, a replaced by a' and 6 by x ] = a [by 3]. Proof of Ilia. a \ b = b | a [by ¿ ]. Hence (a|6)'= (6|a)'. Proo/ o/ 7776. a'\b' = b'\ a' [by ^4, a replaced by a' and b by b']. Proof of IVa. [ a \ (b' | c') ]' = [ (6')'| o] | [ (c')' | a] [by 5, b replaced by V and c by c' ] = (6 | a) | (c | a) [by 3, used twice] = (a | 6) | (a | c) [by .¡4, used twice] = [ (a | 6)' ]' | [ (a | c)' ]' [by 3, used twice]. Proof of IVb. a'\[(b\c)']' = a'\(b\c) [by3] = [[a'\(b\c)}']' [by3] = [(b'\a')\(c'\a')]' [by 5, a replaced by a' ] = [(a'\b')\(a'\c')]' [by A, used twice]. Proo/ of V. Take ä = a'. Then (a | a')' = (x | x')' [by B, 6 replaced by x] = z' [by lia] = u [by lib]. a'\(a')' = a'\a [by 3] = a | a' [by A ] = z [by fi, 6 replaced by x ]. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 486 H. M. 8HEFFER: A SET OF FIVE [October Postulates 1-5 oTid Boolean Algebras. The following is Huntington's first postulate-set* for Boolean algebras: " [ For this postulate-set] we take as the fundamental concepts a class K with two [binary K-] rules of combination e and o ; and as the fundamental propositions the following ten postulates: la. a © 6 is in the class whenever a and 6 are in the class. 16. a 0 6 is in the class whenever a and 6 are in the class. Ha. There is an element t z such that a © z — a for every element a. 116. There is an element t u such that a 0 u = a for every element a. Ilia, a © 6 = 6 © a whenever a, 6, a © 6, and 6 © a are in the class. III6. a o 6 = 6 © a whenever a, b, a o 6, and 6 o a are in the class. IVa. a© (6©c) = (a©6) o (a ® c) whenever a, 6,c,affi6,affic, 60c,a©(6oc), and (a©6)o(a©c) are in the class. IV6. a© ( 6 © c ) = (a©6) © (aOc) whenever a,6,c,a©6,a0c, 6ffic,aO (6©c), and (a©6)©(aOc) are in the class. V. If the elements z and u in postulates lia and 116 exist and are unique, then for every element a there is an element ä such that a © ä = u and a 0 ä = z. VI. There are at least two elements, x and y, in the class such that x#=y."{ That set 1-5 is a postulate-set for Boolean algebras we shall prove by showing that this set and Huntington's first postulate-set are equivalent. Proof.—If for any elements, a and 6, of our class K we write ä for a', a © 6 for (a | 6)', and a 0 6 for a' \ b', theorems Ia-V and postulate 1 are precisely Huntington's first postulate-set; hence set 1-5 implies Huntington's set. If for any elements, a and 6, of Huntington's class we write a | 6 for 5 o B, Huntington's set implies set 1-5. § § 2. Application to Primitive Logical Constants. Since not only in special deductive systems but even in the foundations of logic not all propositions can be proved and not all non-propositional entities * Huntington, loe. cit., pp. 292-3. t For 2 and u respectively Huntington uses the symbols A and V, which he takes from Peano's Formulaire de Mathématiques. These are, however, symbols for logical constants, just as 0 and 1 are symbols for numerical constants. We have replaced, therefore, Boole's and Schroder's 0 and 1, and Huntington's A and V, by z and u . t That is, such that x and y are distinct. S By the_" principle of duality " the results of 51 hold also when a\b is interpreted throughout as 5©b. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 1913] POSTULATES FOR BOOLEAN ALGEBRAS 487 can be defined, some logical constants* must be primitive,! that is, either unproved or undefined. A list of primitive logical constants—primitive ideas and primitive propositions—in terms of which, presumably,4: all other logical constants can be either defined or proved, is given by Whitehead and Russell in their Principia Mathematical This list contains, among other logical constants, the primitive ideas|| negation (symbolized ~ ) and disjunction (symbolized v). Negation and disjunction are partly explained— but, of course, not at all defined—by the statement that for any elementary proposition p (elementary proposition being itself one of the Principia's primitive ideas), ~ p means the elementary proposition not-p; and for any two elementary propositions, p and q, pvq means the elementary proposition either p or q (or both). On these two primitive ideas, in view of the following interpretation of K and |, our set 1-5 has an important bearing. For, if Ar is the class of all propositions of a given logical type.^f then whenever p and q are two propositions of this type, p \ q may be interpreted as the proposition neither p nor q; in other words, | has the properties of the logical constant neither-nor. This logical constant we may symbolize by a, and for obvious reasons we may name rejection.** Theorem 1. If in any list of primitive ideas for logic both negation and disjunction are primitive, they may be replaced by the single primitive idea rejection. Proof.—In terms of negation and disjunction, rejection is defined by the Def.—For any two elementary propositions, p and q, pAq = co (pvq). In terms of rejection, negation is defined ft by the Def.—For any elementary proposition p, «*> p = p a p. In terms of rejection, disjunction is defined by the Def.—For any two elementary propositions, p and q, pvq = (p*q)*(p*q). By the following theorem, a similar reduction is possible for primitive propositions. * Whitehead and Russell, loc. cit., pp. 94-101. t Ib., p. 95. J ". . . there must always be some element of doubt, since it is hard to be sure that one never uses some principle unconsciously" (ib., p. 94). § Whitehead and Russell, loc. cit., partial list, pp. 95-101; the other primitives are scattered throughout the rest of the book. || 76., p. 97. f 7b., pp. 39-68. ** By analogy with subject and object, we may call p a g the reject of p and q . ft Negation may thus be considered as a special case of rejection. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 488 H. M. SHEFFER: BOOLEAN ALGEBRAS Two primitive propositions of the Principia* are: * 1.7. If p is an elementary proposition, « p is an elementary proposition. * 1.71. If p and q are elementary propositions, pvq is an elementary proposition. Theorem 2. If in any list of primitive propositions for logic both * 1.7 and * 1.71 are primitive, they may be replaced by the single primitive proposition. * 1.7'. // p and q are elementary propositions, p*q is an elementary proposition. Proof.—If in * 1.7 we replace pby pwq, * 1.7 and * 1.71 imply * 1.7'. If in * 1.7' we replace q by p, * 1.7' implies * 1.7. If in * 1.7' we replace p by pnq and q by p*q * 1.7', used twice, implies * 1.71. t 'Thus we have made it possible to reduce, by one each, the number of primitive ideas and of primitive propositions used in the Principia for the foundation of logic. Cornell University, February, 1913. * Whitehead and Russell, loc. cit., p. 101. t By the "principle of duality" the results of §2 hold also when pAq is interpreted throughout as the logical constant cither not-p or not-q.