3 ms·

A related derivation of the "uncountably infinite" is Cantor diagonalization: https://en.m.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.m.wikipedi

A related derivation of the "uncountably infinite" is Cantor diagonalization: https://en.m.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.m.wikipedia.org/wiki/Cantor%27s_diagonal_argument Put in more concrete terms (hard to say when we are talking about infinities): there are an infinite number of integers. For each integer, there are an infinite number of real numbers (decimals) between n and n+1. For each of those doubly-infinite real numbers, there are an infinite number of complex numbers with that real component and varying imaginary components. And so on ... In fact, there are an infinite number of infinities ... It's turtles all the way down.

lukasb 11y ago
That's the clearest, most concise explanation I've seen for how different infinite sets can have different cardinalities. Thanks!
- yongjik 11y ago
  Wait, but between n and n+1 there are also an infinite number of rational numbers, but the cardinality of all rational numbers is the same as that of integers (or that of all rational numbers between a fixed n and n+1). So, while what the gp wrote is correct, it's not an explanation of why there are more real numbers than integers.
- mikeash 11y ago
  I don't think the summary in the comment is correct, though. There are also an infinite number of rational numbers between any given integer n and n+1, and indeed an infinite number of rational numbers between any two rational numbers, yet the cardinality of the rationals is still the same as the cardinality of the integers. Diagonalization is brilliant, though!
- buzzdenver 11y ago
  It's a little confusing though, at least for me. There are infinite integers, and "doubly-infinite" reals. But there are also only "doubly-infinite" complex numbers. IMO the easiest way to illustrate different, and infinite number of, infinities is to think of sets. Suppose you have N-infinite number of things, say triple-infinite to use the grandparent's lingo. Now the number of sets that you can create from these triple-infinite objects is greater than triple-infinite, and it's called quad-infinite. You can prove that indirectly. Assume that there is a one to one mapping of the original object to the sets. That means that some of the objects are mapped to sets that the objects are members of (let's call these red objects), others not (let's call them blue objects). Does the set of blue objects get paired with a blue or a red object ? Cannot be either, so we've reached a contradiction, ergo there are always more subsets of things than things.
lgandersen 11y ago
Just to clarify a little bit: For each integer n there is also an infinite amount of rationals (fractions) between n and n+1 and the rationals is also a countable set like the integers (just as 'infinite', so to speak). Quite counter-intuitive, I think. I usually interpret the first steps in Hilbert's hotel as the first steps in the ordinal hierarchy (https://en.wikipedia.org/wiki/Ordinal_number https://en.wikipedia.org/wiki/Ordinal_number).
pdkl95 11y ago
Vi Hart has a few interesting videos on infinity: "Proof some infinities are bigger than other infinities" (w/ Cantor's diagonal proof) https://www.youtube.com/watch?v=lA6hE7NFIK0 https://www.youtube.com/watch?v=lA6hE7NFIK0 "How many kinds of infinity are there?" (a very good list including surreals, P-adic, the long line, others) http://vihart.com/how-many-kinds-of-infinity-are-there/ http://vihart.com/how-many-kinds-of-infinity-are-there/ Also, I support her suggestion in "Infinite Trees Are Super Weird" that since we call uncountable line segments the "long line", we should call the uncountably-branching tree the "big tree". https://www.youtube.com/watch?v=BEz-vGJvaik https://www.youtube.com/watch?v=BEz-vGJvaik

lukasb 11y ago

That's the clearest, most concise explanation I've seen for how different infinite sets can have different cardinalities. Thanks!

yongjik 11y ago
Wait, but between n and n+1 there are also an infinite number of rational numbers, but the cardinality of all rational numbers is the same as that of integers (or that of all rational numbers between a fixed n and n+1). So, while what the gp wrote is correct, it's not an explanation of why there are more real numbers than integers.
mikeash 11y ago
I don't think the summary in the comment is correct, though. There are also an infinite number of rational numbers between any given integer n and n+1, and indeed an infinite number of rational numbers between any two rational numbers, yet the cardinality of the rationals is still the same as the cardinality of the integers. Diagonalization is brilliant, though!
buzzdenver 11y ago
It's a little confusing though, at least for me. There are infinite integers, and "doubly-infinite" reals. But there are also only "doubly-infinite" complex numbers. IMO the easiest way to illustrate different, and infinite number of, infinities is to think of sets. Suppose you have N-infinite number of things, say triple-infinite to use the grandparent's lingo. Now the number of sets that you can create from these triple-infinite objects is greater than triple-infinite, and it's called quad-infinite. You can prove that indirectly. Assume that there is a one to one mapping of the original object to the sets. That means that some of the objects are mapped to sets that the objects are members of (let's call these red objects), others not (let's call them blue objects). Does the set of blue objects get paired with a blue or a red object ? Cannot be either, so we've reached a contradiction, ergo there are always more subsets of things than things.

lgandersen 11y ago

Just to clarify a little bit: For each integer n there is also an infinite amount of rationals (fractions) between n and n+1 and the rationals is also a countable set like the integers (just as 'infinite', so to speak). Quite counter-intuitive, I think. I usually interpret the first steps in Hilbert's hotel as the first steps in the ordinal hierarchy (https://en.wikipedia.org/wiki/Ordinal_number https://en.wikipedia.org/wiki/Ordinal_number).

pdkl95 11y ago

Vi Hart has a few interesting videos on infinity: "Proof some infinities are bigger than other infinities" (w/ Cantor's diagonal proof) https://www.youtube.com/watch?v=lA6hE7NFIK0 https://www.youtube.com/watch?v=lA6hE7NFIK0 "How many kinds of infinity are there?" (a very good list including surreals, P-adic, the long line, others) http://vihart.com/how-many-kinds-of-infinity-are-there/ http://vihart.com/how-many-kinds-of-infinity-are-there/ Also, I support her suggestion in "Infinite Trees Are Super Weird" that since we call uncountable line segments the "long line", we should call the uncountably-branching tree the "big tree". https://www.youtube.com/watch?v=BEz-vGJvaik https://www.youtube.com/watch?v=BEz-vGJvaik