The Russell Paradox on the Web

Considering the great amount of interest in the web, I think it is easier to introduce the reflexive paradox in the context of the internet than in the abstract realm of set theory.

Webmasters can appreciate the Russell Paradox. As everyone knows, the web is about links. Any page worth its salt has links to other pages. Some pages (like my little Grand Junction Links Page) have nothing but links.

A web crawler is a program that crawls through pages on a web site. The typical web crawler reads a web page, then follows each of the links one that page.

Web crawlers have to worry about infinite loops. The simplest infinite loop happens when a page contains a link back to itself. For example, this page has the name russ.html. I made the name hot. The page links back on itself. It is "self-referential."

A web crawler needs to watch out for self-referential pages; Otherwise, it would fall into an infinite loop. If the bot was not programmed to handle recursive links, the bot would read a page, then follow the link back to the page, and read it again... To avoid infinite loops, the web crawler needs to maintain a database of all the places it has visited.

Now, we get into the problem that caused Bertrand Russell such angst a century ago: 

It is possible that a programmer is interested in displaying the self-referencing and non-self-referencing web pages on a web page. It's a fiendish trick. The web master simply instructs the web crawler to displays its results on a page. In our case, I instruct the unsuspecting bot to display the self-referencing pages on the page sr.html, and the non-self-referencing pages on nsr.html.

The Russell paradox occurs when the web crawler tries to crawl the sr.html and nsr.html pages. The first time the crawler reads nsr.html, it won't find a link back to itself. It marks the page as non-self-referential, automatically adding it to nsr.html. The page is now self-referential. The unhappy bot notices this. It corrects the mistake and marks the page as self-referential, automatically removing it from the nsr.html page.

The evil web programmer has created an insolvable paradox for the web crawler. A web page filled with links to non-self-referential pages is not stable. Each time the bot looks at the page, it reclassifies the page.

The web page with links to self-referential pages (sr.html) is stable, but can go either way. If sr.html did not have a link to itself, the bot would conclude that it is non-self-referential and leave it off the sr.html page. If sr.html had a link to itself, the bot would see the self-reference and leave the page unchanged.

The paradox of the Barber of Seville does a great job showing this problem. The barber in Seville boasts of having a monopoly. He boasts that everyone in Seville either has their hair cut by him, or they cut their own hair. The barber's sentence implies an exclusive or. A person either belongs to the set of people who cut their own hair, or whose hair is cut by the barber of Seville. Well, asks the humble logician, what about the barber himself? He belongs to both sets.

Back to Set Theory

The Russell Paradox is often introduced in set theory classes. Instead of using web pages and links, the professor refers to sets of sets.

Personally, I find it a lot easier to talk about web pages and web links. The internet analogy helps people keep clear in their mind the distinction between the container entity (the page) and the referencing entity (the web link). Talking about sets of sets garbles the mind. It is not immediately clear how a container can contain itself. 

Since the Russell Paradox is often debated in the context of transfinite theory, I fear that many students (and even some teachers) mistakenly concluded that the reflexive paradox is something that only affects transfinite sets. In reality, it affects any set with a self reference. The set could have as few as a single element.

Imagine the web crawler crawling a web site that contains only the infamous nsr.html page (you know, the page with links to non-self-referencing pages). The web crawler is now in a universe with only one page, but that one single page wreaks havoc on the bots sense of self esteem. It reclassifies itself with each scan of the crawler.

The reflexive paradox is not just something that appears when you start talking about the set of all sets. It is paradox that occurs whenever you have any type of self reference. The Russell Paradox is not something that suddenly appears with super large or transfinite sets. It is a problem that can happen in any self referencing system.

Logicians have know about the reflexive-paradox since antiquity. They chose to view the paradox as a time wasting Sophism. For the most part, you can live a long happy life, simply by avoiding meta-theories and self-references. 

Unfortunately set theory attempts to be an inclusive theory of everything, and a theory of everything has to deal with self-references. After all, "everything" itself is a thing; Somehow, this nebulous concept of "everything" must include "everything."

