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.
For infinite sets, though, you can’t “count out all the smaller set” or equivalent.
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.
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?
Mathematical formalization is necessary to make sure we both mean the same thing. Can you state your notion in terms of sets and functions and so on? Because I can see several different possible formalizations of what you just wrote and I really don’t know which one you mean.
Edit: possibly one thing that made the intuitive-ness of the primes vs. naturals problem is that the naturals is a special set (both mathematically and intuitively). How would you compare P={primes} and A=P+{even numbers}? A still strictly contains P, so intuitively it’s “bigger”, but now you can’t say that every number in A “accounts” for itself if you want to build a mapping from A to the naturals (i.e. if you want to arrange A as a series with indexes).
Question 2: how do you compare the even numbers and the odd numbers? Intuitively there is the same amount of each. But neither is a subset of the other.
Can you state your notion in terms of sets and functions and so on?
Probably not very well. Please keep in mind that the last time I took a math class, it was intro statistics, this was about four years ago, and I got a C. The last math I did well in was geometry even longer ago. This thread already has too much math jargon for me to know for sure what we’re talking about, and me trying to contribute to that jungle would be unlikely to help anyone understand anything.
Then let’s take the approach of asking your intuition to answer different questions. Start with the one about A and P in the edit to my comment above.
The idea is to make you feel the contradiction in your intuitive decisions, which helps discard the intuition as not useful in the domain of infinite sets. Then you’ll have an easier time learning about the various mathematical approaches to the problem because you’ll feel that there is a problem.
possibly one thing that made the intuitive-ness of the primes vs. naturals problem is that the naturals is a special set (both mathematically and intuitively). How would you compare P={primes} and A=P+{even numbers}? A still strictly contains P, so intuitively it’s “bigger”, but now you can’t say that every number in A “accounts” for itself if you want to build a mapping from A to the naturals (i.e. if you want to arrange A as a series with indexes).
A seems to contain the number 2 twice. Is that on purpose?
Question 2: how do you compare the even numbers and the odd numbers? Intuitively there is the same amount of each. But neither is a subset of the other.
In that case the sensible thing to do seems to me to pair every number with one adjacent to it. For instance, one can go with two, and three can go with four, etc.
A seems to contain the number 2 twice. Is that on purpose?
In the mathematical meaning of a ‘set’, it can’t contain a member twice, it either contains it or not. So there’s no special meaning to specifying 2 twice.
In that case the sensible thing to do seems to me to pair every number with one adjacent to it. For instance, one can go with two, and three can go with four, etc.
Here you’re mapping the sets to one another directly instead of mapping each of them to the natural numbers. So when does your intuition tell you not to do this? For instance, how would you compare all multiples of 2 with all multiples of 3?
Half of the multiples of 3 are also multiples of 2. Those can map to themselves. The multiples of 3 that are not also multiples of 2 can map to even numbers between the adjacent two multiples of 3. For instance, 6 maps to itself and 12 maps to itself. 9 can map to a number between 6 and 12; let’s pick 8. That leaves 10 unaccounted for with no multiples of 3 going back to deal with it later; therefore, there are more multiples of 2 than of 3.
Essentially, you’ve walked up the natural numbers in order and noted that you encounter more multiples of 2 than multiples of 3. But there’s no reason to privilege that particular way of encountering elements of the two sets.
For instance, instead of mapping multiples of 3 to a close multiple of 2, we could map each multiple of 3 to two-thirds of itself. Then every multiple of 2 is accounted for, and there are exactly as many multiples of 2 as of 3. Or we could map even multiples of 3 to one third their value, and then the the odd multiples of 3 are unaccounted for, and we have more multiples of 3 than of 2.
Your intuition seems to correspond to the following: if, in any large enough but finite segment of the number line, there are more members of set A than of set B; then |A|>|B|.
The main problem with this is that it contradicts another intuition (which I hope you share, please say so explicitly if you don’t): if you take a set A, and map it one-to-one to a different set B (a complete and reversible mapping) - then the two sets are equal in size. After all, in some sense we’re just renaming the set members. Anything we can say about set B, we can also say about set A by replacing references to members of B with members of A using our mapping.
But I can build such a mapping between multiples of 2 and of 3: for every integer x, map 2x to 3x. This implies the two sets are equal contradicting your intuition.
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?
Mathematical formalization is necessary to make sure we both mean the same thing. Can you state your notion in terms of sets and functions and so on? Because I can see several different possible formalizations of what you just wrote and I really don’t know which one you mean.
Edit: possibly one thing that made the intuitive-ness of the primes vs. naturals problem is that the naturals is a special set (both mathematically and intuitively). How would you compare P={primes} and A=P+{even numbers}? A still strictly contains P, so intuitively it’s “bigger”, but now you can’t say that every number in A “accounts” for itself if you want to build a mapping from A to the naturals (i.e. if you want to arrange A as a series with indexes).
Question 2: how do you compare the even numbers and the odd numbers? Intuitively there is the same amount of each. But neither is a subset of the other.
Probably not very well. Please keep in mind that the last time I took a math class, it was intro statistics, this was about four years ago, and I got a C. The last math I did well in was geometry even longer ago. This thread already has too much math jargon for me to know for sure what we’re talking about, and me trying to contribute to that jungle would be unlikely to help anyone understand anything.
Then let’s take the approach of asking your intuition to answer different questions. Start with the one about A and P in the edit to my comment above.
The idea is to make you feel the contradiction in your intuitive decisions, which helps discard the intuition as not useful in the domain of infinite sets. Then you’ll have an easier time learning about the various mathematical approaches to the problem because you’ll feel that there is a problem.
A seems to contain the number 2 twice. Is that on purpose?
In that case the sensible thing to do seems to me to pair every number with one adjacent to it. For instance, one can go with two, and three can go with four, etc.
In the mathematical meaning of a ‘set’, it can’t contain a member twice, it either contains it or not. So there’s no special meaning to specifying 2 twice.
Here you’re mapping the sets to one another directly instead of mapping each of them to the natural numbers. So when does your intuition tell you not to do this? For instance, how would you compare all multiples of 2 with all multiples of 3?
Half of the multiples of 3 are also multiples of 2. Those can map to themselves. The multiples of 3 that are not also multiples of 2 can map to even numbers between the adjacent two multiples of 3. For instance, 6 maps to itself and 12 maps to itself. 9 can map to a number between 6 and 12; let’s pick 8. That leaves 10 unaccounted for with no multiples of 3 going back to deal with it later; therefore, there are more multiples of 2 than of 3.
Essentially, you’ve walked up the natural numbers in order and noted that you encounter more multiples of 2 than multiples of 3. But there’s no reason to privilege that particular way of encountering elements of the two sets.
For instance, instead of mapping multiples of 3 to a close multiple of 2, we could map each multiple of 3 to two-thirds of itself. Then every multiple of 2 is accounted for, and there are exactly as many multiples of 2 as of 3. Or we could map even multiples of 3 to one third their value, and then the the odd multiples of 3 are unaccounted for, and we have more multiples of 3 than of 2.
Your intuition seems to correspond to the following: if, in any large enough but finite segment of the number line, there are more members of set A than of set B; then |A|>|B|.
The main problem with this is that it contradicts another intuition (which I hope you share, please say so explicitly if you don’t): if you take a set A, and map it one-to-one to a different set B (a complete and reversible mapping) - then the two sets are equal in size. After all, in some sense we’re just renaming the set members. Anything we can say about set B, we can also say about set A by replacing references to members of B with members of A using our mapping.
But I can build such a mapping between multiples of 2 and of 3: for every integer x, map 2x to 3x. This implies the two sets are equal contradicting your intuition.