Coding Russell’s paradox: let’s ask Prof. Wittgenstein.

[This post is only 72% serious]

“Like all men of the Library, I have traveled in my youth;
I have wandered in search of a book,
perhaps the catalogue of catalogues…”

Jorge Luis Borges, “The Library of Babel”

…Some of the books in the Library are catalogs that list other books. Some of the catalogs list other catalogs. And some of the catalogs list themselves. Such catalogs are called “funny catalogs”. And those catalogs that don’t list themselves are called “boring”. There is one book in the Library named “A Complete Catalog of All Boring Books”. A boring title indeed … or is it? What’s funny about it, is that it was very easy to write, but quite difficult to read. And until you finish it, you cannot really tell whether it’s funny or boring. So it can provide you entertainment (or boredom) for eternity. It is really the only book you’ll ever need. It doesn’t loose its value even if you throw away all other books in the Library.

class Russell
{
    public List<IEnumerable<object>> Library;

    public Russell()
    {
        Library = new List<IEnumerable<object>>();
        Library.Add(
            //the only book you'll ever need:
            //a catalog of all non-self-referential catalogs
            (from catalog in Library
             where !catalog.Contains(catalog)
             select catalog).Cast<object>()
            );
    }
}

           //now let's read it
            var russell = new Russell();
            var paradox = russell.Library[0].ToList();

 

Of course, this is cheating! You get a Stack Overflow simply because of the self-reference, not because of Russell’s paradox! If you remove the NOT operator and try to obtain a genuinely “boring” Complete Catalog of All Funny Books, you’ll still get a Stack Overflow.

Now let’s see what our friend Prof. Wittgenstein has to say on this subject:

“The reason why a function cannot be its own argument is that the sign for a function already contains the prototype of its argument, and it cannot contain itself. For let us suppose that the function F(fx) could be its own argument: in that case there would be a proposition ‘F(F(fx))’, in which the outer function F and the inner function F must have different meanings, since the inner one has the form O(f(x)) and the outer one has the form Y(O(fx)). Only the letter ‘F’ is common to the two functions, but the letter by itself signifies nothing. This immediately becomes clear if instead of ‘F(Fu)’ we write ‘(do) : F(Ou) . Ou = Fu’. That disposes of Russell’s paradox.” (Tractatus Logico-Philosophicus, 3.333)

Hey, didn’t he cheat as well? I think he cheated even more than I did. He simply banned the self-reference on the language level by proclaiming type invariance. If you noticed, I worked around type invariance of my language by adding that little .Cast<object>(). But I could use covariant collections. Self-reference is not an issue for programming languages. Well, considering that Bertrand Russell himself called Wittgenstein a genius, let’s admit that Wittgenstein correctly understood that the naive set theory was flawed on the syntax level, and that indeed had to be fixed (and was fixed) by restricting the type system.

Believe it or not, I had not been planning to mention Wittgenstein when I started this post. But I found the quote in Wikipedia and couldn’t resist the urge to make fun of Professor.

I was particularly fascinated by the F(Fu) part. I think I’ll make this my email signature:

“F(Fu)” – Ludwig Wittgenstein, Tractatus Logico-Philosophicus, 3.333

Speaking of Wikipedia, I ran into the following nonsense at http://en.wikipedia.org/wiki/Russell’s_paradox

“The Barber paradox, in addition to leading to a tidier set theory, has been used twice more with great success: Kurt Gödel proved his incompleteness theorem by formalizing the paradox, and Turing proved the undecidability of the Halting problem (and with that the Entscheidungsproblem) by using the same trick.”

Gödel’s proof has almost nothing to do with the Barber paradox, with the Liar paradox, or with Russell’s paradox. It has to do with Quine’s paradox (http://en.wikipedia.org/wiki/Quine%27s_paradox) which does not involve any self-reference on the syntax level. In the same manner, a program that can print out its own source code, is not self-referential.

Too bad I couldn’t find any good anagrams on the subject. And Wittgenstein could probably find meaning in any anagram. Professor even claimed that he could “readily think what Heidegger means”!

Have a consistent and sound New Year! (“Sound” means that no wish comes false) 🙂