Paradoxical decompositions of sets usually require the axiom of choice; Hausdorff or Banach-Tarski are well-known examples. A paradoxical decomposition of a point set without the axiom of choice has been constructed by Sierpinski and Mazurkiewicz. A set $S$ is the union of two sets $A$ and $B$. When the elements of $A$ are rotated ($\rho$) by one radian, then $\rho$$A = S$, and when the elements of $B$ are translated ($\tau$) by one unit, then $\tau$$B = S$ too.

There is a simple variant. Decompose the set $\mathbb{Z}$ of all integers into $A$, the set of even integers, and $B$, the set of odd integers. When the elements of $A$ are divided $(\delta)$ by 2, then $\delta$$A = \mathbb{Z}$. When the elements of $B$ are translated by one unit (in positive or negative direction) and then divided by 2, then $\delta\tau$$B = \mathbb{Z}$.

Same can be shown for other sets $S$, for instance the set of positive integers (then $B$ must be translated by +1).

My question: Have these paradoxical decompositions already appeared in literature? I would like to include them into my lectures with appropriate quotation but could not yet find a source or an author.

  • 1
    $\begingroup$ See the "infinitely many guests" here: en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel . Of course this is well-documented. $\endgroup$ – YCor Jan 8 '16 at 9:39
  • $\begingroup$ Thank you. Of course I know Hilbert's hotel, but I miss the idea of a paradoxical decomposition of a set. $\endgroup$ – Rhett Butler Jan 8 '16 at 10:02
  • 1
    $\begingroup$ @RhettButler "did not hint" does not mean "did not use". $\endgroup$ – Anton Petrunin Jan 8 '16 at 11:15
  • 2
    $\begingroup$ In the Banach-Tarski paradox the AC is only used to translate (in the ordinary sense) the paradoxal decomposition of the free group on two elements (that does not require AC and is very explicit and very much like your decomposition of the integers) to a paradoxical decompostion of a space (a solid sphere in R^3 say) on which the group acts. The latter 'feels' more paradoxical because of the distance preserving property of the group action. Intuitively distance preserving maps should preserve measure. The decompostion of the group as an abstract object doesn't feel paradoxical at all. $\endgroup$ – Vincent Jan 8 '16 at 11:23
  • 4
    $\begingroup$ What I mean is: people would probably not talk a lot very explicitly about paradoxical decompostions of sets if there weren't examples of sets that intuitively cary some sense of size that should be preserved by the action, but (by the paradox) apparently isn't. The example of Hilbert's hotel is interesting in that respect. The fact that every integer is half of some even integer is not really interesting, until you reformulate it in terms of size: are there more integers than even integers, or just as many? Only now it becomes paradoxical. $\endgroup$ – Vincent Jan 8 '16 at 11:28

This is not a full answer, but the reference may be interesting nonetheless. Paradoxical decompositions of sets are discussed in the very beginning of Stan Wagon's book "The Banach-Tarski paradox", Cambridge University Press, 1985 (very recommendable, lots of paradoxes, nice for lectures). The following is a nice quote from the first paragraph of the first chapter:

In a famous example, Galileo observed that the set of positive integers can be put into a one-one correspondence with the set of square integers, even though the set of non-squares, and hence the set of all integers, seems more numerous than the squares.

Ok, this is slightly different from the Hilbert hotel situation, but the basic idea seems to appear as early as 1638. The more general statement (Wagon calls it "the modern version of Galileo's observation") appears as Theorem 1.4 of Wagon's book: a set $X$ is paradoxical with respect to the action of its permutation group if and only if it is infinite. Unfortunately, the exact history of this result is not discussed in Wagon's book (the name Tarski appears, though). The if direction requires the axiom of choice (but not for cardinals).

  • $\begingroup$ Thank you, I also read Stan Wagon's book which is certainly the standard source for this topic, in particular if the reader is not fluent in French. And I looked into a lot of other literature, but could not find the crucial idea $A\cup B$ = $\mathbb{Z}$ and simultaneously, after applying operators according to the idea of Sierpinski and Mazurkiewicz, $A' = \mathbb{Z}$ and $B' = \mathbb{Z}$. Therefore I asked here. But I will not yet give up. Perhaps there will be an expert on history here around who has come across the source on some old conference proceedings or lessons. $\endgroup$ – Rhett Butler Jan 9 '16 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.