Hour 98724897489498748912375470249072390472907561514745123767912741923742917561907569127423975912750197539274123901925709600749372417709128740987049817091823709178340914701923470123947901234701239470192470129347012394701293470129347012947097568729057091720670934759710947019472390874097808 : Second 98724897489498748912375470249072390472907561514745123767912741923742917561907569127423975912750197539274123901925709600749372417709128740987049817091823709178340914701923470123947901234701239470192470129347012394701293470129347012947097568729057091720670934759710947019472390874097808
Hour 98724897489498748912375470249072390472907561514745123767912741923742917561907569127423975912750197539274123901925709600749372417709128740987049817091823709178340914701923470123947901234701239470192470129347012394701293470129347012947097568729057091720670934759710947019472390874097809 : Second 98724897489498748912375470249072390472907561514745123767912741923742917561907569127423975912750197539274123901925709600749372417709128740987049817091823709178340914701923470123947901234701239470192470129347012394701293470129347012947097568729057091720670934759710947019472390874097809
.
.
.
Now tell me exactly where these will diverge.
ETA: typing times can be longer than other typing times
Boy, I fucked up the coding something awful in my last post. Sorry about that.
Anyway, a link to a previous explanation of Cantor’s first argument for the uncountability of the reals (the only proof which I would say actually deals with the reals as a continuum, and not just as a proxy for countable sequences of bits).
With regard to what KellyCriterion said earlier in the thread:
Some philosophers and mathematicians (starting with Aristotle, I think) distinguish between potential infinity and actual infinity (or uncompleted vs. completed infinity)—see here or here. Some take the point of view that KellyCriterion seems to be expressing here and explicitly reject the use of actual infinities in mathematical arguments, as in Gauss’s (pre-Cantor) remark “I protest against the use of infinite magnitude as something completed, which is never permissible in mathematics.”
When I read these sorts of SDMB threads, I’m tempted to incline to this point of view. It would prevent a lot of confusion and controversy and seeming paradox if we could just say “There isn’t really any such thing as infinity.” But, I’m not willing to be expelled from the Paradise that Cantor has created for us.
Well, it does seem likely that there are no infinite sets in reality: the universe is likely to be finite in extent, be finite in duration, and contain a finite number of fundamental particles. So a set like the set of all the natural numbers is a purely theoretical concept, just as any mathematical concepts which involve infinite cardinal numbers, or infinite divisibility of geometrical constructs, such as a line interval.
So, when we talk about doing things like putting the rational numbers and the natural numbers into a one-to-one correspondence, we are not constructing the whole thing – because a complete construction would not fit into the universe. We are just saying, “Here is a rule for doing it, which can be carried out as far as you like, and which will eventually map any given rational number to a specific natural number, and vice-versa.” Showing that you have a rule that would work, given infinite time, is enough: we don’t have to carry it out.
Ah, yes, I was taking an inappropriate limit, there. Beth_0 to any finite power is beth_0, so the lim(n -> infinity)(beth_0^n) = beth_0, but that does not imply that beth_0^beth_0 = beth_0.
Quoth Thudlow Boink:
This gets back to what Indistinguishable keeps saying about picking the rules of your game. You can play a perfectly valid game of mathematics where there is no such thing as “infinity”. It’s just a different game, is all.
I think you’re right that Kelly Criterion was expressing suspicion concerning actual infinities. The explanation I gave in my posts above is one I designed to be meaningful even to someone who has that suspicion. Even someone who is suspicious of completed infinities still, surely, thinks there’s a meaningful sense in which we could put “all” the integers “in order”. I try to capitalize on that.
I’d love to put it this way but I’m afraid to because I’m afraid that there can be orderings without rules (i.e. no finitely expressable rule could tell you how to construct the list out to arbitrary lengths) and it’s not strong enough to just say that the reals can’t be listed (read: ordered in a way yielding one-to-one correspondence with the integers) according to any rule. The fact is, they simply can’t be listed. You can’t get that concept across if you only talk in terms of rules for list construction.
Sure, except the thing is, all the discussion of actual infinities can be translated into talk of potential infinities, or whatever you want to call it. Saying “The integers and the rationals have the same cardinality” doesn’t have to mean “There’s a big bag out there in the Platonic realm with lots of dots marked with integers in it, all of them, all at once, and another big bag out there with lots of dots marked with rationals in it, all at once, and there’s some ethereal lines between them connecting them in one-to-one correspondence” or whatever. It just means “Here’s a technique you can use which, whenever someone presents you with an integer, produces a rational, and vice versa, in such a way as that going back and forth always ends up where you started”. What was a discussion in terms of actual infinities is rephrased into a discussion in the terminology of potential infinities.
Similarly, “There are more sequences of bits than natural numbers” really ultimately means “If you give me any rule R for turning natural numbers into rules for turning natural numbers into bits, then I can produce from it a rule D for turning natural numbers into bits, such that no matter what natural number A you pick, I can pick a natural number B such that D(B) is not equal to R(A)(B).” And the diagonalization proof is just “If you pick the rule R, then I’ll define the rule D by D(X) = the opposite of R(X)(X); then after you pick the number A, I’ll pick the same number for B, so that D(B) = the opposite of R(B)(B) = the opposite of R(A)(B)”. No need for “actual infinities”, whatever that would mean. Just some game about rules for generating bits.
And no one would object to these kinds of claims once they were all spelt out like this (at least, once they finished parsing them). The only problem is that mathematicians do not always make it clear that this is all what they’re talking about ultimately means. But it is.
There are real cats – a finite number of them, and a number which is changing all the time as cats are born and die. But the “set of all cats” is an abstraction: it’s a way of taking about reality, but a set is not a real thing. You might talk about three specific cats in a specific basket: the cats are real, the basket is real, but the set of the three cats is an abstraction, and is not the same thing as the basket containing the cats.
So, while you could build an infinity of sets containing sets … containing sets containing real objects, a set contains objects in quite a different way from how a basket contains cats. And while you could potentially have an infinite number of sets of sets, none of those sets are real objects.
Putting things solely in terms of “rules” is fine, even in the sense of “rule” as “Something I can express”; you are of course worried about “Well, what about functions which no one knows how to carry out or even express?”. But that’s a misguided worry.
Whether you can express something always depends on what language you are using. You can always, for any function (even if you want to think of functions as pre-existent objects off living in the Platonic realm), imagine a language in which there was a term referring directly to that function. And working solely with the functions expressible in that language, Cantor’s diagonal argument goes through just as fine as in any other language; given any map from N to 2^N expressible in language L, there is a map from N to 2 expressible in language L which is not in its range. Since L is arbitrary, this covers everything you could care to cover.
That having been said, I would argue that we oughtn’t think of functions, or anything else in mathematics, as pre-existent objects off living in the Platonic realm anyway, so there needn’t have been any worry in the first place. But whatever.
Right. There are various kinds of existence and non-existence proofs. One kind of existence proof is saying, “I have a simple rule, and it works for all the natural numbers.”
But (to take another proof about a set having the same cardinal number as the set of natural numbers), there’s a simple rule to find prime numbers:
(1) take each natural number in turn.
(2) count its divisors (including itself and one).
(3) if the number of divisors is two, then you have the next prime number.
However, that simple rule does not prove that there is an infinite number of prime numbers: it might be that at some point you stop finding primes using this algorithm. You need to use a different existence proof to show that there is an infinite number of primes: one which assumes that you have found a finite number, and shows you how to find the next. However, that proof (repeated over and over) might not find all the possible prime numbers. So the simple ordering method is different from the existence proof.
(And the order of primes with the existence proof is 2, 3, 7, 43, 13, 53, 5, … by my calculations)
Similarly, non-existence proofs won’t just assume that you’ve got a simple rule: they will show that any ordering, no matter how arbitrary, will work.
It was not at all clear to me what you meant by this. To save anyone else the mental effort:
You’re referring to the proof of the infinitude of the primes based on the fact that, given any finite set of numbers, there exists a number > 1 coprime to all of them (and thus, any of the prime factors of this number, of which at least one exists, must be outside the original finite set).
If you generate numbers coprime to a set by taking its product and adding 1, and select prime factors by always selecting the lowest prime factor, this becomes an algorithm for taking a finite set and spitting out a prime not within that set. If you then apply this algorithm iteratively, it becomes a way of starting with the empty set and one by one adding new primes to that set. The order in which primes are added to that set on this formalization is, as you say, 2, 3, 7, 43, 13, 53, 5, … . Sure.
But, there are any number of other ways you could present the ideas of the same proof; you could take the least common multiple and add 1, and always select the highest prime factor, for instance. The proof of the infinitude of the primes is already complete well before you decide how to turn it into an algorithm for enumerating an infinite sequence of primes [if indeed you want to do so at all].
The confusing thing to me was that you seemed to refer to a proof of the infinitude of the primes as a particular kind of enumeration of primes. But a proof needn’t provide any particular enumeration anymore than a description of an enumeration provides a proof of any facts about itself. They’re just, you know, different things, proofs and enumerations. I don’t know; I was confused by what you were saying.
Me too. What I’m saying is that putting it in terms of rules for lists, when you’re explaining the concept to the typical interested lay person, is going to trip off circuits in that person’s mind that make him or her think of “nice functions” that are humanly explicable and in that sense have a kind of “Platonic existence” that “not-nice functions” don’t share. Then they might think they’ve understood the argument, when in fact they haven’t. So I’ve been trying to figure out a way to express the argument while avoiding talk in terms of rules for lists. Unfortunately I just end up talking about “ways to order” things and that pretty much trips off the same circuits.
I guess it all just points to the fact that its sometimes no use trying to do an end run around certain misconceptions when explaining certain things…
The thing everyone always leaves out in these talks is that you necessarily take a section out of the infinite set before you can compare them. You then notice that pattern, and notice that it will continue infinite times.
The one to one mapping has to occur with a finite set that is a set proportion from an infinte one. Lets say you take all positive integers less than 100, and compare it with all positive odd integers less than 100. You notice that there is a 1:2 mapping. (1, 1&2), (3, 3&4) (5, 5&6), etc. Therefore, in that set, there are twice as many positive integers as odd positive integers.
Now, it doesn’t matter where you make this arbitrary cutoff. As long as the cuttoff is at the same point, you will have a 1:2 mapping. So that means there are twice as many positive integers as odd positive integers, even thought the sets are infinite.
That doesn’t mean that there is any actual divergence–there can’t be, because the sets are infinite. You could say the divergence is at some part of infinity. Infinite and finite numbers are essentially two different types of numbers, and there’s no direct way to get from one to the other.
OK, for my first subset, I’ll try all of the positive odd integers less than 100. OK, I count that there are 50 positive integers in this set, and 50 positive odd integers. So in this subset, there are one times as many positive integers as positive odd integers. All right, let’s try a different subset: Let’s try it for the subset of all positive odd integers less than 1000. Wow, now there’s 500 positive integers in the set, and 500 positive odd integers in it-- It’s still the same 1:1 mapping! In fact, I can find all sorts of subsets with that 1:1 mapping! There must be exactly one times as many positive integers as there are odd positive integers.
BigT, if you want to talk about asymptotic density of subsets of the naturals, you can. But then you wouldn’t be talking about cardinalities. That’s fine; there’s all kinds of things in the world you might want to talk about. Do you think people who discuss cardinalities are making a mistake in talking about cardinalities rather than talking about asymptotic density? There’s no mistake; they’re just talking about something else. The only mistake would be in conflating the two.
Given infinity is represented here by j… and think in terms of graphically representing j (Cartesian for the heck of it)… How do you visualize j^j^j (ad nauseum)? My thought is an infinite number of spheres within spheres. Math can’t define the cosmos, as it is as incomprehensible as any being who could create it. Think outside the rigors… visualize how the network this construct would appear if you could see it with your eyes… daunting, but it might be quantum in nature, given any number of infinite particles exist simultaneously in an infinite number of probabilities… perhaps?
