Santa in the Continuum

This year’s festive offering considers countable and non-countable infinities and follows (very) loosely from last year’s discussion of deterministic and non-determininstic optimisation

[Specially for Alex Irvine, who is either having trouble getting his head around infinite sets or still believes in Santa Claus: we’re not allowed to say which]

Father Christmas has a problem. The Intergalactic Department of Work and Pensions (IDWP) has threatened to cut his tax credits because he apparently only works one day a year. He’s tried to point out that he’s the head of a vast multinational organisation of elves and reindeer, who themselves work all year round, but that doesn’t wash with the IDWP boss, Ian ‘Dunkin’ Smiff, because his dad didn’t go to public school.

So, he’s been given extra work to do: a lot of extra work to do …

In his ‘days off’, Santa’s been told by the IDWP that, to keep his tax credits, he has to deliver presents to children on other planets as well. This proposition was met with a certain level of complacency from Santa and his Head Elf, Boz, until it was pointed out to them that there might be an infinite number of them.

• Santa: “Are there really an infinite number of inhabited planets out there?”
• Boz: “Well, sort of quasi-infinite really.”
• Santa: What’s quasi-infinite?”
• Boz: “Depends on who’s updated Wikipedia last.”
• Santa: “Ah!”

Santa consulted his top reindeer, Rudolph, who, as we know, is magic.

• Santa: “Rudolph, me old mate … “
• Rudolph: “Uh oh!”
• Santa: “How’s the new stable complex?”
• Rudolph: “What do you want, fat boy?”
• Santa: “Well, Rudolph, me old chum …”
• Rudolph: “Yes?”
• Santa: “Well, you know you can do non-deterministic polynomial?”
• Rudolph: “Yes; well, my nose can.”
• Santa: “Which, for non-magical people, is, sort of, like exponential?” (See The Travelling Santa Problem for a discussion of this)
• Rudolph: “Yes.”
• Santa: “Well, er … Can you do infinite?”
• Rudolph: “What?”
• Santa: “I said, can you do infinite?”
• Rudolph: “Are you taking the #@&$?”
• Santa: “No, seriously, we’ve just been told we have to deliver to an infinite number of planets. Can you do infinite?”
• Rudolph: “No.”

There was a slight pause, during which Father Christmas looked pretty crestfallen, before Rudolph continued …

• Rudolph: “… But my hyper-magic cousin can!”
• Santa: “You’ve got a cousin?
• Rudolph: “Yes, a Russian one.”
• Santa: “Where does he live?”
• Rudolph: “Now wait, let me see, ah yes, I remember, Russia. Doh!”
• Santa: “What’s he called?”
• Rudolph: “Nureyev.”
• Santa: “Are you taking the #@&$?”
• Rudolph: “No, seriously.”
• Santa: “You’ve got a Russian cousin, called Nureyev, who can do infinite?”
• Rudolph: “Yes.”

Santa brightened considerably, until Rudolph added as an afterthought …

• Rudolph: “At least, I think he can.”
• Santa: “What do you mean, you think he can?”
• Rudolph: “Well, I get a bit confused by the infinite stuff. I’m OK with non-determinism but I get lost on the infinite. I know he can do something like that.”

Father Christmas turned to Boz, who just shrugged his shoulders. The three of them, now utterly confused, decided to send for Nureyev to see if he could help. A messenger elf, Phiz,  was dispatched to St. Petersburg that very evening.

Three minutes later, a pure-white reindeer, wearing Cossack boots and a big red star on his nose, landed on the North Pole runway.

• Rudolph: “See, I said he was quick!”
• Nureyev: “Greetings, comrade. I understand you need my assistance?”
• Rudolph: “Hey, Cuz! How you doing?”
• Boz: “But the messenger’s only just left! He hasn’t got to St. Petersburg yet. How come you’re already here?”
• Nureyev: “The less you know about quantum space travel the better, comrade!”

Father Christmas needed a sherry. They all went in to the lodge. Father Christmas explained the problem …

• Santa: “Ian ‘Dunkin’ Smiff, from the IDWP, has decided we need to deliver to other planets; otherwise they’ll cut our tax credits.”
• Boz: “Problem is, we think there’s an infinite number of them.”
• Nureyev: “What sort of infinite?”
• All: “WHAT?”
• Nureyev: “What sort of infinite? It depends. I can do countable infinite but not non-countable infinite.”
• All: “WHAT?”
• Nureyev: “Can you set up a bijection mapping the natural numbers to the planets we have to visit?”
• All: “WHAT?”
• Nureyev: “Show me the ^%$@£” spec., comrade …”

