Set Theory and Orders of infinityDate: 04/08/97 at 21:06:07 From: Sergio Subject: sizes or orders of infinity Hello, I am an Algebra II student, and I have been assigned a project concerning infinity. I really need help with this. I have been given the following sets and I am supposed to compare their size and explain what rationale I have used in doing so. A. (1,2,3,4) B. (a,b,c,d) C. (1,2,3,4,5) D. (1,2,3....) E. (2,4,6....) F (-5,-4,-3,...) G (1000,2000,3000,....) H. (all real numbers between 0 and 1) I (all real numbers between -1 and 1) J. (all real numbers between 0 and 1000) K. (all rational numbers between 0 and 1) L. (the grains of sand in the sahara desert to a depth of 10 feet) I have done some research, especially on Cantor's set theory, but it doesn't really make sense to me. Could you please tell me how to label one set as being larger than another? What criteria are used? Thanks. Date: 04/10/97 at 17:50:45 From: Doctor Daniel Subject: Re: sizes or orders of infinity Hi Sergio, You asked about orders of infinity; specifically, you listed a bunch of sets, all of which were pretty well-specified, and wanted to know how to order them by size. That's not terribly easy! It's worth realizing that the rigorous mathematical definitions of things like "the real numbers between 0 and 1" weren't well-developed until roughly 1900, and so it was very hard to also talk about things like "this infinite set is bigger than that one" until about that same time. (As a side note, it may be for the best that they're hard to identify; Georg Cantor, who's responsible for much of the formal set theory that underlies these questions, went mad late in life and died in an asylum, as have some other people who have looked at them!) Anyhow, here goes: Basically, we say that two sets A and B have "equal cardinality" (or, more informally, are the same size), if we can map from one to the other so that every element of A has exactly one mapping in B, and every element of B is the mapping of exactly one element of A. That's called a "bijection," or a "one-to-one" mapping. Here's an easy example: The sets A = {1,2,3,4} and B = {A,B,C,D} have the same cardinality. That's true because if we take 1 -> A, 2 -> B, 3 -> C, and 4 -> D, each element of A has a companion in B, and each element of B is the companion of an element of A. So A and B are the same size. Here's a harder example: The sets A = {1,2,3,4,...} and B = {2,4,6,8,...} have the same cardinality. Huh? But doesn't A have all of those extra elements, like 1,3,5, etc.? YES. However, that doesn't matter. Remember, we said that all we needed was the bijection, which is easy; map 1 -> 2, 2 -> 4, 3 -> 6, and so on. Every element a of A has a mapping in B, 2a, and every element b of B is the mapping of b/2. So these two sets have the same size. I'll repeat the argument: B and A have the same size, because we can map every element of A to an element of B so that every element of B is taken exactly once as well. Here's another one: {1,2,3,4,5,...} has the same cardinality as {100000, 100001, 100002, 100003, ...}, even though the first set has 100,000 more elements! Just map 1 -> 100001, 2 -> 100002, etc., and the bijection is obvious. This will take care of sets A through G and L on the list you gave; L is obviously an enormous finite set, so it's not able to be put in bijection with {1,2,3,4,...}; you'd have to leave elements of {1,2,3,4,...} that weren't the mapping of a grain of sand. So L has less cardinality than the infinite sets. Now, there's two more types of sets you gave: Sets of all real numbers in an interval (like [0,1] or [1,10], and sets of rationals in [0,1]. It should be clear that the cardinality of A = {all real numbers in [0,1]} is the same as the cardinality of B = {all real numbers in [1,10]). Huh? Well, let a be an element of A. Map a to 9a + 1. This is clearly in [1,10]. Now, consider each b in B. It is, clearly, the mapping of exactly one point, 1/9 * (b-1). That is, 1/9 * (b-1) was mapped by the mapping onto b. Moreover, it's obvious that ONLY that value was mapped onto b. So every b in [1,10] is the mapping of exactly one element of A, and every element of A has exactly one mapping in B. Hence [0,1] and [1,10] have the same cardinality! That should help you compare between H, I, and J. But what about the difference between I and, say, D? Are there more real numbers between 0 and 1 than there are integers? Eek! Let's wait on that one. (But the answer is yes.) We've still got one type of set left; K = {the rationals between 0 and 1.} Now, if we can come up with a way of mapping K onto D by a bijection, then there's as many integers as there are rationals between 0 and 1. And, actually, that's true! Here goes: Map 1 -> 0/1 Map 2 -> 1/1 Map 3 -> 1/2 Map 4 -> 1/3 Map 5 -> 2/3 Map 6 -> 1/4 Map 7 -> 3/4 ... In general, then, reduce all fractions to least terms. List all the fractions with 1 as their denominator, then the fractions with 2 as their denominator, then those with 3 as their denominator, and so on. (For example, we don't list 2/4, since it's already taken as 1/2.) Now, it's clear that this list is infinite; that is, each integer can be mapped to something. Why? Because just the list 1/1, 1/2, 1/3, etc. is infinite, and it's in least terms. Also, we've made sure that we only take each fraction once; not more often. And, since each fraction in [0,1] is taken exactly once, we do, in fact, wind up with a bijection. If that's hard to understand, look at it a couple more times. Basically, I've just shown that there's exactly as many fractions between [0,1] as there are positive integers. That's counterintuitive, so it's not surprising if it's not immediately obvious! Okay, so now here we are: We know that all the finite sets are easily ordered, that all the infinite subsets of the integers are of the same size, which is also the size of the rationals between [0,1], and that all the intervals on the real line like [0,1] or [1,10] all have the same cardinality. All that's left is that we need to find out how A = {the positive integers} and B = {the reals in [0,1]} compare. It should be clear, now, that that's the same question as the question of how the rationals and the reals between [0,1] compare! Now comes the biggie. This is actually a hard proof, so read it a couple times if it's not clear the first time. It's also a proof by indirection, which you probably aren't too familiar with. I'm going to take advantage of this fact: The set of reals between 0 and 1 is EXACTLY the same as the set of all infinite-length decimal numbers. Suppose that A and B have the same cardinality. Then we know that there must be a bijection from A -> B. That basically means there's a list of all the reals between 0 and 1, where all of them are listed exactly once; the mapping of 1, then the mapping of 2, and so on. So we have something like this: 1 -> .043293084... 2 -> .2359852423... 3 -> .224390823... etc. I show that there's at least one element of B which isn't on the list. Look at the first decimal digit of 1's mapping. It's 0. Hence, any number whose decimal doesn't have first digit 0 is not 1's image. Look at the second decimal digit of 2's mapping. It's 3. Hence, any number whose decimal doesn't have second digit 3 is not 2's image. So any number which starts .146... will not be the image of 1, 2, or 3. In general, if the k'th decimal digit of k's mapping is, say, t, then any number whose kth decimal digit isn't t (or 0 or 9, to avoid the possible .09999... = .10000 problem) will also not be the mapping of k! So we can easily construct a number which is not the image of ANY integer; it differs in the first digit from the image of 1, in the second digit from the image of 2, and so on. So it's not the image of ANY integer. But it IS an infinite decimal, and hence a real number between 0 and 1. So we have an element of B which is NOT the image of any element of A. Hence, A has different cardinality (smaller) than B. That's almost certainly hard on the first (second, ...) reading, so give it a bit of a go. This argument dates to Cantor and is called the "diagonalization" argument, since we kind of go down the diagonal of the decimals; we look at the first digit of 1's image, the 2nd of 2's image, and so on. It's absolutely the most common proof that there are more real numbers than there are integers (and hence rationals); while there are others, none are nearly as clean. It might be obvious by looking at this, in fact, that there are LOTS more reals than integers; there are formalizable ways of looking at that which are much more complicated than I want to go here. So let's recap: To compare two sets, we know that they're equal in size (cardinality) if we can find a bijection between them, which is a mapping from one to the other, where every element of the first is mapped to exactly one element of the other set, and every element of the second set is the mapping of exactly one element of the first set. It's very easy to find if two finite sets have the same cardinality, and all finite sets have smaller cardinality than all infinite sets. The integers are infinite, and all infinite subsets of the integers are of the same cardinality as is Z = {the integers}. Even though we'd expect that there'd be more integers, say, than odd integers, this is actually false; there's exactly the same number. The rational numbers between [0,1] and, actually, all rational numbers, have equal cardinality to the integers; there's the same number of rational numbers as there are integers. Any interval of the real line has the same cardinality. This is also true of the entire real line (We can map [0,1] to [1,infinity) easily by taking a and mapping it to 1/a; then, mapping onto the entire real line is fairly easy). So [0,1] has the same cardinality as [1,1000], etc. And, lastly, I showed that any interval of the real line has higher cardinality than the integers, or the rationals, or, certainly, any finite set! One last bit of terminology, before I let you go! We say that any set which has equal cardinality with the integers is "countably infinite" or "denumerable." A set which is finite or denumerable is "countable," and a set which is not countable is "uncountable" or "uncountably infinite." So the rationals are countably infinite, while the reals are uncountable. This is the first lesson in Cantorian Set Theory. And if this seemed hard for starters, rest assured; they get worse! Good luck. If you have troubles with this answer, or any other problems, please don't hesitate to use us again! -Doctor Daniel, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/