Misplaced Pages

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (November 2013) (Learn how and when to remove this message)

The Ross–Littlewood paradox (also known as the balls and vase problem or the ping pong ball problem) is a hypothetical problem in abstract mathematics and logic designed to illustrate the paradoxical, or at least non-intuitive, nature of infinity. More specifically, like the Thomson's lamp paradox, the Ross–Littlewood paradox tries to illustrate the conceptual difficulties with the notion of a supertask, in which an infinite number of tasks are completed sequentially. The problem was originally described by mathematician John E. Littlewood in his 1953 book Littlewood's Miscellany, and was later expanded upon by Sheldon Ross in his 1988 book A First Course in Probability.

The problem starts with an empty vase and an infinite supply of balls. An infinite number of steps are then performed, such that at each step 10 balls are added to the vase and 1 ball removed from it. The question is then posed: How many balls are in the vase when the task is finished?

To complete an infinite number of steps, it is assumed that the vase is empty at one minute before noon, and that the following steps are performed:

• The first step is performed at 30 seconds before noon.
• The second step is performed at 15 seconds before noon.
• Each subsequent step is performed in half the time of the previous step, i.e., step n is performed at 2 minutes before noon.

This guarantees that a countably infinite number of steps is performed by noon. Since each subsequent step takes half as much time as the previous step, an infinite number of steps is performed by the time one minute has passed. The question is then: How many balls are in the vase at noon?

Solutions

Answers to the puzzle fall into several categories.

Vase contains infinitely many balls

The most intuitive answer seems to be that the vase contains an infinite number of balls by noon, since at every step along the way more balls are being added than removed. By definition, at each step, there will be a greater number of balls than at the previous step. There is no step, in fact, where the number of balls is decreased from the previous step. If the number of balls increases each time, then after infinite steps there will be an infinite number of balls.

Vase is empty

Suppose that the balls of the infinite supply of balls were numbered, and that at step 1 balls 1 through 10 are inserted into the vase, and ball number 1 is then removed. At step 2, balls 11 through 20 are inserted, and ball 2 is then removed. This means that by noon, every ball labeled n that is inserted into the vase is eventually removed in a subsequent step (namely, at step n). Hence, the vase is empty at noon. This is the solution favored by mathematicians Allis and Koetsier. It is the juxtaposition of this argument that the vase is empty at noon, together with the more intuitive answer that the vase should have infinitely many balls, that has warranted this problem to be named the Ross–Littlewood paradox.

Ross's probabilistic version of the problem extended the removal method to the case where whenever a ball is to be withdrawn that ball is uniformly randomly selected from among those present in the vase at that time. He showed in this case that the probability that any particular ball remained in the vase at noon was 0 and therefore, by using Boole's inequality and taking a countable sum over the balls, that the probability the vase would be empty at noon was 1.

Depends on the conditions

Indeed, the number of balls that one ends up with depends on the order in which the balls are removed from the vase. As stated previously, the balls can be added and removed in such a way that no balls will be left in the vase at noon. However, if ball number 10 were removed from the vase at step 1, ball number 20 at step 2, and so forth, then it is clear that there will be an infinite number of balls left in the vase at noon. In fact, depending on which ball is removed at the various steps, any chosen number of balls can be placed in the vase by noon, as the procedure below demonstrates. This is the solution favored by philosopher logician Tom Tymoczko and mathematician logician Jim Henle. This solution corresponds mathematically to taking the limit inferior of a sequence of sets.

The following procedure outlines exactly how to get a chosen n number of balls remaining in the vase.

Let n denote the desired final number of balls in the vase (n ≥ 0).
Let i denote the number of the operation currently taking place (i ≥ 1).

Procedure:

for i = 1 to infinity:

put balls numbered from (10*i - 9) to (10*i) into the vase

if i ≤ n then remove ball number 2*i

if i > n then remove ball number n + i

Clearly, the first n odd balls are not removed, while all balls greater than or equal to 2n are. Therefore, exactly n balls remain in the vase.

Problem is underspecified

Although the state of the balls and the vase is well-defined at every moment in time prior to noon, no conclusion can be made about any moment in time at or after noon. Thus, for all we know, at noon, the vase just magically disappears, or something else happens to it. But we don't know, as the problem statement says nothing about this. Hence, like the previous solution, this solution states that the problem is underspecified, but in a different way than the previous solution. This solution is favored by philosopher of mathematics Paul Benacerraf.

Problem is ill-formed

