Infinite Balls and Jugs [solution]

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Qaanol » Wed Mar 23, 2011 4:31 pm UTC

redrogue wrote:I'm envisioning Zeno's paradox flipped on its head. The tortoise is trying to chase down Achilles. Are you saying that over an infinite number of legs of the race, the tortoise eventually catches him?

For every inch of ground Achilles has covered, the tortoise has covered that inch as well.

A more-easily visualized setup would be, an historian starts writing a detailed history of the world. However, for every year of history, it takes 10 solid years to write it all down. And of course each year is written about in order, so the 9-year delays pile up one after the next.

Nevertheless, for every year that goes by, that year will eventually be recorded in the history book.
wee free kings

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby redrogue » Wed Mar 23, 2011 4:45 pm UTC

Right, but won't there also be an infinite distance between Achilles and the tortoise? Just because I can't name a *finite* distance both haven't covered in an infinite race doesn't mean the tortoise will have caught him.
Is 'no' your answer to this question?

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Qaanol » Wed Mar 23, 2011 5:08 pm UTC

redrogue wrote:Right, but won't there also be an infinite distance between Achilles and the tortoise? Just because I can't name a *finite* distance both haven't covered in an infinite race doesn't mean the tortoise will have caught him.

Is there an inch immediately in front of the tortoise?
wee free kings

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby redrogue » Wed Mar 23, 2011 6:47 pm UTC

You've just asked a question I don't fully comprehend.

If I answer 'yes,' then I concede that the tortoise hasn't run an infinite distance, which is clearly not the case. If I answer 'no,' then I must somehow rationalize how Achilles hasn't outpaced the tortoise.

I'd like to answer that yes, there an infinite number of inches stretching out in front of the tortoise. And also behind the tortoise. And in front of and behind Achilles. And of course, between the two competitors.

Honestly, though, I don't know.

Edit:
And yet, it seems absurd to suggest that there is an infinite untraveled distance in front of the tortoise, since he's traveled infinitely far.
Is 'no' your answer to this question?

User avatar
Shufflepants
Posts: 19
Joined: Wed Jul 20, 2016 3:12 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Shufflepants » Tue Oct 11, 2016 8:01 pm UTC

I feel like this problem is much more easily solved in the Surreal Numbers than it is in the familiar natural numbers which are explicitly all finite. The Surreals include all the natural numbers, but also explicitly includes the number ω which is greater than all natural numbers and in the Surreal numbers we can also talk about ω+1 and show that it is indeed true that ω+1 > ω. If we work in the Surreals, I think the answers are fairly clear:

If we remove the lowest numbered ball each time, at the end, there will be no natural numbers left in the jug, but the jug will contain 9ω balls in it labeled ω through 10ω-1.

If we remove the highest numbered ball each time, at the end, there will still be 9ω, but it will be missing every 10th ball.

If we remove a ball randomly each time, at the end, most natural numbers will have been removed, but most likely not quite all of them and there will be 9ω balls in the jug.

In the case of instead of removing a ball, simply adding a zero onto the end and replacing it, we will have 10ω balls in the jug at the end, and none of them will be labeled with natural numbers.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Fri Oct 14, 2016 11:35 pm UTC

Shufflepants wrote:If we remove the lowest numbered ball each time, at the end, there will be no natural numbers left in the jug, but the jug will contain 9ω balls in it labeled ω through 10ω-1.


My reservation with this is that, since we started with balls labeled with natural numbers, we don't have a ball labeled ω (or any ordinal containing ω) to put into the jug in the first place, so how did such a ball get into the jug?

Additionally, it seems like the conclusion of the final composition of balls in the jug is somewhat circular. Why does ω remain in the jug, and is never removed? Is it because we never reached the step where we put in ball 10ω? Because then, why is that other than so that ω would remain in the jug?

I would need to resolve that before I can accept the further conclusions, or that surreal numbers can even apply to this problem at all.

mward
Posts: 123
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby mward » Tue Oct 18, 2016 3:49 pm UTC

I have scanned the whole thread, and I don't think that the following explanation has been posted yet:

First consider a simplified scenario:

Suppose that there are three jugs labelled A, B and C.
Initially, jug A contains all the balls (numbered 1, 2, 3, ... and so on).
At step n we move the ball labelled n from jug A and place it into jug C.

Are we all agreed that at midnight (step ω, in which we do nothing except look at the jugs), jug A is empty (because every ball has been removed), jug B is empty (nothing was put in and nothing taken out) and jug C contains all the balls that were originally in jug A?

Do not read any further until you have convinced yourself that the above argument is correct!

Now consider the actual scenario:

At step n we move balls 10n-9 to 10n from jug A to jug B. Then we move ball n from jug B to jug C.

At midnight (step ω, in which we do nothing except look at the jugs), jug A is empty (because every ball has been removed) and jug C contains all the balls (because, for every n, ball n was placed into it at step n).

Therefore, at midnight, jug B must be empty: since all the balls have been accounted for!

QED?

User avatar
Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Infinite Balls and Jugs [solution]

Postby Wildcard » Sun Oct 23, 2016 8:17 am UTC

My opinion on this problem has changed since I first posted about it.

This experiment can't be performed according to the laws of the physical universe in which we live. (The balls must have mass; infinite mass cannot be placed in a finite space; to move mass any distance in zero time as must occur by midnight the speed must be infinite...I could go on.)

