# Another lot of lots of balls

wolfgang59
Posers and Puzzles 08 Oct '10 21:20
1. 11 Oct '10 16:241 edit
Originally posted by wolfgang59
Very elegant. I'm glad I've got an ally!
You guys still have not convinced me that there is any problem here.
2. 12 Oct '10 00:462 edits
Originally posted by LemonJello
No. The numbering of balls is irrelevant. It doesn't matter if you simply don't number the balls at all. What is relevant is the relationship between the extraction command and the temporal indexing of the balls (in terms of bag age). In the actual problem statement, for the case presented here, the extraction command is stated clearly in reference to ...[text shortened]... ntably infinite set can be placed in one-to-one correspondence with a proper subset of itself.
I propose that the notions of one-to-one-correspondence / union / intersection etc are invalid with infinite sets.

I further propose that:
The number of elements in the bag tends to infinity if and only if:
For any number of elements X, there is a step at which the number of elements in the bag is greater than X.

In our case it is then simple to prove that at step number X there will be X + 1 elements. so the number of elements in the bag tends to infinity with increasing step number.
3. 12 Oct '10 04:583 edits
Originally posted by iamatiger
I propose that the notions of one-to-one-correspondence / union / intersection etc are invalid with infinite sets.

I further propose that:
The number of elements in the bag tends to infinity if and only if:
For any number of elements X, there is a step at which the number of elements in the bag is greater than X.

In our case it is then simple to pr ...[text shortened]... 1 elements. so the number of elements in the bag tends to infinity with increasing step number.
Why should I think one-to-one correspondence, for example, is "invalid with infinite sets"? One-to-one correspondence basically means there is some bijection, and I think it is trivial to show that such can exist for infinite sets. You are proposing that it is "invalid" in what sense?

I should also clarify that there may be multiple things at issue in this thread. One I took to be wolfgang's incredulity that the two problems posed could in principle have different answers. That I still would maintain is easily reconciled through the fact that an infinite set can be put in one-to-one correspondence with a proper subset of itself. But the question of what actually is the correct answer to the problem posed in the other thread is, I think, much tougher.
4. 12 Oct '10 07:50
Originally posted by LemonJello
Why should I think one-to-one correspondence, for example, is "invalid with infinite sets"? One-to-one correspondence basically means there is some bijection, and I think it is trivial to show that such can exist for infinite sets. You are proposing that it is "invalid" in what sense?

Regarding the rest, I fully grant you that for any such X as you h ...[text shortened]... is the correct answer to the problem posed in the other thread is, I think, much tougher.
It's just that I think we are leaping to conclusions.

Does the face that every ball is eventually extracted really mean that the number of balls ends up at zero? I'm not sure that we can guarantee that, with infinite sets of added and extracted balls. After all, when ball N is being extracted, ball 2N + 2 is being added, this logic seems to completely ignore the rate of addition.

What worries me about correspondence and infinite sets is this:

Let A be the set {1,2,3,.....}
Let B be the set {2,3,4,.....}

It is clear that there will always be one element of a which is not in B, but we can "prove" with one-to-one correspondence that the mapping B->B-1 aligns set B with A, so the two sets have the same number of elements.
5. 12 Oct '10 11:06
Here's what it probably my final take on the problem.

The argument that the answer cannot be infinite is sound. If there were any balls in the bag at time 0, then it would be possible to name one.

I also find the argument that something is going seriously wrong if the number of balls is monotonic increasing and yet somehow reaches zero quite compelling.

But I'd like to look at is this way (nobody answered this in the other thread, so I'll try again). What we're effectively asked to solve is:

lim(n-> infinity) X_n, where X_n = {n, n+1, n+2, ..., 2n}

What does this mean? We've got a nice solid definition of the limit of a sequence of real numbers. But what is the definition of a sequence of sets? Directly translating the real-number definition isn't straightforward (what is the modulus of the difference between two sets?). Because unless we can agree on a definition, I can't see how we can agree on an answer.

