Von Neumann paradox

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

In mathematics, the von Neumann paradox, named after John von Neumann, is the idea that one can break a planar figure such as the unit square into sets of points and subject each set to an area-preserving affine transformation such that the result is two planar figures of the same size as the original. This was proved in 1929 by John von Neumann, assuming the axiom of choice. It is based on the earlier Banach–Tarski paradox, which is in turn based on the Hausdorff paradox.

Banach and Tarski had proved that, using isometric transformations, the result of taking apart and reassembling a two-dimensional figure would necessarily have the same area as the original. This would make creating two unit squares out of one impossible. But von Neumann realized that the trick of such so-called paradoxical decompositions was the use of a group of transformations that include as a subgroup a free group with two generators. The group of area-preserving transformations (whether the special linear group or the special affine group) contains such subgroups, and this opens the possibility of performing paradoxical decompositions using them.

Sketch of the method

The following is an informal description of the method found by von Neumann. Assume that we have a free group H of area-preserving linear transformations generated by two transformations, σ and τ, which are not far from the identity element. Being a free group means that all the its elements can be expressed uniquely in the form \sigma^{u_1}\tau^{v_1}\sigma^{u_2}\tau^{v_2} \cdots \sigma^{u_n}\tau^{v_n} for some n, where the us and vs are all non-zero integers, except possibly the first u and the last v. We can divide this group into two parts: those that start on the left with σ to some non-zero power (we call this set A) and those that start with τ to some power (that is, u_1 is zero—we call this set B, and it includes the identity).

If we operate on any point in Euclidean 2-space by the various elements of H we get what is called the orbit of that point. All the points in the plane can thus be classed into orbits, of which there are an infinite number with the cardinality of the continuum. Using the axiom of choice, we can choose one point from each orbit and call the set of these points M. We exclude the origin, which is a fixed point in H. If we then operate on M by all the elements of H, we generate each point of the plane (except the origin) exactly once. If we operate on M by all the elements of A or of B, we get two disjoint sets whose union is all points but the origin.

Now we take some figure such as the unit square or the unit disk. We then choose another figure totally inside it, such as a smaller square, centred at the origin. We can cover the big figure with several copies of the small figure, albeit with some points covered by two or more copies. We can then assign each point of the big figure to one of the copies of the small figure. Let us call the sets corresponding to each copy C_1, C_2, \dots, C_m. We shall now make a one-to-one mapping of each point in the big figure to a point in its interior, using only area-preserving transformations. We take the points belonging to C_1 and translate them so that the centre of the C_1 square is at the origin. We then take those points in it which are in the set A defined above and operate on them by the area-preserving operation σ τ. This puts them into set B. We then take the points belonging to B and operate on them with σ2. They will now still be in B, but the set of these points will be disjoint from the previous set. We proceed in this manner, using σ3τ on the A points from C2 (after centring it) and σ4 on its B points, and so on. In this way, we have mapped all points from the big figure (except some fixed points) in a one-to-one manner to B type points not too far from the centre, and within the big figure. We can then make a second mapping to A type points.

At this point we can apply the method of the Cantor-Bernstein-Schroeder theorem. This theorem tells us that if we have an injection from set D to set E (such as from the big figure to the A type points in it), and an injection from E to D (such as the identity mapping from the A type points in the figure to themselves), then there is a one-to-one correspondence between D and E. In other words, having a mapping from the big figure to a subset of the A points in it, we can make a mapping (a bijection) from the big figure to all the A points in it. (In some regions points are mapped to themselves, in others they are mapped using the mapping described in the previous paragraph.) Likewise we can make a mapping from the big figure to all the B points in it. So looking at this the other way round, we can separate the figure into its A and B points, and then map each of these back into the whole figure (that is, containing both kinds of points)!

This sketch glosses over some things, such as how to handle fixed points. It turns out that it is necessary more mappings and more sets to work around this.

Consequences

The paradox for the square can be strengthened as follows:

Any two bounded subsets of the Euclidean plane with non-empty interiors are equidecomposable with respect to the area-preserving affine maps.

This has consequences concerning the problem of measure. As von Neumann notes,

"Infolgedessen gibt es bereits in der Ebene kein nichtnegatives additives Maß (wo das Einheitsquadrat das Maß 1 hat), dass [sic] gegenüber allen Abbildungen von A2 invariant wäre."[1]
"In accordance with this, already in the plane there is no nonnegative additive measure (for which the unit square has a measure of 1), which is invariant with respect to all transformations belonging to A2 [the group of area-preserving affine transformations]."

To explain this a bit more, the question of whether a finitely additive measure exists, that is preserved under certain transformations, depends on what transformations are allowed. The Banach measure of sets in the plane, which is preserved by translations and rotations, is not preserved by non-isometric transformations even when they do preserve the area of polygons. As explained above, the points of the plane (other than the origin) can be divided into two dense sets which we may call A and B. If the A points of a given polygon are transformed by a certain area-preserving transformation and the B points by another, both sets can become subsets of the B points in two new polygons. The new polygons have the same area as the old polygon, but the two transformed sets cannot have the same measure as before (since they contain only part of the B points), and therefore there is no measure that "works".

The class of groups isolated by von Neumann in the course of study of Banach–Tarski phenomenon turned out to be very important for many areas of mathematics: these are amenable groups, or groups with an invariant mean, and include all finite and all solvable groups. Generally speaking, paradoxical decompositions arise when the group used for equivalences in the definition of equidecomposability is not amenable.

Recent progress

Von Neumann's paper left open the possibility of a paradoxical decomposition of the interior of the unit square with respect to the linear group SL(2,R) (Wagon, Question 7.4). In 2000, Miklós Laczkovich proved that such a decomposition exists.[2] More precisely, let A be the family of all bounded subsets of the plane with non-empty interior and at a positive distance from the origin, and B the family of all planar sets with the property that a union of finitely many translates under some elements of SL(2,R) contains a punctured neighbourhood of the origin. Then all sets in the family A are SL(2,R)-equidecomposable, and likewise for the sets in B. It follows that both families consist of paradoxical sets.

References

  1. On p. 85 of: Lua error in package.lua at line 80: module 'strict' not found.
  2. Lua error in package.lua at line 80: module 'strict' not found.