The Continuum Hypothesis Solved: All Infinities are the Same? Nope.

Of all of the work in the history of mathematics, nothing seems to attract so much controversy, or even outright hatred as Cantor’s diagonalization. The idea of comparing the sizes of different infinities – and worse, of actually concluding that there are different infinities, where some infinities are larger than others – drives some people absolutely crazy. As a result, countless people bothered by this have tried to come up with all sorts of arguments about why Cantor was wrong, and there’s only one infinity.

Today’s post is another example of that. This one is sort of special. Unless I’m very much mistaken, the author of this sent me his argument by email last year, and I actually exchanged several messages with him, before he concluded, roughly “We’ll just have to agree to disagree.” (I didn’t keep the email, so I’m not certain, but it’s exactly the same argument, and the authors name is vaguely familiar. If I’m wrong, I apologize.)

Anyway, this author actually went ahead and wrote the argument up as a full technical paper, and submitted it to arXiv, where you can download it in all it’s glory. I’ll be honest, and admit that I’m a little bit impressed by this. The proof is still completely wrong, and the arguments that surround it range from wrong to, well, not even wrong. But at least the author has the Chutzpah to treat his work seriously, and submit it to a place where it can actually be reviewed, instead of ranting about conspiracies.

For those who aren’t familiar with the work of Cantor, you can read my article on it here. A short summary is that Cantor invented set theory, and then used it to study the construction of finite and infinite sets, and their relationships with numbers. One of the very surprising conclusions was that you can compare the size of infinite sets: two sets have the same size if there’s a way to create a one-to-one mapping between their members. An infinite set A is larger than another infinite set B if every possible mapping from members of B to members of A will exclude at least one member of A. Using that idea, Cantor showed that if you try to create a mapping from the integers to the real numbers, for any possible mapping, you can generate a real number that isn’t included in that mapping – and therefore, the set of reals is larger than the set of integers, even though both are infinite.

This really bothers people, including our intrepid author. In his introduction, he gives his motivation:

Cantor’s theory mentioned in fact that there were several dimensions for infinity. This, however, is questionable. Infinity can be thought as an absolute concept and there should not exist several dimensions for the infinite.

Philosophically, the idea of multiple infinities is uncomfortable. Our intuitive notion of infinity is of an absolute, transcendent concept, and the idea of being able to differentiate – or worse, to be able to compare the sizes of different infinities seems wrong.

Of course, what seems wrong isn’t necessarily wrong. It seems wrong that the mass of something can change depending on how fast it’s moving. It seems even more wrong that looked at from different viewpoints, the same object can have different masses. But that doesn’t change the fact that it’s true. Reality – and even worse, abstract mathematics – isn’t constrained by what makes us comfortable.

Back to the paper. In the very next sentence, he goes completely off the rails.

Continue reading The Continuum Hypothesis Solved: All Infinities are the Same? Nope.

Ropes: Twining Together Strings for Editors

It’s been a while since I’ve written about any data structures. But it just so happens that I’m actually really working on implementing a really interesting and broadly useful data structure now, called a Rope.

A bit of background, to lead in. I’ve got this love-hate relationship with some of the development tools that Rob Pike has built. (Rob is one of the Unix guys from Bell labs, and was one of the principal people involved in both the Plan9 and Inferno operating systems.) Rob has implemented some amazing development tools. The two that fascinate me were called Sam and Acme. The best and worst features of both are a sort of extreme elegant minimalism. There’s no bloat in Rob’s tools, no eye-candy, no redundancy. They’re built to do a job, and do it well – but not to do any more than their intended job. (This can be contrasted against Emacs, which is a text editor that’s grown into a virtual operating system.) The positive side of this is that they’re incredibly effective, and they demonstrate just how simple a programmers text editor should be. I’ve never used another tool that is more effective than Acme or Sam. In all seriousness, I can do more of my work more easily in Sam than I can in Emacs (which is my everyday editor). But on the other hand, that extreme minimalist aesthetic has the effect of strictly eliminating any overlaps: there’s one way to do things, and if you don’t like it, tough. In the case of Acme and Sam, that meant that you used the mouse for damn-near everything. You couldn’t even use the up and down arrows to move the cursor!

This is a non-starter for me. As I’ve mentioned once or twice, I’ve got terrible RSI in my wrists. I can’t use the mouse that much. I like to keep my hands on my keyboard. I don’t mind using the mouse when it’s appropriate, but moving my hand from the keyboard to the mouse every time I want to move the cursor?. No. No damned way. Just writing this much of this post, I would have had to go back and forth between the keyboard and mouse over 50 times. (I was counting, but gave up when I it 50.) A full day of that, and I’d be in serious pain.

I recently got reminded of Acme, because my new project at work involves using a programming language developed by Rob Pike. And Acme would really be incredibly useful for my new project. But I can’t use it. So I decided to bite the bullet, and use my free time to put together an Acme-like tool. (Most of the pieces that you need for a prototype of a tool like that are available as open-source components, so it’s just a matter of assembling them. Still a very non-trivial task, but a possible one.)

Which finally, leads us back to today’s data structure. The fundamental piece of a text editor is the data structure that you use to represent the text that you’re editing. For simplicity, I’m going to use Emacs terminology, and refer to the editable contents of a file as a Buffer.

