Doing the impossible (but not really) with infinitary processes and the axiom of choice

7 June 2013

One of the interesting things about mathematics is that it allows us to reason about objects (like fractals, dimensionless points or infinite sequences) and processes (limits, the axiom of choice) that, while logically sound and often even intuitive, cannot actually exist or be feasibly carried out in real life. This is arguably one of the main reasons for a common popular view of pure mathematics as being “too theoretical”, aka. of no practical use. Admittedly this ability of what is known as “classical” mathematics to talk about infinities, infinitesimals and ambiguous choices has given rise to some strange results, like the notorious Banach–Tarski paradox, which informally says that a 3-dimensional ball can be divided into finitely many pieces and reassembled into two balls each identical to the original, or the Riemann rearrangement theorem, which states that a conditionally convergent real infinite series can be rearranged to converge to any real number whatsoever, or to .

Effective or not?

Both these theorems are statements about our ability to accomplish certain actions, and the proof of each consists of a description of a procedure to do so. So are these surprising results actually practicable in real life? The latter is; we can obtain an algorithm that, given a conditionally convergent series, rearranges its terms to either diverge or converge to a specified real number [BB09]. The former is not, as it relies on the axiom of choice to select points from an infinite number of sets, and while we can infer non-trivial things about the resulting set, there is no way for finite, mortal mathematicians to actually construct it. So while both theorems are statements of the logical possibility of accomplishing a certain seemingly impossible task, only the rearrangement of the infinite series to converge to any sum is “physically” possible; the feasibility of cutting an orange into five pieces and putting them back together to get two oranges remains firmly in the realm of logic, out of the material world.

This illustrates a subtle but important distinction between the procedures described in the respective proofs. We say that there is an effective procedure for the series rearrangement problem: for any conditionally convergent series the procedure always terminates in a finite number of steps and returns the desired result, a permutation of the terms of the series which sums to a given number, or diverges. This is characteristic of what we call effective procedures in general: a series of instructions guaranteed to end in a finite number of steps, always returning a correct result. The procedure for decomposing a 3-ball into a finite number of pieces and reassembling them into two identical 3-balls is a non-effective process; since an infinite number of selections must be made in order to obtain those pieces in the first place, we can never hope to actually get our hands on any of the pieces, much less reassemble them!

Guessing numbers in a random real sequence

I would like to discuss another example of a non-effective procedure which “enables” us to accomplish an impossible feat. Consider the following

Problem. A house has a hundred rooms. In each room are an infinite number of boxes labelled with the natural numbers , each containing an arbitrary real number. The rooms are identical, so that in each room the -th box always contains the same number. We kidnap a hundred mathematicians and into each room send one, where they are allowed to open up boxes to reveal the numbers inside. They may open as many boxes as they like (possibly infinitely many) as long as at least one box is left unopened. Each mathematician’s task is to guess the number inside a particular unopened box of their choice. They know that the rooms are identical, and once they have been sent into the rooms no further communication is allowed. Before they are sent to the rooms they are given a chance to discuss a strategy.

Find a strategy that will enable at least 99 of the 100 mathematicians to correctly guess their real number.

This puzzle appears impossible. There is no relation between the real numbers inside the boxes, so there is no reason to think that opening up any of the other boxes will give any clue as to what is contained inside any particular box. Furthermore the numbers form a countable subset of the (uncountable) reals, hence the probability of any mathematician randomly guessing the number inside any box is zero. However we can “theoretically” do much better than randomly guessing, as the following solution shows.

Solution. The boxes in each room form an infinite sequence of real numbers. Partition this sequence into 100 subsequences and assign one to each mathematician. (For simplicity’s sake we number the mathematicians from to and let the -th mathematician’s sequence be made up of the boxes congruent to modulo .) Also, define an equivalence relation on the set of all real sequences where two sequences are equivalent if they differ in a finite number of places. This relation partitions the set of real sequences into equivalence classes, choose a representative sequence from each class.

Having agreed on each one’s sequence and the representatives for each equivalence class, the mathematicians enter the rooms. In each room, mathematician opens up every box except those belonging to his sequence, to reveal each of the other mathematicians’ sequences. For each , let be the greatest index in which the -th mathematician’s sequence differs from the representative of the equivalence class it belongs to. If the sequence equals its representative, then .

Mathematician now lets

,

and guesses what is inside the -th box of his own sequence according to the following procedure.

He opens up every box of his own sequence, starting from the -th box. Since he knows all but finitely many terms in his sequence he is able to determine the equivalence class to which it belongs, and hence the representative of this class. The -th term of the representative is his guess for the number contained inside the -th box of his sequence.

If all the mathematicians follow this strategy, at most one of them will guess incorrectly: for consider the multiset of indices . If this set contains only one instance of its maximum, then the mathematician whose  may guess incorrectly. Any other mathematician must guess correctly since

1. is the last place where his sequence differs from its representative,
2. , and
3. he knows ,

which implies that the -th term of his sequence agrees with the -th term of its representative.

If multiple mathematicians have then everyone will guess correctly.

Observe that following this strategy gives any particular mathematician in the group a (not less than) probability of correctly guessing the number inside his chosen box. But there is nothing special about the number 100, we can use this strategy for any number of mathematicians by simply dividing the boxes up into more subsequences, and there will always be at most one who may possibly guess incorrectly. In this way we can increase the probability that a given mathematician in the group guesses correctly to arbitrarily close to one—a pretty big improvement from just randomly guessing!

Unfortunately as you may have guessed, this strategy is non-effective and so not actually feasible in real life. The problem begins right from the set up, where there is once again the necessary use of the axiom of choice to choose an arbitrary representative from each of the infinitely many equivalence classes. But it goes even deeper than that—the very construction of the equivalence classes in the first place is non-effective. For to determine if two arbitrary sequences are equivalent, we must compare each of their infinitely many terms to see if only finitely many are non-equal. We can think of this comparison of the sequences and  as a function , where

is then an instance of an infinitary operation, a function that takes infinitely many input values (in this case, the individual terms of the sequences being compared) in order to output a result (true or false, depending on whether the sequences are equivalent or not), and this is again non-effective. This situation occurs again inside each room, when each mathematician has to find the representative that corresponds to each of the other mathematicians’ sequences. In the language of logic and computability theory, we say that the problem of determining the equivalence of two arbitrary infinite sequences is undecidable, i.e. there is no effective method for doing so. This is what causes the above solution, clever as it is, to remain—just like the Banach–Tarski paradox—possible in principle but untenable in practice.

References

[BB09] Josef Berger and Douglas Bridges. Rearranging Series Constructively. Journal of Universal Computer Science, 15(17):3160–3168, 2009. ^{(Back to text)}

Advertisement

Written by Josh Chen Posted in Mathematics, Puzzles Tagged with axiom of choice, impossible problem, non-effective procedure, puzzle, sequences, undecidable problem