Brown Dogs and Barbers

How a crisis in mathematics led to set theory and type theory

Mathematicians have many different ways at their disposal to express their ideas, most of which are inter-related and build on one another. One might assume that, of all these systems of communication, there is a foundational one that lies at the root of all others … a common language for every type of mathematical idea. There are several candidates and the most commonly accepted one is set theory. Set theory is another idea that was developed by pre-computer mathematicians who had no clue that their work would one day be so important to computer scientists.

Developed in the 1870s, set theory is quite simple. It expresses all its ideas in terms of sets. And a set is nothing more than a number of things grouped together because they share one or more common properties. A similar idea, with which you are probably familiar, is the Venn diagram. I’ll bet that in maths class you drew diagrams like this one:

This diagram shows two sets. The set of all brown dogs is represented by the circle on the left, and the set of all white dogs by the circle on the right. The two sets overlap because some dogs are both brown and white, a fact that yields a third set — all dogs that are brown and white. This simple example demonstrates the basic elements of set theory: judging which objects belong in a set and creating new sets by playing around with existing ones.

We can say that the set of all brown dogs is B, the set of all white dogs is W, and the set of all brown and white dogs is M (multi-coloured). Using set theory notation, M is defined like this:

M = B ∩ W

You would say: “M equals the intersection of B and W.” That funny-looking arch between B and M is an operator you use to fiddle around with sets to make new sets, a process called intersection. Intersection creates a new set that contains only those objects that are in the both original sets. There are many other operators that you can use to combine sets in creative ways.

Furthermore, because we’re operating in the abstract world of maths, it’s actually possible to define arbitrary sets. For example, you can declare that a set contains all numbers between 1 and 10. You could then intersect it with a set that contains all even numbers. This would yield a new set containing only the numbers 2, 4, 6, 8 and 10. This is how, on a most fundamental level, a mathematician could define all the even numbers between 1 and 10.

So far, so good. Set theory looked very promising after its initial development, until a certain philosopher and mathematician came along to spoil the party around the turn of the twentieth century. This was Bertrand Russell and he’d found a problem with set theory.

Set theory looked very promising after its initial development, until a certain philosopher and mathematician came along to spoil the party.

In purely mathematical terms, the problem was as follows: sets may contain other sets, just like a box may contain other boxes. In Russell’s time, it was even considered acceptable for a set to contain itself; for example, the set of all non-dogs contains absolutely everything that is not a dog — everything, including the set itself. After all, the set of all non-dogs is not a dog, it’s a set. Knowing this, Russell postulated another set called S, which is defined as containing every set that doesn’t contain itself. The question is: should S itself be in that set? If you leave S out of such a set, then S doesn’t contain itself and therefore must be in that set. But if you do put S in that set, then it no longer belongs there because it now contains itself (thus violating the original definition of S).

For those who struggled to understand the problem, Russell rather sniffily redefined it using an analogy that was suitably rooted in his Edwardian times: Imagine a town, where everyone likes to keep clean-shaven. Suppose the only barber in town operates according to the following rule: he shaves all and only those people who do not shave themselves.

Now, the question is: can the barber shave himself and stick to this rule? Let’s look at the possibilities:

• If the barber shaves himself, then (according to his rule) he belongs in the set of people the barber doesn’t shave and therefore cannot shave himself.
• If the barber doesn’t shave himself, then he belongs in the set of people the barber shaves and therefore must shave himself.

We can happily apply the rule to every man in the town. But when we apply the barber’s own rule to himself, we end up with a paradox.

The question was: How should this be dealt with? It may appear to be a trivial problem, but Bertrand Russell knew that problems like this — using seemingly valid rules to reach conclusions that could be both true and false at the same time — threatened the validity of mathematical logic. If set theory was the foundation of all mathematics and it was faulty, then all of mathematics and science was in trouble. We could unknowingly use steps that seem valid to prove true things false or false things true. We could not be sure about any logical argument, no matter how valid it seemed. Mathematicians began to worry that entire theories would come crashing down. They were in one heck of a pickle.

We could unknowingly use steps that seem valid to prove true things false or false things true.

Clearly, there have to be some restrictions on what kinds of sets it’s possible to create and some, as yet unknown, rules to be discovered. The rules Russell proposed were packaged together under the name type theory. Type theory said that, when making logical arguments, statements should be classified according to a hierarchy of types. At the bottom level of the hierarchy are statements that talk about the indivisible entities you’re dealing with. At the second level come statements that talk about groups of entities. The third level consists of statements concerning groups of groups of entities and so on upwards.

The key rule of type theory is: you cannot mix up the levels when you form a statement.

When we apply this to our barber example, we find that the individual entities are men. You can’t say much more about them until you start to define types for them. Two example types could be “citizen” and “businessman”; an arbitrary person could be of neither, one or both. Now armed with our types and our key rule, let’s try again.

Saying someone is a barber is to assign them a type and thus makes a statement one level above that of individual persons. But notice that the same statement refers to both men and barbers — the problem is that the statement (the barber shaves all and only those men who do not shave themselves) mixes up the levels and is therefore disallowed under type theory. To resolve the problem, consider the barber as both a citizen and a businessman. At work, the barber considers himself a businessman and shaves all types who do not shave themselves. At home, the barber is a citizen, who shaves himself. We have therefore avoided the paradox and rescued mathematics from the brink in one fell swoop. And as an added bonus, the barber remains free of face fungus.

When people write programs, they do so according to strict type systems which make absolutely clear the nature of the information being processed.

Today, types are an essential part of computer programming as you’ll see in a later chapter. When people write programs, they do so according to strict type systems which make absolutely clear the nature of the information being processed (like whether or not something is a number, whether or not it’s part of a group, and so on). In this way, a computer can automatically check whether a program contains a logically invalid statement and thus prevent catastrophic commands from being run.

That’s set theory in a nutshell. Many believe that it serves as the fundamental language of all mathematics. This is why computer scientists, who are seeking to understand the very fundamentals of computation, are so interested in it. In theory, any mathematical problem (and therefore any computational problem) can be expressed in terms of sets and the relationships between them.

But as we’ve seen, there are restrictions on what we can do with set theory. If it is indeed the fundamental language of mathematics, then this implies that there are restrictions on what we can compute. As you’ll see in a later article, the truth of this implication became a critical issue when computer science began its formal existence.