[There may well be an established definition for this. I've had a look, but anything I could find that looked like it might be relevant is beyond an ex-applied-mathematician like myself]
6. 12 Oct '10 20:19
Originally posted by mtthw
[b]Here's what it probably my final take on the problem.

The argument that the answer cannot be infinite is sound. If there were any balls in the bag at time 0, then it would be possible to name one.
At every step I put a random ball numbered between 1 and infinity into the bag.

Name a ball in the bag at T0
7. 13 Oct '10 08:342 edits
Originally posted by iamatiger
It's just that I think we are leaping to conclusions.

Does the face that every ball is eventually extracted really mean that the number of balls ends up at zero? I'm not sure that we can guarantee that, with infinite sets of added and extracted balls. After all, when ball N is being extracted, ball 2N + 2 is being added, this logic seems to completely i at the mapping B->B-1 aligns set B with A, so the two sets have the same number of elements.
Does the face that every ball is eventually extracted really mean that the number of balls ends up at zero?

Yes, I think it does. But, again, I do not think it follows without some ancillary continuity conditions. I think arguments with intuitive clout can be made either way.

After all, when ball N is being extracted, ball 2N + 2 is being added

Yes, but what does this matter? There is surely a subsequent step where ball 2N +2 is extracted just the same. To me, the problem for you seems worse than just not being able (or in a position) to name a ball that remains in the bag: for any ball that goes into the bag, we can easily report the stopwatch reading at which this ball gets extracted. Ball M gets extracted at a stopwatch reading of 60*(1/2)^M seconds, for any M. Of course, you may just tell me that my problem seems bad too: the number of balls in the bag grows beyond all bounds during the super-task.

What worries me about correspondence and infinite sets is this:

Let A be the set {1,2,3,.....}
Let B be the set {2,3,4,.....}

It is clear that there will always be one element of a which is not in B, but we can "prove" with one-to-one correspondence that the mapping B->B-1 aligns set B with A, so the two sets have the same number of elements.

Right, B is a proper subset of A even though they are in one-to-one correspondence and have the "same number" of elements. I do not see any problems at all here. More or less by definition, ANY countably infinite set has one-to-one correspondence (bijection) with your set A and has the "same number" of elements as A. That there is a bijection between A and B is obvious (and that is more or less definitionally all that is needed for one-to-one correspondence); so, if I understand you, your problem would be with a subsequent inference to the idea that A and B have the "same number" of elements. If I understand you there, I would agree that this terminology only makes sense in a trivial, definitional sort of way: definitionally we could say infinite sets A and B have the "same number" of elements if there is a bijection between them; but then the inference from one-to-one correspondence between A and B to the idea that A and B have the same number of elements has no more substance than just this. But I do not think anything here would have anything to do with showing that the notion of one-to-one correspondence (bijection) is "invalid" with infinite sets, which was your earlier claim. I might be missing your point still...
8. 13 Oct '10 08:38
Originally posted by iamatiger
At every step I put a random ball numbered between 1 and infinity into the bag.

Name a ball in the bag at T0
But that's a random process, not a deterministic one.
9. wolfgang59
surviving
15 Oct '10 23:26
Originally posted by iamatiger
At every step I put a random ball numbered between 1 and infinity into the bag.

Name a ball in the bag at T0
Name the last ball out!
...
The problem is NOT about naming individual balls , it is about a function after infinite iterations.
10. Palynka
Upward Spiral
17 Oct '10 17:052 edits
Originally posted by iamatiger
At every step I put a random ball numbered between 1 and infinity into the bag.

Name a ball in the bag at T0
At T0, I put my hand in the bag, take one out and tell you the number on it. Easy.

Of course, there is also no distribution that could possibly allow me to take a random ball numbered between 1 and infinity with equal probability.
11. 19 Oct '10 09:471 edit
I've also been thinking along the lines of randomness, but in a somewhat different way.

Let's suppose that in the original stipulation, two balls are still added at every step, but rather than removing the "oldest" or "youngest" ball, you instead remove a ball at random. Then how many balls are left at the end?

How is it possible that there will be a different amount of balls if the randomly chosen one happens to be the youngest at every step, than if it were any other sequence of balls?

As for the idea of "positive numbers increasing to zero" being more acceptable than "removing all inputs to yield an infinite amount", I just don't think that's the case when each removal is matched by twice as many inputs.

Say what you will, I can't imagine ever being convinced that the order in which the balls are removed should have any bearing on the amount of balls remaining.
12. Palynka
Upward Spiral
19 Oct '10 09:54
Originally posted by Jirakon
Say what you will, I can't imagine ever being convinced that the order in which the balls are removed should have any bearing on the amount of balls remaining.
Do you agree that the sets A={1,2,3,..} and B={2,4,6,...} have the same cardinality?

Yet if you remove all elements of B in A you get C={1,3,5,...} which still has the same cardinality as A and B?

It's the same issue here. If you remove B from A or A from A you are removing sets with the same number of elements but you either get a set of infinite size or the empty set.
13. 19 Oct '10 10:21
I guess the main disagreement everyone's having is whether the two sets in the problem are ever actually the same size. It just doesn't make sense that two sets start out empty, then start growing, with one growing twice as fast as the other, until they're the same size ðŸ˜•

In my view, the set of balls removed will always contain half the values in the set of balls added, no matter how many steps are taken, nor when each ball is taken out. The alternative is just too much for my finite mind @_@
14. Palynka
Upward Spiral
19 Oct '10 13:17
Originally posted by Jirakon
I guess the main disagreement everyone's having is whether the two sets in the problem are ever actually the same size. It just doesn't make sense that two sets start out empty, then start growing, with one growing twice as fast as the other, until they're the same size ðŸ˜•

In my view, the set of balls removed will always contain half the values in the set ...[text shortened]... ken, nor when each ball is taken out. The alternative is just too much for my finite mind @_@
LOL, it is indeed a mind-boggling problem.

Do you recognize the difficulty of the answer 'infinite', though? If I take a ball out of this bag which has so many balls and I look at its number, then I will realize it must have been taken out before!
15. 19 Oct '10 16:39
Actually, I wouldn't mind just labelling all the remaining balls with "infinity". It may not be very elegant, but it's better (in my mind) than thinking the set {1, 2, 3,...} of the total number of balls at each step converges to zero ðŸ˜•