Actually, isn’t that just the best-known upper bound for Graham’s number?
IIRC, the best-known lower bound on Graham’s number is 6.
They’re both non-trivial, but not tight.
But the very same reasoning argues that the number of chips in the first case (with largest chip removed each time) is zero, because the very simple argument given by several posters in this thread shows that the dish is empty in the second case.
Therefore, since your reasoning gives two different contradictory conclusions depending on what facts you apply it to, you must conclude that this reasoning is fallacious, and abandon it, however attractive it may seem. In particular, you have to abandon the notion that “chips in & chips out” determines the total amount remaining in the end when both “chips in” and “chips out” are infinite. That this reasoning fails is just another peciliarity of infinite sets, such as the fact that an infinite set can be put in one-to-one corresponce with a proper subset of itself.
This is why one has to be careful when applying to infinite cases reasoning that works well in finite cases. It is an at-first-unintuitive fact that some infinite sums can take different values when the terms are rearranged. For example:
1 + (-1 + 1) + (-1 + 1) + (-1 + 1) + . . .
= 1 + 0 + 0 + 0 + . . .
= 1,
even though, just shifting the parentheses over, we can get
(1 - 1) + (1 - 1) + (1 - 1) + . . .
= 0 + 0 + 0 + . . .
= 0.
knock knock, analyzing at each step how many chips are put in, versus how many are taken out, in order to deterine how many chips are left in the box, actually works, but only at the finite level; things get counter intuitive once we bump it up to infinity.
For example, I start with an empty box, I put m chips in the box, then take out n chips (assuming n <= m, both nonnegative integers). How many chips are left in the box? Obviously m-n chips; there’s no denying that.
However, in the examples we’re looking at, over time, infinitely many chips were put in, and infinitely many were taken out. With this information how can you determine how many chips are left in the box when the whole process is over? The answer is simple–you can’t. You need specific information about which chips were put in and which chips were taken out.
Now, thinking of the chips as positive integers again, what if I put all the chips in, and only take out the evens? Then infinitely many chips are left in the box.
What if I put all the chips in, and take all of them out? Clearly none are left in the box.
Now put all of them in, and take out the ones greater than 10. Obviously only 10 are left in the box.
In each case, infinitely many chips were put in, infinitely many were taken out, but the number left in the box is different each time. That’s exactly the problem with what’s happening in our two examples–in both cases, infinitely many are put in, infinitely many are taken out, but in the first case, infinitely many are left in the box, while in the second case, none are left.
At the risk of flogging the greasy spot on the pavement where the dead horse used to be, let me weigh in on this one more time. I still say that in the second case, the number of chips in the bowl grows without limit. It seems to me that the whole catch to this paradox is the underlying assumption that the process can be completed in a finite time - 2 hours, 2 seconds, whatever. The form of Zeno’s paradox to which owlofcreamcheese seems to refer to is the one in which he argues that when a ball is thrown at a wall (say 2 meters away) it can never reach the wall because first it must travel 1/2 way there, the 1/2 the remaining distance, then 1/2 of the remaining remaining distance, and so on. However, legend has it that when Zeno stood in front of the wall and dared all comers to try to hit him he was forced to call off the demonstration due to the nosebleed he got when the first nay-sayer nailed him. Clearly, even though the ball must cross an infinite number of ever shorter distances, the total distance is finite.
And Cabbage, I’ll name one just as soon as you name the largest integer!
knock knock, how would you analyze the following two scenarios:
(In both cases, we’re using the same division of the two hours into steps as we’ve been doing throughout the thread).
-
First step, God throws the number 1 in the box. Second step, God throws the number 2 in the box, and then removes the largest number from the box (2 at this stage). At each of the remaining steps, God always throws the next number in the box (3,4,5,…), then removes the largest number from the box.
-
First step, God throws the number 1 in the box. Second step, God throws the number 2 in the box, and then removes the smallest number from the box (1 at this stage). At each of the remaining steps, God always throws the next number in the box (3,4,5,…), then removes the smallest number from the box.
How many numbers are left in the box after the completion of the steps in case 1? Case 2? Be sure to note that both cases are exactly the same in the sense you’ve mentioned above–in both cases, God simply throws a chip in on the first step. And, again in both cases, for each of the following steps, he adds a chip, then removes a chip. By your reasoning, therefore, both boxes should wind up with the same number of chips when all is said and done. Is this so in these two cases?
moes lotion, what you’ve posted seems to have everything to do with the way we’ve divided up the two hours, but nothing to do with how many chips are left in the box.
Ah…proof by intimidation. 
OK,
Step 1: God puts chip #1 in the bowl.
Step 2: God puts chip #2 in the bowl.
Step 3: God takes chip #1 out of the bowl.
Elapsed time, one hour, chip #2 is in the bowl.
Step 4: Chip #3 in.
Step 5: Chip #4 in.
Step 6: Chip #2 out.
Elapsed time, one hour and thirty minutes, Chips #3 and #4 are in the bowl.
Is there a rule that says that at two hours, after an infinite number of iterations that God must have completed some number of steps that is exactly divisible by three? Why?
OK, we ask God to do each set of three steps as a single operation in a finite, but always decreasing time interval, even dividing intervals less than the Planck interval, and approaching two hours as a limit.
In His infinite wisdom, and mercy, God does as we ask. (I certainly wouldn’t.)
So, there are always 2n - n chips in the bowl. At the end of the time period whose limit is defined by the function for speed, that number n will be infinite, but will be a member of the set of natural numbers. The answer is there are n chips in the bowl, and the value of n is infinite. The least value in the bowl, is the chip numbered n. There is no finite answer for the value of n, and no finite number on any of the chips in the bowl. All of the chips in the bowl will have values inscribed on them, which are infinite integers. We cannot name them, but that is not a problem for God. We were the ones who asked Him to do this silly experiment.
So, asking for the name of an infinite integer is no less silly if you ask God to do it, than it is if you ask some mathematician.
Tris
Oops, the smallest value would be n + 1, not n.
Sheesh. Off by one errors, at infinite magnitutes.
Tris
Actually, I guess I should respond to this, rather than just dismiss it, as I did above; I don’t know whether the quote was meant facetiously or not.
The difference here is that I never claimed there is a largest integer; in fact, I’ll go on record here and state that there is no largest integer. Why ask me to name something when I deny its existence?
On the other hand, you do, in fact, claim there is a number in the box (infinitely many of them, in fact). It’s perfectly reasonable for me to ask you to name one of them if you claim that such a thing exists. If, for whatever reason, you claim to not be able to name one, yet still maintain that such a thing exists, then give me an argument on how this can be so. Why can’t you name one?
Triskadecamus, sure, at each step, there are 2n - n chips in the box. But that only works so long as only finitely many steps have been completed. Give me some justification that you can use similar logic to deduce how many chips are left after infinitely many steps have been concluded.
Consider this–say we start with a box already full of all the positive integers (and only the positive intgers). At each step, I remove the smallest one, leaving infinitely many. How many are left at the end of the two hours now? Again, it should be clear that none are left (if any are left, consider the smallest one left–ah, but it would have been removed in the step immediately following when its predecessor was removed–Contradicting the assumption that it was left), even though at every individual step, infinitely many are in the box.
Now if you buy that argument, do you see that it must necessarily imply that no chips are left in the original example (where God removes the smallest chip at each step, after throwing two chips in). In the original example, God is putting all of the positive integers in (and only the positive integers) two at a time. Now, in my newest example, I’m saying the hell with it, just throw them all in there to begin with (but do everything else the same). Now remove them one at a time–removing the smallest one at each step. There won’t be any left–I’ve removed them all, dammit! And neither can there be any left in the original example.
Nothing good to add, but when I first read about this paradox, it was explained by the sentence, “We have no mathematics to describe the completion of infinite tasks.” I suppose it’s rather like saying, “Count 1, 2, 3,… What number do you finish on?” The fact that it takes a finite time changes nothing.
Cardinalities of infinities are represented by the Hebrew letter aleph. (I’d include the letter, but I don’t know how to hamsterize the VB code to do so.) The set of integers, the “countable” infinity, is aleph[sub]0[/sub]; the set of reals is aleph[sub]1[/sub]; the set of (I think) curves is aleph[sub]2[/sub].
I learned this from One, Two, Three… Infinity, which only went that far on infinities. Conceptually, there would be an infinite number of infinities, but my mind seg faults on the idea of aleph[sub]2[/sub]. Professional mathematicians are welcome to discuss higher order infinities.
Perhaps this will help: God has a bowl with zero chips in it, and puts in (-2) more. How many are in the bowl now? Well, -2, of course. But how do you put -2 chips in? What the hell are negative chips? Of course there is no such thing, and doing so is imposible. This is why we assigned the action to God in the first place: he is a being by definition capable of doing the impossible. So he is going to be the one to put infinitely many chips in and take infinitely many out in two hours, because doing so is obviously, blatantly impossible. We are not surprised that regular addition of positive integers doesn’t help when God puts in -2 chips; likewise we should not be surprised when finite arithmetic doesn’t tell us what happens when infinitely many chips are added and removed. And we also shouldn’t be surprised when our common sense gives the wrong answer in such unfamiliar cases. If we accept that God is doing the impossible, then we must accept that there are -2 chips in the bowl in my example, or zero chips in the bowl in the OP’s example.
Suppose each chip has a different thickness. In particular, suppose the thickness of chip k is 1/k. God, with His infinite sense of aesthetics, doesn’t just toss the chips into the dish. He stacks them up. The height of the stack after step N is Sum [k = 1 to N] {1/(2k-1) + 1/(2k )- 1/k }. After 2 hours, the height of the stack would be Sum [k = 1 to infinity] {1/(2k-1) + 1/(2k) - 1/k } = Sum [k = 1 to infinity] {1/(2k(2*k-1)) } This sum converges to a finite number greater than zero, call it S. Are we now saying this sum does not equal S?
I have a difficulty reconciling a stack of height greater than zero, made up of zero chips. I also have a difficulty believing that Sum [k = 1 to infinity] {1/(2k(2*k-1)) } approaches S, but is in fact equal to zero. I would not have a problem if the number of chips were taken to be undefined or indeterminate, but no one seems to be arguing that.
Note that I get reasonable answers to the height of the stack for both of these scenarios from cabbage:
The height of the stack for the first case approaches 1, the height of the stack for the second case approaches zero.
Scuba_Ben
That’s the common “continuum hypothesis” mistake. True, the set of integers is aleph0. The set of reals is bigger than aleph0, but it may also be much bigger than aleph1, as well. I’m not sure what you mean by curves, but I figure either the set of functions from the reals to the reals, in which case that would certainly be a set bigger than the reals, and not necessarily aleph2. I’m not sure off hand if the set of continuous functions from the reals to the reals is strictly larger than the reals, but it can still certainly be much bigger than aleph2, as well (since the reals can be much bigger than aleph2).
ZenBeam, you’re making the same mistake I accused knock knock of making when I posted after your earlier post–you’re assuming a continuity that isn’t there. Your sum is meaningful so long as there are finitely many chips in the box, but you haven’t demonstrated that it still has any meaning when we take it to the infinite level.
Consider this classic example: I don’t want to get bogged down in the notation and algebra, so I’ll simply describe the following sequence of functions.
The nth function f[sub]n[/sub] (n=1,2,3,…) mapping the interval [0,1) is described as follows. It’s zero from x=0 until we get to the point x= 1 - 1/n, at which point it takes off in a straight line up to the point (1, 2n[sup]2[/sup]).
So, in general, the function f[sub]n[/sub] looks flat for a considerable length, then suddenly shoots up steeply. What is the integral (area under the curve) of f[sub]n[/sub]? Well, it gets no area for the flat part; when it shoots up steeply it forms a triangle with base 1/n and height 2n[sup]2[/sup]. This triangle has area n.
These functions converge pointwise to another function, call it f[sub]inf[/sub]. What is the integral of this function? The integrals of the functions in the sequence are growing without bound, so by your logic, the integral of f[sub]inf[/sub] should be infinite.
However, for any x you pick in [0,1), the sequence f[sub]n/sub converges to zero. So actually, f[sub]inf[/sub] is identically zero on [0,1}, hence the integral of f[sub]inf[/sub] is zero.
Similarly, despite the fact that the chips in the box are growing without bound throughout the two hours, you just can’t rely on limits and convergence to tell you how many chips are in the box at the end of the two hours. What is your assumption that there is any convergence to begin with based on?
Okay, here is my reasoning for saying that the number of chips in the bowl grows without limit - which is equivalent to saying that the bowl is never empty. To re-iterate the process:
step 1 - place chips 1 & 2 in the bowl
step 2 - place chips 3 & 4 in the bowl and remove chip 1
step 3 - place chips 5 & 6 in the bowl and remove chip 2
.
.
step n - place chips 2n - 1 and 2n in the bowl and remove chip n - 1
Note that for each step, the number of chips in the bowl is exactly n + 1.
Now, let n approach infinity. QED
You’re right. After any finite number of steps, the bowl is never empty. That doesn’t mean that it isn’t empty after an infinite number of steps.
They’re the same size. A continuous function from R to R is essentially a function from Q to Q. It’s not hard to show that Q -> Q is the same size as R, but I’d have to work out the details again.
btw, y’all might be interested in this thread I started on large numbers. Chronos’s discussion of Graham’s number got me thinking, and I ran from there…
Except that, as has already been mentioned, any particular finitely numbered chip has already been removed. Pick one. 147? 20045? 999998? They’ve all been removed, and we can tell you exactly at what step. That is, you cannot specify a particular chip that has not been removed.
If all of the finitely-numbered chips have been removed, you’re not really left with much.
I promise that this is my last response to this thread. ultrafilter, lets play the following game of leap frog. You name a chip that’s been removed from the bowl, call it n. Now, on my turn I say fine, when chip n was removed on turn n + 1, chips 2n - 2 and 2n - 1 were put in the bowl, when were they removed? Your turn…
Note: the first one to stop loses.[smileyface]
You’re assuming that this function is continuous at infinity (which is a meaningless phrase to begin with). We can go on forever, but the behavior of this process after any finite number of steps implies nothing about its behavior after an infinite number of steps.