January/February 2018 issue of acmqueue

The January/February issue of acmqueue is out now

  Download PDF version of this article PDF

File Under “Unknowable!”

It’s been ahard day’s night—proving nonexistence!

Stan Kelly-Bootle

The Yellow Pages used to advertise along the following lines: “If you can’t find it here, it does not exist.” Shannan Hobbes, my favorite epistemologist, and I would ponder this claim well into the wee hours, testing its validity by searching for vendors of “Square Circles,” “Pet Unicorns,” “Cold Fusion,” “The Largest Prime Number,” “Reigning Bald Kings of France,” and similar quiddities oft debated in the PhilTrans (Philosophical Transactions). Our mounting failures—or, to quickly remove the scandalous ambiguity—our growing number of “not founds” amounted to some sort of inductive verification (of which, more anon). The Yellow Pages, considered as a merely finite hierarchy of marketable strings, has nothing much to tell us of contingent, objective existence. Indeed, we searched in vain for many incontrovertibly real, corporeal “thingies.” No sign of the Renaissance crypto-text, Hypnerotomachia Poliphili, which will be on everyone’s lips as soon as the Da Vinci Code mercifully fades from the best-seller lists.1

Madison Avenue (or whatever now serves as the hot-throbbing heart of marketeering) seeks to confuse us on the difference between IF and IFF. Not that the gullible, consuming plumpen need much persuasion! As Marshall McLuhan warned: “The Medium is the Massage.” (Doryphores should note that this is not a typo for Message, but rather McLuhan’s self-mockery, used as a title for his 1967 book coauthored with Quentin Fiore [Penguin]).

IFF is pronounced “IF and ONLY IF,” removing the asymmetry of the plain IF implication.2 Thus: “A IF B” means that “B implies A,” but does not assert that “A implies B.” In plainer English, we can say that B is a “sufficient” but not necessarily a “necessary” condition for A. A can be true regardless of the truth of B, whereas “A IFF B” means “B implies A” and “A implies B.” This makes B a “necessary and sufficient” condition for A.

As Professor Underwood Dudley used to tell us: “A logician’s salary is necessary but not sufficient.” Don’t let this confuse you!

The Yellow Pages claim, which we’ll call Proposition YP, reduces to “‘X not found in Yellow Pages’ implies ‘X does not exist,’” which is a real sod to prove or disprove, given the unfashionably large size of the rather fuzzy sets involved on both sides. Shannan and I were playfully examining the reverse implication, “‘X does not exist’ implies ‘X not found in Yellow Pages’” (which we’ll call PY), with a marginally better chance of success. As epistemologists, we have a clearer notion of the predicate “nonexistent” (we know the empty set inside out!) than the much larger set specified by the predicate “not-found-in-the-Yellow-Pages.”

If we assume that the Yellow Pages would not knowingly offer a nonexistent X for sale, and the phrase “X in the Yellow Pages” means they list a vendor for X, then PY is trivially true. But there may well be crackpot tracts offered, such as “Pet Unicorns for Dummies,” or “The Largest Prime Revealed.” (I won’t mention Cold Fusion again, since I have friends in Utah who “believe,” and in any case, tomorrow is another brand new day.) The Yellow Pages might then be accused of wrongly implying the existence of nonexistent Xs. Perish the thought of litigation, though. Imagine lawyers backed by expert philosophers wrangling on (and on...): “M’lud, Exhibition D is the Null Set, clearly labeled as ‘Out of Stock’...”

Thus, the simple grepping for string matches for a target X is inappropriate. Indeed, back in my early Univac days, we were asked to extract from a British Standards database all standards relating to lead piping. Searching was in its infancy in those days, and it took many a rotation of the Fastrands3 to produce the first match: “This standard applies to copper but not to lead piping...”

So, what about clever Googling or Yahooing of the various Yellow Pages Web sites? Alas, my experience is an overflow of cunning near-matches based on subtle marketing ploys. “We can’t find X, but your profile indicates you would be far happier with Y!”


As I mentioned earlier, apart from seeking a formal proof of PY (“Nonexistence” implies “Not-in-Yellow-Pages”), or proving that no such proof exists, there is a case to be made for inductive verification. Each time we test a nonexistent X and fail to find that X in the Yellow Pages, our confidence increases that PY is at least plausible. Much of empirical science rests on similar assumptions, suitably gift-wrapped to divert the grants committee. After (Carl) Saganic “billyons and billyons” of positive trials, the confidence converges to “let’s call it certainty.” Yet, yet, a single failure, unless you can fudge it by blaming the instruments, forces you to reexamine your hypothesis.

