thinking

In this post I’m going to prove that there cannot exist a good notation system for talking about sizes of infinity.

It’s fun to think about big numbers.  And by big numbers, I mean different sizes of infinity.

You can define different sizes of infinity in many ways – there are the cardinal numbers, the more specific ordinal numbers, and then the even more specific (and my personal favorite), surreal numbers.  There are also the hyperreals, but those are not as cool as the surreals.

When you start talking about sizes of infinity, you have your first size of infinity – let’s call it omega – and you get numbers like omega + 1, 2 * omega, omega squared, and so forth.  In the surreals, you can even talk about crazy-sounding things like x = the square root of omega, and this number really does exist (in the surreals), and has nice properties like x * x = omega (we would be offended otherwise!).  The important thing is, I’m not just making up nonsense about some vague idea of sizes of infinity.  These are well-defined mathematical constructs that very smart people have thought about, and nodded sagely in solemn agreement.  For the sake of using something specific, when I say “size of infinity,” or “infinite number,” I’ll mean an infinite ordinal number.

So far so good.  Now for the fun stuff.

A little while ago, I sat down with pencil and paper, and decided to invent a system of notation that would capture the notion of how big different sizes of infinity are.  Having some basic math background I was already aware of Impossible Fact #1:

Impossible Fact #1: No system of notation can express every size of infinity.

Let me be more precise.  By a “system of notation” I mean a way that we can turn a human-writeable string into a fixed ordinal number.  The input string must be from a fixed-size alphabet, since otherwise humans couldn’t practically learn it.  You could suggest analog parameters, such as “the length of this line I just drew,” but then you would be assuming we have infinite-precision measuring capacity, which we don’t.  So a system of notation is any definable function from strings of a fixed alphabet into ordinal numbers.  This is an extraordinarily general definition, and probably includes any practical system any human will ever come up with.

But the first thing to notice (as a mathematician), is that the set of possible outputs from this system of notation is necessarily countable.  And there are an uncountable number of sizes of infinity.  This was one of the first big surprises when set theory was being born – a fact that can be seen in Georg Cantor’s diagonal argument.  So right away, there will be some specific size of infinity that is impossible to write down.  And I don’t mean impossible like some number with a billion kazillion digits is “impossible;” I mean literally, logically impossible.  As in, if you wrote down every number you could possibly write down, you would still be missing a number.

This will not suprise any mathematicians who are reading this, because it is a well-known idea in the math-world.  However, the next fact is something I had to think about a little before understanding.

We know we have to give up on being able to write down every size of infinity – ok.  So let’s compromise.  How about we come up with a system of notation where, for any infinite number x, we can write down some number y with x < y.  That’s a pretty big compromise.  We’re giving up on being able to write down an infinite, arbitrarily-large portion of all numbers.  But, no, infinity has no mercy.

Impossible Fact #2: Any one system of notation will have all its numbers < most numbers.

In other words, no matter what system of notation you invent, there will always be an infinite number y so that x < y for every single number x in the notation.  In fact, it’s even worse than that.  If you take the union of all numbers less than any number in the notation, the set you arrive at will still be smaller (as a set) than the numbers remaining.  In other words, even in this compromised setting, we still are forced to miss so many numbers that our “captured” set looks infinitely small in comparison.

This last point is not completely obvious to see, although the proof from the ZFC axioms (the most commonly-used axioms of set theory) is easy to understand.  Because ZFC works easily with ordinals, I’ll give the proof for ordinals as the sizes of infinity, but surreals are easy to understand as an order-preserving superset of ordinals, so the proof carries over to the surreals as well.

We think of the notation system as a definable function F(x) where x is a natural number (N = natural numbers), and F(x) is an ordinal.

1. By the axiom schema of replacement, there is a set A = {F(x) | x in N}.

Each ordinal number is itself a set, so every element a in A is a set.  Every ordinal o can be defined as the set of all smaller ordinals o = {p : p < o}.  So the union of A is the union of all elements smaller than any number F(x) that we can write in the notation.  We’ll call this union B.

2. By the axiom of union, B = union(A), given by b in B iff b in a for some a in A, is also a set.

