thinking

((Click here for a pdf of the paper.))

This is a math post to serve as an introduction to the paper linked above.

Many sets of numbers, like the integers, the rationals, or the reals, can be totally ordered, which means there is a binary relation < that satisfies these properties:

1. For any two elements a, b, exactly one of these is true: a < b, a = b, or a > b.
2. If a < b and b < c, then a < c.

To give a less obvious example, think of complex numbers a+bi. Normally we don’t think of them as being totally ordered, but we can say a+bi < c+di iff (a < c or a=c and b < d). Another example that everybody knows, but maybe hasn't thought of as a "total order," is alphabetical order, which tells you exactly how to sort any list of words, even if they're words you've never seen before (as long as you know the alphabet, and the order of that alphabet).

The set of rational numbers Q has an interesting property. Given any other countable set X with a total order on X, it’s possible to embed X into Q. In other words, there is a function f:X→Q such that f is 1-1 and x < y ⇒ f(x) < f(y). To show why this is an interesting property, try to find a function f:Q→Z which does the same thing, where Z is the set of all integers.

Well, don’t try too hard, because it turns out that’s impossible. I’ll explain why. Suppose, for the sake of contradiction, that you have a 1-1 function f:Q→Z with x < y ⇒ f(x) < f(y). Then f(0) and f(1) must be integers. But there are infinitely many rational numbers in the interval (0,1), while there can only be finitely many numbers between f(0) and f(1), so such a function can’t exist.

The point is that, there’s something special about Q that really captures the full complexity of countable total orders. Georg Cantor had a name for the key property: he suggested we say an order is everywhere dense if it has the property that, for any x < y, there is another element z with x < z < y. In other words, between every two elements is another.

The question I’m exploring in the paper is this: Is there an analogue of Q, and of this “everywhere dense” property, for higher cardinalities? Using the axiom of choice, and the generalized continuum hypothesis, the answer is definitely yes, and the proofs are explained in the paper.

To give a preview of how to extend Q to higher cardinalities: Let S₁ denote the set of binary strings indexed by any countable ordinal number, ordered lexicographically with the proviso that, if s is a binary prefix of t, then t < s when the first bit after s is 0; otherwise t > s. It’s easy to see how to embed the real [0,1] interval into S₁ using binary notation, and we can also embed all of R into [0,1] by using any order-preserving bounded function, such as arctan(x)/(π/2). But the other direction is impossible: for example, the first uncountable ordinal, ω₁, is part of S₁, as the set of all 1-only strings, indexed by all the countable ordinals. However, ω₁ can’t be embedded in R. If ω₁ fit in R, then it could be embedded in [0,1]; let x_i denote the distance between f(x_i) and f(x_i+1), and we end up with an uncountable set of positive reals whose sum is finite. To show this last feat is impossible, there must exist an n such that the number of elements x_i > 1/n is uncountable; but then clearly the sum cannot be finite.

By the way, the name “surreal” comes in because the canonical orders are key subsets of the class of surreal numbers.

Here are the solutions for the crazy cut puzzles I posted last week.  Did you solve them all?

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 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.