Diversions in Mathematics #1: How to Count like a Pure Mathematician

If you want to know what this is all about, read my introduction to the series.

If you have already read the introduction, then welcome to the first Diversion in Mathematics! I emphasise, as I did in the introduction, that I will write with the general public in mind, so don’t be worried if you don’t consider yourself a “fan” of mathematics, or if you’ve totally suppressed all memories of maths classes from high school. And if you are a keen mathematician, whether recreationally or studying seriously at college/university, hopefully you will also find these blogs to be of some interest.

Counting and the Natural Numbers

Let us start at the very beginning: 1, 2, 3, 4, … This is presumably how you learnt to count when you were still a baby. Furthermore, as you may remember from Sesame Street (or similar shows for kids), counting and the learning of numbers always corresponds to pairing the number word, say eight, with a visual aid. To give an explicit example, we know that the following picture contains eight penguins:

falkland_islands_penguins_40

Eight (Falkland Island King) Penguins. Yes, there are eight, look closely! Source: Wikimedia Commons

Notice that I write ‘number word’, because it is only later in life that we learn to treat numbers abstractly. By this, I refer to the separation of the number word from the visual aid, so that ‘eight’ need not be understood only in the context of ‘eight penguins’, but stands by itself as an abstract entity. We learn to do this when we are introduced to arithmetic in primary school. We all know that it is possible and meaningful to say “two plus seven is nine” without referring to any physical objects, and so over the course of millenia, humans have devised symbols to express numbers. For example, seven corresponds to the symbol 7, if we use the Hindu-Arabic system, or VII in the Roman system, or  if you use Chinese characters, and so on. In fact, the labels actually don’t matter, the important thing is to have a system for counting. Now we know intuitively what the word ‘counting’ means, but how do we really define counting? No, there’s no need to reach for the dictionary, we are doing maths here. Let me suggest a definition of sorts. Grab any object, let’s say a plush-toy penguin. We can all agree, provided we use the English language and the Hindu-Arabic numerals, that a single object will always correspond to the number called one with the associated symbol 1. As it turns out, we only need one other condition: to agree that getting another plush-toy penguin (or whatever your object of choice) will correspond to an action we call adding one (+1)Now I claim this is all you need, mathematically speaking!

Suppose you meet a representative from an intelligent alien civilisation, and clearly neither one of you speaks the language of the other. Nevertheless, you are eager to start collaborating on mathematics (maybe they have proved the Riemann hypothesis?), and the natural place to start is… well, with the natural numbers, which is what mathematicians call the counting numbers. [An important side note: it was not obvious to our ancestors that zero is a number, and in fact, the discovery or invention of zero is one of the most important results in the history of mathematics. Many mathematicians include zero in the natural numbers, but for now, we’ll stick to counting starting at ‘one’]. As long as you manage to convey to the alien visitor the meaning of one and the concept of adding one, the rest is simple. Convey the meaning of two by adding one to one, and likewise, show that three is the result of adding one to two, which you have already defined. To see this in action, watch this inexplicably hilarious Khan Academy video:

Now it is your job to convince your intergalactic colleague to repeat the same process. Suppose you learn that one corresponds to un. Then by adding un each time, you can learn the labels for each successive natural number in the foreign language. Maybe it goes a bit like this:

  • 1: un
  • 2 = 1 + 1: deux
  • 3 = 2 + 1: trois
  • 4 = 3 + 1quatre

and so on. (At this point, I hope any French readers out there have a decent sense of humour). Of course, this gets tedious after a while, and both of you will inevitably need to learn each other’s number system to anything useful, but in principle, you can learn the label for any natural number this way. Furthermore, you have exploited an important feature of the natural numbers: order. As you have probably observed, any natural number not equal to one has a unique successor and predecessor (remember, we are not considering zero for now). Why is the uniqueness important? In this case, it ensures that our operation of adding one is well-defined. When you add one to nine, for example, you can only get ten. Likewise, there is a unique number that comes before twenty, namely nineteen, and so on. This makes it possible to say, for example, that five is less than seven, which is written 5 < 7. Equivalently, we can say that seven is greater than five, and write 7 > 5. It is this ordering of the natural numbers that allows us to count.

