More than 150 years ago, the German mathematicians Richard Dedekind and Georg Cantor introduced a “set theory.” Thirty years later, the British philosopher Bertrand Russell stumbled upon a contradiction that he could not resolve within the framework of the original theory.
Playing with the logic of set theory, Russell noticed that it allowed the existence of a set, which is defined as a collection of sets that do not contain themselves. Being a mathematician, Russell failed to assign any mathematical statement that would describe something that could not exist.
If we assume that the set of all sets that do not contain themselves (we will call it Russell’s set) can exist, then it will be mathematically proved that it does not. For if Russell’s set contains itself, it should not be in the set; if it does not, it should be in the set.
You might ask: who cares? After all, what does abstract theory have to do with our global or everyday problems? Actually, it’s a lot more than you might think. Set theory is one of the few areas that lies on the edge of mathematics. This only means that it is a logical problem.
You probably know that mathematics is a subset of logic. A philosophical approach called the logicist programme reduces all mathematics to logic. Some mathematicians disagree with this. One thing is clear: the first sentence of this paragraph uses logic and refers to set theory (go ahead, read it again).
Mathematics provides a language that allows logical statements to be expressed with the necessary precision. This ability enables mathematicians to construct very complex conclusions with the confidence that they have not erred. This is the distinct feature of logic – it can provide logical proof of something we can call an objective, verifiable, and undeniable truth.
Logical reasoning is an essential component of human intelligence. It is responsible for our ability to reason. Since its invention some three thousand years ago, mathematics has evolved as a universal language of complex logical statements. This was the case until very recently. With the invention of computers and programming languages, there are many ways to build complex logical statements in an automated and objective environment that helps you to detect and correct errors.
For a long time, any logical statement that could not be expressed mathematically had to be encoded using natural languages like English, German, or French. While these languages are good for literature and poetry, they lack the precision needed for logical reasoning. Programming languages do not have this problem. Programming is used to instruct computers on how to perform complex tasks. I can demonstrate how programming language can be used to solve logical problems.
For example, let’s look again at Russell’s paradox. A set is defined as a collection of distinct items called elements or members. While mathematics is usually good at dealing with abstract entities, it becomes too complex when dealing with the real world. This definition of a set may be suitable for a mathematician, but it is not precise enough for a programmer. First, we need to define not only the set but also the elements.
The members of a set “belong” to the set, but they are not part of the set. A set just defines the criteria by which one can determine whether a given element is a member of the set. Such a definition must be expressed only in terms of measurable characteristics of the elements. Such characteristics are called properties. Following this logic, we can modify the original definition of a set:
Now, it’s time to use some precise language. Let’s define a set as an object that inherits the following class:
public class AnySet()
{
public virtual string Filter => "false";
public virtual bool IsPartOfMe(Object element)
{
var lambdaParser = new NReco.Linq.LambdaParser();
var varContext = new Dictionary<string,object> { ["element"] = element };
try
{
return (bool)lambdaParser.Eval(Filter, varContext);
}
catch (Exception ex)
{
return false;
}
}
public bool EqualsTo(AnySet? another)
{
return this.Filter == another!.Filter;
}
}The class has a Filter property that represents an inclusion function. The class also has an IsPartOfMe method that takes any object and passes it through the filter by executing the include function with that object as a parameter. Another EqualsTo method can be used to compare two sets.
The include function decides whether an element is a member of a set. It can check any combination of element properties, but it should not use anything else to make this decision. For example, you can define the set of all apples, but it would be ridiculous to define a set that contains apples when it rains.
We can use this class to define a particular set. For example, the class representing a set of all numbers between 0 and 100 would look like this:
public class SetOfNumbers100 : AnySet
{
public override string Filter => "element >= 0 && element <= 100";
}With a statement like this, we can check whether a number is part of the set:
var theSet = new SetOfNumbers100();
if (theSet.IsPartOfMe(5.76)) {
// confirms that number 5.76 belongs to the set of numbers betwee 0 and 100
}We can define an empty set as a set that contains no elements:
public class EmptySet: AnySet
{
public override string Filter => "false";
}Notice that this set is empty by definition. However, for any other set, there is no universal way to determine how many elements it contains and whether the set is empty. If we can find an element that belongs to it, this proves that the set is not empty. But it is impossible to prove the opposite.
Since a set is an object, we can define a set that contains all sets:
public class TheSetOfSets: AnySet
{
public override string Filter => "element is AnySet";
}Using the same approach, let’s define a set of all sets that include themselves. The code will look like this:
public class SetThatIncludeItself: AnySet
{
public override string Filter => "element.IsPartOfMe(element)";
}The Russell’s set uses a very similar filter. It is defined as a set of all sets that do not contain itself:
public class SetRussell: AnySet
{
public override string Filter => "!element.IsPartOfMe(element)";
}The code looks correct. We can even try to validate the statement that the set of sets is a member of the set of all sets that include itself:
var theSetOfSets = new TheSetOfSets();
var theSelfIncluded = new SetThatIncludeItself();
if (theSelfIncluded.IsPartOfMe(theSetOfSets)) {
// confirms that Set of sets is a set that includes itself
}Even though the code above works, the definition of a set is wrong. If you try to use it on itself, it will enter an infinite loop:
var theSelfIncluded = new SetThatIncludeItself();
if (theSelfIncluded.IsPartOfMe(theSelfIncluded)) {
// will never reach this point
}From a programmer’s point of view, Russell’s paradox is not a paradox at all. It’s just a bug. The set that includes itself and one that does not contain itself are both invalid. Because they both define the inclusion function, which tries to use something other than the element’s property.
This is a classic case of invalid design due to vague definitions. The inclusion function is the primary property of a set. If a set is an element, then the value of the property called Filter can be used by an inclusion function. But the result of the function cannot.
Russell’s set is an attempt to stretch the definition of a property. Russell tries to create an inclusion function that depends on its own result, a concept known as recursion in programming. The inclusion function of Russell’s set lacks an exit option, causing it to enter an infinite loop, trying to call itself. In essence, Russell’s Paradox is nothing more than a logical fallacy.
Q.E.D.
Sergey Kucherov