The Grice Club: H. P. Grice reconsiders C. S. Peirce's philosophical justification for his stroke

Monday, April 6, 2020

H. P. Grice reconsiders C. S. Peirce's philosophical justification for his stroke

Peirce’s Discovery

It turns out that the American logician and philosopher Charles Sanders Peirce (1839-1914) had already discovered the logical connective we call the Sheffer Stroke, as well as the related connective NOR (also called Joint Denial, and quite appropriately Peirce’s Arrow, with other names in use being Quine’s Arrow or Quine’s Dagger and today usually symbolized by “ $\downarrow$ ”). The relevant manuscript, dating to 1880, numbered MS 378 in a subsequent edition and titled “A Boolian [sic] Algebra with One Constant” (Peirce, 1971), was actually destined for discarding and was salvaged for posterity literally at the nick of time in 1926. A fragmentary text by Peirce dating from 1880 also shows familiarity with the remarkable metalogical characteristics that make a single function functionally complete, and this is also the case with Peirce’s unfinished Minute Logic (1902, ch. 3): these texts were eventually published posthumously (1933, vol. 4, pp. 13-18, 215-216.)

Peirce designated the two truth functions, NAND and NOR, by using the symbol “ $\curlywedge$ ” which he called Ampheck, coining this neologism from the Greek word ἀμφήκης which means “of equal length in both directions.” (Peirce, 1933: 4.264) Peirce’s editors disambiguated the use of symbols by assigning “ $\overline{\curlywedge}$ ” to the connective we call the Sheffer Stroke while preserving the symbol “ $\curlywedge$ ” for NOR.

(More about Peirce’s work in logic, including reference to the 1880 manuscript, can be found in another encyclopedia article.)

Like Sheffer did later, Peirce understood that these two connectives can be used to “reduce” all mathematically definable connectives (also called “primitives” and “constants”) of propositional logic: this means that all definable connectives of propositional logic can be defined by using only the Sheffer Stroke or NOR as the single connective. No other connective (or associated function) that takes one or two variables as inputs has this property. Standard, two-valued propositional logic has no unary functions that have the property of functional completeness. In subsequent section, we will explore this remarkable logical property in detail. At first blush, availability of this option ensures that economy of resources can be obtained—at least in terms of how many functions or connectives are to be included as undefined. Unfortunately, there is a trade-off between this gain in economy of symbolic resources and the unwieldy length and rather counterintuitive appearance of the formulas that use only the one connective.

It is characteristic of Peirce’s logical genius and emblematic of his rather under-appreciated contributions to the development of modern logic that he grasped the significance of functional completeness and figured out what truth functions—up to arity 2—are functionally complete for two-valued propositional logic. (Strictly speaking, this is the property of weak functional completeness, given that we disregard whether constants or zero-ary functions like 1 or 0 can be defined.) Peirce subscribed to a Semeiotic view, according to which the fundamental nature and proper tasks of the formal study of logic are defined by the rules set down for the construction and manipulation of symbolic resources. A proliferation of symbols for the various connectives that are admitted into the signature of a logical system suffers from a serious defect on this view: the symbolic grammar fails to match or represent the logical fact of interdefinability of the connectives. Peirce was willing sometimes to accept constructing a formal signature for two-valued propositional logic by using the two-members set of connectives $\{\neg , \bot \}$ , which is minimally functionally complete. This means that these two connectives—or, if we are to stick to an approach that emphasizes the notational character of logical analysis, these two symbols—are adequate expressively: every mathematically definable connective of the logic can be defined by using only these two; and the set is minimally functionally complete in the sense that neither of these connectives can be defined by the other (so, as we say, they are both independent relative to each other.) The symbol $\ulcorner \bot \urcorner$ can be viewed as representing a constant truth function (either unary or binary) that returns the truth value False for any input or inputs. Or it can be regarded as a constant, which means that it is a zeroary (zero-input) function, a degenerate function, which refers to the truth value False. Although not using our contemporary terminology, Peirce took the second option. This set has cardinality 2 (it has exactly two members) but it is not the best we can do. Peirce’s discovery of what we have called the Sheffer Functions (anachronistically and unfairly to Peirce, but bowing to convention) shows that we can have a set of cardinality 1 (a one-member set or a so-called singleton) that is minimally functionally complete with respect to the definable connectives of two-valued propositional logic. Thus, either one of the following sets can do. The sets are functionally complete and, because they have only one member each, we say that the connectives themselves have the property of functional completeness. $\ulcorner \mid \urcorner$ is the symbol of the Sheffer Stroke or NAND and $\ulcorner \downarrow \urcorner$ is the symbol of the Peirce Arrow or NOR. (We stipulate as such, even though we have not introduced our grammar formally.)

It is important to show, albeit briefly, how these functions can define other functions. Algebraically approached, this is a matter of functional composition but we do not enter into such details here. We will have more details in subsequent sections. In case one wonders why the satisfaction with defining the connectives of the set that comprises the symbols for negation, inclusive disjunction, and conjunction, namely $\{ \neg, \vee, \wedge \}$ , there is an explanation: there is an easy, although informal, way to show that this set is functionally complete. It is not minimally functionally complete because $\ulcorner \vee \urcorner$ and $\ulcorner \wedge \urcorner$ are inter-definable. But it is functionally complete. Thus, showing that one can define these functions suffices for achieving functional completeness. Definability should be thought as logical equivalence: one connective can be defined by means of others if and only if the formulas in the definition (what is defined and what is doing the defining) are logically equivalent. (Presuppose the truth-tabular definitions of the connectives.)