## Thursday, February 12, 2015

### Six things that cannot be listed - #4 is totally non-trivial!

There are many lists of things out there right now. But not everything can be listed. Here is a list of some things that can not be listed. In a particular order:

### The real numbers

You might think it's easy to list the real numbers. Start at 0, and then you have 0.1, 0.2, 0.3... But wait, between 0 and 0.1 you have 0.01, 0.02 and so on. And between 0 and 0.01 you have 0.001, 0.002... In fact, it is impossible to get anywhere at all, because there is always a finer-grained way of listing the numbers. Unlike the natural numbers (positive integers), which you can simply list as 1, 2, 3... Georg Cantor proved that this was the case. And that's why the real numbers are in a sense more infinite than the natural numbers.

Cantpr later tried to prove that nothing could at the same time be more infinite than the natural numbers and less infinite than the real numbers. He couldn't, so he went crazy and ended up in a mental asylum.

### The list of all lists that do not contain themselves

Sure, there are many lists that do not contain themselves. Your laundry list is presumably one of those, even if you write the list on a piece of paper you forget in your jeans (you'd only be washing the paper, not the list). An example of a list that does contain itself is the list of all lists of lists. And of course the list of all lists also contains itself. But the question is whether the list of all lists that do not contain themselves should list itself or not. Because if it does, it shouldn't, and if it doesn't, it should. Bertrand Russell spent a number of years puzzling over this so you don't have to.

This was important, because lists of lists are necessary in order to show that mathematics are true. Having thus destroyed attempts at founding mathematics on logic, Russell went on to be imprisoned for pacifism.
 Thinking about infinity might make you want to hide.

### All the animals

Jorge Luis Borges provided the following list of animals, in a fictional text about a text:
• Those that belong to the emperor
• Embalmed ones
• Those that are trained
• Suckling pigs
• Mermaids (or Sirens)
• Fabulous ones
• Stray dogs
• Those that are included in this classification
• Those that tremble as if they were mad
• Innumerable ones
• Those drawn with a very fine camel hair brush
• Et cetera
• Those that have just broken the flower vase
• Those that, at a distance, resemble flies
It's clear that this is not getting us anywhere and we should stop now.

Borges later lost his eyesight, but apparently never his virginity.

 There are some pretty weird animals out there.

### All statements that are true in a formal system of sufficient power

Kurt Gödel thought a lot about truth. In particular, about which statements were true and which were not. To find out which statements were true, he invented a way to list all the statements in a system. Even more impressively, using this list he could figure out whether the statement was true just by looking at the number of it. Because the statements could be about anything within the system, there must be a statement in the list which talks about whether this statement itself is true - a statement that contains the proof of itself. As with all other statements, the number of this statement says whether it is true or false. Gödel showed that this statement is false. This means that is is impossible to list all true statements in a formal system, or all false statements for that matter. Rather disheartening really if you want to believe that the truth is in there.

Gödel, always a somewhat troubled fellow, later starved himself to death.

### All steps you take as you follow a coastline

 Following the coastline of Britain in larger and smaller steps. Sorry, no animals. Image from Wikipedia.
Benoit Mandelbrot wrote a paper with the amazing title "How Long Is the Coast of Britain?". You might think that this should have been a very short paper. I mean, it's something like 12000 kilometers or so. But actually the question is complicated. There's another figure you can find online which is something like 19000 kilometers. How can they be so different? You see, you can only measure length in straight lines, and a coast is never completely straight (neither are most things in the natural world). In order a measure a coastline, you need to approximate it with a series of straight lines. Think of when you want to measure the length of a path by a walking it: you simply count the steps you take. Perhaps surprisingly, the length you measure depends on how long steps you take. You see, with smaller steps you can follow the path more closely and take more turns, and you will arrive at a higher number. The same goes for coastlines. If you want to measure the coast of Britain, you can do this in different ways. For example, you can choose to measure it by fitting straight lines of 10 kilometers to it and get one number. Or by fitting straight lines of 1 kilometer and get a much higher number. If you fit lines of a hundred meters you get an even higher number... and so on. At some point you will be measuring around individual grains of sand, and Brighton beach itself will probably be hundreds of kilometers long. In fact, you can't list the number of steps you would need to take, for the same reason you can't list the real numbers: there's always a smaller step possible.

Mandelbrot escaped the nazis and went on to live a long (how long?) and apparently happy life.

(Note to self: should illustrate this text with pictures of puppies, kittens and/or smiling people. That way, people might actually read it. Or at least click on it.)