That doesn’t quite work when comparing infinite sets. It might seem surprising, but indeed, there are exactly as many rational numbers between zero and one as there are between zero and two.
The short version of the explanation:
Two infinite sets are the same size if you can construct a one-to-one correspondence between them. In other words, if you can come up with a list of pairs (x,y) of members of sets X and Y such that every member of set X corresponds to exactly one member of set Y, and vice versa, then sets X and Y are the same size. For example, the set of positive integers and the set of positive even integers are the same size, because you can list them like this:
(1,2),
(2,4),
(3,6),
(4,8),
and so on. Each positive integer appears exactly once on the left side of the list, and each positive even integer appears exactly once on the right side of the list. You can use the same function I used here, f(x)=2x, to map the rational numbers between zero and one to the rational numbers between zero and two.
(As it turns out, you can map the positive integers to the rational numbers, but you can’t map them to the real numbers...)
You are not the first person to try to explain this to me, but it doesn’t seem “surprising”, it seems like everybody is cooperating at pulling my leg. Since I’m aware that such a conspiracy would be impractical and that I am genuinely terrible at math, I don’t think that’s actually happening, but the fact remains that I just do not get this (and, at this point, no longer seriously entertain the hope of learning to do so). It is only slightly less obvious to me that there are more numbers between 0 and 2 than 0 and 1, than it is that one and one are two.
To put it a little differently, while I can understand the proofs that show how you may line up all the rationals in a sensible order and thereby assign an integer to each, it’s not obvious to me that that is the way you should count them, given that I can easily think of other ways to count them where the integers will be used up first. Nothing seems to recommend the one strategy over the other except the consensus of people who don’t seem to share my intuitions anyway.
Imagine A is the set of all positive integers and B is the set of all positive even integers. You would say B is smaller than A. Now multiply every number in A by two. Did you just make A become smaller without removing any elements from it?
It gets even worse than that if you want to keep your intuitions (which are actually partially formalized as the concept natural density). Imagine that T is the set of all Unicode text strings. Most of these strings, like “🂾⨟ꠗ∧̊⩶🝍”, are gibberish, while some are valid sentences in various languages (such as “The five boxing wizards jump quickly.”, “print ‘Hello, world!’”, “ἔσχατος ἐχθρὸς καταργεῖται ὁ θάνατος·”, or “וקראתם בשם אלהיכם ואני אקרא בשם יהוה והיה האלהים אשר יענה באש הוא האלהים ויען כל העם ויאמרו טוב הדבר”). The interesting strings for this problem are things like “42“, “22/7”, “e”, “10↑↑(10↑↑10)”, or even “The square root of 17”. These are the strings that unambiguously describe some number (under certain conventions). As we haven’t put a length limit on the elements of T, we can easily show that every natural number, every rational number, and an infinite number of irrational numbers are each described by elements of T. As some elements of T don’t unambiguously describe some number, our intuitions tell us that there are more text files than there are rational numbers.
However, a computer (with arbitrarily high disk space) would represent these strings encoded as sequences of bytes. If we use a BOM in our encoding, or if we use the Modified UTF-8 used in Java’s DataInput interface, then every sequence of bytes encoding a string in T corresponds to a different natural number. However, given any common encoding, not every byte sequence corresponds to a string, and therefore not every natural number corresponds to a string. As encoding strings like this is the most natural way to map strings to natural numbers, there must intuitively be more natural numbers than strings.
We have thus shown that there are more strings than rational numbers, and more natural numbers than strings. Thus, any consistent definition of “bigger” that works like this can’t be transitive, which would rule out many potential applications of such a concept.
EDIT: Fixed an error arising from my original thoughts differing from the way I wanted to explain them
I think that part of the difficulty (and part of the reason that certain people call themselves infinite set atheists) stems from the fact that we have two very basic intuitions about the quantity of finite sets, and it is impossible to define quantity for infinite sets in a way that maintains both intuitions.
Namely, you can have a notion of quantity for which
(A) sets that can be set in some 1-to-1 correspondence will have the same quantity,
OR a notion of quantity for which
(B) a set that strictly contains another set will have a strictly larger quantity.
As it turns out, given the importance of functions and correspondences in basic mathematical questions, the formulation (cardinality) that preserves (A) is very natural for doing math that extends and coheres with other finite intuitions, while only a few logicians seem to toy around with (B).
So it may help to realize that for mainstream mathematics and its applications, there is no way to rescue (B); you’ll just need to get used to the idea that an infinite set and a proper subset can have the same cardinality, and the notion that what matters is the equivalence relation of there existing some 1-to-1 correspondence between sets.
My problem doesn’t arise only when comparing sets such that one strictly contains another. I can “prove” to myself that there are more rational numbers between any two integers than there are natural numbers, because I can account for every last natural number with a rational between the two integers and have some rationals left over. I can also read other people “proving” that the rationals (between two integers or altogether, it hardly matters) are “countably infinite” and therefore not more numerous than the integers, because they can be lined up. I get that the second way of arranging them exists. It’s just not at all clear why it’s a better way of arranging things, or why the answer it generates about the relative sizes of the sets in question is a better answer.
If you come up with a different self-consistent definition of how to compare sizes of sets (“e.g. alicorn-bigger”), that would be fine. Both definitions can live happily together in the happy world of mathematics. Note that “self-consistent definition” is harder than it sounds.
There are cases where mainstream mathematical tradition was faced with competing definitions. Currently, the gamma function is the usual extension of the factorial function to the reals, but at one time, there were alternative definitions competing to be standardized.
Another example: The calculus was motivated by thought experiments involving infinitesimals, but some “paradoxes” were discovered, and infinitistic reasoning was thought to be the culprit. By replacing all of the arguments with epsilon-delta analogs, the main stream of mathematics was able to derive the same results while avoiding infinitistic reasoning. Eventually, Abraham Robinson developed non-standard analysis, showing an alternative, and arguably more intuitive, way to avoid the paradoxes.
The trouble is that with a little cleverness, you can account for all of the rationals by using some of the natural numbers (once each) and still have infinitely many natural numbers left over. (Left as an exercise to the reader.) That’s why your intuitive notion isn’t going to be self-consistent.
Well, that was the short explanation. The long one makes a little more sense. (By the way, the technical term for the number of members in a set is the cardinality of a set.)
Let’s try this from a different angle.
If you have two sets, X and Y, and you can map X to a subset of Y and still have some members of Y left over, then X can’t be a bigger set than Y is. In other words, a set can’t “fit inside” a set that’s smaller than itself. For example, {1,2,3} can fit inside {a,b,c,d}, because you can map 1 to a, 2 to b, 3 to c, and still have “d” left over. This means that {1,2,3} can’t be bigger than {a,b,c,d}. It shouldn’t matter how you do the mapping, because we only care about whether or not the whole thing fits. Am I making sense here?
Now, because you can map the positive even integers to a subset of the positive integers (for example, by mapping each positive integer to itself) and still have positive integers left over (all the odd ones), the set of positive even integers fits inside the set of positive integers, and so it can’t be bigger than the set of positive integers.
On the other hand, the positive integers can also fit inside the positive even integers. Just map every positive integer n to the positive even integer 2*(n+1). You get the list (1,4), (2,6), (3,8), and so on. You’ve used up every positive integer, but you still have a positive even integer − 2 - left over. So, because the positive integers fit inside the positive even integers, so they’re not bigger, either.
If the positive even integers aren’t bigger than the positive integers, and the positive integers aren’t bigger than the positive even integers, then the only way that could happen is if they are both exactly the same size. (Which, indeed, they are.)
So in fact, we count them both ways, get both answers, and conclude that since each answer says that it is not the case that the one set is bigger than the other, they must be the same size?
Congratulations! I think I have, if not a perfect understanding of this, at least more of one than I had yesterday! Thanks :)
You’re welcome. I like to think that I’m good at explaining this kind of thing. ;) To give credit where credit is due, it was the long comment thread with DanArmak that helped me see what the source of your confusion was. And, indeed, all the ways of counting them matter. Mathematicians really, really hate it when you can do the same thing two different ways and get two different answers.
I learned about all this from a very interesting book I once read, which has a section on Georg Cantor, who was the one who thought up these ways of comparing the sizes of different infinite sets in the first place.
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.
For example, there are obviously as many prime numbers as there are naturals
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.
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.
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?
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.
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.
Sure, you can line them up such that the integers run out first. You can even line them up so the rationals line up first. There are an infinite number of ways to line them up. In order to satisfy the definition of them being the same size we only require that ONE of the ways of lining them up leads to them corresponding exactly.
It’s merely a definition, though. The kicker is that the definition is useful and consistent.
That doesn’t quite work when comparing infinite sets. It might seem surprising, but indeed, there are exactly as many rational numbers between zero and one as there are between zero and two.
The short version of the explanation:
Two infinite sets are the same size if you can construct a one-to-one correspondence between them. In other words, if you can come up with a list of pairs (x,y) of members of sets X and Y such that every member of set X corresponds to exactly one member of set Y, and vice versa, then sets X and Y are the same size. For example, the set of positive integers and the set of positive even integers are the same size, because you can list them like this:
(1,2),
(2,4),
(3,6),
(4,8),
and so on. Each positive integer appears exactly once on the left side of the list, and each positive even integer appears exactly once on the right side of the list. You can use the same function I used here, f(x)=2x, to map the rational numbers between zero and one to the rational numbers between zero and two.
(As it turns out, you can map the positive integers to the rational numbers, but you can’t map them to the real numbers...)
You are not the first person to try to explain this to me, but it doesn’t seem “surprising”, it seems like everybody is cooperating at pulling my leg. Since I’m aware that such a conspiracy would be impractical and that I am genuinely terrible at math, I don’t think that’s actually happening, but the fact remains that I just do not get this (and, at this point, no longer seriously entertain the hope of learning to do so). It is only slightly less obvious to me that there are more numbers between 0 and 2 than 0 and 1, than it is that one and one are two.
To put it a little differently, while I can understand the proofs that show how you may line up all the rationals in a sensible order and thereby assign an integer to each, it’s not obvious to me that that is the way you should count them, given that I can easily think of other ways to count them where the integers will be used up first. Nothing seems to recommend the one strategy over the other except the consensus of people who don’t seem to share my intuitions anyway.
Imagine A is the set of all positive integers and B is the set of all positive even integers. You would say B is smaller than A. Now multiply every number in A by two. Did you just make A become smaller without removing any elements from it?
...Okay, that’s weird! Clearly that shouldn’t work. Thanks for the counterexample.
It gets even worse than that if you want to keep your intuitions (which are actually partially formalized as the concept natural density). Imagine that T is the set of all Unicode text strings. Most of these strings, like “🂾⨟ꠗ∧̊⩶🝍”, are gibberish, while some are valid sentences in various languages (such as “The five boxing wizards jump quickly.”, “print ‘Hello, world!’”, “ἔσχατος ἐχθρὸς καταργεῖται ὁ θάνατος·”, or “וקראתם בשם אלהיכם ואני אקרא בשם יהוה והיה האלהים אשר יענה באש הוא האלהים ויען כל העם ויאמרו טוב הדבר”). The interesting strings for this problem are things like “42“, “22/7”, “e”, “10↑↑(10↑↑10)”, or even “The square root of 17”. These are the strings that unambiguously describe some number (under certain conventions). As we haven’t put a length limit on the elements of T, we can easily show that every natural number, every rational number, and an infinite number of irrational numbers are each described by elements of T. As some elements of T don’t unambiguously describe some number, our intuitions tell us that there are more text files than there are rational numbers.
However, a computer (with arbitrarily high disk space) would represent these strings encoded as sequences of bytes. If we use a BOM in our encoding, or if we use the Modified UTF-8 used in Java’s DataInput interface, then every sequence of bytes encoding a string in T corresponds to a different natural number. However, given any common encoding, not every byte sequence corresponds to a string, and therefore not every natural number corresponds to a string. As encoding strings like this is the most natural way to map strings to natural numbers, there must intuitively be more natural numbers than strings.
We have thus shown that there are more strings than rational numbers, and more natural numbers than strings. Thus, any consistent definition of “bigger” that works like this can’t be transitive, which would rule out many potential applications of such a concept.
EDIT: Fixed an error arising from my original thoughts differing from the way I wanted to explain them
I think that part of the difficulty (and part of the reason that certain people call themselves infinite set atheists) stems from the fact that we have two very basic intuitions about the quantity of finite sets, and it is impossible to define quantity for infinite sets in a way that maintains both intuitions.
Namely, you can have a notion of quantity for which
(A) sets that can be set in some 1-to-1 correspondence will have the same quantity,
OR a notion of quantity for which
(B) a set that strictly contains another set will have a strictly larger quantity.
As it turns out, given the importance of functions and correspondences in basic mathematical questions, the formulation (cardinality) that preserves (A) is very natural for doing math that extends and coheres with other finite intuitions, while only a few logicians seem to toy around with (B).
So it may help to realize that for mainstream mathematics and its applications, there is no way to rescue (B); you’ll just need to get used to the idea that an infinite set and a proper subset can have the same cardinality, and the notion that what matters is the equivalence relation of there existing some 1-to-1 correspondence between sets.
(B) is roughly measure theory, innit?
Yes, for some value of “roughly”.
(A value of “roughly” that encompasses sets of measure zero is what I had in mind.)
My problem doesn’t arise only when comparing sets such that one strictly contains another. I can “prove” to myself that there are more rational numbers between any two integers than there are natural numbers, because I can account for every last natural number with a rational between the two integers and have some rationals left over. I can also read other people “proving” that the rationals (between two integers or altogether, it hardly matters) are “countably infinite” and therefore not more numerous than the integers, because they can be lined up. I get that the second way of arranging them exists. It’s just not at all clear why it’s a better way of arranging things, or why the answer it generates about the relative sizes of the sets in question is a better answer.
If you come up with a different self-consistent definition of how to compare sizes of sets (“e.g. alicorn-bigger”), that would be fine. Both definitions can live happily together in the happy world of mathematics. Note that “self-consistent definition” is harder than it sounds.
There are cases where mainstream mathematical tradition was faced with competing definitions. Currently, the gamma function is the usual extension of the factorial function to the reals, but at one time, there were alternative definitions competing to be standardized.
http://www.luschny.de/math/factorial/hadamard/HadamardsGammaFunction.html
Another example: The calculus was motivated by thought experiments involving infinitesimals, but some “paradoxes” were discovered, and infinitistic reasoning was thought to be the culprit. By replacing all of the arguments with epsilon-delta analogs, the main stream of mathematics was able to derive the same results while avoiding infinitistic reasoning. Eventually, Abraham Robinson developed non-standard analysis, showing an alternative, and arguably more intuitive, way to avoid the paradoxes.
http://en.wikipedia.org/wiki/Non-standard_analysis
Thanks for that super-interesting link about factorial-interpolating functions!
The trouble is that with a little cleverness, you can account for all of the rationals by using some of the natural numbers (once each) and still have infinitely many natural numbers left over. (Left as an exercise to the reader.) That’s why your intuitive notion isn’t going to be self-consistent.
Well, that was the short explanation. The long one makes a little more sense. (By the way, the technical term for the number of members in a set is the cardinality of a set.)
Let’s try this from a different angle.
If you have two sets, X and Y, and you can map X to a subset of Y and still have some members of Y left over, then X can’t be a bigger set than Y is. In other words, a set can’t “fit inside” a set that’s smaller than itself. For example, {1,2,3} can fit inside {a,b,c,d}, because you can map 1 to a, 2 to b, 3 to c, and still have “d” left over. This means that {1,2,3} can’t be bigger than {a,b,c,d}. It shouldn’t matter how you do the mapping, because we only care about whether or not the whole thing fits. Am I making sense here?
Now, because you can map the positive even integers to a subset of the positive integers (for example, by mapping each positive integer to itself) and still have positive integers left over (all the odd ones), the set of positive even integers fits inside the set of positive integers, and so it can’t be bigger than the set of positive integers.
On the other hand, the positive integers can also fit inside the positive even integers. Just map every positive integer n to the positive even integer 2*(n+1). You get the list (1,4), (2,6), (3,8), and so on. You’ve used up every positive integer, but you still have a positive even integer − 2 - left over. So, because the positive integers fit inside the positive even integers, so they’re not bigger, either.
If the positive even integers aren’t bigger than the positive integers, and the positive integers aren’t bigger than the positive even integers, then the only way that could happen is if they are both exactly the same size. (Which, indeed, they are.)
So in fact, we count them both ways, get both answers, and conclude that since each answer says that it is not the case that the one set is bigger than the other, they must be the same size?
Congratulations! I think I have, if not a perfect understanding of this, at least more of one than I had yesterday! Thanks :)
You’re welcome. I like to think that I’m good at explaining this kind of thing. ;) To give credit where credit is due, it was the long comment thread with DanArmak that helped me see what the source of your confusion was. And, indeed, all the ways of counting them matter. Mathematicians really, really hate it when you can do the same thing two different ways and get two different answers.
I learned about all this from a very interesting book I once read, which has a section on Georg Cantor, who was the one who thought up these ways of comparing the sizes of different infinite sets in the first place.
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?
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.
The definition of equal cardinality is that there is a one-to-one correspondence between the objects. It doesn’t matter what that correspondence is.
Sure, you can line them up such that the integers run out first. You can even line them up so the rationals line up first. There are an infinite number of ways to line them up. In order to satisfy the definition of them being the same size we only require that ONE of the ways of lining them up leads to them corresponding exactly.
It’s merely a definition, though. The kicker is that the definition is useful and consistent.