fishface.org.uk

Here are the (slightly expanded) notes from my talk about Ultrapowers.

It's time to make a post about MATHS.

Most people who know some mathematics know that there are infinitely many natural (whole) numbers. It's easy to see — you can always add one to a number and you get a brand new one. Clearly this also goes for many other sets: there are infinitely many even numbers, odd numbers, rational numbers (fractions) and real numbers (decimals). But one of these sets is not like the others — it is bigger than the rest!

Most people (unless they have inside knowledge) will think this is either obviously true or obviously false, and they will both be wrong! The first person will think that there are obviously more natural numbers than evens, more rational numbers than natural numbers, and more real numbers than rational numbers (since every fraction can be written as a possibly repeating decimal, but there are irrational numbers, like .) The second will think that they are all just infinite, and therefore the same size — if you add something to infinity, you still have infinity.

The first person is right, to a point. However in mathematics once you get to dealing with infinite sets we need to pin down what we mean by "size", and the concept we landed on is "cardinality." The upshot is just that two sets are the same size if the elements of each set can be paired off with each other, so that all elements of set A have one and only one corresponding element in set B, and vice versa.

Thus there are as many natural numbers as even numbers, because we can pair each number with the even number . It's easy to see that there is one, and only one, for each , and one, and only one for every even number — since an even number is a number in the form :

What we've done is exhibited a bijection between the set of natural numbers, , and the set of evens, . A set that is in bijection with the natural numbers is called countable. The link shows how it is possible to prove that the set of rational numbers is countable.

So, up until now the second person was correct, but no longer. Cantor proved in 1891 that there are more reals than there are naturals — that the set of reals is uncountable.

The proof is quite simple. Suppose is countable, and we will find a contradiction, so what we supposed is impossible, and must be of a different cardinality than . (And, since , it is clearly bigger!)

To be countable, there must be a bijection — a function from to pairing off the elements with each other. We can illustrate such a function as follows:

Now we have to imagine that this table goes on forever down and right, since there are infinitely many s, and each can be infinitely long if it is irrational, but that's OK. This table just illustrates what part of one possible potential bijection would look like, and we are about to argue about any candidate — it's important to remember that whatever we try, this argument will still apply, whether we try to modify it slightly, or pick a completely new one. It also doesn't matter that we only showed numbers between zero and ten.

Suppose we had indeed paired off everything, so that every real had its , then I will show how to find a new real number, . The idea is that we will show that does not appear anywhere in the table, and hence will not be a bijection (if it were, then every possible real, including ones we cook up in fanciful ways, must be listed.) Then, we will have a contradiction, meaning that is not countable.

The contradiction follows from looking at the diagonal of the s. So, look at the first decimal digit of — above it is 0. If it's zero, then the first digit of will be one, and otherwise it will be zero. So for the above table, starts . Then, look at the second digit of . Do the same, so now starts . Continuing in this way, we get , and the th digit of is if the th digit of is , otherwise it is .

Now, if were indeed a bijection, as we want it to be, this must be listed on the table somewhere — every real number is. But it is quite obvious that does not appear, because it is different from at position 1, at position 2, and so on — it is different from at position !

And that is the contradiction. Any possible bijection — one-to-one pairing — of the natural numbers with the reals has this problem, so no such pairing can exist. Hence there really are more real numbers than there are natural numbers.

Now, some people will be entirely convinced by this while others might have objections. The first common objection says, "why couldn't we just add this new number to the list?" But remember, the argument above works with any possible listing, so just adding a number (or infinitely many!) to the list won't help; we can run the same procedure and find a missing number still.

The second common objection is that the notion of cardinality must somehow not be fit for purpose. After all, if it produces such weird results, why should we accept it as the mathematical notion of "size"? Well, first of all, even if we rejected cardinality as the correct definition of size, we'd still be left with the fact that we can't pair off the natural numbers with the reals, and if that's not because there are more reals than naturals, why is it? Second, it turns out that this concept is much more robust than any other notion of size when applied to infinite collections of things and so weird as it may be, cardinality is the best tool for the job!

I went to a conference last week. It wasn't the first conference I've been to, but in some ways it was the first "real" one since the actual first was before I started the PhD, and neither of the ones before this was strictly relevant to my topic.