Let’s call the rest of the ordinals R.  All ordinals O taken together form a proper class — essentially, they are too big to be considered a set.  (We get paradoxes if we do – see Russell’s paradox.)  As a class, we have R = O – B.

3. B is a set, O is not, so R cannot also be a set.

4. If there were a injective function f:R -> B, then we could use the axiom scheme of replacement (via f inverse) to show that R is a set.  This would be a contradiction, so there is no such f, meaning that R can be thought of as having more elements than B.

We could informally write card(R) > card(B), but some might object since usually we only allow taking card(x) when x is a set.  But we can safely say that R is infinitely larger than B.

QED

In fact, we’ve proven something even stronger than Impossible Fact #2, because even if we pretend that the input for our notation function F(x) is any ordinal, the same proof works to show that we still miss most infinite numbers R.  So, for example, if we allow any real number as an input into our notation, it would still fail.

Alas, there is no system of notation that does what we want.  But at least we know to stop looking.

Final score

Humanity: epsilon (for knowing to give up)

Infinity: omega

This post explains solutions for the pizza puzzle. If you haven’t read that puzzle yet, you should try it first!

There are multiple ways to solve this one. For these solutions, we’ll treat the radius of the pizza as length 1. Even if it had a different radius, we could scale all the work in a solution accordingly, and the end result would be the same, since it’s a percentage of the total area.

First, let’s draw another hexagon inside the pizza, with vertices at the center of each pepperoni circle.

The bold hexagon is the one we already see on the pizza; the dashed hexagon is drawn with vertices on the center of each pepperoni circle.  We’ve also drawn new circles at the corner of each vertex of the bold hexagon. Since each triangle in the large hexagon is equilateral, and two of its sides are radii of the pizza circle, each edge of the bold hexagon has length 1. Each outside circle (the new circles) have radius half that, which means they each have area A = π r² = π/4 (that should read “pi over 4,” in case the “pi” isn’t showing up correctly for you). The total area of the outside circles is thus six times that, which is 3π/2.

Notice that the large bold hexagon and its circles are similar to the small dashed hexagon and its circles (the pepperoni circles). If we can find the ratio of areas between the large hexagon and the small hexagon, this will also tell us the ratio of areas between the outer circles and the inner circles. This is a general rule of geometry; as another example of this rule, see the next figure. Whenever shapes are resized together, the scale factor of their areas is the same for each shape – either all are doubled, or all are halved, etc.

If area(big M-shape) = 2×area(little M-shape), then area(big circle) = 2×area(little circle).

Let’s take a closer look at one of the equilateral triangles in the big hexagon, from the first figure. The bold and dashed lines here show how this is a close-up on the bold and dashed hexagons.

There are six copies of the wavy triangle in the large equilateral triangle, and two copies of it in the smaller equilateral triangle (lower-right).  So the area of the smaller equilateral triangle is exactly 1/3rd the area of the larger. This means the area of the pepperoni circles is also a third of the area of the outer circles. Hence the pepperoni area is exactly (1/3) · (3π/2) = π/2, which means they take up half the area of pizza!

I personally enjoy this first solution because it involves no knowledge of trigonometry. However, there is another way to find the answer that looks more explicitly at the angles involved. In the next figure, we see the same wavy triangle from the last drawing.

We could find an equation between r and R through either the Pythagorean theorem, or using the fact that

r/R = sin(π/6) = 1/2.

The altitude of the large equilateral triangle is sin(π/3) = √3 /2 = r+R = 3r, so r = √3/ 6. Notice that r is the radius of a pepperoni circle, so the area of each pepperoni is π/12. The area of six pepperoni circles is then π/2, confirming it’s half the area of the pizza.

A mathematical pizzeria sells pizzas with six slices, each slice containing a maximally-sized equilateral triangle, as shown in the figure. Their pepperoni pizza features one maximally-sized circle of pepperoni per slice. What fraction of the area is taken up by the pepperoni circles?

This article caught my eye today:

http://www.newsweek.com/2010/08/05/the-limits-of-reason.html

