Posers and Puzzles

Posers and Puzzles

  1. Joined
    24 Apr '05
    Moves
    3061
    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. Joined
    26 Apr '03
    Moves
    26707
    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. Joined
    24 Apr '05
    Moves
    3061
    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?

    Regarding the rest, I fully grant you that for any such X as you have described, we can find some step such that the number of balls in the bag exceeds X. But I think that is not sufficient to answer the question. Just like I can say to you, hey, for any ball that goes into the bag, we can find some step such that this ball is extracted. (I am talking here about the problem posed in the other thread. For the problem posed in the opening post of this thread, I think we already agree on the same answer.) That also, I think, is not sufficient to answer the question. One thing that is interesting about this problem (or about the Littlewood-Ross type paradox problem, generally) is that it is logically under-described. The information you are given in this case for all these events before a certain time does not formally entail a certain state of affairs at that certain time in question. That is why, from my past study of such problems, much of the debate seems to come down to what "continuity conditions" are imported to answer the question, which ones are reasonable or plausible, etc. The ones I agree with in this case would be similar to those proposed by Allis & Koetsier, and I think the combination of states of affairs such that (1) the number of balls in the bag grows at each step and (2) there are no balls remaining in the bag at the time in question is an intuitively frustrating resolution but an acceptable one (and one that is not inconsistent). On the other hand, I think the combination of states of affairs such that (1) for any ball there is some step where it gets extracted from the bag and (2) there are infinitely many balls remaining in the bag at the time in question is not only intuitively frustrating but also unacceptable and inconsistent. But, I do think this is highly debatable, based on what continuity conditions should also be in play. There are yet others who think the problem is not well-defined to begin with; or those who think it represents an impossible super-task to begin with; etc.

    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. Joined
    26 Apr '03
    Moves
    26707
    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. Joined
    07 Sep '05
    Moves
    35068
    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. Joined
    26 Apr '03
    Moves
    26707
    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. Joined
    24 Apr '05
    Moves
    3061
    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. Joined
    07 Sep '05
    Moves
    35068
    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. Standard memberwolfgang59
    Mr. Wolf
    at home
    Joined
    09 Jun '07
    Moves
    46307
    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. Standard memberPalynka
    Upward Spiral
    Halfway
    Joined
    02 Aug '04
    Moves
    8702
    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.

    You can't do that with your answer to the original problem without reaching a contradiction.

    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. In Christ
    Joined
    30 Apr '07
    Moves
    172
    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. Standard memberPalynka
    Upward Spiral
    Halfway
    Joined
    02 Aug '04
    Moves
    8702
    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. In Christ
    Joined
    30 Apr '07
    Moves
    172
    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. Standard memberPalynka
    Upward Spiral
    Halfway
    Joined
    02 Aug '04
    Moves
    8702
    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. In Christ
    Joined
    30 Apr '07
    Moves
    172
    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 😕
Back to Top