Russell's paradox from a programmers point of view

Recursion means essentially talking about oneself (yes, we all have one friend doing that all time). For example, the index of a programming  book talks about the book itself not really about programming. Or, "this sentence has five words" is self-allusive. As a child I was puzzled by this box of biscuits which was decorated with a picture of a boy eating biscuits from a box painted like the real one. I could then imagine a box inside a box inside a box... 

Clearly, recursion may be fascinating at first sight but it is also slippery. Don't you think so? Then, try to imagine yourself thinking of yourself thinking of yourself. You can't, right? Probably our minds have strong fences preventing us from getting stuck in an infinite recursion! 

But beyond fun, recursion has also puzzled mathematicians: for example, Bertrand Russell showed that recursion can lead to unsolvable paradoxes in set theory. I will try to explain it in simple a manner. For this purpose, let us first define more precisely what we are talking about: 

• A set is a collection of objects (for example, a collection of books).

• Sets are objects themselves, and can therefore belong to a collection (for example, my collection of books belongs to the collection of all libraries ;).

• A set can be a member of itself (for example, by definition, the collection of all sets one can define is also a set).

• It is a natural question to ask whether a certain object is a member of a given collection.

Suppose that it were always possible to determine if a given object belongs to a particular set ("always" here means "for every object and for every conceivable set").  Then, the set R made of all sets which are not a member of themselves breaks this assumption. Russell's argument is a logical one: it is contradictory both saying that R belongs to R and also the opposite (R is not a member of R). You can check easily that, in both cases, one reaches a contradiction.

Let us examine the paradox from a (Java) programmer point of view. The following code defines what a (computable) set should be (we will discuss later what the adjective computable adds to the meaning of set): 

/**

 * The definition of a computable set: there is a function which answers if an

 * object o is a member of the set or not

 */

public interface ComputableSet {

    public boolean contains(Object o);

}

A Java interface is nothing but a contract which all valid implementations must follow. In this case, this peace of code means that a computable set is a special kind of object which implements a function answering membership queries. 

One implementation which fits the above specification of computable set is the definition of the Russell set R:

/**

 *  The Russell set R contains all sets with are not a member of themselves

 */

public class RussellSet implements ComputableSet {

    @SuppressWarnings("unchecked")

    public boolean contains(Object o) {

        //first check if the object is a ComputableSet

        if (o instanceof ComputableSet) {

            ComputableSet s = (ComputableSet)o;

            System.out.println("I'm thinking");

            return s.contains(this) == false;

        } else {

            return false;

        }

    }

    public static void main(String[] args) {

        RussellSet R = new RussellSet();

        boolean paradox = R.contains(russell);

        System.out.println(paradox);

    }

This program just translates the definition of R into a few lines of code: membership is resolved by first checking if the object is a set; then, it checks whether the set contains itself or not, and answers accordingly. What happens if we compile the code and then execute the main function in RussellSet?  A long run of "I'm thinking" statements appear then on screen till the program stops when it reaches the maximal number of recursive calls (essentially preventing memory to be exhausted).

In conclusion, the famous Russell's paradox is nothing but an ill-defined piece of code: obviously the definition of a set must provide a membership function which is guaranteed to terminate! That is exactly the meaning of the word "computable" which precedes "set": a computable set is equipped with a membership function which, whatever the input, always returns an answer (perhaps, after a long time, but that is another issue). 

Unfortunately, this natural requirement does not solve all the problems since it leads to a new question: is there a procedure to determine if a membership function always returns an answer? In other words, how do we check if a set we have defined is computable? And, will be this procedure computable? [Oh, here we meet recursion again!]

Unfortunately, there is no such procedure, as we will see soon.