It’s interesting for a number of reasons.  First, the content itself is kind of cool – why are humans irrational?  It’s a good question.  Second, they mention specific examples – including some actual logic analysis – of things people get wrong, and maybe why they get it wrong.  Finally, and perhaps most importantly, it’s interesting for what it doesn’t do.  It doesn’t do a good job of analyzing how the conclusion was reached.

1. Why are humans irrational?

This is a great question, because it is a major contradiction in our day-to-day lives that has a huge impact on how we live and our success as individuals and societies.  And looking at it from the evolutionary perspective is insightful, because it strikes at the core of the contradiction — if our reasoning is flawed, wouldn’t it follow that our faulty conclusions would diminish our survival?

For these reasons, I feel the work being discussed is very relevant and worthwhile.  It is a great question, and a good context within which to ask that question.

The article claims (or rather, cites other work which claims) that we tend to make reasoning mistakes which can help us win arguments.

I’m not sure I really agree with this conclusion.  The main problem is: Wouldn’t it just be better for humans if we were swayed by more logically-correct arguments?

In other words, the article’s conclusion seems to simply defer the contradiction of bad human reasoning to a new problem of bad human argument-listening.  This is still a huge, looming problem that hasn’t even been attempted here.

Here’s another approach we could take to tackling this problem: categorize the types of mistakes humans most often make (I think this has already been worked on), and then look for situations in which the mechanism behind the “faulty” reasoning is actually helpful.  This method – finding good properties of evolved traits – makes much more sense to me.

If you want to understand why something evolved, you must understand how it helps survival.

2. Logic analysis

As a mathematician, I can’t avoid commenting on the logic analysis of the article.  Specifically, the article says:

Consider the syllogism “No C are B; all B are A; therefore some A are not C.” Is it true? Fewer than 10 percent of us figure out that it is, says [Hugo] Mercier.

Actually, this line of reasoning is not generally correct.  To be more precise, if any B exist, it is correct, but if no B exist, then the conclusion may or may not be correct.  If you know what a Venn diagram is, then that’s probably the simplest way to visualize the problem:

The first statement omits anything from being in C ∩ B.  The second omits anything in B outside of A.  The result is the Venn diagram on the right.  Clearly, anything in B must be in A but not C, which would verify the conclusion.  The possible mistake is that B and A outside of C could be empty!

Let me illustrate with an example.  Fermat’s Last Theorem states that there is no integer solution to the equation x^n + y^n = z^n with x,y,z,n > 0 and n > 2.

Let’s plug in some values to the above argument.

Let A = (quadruples (x,y,z,n) of positive integers with n > 2).

Let B = (quadruples (x,y,z,n) of positive integers with n > 2 and x^n + y^n = z^n).

Let C = (quadruples (x,y,z,n) of positive integers with n > 2 and x^n + y^n ≠ z^n).

We can apply the above argument:

First, No C are B.  Yes, that’s true.

Second, all B are A.  Yes, that’s also obviously true.

Therefore, some A are not C.  But anything in A and not C is a counterexample to Fermat’s Last Theorem!  According to the article, I’ve just proven the theorem false.  But of couse I haven’t.  I’ve just pointed out that this line of reasoning can fail.  So the 90% of humans who “fail” to confirm the syllogism aren’t so stupid, after all.

3. The missing analysis

I’m about to criticize this article, but I want to preface the criticism by saying that I’m glad the article exists.  There is a gaping hole in journalism around science.  We need more science journalism because we need a culture that celebrates research and progress.

The best kind of scientific journalism is both appreciative and critical at once – this article is not critical enough.  It doesn’t sufficiently explore the key question of any good investigation: why do the researchers think the new claim is true?  Sadly, this is the norm in mainstream so-called scientific journalism.  The articles are so caught up in trying to decipher the complexities of the new ideas that they forget to ask why we need the complexities in the first place.  Why don’t the simpler answers suffice?

It is a bit ironic that an article decrying the carelessness of human reasoning fails to reason carefully.

This is the solution for the pirate-catching puzzle I posted a few days ago.

Here’s the general idea:

It’s helpful to put things into a coordinate system where the starting position of the pirate ship is (0,0), and the government ship is at (3,0).  This works because we know they start 3 km apart, so any two points at distance 3 are fine as starting points.  In the picture above, the blue line is the path of the pursuing government ship, and the red line is one possible straight line the pirates could take.

The strategy is in two parts:

1. Start by travelling straight toward the pirate ship for 2 km.  If, by luck, the pirates are headed directly toward the government ship, they’ll meet at this point, since the pirates will have travelled 1 km in the same time (1 minute).
2. After that, go in an expanding spiral around the origin.  Think in polar coordinates.  You know the pirates are going directly away from (0,0) at constant speed 1 km/min, so their distance r from the origin is the same as the time t that has passed since the start.  Your ship (the government one) just needs to keep at the same radius as the pirate ship, while sweeping its angle around in a circle.  The government ship has to meet the pirate ship by the time it completes 360 degrees.

This strategy is possible because the government ship is going faster than the pirates.  That gives us a general idea of how to solve the puzzle – but it’s still a little vague.  We still don’t know the exact spiral to take, or how long it will take at most to catch them.

That’s where the real fun starts.  Let’s find the spiral’s equation, using as the coordinates of the government ship at time (where is the instant they spotted the pirates and went for them).

We have two constraints:

• , and
• speed .

We also know that the angle and radius are increasing over time.  To put this all together, we can use this equation for the speed of the government ship as a derivative of time:

Where did that equation come from?  Well, it’s basically the derivative (with respect to t) of arc length in polar coordinates.  We know , so

We also know that and therefore , so

Almost got it!  Using that again, we see that , so solve for to get

That’s the path of the government ship, which looks like this:

How long does it take to traverse?  The highest the angle can get is arbitrarily close to 360 degrees.  Our equations use radians (for example, the speed equation assumes is in radians), so we can just plug in for to find out the answer to our puzzle.  The longest time is exactly

minutes.

As a mathematician, I think this is a great answer to such a simple-to-state problem!

This weekend I heard a good mathy puzzle from George Miller.  Here’s a version I found online, attributed to Howard Lederer:

You’re on a government ship, looking for a pirate ship.  You know that the pirate ship travels at a constant speed, and you know what that speed is.  Your ship can travel twice as fast as the pirate ship.  Moreover, you know that the pirate ship travels along a straight line, but you don’t know what that line is.  It’s very foggy, so foggy that you see nothing.  But then!  All of a sudden, and for just an instant, the fog clears enough to let you determine the exact position of the pirate ship.  Then, the fog closes in again and you remain (forever) in the thick fog.  Although you were able to determine the position of the pirate ship during that fog-free moment, you were not able to determine its direction.  How will you navigate your government ship so that you will capture the pirate ship?

If you wanted, you could give a convincing but math-lite answer to this.  But you can also do better, so I’m going to ask my own version of the question:

Using your answer to the above question, what is the longest amount of time that may pass from the instant you saw the pirate ship until you capture it?  Suppose the pirate ship travels at 1 km/minute, and you first see it 3 km away.  How many minutes, at most, until you capture it?

I’ll post my answer on Friday (in 5 days).

The curve described by a simple molecule of air or vapor is regulated in a manner just as certain as the planetary orbits; the only difference between them is that which comes from our ignorance.

Probability is relative, in part to this ignorance, in part to our knowledge.

The phrase the scientific method implies that there is some universal, automated process that investigators blindly follow in order to do science. In truth, there is a great deal of improvisation and creativity required for the doing of good science. Great leaps forward, such as general relativity or the complex (as in complex numbers) proof of the prime number theorem, often rely on bold, inspired insights into the nature of an unsolved problem.

However, there are a few common principles that unite the rational attitudes of modern research. I want to highlight a few that I feel are somewhat neglected. They are:

• experimental candor,
• easily reproducible experiments, and
• induced correlation.

Experimental candor

Here’s a nice way to get great results: suppose you think that drug A will help people lose weight. Conduct a thousand studies on small groups of test subjects. Suppose one of those studies shows good results – publish those good results, and throw away the rest of the results.