In the case of set theory, the set of all sets is, itself, a set. In Cantorian Set Theory, the set of all sets is transfinite. However, you can create the same paradox in a finite universe. Look at the table below:

Set Description Self-Ref?
Null No
SAS Set of all sets in this table
{,SAS,NSR}
Yes
NSR Non-Self-Referencing Sets
in this table.
paradox

 This table contains three sets: is the null set. SAS refers to set of all sets in this finite universe, and NSR refers to the set of non-self-referencing sets in this universe. The paradox exists in this finite universe.

Modeling the Paradox

We have already discussed creating a web crawler that chokes on the Russell's Paradox. Since we are dealing with a finite number of elements, it should be easy to create a computer program that models the paradox.

The first problem we come across in trying to model the program is one of definition. What in blazes is a "set," and how can a set contain itself? Mathematicians bandy about the term "set" as if were somehow the foundation of all mathematics. When I get down to act of coding, I find I haven't a clue exactly how to go about creating a set in a computer program.

A set is obviously an array of things, but what type of things? My inclination is to use object oriented design. I would create one object called an element, and another object called a set. The set object would contain an array of elements. Since I am interested in sets of sets, I see that an element object must somehow contain or extend the set object. I already have a dangerous circular reference.

While it seems easy to talk about sets of sets. It is more difficult to write down and code a program to test set theory. 

In trying to build this model, I found myself pondering a fundamental question about the relation between sets and its elements. Does the set physically contain the elements, or does it simply contain references to the elements? I realize that there is a fundamental difference between actually containing something and referencing something.

My initial understanding of a set is that of a simple physical container. We can symbolize this concept of a container with the bracket notation. I simply write out the members of the set delimited by commas and enclosed in brackets: This is the set of the first three integers:

{1,2,3}

The curly brackets denote the physical beginning and end of the set. Using the bracket notation, I can create a set of the sets  {1}, {2}, {3}. It would look like:

{{1},{2},{3}}

Container Objects

Note: with the container model (as demonstrated with the brackets example), it is impossible to actually construct an instance of a set with in a set. Making debates about the paradox moot. The paradox only exists in structures that cannot exist. Well, gosh, there are all sorts of paradox in things that cannot exist. Several schools of logicians demand that a logical structure must be constructible before we build our world around it.

In the bracket notation, the set of all sets in the system must have at least 1 more set of brackets than the contained sets.

Transfinite theorist contend that an infinite set with N members is the "same size" as one with N+1 members. If this is the accepted interpretation of the paradox, then yes, it is something that only applies to transfinite theory.

If this is the accepted interpretation, then I would cite it as further example that the transfinite theorist insistence that N=N+1 where N is infinite is incorrect. See  [Critique of the Diagonal Method]

With the bracket notation, I can create extremely complex sets. I can create a symbolic representation of sets within sets of sets. However, I can never create a physical representation of a set containing itself. I can prove this by counting the number of brackets. A set A that contains set B will always have at least one more set of outer brackets than set B. This is similar to Russell's theory of types.

The phrase "set of all sets" falls off the tongue so easily, but I am unable to create such a set with my limited bracket notation.

The idea that the set simply contains references to objects seems to fit better with the discussions I've read on the subject. For example, I earlier wrote out the set {,SAS,NSR} where SAS is a reference to the  set of all sets in my finite domain, and NSR is the set of non-self-referencing sets in my finite domain. I've abandoned the bracket notion. SAS is now a simple reference back to itself. 

SAS refers to the set {,SAS,NSR}. However, I cannot simply replace the symbol SAS with the data {,SAS,NSR}. If I did, I would have the set: SAS = {,{,SAS,NSR},NSR}. Notice I still have the reference to SAS in the set. So, if I replaced SAS with {,SAS,NSR} again, I would get: {,{,{,SAS,NSR},NSR},NSR}. This type of thing will go on forever.

The important point here is that there is some type of important distinction between a set actually containing the members of the set and the idea of a set containing references to its elements.

Trying to build a set that actually contains itself involves a infinite loop. Building a set that contains references to itself is fairly easy. However, we notice that in evaluating the set, there is always an additional step needed in a program to evaluate the references.