You might be thinking, ‘what a waste of time, I certainly knew that!’ But think about how important it is in our daily lives to be able to discern not only what a specific quantity is, but also how different quantities relate to each other. Take a look at the following figure. Which set, A or B, contains more black dots?

setsab

It is immediately obvious, isn’t it? You can count how many dots are in each of the sets, and hence determine which is larger as a result of the ordering property of the natural numbers. But this is because we also possess the number system to describe exactly that set A contains 4 dots, and set B contains 7. Now suppose you were a child of the Warlpiri indigenous Australians, whose language only makes distinctions between what is essentially “one” and “two”, and all other quantities are described as “few” or “many”. You won’t be able to describe in words that “set A has four dots”, but you can certainly work out which set has more. Simply take one dot from A and pair it with a dot from B, and you will end up with some quantity of dots in B without a matching partner from A. Then you must conclude that B has more dots than A, although you won’t be able to express exactly how much more. But you certainly can tell when B has exactly one more than A, and once again we return to the fundamental notions of “one”, “adding one”, and the ordering of natural numbers. Keep this example in mind, as later on (in a future post), we will discuss more formally the concept of taking a thing from one set and pairing it with an element from another set.

It seems I’ve just taken you back to kindy class (that’s kindergarten, for the readers who may not be aware of the Australian custom of abbreviating everything), but in fact I have disguised some very important mathematical notions in this section. Experienced mathematicians will also notice that I have been rather naughty, since I have introduced various concepts with no rigorous definitions, instead appealing to the general reader’s intuition. But I hope you will understand that this blog isn’t the place to give a full treatment of Peano axioms and other such formalisms. Nevertheless, we have discussed enough for the general reader to proceed to the next section. So far, I have stressed that the number labels (1, 2, 3, 4, …) are not actually important, all you really need are notions of “one” and “adding one”. This suggests that we can construct the natural numbers from even more fundamental concepts than numbers…

Sets

We will now introduce what is perhaps one of the most fundamental of mathematical concepts.

Definition 1.1

  • set is a collection of objects.
  • If some object x belongs to a set A, we say is an element of A, and write x ∈ A.
  • The set with no elements is also a set, and is called the empty set, denoted by ∅.

That was easy, wasn’t it? In fact, I have already sneaked the term into the previous section. You will already have intuitive notions of sets. For example, consider the set A = ‘set of all birds’, then obviously owl ∈ A, penguin ∈ A, but llama ∉ A (notice the crossed-out symbol denoting ‘not an element of’). Sets can also contain other sets, and this is in fact a very fundamental concept in mathematics. For example, let B = ‘set of all flightless birds’. Then B is a subset of A, and in mathematical notation, we write B ⊂ A. Because mathematicians love symmetry, you can also write this as A ⊃ B. (Notice how similar this is to the notation 1 < 2 and 2 > 1, I am anticipating the discussion ahead…). Another way of saying this is that every element of B is also an element of A, and in our example, this says nothing more than ‘all flightless birds are birds’. One more fact before continuing: when writing down elements of sets, duplications are not counted, so the set {1, 2, 3} is the same as {1,1, 2, 2, 3, 3, 3}.

Sets are quite naturally visualised in Venn diagrams. It is a bit of a mystery to me why some basic set theory isn’t taught in high school. Given the proliferation of Venn diagram memes on the internet, I am sure it can be approaced in a fun way:

venn-diagram-beaver-duck-platypus

In the first example… I have absolutely no idea how that relates to maths, I just really like that meme. But in the second example, we could define A = set of all symbols of chemical elements, and B = set of all abbreviations of US states. The elements that are in the overlapping region are elements of both A and B, so is there a way to denote them? And can we also denote the set consisting of everything in A and B? Indeed we can, and the definitions are quite natural:

Definition 1.2

  • Let A and B be sets. Then is in the intersection of A and B if x ∈ A and x ∈ B. We denote this x ∈ A ∩ B. It should be clear that A ∩ B is a subset of A and also of B. Hence the set A ∩ B is the set of all elements that are in both A and B, and in mathematical notation:

A ∩ B = { x | x ∈ A, x ∈ B }