This may sound a bit unrealistic, but something like this can happen much more easily in computer science. In this case, there is a growing field of algorithms which are both probabilistic and approximate – very similar to experimental drugs in medicine. If they do pretty well most of the time, that’s good enough. Yet with an algorithm, it’s incredibly easy to run a million trials of your code, and only publish the best subset of that. Even if the quality of your results are completely random, it’s just a matter of time before one small subset of the test results look good.

Hence the need for experimental candor. It’s important to reveal all the relevant experiments performed, including the negative or inconclusive ones. The web is the perfect platform for this kind of data disclosure – you can pre-publish your intended experiments and hypotheses before you actually run the experiments. This way, good results look better, and other researchers won’t waste time on previously failed experiments. Of course, it’s always possible that an experiment failed for unaccounted-for parameters (including human error), which is why experimental reproducibility is also crucial to good research.

Easily reproducible experiments

This scientific tenet is well agreed upon, but poorly executed. In practice, I know of very few experiments which can be very easily reproduced at the research level. In some cases, one may wish to build upon the work of another, such as by augmenting a biochemical procedure with a new step. Articles involving experimental lab work do indeed contain careful procedural explanations meant just for this purpose, which is great. But in many cases, even this is not enough for other researchers – in my days as a grad student, I would see other grad students emailing or calling other investigators (often ones who were considered serious competitors) to ask for critical clarifications in procedure.

We can do better than that.

I’m going to pick on computer scientists for a moment, because they’re the worst offenders. An algorithmic experiment has the most potential to be easily reproducible. Ironically, it seems typical to leave out necessary parameters to perform the experiments used in many papers. In order to reproduce a certain graph of time complexity versus input size on a certain real-world dataset, for example, a reader will often have to code up the algorithm based on very vague pseudocode and hand-wavy explanations, guess at parameter values, and separately download the dataset. I’ve even seen code used which was nowhere available in either pseudocode or executable code – the reference given was by personal communication with another researcher (who won’t answer my emails).

There is no excuse for this. Any good algorithmic experiment can be reproducible at the click of a button. The experimenters have already written the code – it is simply a matter of adding a link to this code to a website. It would be friendly to add a little documentation; or better yet, to follow a pattern of operation for the field, in much the same way that some software installation procedures have become standardized.

Induced correlation

This point is a call for the conscious recognition of an idea that’s been implicitly used for some time.

Certain experiments have the goal of looking for something like a causal relationship. If a drug company is testing a weight-loss drug, they want to know that their drug causes the weight loss, as opposed to it causing something else, or something else causing the weight loss.

Unfortunately, there’s no fool-proof way to experimentally test causality. This is a well-known problem. It’s also interesting to note that, philosophically, causality itself is subjective in nature, although that is the matter of another post.

Here’s the trouble: Let’s hypothesize that chemical X causes weight gain. As an experiment, get a large group of people together. We randomly select some folks as the control – they won’t change their diets, and we randomly select some others to change their diet to no longer consume chemical X. We see the desired results: the control group gains a little weight on average, but the experimental group (no chemical X) actually loses some.

Does that mean anyone can prevent weight gain by avoiding chemical X? Absolutely not. Here is one possible explanation: Suppose that the vast majority of foods contain both chemicals X and Y together, or not at all. So when the experimental group avoided X, they were also avoiding Y without knowing it. Now you unleash your study on the world, and everyone starts avoiding X. But there are some foods with chemical Y in it, without X. It could happen that those foods become more popular, or that certain people subconsciously crave Y. In either case, we have people consuming Y, not X, and gaining weight.

Is there anything we can do to experimentally show something stronger than mere correlation? A little bit, yes – we can show induced correlation. This is a correlation between parameters which was observed specifically by either turning on or off the cause in each trial, and purposefully leaving all other known parameters the same. Let’s use the term natural correlation to indicate experiments where the cause was either present or absent without any control by the experimenters. Induced correlation gives more evidence of causality than natural correlation since there is more evidence that we can control the effect by controlling the cause.

I think this general idea has been understood already, but I’m not sure that it has been explicitly recognized. My goal throughout this post has been to encourage the codification and emulation of a few good core principles of scientific investigation. There are definitely more key principles, although I’ve been reminded many times that at least these three could use a little more awareness and observation.