How do you represent a buffer?

As usual with data structures, you start by asking: What do I need it to do? What performance characteristics are important?

In the case of a text buffer, you can get by with a fairly small set of basic operations:

  • Fast concatenation: concatenating blocks of text needs to be really fast.
  • Fast insert: given a point in a block of text, you need to be able to quickly insert text at that point.
  • Fast delete: given two points in a block of text, you need to be able to quickly remove the text between those points.
  • Reasonably fast traversal: Lots of algorithms, ranging from printing out the text to searching it are based on linear traversals of the contents. This doesn’t have to be incredibly fast – it is an intrinsically linear process, and it’s usually done in the context of something with a non-trivial cost (I/O, regular-expression scanning). But you can’t afford to make it expensive.
  • Size: you need to be able to store effectively unlimited amounts of text, without significant performance degradation in the operations described above.

Continue reading Ropes: Twining Together Strings for Editors

Lottery Probabilities and Clueless Reporters

A simple, silly, but entertaining example of mathematical illiteracy by way of the Associated Press:

OMAHA, Neb. (AP) — The odds are against something this odd. But a Nebraska Lottery official says there was no mistake: The same three numbers in Nebraska’s Pick 3 lottery were drawn two nights in a row this week.

Lottery spokesman Brian Rockey said one of two lottery computers that randomly generate numbers produced the numbers 1, 9 and 6 — in that order — for Monday night’s Pick 3 drawing. Rockey says the next night, the lottery’s other computer produced the same three numbers in the same sequence.

The odds of such an occurrence? One in a million.

Close… Only off by three orders of magnitude…

Continue reading Lottery Probabilities and Clueless Reporters

Can 20 People Stand on a Wing? Can a Conspiracy Theorist Be Stupid?

I’m sure you’ve all heard about the airplane that ditched in the Hudson last week. (Just 30 blocks from my office!) When it happened, after we found out more about what caused the plane to ditch, I wondered how long it would take before the 911 Truthers came up with a conspiracy theory about it.

Not long. Via SkepticBlog comes news of a conspiracy theorist claiming that the ditching doesn’t make any sense. Brian Dunning at SkepticBlog does a good
job explaining what’s so stupid about this, but there were two things about
it that I thought were particularly interesting from the point of view of a math and computer science geek.

Continue reading Can 20 People Stand on a Wing? Can a Conspiracy Theorist Be Stupid?

Apples vs Orchards: Comparing Inauguration Costs

People keep sending me links to this, so I’ll make a short post about it.

In the hubbub surrounding the Obama inauguration, there’ve been all sorts of incredulous press pieces discussing the supposed outrageousness of the costs of this inauguration compared to others. I’ve personally heard this reported on the BBC world service, CNN, Fox, and MSNBC. In these
reports, the cost of the Obama inauguration is generally reported as
between 150 and 160 million dollars. When they provide a contrast, they talk about how Bush’s second inauguration cost $40 million.

The problem is, this is a metric error. They’re comparing apples to orchards.

When they cite the Bush inauguration cost as $40 million, they’re talking
about the cost of the inauguration parties – that is, the cost of the festivities themselves. That cost does not include security. It does
not include the cost of paying police to shut down the city streets. It doesn’t include the cost of cleaning up after the crowds. It’s just
the cost of the parties.

The Obama figure of $150-$160 million includes everything – police, security, setup, and cleanup.

A fair comparison? If you exclude the security costs, Bush’s second
inauguration cost $42 million; Obama’s is expected to cost around $45 million. If you include the security costs, Bush’s second inauguration
cost somewhere around $155 million. (The exact figures are still not public
knowledge; Bush and company treated it as a “national security matter” which
did not need to be disclosed.)

Yet another fake controversy brought to you by the supposedly liberal-biased media.

Excuse the brief interruption…

Just a brief note, to let you all know why there’s a lack of new posts.

Once again, I managed to kill my laptop. The machine died suddenly, with no warning. I’m currently waiting for a replacement, and once I get it, I’ll need some time to set everything up to my liking. I also had three posts in progress on the machine; I’m not sure whether they were backed up or not, and won’t be able to find out until I get a new machine.

Things will be back to normal as soon as possible, but don’t expect much for the next couple of days.

Blaming Bush: This time, it wasn't his fault.

And now for a short gripe from the other side of the political spectrum.

Normally, I like Media Matters. I personally think that the whole “left-wing media” thing
is a crock. The media has become so sensitive to the accusation of left-wing bias that they actually shy away from even dreaming of criticizing a conservative, and attack liberals with great fervor as a way of showing that they’re not being unfairly nice to them. In general,
I find Media Matters does a good job of showing how the modern press really works.

But the fact is, they are a biased organization, and you need to be very careful
to look at the details of what they write. Just like right-wing media-watch organizations,
they do look for interpretations of facts that support their bias, even if it requires
significant abuse of those facts to make the interpretation fit.

This morning, they provided an excellent demonstration of that. President Bush gave his final press conference this morning. The people at the conference showed a lot of deference to him, and let him get away with a lot. But one thing that Media Matters focused on
touches on math, and it’s bad.

Continue reading Blaming Bush: This time, it wasn't his fault.