[The curly brackets collect elements of a set. The stuff in between can be read as follows: “(all) such that is an element of A and also of B.” The comma (,) often represents “and” in the language of maths. The bar | represents “such that”, and equivalently may be written with the colon : instead.]

  • The union of A and B is denoted A ∪ B, and is defined as the set consisting of all elements in A and all elements in B:

A ∪ B = { x | x ∈ A or x ∈ B }

Earlier I hinted that we could construct the natural numbers, and indeed, one of the ways to do it is using sets. The following approach is paraphrased from Paul Halmos’ text Naive Set Theory. By the way, he takes 42 pages to get to this point, so you can thank me for saving you the trouble. (But in all seriousness, given how rigorously Halmos treats the subject, it’s actually surprisingly concise. Halmos’ approach is based on something called Zermelo-Fraenkel set theory).

Take the empty set ∅, and then consider the set containing the empty set {∅}. There is a world of difference between the two. The empty set clearly has no elements, while the other contains one element: the empty set! (Recall that sets can contain other sets). Now here is the exciting bit. For any set X, we define its successor to be the set obtained by joining with the set containing X, namely {X}. Denote this successor as X+ (following Halmos’ notation), then X+ = X ∪ {X}. We start with X = ∅, so ∅+ = ∅ ∪ {∅} = {∅}. The last step comes from realising that the empty set doesn’t contain anything, so joining it with the set {∅} just gives {∅} again. Let’s write this new set ∅+ = \mathit{1}. Then applying the same procedure gives \mathit{1}+ = \mathit{1} ∪ {\mathit{1}} = {∅} ∪ {\mathit{1}} = {∅, \mathit{1}}. We may as well call this new set \mathit{2}. Continuing this process of joining up sets and labelling the results, we get the following sequence of sets:

  • ∅+ = \mathit{1}
  • \mathit{1}+ = \mathit{2}
  • \mathit{2}+ = \mathit{3}
  • \mathit{3}+ = \mathit{4}

and by now, I think it’s quite clear what this looks like! Moreover, we have the following relationship between the sets:

\emptyset \subset \mathit{1} \subset \mathit{2} \subset \mathit{3} \subset \mathit{4} \subset \mathit{5} \subset \ldots

which should instantly remind you of 0 < 1 < 2 < 3 < 4 < 5 < …, the ordering of natural numbers.

Notice that this construction uses nothing but the basic definitions of sets. It does not even require any notion of arithmetic, since we have effectively defined “adding one” by adjoining sets, which is why I liked Halmos’ suggestive notation X+. It also quite naturally includes zero (hooray!), using its set-theoretical counterpart, the empty set. For a rigorous treatment, there is still a bit of housekeeping to do before we can claim to have defined the natural numbers properly, and so I attach an extract from Halmos’ book if you wish to see how to complete the argument (I do not find it to be an easy conclusion). At this point, perhaps you’ve had enough of counting like a pure mathematician, and I can’t blame you for that. However, there is still one more thing to do. Using more familiar notation, we can rewrite the construction above using numbers (now that we’ve “defined” them):

Definition 1.3: Inductive construction of the natural numbers

The set of natural numbers N is a set with the property that:

  • 0 ∈ N
  • if n ∈ N, then + 1 ∈ N

[Note: the N should really be a fancy \mathbb{N} , but I can’t get LaTex working within those quote boxes].

Hopefully this definition is quite clear by now, as it is completely analogous to the construction with sets. But is it clear that this process of “adding one” can be continued indefinitely? In fact, it can be logically concluded from the above constructions that the set of natural numbers must be infinite. We can show this as follows. Suppose there is a “last natural number”, we call it Z. Then Z \in \mathbb{N} , but by the definition above, we must also have Z + 1 \in \mathbb{N} . By the ordering of natural numbers, Z + 1 is certainly larger than Z, which is a contradiction. To explore infinity further, we must pay a visit to Hilbert’s Hotel — our topic for next time!


References

Butterworth, B., Reeve, R., Reynolds, F., & Lloyd, D. (2008). Numerical thought with and without words: Evidence from indigenous Australian children. Proceedings of the National Academy of Sciences of the United States of America, 105(35), 13179–13184. http://doi.org/10.1073/pnas.0806045105

Halmos, P. (1974). Naive Set Theory. New York, Springer-Verlag.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s