Therefore, it is meaningless to talk about what "would" occur unless we determine what are the laws of the universe in which we are working (since it isn't the real physical universe where rules can be empirically established or verified).

Mathematics are methods of postulating or resolving real or abstract data—and in this case the data is abstract.

The outcome of the experiment, therefore, depends upon how the rules of the universe are set up by those who set up the universe. Since this is a mathematician's thought experiment, the one who set up the universe is the mathematician.

Any set of rules can be set up when you set up your own universe as for a thought experiment. They don't have to be consistent, or even "logical" in any meaningful sense of the word, since you define what logic means in the universe you set up.

So there is no single correct answer to this riddle, and anyone saying otherwise is actually simply saying, "The laws of the universe that I set up for this experiment are senior to the laws of the universe that you set up for this experiment."

They may also be saying, "I can cite more mathematicians who agree with my set of rules than you can cite who agree with your set of rules," but either way, since the rules do not apply to the physical universe, there is still no single correct answer, nor is any answer more "true" than any other answer.

*bows, exits*
There's no such thing as a funny sig.

User avatar
Sableagle
Ormurinn's Alt
Posts: 2149
Joined: Sat Jun 13, 2015 4:26 pm UTC
Location: The wrong side of the mirror
Contact:

Re: Infinite Balls and Jugs

Postby Sableagle » Sun Oct 23, 2016 9:37 am UTC

jestingrabbit wrote:The way to resolve indeterminate forms is to get your hands dirty and this is only a thought experiment. There are not urns like this and its impossible to do the things with the balls that the problem suggests.


Image
Zohar wrote:You don't know what you're talking about. Please spare me your quote sniping and general obliviousness.

CorruptUser wrote:Just admit that you were wrong ... and your entire life, cyberspace and meatspace both, would be orders of magnitude more enjoyable for you and others around you.

User avatar
ucim
Posts: 6888
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Infinite Balls and Jugs [solution]

Postby ucim » Sun Oct 23, 2016 5:00 pm UTC

mward wrote:Are we all agreed that at midnight (step ω, in which we do nothing except look at the jugs), jug A is empty (because every ball has been removed), jug B is empty (nothing was put in and nothing taken out) and jug C contains all the balls that were originally in jug A?
We can never reach step ω. If we could, there would be a step ω-1 in which there was just one ball left in jug A, and it would have to be labeled ω-1. There is no such ball.

ω is not an integer that can be reached from the finite integers. Operations using ω are only valid "once you've reached it".

So, no. I'm not convinced.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

User avatar
Shufflepants
Posts: 19
Joined: Wed Jul 20, 2016 3:12 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Shufflepants » Tue Oct 25, 2016 7:10 pm UTC

I guess I need to amend my answer.

In the case where we place the next ten balls in the jug and then remove the lowest:
If we don't have any balls beyond ω to start with. Then when we reach step ω/10 we run out of balls to add. And the last 9ω/10 of the integers remain in the jug.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Wed Oct 26, 2016 4:51 am UTC

Shufflepants wrote:I guess I need to amend my answer.

In the case where we place the next ten balls in the jug and then remove the lowest:
If we don't have any balls beyond ω to start with. Then when we reach step ω/10 we run out of balls to add. And the last 9ω/10 of the integers remain in the jug.


What ball is removed in step "ω/10"?

And before you amend your answer further: What time is it when you perform the first step in which no ball is put in, yet one is removed? And what rule in the game allows such a step to take place? What happened the step before that?

It seems as though you are taking the intuition that there are 9 times n balls in the jug (where n is the number of steps) and trying to invent an answer that doesn't contradict that intuition. That process is leading you to absurdity. Disregarding intuition, you know what happens to each ball. It gets added at some step and removed at step n. The rules are defined for each step and for each ball.

If you still have trouble giving up the (incorrect) intuition, try grappling with mward's alternatives above.

User avatar
Shufflepants
Posts: 19
Joined: Wed Jul 20, 2016 3:12 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Shufflepants » Fri Oct 28, 2016 3:43 pm UTC

Xias wrote:What ball is removed in step "ω/10"?


Well if you're going to start asking those sorts of questions, then I guess I'll just have to give up and agree with Wildcard that there can be no correct answer. Because if you're going to ask which ball is removed at step ω/10, we might as well also ask of the original question: "what is the number on the last ball removed". Since clearly there must have been a last one since we completed our task by midnight.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Fri Oct 28, 2016 5:47 pm UTC

Shufflepants wrote:
Xias wrote:What ball is removed in step "ω/10"?


Well if you're going to start asking those sorts of questions, then I guess I'll just have to give up and agree with Wildcard that there can be no correct answer. Because if you're going to ask which ball is removed at step ω/10, we might as well also ask of the original question: "what is the number on the last ball removed". Since clearly there must have been a last one since we completed our task by midnight.


You're right: both of those questions can be asked. The answer to both is, easily, "there is no such step." If there were a last step, then there would be a ball that is the last ball removed. However, there is no last step. The difference between my question and yours is that my question points out a consequence of your solution to the puzzle - one that is contradictory to the rules of the puzzle. Your question doesn't contradict anything because it's asking about something that I don't claim exists. There is no last ball removed. There is no last step. There is no ball left in the jug.

In fact, asserting that there is a last ball removed is exactly where your intuition is failing you. There cannot be a last ball removed because that is contradictory: Let t be the time when the last ball n is removed. Then at t/2, ten balls are added and ball n+1 is removed. So n is not the last ball removed.

The solution can be proved in the same way: If the jug has any balls in it, then there is some natural number m such that the ball labeled m was never removed. However, the rules dictate that for every natural number n, ball n is removed at step n. Then ball m is removed at step m, which is a contradiction. No such ball can exist.

On the other hand, when I ask you what ball is removed at step ω/10, I'm asking because you claimed that there was such a step. So while I'll happily respond to your question with "There is no last step" and remain consistent with my solution, if you want to respond "there is no step ω/10" then it undermines the solution that you suggested. And rightfully so, since your solution is inconsistent with the rules of the puzzle, and is therefore not correct.

The given solution is logically airtight, and its only flaw is that it goes against intuition. That's fine. Intuition regarding infinities and supertasks is often wrong, because there is no reason for us to develop intuition for things that can't actually exist in real life. The infinite geometric sum of (1/2)n from n=1 to infinity is equal to 1. The entire field of calculus involves using limits to circumvent the problem of dividing by zero. 0.99... = 1.

If your approach to such problems is to throw your hands up because you refuse to accept the rules of the game, then why are you even playing?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Cauchy » Fri Oct 28, 2016 7:10 pm UTC

I'm not sure why we should just blindly accept that the pointwise limit of the sets is the correct one. I agree that no other limit makes sense, but in a lot of contexts we simply say "there is no limit" when the pointwise limit fails to do what we want. And if it can't even preserve cardinality, then I'm perfectly happy saying that there is no limit.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Fri Oct 28, 2016 7:55 pm UTC

Cauchy wrote:I'm not sure why we should just blindly accept that the pointwise limit of the sets is the correct one. I agree that no other limit makes sense, but in a lot of contexts we simply say "there is no limit" when the pointwise limit fails to do what we want. And if it can't even preserve cardinality, then I'm perfectly happy saying that there is no limit.


I'm far more open to that being the solution to some of the many variants of the problem, such as the removing-balls-at-random version.

With the first version, though, it seems to me that suggesting that there is no limit is equivalent to saying that nobody leaves the island.

mward
Posts: 123
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby mward » Sat Oct 29, 2016 12:08 pm UTC

There is no step "ω/10" since there is no (finite or infinite) number which gives ω when multiplied by 10.

In case you are not convinced, consider the fact that "ω/10" must be either finite or infinite:
(1) If "ω/10" is finite, then ω/10*10 = ω is also finite. But ω is infinite. This is a contradiction, so "ω/10" must be infinite
(2) If "ω/10" is infinite, then nothing happens on that step (since somthing happens only on finite numbered steps)
So there is no step "ω/10" on which balls are inserted or removed.

Similarly, there is no step "ω-1".

User avatar
ucim
Posts: 6888
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Infinite Balls and Jugs [solution]

Postby ucim » Sun Oct 30, 2016 1:56 pm UTC

This is really just a variant of Zeno's paradox. Here's another:
There is a light switch and a finite negative number t. At time t, the switch is in the on position. At time t/2 it is switched off, at time t/3 is is switched on again and at time t/4 it is switched off..., so that the switch is toggled at every t/n. What position is the switch in at time 0?
Spoiler:
broken
Clearly you can get there because zero exists. But you can't get there from here. Similarly even though ω gives you have a "solution" to the jugs problem, you can't get there from here. ω is discontiguous to the integers.

The same trap awaits those who think they have found an alternate form of -1/12.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Mon Oct 31, 2016 4:07 am UTC

ucim wrote:This is really just a variant of Zeno's paradox. Here's another:
There is a light switch and a finite negative number t. At time t, the switch is in the on position. At time t/2 it is switched off, at time t/3 is is switched on again and at time t/4 it is switched off..., so that the switch is toggled at every t/n. What position is the switch in at time 0?
Spoiler:
broken
Clearly you can get there because zero exists. But you can't get there from here. Similarly even though ω gives you have a "solution" to the jugs problem, you can't get there from here. ω is discontiguous to the integers.

The same trap awaits those who think they have found an alternate form of -1/12.

Jose


A key difference between this and the light switch paradox is that you can't come to any sensible conclusion about the light switch. In this case, we can make a logical argument for the jug being empty, but not being nonempty. Just like we can say what the sum of certain infinite geometric series are.

Do you agree that in the second game, where you remove the highest labeled ball at each step, there are infinite balls left in the jug? That is the only reasonable conclusion. And being empty is the only reasonable conclusion in the first game. The disconnect between the integers and ω is not a problem; it is necessary for any sense to be made. Calling midnight "step ω" is an informality to illustrate that midnight comes after an infinite number of steps.

If your only reason for saying there is no solution is because we "can't get there from here" then you seem to take issue with this entire form of puzzle. Do you take similar issue with the Hilbert Hotel?

It's interesting that you bring up Zeno's Paradoxes, since two of them demonstrate that we complete infinite tasks in finite time every day, despite the paradox. Achilles catches the tortoise, despite the tortoise always being ahead. Homer reaches the end of the path despite never having a first step to take. The arrow flies, despite being still at every instant. And the jug is empty despite never reducing its contents.

User avatar
ucim
Posts: 6888
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Infinite Balls and Jugs [solution]

Postby ucim » Mon Oct 31, 2016 4:21 pm UTC

Xias wrote:A key difference between this and the light switch paradox is that you can't come to any sensible conclusion about the light switch.
But "sensible" conclusions about infinities are illusions. The fact that a "sensible" conclusion exists just makes it an interesting "wait, wut?", but sensibleness and correctness are not so simply connected.

Xias wrote:Calling midnight "step ω" is an informality to illustrate that midnight comes after an infinite number of steps.
There are infinities and there are infinities. The informality employed here handwaves this, leading to the absurd conclusion, because midnight is not, in fact, "step ω".
Spoiler:
If it were, it would also be step ω+1, step ω-1, step 2ω, step ωω, etc., all at the same time. Contrary to mward's contention:
mward wrote:Are we all agreed that at midnight (step ω, in which we do nothing except look at the jugs)...
..."At midnight", everything happens, all at once. Also, there aren't ω balls in the jug. There are aleph naught (the cardinality of integers) of them. ω is an ordinal, not a cardinal, and being an infinite ordinal, it is not included in the set of (finite) integers whose cardinality is aleph null. Therefore, there is no step ω, and no ball ω. You can't get there from here.
Xias wrote:If your only reason for saying there is no solution is because we "can't get there from here" then you seem to take issue with this entire form of puzzle. Do you take similar issue with the Hilbert Hotel?
The Hilbert Hotel (as I understand it) is not a paradox; it's a proof and is well formed. It shows that two infinities can be equal (have the same cardinality) even if one is a proper subset of the other. This puzzle is not well formed, because it inherently handwaves over the differences between the infinities.

Xias wrote:Achilles catches the tortoise, despite the tortoise always being ahead.
The tortoise is not always ahead. It's only ahead until Achilles catches up.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Mon Oct 31, 2016 5:34 pm UTC

edit: I say "integers" a lot when what I mean is "natural numbers." Please excuse the mistake.

ucim wrote:
Xias wrote:Calling midnight "step ω" is an informality to illustrate that midnight comes after an infinite number of steps.
There are infinities and there are infinities. The informality employed here handwaves this, leading to the absurd conclusion, because midnight is not, in fact, "step ω".
Spoiler:
If it were, it would also be step ω+1, step ω-1, step 2ω, step ωω, etc., all at the same time. Contrary to mward's contention:
mward wrote:Are we all agreed that at midnight (step ω, in which we do nothing except look at the jugs)...
..."At midnight", everything happens, all at once.


Nothing is described as happening at any time later than a time before midnight. Since nothing happens at midnight, calling it a step is incorrect. However, it is important to recognize that midnight happens after a million steps have occurred, after a googolplex of steps have occurred, after a Graham's Number of steps have occurred. For any integer step, the time that step happens is before midnight. Furthermore, nothing happens between the integer steps that occur before midnight, and midnight. Then, informally calling midnight "step ω" to illustrate that it happens immediately after every integer step has completed may be helpful to some people. If it's not helpful to you, you're welcome to ignore it. I don't want to speak for mward, but I see no reason to believe he was trying to assert anything about a relationship between the properties of ω and the solution. (It may also be important to note that, as far as I understand, mward was referring to the transfinite number ω defined in the surreal numbers as greater than all positive numbers, not the set ω defined as the set of all finite ordinals.)

Going back to what you said earlier: "Similarly even though ω gives you have a 'solution' to the jugs problem" does not apply to what anyone here is saying, because the solution is not "given by" ω. ω has nothing to do with it.

ucim wrote:Also, there aren't ω balls in the jug. There are aleph naught (the cardinality of integers) of them. ω is an ordinal, not a cardinal, and being an infinite ordinal, it is not included in the set of (finite) integers whose cardinality is aleph null.


How are there any balls in the jug? Unless you mean Jug A in mward's alternative game, in which case, nobody ever said that we started with ω balls in jug A, nor is that at all a necessary premise for the conclusion.

ucim wrote:
Xias wrote:If your only reason for saying there is no solution is because we "can't get there from here" then you seem to take issue with this entire form of puzzle. Do you take similar issue with the Hilbert Hotel?
The Hilbert Hotel (as I understand it) is not a paradox; it's a proof and is well formed. It shows that two infinities can be equal (have the same cardinality) even if one is a proper subset of the other. This puzzle is not well formed, because it inherently handwaves over the differences between the infinities.


It is what is called a "veridical" paradox, in that the conclusion is counterintuitive, but provably true. It is provably true, despite not being demonstrably true (since no such hotel could possibly exist).

I contend that this is also a veridical paradox. It is counterintuitive, since intuition dictates that since the number of balls in the jug is strictly increasing with no limit, it follows that there are an infinite balls in the jug after infinite steps. However, it is provably true that the jug is empty:

Spoiler:
Suppose the jug has a nonzero number of balls in it at midnight.

Then for some integer m, there exists a ball m that is never removed.

By the rules of the game, for every integer n, ball n is placed into the jug at some step pn, where pn is less than or equal to n, and then removed at step n.

Then ball m is placed into the jug at step pm and removed at step m.

Therefore, ball m is removed. This is a contradiction.

Assuming that there are zero balls left in the jug leads to no such contradiction.


It is provably true, despite being counterintuitive, and despite not being demonstrably true (since no such jug could possibly exist.)

Let's take a step back, to an amended version of mward's alternative:

You have two empty jugs, A and B. You also have, for each integer n, a ball labeled with that integer (called "ball n"). So you have ball 1, ball 2, ball 3... for all of the integers.

Before time 0, place all of the balls in jug A. At time 0, remove ball 1 from jug A and place it into jug B. At time t/2, remove ball 2 from jug A and place it into jug B. At time t(1/2)n-1, remove ball n from jug A and place it into jug B. At time t, do you agree that there are zero balls in jug A, and every ball is in jug B?

ucim wrote:
Xias wrote:Achilles catches the tortoise, despite the tortoise always being ahead.
The tortoise is not always ahead. It's only ahead until Achilles catches up.

Jose


Indeed; despite the paradox.

---
Last edited by Xias on Mon Oct 31, 2016 7:30 pm UTC, edited 1 time in total.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby PeteP » Mon Oct 31, 2016 7:18 pm UTC

The comparision with Zeno's paradox does not work. It is about an infinite sum of increasingly smaller numbers summing to a non infinite number. This is about (10-1)x becoming zero at infinity. Translating it to the scenario from Zeno's paradox Achilles is running in front and the tortoise is still slower but will catch up because at infinity you can name no meter Achilles has run that she hasn't run. Imo this is more of a demonstration of how slavishly following an argument can led to absurd results. (And that infinity in no number so just inserting it like one can return nonsense.) You say it is true because it is a contradiction otherwise, how is there no contradiction in a monotonically growing function reaching a lower value when increasing the parameter?

Run variant 1 and 2 at the same time, you add and subtract the same number of balls at each step so they always have the same number, how is them ending up with a different number not a contradiction?

Number the balls for problem 1 at step n ball n is removed and the last ball added is n*10. To empty it the last ball removed has to be the last ball added, how is 10*n=n with n>0 not a contradiction?

There are many reasons why the answer makes no sense so why does only the contradiction that it has to be the case count? (And imo how is the contradiction different than saying: "e^x can't always grow faster than x^2, at infinity there is no number bigger than x^2 so it must have reached e^x". It sounds more like a nonsensical question to ask about something infinite. If you can explain why the argument does not mean that f1-f2 goes against 0 when both going against infinity individually and f1 grows faster than f2, then I might be convinced of this. (Or alternatively why it does mean that but that makes more sense.) The contradiction only is a contradiction if infinity can't be smaller than another infinity, but when forming limits of anything with a minus sign we regularly consider one part insignificantly small compared to the other even if both go against infinity.)

Edit: Let me add a last one: Scenario 1 with an extra. When removing the balls you put them in the a second urn B (it starts with one ball numbered 10) but when adding them you renumber them to (x+1)*10 (x being their old number), when adding the 10 balls to urn A ball number 10n comes from urn B. There is no number that hasn't been removed from urn A, thus the argument that it is empty should remain the same. You can also name no ball that hasn't been removed from urn B, so where the hell are the balls?

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Mon Oct 31, 2016 9:10 pm UTC

PeteP wrote:The comparision with Zeno's paradox does not work.


I'm actually inclined to agree with you. ucim made the initial comparison to Zeno's and I wanted to explore the consequences of that.

In reality, Zeno's are examples of falsidical paradoxes, while this is an example of a veridical paradox.

PeteP wrote:Run variant 1 and 2 at the same time, you add and subtract the same number of balls at each step so they always have the same number, how is them ending up with a different number not a contradiction?


The nature of each variant puts importance on what happens to each individual ball. While the amount of matter that moves remains the same in both variants, the journey that each ball takes is different. There is a solution only because the puzzle created one by offering new parameters beyond "S = 10 - 1 + 10 - 1..."

PeteP wrote:Number the balls for problem 1 at step n ball n is removed and the last ball added is n*10. To empty it the last ball removed has to be the last ball added, how is 10*n=n with n>0 not a contradiction?


I contend that there is no last ball added and no last ball removed. To say there is would mean that there is a largest natural number, which there isn't, and it would mean there is a last step, which there isn't.

I know that we agree that Zeno's paradoxes aren't well suited for comparison here, but I want to point out that if you get hung up on there being a "last step" required to resolve them, then they are also unable to be resolved. At any given point before Achilles passes the tortoise, he is behind the tortoise by some distance. And when he moves over that distance, the tortoise moves forward another distance. If I were skeptical that Achilles could ever pass the tortoise because then there would be a "last step" where Achilles covers the distance while the turtle remains still, but that never happens, how would you convince me otherwise?

PeteP wrote:There are many reasons why the answer makes no sense so why does only the contradiction that it has to be the case count? (And imo how is the contradiction different than saying: "e^x can't always grow faster than x^2, at infinity there is no number bigger than x^2 so it must have reached e^x". It sounds more like a nonsensical question to ask about something infinite. If you can explain why the argument does not mean that f1-f2 goes against 0 when both going against infinity individually and f1 grows faster than f2, then I might be convinced of this. (Or alternatively why it does mean that but that makes more sense.) The contradiction only is a contradiction if infinity can't be smaller than another infinity, but when forming limits of anything with a minus sign we regularly consider one part insignificantly small compared to the other even if both go against infinity.)


There are many reasons? The only one I know of is that the jug should be infinitely full because the number of balls inside is monotonically increasing. That leads to a contradiction.

It is the discrete nature of the problem - that we are talking about individual, well-defined objects and how they behave - that differentiates this from a mere limit of a function. This is more like a limit of the union of sets:

Let α1 = {1}, α2 = {2}, and so on; αn = {n}.

Let β1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, β2 = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, and so on: βn = ∪i=0→9{10n-i}

Then let
Ak = ∪i=1→kαi
Bk = ∪i=1→kβi

Then
limk→∞Ak = limk→∞Bk = N

Furthermore, Ak and Bk can be indexed, so that the nth term of Ak is n, and the same for Bk.

Now, it's clear that Ak⊂Bk for all k∈N. It's also clear that

|Bk\Ak| < |Bk+1\Ak+1| k∈N.

However, once you take k to infinity, the symmetric difference of A and B is the null set. The relative complement of A in B is the null set. |B \ A| is zero. Formally, if C is the set of all balls remaining at midnight:

C = ∪i=1→∞βi - ∪i=1→∞αi = N - N = 0.

Again, this all only works because we are working with sets of objects (balls in the jug at each step) rather than typical functions and limits.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby PeteP » Mon Oct 31, 2016 11:32 pm UTC

Question based on taking a scenario from elsewhere*:
Suppose we have two urns, A and B. At the nth stage we place ball balls 10n-9 to 10n-1 in urn A, and ball 10n in urn B, renumbering the balls at each stage so that urn B contains balls numbered 1 to n, and urn A contains balls numbered n+1 to 10n. At each stage the balls in urn A will be identical to those in the urn of Littlewood's super-task.


So B will be N at the end. A only contains numbers from N and contains no numbers that are in B. So N-N=0 applies, does that imply A will empty despite never removing a ball from it just by virtue of relabeling the balls?

*I suppose I should link when stealing someone elses example. http://www.csc.twu.ca/byl/little.fin.doc

User avatar
ucim
Posts: 6888
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Infinite Balls and Jugs [solution]

Postby ucim » Tue Nov 01, 2016 2:32 am UTC

Xias wrote:Furthermore, nothing happens between the integer steps that occur before midnight, and midnight.
I'm pretty sure that's "not even wrong". Consider the series 1/n as n goes to infinity. What's between the set of points consitituting that set, and zero? Does it ever reach zero?

You can't get there from here.

Xias wrote:How are there any balls in the jug?...
It's the starting condition. I should have been specific - jug A. If there aren't ω balls in the jug, then ball ω can never emerge.

I agree that there are no balls left in the jug (B). More precisely, there are infinity minus infinity balls left in the jug. My issue is with the existence of step ω, where "nothing happens". There is no such step.

Xias wrote:Before time 0, place all of the balls in jug A. At time 0, remove ball 1 from jug A and place it into jug B. At time t/2, remove ball 2 from jug A and place it into jug B. At time t(1/2)n-1, remove ball n from jug A and place it into jug B. At time t, do you agree that there are zero balls in jug A, and every ball is in jug B?
Yes.

PeteP wrote:To empty it the last ball removed has to be...
There is no last ball removed.
PeteP wrote:...how is 10*n=n with n>0 not a contradiction?
When n "equals" infinity. It would be a contradiction at every step of the way (all are finite) but when all is said and done, you have infinity minus infinity, which equals anything without paradox. Hilbert's Hotel.

10k - 1k = (10-1)k for finite k. This is not so for infinite k.

The parallel to Zeno's paradox is in the idea of a "last step". There isn't one, but we do complete the task.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Tue Nov 01, 2016 5:54 am UTC

PeteP wrote:Question based on taking a scenario from elsewhere*:
Suppose we have two urns, A and B. At the nth stage we place ball balls 10n-9 to 10n-1 in urn A, and ball 10n in urn B, renumbering the balls at each stage so that urn B contains balls numbered 1 to n, and urn A contains balls numbered n+1 to 10n. At each stage the balls in urn A will be identical to those in the urn of Littlewood's super-task.


So B will be N at the end. A only contains numbers from N and contains no numbers that are in B. So N-N=0 applies, does that imply A will empty despite never removing a ball from it just by virtue of relabeling the balls?

*I suppose I should link when stealing someone elses example. http://www.csc.twu.ca/byl/little.fin.doc


No, but it does imply that A does not empty, despite having balls labeled the same as in the initial game at every step, just by virtue of relabeling the balls.

The parameters of the game have changed very much, which really does change the outcome of the game. I'm not sure what happens in this case, if at midnight you reach into jug A and pull out a ball. However, there was a variant earlier in the thread, where you put balls 10(n-1)+1 through 10(n-1)+9 in the jug, then take ball n and add a 0 to the end of the label. So in step one, you put in balls 1 through 9, and then change ball 1 to ball 10. At the end of each step, the balls are identical to the balls in the original variant; yet the jug is full at midnight. So then we pose the question, when you pull out a ball, what is on the label? The only answer we could really come up with was that it would have an arbitrary finite string of digits followed by an infinite string of zeroes. There's never a step where the string goes from finite to infinite; however, for every zero in the string, you can determine at what point that zero was added.

In the variant you bring up, again, I'm not sure what happens, because how the relabeling happens is not well defined. I cannot follow a ball and determine how it is labeled at each step. Maybe you do end up with jug A containing ω, ω+1, ... ω+ω; but this would only be because the process allows you to create such labels that didn't exist before.

This doesn't mean that there is a flaw in the original solution, though. In Hilbert's Hotel, it's quite acceptable that there is a strategy to fit an infinite number of new guests; one such strategy is to have every guest move from n to room 2n. This doesn't change if we turn this into a supertask. I'll put this in spoiler tags for ease of formatting:

Strategy A:
Spoiler:
Take all incoming guests and label them with the odd numbers n=2k-1. So we have incoming guests labeled guest 1, guest 3, guest 5... etc.

At time 0, take the guest in room 1 and move them to room 2, the guest in room 2 and move them to room 4, the guest in room 4 and move them to room 8, etc. Then put guest 1 in room 1.

At time t/2, take the guest in room 3 and move them to room 6, then the guest in room 6 moves to room 12, the guest in room 12 moves to room 24, etc.

At each step k, taking place at time 1-t/(2^(k-1)), let n=2k-1. Then take every guest in room n(2^(i-1)) and move them to room n(2^(i)), for all i in N. Then put incoming guest n in room n.


As you can see, at time t this ends up with the exact same result as the original solution to the Hilbert Hotel paradox. Each guest currently in the hotel is moved to a room with double the number they had before, and each incoming guest moves into an odd numbered room.

However, if we change the task ever so slightly:

Strategy B:
Spoiler:
Take all incoming guests and label them with the natural numbers n. So we have incoming guests labeled guest 1, guest 2, guest 3, ... etc.

At time 0, take the guest in room 1 and move them to room 2, the guest in room 2 and move them to room 4, etc. Then put guest 1 in room 1.

At time t/2, take the guest in room 2 and move them to room 4, then the guest in room 4 and move them to room 8, etc. Then put guest 2 in room 2.

At each step n, taking place at time 1-t/(2^(n-1)), take every guest in room n(2^(i-1) and move them to room n(2^(i)), for all i in N. Then put incoming guest n in room n.


In this case, at each step the hotel looks exactly the same (every room is filled), and the group of guests remaining outside remains exactly the same. However, the path followed by each original guest looks very very different. The guest initially in room 1 moves to room 2 at step 1, then moves to room 4 at step 2, then moves to room 8 at step 4, and ultimately moves to room 2^i at step 2^(i-1). And now I can't really say anything about where any original guest is at time t.

Hopefully this helps illustrate why the path of each individual object matters.

-

Also, I read through the paper that you linked, and there are multiple errors that were glaringly obvious to me, especially in sections 3 and 4, including the part you quoted. See:

Spoiler:
From http://www.csc.twu.ca/byl/little.fin.doc

First, the subtraction of one infinite set from another does not necessarily lead to a null result: it depends on the details of the operations.


It does if both sets are identical. N-N = 0. See the discussion after this spoiler.

However, the super-task as posed is completed when the last ball enters the urn, not when it exits. At noon balls numbered 1 to ω have been removed but the urn still contains balls numbered from ω+1 to 10ω.


There is no "last ball" to enter the urn. There is also no ball numbered ω, ω+1, 10ω, or anything involving omega at all. The balls we are operating with are strictly defined.

It would seem that the balls left in the second urn at noon are precisely those that never exited the urn in the first super-task.


The balls left in the second urn have labels that do not match any label that ever exited the urn in the first super-task. However, since the balls that exited the urn in the first super-task are labeled with all of the natural numbers, the balls left in this super-task must have labels that are not natural numbers. Such labels never even exist in the original super-task, so how can they be in the jug?

Alternatively, one could argue that the set of natural numbers is of cardinality Aleph0, encompassing 1,2,3,...ω.


You can't just treat a set with cardinality Aleph0 as though it were finite. There is no number omega as the largest number in the natural numbers.

On the last action, just before noon, the last number to be removed from the urn is ω. Thus the lowest number in the urn is the next number, ω+1.

One might ask, how can there be a next number ω+1 if ω is the largest natural number? The answer lies in the fact that an infinite set, unlike finite sets, can be partitioned into two or more subsets each having the same cardinality as the original set. Consequently, the subtraction of an infinite subset from an infinite set of the same cardinality does not necessarily leave one with the null set.


Emphasis mine. The emphasized part is true (see the discussion after this spoiler). However, taking it to then conclude that the lowest number in the urn is omega+1 is a sort of magic trick by applying the rules of a set with cardinality Aleph0 to a set with cardinality Aleph0 while also treating it like a finite set. If it has cardinality Aleph0, there is no "last number" to be removed, so saying that the ball numbered omega is the "last number to be removed" is nonsense even if there were a ball labeled omega to begin with. THIS is the sort of thing that leads you to conclusions like 1 = 2, not what I'm arguing for.

Another approach is to consider the actions making up the super-task to be members of an infinite series:


And finally, this whole section is an exercise in conflating two different types of mathematics. Sets of distinct objects can't be treated like numbers. The series 1 - 1 + 2 - 2 + 3 - 3 + ... is divergent because 2 is not a distinct object from 1, especially when talking about the sum operator since 2 = 1 + 1. But the set {2} is not the same as the set {1}∪{1}. Also, you can't merely add and subtract infinities, but you can subtract infinite sets:

let N = {1, 2, 3, ...}, A = {1, 2, 3}, E = {2, 4, 6, 8, ...}, and O = {1, 3, 5, 7, ...}. Then
N - A = {4, 5, 6, ...},
N - (N - A) = A,
N - E = O,
O - A = {5, 7, 9, ...}.
N - (O - A) = {1, 2, 3, 4}

These are things that you can do with infinite sets, but obviously you can't do the same with ∞: ∞ - (∞ - 3) != 3.

In the reference text Littlewood's Miscellany, Littlewood makes the distinction that the series is a sum of points p1, p2, etc., which is completely ignored (or misunderstood) by Byl.


Now, the promised discussion: You say that in the given variant, you still end up with N-N, but I disagree.

First, I did a bit of a handwave as part of the proof, that I do not feel is at all destructive of the integrity of the proof: I considered the set of balls labeled n to be equivalent to the set of natural numbers, and I think that such a consideration is fine in the first variant. At the beginning, you assign to each object a natural number, and since throughout the game that assignment never changes, you can consider the sets equivalent. However, any time you introduce a change in that assignment, your objects take on a nature that loses that equivalency.

To be a bit more thorough, each ball can be considered a set {as: as = the label on the ball at step s.}. So then the ball labeled 1 is {1, 1, 1, ...}, ball 2 is {2, 2, 2, ...} and so on. The set of all balls, then, is a set {{1, ...}, {2, ...}, {3, ...}, ...}. Now, you can call this set Nb and replace the N in my previous proof with Nb.

In the variant you put forth from Byl's paper, the set assigned to the ball labeled 1 changes. Let's say that after balls 1-9 are placed in jug A, and ball 10 is placed in jug B, then ball 1 and ball 10 switch labels. You repeat this, switching the label on the lowest ball in jug A with the label on the highest ball in jug B. Then the set associated with ball 1 becomes {1, 10, 10, ..., 100, 100, ..., 1000, 1000, ..., ...} and the set associated with ball 10 is {10, 1, 1, 1, ...}. As you can see, performing the same operations as in the proof, you do not end up with Nb in either jug at the end. What you do end up with is, for each set {bkm} in B and each set {nkm}, there exists a number m0 such that bkm = nkm for all m > m0. And each set in A is defined as akm = k(10)^i for 10^i <= m < 10^(i+1). Those sets have (I believe) the same cardinality, but are not the same set, so you need to do closer inspection to see what B - A is. In this case, since none of the elements in A are in B, B - A is still B.

You could simplify this further and just notice that the jug A does not have any balls that share a label with any ball in B, so B - A is still B.

However, in the initial variant, the set Nb is both placed in the jug and removed from the jug; so Nb - Nb is equal to the null set. And that's the major thing that Byl got wrong, is that showing that the difference between two sets of the same cardinality can be anything does not mean that the difference between two defined sets can. Subtracting one infinite set from another may not always yield the null set, but subtracting one infinite set from itself does. For example, N - {1, 2, 3} still has cardinality aleph0, but if you find N - (N - A), you get the set {1, 2, 3} which has cardinality 3. As I said before, you can do things with infinite sets that you can't do with infinity.

---

ucim, since I agree with you that there is no step omega, is there any other issue you have with the solution that the jug is empty? I've said multiple times that there is no step omega and that the solution does not require such a step. And I've articulated what I believe mward's intention was with referencing step omega. So at this point I'm not sure what you're disagreeing with.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby PeteP » Tue Nov 01, 2016 10:42 am UTC

Okay, I accept that set theory gives the result, I still consider the result nonsense and the puzzle does not demand that I use set theory. Thus I see no reason to accept it as the result of the problem. Obviously arguing with someone who does not accept the application of the relevant math would just be pointless and annoying so I will leave it at that. (My personal answer is: It is impossible and as such there does not have to exist a clear answer.)

User avatar
Shufflepants
Posts: 19
Joined: Wed Jul 20, 2016 3:12 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Shufflepants » Tue Nov 01, 2016 4:02 pm UTC

Xias wrote:
You're right: both of those questions can be asked. The answer to both is, easily, "there is no such step." If there were a last step, then there would be a ball that is the last ball removed. However, there is no last step. The difference between my question and yours is that my question points out a consequence of your solution to the puzzle - one that is contradictory to the rules of the puzzle. Your question doesn't contradict anything because it's asking about something that I don't claim exists. There is no last ball removed. There is no last step. There is no ball left in the jug.

In fact, asserting that there is a last ball removed is exactly where your intuition is failing you. There cannot be a last ball removed because that is contradictory: Let t be the time when the last ball n is removed. Then at t/2, ten balls are added and ball n+1 is removed. So n is not the last ball removed.

The solution can be proved in the same way: If the jug has any balls in it, then there is some natural number m such that the ball labeled m was never removed. However, the rules dictate that for every natural number n, ball n is removed at step n. Then ball m is removed at step m, which is a contradiction. No such ball can exist.

On the other hand, when I ask you what ball is removed at step ω/10, I'm asking because you claimed that there was such a step. So while I'll happily respond to your question with "There is no last step" and remain consistent with my solution, if you want to respond "there is no step ω/10" then it undermines the solution that you suggested. And rightfully so, since your solution is inconsistent with the rules of the puzzle, and is therefore not correct.

The given solution is logically airtight, and its only flaw is that it goes against intuition. That's fine. Intuition regarding infinities and supertasks is often wrong, because there is no reason for us to develop intuition for things that can't actually exist in real life. The infinite geometric sum of (1/2)n from n=1 to infinity is equal to 1. The entire field of calculus involves using limits to circumvent the problem of dividing by zero. 0.99... = 1.

If your approach to such problems is to throw your hands up because you refuse to accept the rules of the game, then why are you even playing?


Keep in mind that when I suggested a step ω/10, I was talking about the surreal numbers not the natural numbers. I frankly don't know how to do limits in the surreals where ω is a number, but I had hoped some one else could make it more rigorous.

The reason I act as though you pre-suppose a last step is if you accept the premise is that the problem statement seems to hand-wave over what I consider to be a non-trivial assumption. I see no issue with other statements like "there is no last integer" when we're not talking about reaching the end. But the problem statement supposes that after a finite time we have reached the end. And it is problematic in a way that I don't think is comparable to other problems like Achilles and the Tortoise. Because with Achilles, there is a definite time that we can point to where his distance traveled has exactly matched the Tortoise and we can point to the exact distance i.e. the last distance mark in the infinite series of real valued distances traveled. From what I understand about making dealing with reaching infinities (such as those involved in infinite sums) rigorous, they must be reached via limits. But the answer that the jug is empty seems to come without such a limit and would seem to me to have more in common with the sort of methods used to show 1 + 2 + 3 + ... = -1/12.

For any one claiming to have an unambiguous solution without contradiction, I would propose that no solution is contradiction free unless all limits involved are similarly contradiction free. The limit of the number of balls in the jug at step n as n goes to infinity should be equal to your proposed answer.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Demki » Tue Nov 01, 2016 5:11 pm UTC

The problem with limits to infinity is that they often don't conserve some of the structure, for example is the famous 'proof' that pi=4, by taking a square and in each step cutting rectangular chunks out of it so that the pointwise limit is a circle, yet in every step along the way we have a shape with perimeter 4. Similarily the structure of cardinality isn't coserved in the limit. And we can show that there is no ball in the jug.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Tue Nov 01, 2016 5:46 pm UTC

Shufflepants wrote:Keep in mind that when I suggested a step ω/10, I was talking about the surreal numbers not the natural numbers. I frankly don't know how to do limits in the surreals where ω is a number, but I had hoped some one else could make it more rigorous.


I don't believe that the surreal numbers allow for a ω/10. I could be wrong though as I am only slightly familiar with the surreal numbers. That being said, we only have balls labeled with natural numbers and we only have steps defined for natural numbers, so I feel like using surreal numbers to find new balls or steps outside of the naturals is breaking more rules than someone who thinks we can't have an empty jar should be comfortable with.

Shufflepants wrote:he reason I act as though you pre-suppose a last step is if you accept the premise is that the problem statement seems to hand-wave over what I consider to be a non-trivial assumption. I see no issue with other statements like "there is no last integer" when we're not talking about reaching the end. But the problem statement supposes that after a finite time we have reached the end. And it is problematic in a way that I don't think is comparable to other problems like Achilles and the Tortoise. Because with Achilles, there is a definite time that we can point to where his distance traveled has exactly matched the Tortoise and we can point to the exact distance i.e. the last distance mark in the infinite series of real valued distances traveled.


I contend that in this case there is a definite time that we can point to (midnight) where the balls removed exactly match the balls put in (one for each natural number).

Do you agree that if, at every step n, we placed ball n in the jug and removed nothing, that at midnight we would have no balls left outside of the jug and infinite balls left in the jug?

Shufflepants wrote:From what I understand about making dealing with reaching infinities (such as those involved in infinite sums) rigorous, they must be reached via limits. But the answer that the jug is empty seems to come without such a limit and would seem to me to have more in common with the sort of methods used to show 1 + 2 + 3 + ... = -1/12.


You seem to be treating that equality as some sort of joke. There are many rigorous and consistent methods used to find the sum of that series, and the sum has applications in real life. If anything, that equality is evidence that limits are not the be-all-end-all of infinity. The sequence is divergent, the series is divergent, and yet it has a sum.

Shufflepants wrote:For any one claiming to have an unambiguous solution without contradiction, I would propose that no solution is contradiction free unless all limits involved are similarly contradiction free. The limit of the number of balls in the jug at step n as n goes to infinity should be equal to your proposed answer.


A few posts ago I used sets to demonstrate how the solution uses limits:

Xias wrote:It is the discrete nature of the problem - that we are talking about individual, well-defined objects and how they behave - that differentiates this from a mere limit of a function. This is more like a limit of the union of sets:

Let α1 = {1}, α2 = {2}, and so on; αn = {n}.

Let β1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, β2 = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, and so on: βn = ∪i=0→9{10n-i}

Then let
Ak = ∪i=1→kαi
Bk = ∪i=1→kβi

Then
limk→∞Ak = limk→∞Bk = N

Furthermore, Ak and Bk can be indexed, so that the nth term of Ak is n, and the same for Bk.

Now, it's clear that Ak⊂Bk for all k∈N. It's also clear that

|Bk\Ak| < |Bk+1\Ak+1| k∈N.

However, once you take k to infinity, the symmetric difference of A and B is the null set. The relative complement of A in B is the null set. |B \ A| is zero. Formally, if C is the set of all balls remaining at midnight:

C = ∪i=1→∞βi - ∪i=1→∞αi = N - N = 0.

Again, this all only works because we are working with sets of objects (balls in the jug at each step) rather than typical functions and limits.


To contextualize this for your particular concerns, note that if you take any pair of sets αi and αj, and take their intersection, you get the null set. The same goes for any pair of sets βk and βl. Thus, the cardinality of Bk\Ak is 9k for all k in N. So if you merely take a function where f(k) is the cardinality of Bk\Ak, and take the limit as k approaches infinity, you end up with limk→∞f(k)=∞. But, if you take the limit of Bk\Ak as k approaches infinity, you get the null set. So the limit of the cardinality is infinity, but the cardinality of the limit is 0.

That is the issue, is that you are thinking of the limit of the cardinality, but the cardinality doesn't say anything about what goes on within the set, so the limit of the cardinality is worthless. Actually, the set is what dictates the cardinality, so you have to examine what happens to the set as k approaches infinity, which is that it becomes the null set. It is analogous to limx→kf(x) ≠ f(limx→kx). You may be familiar with cases like this: consider f(x) = x/x as x approaches 0.

Demki wrote:The problem with limits to infinity is that they often don't conserve some of the structure, for example is the famous 'proof' that pi=4, by taking a square and in each step cutting rectangular chunks out of it so that the pointwise limit is a circle, yet in every step along the way we have a shape with perimeter 4. Similarily the structure of cardinality isn't coserved in the limit. And we can show that there is no ball in the jug.


This is such an elegant example of what I'm talking about.

User avatar
ucim
Posts: 6888
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Infinite Balls and Jugs [solution]

Postby ucim » Tue Nov 01, 2016 11:02 pm UTC

Xias wrote:The [ -> -1/12 ] sequence is divergent, the series is divergent, and yet it has a sum.
No, it doesn't. Not really. A different function evaluates to -1/12 with certain parameters that reduce it in a limited range to the series in question. But that's a different function.

It so happens that the "different function" is also unique, inasmuch as it's the only function that reduces to the series. This is pretty cool. However, it is a mistake to think of it as a sum, since the actual series is divergent at the chosen parameter.

It makes a nice parlor game, but the reality is it abuses the notion of "sum".

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby PeteP » Thu Nov 03, 2016 11:43 am UTC

Ignore this:
Spoiler:
<rant>About the notion that it leads to an interesting counter intuitive result: The mathematical side is pretty much analogous to proving that rational numbers are countable, the version are in which order you count them and if you pick one that works you get a bijection and that is of course rather easy to do from N to N. Nothing new about it. Adding them faster than you are removing/labeling them instead of just starting with infinitely many of them only highlights that it is an endless task but doesn't really change anything.

The thing which causes discussion is the validity of its premise: If you accept that the task can have an after it is finished then sure it follows that every ball has been removed since it involved removing every ball. If you said "After Sisyphus finishes his task is the rock anywhere on the mountain beside its top." then accepting the premise the answer is no otherwise the task wouldn't be finished. The stone might be on the top, it might not exist anymore, maybe the mountain disappeared, maybe existence ended. The questionable thing is him finishing an unfinishable task. (Well it is a mythological story so it is not unfinishable in its origin, but if you state the ball always rolls down thing as part of the premise and forbid him tricking some god or getting forgiven or wearing down the mountain as solution, etc. then it is.) There is nothing particularly interesting in that result. Making the statement of "what if the endless task ended" indirectly by declaring your are halving the time each iteration to create an endpoint and making the statement that the action that ended was removing every ball by using the label and the right order does makes it more convulted but that does not automatically make the result more interesting. (I suppose there could be something interesting in the premise itself of finishing an endless task but that would be part of any super task.) Similarly you can generate countless conclusion from asserting a contradiction, without getting anything interesting (garbage in, garbage out).

(I don't think parallels to Zeno's paradox demonstrate that it makes sense to talk about an after. With Zeno's paradox both time needed and distance to travel can be summed to single finite number, here only the time can. Though I would probably accept a premise that involves moving infinitely many objects at once (when phrased as transferring the content from object a to object b), which as a process should also be endless so I guess rejecting one premise without the other would be inconsistent.) (The puzzle has a second premise which is probably the one that bothers me more: It describes a physical task and postulates that describing it differently (assigning labels to the balls is a description) influences the outcome. I guess you can say declaring a specific order of removal is changing the physical progress.) (I suppose I should just accept the premise, but "if impossible thing is done then you can draw weird conclusion from impossible thing being true" still isn't an interesting result.)

So I think I got my (admittedly not very rational) strong dislike for super tasks out of my system for now. Self indulgent intellectual masturbation… </rant>

User avatar
ucim
Posts: 6888
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Infinite Balls and Jugs [solution]

Postby ucim » Thu Nov 03, 2016 5:20 pm UTC

Seems to me that the idea of a discontinuity is most apt here. We're used to mathematical functions (such as 1/sin x) which have discontinuities (e.g. at zero), so that naively taking the limit does not give you a consistent answer. Others (such as x/sin x) don't have an answer at zero, but a value can be defined for it that preserves continuity. Yet others (the divergent series that "sums" to -1/12) can have a (unique!) value defined that while nonsensical, preserves a higher-order continuity. The original series is still divergent, so the two functions are not the same, but they mesh together. Something similar happens with the perimeter of a square that becomes a circle after continuously taking the corners away.

In my mind, a supertask like the one we're discussing, has the same thing embedded in it - a discontinuity at t=0 (which reflects the discontinuity between the natural numbers and the surreal numbers) "at which" the task gets finished (or the "function" is evaluated). We are led to naively follow the continuous part of the function down the rabbit hole, and there (surprise!) is a discontinuity which we are not used to.

Nonetheless, it is there. "Everything happens" at that "point", analogous to the way that 1/sin x "goes from infinity to -infinity" "at" zero.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

User avatar
Shufflepants
Posts: 19
Joined: Wed Jul 20, 2016 3:12 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Shufflepants » Thu Nov 03, 2016 6:57 pm UTC

I did some more reading about the surreals. They contain the integers and the reals within them, but they aren't a set, they are a proper class. And because of how they are recursively defined, even though they contain the reals and the reals are Dedekind Complete, the surreals are not and they have an infinite number of gaps. And limits in the surreals can be equal to one of these gaps (rather than an actual number). One such interesting gap is between 0 and all positive numbers, and another gap between 0 and all negative numbers. And indeed there exists a gap between every two numbers, so under the usual topology assigned to the reals, the surreals are completely disconnected. You can, however, define a different topology for the surreals which makes them connected and allows you to consistently define various things such as continuity and prove the intermediate value theorem, but all the definitions have to be slightly modified.

Another thing: even though in the surreals, the definition of ω = {1,2,3,...|}, that is the first (by birthday) number that is recursively defined that is bigger than all integers, ω != ∞. Where ∞ is the infinity of the reals and integers, i.e. the usual limit of infinite sequence 1,2,3,...; ∞ in the surreals actually corresponds to a gap that sits between all positive finite numbers and all the positive infinite numbers.

Because of this, while we can use numbers like ω/10 and consistently say that ω/10 < ω, and we can use ω+1 and consistently show that it is equal to (ω-1) + 2; these numbers won't come to our rescue for this problem since our number line would look like [positive integers](a gap, namely ∞)[positive infinite numbers less than ω]. And it would still seem that at no step would we be grabbing balls with labels beyond the gap of ∞, nor would it let us name the "last step".

User avatar
kryptonaut
Posts: 79
Joined: Mon Nov 07, 2016 4:06 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby kryptonaut » Mon Nov 07, 2016 4:37 pm UTC

It seems to me that after N steps there will be 9N balls in the jug, numbered from (N+1) to 10N inclusive, in case (a).

As midnight approaches and N->infinity, the number of balls will approach infinity, as will the lowest (and highest) number.

After midnight, if you're prepared to contemplate a jug containing an infinite number of balls then it's just as meaningful to imagine that the lowest number on any ball is also infinite.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Infinite Balls and Jugs [solution]

Postby Xias » Tue Nov 08, 2016 1:30 pm UTC

kryptonaut wrote:It seems to me that after N steps there will be 9N balls in the jug, numbered from (N+1) to 10N inclusive, in case (a).

As midnight approaches and N->infinity, the number of balls will approach infinity, as will the lowest (and highest) number.

After midnight, if you're prepared to contemplate a jug containing an infinite number of balls then it's just as meaningful to imagine that the lowest number on any ball is also infinite.


Where did those balls with infinite numbers on them come from?

User avatar
kryptonaut
Posts: 79
Joined: Mon Nov 07, 2016 4:06 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby kryptonaut » Wed Nov 09, 2016 4:21 pm UTC

Xias wrote:Where did those balls with infinite numbers on them come from?


They were put in during the infinite number of infinitesimally short steps that happened on the stroke of midnight.

The thrust of the argument for the jug ending up empty is to say that for any ball number N there is a particular time when that ball is removed from the jug, therefore no ball is left. My argument is that for any ball number N that is removed, there are always 9N balls with higher numbers left in the jug, therefore there are always balls in the jug.

How many steps had been taken when midnight arrived? That number plus one will tell you the number on the lowest-numbered ball.

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Infinite Balls and Jugs [solution]

Postby phlip » Wed Nov 09, 2016 11:39 pm UTC

kryptonaut wrote:
They were put in during the infinite number of infinitesimally short steps that happened on the stroke of midnight.

"During" a number of steps? Be specific. At what specific time was this ball:
kryptonaut wrote:
How many steps had been taken when midnight arrived? That number plus one will tell you the number on the lowest-numbered ball.
put into the jug?

If that ball wasn't added to the jug at any particular time, then how did it get there?

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
kryptonaut
Posts: 79
Joined: Mon Nov 07, 2016 4:06 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby kryptonaut » Thu Nov 10, 2016 10:18 am UTC

phlip wrote:At what specific time was this ball:
kryptonaut wrote:
How many steps had been taken when midnight arrived? That number plus one will tell you the number on the lowest-numbered ball.
put into the jug?

If that ball wasn't added to the jug at any particular time, then how did it get there?


It, and the infinite other balls were put in at the stroke of midnight. Calculating the number on it is left as an exercise for the reader.

If you are prepared to consider an infinite number of steps having been performed by midnight, then you also need to accept an infinite number of infinitely-numbered balls being in the jug as a logical conclusion. If you deem that conclusion to be non-realistic then so is the original question.

What if the steps were all taken at intervals of one second - the task then becomes to determine how many balls are in the jug at the end of time. Does that make the meaninglessness more apparent?

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Infinite Balls and Jugs [solution]

Postby phlip » Thu Nov 10, 2016 11:22 am UTC

kryptonaut wrote:
It, and the infinite other balls were put in at the stroke of midnight.

Why would you assume such a thing, when the puzzle pretty explicitly only describes us doing things strictly before midnight? At midnight, we're doing nothing except checking to see what's left in the jug.

kryptonaut wrote:If you are prepared to consider an infinite number of steps having been performed by midnight, then you also need to accept an infinite number of infinitely-numbered balls being in the jug as a logical conclusion.

But why? That there we are considering an infinite number of balls does not somehow imply that some of the balls magically have infinite numbers written on them.

There are an infinite number of naturals, but each one individually is a finite number.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests