# Infinite processes riddle

A train with infinitely many seats, one for each rational number, stops in countably many villages, one for each positive integer, in increasing order, and then finally arrives at the city. At the first village, two women board the train. At the second village, one woman leaves the train to go visit her cousin, and two other women board the train. At the third village, one woman leaves the train to go visit her cousin, and two other women board the train. At the fourth village, and in fact at every later village, the same thing keeps happening: one woman off to visit her cousin, two new women on board the train. How many women arrive at the city?

-
The answer seems to depend on whether the last stop has women getting on or off the train (ie, infinite being even or odd) which doesn't seem to be a question we can answer. Can someone clarify this at all? – Cam Aug 29 '10 at 5:36
@Cam: there is no last stop (before the city). – Qiaochu Yuan Aug 29 '10 at 6:13
Bonus question: Suppose each woman has a hat, and when she gets off the train she swaps it with a woman getting on. How many hats reach the city? Who's wearing them? – Oscar Cunningham Aug 29 '10 at 9:04
– Larry Wang Aug 29 '10 at 12:56
Isn't this just a duplicate of the question linked to above? – Seamus Aug 30 '10 at 11:08

There is not enough information to uniquely determine the answer.

Here is a situation in which $0$ women get to the city: we place the women in order according to when they boarded the train, and every time a new village is reached the woman who boarded the train farthest back in time leaves. This procedure ensures that every woman eventually leaves the train.

Here is a situation in which countably many women get to the city: every time a new village is reached one of the women who boarded at the previous village leaves. This procedure ensures that the number of women who eventually reach the city increases by $1$ at each village.

One can in fact get any finite number of women to the city.

-
Thank you for the response! So if we wanted to get n women to the village, we could follow the second method you gave for the first n-1 village visits. Before the train reaches the nth village, you could separate this group of n women from the newcomers, and then employ the first strategy to ensure that women n+1, n+2, n+3, etc. all eventually leave the train. – Yun Aug 29 '10 at 8:30
@Yun: that's correct. Divorcing this problem from the story, the issue here is that if f : A \to B is an injection from one countable set into another, the cardinality of the complement of the image of f is not independent of f. (Here A is the set of women who get off and B is the set of women who get on.) This is in marked contrast to the situation when A and B are finite and shows that one must really be careful when reasoning about infinite processes like this. – Qiaochu Yuan Aug 29 '10 at 15:59
There was one last point that irked me. Even if we can ensure that the number of women on the train increases by 1 after each visit, how do we know that the train actually ever reaches the city? It seems that the city would act as an 'upper bound' of that natural numbers, which doesn't make much sense to me. – Yun Aug 30 '10 at 7:39
@Yun: it is perfectly possible to define an abstract object (an ordinal) consisting of the natural numbers in their usual order together with an element, infinity, (here, the city) greater than all of the other elements. This object is no more or less real than the natural numbers themselves. If you prefer to avoid this construction, then I think the only sensible definition of "the set of women who reach the city" is "the set of women who never leave the train." – Qiaochu Yuan Aug 31 '10 at 21:15

The problem is not well posed, since you don't specify which woman leaves the train at each station. See Ross–Littlewood paradox.

-

This problem isn't well defined as it relies on infinity to actually exist. There are two ways of viewing this.

If we want the limit of the number of people on the train as we approach the infinitith stop, this series is +2-1+2-1..., so a number of people with the same cardinality as the integers.

The second and seemingly more correct interpretation is: "How many women stay on the train throughout the whole journey?". If we make women leave the train in the same order they board, the answer is 0, as no-one remains on the train through the whole journey. If we make the last women to board leave, then the answer is infinite.

This behaviour is not strange if you have seen the behaviour of infinite series. For example, while +2-1+2-1... approached infinity, +2-1-1+2-1-1 will always be almost 0.

-
I do not see what reordering a series which doesn't converge has to do with this problem. As my answer shows one must take into account which women are leaving and not just the cardinality of the set of women at each step. – Qiaochu Yuan Aug 29 '10 at 6:12
Thank you also for pointing out the case where 0 women arrive in the city. – Yun Aug 29 '10 at 8:35
Someone upvoted this answer, so let me explain more thoroughly why I think it is misleading. First of all, the hidden assumption here is that passing from sets to their cardinalities is a sensible thing to do. The mathematical argument that actually makes this work for any finite step has to do with symmetry; it says that, up to permutation of the set B, any two injections from a finite set A to another finite set B are the same. As I explained in the comments to my answer, this symmetry argument fails miserably once A and B are infinite, so one must work directly with the sets. – Qiaochu Yuan Aug 29 '10 at 19:57
@Qiaochu: I edited my question. I think it is worth making the point that there are two different ways people interpret the question. I now agree that "How many people stay on the train for the whole journey?" is the better one, but it is worth listing both and explaining that they are different, which may lead some people to think this is a paradox – Casebash Aug 29 '10 at 21:12
@Casebash: the limit interpretation is invalid. For the reasons explained in the answers to the question linked to in the comments above, there is no reason to expect that "number of women on the bus" is a continuous function on the set of villages plus the city in the topology where the city is the limit of the villages. (This is what happens when people learn calculus before set theory...) – Qiaochu Yuan Aug 29 '10 at 21:27