“This sentence is false.”
Attempting to decide whether or not the previous sentence is true or false yields a paradox. This paradox has been known for centuries and is called the Liar paradox. It is a very simple manifestation of a far-reaching idea, which will, ultimately, ruin our attempt to define numbers via the route we have been going down.
Enjoyment of this post really does require the reader to have understood the previous post.
Remember, at this stage we are trying to define an abstract notion of number, and in order to do so we cannot use numbers!
First let’s see if we can make more precise the promising idea we were heading towards at the end of the last post. We described a way of relating two sets to one another by pairing off the elements one-by-one. We said “For each element of the first set there is a single element of the second and for each element of the second there is a single element of the first.” When this is true we say that the two sets are in bijection with one another or that there exists a bijection between them. (I should add that although I have said words like ‘single’, the notion of bijection really doesn’t use numbers at all – there are other ways of phrasing it, e.g. by use of the Cantor-Schroeder-Bernstein theorem)
Two sets being in bijection with one another is a potential relation between pairs of sets that tells us when two sets have the same size without having to use numbers to say how many elements they each have.
Let’s just pause to get our heads around that big collection. It is a very large collection of sets. It contains sets like the set of three oranges and the set of three apples which I spoke about in the last post. It also contains a set of twenty-seven giraffes and five billion apostrophes and the set of whole numbers from one to eight-hundred etc.. If the set of all sets does not seem like a stupendously vast thing to think about then you have not understood what I am saying. This collection contains every conceivable collection of every conceivable thing. In my opinion it is almost more philosophical than mathematical and one can’t do much to make it more tangible: It is a monstrosity. The reason why it is a useful idea here is because it really does enable us to abstract away from numbers. I can summon it into existence without saying things like ‘twenty-seven giraffes’, I just say ‘the set of all sets’.
Let’s think about the equivalence classes of this relation. What general observations did we make about equivalence classes in the previous post? Well, the equivalence classes divide up the big collection into smaller subsections. Within each subsection, everything is equivalent to one another. So, if we jump ahead for a moment and allow ourselves to use numbers explicitly then we can describe what is going on here more easily: An equivalence class contains all the sets of a given size. For example, all the sets with four elements constitute a single equivalence class. They are all the same size and so can all be paired off with one another; bijections exist between any pair of sets in this subsection because all the sets in this subsection have four elements. Note however that we didn’t need to mention numbers in order to think about these classes, I only mentioned them to illustrate what was going on more explicitly. Instead I could have said: “Take the set of all sets and define an equivalence relation by saying that two sets are equivalent if you can pair off their elements one-by-one. What are the equivalence classes?”
The point is that for each positive whole number (e.g. ten) there is an equivalence class (the set of ten-element sets). But, the problem is that we are still unable to refer to a specific equivalence class without saying something along the lines of “‘the one with all the ten-element sets”, which is unsatisfactory because it uses the number ‘ten’ explicitly. How do we get around this problem of reference?
We need some way of referring to the collection of ten-element sets, say, without mentioning the size of the sets it contains. I’ll explain very roughly how this problem can be solved. After that we’ll discuss the flaws in the premise.
We’ve already spent a lot of time thinking about the most basic characteristics of the positive whole numbers, or the natural numbers as I like to call them, but one aspect which we haven’t considered yet is their order. After all, they are in a specific order. ‘Five’ is the number which comes after ‘four’ and before ‘six’ is it not? We haven’t actually used this fact at all yet. The idea of this section, that each number has a successor is a very basic one then when dealing directly with numbers: We start with four. We add one. We end up with five. Five is the ‘next’ number after four. However, things are a little bit more tricky when dealing with just sets and no numbers at all. It is here that I will be rough.
Suppose I have a set with a single element, a one-element set. If I were to ask “What equivalence class am I in?” The answer would be “The class of one-element sets”. Fine. Suppose I add an element to my set and then ask the same question. The answer is now “The class of two-element sets”. I could continue this process, adding another element and asking the same question again each time. This would go on forever but crucially, given any natural number, say six-hundred, I would eventually land in the equivalence class of six-hundred-element sets. This equivalence class represents the number six hundred itself! This is the basic idea in set-theoretic terms, although I am glossing over numerous technicalities.
So, what we have is a long chain of equivalence classes, each of which is the successor of the previous one in this manner. I then declare that this chain of equivalence classes is the natural numbers. Now, the number five (which is referred to as the successor of the successor of the….of the number one), contains all the five-element sets and nothing else. This definition is naive, but it was a genuine candidate, back in the 19th Century, for the definition of the natural numbers. You can see it outlined here on Wikipedia under ‘the oldest definition’.
I will wrap up this discussion before it spirals out of control. We have been working on the foundations of mathematics, thinking about whether or not it is possible to put the simplest and most basic notions such as number, on rigorous footing. We haven’t done very well in these four blog posts, to be honest. We have failed.
The most catastrophic failure is our use of the set of all sets. This is bad because accepting its existence leads to a very well-known paradox called Russell’s paradox. Russell’s paradox has numerous different forms, all of them based on the idea of impredicativity and self-reference. Discussing any of these things in depth would be opening a can of worms, but it is a fun can of worms to nose around in if you are that way inclined.
One of the most straightforward manifestations of the paradox is the liar paradox at the start of the post. Another is : In a small town there is one male barber. His rule is that he shaves all and only those men who don’t shave themselves. Seems reasonable. Does the barber shave himself?
The version we encounter directly if we allow the validity of constructions such as “set of all sets” is the following: Consider the set of all sets which don’t contain themselves. Does this set contain itself?
[To see that sets which contain themselves aren’t paradoxical a priori: the set of things that aren’t elephants must contain itself because it is not an elephant…however the set of all elephants does not contain itself for the same reason. The paradox starts when we allow ourselves to say consider all the things which satisfy a certain property, without worrying about what the property is.]
In conclusion, we have not achieved nothing, but we do need to be much more careful than we have been when dealing with foundational issues in mathematics. It is an entire area of research in itself, even today.