When are the Real Numbers Necessary?

The natural numbers can all be finitely represented, as can the rational numbers. The real numbers, however, cannot be so represented and require some notion of “infinity” to define. This makes it both computationally and philosophically interesting to determine for what purposes you need the real numbers, and for what purposes you need only the rationals.

It’s pretty clear that spatial concepts having to do with distances and rotation require the real numbers. For example, if we took \mathbb{Q}^2 as our model of the plane, the distance from (0,0) to (1,1) would not be rational, and we would not be able to rotate the point (1,0) about the point (0,0) by most angles.

But I always implicitly thought that spatial notions not depending on distances or angles required only the rationals. It turns out that I was wrong: there are spatial notions not depending on distances or angles which differ depending on whether you take space to be \mathbb{Q}^n or \mathbb{R}^n. The fact that I was wrong follows from a theorem of Micha Perles which is very famous in combinatorics, but which I only found out about recently.

I found out because the combinatorialist Drew Armstrong told me about it, and he referred me to the online book Lectures on Discrete and Polyhedral Geometry by Igor Pak.

Actually, the fact that I was wrong follows just from a lemma in the proof of Perles’s result, which I will state before telling you what Perles’s main result was.

Consider the following system of points and lines (the image is stolen from Pak’s manuscript):

The lemma is then that while there is a collinearity- and noncollinearity-preserving embedding of this diagram into \mathbb{R}^2, there is not one into \mathbb{Q}^2. Note that the question of a collinearity- and noncollinearity-preserving embedding of the diagram says nothing about angles or distances. The proof is simply to assume that there is a rational embedding, then to find a rational transformation of the configuration to one where you know that one of the points has an irrational coordinate. This proof appears on page 108 of Pak’s book.

Perles’s main theorem is the following, and I think it’s quite striking: A polytope is the convex hull of a finite set of points in some \mathbb{R}^n, where we consider two polytopes equivalent if they are combinatorially equivalent: i.e., if there is a bijection between the two sets of vertices such that if one pair of vertices has an edge between them, the corresponding pair does as well, etc. Then for all dimensions n greater than 3, there is an n-dimensional polytope which is not equivalent to one which is the convex hull of a set of points with only rational coordinates.

The discussion of this in Pak’s book is in Part I, Section 12.5.

Edit: I removed a paragraph on planar graphs because it didn’t really fit the article, and I took out the phrase “purely combinatorial property,” which was misleading and probably incorrect.

About these ads

5 Comments

Filed under Uncategorized

5 responses to “When are the Real Numbers Necessary?

  1. That is a striking result!

    I was wondering if you could just clarify one small detail: is the convex hull in the phrase “convex hull of a set of points with only rational coordinates” a convex hull over the reals or rationals? That is, if x and y are two rational coordinates then ax + (1-a)y is in the convex hull. Are the coefficients a and b real or rational?

  2. Ah, good point. The convex hull is over the reals.

    To clean up the statement of the result a bit: A polytope is the convex hull (in the reals) of a finite set of points in \mathbb{R}^n. A polytope is called rational if it’s equivalent to one which is the convex hull (in the reals) of a finite set of points in \mathbb{Q}^n. The result is that there are polytopes which are not rational in dimensions greater than 3.

  3. anon

    I’m a little confused by what is covered by the “etc” in the definition of polytope equivalence. I think that two polytopes are equivalent if there is a bijection between their vertex sets that preserves adjacency, collinearity and noncollinearity. Is that all?

  4. Sorry it took me so long to respond. What you said is right, except the notion of polytope equivalence also extends to higher dimensions: i.e., the bijection must preserve whether or not their is a face bounded by edges between vertices, and a solid bounded by faces bounded by edges between vertices, and so on.

  5. none

    Eh? The whole point of the reals is that if two curves in the plane cross over each other when you draw them on paper, then they actually intersect at a point. That requires completeness, i.e. some form of the least upper bound property. If you’re just on the rationals, or just on the algbraic points, or something like that, the curves can pass “through” each other without intersecting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s