Sheffer stroke the most important advance in logic?

I think I once read, or heard, that Bertrand Russell once said that the discovery that all logical operators are expressible in terms of the Sheffer stroke was the most significant advance in logic since the publication of Principia Mathematica, and that had he and Whitehead known about it beforehand, they would have proceeded completely differently.

This is a really strange claim, so I imagine that I (or the person who told me) misunderstood, or misheard, or made it up completely.

If Russell really did say something like this, what exactly did he say, and where and when?

• Regardless of what he said, I think Godel effectively shattered any opinions that Russell had on formal logic – William Mar 28 '12 at 13:52
• Let's try to stick to the subject of the question. – MJD Mar 28 '12 at 13:53
• If it is true, it shows that he may have had a sense of humour. – André Nicolas Mar 28 '12 at 14:13
• Jokes aside, Russell really did think highly of the Sheffer stroke, and in his $1925$ revision of Principia, spent a fair bit of time on it in the Introduction. He was also very impressed by Nicod's "single axiom" for propositional logic. – André Nicolas Mar 28 '12 at 14:47
• Note that Charles Sanders Pierce discovered the Sheffer stroke about 30 years before Sheffer. – user28365 Apr 5 '12 at 2:52

Russell apparently made this comment in the 1925 edition of PM, where he introduced the (NAND) Sheffer stroke. See page 1 of The Evolution of Principia Mathematica. It says that Russell called it "the most definite improvement resulting from mathematical logic during the past fourteen years." But as the author notes, this is an odd comment, and the change is a technical triviality. I don't understand why Russell was so impressed with this either. I have never found it useful for proving anything, and I have never seen others use it either. It gets a passing mention at most.

• Some might disagree, but I think the last 90 years have shown Russell was wrong here. The Sheffer stroke while interesting isn't all that fundamentally important. Its discovery has had little impact on the development of logic or computational technology. It's analogous to taking a nice 3 axiom system and finding an equivalent unwieldy single axiom. While interesting that it can be done, often it's not useful. – Bill Cook Mar 28 '12 at 15:11
• A more full quotation from the Principa: The most definite improvement resulting from work in mathematical logic during the past fourteen years is the substitution, in Part I, Section A, of the one indefinable "$p$ and $q$ are incompatible" (or, alternatively, "$p$ and $q$ are both false") for the two indefinables "not-$p$" and "$p$ or $q$." This is due to Dr H. M. Sheffer. – user642796 Mar 28 '12 at 15:18
• Thanks! I'm sure that's what I must have been thinking of. – MJD Mar 28 '12 at 15:19
• I do not think that Russell is calling the Sheffer stroke the most dramatic improvement in mathematical logic, but only its use the most dramatic improvement to the text resulting from advances in mathematical logic. – user642796 Mar 28 '12 at 15:19
• I see that Linsky also agrees that it is peculiar. – MJD Mar 28 '12 at 15:28

I have been reading the recent book The Evolution of Principia Mathematica, by Bernard Linsky.

The quote in the post is in significant ways not quite right. It comes in the Introduction to the 1925 Edition of Principia, first page. Here is what was actually written, in full.

"The most definite improvement resulting from work in mathematical logic is the substitution, in Part I, Section A, of the one indefinable "$p$ and $q$ are incompatible" (or, alternatively, "$p$ and $q$ are both false") for the two indefinables "not-$p$" and "$p$ or $q$." This is due to Dr. H.M. Sheffer. consequently, M. Jean Nicod showed that one primitive proposition could replace the five primitive propositions $\ast$1.2.3.4.5."

So Russell is saying that the greatest improvement in the second edition of Principia that is due to recent advances in mathematical logic, presumably by others, came from using the Sheffer stroke and an axiomatization based on the work of Nicod. There are also significant changes in the description of type theory, but presumably that is not mentioned here because it is based on ideas of Russell. (By this time, Whitehead had bailed.)

Russell is not saying that Sheffer's work is the most important development in mathematical logic of the previous fourteen years.

