4 ms·
Different sizes of infinity
- qntm 14y agoA much harder question is "How many infinities are there?" http://everything2.com/user/sam512/writeups/How+many+infinities+are+there%253F http://everything2.com/user/sam512/writeups/How+many+infinit...
- ionfish 14y agoWhy is that a harder question? It's a direct corollary of Cantor's Theorem that there is no largest cardinal number (assuming the powerset axiom, of course).
- pndmnm 14y agoIt's sort of interesting -- there's also no largest natural number, but we can talk about the size of their cardinality. You can't do that with all of the "infinities" since the collection of ordinals doesn't form an ordinal (Burali-Forti) and you can't form the set of all cardinals.
- ionfish 14y agoI'm not saying it's not interesting—in fact, I think it's fascinating—but all of this is implicit in Cantor's Theorem. "Harder question" to me implies there's something there that goes beyond the fundamental result that the powerset of a set X has strictly larger cardinality than X. One might think that it's just harder to understand, but I would dispute that too: if someone thinks they get Cantor's Theorem but has trouble grasping that there is no set of all sets, or largest cardinal number, it just shows that they don't really understand the theorem itself yet.
- pndmnm 14y agoAh, I gotcha. Yeah, the question as posed is straightforward, though there's some fun stuff (fixed points of ordinal exponentiation, inaccessibles, etc) floating around in the same neighborhood.
- qntm 14y agoThere's no largest integer, but the integers still form a set with an (infinite) cardinality, namely aleph-zero. Likewise, there's no largest cardinal, but you'd think that the cardinals also formed a set with an (infinite) cardinality of its own. Fun fact: they don't. There are too many of them.
- ionfish 14y agoLike I said in my response to pndmnm, in my view if someone "[would] think that the cardinals also formed a set with an (infinite) cardinality of its own" then they haven't really grasped the theorem yet. It's built into it that if we're always allowed to form the powerset of a set then regardless of how large a cardinal you can find, you can always take its powerset and obtain a larger cardinal.
- jowiar 14y agoSteven Rudich's lecture slides on the topic are pretty great, and how I was first introduced to the topic: http://www.cs.cmu.edu/afs/cs/academic/class/15251-s04/Site/Materials/Lectures/Lecture25/lecture25.html http://www.cs.cmu.edu/afs/cs/academic/class/15251-s04/Site/M... Not sure if the lecture itself is available anywhere.
- learc83 14y agoI've always liked the explanation of different sizes of infinity that compares the infinite set of whole numbers to the larger infinite set of fractions.
- qntm 14y agoThose sets have the same cardinality...
- ionfish 14y agoThe set of fractions isn't larger than the set of whole numbers, so how good an explanation could it be?
- pndmnm 14y agoThere are the same number of whole numbers as there are fractions/rational numbers (my favorite quick proof -- every whole number is a rational number (itself over 1). Map each n/m in lowest terms to 2^n*3^m for an injection of rationals into the integers (by the fundamental theorem of arithmetic)).
- ionfish 14y agoThat's a really nice way to show that, thanks. I may borrow it for future use.
- JadeNB 14y ago> There are the same number of whole numbers as there are fractions/rational numbers (my favorite quick proof -- every whole number is a rational number (itself over 1). Map each n/m in lowest terms to 2^n*3^m for an injection of rationals into the integers (by the fundamental theorem of arithmetic)). Notice that this shows only that there are no more whole numbers than rational numbers, and no more rational numbers than whole numbers. To conclude that there is the same number of each (more generally, that cardinal numbers are totally ordered (EDIT: as ionfish (http://news.ycombinator.com/item?id=4251492 http://news.ycombinator.com/item?id=4251492) points out, I should have said that the inclusion relation on cardinals is antisymmetric)) is actually a bit delicate; it's called the Schröder–Bernstein theorem (although Wikipedia attaches more names, in a different order: https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem https://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80...).
- tokenadult 14y agoIf you like this you may also like "All about Infinity" (former title, "Infinity Is Not a Number - It's a Free Man") http://nrich.maths.org/2756 http://nrich.maths.org/2756 by Katherine Körner.
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- jpallen 14y agoIf I've followed your argument correctly, then the same is also true of the rational numbers, but these are countable (i.e. the same 'size' as the integers). Oh fiddlesticks, the post was deleted before I'd even finished my reply! :(
- shenberg 14y agoOne point I never see discussed in these things is that you need to take a bit of care with digit-based representations because 0.1111... = 1.000..., 0.0111.... = 0.1000... - an argument could be made that perhaps while you know the number you're constructing via diagonalization doesn't appear in the list of numbers you created, but it may be a different representation of a number that does appear in the list. The simplest way I know to work around that is by excluding numbers ending in infinite strings of 0s or 1s from the list. Anyone know a nicer way?
- ionfish 14y agoThe usual way this is done is by selecting a canonical representation for the reals in the list. It's pretty much the same thing as you said, but I don't think you're putting it in the right terms. The list you're diagonalising (in Cantor's diagonal argument that the reals are uncountable) is a list of real numbers. Each of those reals has a canonical representation, and the reals in the list are ordered according to an order defined on those representations. The argument then demonstrates a method of constructing from those representations a representation of a new real which, by definition, cannot be one of the reals in that list. Put in those terms it feels a lot less arbitrary than simply excluding certain strings.
- ColinWright 14y agoProblem there is that you then have to prove that the string you've constructed is in your canonical form, and it might not be.
- alphaBetaGamma 14y agoThe ambiguity in digit representations only comes from numbers ending in 1's (in base 2, or ending in 9's in base 10). If you do the argument in a different base than 2 you can avoid the problem: you can construct a number whose base 10 representation consists only of 5's and 6's and which is different from any number in the list.
- deleted 14y ago[deleted]
- scovetta 14y agoI never liked Cantor's argument here. I'm sure I'm missing something, but the 'grid' that you set up has infinity rows but 2^infinity columns. The diagonal that you make just cuts off the top-right corner of the grid, and that missing element is one of the remaining rows. The diagonalization argument just seems like handwaving.
- ColinWright 14y agoThere aren't 2^oo columns - the number of columns is the same as the number of rows. And the argument can be made a lot less handwavey, it can be made very precise in set theoretic terms. Do you want references?
- scovetta 14y agoThat would rock, yes. (But why aren't there 2^oo columns? In order to fill up all possible ...<snap> I think I got it... You're not trying to use every possible oo-length binary string, you're just mapping each natural number to an arbitrary (unique) oo-length binary string, so the grid in a square in the end.
- ColinWright 14y agoYes. When working more formally it's actually easier just to show that for every set A the set 2^A is strictly bigger, where 2^A is a common representation for the power set of A, the collection of all subsets. As an aside, if A and B are sets, the set A^B is {f : f:B->A}, the set of all functions from B to A. You can quickly show that if A and B are finite, and |A|=n and |B|=m then |A^B|=n^m, thus matching our intuition. A function in 2^A says for each element of A, choose whether it's in or out. That gives a subset of A, so it makes sense to call the set of subsets 2^A, the power set. In what follows you need to "read like math." This is not a novel - work through it, don't simply try to read. Draw pictures, use simple examples, try to fund counter-examples. Work on understanding. So, given a set A, how do we show that |A| < |2^A|? Simple, we take any function from A to 2^A and show that some element of 2^A doesn't get hit. This shows that for every function from A->2^A it's not a matching. Hence no matching exists between A and 2^A, so 2^A is not the same size. I'll leave it to the interested reader to show that 2^A is never smaller than A. So how do we show that any function from A to 2^A leaves some element of 2^A unhit? Let g:A->2^A be any function from A to 2^A. We construct h in 2^A such that h is not in the image of g. h needs to be a function from A->{0,1}, so for every a in A, we need to say whether h(a)=0 or h(a)=1. Remembering that g(a) is in 2^A, and hence is a function A->{0,1} we define h:A->{0,1} as: h(a) = 0 if (g(a))(a) = 1 h(a) = 1 if (g(a))(a) = 0 Chase the definitions and you'll find that for every a in A, h != g(a).
- ColinWright 14y agoWhat really tends to upset people is this: * Between any two irrationals there is (at least one) rational * Between any two rationals there is (at least one) irrational * There are more irrationals than there are rationals.
- ionfish 14y agoI think this becomes much more intuitive once one understands that the cardinality of any nondegenerate closed interval is the same as the cardinality of the continuum.
- ColinWright 14y agoIt becomes perhaps even more obvious when you realize that any non-empty open interval (a,b) with a<b is homeomorphic to the reals. Once that really sinks in, much of this becomes easier.
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- derleth 14y ago> the cardinality of any closed interval is the same as the cardinality of the continuum. In English: There are just as many real numbers (rational and irrational combined) in between any two real numbers as there are real numbers total. (That's a somewhat simplified statement as I didn't really define 'closed interval', but it serves to give a taste of the concept.) If nothing else, statements like those completely break your intuitive notions regarding size in this context and convince you that you can only proceed based on logic and proven theorems. Which is, of course, accurate, at least until you develop a new intuition. Measure theory is the branch of mathematics concerned with developing new notions of size appropriate to different contexts. http://en.wikipedia.org/wiki/Measure_(mathematics) http://en.wikipedia.org/wiki/Measure_(mathematics)
- wkdown 14y agoI thought infinity is infinity; no varying degrees. How is this different from saying counting to infinity with integers is smaller than counting with floats?
- chp 14y agoOne simply cannot "count" with "real" numbers. But "floats" is probably countable since it's represented with limited digits. However, considering the inherent error associated with it, I wouldn't say it's countable. Also, if you are trying to find an infinite large number, for any arbitrarily large real number, you can find a larger integer and vice versa. But the point here is that there are more real numbers than integers.
- ColinWright 14y agoThis is not "infty" as per computer representations of numbers. This is "infinity" as in "how many counting numbers are there" and "how many reals are there". We are not dealing with floats. Trivial, for any size being used, the number of floats that can be represented is finite. So what this is saying is this: Consider the collection of counting numbers: 1, 2, 3, ... and so on. Call that set N. There is a set P which has the property that every time you try to match up items of N with items of P, there are items of P left over. If you have some cups and saucers, and every time you laid them out you had some saucers left over, you'd say you had more saucers. Yes? Well every time we try to match up things from N with things from P we can things from P left over, so we should say we have more of them, right? But there are infinitely many things in N, so P must be a bigger infinity.
- mchahn 14y agoThis is only tangentially relative, but I find the argument that real numbers may not ever exist in nature to be fascinating. The argument is that all of nature breaks down at the size of plank's constant so every real measurement has a finite resolution.