Rather than writing out a program at this time, I invite the reader to create a simple program that has two objects, a set object and and element object. The set object should have a method that looks through all the element objects to see if any of them refer back to the set.

With these base objects in place, you can try to create the infamous nsr (non-self-referential) object that extends element and is still a member of set. You will find that the program reclassifies itself with each iteration of the loop, just like the web crawler reclassifies the page nsr.html each time it reads the page.

You should execute the program several times in a step by step debugger. You will notice that there is a distinct step involved in resolving the reference, which brings us to my personal view of the nature of a self referential paradox.

The Self-Referential Paradox

Contradictory statements exist. Go to your local elementary school at recess. You are likely to here an argument of the form:

Stephie: "Timmie is lying."
Timmie: "Stephie is lyng."

These two young debaters are caught up in a serious head to head contest to win the favor of the playground monitor. Their statements contradict each other. It is easy to understand this scenario because we have two people with two different perspectives of the world. They might see things differently, or it is possible that one of them is actually lying. It is apparent in this heart felt debate that there are two different conflicting statements.

Self-referential paradoxes pops up on is in unsuspecting ways because self-referential paradoxes contradict themselves. We don't expect speakers to contradict themselves.

The most famous of all self-referential paradox is:

"This sentence is false."

This four word sentence is confusing because it appears to be a single, solidified argument that contradicts itself. It is only one sentence. There is only one predicate and object. There is only one speaker of the sentence, yet something is seriously wrong with the statement.

Now, the thing I have noticed about all self-referential paradoxes is that they all seem to contain a strange thing called a self-reference. Notice in the example above that the words "This Sentence" is not actually a thing, it is a reference to a thing. Replace the pointer "This sentence" with the full sentence "This sentence is false," and you can see that there is more than one argument involved in the statement:

"This Sentence is false" is false.

Each time you evaluate the reference "This sentence" you expand the argument and can see how it toggles back and forth: """This Sentence is False" is false." is false" is false.

By definition, all self referential paradox contain a reference back to itself. Although it appears that a given self-referential paradoxes is a single logical entity that contradicts itself, I am of the opinion that self referential paradoxes actually contain two logical steps: the resolution of the reference and the contradiction. A self-referential argument is just like the playground incident where two children have differing opinion.

Sentence A: "Sentence B is false."
Sentence B: "Sentence A is false."

Self-referential paradoxes appear as a different class of argument simply because we don't think of resolving the reference as a full logical step.

When we try to construct a self referential paradox in a computer, we notice that resolving the reference requires a logical step.

Descriptive Mathematics-Conclusion

The reflexive paradox caused a great deal of problems for logicians at the turn of the 20th century. This generation of logicians was trying to expand the theories of Kant, Cantor and Hegel into a general theory of everything. From a historical standpoint, the paradox plays an important role in the rifts that developed between the logicists, formalists and intuitionalist camps of mathematics.

From the vantage of Descriptive Mathematics, I am more interested in the students learning mathematics than in the arguments between dead mathematicians. The primary concern for the student is to learn how to use mathematics to develop and communicate their ideas.

Students need to learn that paradoxes do exist. Often people say contradictory things. The student's challenge in life is to root out the valuable information from white noise and lies.

The students need to learn the words paradox, contradiction and the primary rules of syllogistic thinking.

Students should know about the self-referential paradox,  recursive programming and infinite loops. It is also important to understand the difference between a reference and a thing itself.

Early programming languages like C++ and C made great use of references in the form of pointers. In developing programs (a sort routine is a good example), it is often more efficient to work with the pointers to the data than the data itself.

The index in a relational database is another good example of the use of references. The index might contain an ordered list of the primary keys of a table. It is often quicker to reference the index than to resort the table.

Most of the time, people use self-referential paradoxes to show how clever they are. I think a good teacher could create a lesson about the self-referential paradox that expose students to useful terminology and help expand their ability handle the contradictions that naturally pop up in life. 

Index - - Back to the transfinite

Descriptive Mathematics, Protophoto, Index, Sponsors
©2002 Kevin Delaney