Von Neumann paradox
Encyclopedia
In mathematics, the von Neumann paradox, named after John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
, 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
Special affine group
In the mathematical study of transformation groups, the special affine group is the group of affine transformations of a fixed affine space which preserve volume...
such that the result is two planar figures of the same size as the original. This was proved in 1929 by John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
, assuming the axiom of choice. It followed on the work of Stefan Banach
Stefan Banach
Stefan Banach was a Polish mathematician who worked in interwar Poland and in Soviet Ukraine. He is generally considered to have been one of the 20th century's most important and influential mathematicians....
and Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
, who proved a similar paradox in three dimensional space (the Banach–Tarski paradox
Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set theoretic geometry which states the following: Given a solid ball in 3-dimensional space, there exists a decomposition of the ball into a finite number of non-overlapping pieces , which can then be put back together in a different way to yield two...
), but using only isometric transformations (Euclidean motions).
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
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
of transformations which include as a subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
a free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...
with two generators
Generating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
. The group of area preserving transformations (whether the special linear group or the special affine group
Special affine group
In the mathematical study of transformation groups, the special affine group is the group of affine transformations of a fixed affine space which preserve volume...
) 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 groupFree group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...
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
for some n, where the 
's and 
's are all non-zero integers, except possiblly 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 (let's call this set A) and those that start with τ to some power (that is, 
is zero—let's 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
Cardinality of the continuum
In set theory, the cardinality of the continuum is the cardinality or “size” of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by |\mathbb R| or \mathfrak c ....
. According to 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 let us 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
. 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 
and translate them so that the centre of the 
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 σ τ. Note that 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)!
We have glossed over some things, like how to handle fixed points. It turns out that we have to use 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."
- "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
Banach measure
In mathematics, Banach measure in measure theory may mean a real-valued function on the algebra of all sets , by means of which a rigid, finitely additive area can be defined for every set, even when a set does not have a true geometric area. That is, this is a theoretical definition getting round...
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 set
Dense set
In topology and related areas of mathematics, a subset A of a topological space X is called dense if any point x in X belongs to A or is a limit point of A...
s 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 group
Amenable group
In mathematics, an amenable group is a locally compact topological group G carrying a kind of averaging operation on bounded functions that is invariant under translation by group elements...
s, or groups with an invariant mean, and include all finite and all solvable group
Solvable group
In mathematics, more specifically in the field of group theory, a solvable group is a group that can be constructed from abelian groups using extensions...
s. 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 LaczkovichMiklós Laczkovich
Miklós Laczkovich is a Hungarian mathematician mainly noted for his work on real analysis and geometric measure theory. His most famous result is the solution of Tarski's circle-squaring problem in 1989.- Career :...
proved that such a decomposition exists. 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.