But back in 1939 when scientists were elsewhere engaged, Nelson Goodman threw a spanner in the inductive works with his Grue Paradox. Grue, a blend of green and blue for reasons that will emerge shortly, aroused little interest until 1954 when Goodman enlarged on his paradox in a book called Fact, Fiction and Forecast (OUP). Since then, a growing number of philosophers and scientists have started taking the Grue problem and its implications seriously. Some 20 different “solutions” have been proposed so far. Douglas Stalker’s book, GRUE! The New Riddle of Induction,4 offers 16 detailed essays together with an annotated bibliography of 316 major works on Grue.

Here’s a simplified account of the Grue Paradox. Consider these two hypotheses: (1) “all emeralds are green;” and (2) “all emeralds are grue.” By grue, we mean “green if examined before time t, otherwise blue.” Now comes the soul-searing crunch. Suppose we have been collecting emeralds, one by one, up until time t, and found them all to be green. The “normal” application of induction indicates that hypothesis 1 is strongly supported, and we can predict that the next emerald we encounter will also be green. But all our observations support hypothesis 2 with equal force, since every emerald seen so far is indisputably grue. We are therefore equally justified in making the prediction that any emerald examined after time t is also grue—that is, blue! We all feel instinctively that the grue hypothesis is untenable, yet the resulting paradox has proved quite intractable. I should mention that there are many variants that avoid calling in doubt the general and sound belief that gems do not suddenly change color.

The resulting “riddle of induction” strikes at the very heart of scientific inquiry: Given sets of hypotheses equally supported by the evidence, why do we favor some as more “natural” than others? Ockham’s Razor offers parsimony as a guide, but Einstein warns against oversimplification. Goodman’s own Humean wriggle is that certain predicates, such as “green” and “blue,” are more “entrenched” and “projectible” than “grue.” This approach, further amplified by Quine,5 takes us to Natural Kinds, the classification challenges of OOT (object-oriented technology), the ontological problems of knowledge engineering,6 and the emerging applications of ILP (inductive logic programming).7

Finally, I feel I should warn suspicious readers that grue is a real paradox, unrelated to the cruel month of April.


1. After Dan Brown’s dubious prose and flippant historicity, you should try The Rule of Four, by two Princeton medieval scholars, Ian Caldwell and Dustin Thomason (Simon & Schuster, 2004). The decryption of the Hypnerotomachia Poliphili, a Renaissance text of obscure erudition with a small splash of sexual violence, unfolds more convincingly than Brown’s saga. I would call The Rule of Four the “thinking man’s Da Vinci Code.”

2. Meilir Page-Jones, my favorite Welsh Method[olog]ist, notes a quirk in Welsh orthography: f is pronounced v, as in the English if! But Welsh ff is plosive like the English f. Which is why the Welsh for film is ffilm.

3. Fastrand (™ Sperry Rand Corporation) is a nonfloppy rotating cylindrical device used for storing angular momentum. The total angular momentum available is slightly reduced if the data-storage option is fitted, owing to the braking effect of the read-write heads on the magnetized surface. (Kelly-Bootle, S. 1995. The Computer Contradictionary, Second Edition. Cambridge: MIT Press.)

4. Stalker, D., ed. 1994. GRUE! The New Riddle of Induction. Chicago: Open Court Publishing.

5. Quine, W. 1994. Natural kinds. In GRUE! The New Riddle of Induction, ed. D. Stalker, 41-56. Chicago: Open Court Publishing.

6. Lenat, D. B. 1995. CYC: A large-scale investment in knowledge infrastructure. Communications of the ACM 38 (November): 33-38.

7. Bratko, I., and Muggleton, S. 1995. Applications of inductive logic programming. Communications of the ACM 38 (November): 65-70.



[email protected] or www.acmqueue.com/forums

STAN KELLY-BOOTLE (http://www.feniks.com/skb/; http://www.sarcheck.com), born in Liverpool, England, read pure mathematics at Cambridge in the 1950s before tackling the impurities of computer science on the pioneering EDSAC I. His many books include The Devil’s DP Dictionary (McGraw-Hill, 1981) and Understanding Unix (Sybex, 1994). Under his nom-de-folk, Stan Kelly, he has enjoyed a parallel career as a singer and songwriter.

© 2005 ACM 1542-7730/05/0400 $5.00


Originally published in Queue vol. 3, no. 3
see this item in the ACM Digital Library



(newest first)

Leave this field empty

Post a Comment:

© 2018 ACM, Inc. All Rights Reserved.