*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*etc, infinitely.”_{1}, P_{2}, P_{3}, … - 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*etc. so my visiting algorithm is essentially the same. We visit each one in order.”_{1}, 2- P_{2}, 3- P_{3}, … - 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 _{1}, 2- P_{2}, 3- P_{3}, …* 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*etc.”_{1}, Q_{2}, Q_{3}, … - Rudolph: “Is that
*instead of*the*P*list or_{1}, P_{2}, P_{3}, …*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 _{1}, Q_{2}, Q_{3}, …* 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*etc. instead.”_{1}, 2-Q_{1}, 3-P_{2}, 4-Q_{2}, 5-P_{3}, 6-Q_{3}, … - 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 _{1}, 2-Q_{1}, 3-P_{2}, 4-Q_{2}, 5-P_{3}, 6-Q_{3}, …* 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 _{1}, P_{2}, P_{3}, …, Q_{1}, Q_{2}, Q_{3}, …, R_{1}, R_{2}, R_{3}, …, S_{1}, S_{2}, S_{3}, …* and

*T*, the visiting algorithm was

_{1}, T_{2}, T_{3}, …*1-P*. 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

_{1}, 2-Q_{1}, 3-R_{1}, 4-S_{1}, 5-T_{1}, 6-P_{2}, 7-Q_{2}, 8-R_{2}, 9-S_{2}, 10-T_{2}, 11-P_{3}, 12-Q_{3}, 13-R_{3}, 14-S_{3}, 15-T_{3}, …*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!*

February 2nd, 2016 at 7:12 pm

[…] take another example, which we’ve looked at recently in a more festive context […]

December 1st, 2016 at 10:08 am

[…] Then the following year, 2015, Father Christmas was given a whole load more (in fact, an infinite number of) planets to deliver to and he needed the help of Rudolf’s ‘countable’ Russian cousin, Nureyev, in Santa in the Continuum. […]