(This post is part of the NewAPPS symposium on Paul Livingston's 'Derrida and Formal Logic: Formalizing the Undecidable')

Paul Livingston’s paper presents a comparative analysis of Gödel’s incompleteness results, Priest on diagonalization, and Derrida on *différance*. One of the goals seems to be to show that there are significant analogies between these different concepts, which would be at odds with the fact that Derrida’s ideas encounter great hostility among most philosophers in the analytic tradition. In particular, Derrida’s *différance* and the concept/technique of diagonalization are presented as being each other’s counterpart (a view earlier defended by Graham Priest in *Beyond the Limits of Thought*).

But crucially, while *différance* is presented as cropping up in any discourse whatsoever, for a particular language/formal system to have the kind of imcompleteness identified by Gödel specifically with respect to arithmetic, certain conditions must hold of the system. So a fundamental disanalogy between what could be described as the ‘Gödel phenomenon’ (incompleteness arising from diagonalization and the formulation of a so-called Gödel sentence) and Derrida’s *différance* concerns the scope of each of them: the latter is presented as a perfectly general phenomenon, while the former is provably restricted to a specific (albeit significant) class of languages/formal systems. Although Livingston does not fail to mention that a system must have certain expressive characteristics for the Gödel phenomenon to emerge, it seems to me that he downplays this aspect in order to establish the comparison between *différance* and diagonalization. (There is much more that I could say on Livingstone’s thought-provoking piece, but for reasons of space I will focus on this particular aspect.)

First, let me present one possible formulation of Cantor’s original diagonal argument – notice that it is not Cantor’s own original formulation, but this is the formulation that I use to explain diagonalization to students (so far successfully). The goal is to establish that there are more real numbers than natural numbers, even though both sets are infinite (leading to the famous conclusion that infinity comes in different sizes). In fact, it is not necessary to consider all real numbers; even in the interval between 0 and 1 there are more real numbers than there are natural numbers. This is how the argument goes: assume that you produce an enumeration of each possible (infinite) decimal expansion between 0 and 1, for example:

1 0,38957…

2 0,74581…

3 0,64633…

4 0,99432…

5 0,72590…

…

Now take the first number of the first item on the list; the second of the second item etc. (the ones indicated with *x* above), and add 1 to each of them. One then produces the following number:

0,45741…

This number is provably not on the original list, because it differs in at least one position from each of the items already on the list (this is what the operation of adding 1 uniformly is meant to accomplish). And yet, by the hypothesis it should have been on the list, because it is a decimal expansion between 0 and 1: it both ‘is and is not’ on the list. So the original hypothesis, namely that the list contained the totality of decimal expansions between 0 and 1, is proved to be false, which then allows for the conclusion that there cannot be an enumeration of this totality, and thus no surjective mapping from the natural numbers to the reals between 0 and 1. (Adding the newly produced number to the list does not solve the problem, as the same procedure can be iterated again and again, always producing items not on the list.)

This is how a typical diagonalization argument illustrates the paradoxical interplay between Closure and Transcendence, in Priest’s terminology, which Livingston discusses at length in the paper. (Dennis des Chene points out to me in correspondence that a diagonal argument need not be formulated as a *reductio* argument, which is its usual formulation; if formulated as a direct, constructive argument, then the Closure-Transcendence interplay is not nearly as explicit. This observation has interesting philosophical implications, but I’ll leave them for another occasion.)

More technically, the diagonalization of an expression is now usually understood as the result of concatenating its quotation name with itself: for example, the diagonalization of *x* = 0 (using ‘ ’ to generate the name of the expression) is

‘*x* = 0’ = 0

(i.e. the *x* in the original expression has been replaced by the name of the expression itself – I borrow this example from Jeff Ketland). Diagonalization is a key component of Gödel’s incompleteness theorems, and Haim Gaifman has a very nice paper showing how the results arise naturally from the diagonalization method. (Note: from now on, my observations will rely heavily on the insightful comments to a post I wrote on the topic at M-Phi, in preparation for this post. Thanks again to those who have chipped in there!)

Gödel’s original argument was intended to show that arithmetic is incomplete, as the Gödel sentence ‘This sentence is not provable’ (construed by diagonalization) is not provable if true (if false, then the system proves a false sentence, and thus is unsound, and that would be much worse than being incomplete!). This means that any language/formal system containing arithmetic will give rise to the Gödel phenomenon, and thus that containing arithmetic is a *sufficient* condition for the Gödel kind of incompleteness to emerge.

******UPDATE******

Reading the comments on this thread, especially Michael Kremer's #13, I realize that the characterization of diagonalization as concatenation may seem to suggest that it is a trivial affair to construct a Gödel sentence for a given language/system: just replace the variable with the name of the expression! But the point is actually to *prove *the following equivalence as a theorem of the system (using G for Gödel sentence and ~P for not provable):

G <==> ~P('G')

And to prove *this *equivalence, a fair amount of the formal machinery of the system is required. This machinery is a necessary condition for the Gödel phenomenon to arise, and this is precisely why I am emphasizing here that whether a given language/system is Gödel-incomplete is a non-trivial question.

****************

But there is a significant body of research (dating back to Smullyan, but more recently in work by Andrzej Grzegorczyc and Albert Visser) showing that other systems which are not obviously ‘arithmetical’ are prone to the same kind of Gödel-like incompleteness, in particular theories of syntax and theories of computation. In other words, containing arithmetic (in a particular sense of ‘containing’ at least) does not seem to be a necessary condition for the Gödel phenomenon to arise. As well put by Jeff Ketland (in comments here), “arithmetic, syntax and computation are all heavily intertwined. It's what they have in common which is at the heart of the phenomenon.” These investigations provide elements for the investigation of the *technical* issue of the necessary conditions in a formal system for it to be Gödel-incomplete.

Now back to Livingston’s text. Derrida’s concept of *différance *is presented as absolutely general, as emerging in any form of discourse. Now, it is clear that the Gödel phenomenon does not pertain only to arithmetic and related systems, but it is also clear that it does not affect any arbitrary language/formal system. Certain conditions, especially related to expressivity, must be met for diagonalization to be possible. Needless to say, there are many significant systems that are perfectly complete, first-order predicate logic for example (whose completeness was proved by Gödel himself, prior to the incompleteness results).

So while there are interesting conceptual and structural similarities, the fact that *différance* and diagonalization/incompleteness have different scopes seems to me to suggest that the analogy is not as smooth as Livingston seems to present it to be. Whether a given language gives rise to the Gödel phenomenon or not is a technical, non-trivial question, thus not warranting the kind of generalization that Livingston seems to be proposing.

A final general remark: even if it is ‘writing itself’ that arguably gives rise to the phenomenon of diagonalization, it is also writing and fomalization itself which allow for the very investigation of the limits of formalization. The technique creates a limitation, so to speak, but it also has the resources to investigate the very limitation, and that’s pretty impressive.

## Recent Comments