This was the 5th Young Set Theory Workshop, held at the CIRM, a conference centre in Luminy, near Marseille in the south of France. Since I study set theory, this was definitely a good start.

The surroundings of Marseille are pretty spectacular --- slanted rock strata form impressive, somewhat barren mountains with sparse coverings of scrub. I watched these slide past on the bus from the airport, and again on the bus from the train station, in a slight daze having got up at 4:30 in the morning, with only coach- and plane-sleep to supplement. Nonetheless it was suitably impressive.

Arriving at the conference with old tutor Andrew (whom I'd met at the bus stop, handily settling the question of which side of the road the bus went from) I found old friends David and Greg --- we'd graduated together with PhDs in set theory lined up, so we knew it wasn't "goodbye" and sure enough we'd made it this far.

The days that followed were a pleasant mix of mathematics and socialising. I find it very easy to get on with academics; whether it's that our thinking patterns are similar, their outlooks or something that smacks less of pseudo-science, there seem always to be good humour and a similar curiosity. The latter especially so in such a context when there are many strangers from different cultures.

I was glad that I had learned the rudiments of Forcing, since the majority of talks and lectures touched on the subject in some way. At times I felt pretty behind --- which is to be expected, although it can be disheartening when there are apparently intelligent questions from the audience indicating they have a clue what's going on. However by the end it was clear that, at least among the early PhD students, I was predictably in good company (and in fact several of us opted out of some of the later talks)

Itay Neeman's lecture series was specifically on Proper Forcing --- a technique I hadn't even heard of, but were actually quite understandable. The reason for this is that he actually covered only the basics; this was described as

It was as if, in the first lecture, he showed this beautiful, pristine, vinyl record, just lifting it from the dust jacket. But then he spent the next three lectures building a record player, only playing a tiny snatch of it in the last few minutes and saying "oh, you can come and listen to it at my house!"

So he obviously was left wanting more of the advanced stuff!

Anyways there were also a few talks quite directly related to my work, which is pretty much a first. Likewise it's amazing to be able to talk about my research without simplifying everything; there's a broad spectrum from "lay person" through "general mathematician" to "pure mathematician", "set theorist" and finally "someone who understands what I'm talking about". Even within the conference most people don't understand all the background to a particular person's research.

The social aspect is of course not to be ignored. We all spent long evenings telling jokes and discussing the fine distinctions between British and American English (we call it a "table tennis bat", they call it a "ping pong paddle"!) drinking slightly overpriced French wine. There was also a vending machine that dispensed beer, which was a bit disturbing...

There was a Greek who knew about as much Monty Python as I do, a Canadian who taught us Magic: The Gathering, a Finn who was as serious as the stereotype and who told disturbing jokes and everyone else besides. In the discussion blocks one was free to find someone to talk maths with or chat about this and that. One afternoon we walked out over the hill down to the "calanque" or inlet to paddle in the Mediterranean. (There was also a more intrepid group which hiked up the mountain --- I was not feeling up for this, clearly the right decision in the end as I didn't have nearly enough water and got sunburnt on the shorter walk.) Here I caught up with Greg, who, it turns out, is in a similar situation to me; we both procrastinate too much but have proved one or two rather trivial results that nonetheless serve to boost ones confidence.

On other occasions I told someone who knew about Determinacy what I was doing, and he suggested some interesting things that might be useful in the future. Another time I looked at a generalisation of stationary sets with my supervisor's other student. One other time I told David and Greg how MOBA games like LoL and DotA work.

Before long it was time to return home. For the second time I brought my terrible French to bear to tell the staff that I didn't need lunch on Friday (the first was to check I was boarding the correct train; I was. In fact I was surprised by how much French I remembered, although I certainly forgot almost all of it) and was away at 11AM. 13 hours of travelling later and I was home by 11PM, UK time. Protip: Marseille terminal MP2 is a dive and a sandwich/drink combo costs €7 --- altogether an unpleasant place for your flight to be delayed an hour. Not that being stuck at passport control for nearly an hour at Stansted is much better, especially when you can't even see the passport desks.