Father Christmas searched out the letter from the IDWP and handed it to Boz, who scanned it for the essential detail …

• Boz: “It says we have to visit all these planets. We can do it in any order we like but we have to visit them all. They haven’t given us names, just intergalactic coordinates and they’ve numbered them P₁, P₂, P₃, … etc, infinitely.”
• Nureyev: “PERFECT!”
• Boz: “Why perfect?”
• Nureyev: “Because that numbering means it’s countable. It may be infinite but it’s countable. I can do that.”
• Boz: “How can you count them? There are an infinite number of them!”
• Nureyev: “I don’t mean I can count them; I mean I can count through them.”
• Boz: “Eh?”
• Nureyev: “If you give me any planet, I can count up to it. I’ll get there eventually, in the end. That’s countable. I can do that. Rudolph’s got his non-determinism thing; this is mine.”
• Santa: “So, we can do this then, guys? Nureyev, you can visit an infinite number of planets as long as it’s countable?”
• Nureyev: “Yes, the mapping is just 1-P₁, 2- P₂, 3- P₃, … etc. so my visiting algorithm is essentially the same. We visit each one in order.”
• Rudolph (feeling a little left out): “Yes, and I can solve the TSP for each of the planets as we visit them in turn.”

They all had another sherry to celebrate.

Sure enough, when they tried it out, it worked like a dream. Nureyev visited each of the countably infinite planets in 1-P₁, 2- P₂, 3- P₃, … order, Rudolph solved each planet’s TSP non-deterministically and Father Christmas delivered the presents. It looked like his tax credits were saved.

However, about a week later, there was another problem …

One afternoon, Rudolph and Boz were in the stable, playing ‘Chase the Holly’ for sherry oats, when Father Christmas rushed in, waving a letter, looking not a little put out …

• Rudolph: “Whaaasup, Bro?” (He’d won most of the hands so far)
• Santa: “it’s another letter from that @*&%$£ Ian ‘Dunkin’ Smiff.”
• Boz: “What does it say?”
• Santa: “It’s another ^&%$£@ list of planets! We’ve got to visit these as well.”

Boz took the letter and examined it carefully, then sighed …

• Boz: “Yes, it’s a new list. The IDWP has discovered a load more planets; infinitely more apparently. Very much like before except they’ve numbered these Q₁, Q₂, Q₃, … etc.”
• Rudolph: “Is that instead of the P₁, P₂, P₃, … list or as well as?”
• Boz: “As well as, unfortunately.”
• Rudolph: “In that case, we’re knackered then. Cousin Nureyev can do countable but I don’t think he can do two lots of countable: double countable!”

They went to break the bad news to Nureyev. They found him giving a group of young does rides on his troika. He glanced at the letter, including the new Q₁, Q₂, Q₃, … list and drawled casually …

• Nureyev: “No bother.” (he’d lost his Russian formality pretty quickly)

The others were taken aback …

• Boz: “But these planets have to be done as well as the other ones!”
• Nureyev: “No bother: still countable.”
• Rudolph: “How can it still be countable? You can count up to any planet in the first list but you’ll never finish it. So, you’ll never start the second, surely?
• Nureyev: “I’ll just change the mapping … and visit them in a different order.”

Father Christmas was rapidly losing the plot …

• Santa: “What order?”
• Nureyev: “I’ll start with the 1s, then the 2s, then the 3s, and so on. My bijection will be 1-P₁, 2-Q₁, 3-P₂, 4-Q₂, 5-P₃, 6-Q₃, … etc. instead.”
• Boz: “You can do that?”
• Nureyev: “Course I can. I can do what I like. My algorithm will just switch between the two lists. It’ll still work. You give me any planet in either list and I’ll still get there … eventually.”

It was agreed that more sherry was in order.

And it did indeed work. Now, Nureyev visited each of the countably infinite planets in 1-P₁, 2-Q₁, 3-P₂, 4-Q₂, 5-P₃, 6-Q₃, … order, Rudolph solved each planet’s TSP non-deterministically, as before, and Father Christmas still delivered all the presents.  Twice countable was still countable, it appeared.

But it didn’t stop there …

The IDWP kept discovering more planets …

And the lists kept coming …