The problem is ill-posed. To be precise, according to the problem statement, an infinite number of operations will be performed before noon, and then asks about the state of affairs at noon. But, as in Zeno's paradoxes, if infinitely many operations have to take place (sequentially) before noon, then noon is a point in time that can never be reached. On the other hand, to ask how many balls will be left at noon is to assume that noon will be reached. Hence there is a contradiction implicit in the very statement of the problem, and this contradiction is the assumption that one can somehow 'complete' an infinite number of steps. This is the solution favored by mathematician and philosopher Jean Paul Van Bendegem.

See also

• Supertask
• Thomson's lamp
• Zeno's paradoxes
• Hilbert's paradox of the Grand Hotel

References

1. "Imperatives and Logic", Alf Ross, Theoria vol. 7, 1941, pp. 53-71
2. Sheldon Ross, A First Course in Probability (Eighth edition, Chapter 2, Example 6a, p.46)

Further reading

• "Littlewood's Miscellany" (ed. Béla Bollobás), Cambridge University Press, Cambridge, 1986. p. 26. (First published as "A Mathematician's Miscellany" (ed. Béla Bollobás, Methuen & Co., 1953)
• "Tasks, Super-Tasks, and Modern Eleatics", Paul Benacerraf, Journal of Philosophy, LIX, 1962, pp. 765–784
• "A First Course in Probability", Sheldon Ross, New York: Macmillan, 1976
• "On Some Paradoxes of the Infinite", Victor Allis and Teunis Koetsier, The British Journal for the Philosophy of Science, v.42 n.2, Jun 1991, pp. 187–194
• "Ross' Paradox Is an Impossible Super-Task", Jean Paul Van Bendegem, The British Journal for the Philosophy of Science, v.45 n.2, Jun 1994, pp. 743–748
• "Infinite Pains: The Trouble with Supertasks", Earman, J. and Norton, J.D., in S. Stich (ed.) Paul Benacerraf: The Philosopher and His Critics (New York: Blackwell), 1994
• "Sweet Reason: A Field Guide to Modern Logic", Tom Tymoczko and Jim Henle, Freeman Press, 1995

v t e Mathematical logic
General	Axiom list Cardinality First-order logic Formal proof Formal semantics Foundations of mathematics Information theory Lemma Logical consequence Model Theorem Theory Type theory
Theorems (list)  and paradoxes	Gödel's completeness and incompleteness theorems Tarski's undefinability Banach–Tarski paradox Cantor's theorem, paradox and diagonal argument Compactness Halting problem Lindström's Löwenheim–Skolem Russell's paradox
Logics	Traditional Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram Propositional Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞ Predicate First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus
Set theory	Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities Types of sets Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann Maps and cardinality Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary Set theories Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive
Formal systems (list), language and syntax	Alphabet Arity Automata Axiom schema Expression ground Extension by definition conservative Relation Formation rule Grammar Formula atomic closed ground open Free/bound variable Language Metalanguage Logical connective ¬ ∨ ∧ → ↔ = Predicate functional variable propositional variable Proof Quantifier ∃ ! ∀ rank Sentence atomic spectrum Signature String Substitution Symbol function logical/constant non-logical variable Term Theory list Example axiomatic systems (list) of arithmetic: Peano second-order elementary function primitive recursive Robinson Skolem of the real numbers Tarski's axiomatization of Boolean algebras canonical minimal axioms of geometry: Euclidean: Elements Hilbert's Tarski's non-Euclidean Principia Mathematica
Proof theory	Formal proof Natural deduction Logical consequence Rule of inference Sequent calculus Theorem Systems axiomatic deductive Hilbert list Complete theory Independence (from ZFC) Proof of impossibility Ordinal analysis Reverse mathematics Self-verifying theories
Model theory	Interpretation function of models Model equivalence finite saturated spectrum submodel Non-standard model of arithmetic Diagram elementary Categorical theory Model complete theory Satisfiability Semantics of logic Strength Theories of truth semantic Tarski's Kripke's T-schema Transfer principle Truth predicate Truth value Type Ultraproduct Validity
Computability theory	Church encoding Church–Turing thesis Computably enumerable Computable function Computable set Decision problem decidable undecidable P NP P versus NP problem Kolmogorov complexity Lambda calculus Primitive recursive function Recursion Recursive set Turing machine Type theory
Related	Abstract logic Algebraic logic Automated theorem proving Category theory Concrete/Abstract category Category of sets History of logic History of mathematical logic timeline Logicism Mathematical object Philosophy of mathematics Supertask
Mathematics portal

• Supertasks
• Paradoxes of infinity