• A great example of how context can completely change the meaning of a quote. – Antonio Vargas Apr 3 '12 at 3:16
• Linsky says “However, Russell does not say that this is the most important improvement in logic, but rather only the most definite improvement that could be made to PM.” (p.108–109) – MJD Apr 14 '14 at 18:24
• The quotation is from the $1925$ edition. Presumably somewhere else Russell wrote the sentence attributed to him by Linsky. – André Nicolas Apr 14 '14 at 18:42

The focus that Russell had was very different than the focus logicians have today. Russell's viewpoint of "logic" was tightly connected to Principia Mathematica, and his interpretations of other results depended on their relation with PM, because that system was the basis for his research program in logic and philosophy.

Russell's work was the peak of the logicist program: to argue that all of mathematics can be expressed in pure "logic" and to study the properties of that "logic". The existence of a single operator to which all other "logical" operators can be reduced would be wonderful from that point of view - just as a single physical law that explains all of physics would be wonderful for the foundations of physics. The use of a single primitive would have reduced the number of "logical notions" that were needed in the foundations of PM, which was an important philosophical goal.

So, in the context of PM, Russell's remarks were perfectly reasonable. The key is that his viewpoint of "logic" was directly focused on PM.

• It's worth pointing out that, in the parallel world of digital logic design, the NAND gate is considered to be the "universal" logical element -- any digital device you want to build can be built fron NAND gates. (And, in fact, this was often done.) I can imagine that if NAND gates had been invented fairly late in the development of digital electronics (rather than being just about the first thing invented) they would have been considered quite magical. – Daniel R Hicks Apr 3 '12 at 3:35

The idea of improvement that could have been brought to Principla Mathematica [PM] is quite misplaced! Replacing the primitive team {INCLUSIVE-OR, NEGATION} by Sheffer's (actually Peirce's or even... Chrysippus'!) NAND wouldn't have improved PM, at all.

Because, primo, PM is a piece of kindergaten charabia that should not have been written -- and published -- in the first place: it is nothing but an elementary exercise in formalisation (a rather long one, indeed). As a matter of fact, one can generate it with the help of appropriate software.

Even the idea of formalisation in PM is besides the point: in PM, like in Frege's Begriffsschrift (1879) or in his Grundesetze der Arithmetic (1893--1903) and in Peirce's pioneering 1885-paper, the formalisation concerns only a superficial aspect of logic, namely the (provable) formulas as expressing propositions and / or propositional schemes, not the proofs themselves: the concept of proof -- the central concept of logic, after all -- is left un-formalised in PM. [*]

Second, the handling of quantification (first- and second-order) in PM is seriously flawed and constitutes a considerable step backwards even with respect to Frege. (This is, by the way, one of Goedel's side remarks on Russell, not mine. Cf. Goedel's Russell's mathematical logic, in The Philosophy of Bertrand Russell, edited by Paul Arthur Schilpp, Northwestern University, Evanston and Chicago IL 1944, pp. 123--153.)

Third, the Russellian finding, meant to avoid paradoxes and the like -- namely the so-called ramified theory of types -- is a paradigmatic piece of muddy thinking: in PM, the so-called orders and the type hierarchy are introduced only in order to get rid of them, at a later stage (by the so-called Reducibility Axiom).

Fourth, the actual mathematics `formalised' (so to speak, i.e. in formularian terms) in PM is rather elementary.

Finally, PM (actually Russell and Whitehead) has done more damage than good to the reasearch in (theoretical) logic, during the last hundred years or so.

[*] The proof themselves have been first formalised by Nicolaas Gerrit de Bruijn and his students and collaborators at the Eindhoven Polytechnics (NL), about 40 years ago, within the Automath project (Automated Mathematics), since around 1967--1968. Cf., e.g., https://www.win.tue.nl/automath/ and my Abstract Automath, Mathematical Centre, Amsterdam 1982 [Mathematisch Centrum Tract 160] @ https://www.win.tue.nl/automath/archive/webversion/xaut021/xaut021.html.

• This isn't an answer to the question, just a criticism (and in my opinion, though I am no fan of PM at all, an overly harsh one) of PM. – Noah Schweber Jan 12 '18 at 15:43