= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on The Lifespan Dilemma - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (214)
Sounds like you want measure instead of cardinality. Unfortunately, any subset of the rationals has measure 0, and I'm not pulling your leg either.
I don't even understand the article on measure...
The main takeaway should be that counting, or one-to-one mapping, isn't a complete approach to comparing the "sizes" of infinite sets of numbers. For example, there are obviously as many prime numbers as there are naturals, because the number N may correspond to the Nth prime and vice versa; also see this Wikipedia article. For the same reason there are as many points between 0 and 1 as there are between 0 and 2, so to compare those two intervals we need something more than counting/cardinality. This "something more" is the concept of measure, which takes into account not only how many numbers a set contains, but also where and how they're laid out on the line. Unfortunately I don't know any non-mathematical shortcut to a rigorous understanding of measure; maybe others can help.
You are guaranteed to lose me if you say things like this, especially if you put in "obviously". It's obvious to me (if false, in some freaky math way) that there are more natural numbers than prime numbers. The opposite of this statement is therefore not obvious to me.
The common-sense concept of "as many" or "as much" does not have a unique counterpart in mathematics: there are several formalizations for different purposes. In one widely used formalization (cardinality) there are as many primes as there are naturals, and this is indeed obvious for that formalization. If we take some other way of assigning sizes to number sets, like natural density, our two sets won't be equal any longer. And tomorrow you could invent some new formula that would give a third, completely different answer :-) It's ultimately pointless to argue which idea is "more intuitive"; the real test is what works in applications and what yields new interesting theorems.
Cardinality compares two sets using one-to-one mappings. If such a mapping exists, the two sets are equal in cardinality.
In this sense, there are as many primes as there are natural numbers. Proof: arrange the primes as an infinite series of increasing numbers. Map each prime in the series to its index in the series, which is a natural number.
This definition is mathematically simple. On the other hand, the intuitive concept of "size" where the size of the real line segment [0,1] is smaller than that of [0,2] and there are fewer primes than naturals, is much more complex to define mathematically. It is handled by measure theory, but one of the intuitive problems with measure theory is that some subsets simply can't be measured.
If I understand correctly, there really are no actual infinities in the universe, at least not inside a finite volume (and therefore not in interaction due to speed of light limits). And as far as I can make out (someone please correct me if I'm wrong), there aren't infinitely many Everett branches arising from a quantum fork in the sense that we can't physically measure the difference between sufficiently similar outcomes, and there are finitely many measurement results we can see. So the mathematical handling of infinities shouldn't ever directly map to actual events in a non-intuitive sense.
Yes, I get that you can do that! I get that you can do that - I just don't know why you should do that, instead of doing it the way that seems like the sensible way to do it in my head. What recommends this arrangement over any other arrangement?
Nothing at all, except that it shows there exists such a correspondence -- which is the only question of interest when talking about the "size" (cardinality) of sets.
(EDIT: Perhaps I should add that this question of existence is interesting because the situation can be quite different for different pairs of sets: while there exists a 1-1 correspondence between primes and natural numbers, there does not exist any such correspondence between primes and real numbers. In that case, all mappings will leave out some real numbers -- or duplicate some primes, if you're going the other way.)
All the other ways of "counting" that you're thinking of are just as "valid" as mathematical ideas, for whatever other purposes they may be used for. Here's an example, actually: the fact that you can think of a way of making primes correspond in a one-to-one fashion to a proper subset of the natural numbers (not including all natural numbers) succeeds in showing that the set of primes is no larger than the set of natural numbers.
It is obvious only if you've had the oddities of infinite sets hammered into you. Here's why our intuitions are wrong (the common ones I hear):
"Clearly there are more natural numbers than prime numbers. Prime numbers are a strict subset of natural numbers!" --> the strict subset thing works when everything is finite. But why? Because you can count out all the smaller set, then you have more left over in the larger set, so it's bigger. For infinite sets, though, you can't "count out all the smaller set" or equivalent.
"Okay, but if I choose an integer uniformly at random, there's a 50% chance it's a natural number and a < 50% chance it's a prime number. 50 > <50, so there are more natural numbers." --> You can't choose an integer uniformly at random.
"Really?" --> Yes, really. There are an infinite number of them, so with what probability is 42 selected? Not 0, 'cause then it won't be selected. Not >0, 'cause then the probabilities don't add to 1.
"Fine, if I start counting all the natural numbers and prime numbers (1: 1,0. 2: 2,1. 3: 3,2. 4: 4,2.) I'll find that the number of naturals is always greater than the number of primes." --> You've privileged an order, why? Instead let's start at 2, then 3, then 5, then 7, etc. Now they're equal.
"Something's still fishy." --> Yes, all of these are fine properties to think about. They happen to be equivalent for finite sets and not for infinite sets. We choose cousin_it's correspondence thing to be "size" for infinite sets, because it turns out to make the most sense. But the other properties could be interesting too.
Well, no, but there are finite sets I can't actually count either. I can, however, specify a way to translate an integer (or whatever) into something else, and as long as that algorithm can in principle be applied to any integer (or whatever), I consider myself to have in so doing accounted for all of them. For instance, when comparing the set of primes to the set of naturals, I say to myself, "okay, all of the primes will account for themselves. All of the naturals will account for themselves. There are naturals that don't account for primes, but no primes that don't account for naturals. Why, looks like there must be more naturals than primes!"
This reasoning is intuitive (because it arises by extension from finite sets) but unfortunately leads to inconsistent results.
Consider two different mappings ('accountings') of the naturals. In the first, every integer stands for itself. In the second, every integer x maps to 2*x, so we get the even numbers. By your logic, you would be forced to conclude that the set of naturals is "bigger" than itself.
But in that case something does recommend the first accounting over the second. The second one gives an answer that does not make sense, and the first one gives an answer that does make sense.
In the case of comparing rationals to integers, or any of the analogous comparisons, it's the accounting that People Good At Math™ supply that makes no sense (to me).
If you know which answer makes sense a priori, then you don't need an accounting at all. When you don't know the answer, then you need a formalization. The formalization you suggest gives inconsistent answers: it would be possible to prove for any two infinite sets (that have the same cardinality, e.g. any two infinite collections of integers) both that A>B, and B>A, and A=B in size.
Edit: suppose you're trying to answer the question: what is there "more" of, rational numbers in [0,1], or irrational numbers in [0,1]? I know I don't have any intuitive sense of the right answer, beyond that there are clearly infinitely many of both. How would you approach it, so that when your approach is generalized to comparing any two sets, it is consistent with your intuition for those pairs of sets where you can sense the right answer?
Mathematics gives several answers, and they're not consistent with one another or with most people's natural intuitions (as evolved for finite sets). We just use whichever one is most useful in a given context.
I haven't suggested anything that really looks to me like "a formalization". My basic notion is that when accounting for things, things that can account for themselves should. How do you make it so that this notion yields those inconsistent equations/inequalities?