davidlyness.com

One of the good things about maths is that everything you're working with must be "well-defined". That means that a precise mathematical definition must be given for anything you want to work with, be it functions, properties, operations or sets. And these definitions themselves must be based on even more fundamental concepts of mathematics, and so on. Eventually you get down to one of two things:

• axioms, or
• intuitive definitions.

Axioms are mathematical statements which are taken as "obvious" (I'll leave what "obvious" means in this context to the philosophers!) For example, an axiom saying that we can add two numbers together either way around and get the same result is called commutativity, and written \(a + b = b + a\). From this, and other axioms like it, we are able to build up all of the fundamentals of modern-day mathematics, which comprises the 1st year course in real analysis.

However, even these axioms have a more fundamental basis. If you visit the axiom link above, you'll notice that we define mathematical structures in terms of sets. Naive set theory tells us that a set is just a collection of objects - for example, an apple, a pear and an orange. We denote a set by putting curly braces around the objects in the set (called the elements of the set), and denote it by \[\{\text{apple, pear, orange}\}.\] Note that a set is uniquely determined by its elements - that is, if two sets contain precisely the same elements as each other, we say they are equal. We can also write \(x\in X\) to mean that "\(x \text{ is an element of the set } X\)". Two more simple rules about sets:

• The way a set is ordered is irrelevant: \(\{\text{apple, pear}\} = \{\text{pear, apple}\}\).
• Duplicates in a set are irrelevant: \(\{\text{apple, apple}\} = \{\text{apple}\}\).

Being mathematicians, we usually prefer to work with numbers rather than fruit. So, the set of non-negative whole numbers less than 10 would be \(\{0,1,2,3,4,5,6,7,8,9\}\), the set of square numbers less than 100 would be \(\{0,1,4,9,16,25,36,49,64,81\}\), and so on. In particular, we call the set containing no elements the empty set, and write it as \(\emptyset\). But what if we wanted a list of all the non-negative whole numbers? We'd write it as \[\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,...\},\] and we soon see that it would be quite impossible to write them all down! Such a set is said to be infinite - it has infinitely many elements. Since we can't denote such a set by writing down all the elements, we denote it by using a symbol - in the case of the example above, \(\mathbb{N}\). We have more symbols for other infinite sets:

• \(\mathbb{Z}\) for the set of all whole numbers (both positive and negative);
• \(\mathbb{Q}\) for the set of all fractions;
• \(\mathbb{R}\) for the set of all real numbers, which include numbers like \(\pi\).

If you look closely you can see that every element that is in \(\mathbb{Z}\) is also in \(\mathbb{Q}\) - in this case, we say that "\(\mathbb{Z}\) is a subset of \(\mathbb{Q}\)", and denote it by \(\mathbb{Z}\subseteq \mathbb{Q}\). In actual fact, each of the sets I mentioned above is a subset of its successor, and we can say \[\emptyset\subseteq \mathbb{N}\subseteq \mathbb{Z}\subseteq \mathbb{Q}\subseteq \mathbb{R}.\] Finally, a common practice is to define a set by specifying that all of the elements in that set must have a specific property. For example, above we defined the set of non-negative whole numbers that were less than 10. We would write this mathematically as \[\{ x \in \mathbb{N}:x < 10\}.\] This is how mathematicians proceeded for many years, and everyone was satisfied with this intuitive definition of sets. However, in 1901 a mathematician named Bertrand Russell published a paper in which he outlined a paradox derived from the very foundations of set theory. He proposed the following: take a set \(R\), which contains the sets which do not contain themselves: \[R=\{x:x \notin x\}.\] So far so good, as long as you can wrap your head around the notion of what a set containing itself would "look like". But there's nothing in our rules which says this cannot be defined. He then asked the question: does \(R\) belong to itself: is \(R \in R\)? There are two possibilities, either \(R \in R\) or \(R \notin R\). We consider each case in turn.

• \(R \in R\): then by definition \(R\) does not contain itself, and so \(R \notin R\), which is a contradiction.
• \(R \notin R\): then \(R\) does not satisfy the property of elements of \(R\): namely, it is false that \(R\) does not contain itself. Therefore \(R \in R\), which is again a contradiction.

In the second post on this topic I'll talk about how this issue was solved, and some interesting concepts that arose in set theory thereafter, which I've been studying this term.

You're on a game show, with the opportunity to win big. In front of you are three doors, behind one of which contains a car, and behind the other two doors are goats. After selecting a door, the host (Monty Hall), knowing what is behind each of the doors, opens one of the unselected doors to reveal a goat. He now gives you the choice: do you want to stick with your original selection, or switch to the remaining unselected door?

"Well," you think, "I have a 50/50 chance either way. So I might as well stick with my original selection." Monty Hall then opens the two remaining doors, revealing that you have chosen a goat, while the car lies behind the door you rejected in favour of your original choice. "A shame," says Monty, "you stood twice the chance of winning if you switched."

What I've just explained is a popular counter-intuitive problem in probability theory, most often called the Monty Hall problem. On first glance, it seems to be a simple problem. Your chance of choosing the correct door initially was \(1 \over 3\), and now that you only have two doors to choose from it seems reasonable that the chance of winning has risen to \(1 \over 2\). However, in reality your chance of winning never changed: you always had a chance of \(1 \over 3\) with your selected door, which leaves a \(2 \over 3\) chance that the car is behind the remaining unopened door.

A way to gain a more intuitive understanding of the puzzle is to consider another hypothetical game show scenario, except this time there are 1,000,000 doors instead of the usual three. After a door is selected the host opens 999,998 other doors, all revealing goats. You are then left with the same choice: to stick with your original door, or to switch to the one unopened door. Are you still convinced that there is a 50/50 chance of you being right straight off? Well, before any of the other doors are opened, you have a \(1 \over 1000000\) chance of winning. That means that you have a \(999999 \over 1000000\) chance of losing - that is, the chance that the car is behind a door that you did not choose is \(999999 \over 1000000\). Therefore, when all of the other doors have been opened leaving you with a choice between two, it is still the case that there is a \(999999 \over 1000000\) chance that the car is behind one of the other doors - but there's only one left! In this case, the chance of winning by switching doors will be 99.9999%. If you can grasp that, then the problem "scales down" to the three-door scenario where you have a \(1 \over 3\) chance of winning by sticking with your current choice or a \(2 \over 3\) chance by switching.

There are a few assumptions that need to be made in order to ensure that what has been described above really is the case. In addition to the intuitive assumption that the car is equally likely to reside behind any one door, we must assume that the host knows which door the car is behind - otherwise he runs the risk of revealing the car when he opens an unselected door... which would ruin it somewhat for the contestant! A variant on the original problem assumes that the host never knows which door the car is behind, but somehow always manages to reveal a goat when opening the unselected door. In that case intuition prevails and the car is won exactly \(1 \over 2\) the time - switching makes no difference.

A generalisation to N doors, with the host opening \(p < N-1\) goat doors before offering the player their choice. The probability of winning by switching is then \[N-1 \over N(N-p-1)\] and by the algebra of limits \[{N-1 \over N(N-p-1)} \rightarrow {1 - {1 \over N}}, \quad \text{as } p \rightarrow {N-2}.\] In addition, letting N tend to infinity, the probability of winning by switching tends to 1 - that is, the more doors there are to open in the first place, the more likely you are to win by switching doors.

Interestingly, when originally published in Parade (an American magazine), along with the correct answer that switching provides the optimal chance of success, the editors received over 10,000 letters insisting that the published solution was incorrect; including nearly 1,000 people holding PhDs! (I suppose this means that even mathematicians get it wrong sometimes...)

If you're interested in these type of problems, then you may also want to check out the Three Prisoners problem, a puzzle mathematically equivalent to the Monty Hall problem.