Lists, comprehensive and otherwise
« previous post | next post »
A recent XKCD:
The "Russell and Whitehead" reference is to Russell's paradox, which raised a problem for naive set theory by bringing up the set of all sets that don't include themselves. The "Katherine Gates" reference is to the book Deviant Desires: Incredibly Strange Sex, 2000.
The image's title attribute has the value "They eventually resolved this self-reference, but Cantor's 'everything-in-the-fetish-book-twice' parties finally sunk the idea." This seems to be a evocation of another problem of self-reference, one leading to infinite recursion with an exponential explosion of fetishes at every step, rather than an endorsement of the maxim that "Once is cool, twice is queer".
Anyhow, now that I have your attention, I want to get back to the questions of linguistic grammaticality, acceptability, and probability that were briefly discussed in the comments on Geoff Pullum's post "When a word is redundant enough to be omitted", 8/25/2008. In particular, there was a back-and-forth involving Geoff, Shimon Edelman, and Mark Seidenberg, which is reprinted here for ease of access. As in the case of sexual fetishes, the treatment of concepts like "sentence of English" can be investigated from an individual point of view ("Mmm, passives!"), or from a sort of census-taker's perspective ("Do we have that one already? Yes? Well, increment the count, then."), or from the perspective of an experimental psychologist ("While wearing an eye-tracking device, 34 male and 35 female undergraduates were shown … "). You might also have a theory, or at least a model, that tries to explain (and perhaps even predict) the results of individual reactions, census-taking, or psychological experimentation.
Actually, I don't have time this morning to go any futher with this, so you can regard this as a promise to post some additional remarks over the next few weeks. I have a couple of surprises in mind.
Meanwhile, I invite you to think of all this in the context of a larger trend, recently discussed by Chris Anderson, "The End of Theory: The Data Deluge Makes the Scientific Method Obsolete", Wired, 6/23/2008.
"All models are wrong, but some are useful."
So proclaimed statistician George Box 30 years ago, and he was right. […]
Speaking at the O'Reilly Emerging Technology Conference this past March, Peter Norvig, Google's research director, offered an update to George Box's maxim: "All models are wrong, and increasingly you can succeed without them."
In a (no doubt doomed) attempt to avoid misunderstanding, let me offer the opinion that Peter is more right about certain kinds of engineering (and therefore about psychology) than he is about science; and that in any case, the consequences are not so much to supersede the scientific method as to change the way it's applied.
Gerg said,
September 3, 2008 @ 7:58 am
The image's title attribute has the value "They eventually resolved this self-reference, but Cantor's 'everything-in-the-fetish-book-twice' parties finally sunk the idea." This seems to be a evocation of another problem of self-reference, one leading to infinite recursion with an exponential explosion of fetishes at every step, rather than an endorsement of the maxim that "Once is cool, twice is queer".
It's more specific than that. "Cantor" refers to the proof that the power set of an infinite set is of a higher cardinality than the original set. Ie, if the book was infinite but countable to begin with (such as the list of integers) then Cantor's list of fetishes would include every subset of the existing book. That list is not only infinite but uncountable — like the list of real numbers.
"Everything in the fetish book twice" doesn't seem to quite describe that accurately though which is odd, xkcd is usually bang-on. But Cantor's work is definitely about powers of two and the comment relates to doubling. For that matter Godel's incompleteness theorem wasn't precisely about the paradox implied here either — it was about constructing a formal situation bypassing that paradox.
Gerg said,
September 3, 2008 @ 7:59 am
Odd, the preview image showed the html i included as being rendered then it was stripped when it was posted. Kind of defeats the purpose of a preview…
Mark P said,
September 3, 2008 @ 8:29 am
As usual, the science journalist gets some things right and a lot of things wrong. I think Anderson's model of the future of science is kind of like the situation when scientists, computer scientists (engineers would be a better word) in particular, started talking about fuzzy logic. It sounded like the wave of the future, the way to solve many difficult problems. It turned out to be a nice conversation topic for graduate students who should have been working on their dissertation research. After all, it was just another way of describing good programming.
James Wimberley said,
September 3, 2008 @ 10:09 am
"… not so much to supersede the scientific method as to change the way it's applied."
I don't understand the concept of a method in science, cookery, stamp-collecting, etc. that isn't its own application. On the stage, you can of course have a non-Method acting method: "Don't just do something, stand there". Business schools teach pseudo-methods, nice-sounding apothegms to take the credit for someone else (like Dilbert) working out and doing something. Do you really work this way in linguistics?
Oskar said,
September 3, 2008 @ 10:18 am
The comic is a mishmash of references. The "anything not on your list" is a clear reference to Russell's Paradox, but the "Russell and Whitehead" and "Gödel" parts are not. They're references to the book Russell and Whitehead wrote called Principia Mathematica (echoing a past book of some reknown) where they tried to axiomatize and break down mathematics to it's smallest bits. They wanted to created a system of mathematics that were both consistent and complete, that no two theorems could be produced that contradicted each other and that every true theorem could be proven within the system.
Gödel, using a very clever argument (basically formalizing the statement "This statement is not true") showed that this is not possible. If a system is strong enough to be useful, it will never be complete.
Peter said,
September 3, 2008 @ 11:20 am
Mark P says: "I think Anderson's model of the future of science is kind of like the situation when scientists, computer scientists (engineers would be a better word) in particular, started talking about fuzzy logic. It sounded like the wave of the future, the way to solve many difficult problems. It turned out to be a nice conversation topic for graduate students who should have been working on their dissertation research. After all, it was just another way of describing good programming."
Lest anyone think otherwise from reading this comment, fuzzy logic has been an enormous sucess for engineering. I think you vastly under-estimate the successful applications of fuzzy logic to industrial applications, particularly to sophisticated engineering process control. To conflate talk about fuzzy logic with descriptions of good programming is to make a category error.
Bruce Stephens said,
September 3, 2008 @ 11:31 am
Gödel's statement was (IIRC) "This statement has no proof". So the system in which the statement is formulated must be either inconsistent (the statement does have a proof, but is false), or incomplete (the statement is true, but there's no proof within that system).
(Just nitpicking. Mark's basic point is true, I think, the cartoon is a bit of a mishmash. But as a cartoon it's funny in a nerdy way.)
Nick Lamb said,
September 3, 2008 @ 12:25 pm
"If a system is strong enough to be useful, it will never be complete."
Gödel's proof showed that it's not possible to find a system which is consistent, and complete, and /capable of expressing elementary arithmetic/. This might seem like nit-picking, but systems which aren't capable of expressing elementary arithmetic aren't necessarily too weak to be useful. You can do geometry for example, (at least elementary geoemetry) without Gödel being able to sneak past.
Nathan Myers said,
September 3, 2008 @ 12:51 pm
Gerg: If the parties had to go on the list, you get the desired effect.
Brett said,
September 3, 2008 @ 1:01 pm
The reference to Cantor appears to be an allusion to something much simpler than Cantor's theorem (that every set has more subsets than elements). It's just doubling a countably infinite set doesn't increase the number of elements. There are as many even numbers as integers. Likewise, assuming the fetishes are itemized and infinite and number, acting out each of them twice does not change the total number of acts to be committed.
Mark P said,
September 3, 2008 @ 1:11 pm
While it's true that there is a type of logic called fuzzy logic, and it is not of itself programming, the only way to implement fuzzy logic in an application, whether production or research, is through a computer program. By the nature of computers, fuzzy logic can only be approximated through good programming. Computers are, as of now anyway, binary.
Sridhar said,
September 3, 2008 @ 2:22 pm
Puzzling over the comic for quite a while, trying to see how its history works (why would anyone think Goedel proposed Russell's paradox as a project-deflating response to Principia Mathematica?) and how there even is a paradox within it at all (why can't the list contain everything [hey, it is comprehensive], so that Goedel's response is just "Me, I'm too plain-vanilla to have any fetishes", hardly a stop-in-your-tracks-and-abandon-your-work situation?), I've realized A) and decided B):
A) There actually is no reference to Russell's paradox at all, only to Goedel's Incompleteness Theorem. "Anything not on your list" does not correspond to object "The set of all sets which do not contain themselves", but rather to the predicate of "Whatsoever is not provable in your system"
B) Russell and Whitehead are not putting together a single, unified list of fetishes in the world. Rather, they are putting together individual lists for each person; thus, Goedel is saying "Anything not on your list [of Goedel's fetishes]". As a result, the list of Goedel's fetishes cannot be both comprehensive and accurate (corresponding to "complete and consistent").
It took me a while to reach this point of clarity, though… I still don't think the alt-text for Cantor refers to anything particularly concrete, discussion of the fact that certain infinite cardinals are invariant under doubling (all of them, with the axiom of choice) notwithstanding.
dr pepper said,
September 3, 2008 @ 2:29 pm
I haven't paid much attention to developments in compsci in a long time, but i recall that one of the components of AI research concerned logice chips with more than 2 inputs that used both simple and weighted counting to determine output.
Peter Metcalfe said,
September 3, 2008 @ 3:51 pm
I always thought the once is cool, twice is queer maxim was originally expressed by Voltaire's "Once a philosopher, twice a pervert" although looking it up I see that it's urban legendish in sourcing.
http://everything2.com/index.pl?node_id=1313240.
battlekow said,
September 3, 2008 @ 6:06 pm
The comic reminded me of Rule 34 (semi-NSFW): If it exists, there is a porn of it.
Oskar said,
September 3, 2008 @ 6:52 pm
Gödel's proof showed that it's not possible to find a system which is consistent, and complete, and /capable of expressing elementary arithmetic/.
I know, I was just using "strong enough to be useful" as a convenient shorthand :). I'm fairly certain I got the phrase from Gödel, Escher, Bach (although it's been a good ten years since I read it).
JBL said,
September 3, 2008 @ 6:57 pm
But…the goal for the fetish list isn't necessarily consistency and completeness, just completeness. I'm not sure there's a requirement that fetishes be consistent. That's quite an assumption.
It's tempting to deduce the collorary "All fetishes are wrong, but some are useful."
I suspect that half the joke (at least) is in the notion that Gates' work is mappable onto Russell and Whitehead's, or vice-versa.
Richard Sabey said,
September 4, 2008 @ 3:55 am
A mishmash indeed. The comment "anything not on your list" could be given not to Gödel, but to Russell himself. I see it as a reference to Russell's paradox, an expression of the flaw that Russell found in Frege's Die Grundlagen der Arithmetik. Frege wrote that for any predicate P, there is a set S(P) defined as the set of all x where P(x) is true. Russell showed that, if the predicate P was the property of being a set that is not a member of itself, then no such set S(P) could be defined. (Is S(P) a member of S(P)?)
I might be being irrational here, but could that remark also apply to Cantor? It reminds me of Cantor's "diagonal" proof that the real numbers between 0 and 1 are not countable. The proof is by contradiction. Suppose that they are countable. Construct a comprehensive list of them. Cantor's proof then shows how to construct a number that is between 0 and 1 and is not on the list, thus disproving the supposition.
Aaron Davies said,
September 4, 2008 @ 10:27 am
I also assumed the references were to the barber paradox and the diagonalization argument–the fetish "anything not your list of fetishes" is impossible accurately either to include or not to include on a complete list of fetishes. What exactly "everything on your list twice" has to do with diagonalization though, I'm not sure, but it's the only thing Cantor did that a significant portion of the XKCD audience (more programmers and generalist geeks than mathematicians) could be safely assumed to know.
Anonymous Cowherd said,
September 19, 2008 @ 7:32 pm
I don't think it completely explains the "twice" thing, but the title tag may be a reference to quines, which are intimately related to Godel's paradox. (See also Raymond Smullyan.)
If we define the "quining" of a phrase as that phrase followed by itself in quotation marks, then a phrase whose quining yields a true sentence is "If we define the 'quining' of a phrase as that phrase followed by itself in quotation marks, then a phrase whose quining yields a true sentence is".