But they coped! Nureyev’s strategy of visiting all of the first planets in each list, then the second planets, and so on, still worked. When, for example, they had five lists, P₁, P₂, P₃, …, Q₁, Q₂, Q₃, …, R₁, R₂, R₃, …, S₁, S₂, S₃, … and T₁, T₂, T₃, …, the visiting algorithm was 1-P₁, 2-Q₁, 3-R₁, 4-S₁, 5-T₁, 6-P₂, 7-Q₂, 8-R₂, 9-S₂, 10-T₂, 11-P₃, 12-Q₃, 13-R₃, 14-S₃, 15-T₃, …. The new lists kept coming but Nureyev kept changing the mapping and the delivery algorithm. Rudolph (and his non-deterministic nose) sorted the TSPs and Father Christmas did the rest. Any finite number of countables was still countable.  They got through the year.

It was the evening on Christmas Day.  Father Christmas, Boz, Nureyev and Rudolph were all sitting around the table in the little parlour, drinking sherry. Rudolph was explaining the benefits of the free-market economy to Nureyev …

• Nureyev: “So, instead of just giving the reindeer the oats they need, you make them compete for them?”
• Rudolph: “Yes, that’s right; except it never really works out like that. The winners always tend to get much more than they need so they just save them up for their children. Then they get the others to do the competing for them and it all gets a bit buggered. But, heh-ho, whatcha gonna do?”
• Nureyev: “Well …”

They were interrupted by Father Christmas …

• Santa: “Good work, guys; thanks for everything. It’s been a tough year. Old ‘Dunkin’ had me worried for a while there but we pulled through. I’m proud of you all!”
• Rudolph: “No problem, boss.”
• Nureyev: “Delighted to have been of service!”

But Boz was still looking thoughtful …

• Boz: “So, have we really got this sorted, now?”
• Santa: “Seems that way, to me.”
• Rudolph: “Yes, because it doesn’t matter how many new lists the IDWP throw at us, Nureyev just remaps the algorithm. We do all the 1s, then the 2s, then the 3s, and so on … We’ve cracked it!”
• Nureyev: “Er, not quite!”
• Santa (looking worried again): “What do you mean?”
• Nureyev: “Well, if they were to give us an infinite number of lists, we’d be in trouble. If there was an infinite (even a countably infinite) number of lists, then there’d be an infinite number of 1s, an infinite number of 2s, an infinite number of 3s, and so on … My mapping wouldn’t work. I couldn’t even get through the 1s to start on the 2s. There’d be no counting algorithm. We’d be done for. I can manage a finite number of countable infinities because that’s still countable. But an infinite number of countable infinities isn’t countable. It’s a different infinity – a non-countable one – a bigger one.”
• Rudolph: “I guess we’d need our hyper-hyper-magic Italian cousin, Valentino, for that then?”
• Nureyev: “Don’t talk to me about that show-off. I still haven’t forgiven him for that time he told me the ’15 inch Sicilian’ was a pizza! ‘Sure, says I; I can take that all in one go, says I … ‘ ”

Boz broke in again …

• Boz: “I don’t think that worries me too much. Even the IDWP couldn’t discover an infinite number of infinite lists of planets. I think we’re pretty safe on that one. But is there an easier way they could mess us around?”
• Santa: “Like what?”
• Boz: “Well, find us something to do that wasn’t countable but wasn’t as extreme as the infinite infinities thing?”
• Rudolph: “You mean, find something in between the countables and the non-countable infinite infinities?”
• Boz: “Yes, something like that. If the countables and infinite infinities non-countables are sort of next to each other in the sequence of infinities then we’re OK; but, if they’re not, then we might be in trouble.”
• Nureyev: “Search me!”
• Rudolph: “And me!”

Father Christmas smiled a knowing smile and refilled his glass …

• Santa: “I think you’ll find that’s called the Continuum Hypothesis. I believe it’s an undecidable problem. It doesn’t have a ‘yes’ or ‘no’ answer. It’s independent of conventional set theory. They say Gödel the Great was working on that when he went mad.
• Rudolph: “Why?”
• Santa: Well, years of working with undecidable problems got to him eventually. He couldn’t make any decision at all in the end. You see the Continuum Hypothesis can be either true or false, as you want it to be. It doesn’t matter which and it doesn’t affect the rest of mathematics. Poor old Gödel lost it big time when he realised that. He went to pieces; started doing things at random because nothing seemed to matter either way. Then other people found out and no-one trusted him to make a decision at all.  It didn’t matter what decision he took in the end because no-one believed him anyway.
• Rudolph: “What happened to him?”
• Santa: “He became Intergalactic Prime Minister!”

Merry Christmas!