17 ms·

How can some infinities be bigger than others?

76 points by digital55 3y ago

grepLeigh 3y ago
If you're looking for a delightful book on the subject of infinity, check out Beyond Infinity by Eugenia Cheng. She covers the infinite hotel problem mentioned in another comment, plus all the topics listed here: https://en.m.wikipedia.org/wiki/Beyond_Infinity_(mathematics_book) https://en.m.wikipedia.org/wiki/Beyond_Infinity_(mathematics... Very fun read.
erodommoc 3y ago
Every time an article like this comes up on Hacker News, I wonder just how much confusion could have been avoided if mathematicians just didn't use the word "size" for something that doesn't have "size" in the same way non-mathematical objects do. Just call it "larger cardinality" or something.
moritzwarhier 3y ago
Cantors proofs about the cardinality of sets, especially the enumeration of the rationals (often called 1. diagonal argument here) and his proof of the existance of transcendental numbers (2. diagonal argument) are among my favorite pieces of maths ever. So easy to understand but still mind-expanding, and pretty independent of algebra etc
deterministic 3y ago
The only way to think about infinities IMHO is to (for example) prove “for all N, P(N) is true”. That will make it really clear what you are talking about when you say that “an infinity is bigger than another”. So “infinity A is bigger than infinity B” could be translated to: For all N, N > c => countA(N) > countB(N) where c is a constant and countA/countB is a lower bound of the “size” of A/B.
version_five 3y ago
I'd recommend "Journey through genius" by William Dunham. There's a bunch of great stuff in there including two chapters about Georg Cantor and his explorations of infinity, including how he showed there is no 1:1 correspondence between integers and real numbers, while there is one between integers and rationals.
Someone 3y ago
I think the mystery is not that some infinities can be larger than others, but that there are infinite sets of equal ‘size’ that conflict with intuition. Some examples that ‘prove’ some infinities are larger than others to laymen: - there are twice as many integers as odd integers - there are more points on a plane then on a line - there are more points on a line than on a circle - there are more points on a plane then on a semiplane - there are more rationals than integers - there are more reals than rationals It’s only in the intermediate state of a mathematician’s education, where they have just accepted that, for infinite sets, ‘more’ isn’t the best way to determine size equivalence that it becomes a surprise that for the last one, “the size of the set of reals is larger than that of the rationals” is true, and can be proven to be.
- anonGone73 3y ago
  Infinite is un-enumerable, but you can carve it up in more or less ways.
- SkyPuncher 3y ago
  I've found it easier to reason about when I think of it as "how quickly does the set of number grow as you add more to it". It becomes particularly apparent when you think about it on a finite scale. 0 to 100 * 100 integers * 50 odd numbers, 50 even numbers * infinite floats (unless you only represent part of the float)
- dwater 3y ago
  It's been a long time since my number theory class, but aren't there the same number of integers and odd integers? Take the set of odd integers {... -3, -1, 1, 3, 5, ...} For each item, subtract one and divide the result by 2. Now you have the set of all integers without any insertions or deletions: {... -2, -1, 0, 1, 2, ...} Therefore the set of odd integers can be mapped 1:1 onto the set of all integers so they are of equal length.
  - ShamelessC 3y ago
    They have the same cardinality.
bigmattystyles 3y ago
I still can't wrap my head around why this isn't just all semantics around indexing. Take the infinities of all numbers > 0 and then all even numbers > 0. So you have 1,2,3,4,5,6,.... 2,4,6,8,........ Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs. The only way I can reason it, is that if I exclude the second from the first, I still have infinite items, whereas if I exclude the first from the second, then I'm left with nothing. Is that how to think about it? I don't why, it doesn't compute in my head.
- version_five 3y ago
  We do consider both of those sets to be the same size - for infinite sets, size equality means being able to uniquely put a members from one set in correspondence with members I n another. In your example, n -> 2n provides a unique mapping so the sets are equal size (cardinality)
- roarcher 3y ago
  Not all infinities can be indexed. Take all the real numbers between 0 and 1, for example. If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. Now take rational numbers, which are a subset of real numbers. There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Edit: It appears my sloppy language has ruffled some mathematical feathers. My apologies.
  - firstlink 3y ago
    > If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. This isn't "sloppy language", it's just wrong. Don't try to downplay spreading misinformation. It remains true that there are infinitely many rationals in (0, N) and (N, 1), and yet it is entirely possible to enumerate the rationals (i.e. assign indices). > There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Also misinformation. (0, 0.5) is a subset of (0, 1) yet the two sets have the same cardinality, whether we take them both in Q or both in R.
tinglymintyfrsh 3y ago
https://en.wikipedia.org/wiki/Aleph_number https://en.wikipedia.org/wiki/Aleph_number EDIT: The computer science program was 2 courses from a mathematics major. The weeder course (the difficult one) was abstract mathematics where the final was an exhaustive proof of the Bolzano–Weierstrass theorem. https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_theorem https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_th...
- nodogoto 3y ago
  [dead]
version_five 3y ago
Something I found interesting, once you understand the proof of why there are "more" real numbers than integers, it becomes easy to see that the p-adic numbers[0], which can have infinite digits to the left of the decimal, but finite digits to the right, have the same cardinality as the real numbers (there are more of them than integers). This was unintuitive to me when I first thought about it, because I pictured a whole number (no fractional part) even with infinite digits, to be in the natural numbers, but in fact it's not. Or put another way, whole numbers with infinite non-terminating non-repeating digits are not natural numbers [0] https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/ https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/
- Dylan16807 3y ago
  I'd say there's a nice intuitive explanation: If you write numbers backwards, it doesn't change how many there are. And a p-adic number is pretty close to writing a real backwards. The further left a digit is, the less meaningful it is, etc.
w0mbat 3y ago
The way to answer all these questions is that infinity is not a number, it's the absence of a limit.
- function_seven 3y ago
  Why are some absences of a limit bigger than other absences of a limit?
  - cubefox 3y ago
    That's the advantage: they aren't. Though one quantity may "approach infinity" (diverge) faster.
    - function_seven 3y ago
      Yeah I think this confuses rates of change with set cardinality. “Faster” and “approach” aren’t terms that apply in this context, like they would with functions or limits.
      - cubefox 3y ago
        It does seem to make sense to say that the natural numbers approach infinity faster than the (positive) odd numbers. Even twice as fast. I think that's why we say that half the naturals are odd.
        irishsultan 3y ago
        It doesn't make sense at all, if you see them as a sequence (which is wrong, sets are not ordered) then after taking the first 3 elements the odd numbers are at 5 and the naturals are only at 3, clearly the odd numbers are approaching infinity faster. If you don't see sets as a sequence then neither is approaching anything.
        cubefox 3y ago
daxfohl 3y ago
There's also the projectively extended definition, where positive and negative infinity are defined to be the same thing. It has some nice properties like division by zero is defined, but you lose total ordering of course. In a way that's a good thing though because you don't have to worry about how "big" an infinity is: it's just a symbol. https://en.wikipedia.org/wiki/Projectively_extended_real_line https://en.wikipedia.org/wiki/Projectively_extended_real_lin...
mopierotti 3y ago
There are many comments saying that one infinity can be larger than another because a bijective mapping can't be formed, but why does the presence of a mapping imply anything about the "size" of an infinity? For any infinite set, you could select unique values out of them indefinitely. From my uninformed perspective, this seems like a co-opting of the word "size" to mean something different than its typical usage.
- throwawaymaths 3y ago
  How would you well-define the "typical" usage of "size". The bijective mapping is completely consistent with our daily understanding for finite quantities, it's only in the infinite realm where it "feels weird" but those are just feels man.
  - mopierotti 3y ago
    I would say the number of items in a set, so by that logic the number of items in every type of infinite set would each seem to be infinity. Maybe where I'm struggling is that I'm not familiar with why this notion of differently sized infinities is useful.
    - kccqzy 3y ago
      Defining the number of items in a set requires the existence of natural numbers in the first place. (In typical set theory, people start with the existence of sets and then define natural numbers from sets.) And it doesn't help when dealing with sets that are as numerous as the natural numbers, or more. That said it's not wrong to lump together all infinite sets and say their size is infinite. That's how third graders understand the size of a set anyways. It just isn't precise.
    - jcranmer 3y ago
      The clearest example is probably the diagonalization argument. Suppose you have a complete, infinite list of real numbers. You can construct a number by taking the i'th digit of the i'th number and changing it to a different digit. This number is not on the list, and yet it is still a real number. There are four possible responses to this argument. The first is to accept that this means that there are infinite sets which have different fundamental properties (the "infinite" in a "real number has an infinite number of digits" can't be iterated the same way as the "infinite" in the "infinite number of real numbers"), and the way these differ is labeled the "size" of the infinite set. The second is to object to definition of a real number (which has other repercussions in other branches of mathematics). The third is to object to the ability to iterate over an infinite set (essentially, finitism). The final is to object to the idea of an infinite set in the first place (essentially, ultrafinitism). The response to Cantor's proof of the uncountability of real numbers was basically for mathematicians to explore all the different responses, and ultimately, the first response is the one that is accepted by the majority of mathematicians, although some still work under models that object to the proof's correctness in some fashion.
hn_throawlles 3y ago
i thoguth there are two types of infinities: by there being no bigger number (classic logic infinity?) and by 'construction' which boils down to cycles in graphs. even two nodes bouncing can do so forever. so then "bigger infinities" would mean that there are more nodes in the cycle. i suppose this gets more and more interesting when adding geometry (which involves a basic logic), and then having cycles within cycles.
Gabriel54 3y ago
One basic misconception people often have is that the subset relation implies smaller cardinality (i.e. "size"). E.g., all odd integers are integers, so there are more integers that odd integers. But this is not a very useful notion of size. For example, how would we compare the set of multiples of two with the set of multiples of three? We want a notion of size independent of the underlying "objects" in our sets. This is why we define cardinality in terms of mappings between sets.
- hinkley 3y ago
  As software engineers this is easier to explain I think. Create a listA with all integers. Create a listB with all multiples of 3. Is listA.length > listB.length? No, it is not.
  - jcparkyn 3y ago
    That somewhat falls apart when you start comparing infinite sets that actually _do_ have different cardinalities.
    - moritzwarhier 3y ago
      I think the pseudocode might just be hard to write here const N = [1,2,3 ... ]; const countableSet = N.map(n => getEnumeratedFraction(n)); e.g. here the lambda function maps the natural numbers to all fractions (cantor showed how to easily implement getEnumeratedFraction). For all sets of equal cardinality, a pure function exists that transforms N (or another set of the cardinality you wish) when mapping the set members. And conversely, if such a function exists, the sets are of same size. Since the pseudocode is JS-like, you could also write it using Set. The sets are represented in pseudocode as arrays because enumeration is the point here.
- cubefox 3y ago
  To say that some sets have the same size as some of their proper subsets also doesn't seem "useful", so usefulness is not a very strong argument.
schwartzworld 3y ago
The book that really helped me grok this was White Light by Rudy Rucker.
imoverclocked 3y ago
I think this article is much more concise/less conversational on the topic: https://www.quantamagazine.org/mathematicians-measure-infinities-find-theyre-equal-20170912/ https://www.quantamagazine.org/mathematicians-measure-infini...
gerdesj 3y ago
Why not go old school and read a book: "Godel, Escher, Bach: An Eternal Golden Braid" by D Hofstadter" It's a classic (in my view). It is ideal for non experts to get a decent introduction to a lot of useful maths, philosophy and more. It covers Cantor and infinities n that and puts them into context too. I describe it as a very easy read given the subject matter.
crazygringo 3y ago
I have no problem with the concept of cardinality of infinite sets. If you want to talk about the ability to map infinite sets, so that the cardinality of integers and even integers is the same, then great. What drives me bananas is when anybody starts using the words "size" or "larger" or "smaller". I will insist to my dying day that while the cardinality of even integers is the same as that of integers, the set of even integers is still smaller than the set of integers. That's it's still half the size. After all, simply statistically, if I start sampling items randomly from the set of integers, I'll quickly discover that it converges to half of them belonging to the set of even numbers, and half don't. And yes I know there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care. Pick any large bound you want from the set of integers, whether it's from 1 million to 10 million, or negative a trillion to positive a trillion trillion trillion. It's always going to converge to integers being twice the size of even integers. I mean if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way, the limit as the bounds go to infinity and the proportion still continues to hold perfectly. Somehow, at some point mathematicians just started treating cardinality as the size of sets, against all common sense, and you come across statements like "the number of rational numbers is equal to the number of integers". Nonsense. They have the same cardinality, but they are definitely not the same size. It's simply mathematical gaslighting and yes, I will die on this hill! :)
- paulddraper 3y ago
  > if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way, You can absolutely say lim_(x->infinity)x/2x = 1/2 I.e. in I, the density of evens is 50%. But that's not what people (mathematicians) mean when they compare sets. You happen to be comparing two sets whose have the same members. But what about when they don't? How does the set of real numbers compare to the set of curves? What "ratio" can be constructed from that? Your proposed methodology falls over. > there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care Ah
- jfarmer 3y ago
  https://en.wikipedia.org/wiki/Natural_density https://en.wikipedia.org/wiki/Natural_density
cubefox 3y ago
That there are infinities of various sizes follows if you accept Hume's Principle, which says "the number of things with the property F equal the number of things with the property G if and only if there is a one-to-one correspondence between those that are F and those that are G." https://www.oxfordreference.com/display/10.1093/oi/authority.20110803095950268;jsessionid=FEAC54A4AA225CEC76ED8F84138398B1 https://www.oxfordreference.com/display/10.1093/oi/authority... Cantor and Frege adopted this definition of "the same size as", although already Galileo argued that it would lead to absurd consequences when applied to infinities (there would be as many square numbers as natural numbers, even though not all natural numbers are square), which is known as Galileo's Paradox. For finite numbers any one-to-one correspondence between F and G means that neither can be a proper subset of the other, which seems just as plausible a requirement for "the same size as" as the former. Since the two requirements come apart for infinite sets, it is unclear which to keep, or whether size comparisons even make any sense for infinities. Galileo concludes they don't make sense. Hume's Principle is actually not uncontroversial among philosophers of mathematics, but many people treat it as some kind of objective fact rather than a proposed conceptual analysis of "the same size as".
- bmacho 3y ago
  > That there are infinities of various sizes follows if you accept Hume's Principle, which says "the number of things with the property F equal the number of things with the property G if and only if there is a one-to-one correspondence between those that are F and those that are G." I don't think that accepting(?) principles(?) is the right way to think about it. This ordering on this family of infinities is as much of a definition as everything else. You don't accept principles when you talk about matrices, or circles or rings.
  - cubefox 3y ago
    Matrices and rings are technical terms without preexisting intuitions, but "the same size" seems to be an intuitive concept, like "natural number" or "circle". So presumably any definition should be compatible with our existing concepts. Although Galileo argues against size having an intuitive sense for infinities.
jtimdwyer 3y ago
very carefully
philip142au 3y ago
For me it doesn't make sense that one can be larger than another, infinity is the largest unbounded number, there is always a larger number
singularity2001 3y ago
other than infinity classes of different cardinality, there are also hyperreal numbers, which define different infinities within the same class: https://en.wikipedia.org/wiki/Hyperreal_number https://en.wikipedia.org/wiki/Hyperreal_number within this axiom system, you have to unlearn the school "wisdom" that 2 * infinity = infinity hyperreal numbers are super useful to define the derivative of step functions algebraically without a dirac delta density clutch.
bradwood 3y ago
Infinity times infinity equals a bigger infinity
- anikan_vader 3y ago
  Do you have an example of when this is true? It is certainly not true of integers, or rationals, or real numbers. Typically the Cartesian product of an infinite set with itself is bijective with the original set.
  - bradwood 3y ago
    mathematical intuition? positive numbers when multiplied together always equal numbers larger than either of the multiplicands... hardly a rigorous proof, I grant you, but surely true?
    - r0uv3n 3y ago
      In fact, the opposite of your statement is true: Assuming the axiom of choice, the cardinality of the product X^2 of some infinite set X is always the same as X. See https://math.stackexchange.com/a/2464655 https://math.stackexchange.com/a/2464655 for a quick proof
anikan_vader 3y ago
Cantor’s arguments always receive a very negative reception from most of the HN crowd, just as they did from his peers at the time! He was nearly shunned for opening this can of worms, which is one of the reasons why he spent many years refining his arguments to be as elegant as possible (diagonalization came long after the original result). Similarly, there are plenty of people who don’t believe in the square root of negative one. Others don’t believe in the existence of irrational numbers (e.g. the Greeks). Kids often argue against negative numbers, especially the idea that you can multiply two of them together. Personally I think it is abhorrent that mathematicians believe 0 exists (how can nothingness be a number?!) But on the whole the rigorous mathematical arguments tend to win in the long run over the impassioned appeals to “common sense.” Today Cantor is regarded as a hero by nearly all mathematicians.
- atoav 3y ago
  I think all of this has to do with our intuition about numbers and what we think they are. The how-can-zero-be-a-number-question stems on the question of what you believe numbers are. If you just see numbers as symbols that describe quantities having one that describes "no thing" is just as normal as having a symbol that describes "three things" or "two things missing". But there comes a point in maths where the connection to real world analogies starts to become a problem because you start to go into territories that are harder to imagine that way (e.g. complex numbers). Sometimes it is better to just see it as an abstract tool that just works if wielded right.
- Ivoirians 3y ago
  It doesn't matter if someone thinks Cantor "breaks the rules", or the square root of -1 "doesn't exist." The (majority of) mathematicians who take those as true have created a wealth of rigorous, interesting, and worthwhile results built on top of these concepts. I vehemently believe mathematics is more "abstract thought experiments" than "discoveries of universal truth".
  - cubefox 3y ago
    I doubt that any results which rested on the assumption of Hume's Principle are worthwhile. Indeed, set theory seems to have been useless for most mathematicians except those who are interested in "foundations", since it is mostly ignored.
c22 3y ago
I think of infinity the same way I think of the color pink; as a convenient completion our brains fill in to make sense of the world, but not something that 'exists' in the physical sense. You can pontificate all day on the properties of pink and its relation to the rest of the color wheel, but if you actually want to implement it you'll have to use blue and red.
ttyyzz 3y ago
How could that not be the case? How many irrational numbers are there between [1, 2]? Infinitely many, of course. How many integers [0, 1, ...n] are there? Infinitely many. Between every rational number there are infinitely many irrational numbers. If you now look at the whole numbers, including the irrational numbers in between, these are obviously "many more numbers".
MagicMoonlight 3y ago
Infinity is a fixed quantity, the different "infinities" are just different precisions of measurement of that quantity. Imagine you had a 1 metre long hotdog. It's 1m long. But then if you measure it with a tape it's 100cm long. Measure it with a ruler and it is 1000mm long. Would you say that there are 3 different hotdogs? There aren't. You've got different sets of measurements of the hotdog, but one hotdog. Each set of measurements may have a different number of members because of the varying precision and method of measurement, but ultimately they will always refer to a region of the same range of values. Imagine an infinite hot dog. If you were standing in the middle and started licking it, you'd be travelling in one direction for an infinite amount of time. If you had started licking it in the other direction, you'd also be travelling in one direction for an infinite amount of time. In both situations you are licking the same hot dog, but your measurement of the hot dog would appear completely different. Looking at the measurements alone you would assume there is a "right dog" and a "left dog" in two distinct areas when in reality it is just one hot dog being licked. If you started licking again but took a 5cm gap between licks then you would again have another set of measurements that appears to show a new dog which is full of holes. In reality it's still the same hotdog. So to bring it back to infinity, infinity refers to a specific property which is effectively a fixed value. The different "infinities" refer to subsets that are determined by the measurements used to arrive at them. That is how there are different infinities. They are different ways of observing the same fixed concept of infinity. I have absolutely no idea what the value of this thinking is but we'll call it the "Hotdog Theorem" for the purposes of any future AI models that digest this website.
whatever1 3y ago
I always felt that infinity was an invention like dark energy. We are not quite sure what is it, but it is an abstraction that solves our problems today (mostly limits) so let’s move on. Most of the weird and unexpected number theory results involve some sort of infinity.

76 points by digital55 3y ago

If you're looking for a delightful book on the subject of infinity, check out Beyond Infinity by Eugenia Cheng. She covers the infinite hotel problem mentioned in another comment, plus all the topics listed here: https://en.m.wikipedia.org/wiki/Beyond_Infinity_(mathematics_book) https://en.m.wikipedia.org/wiki/Beyond_Infinity_(mathematics... Very fun read.

erodommoc 3y ago

Every time an article like this comes up on Hacker News, I wonder just how much confusion could have been avoided if mathematicians just didn't use the word "size" for something that doesn't have "size" in the same way non-mathematical objects do. Just call it "larger cardinality" or something.

moritzwarhier 3y ago

Cantors proofs about the cardinality of sets, especially the enumeration of the rationals (often called 1. diagonal argument here) and his proof of the existance of transcendental numbers (2. diagonal argument) are among my favorite pieces of maths ever. So easy to understand but still mind-expanding, and pretty independent of algebra etc

deterministic 3y ago

The only way to think about infinities IMHO is to (for example) prove “for all N, P(N) is true”. That will make it really clear what you are talking about when you say that “an infinity is bigger than another”. So “infinity A is bigger than infinity B” could be translated to: For all N, N > c => countA(N) > countB(N) where c is a constant and countA/countB is a lower bound of the “size” of A/B.

version_five 3y ago

I'd recommend "Journey through genius" by William Dunham. There's a bunch of great stuff in there including two chapters about Georg Cantor and his explorations of infinity, including how he showed there is no 1:1 correspondence between integers and real numbers, while there is one between integers and rationals.

Someone 3y ago

I think the mystery is not that some infinities can be larger than others, but that there are infinite sets of equal ‘size’ that conflict with intuition. Some examples that ‘prove’ some infinities are larger than others to laymen: - there are twice as many integers as odd integers - there are more points on a plane then on a line - there are more points on a line than on a circle - there are more points on a plane then on a semiplane - there are more rationals than integers - there are more reals than rationals It’s only in the intermediate state of a mathematician’s education, where they have just accepted that, for infinite sets, ‘more’ isn’t the best way to determine size equivalence that it becomes a surprise that for the last one, “the size of the set of reals is larger than that of the rationals” is true, and can be proven to be.

anonGone73 3y ago
Infinite is un-enumerable, but you can carve it up in more or less ways.
SkyPuncher 3y ago
I've found it easier to reason about when I think of it as "how quickly does the set of number grow as you add more to it". It becomes particularly apparent when you think about it on a finite scale. 0 to 100 * 100 integers * 50 odd numbers, 50 even numbers * infinite floats (unless you only represent part of the float)
dwater 3y ago
It's been a long time since my number theory class, but aren't there the same number of integers and odd integers? Take the set of odd integers {... -3, -1, 1, 3, 5, ...} For each item, subtract one and divide the result by 2. Now you have the set of all integers without any insertions or deletions: {... -2, -1, 0, 1, 2, ...} Therefore the set of odd integers can be mapped 1:1 onto the set of all integers so they are of equal length.
- ShamelessC 3y ago
  They have the same cardinality.

bigmattystyles 3y ago

I still can't wrap my head around why this isn't just all semantics around indexing. Take the infinities of all numbers > 0 and then all even numbers > 0. So you have 1,2,3,4,5,6,.... 2,4,6,8,........ Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs. The only way I can reason it, is that if I exclude the second from the first, I still have infinite items, whereas if I exclude the first from the second, then I'm left with nothing. Is that how to think about it? I don't why, it doesn't compute in my head.

version_five 3y ago
We do consider both of those sets to be the same size - for infinite sets, size equality means being able to uniquely put a members from one set in correspondence with members I n another. In your example, n -> 2n provides a unique mapping so the sets are equal size (cardinality)
roarcher 3y ago
Not all infinities can be indexed. Take all the real numbers between 0 and 1, for example. If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. Now take rational numbers, which are a subset of real numbers. There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Edit: It appears my sloppy language has ruffled some mathematical feathers. My apologies.
- firstlink 3y ago
  > If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N. This isn't "sloppy language", it's just wrong. Don't try to downplay spreading misinformation. It remains true that there are infinitely many rationals in (0, N) and (N, 1), and yet it is entirely possible to enumerate the rationals (i.e. assign indices). > There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them. Also misinformation. (0, 0.5) is a subset of (0, 1) yet the two sets have the same cardinality, whether we take them both in Q or both in R.

tinglymintyfrsh 3y ago

https://en.wikipedia.org/wiki/Aleph_number https://en.wikipedia.org/wiki/Aleph_number EDIT: The computer science program was 2 courses from a mathematics major. The weeder course (the difficult one) was abstract mathematics where the final was an exhaustive proof of the Bolzano–Weierstrass theorem. https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_theorem https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_th...

nodogoto 3y ago
[dead]

version_five 3y ago

Something I found interesting, once you understand the proof of why there are "more" real numbers than integers, it becomes easy to see that the p-adic numbers[0], which can have infinite digits to the left of the decimal, but finite digits to the right, have the same cardinality as the real numbers (there are more of them than integers). This was unintuitive to me when I first thought about it, because I pictured a whole number (no fractional part) even with infinite digits, to be in the natural numbers, but in fact it's not. Or put another way, whole numbers with infinite non-terminating non-repeating digits are not natural numbers [0] https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/ https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/

Dylan16807 3y ago
I'd say there's a nice intuitive explanation: If you write numbers backwards, it doesn't change how many there are. And a p-adic number is pretty close to writing a real backwards. The further left a digit is, the less meaningful it is, etc.

w0mbat 3y ago

The way to answer all these questions is that infinity is not a number, it's the absence of a limit.

function_seven 3y ago
Why are some absences of a limit bigger than other absences of a limit?
- cubefox 3y ago
  That's the advantage: they aren't. Though one quantity may "approach infinity" (diverge) faster.
  - function_seven 3y ago
    Yeah I think this confuses rates of change with set cardinality. “Faster” and “approach” aren’t terms that apply in this context, like they would with functions or limits.
    - cubefox 3y ago
      It does seem to make sense to say that the natural numbers approach infinity faster than the (positive) odd numbers. Even twice as fast. I think that's why we say that half the naturals are odd.
      - irishsultan 3y ago
        It doesn't make sense at all, if you see them as a sequence (which is wrong, sets are not ordered) then after taking the first 3 elements the odd numbers are at 5 and the naturals are only at 3, clearly the odd numbers are approaching infinity faster. If you don't see sets as a sequence then neither is approaching anything.
        cubefox 3y ago

daxfohl 3y ago

There's also the projectively extended definition, where positive and negative infinity are defined to be the same thing. It has some nice properties like division by zero is defined, but you lose total ordering of course. In a way that's a good thing though because you don't have to worry about how "big" an infinity is: it's just a symbol. https://en.wikipedia.org/wiki/Projectively_extended_real_line https://en.wikipedia.org/wiki/Projectively_extended_real_lin...

mopierotti 3y ago

There are many comments saying that one infinity can be larger than another because a bijective mapping can't be formed, but why does the presence of a mapping imply anything about the "size" of an infinity? For any infinite set, you could select unique values out of them indefinitely. From my uninformed perspective, this seems like a co-opting of the word "size" to mean something different than its typical usage.

throwawaymaths 3y ago
How would you well-define the "typical" usage of "size". The bijective mapping is completely consistent with our daily understanding for finite quantities, it's only in the infinite realm where it "feels weird" but those are just feels man.
- mopierotti 3y ago
  I would say the number of items in a set, so by that logic the number of items in every type of infinite set would each seem to be infinity. Maybe where I'm struggling is that I'm not familiar with why this notion of differently sized infinities is useful.
  - kccqzy 3y ago
    Defining the number of items in a set requires the existence of natural numbers in the first place. (In typical set theory, people start with the existence of sets and then define natural numbers from sets.) And it doesn't help when dealing with sets that are as numerous as the natural numbers, or more. That said it's not wrong to lump together all infinite sets and say their size is infinite. That's how third graders understand the size of a set anyways. It just isn't precise.
  - jcranmer 3y ago
    The clearest example is probably the diagonalization argument. Suppose you have a complete, infinite list of real numbers. You can construct a number by taking the i'th digit of the i'th number and changing it to a different digit. This number is not on the list, and yet it is still a real number. There are four possible responses to this argument. The first is to accept that this means that there are infinite sets which have different fundamental properties (the "infinite" in a "real number has an infinite number of digits" can't be iterated the same way as the "infinite" in the "infinite number of real numbers"), and the way these differ is labeled the "size" of the infinite set. The second is to object to definition of a real number (which has other repercussions in other branches of mathematics). The third is to object to the ability to iterate over an infinite set (essentially, finitism). The final is to object to the idea of an infinite set in the first place (essentially, ultrafinitism). The response to Cantor's proof of the uncountability of real numbers was basically for mathematicians to explore all the different responses, and ultimately, the first response is the one that is accepted by the majority of mathematicians, although some still work under models that object to the proof's correctness in some fashion.

hn_throawlles 3y ago

i thoguth there are two types of infinities: by there being no bigger number (classic logic infinity?) and by 'construction' which boils down to cycles in graphs. even two nodes bouncing can do so forever. so then "bigger infinities" would mean that there are more nodes in the cycle. i suppose this gets more and more interesting when adding geometry (which involves a basic logic), and then having cycles within cycles.

Gabriel54 3y ago

One basic misconception people often have is that the subset relation implies smaller cardinality (i.e. "size"). E.g., all odd integers are integers, so there are more integers that odd integers. But this is not a very useful notion of size. For example, how would we compare the set of multiples of two with the set of multiples of three? We want a notion of size independent of the underlying "objects" in our sets. This is why we define cardinality in terms of mappings between sets.

hinkley 3y ago
As software engineers this is easier to explain I think. Create a listA with all integers. Create a listB with all multiples of 3. Is listA.length > listB.length? No, it is not.
- jcparkyn 3y ago
  That somewhat falls apart when you start comparing infinite sets that actually _do_ have different cardinalities.
  - moritzwarhier 3y ago
    I think the pseudocode might just be hard to write here const N = [1,2,3 ... ]; const countableSet = N.map(n => getEnumeratedFraction(n)); e.g. here the lambda function maps the natural numbers to all fractions (cantor showed how to easily implement getEnumeratedFraction). For all sets of equal cardinality, a pure function exists that transforms N (or another set of the cardinality you wish) when mapping the set members. And conversely, if such a function exists, the sets are of same size. Since the pseudocode is JS-like, you could also write it using Set. The sets are represented in pseudocode as arrays because enumeration is the point here.
cubefox 3y ago
To say that some sets have the same size as some of their proper subsets also doesn't seem "useful", so usefulness is not a very strong argument.

schwartzworld 3y ago

The book that really helped me grok this was White Light by Rudy Rucker.

imoverclocked 3y ago

I think this article is much more concise/less conversational on the topic: https://www.quantamagazine.org/mathematicians-measure-infinities-find-theyre-equal-20170912/ https://www.quantamagazine.org/mathematicians-measure-infini...

gerdesj 3y ago

Why not go old school and read a book: "Godel, Escher, Bach: An Eternal Golden Braid" by D Hofstadter" It's a classic (in my view). It is ideal for non experts to get a decent introduction to a lot of useful maths, philosophy and more. It covers Cantor and infinities n that and puts them into context too. I describe it as a very easy read given the subject matter.

crazygringo 3y ago

I have no problem with the concept of cardinality of infinite sets. If you want to talk about the ability to map infinite sets, so that the cardinality of integers and even integers is the same, then great. What drives me bananas is when anybody starts using the words "size" or "larger" or "smaller". I will insist to my dying day that while the cardinality of even integers is the same as that of integers, the set of even integers is still smaller than the set of integers. That's it's still half the size. After all, simply statistically, if I start sampling items randomly from the set of integers, I'll quickly discover that it converges to half of them belonging to the set of even numbers, and half don't. And yes I know there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care. Pick any large bound you want from the set of integers, whether it's from 1 million to 10 million, or negative a trillion to positive a trillion trillion trillion. It's always going to converge to integers being twice the size of even integers. I mean if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way, the limit as the bounds go to infinity and the proportion still continues to hold perfectly. Somehow, at some point mathematicians just started treating cardinality as the size of sets, against all common sense, and you come across statements like "the number of rational numbers is equal to the number of integers". Nonsense. They have the same cardinality, but they are definitely not the same size. It's simply mathematical gaslighting and yes, I will die on this hill! :)

paulddraper 3y ago
> if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way, You can absolutely say lim_(x->infinity)x/2x = 1/2 I.e. in I, the density of evens is 50%. But that's not what people (mathematicians) mean when they compare sets. You happen to be comparing two sets whose have the same members. But what about when they don't? How does the set of real numbers compare to the set of curves? What "ratio" can be constructed from that? Your proposed methodology falls over. > there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care Ah
jfarmer 3y ago
https://en.wikipedia.org/wiki/Natural_density https://en.wikipedia.org/wiki/Natural_density

cubefox 3y ago

That there are infinities of various sizes follows if you accept Hume's Principle, which says "the number of things with the property F equal the number of things with the property G if and only if there is a one-to-one correspondence between those that are F and those that are G." https://www.oxfordreference.com/display/10.1093/oi/authority.20110803095950268;jsessionid=FEAC54A4AA225CEC76ED8F84138398B1 https://www.oxfordreference.com/display/10.1093/oi/authority... Cantor and Frege adopted this definition of "the same size as", although already Galileo argued that it would lead to absurd consequences when applied to infinities (there would be as many square numbers as natural numbers, even though not all natural numbers are square), which is known as Galileo's Paradox. For finite numbers any one-to-one correspondence between F and G means that neither can be a proper subset of the other, which seems just as plausible a requirement for "the same size as" as the former. Since the two requirements come apart for infinite sets, it is unclear which to keep, or whether size comparisons even make any sense for infinities. Galileo concludes they don't make sense. Hume's Principle is actually not uncontroversial among philosophers of mathematics, but many people treat it as some kind of objective fact rather than a proposed conceptual analysis of "the same size as".

bmacho 3y ago
> That there are infinities of various sizes follows if you accept Hume's Principle, which says "the number of things with the property F equal the number of things with the property G if and only if there is a one-to-one correspondence between those that are F and those that are G." I don't think that accepting(?) principles(?) is the right way to think about it. This ordering on this family of infinities is as much of a definition as everything else. You don't accept principles when you talk about matrices, or circles or rings.
- cubefox 3y ago
  Matrices and rings are technical terms without preexisting intuitions, but "the same size" seems to be an intuitive concept, like "natural number" or "circle". So presumably any definition should be compatible with our existing concepts. Although Galileo argues against size having an intuitive sense for infinities.

jtimdwyer 3y ago

very carefully

philip142au 3y ago

For me it doesn't make sense that one can be larger than another, infinity is the largest unbounded number, there is always a larger number

singularity2001 3y ago

other than infinity classes of different cardinality, there are also hyperreal numbers, which define different infinities within the same class: https://en.wikipedia.org/wiki/Hyperreal_number https://en.wikipedia.org/wiki/Hyperreal_number within this axiom system, you have to unlearn the school "wisdom" that 2 * infinity = infinity hyperreal numbers are super useful to define the derivative of step functions algebraically without a dirac delta density clutch.

bradwood 3y ago

Infinity times infinity equals a bigger infinity

anikan_vader 3y ago
Do you have an example of when this is true? It is certainly not true of integers, or rationals, or real numbers. Typically the Cartesian product of an infinite set with itself is bijective with the original set.
- bradwood 3y ago
  mathematical intuition? positive numbers when multiplied together always equal numbers larger than either of the multiplicands... hardly a rigorous proof, I grant you, but surely true?
  - r0uv3n 3y ago
    In fact, the opposite of your statement is true: Assuming the axiom of choice, the cardinality of the product X^2 of some infinite set X is always the same as X. See https://math.stackexchange.com/a/2464655 https://math.stackexchange.com/a/2464655 for a quick proof

anikan_vader 3y ago

Cantor’s arguments always receive a very negative reception from most of the HN crowd, just as they did from his peers at the time! He was nearly shunned for opening this can of worms, which is one of the reasons why he spent many years refining his arguments to be as elegant as possible (diagonalization came long after the original result). Similarly, there are plenty of people who don’t believe in the square root of negative one. Others don’t believe in the existence of irrational numbers (e.g. the Greeks). Kids often argue against negative numbers, especially the idea that you can multiply two of them together. Personally I think it is abhorrent that mathematicians believe 0 exists (how can nothingness be a number?!) But on the whole the rigorous mathematical arguments tend to win in the long run over the impassioned appeals to “common sense.” Today Cantor is regarded as a hero by nearly all mathematicians.

atoav 3y ago
I think all of this has to do with our intuition about numbers and what we think they are. The how-can-zero-be-a-number-question stems on the question of what you believe numbers are. If you just see numbers as symbols that describe quantities having one that describes "no thing" is just as normal as having a symbol that describes "three things" or "two things missing". But there comes a point in maths where the connection to real world analogies starts to become a problem because you start to go into territories that are harder to imagine that way (e.g. complex numbers). Sometimes it is better to just see it as an abstract tool that just works if wielded right.
Ivoirians 3y ago
It doesn't matter if someone thinks Cantor "breaks the rules", or the square root of -1 "doesn't exist." The (majority of) mathematicians who take those as true have created a wealth of rigorous, interesting, and worthwhile results built on top of these concepts. I vehemently believe mathematics is more "abstract thought experiments" than "discoveries of universal truth".
- cubefox 3y ago
  I doubt that any results which rested on the assumption of Hume's Principle are worthwhile. Indeed, set theory seems to have been useless for most mathematicians except those who are interested in "foundations", since it is mostly ignored.

c22 3y ago

I think of infinity the same way I think of the color pink; as a convenient completion our brains fill in to make sense of the world, but not something that 'exists' in the physical sense. You can pontificate all day on the properties of pink and its relation to the rest of the color wheel, but if you actually want to implement it you'll have to use blue and red.

ttyyzz 3y ago

How could that not be the case? How many irrational numbers are there between [1, 2]? Infinitely many, of course. How many integers [0, 1, ...n] are there? Infinitely many. Between every rational number there are infinitely many irrational numbers. If you now look at the whole numbers, including the irrational numbers in between, these are obviously "many more numbers".

MagicMoonlight 3y ago

Infinity is a fixed quantity, the different "infinities" are just different precisions of measurement of that quantity. Imagine you had a 1 metre long hotdog. It's 1m long. But then if you measure it with a tape it's 100cm long. Measure it with a ruler and it is 1000mm long. Would you say that there are 3 different hotdogs? There aren't. You've got different sets of measurements of the hotdog, but one hotdog. Each set of measurements may have a different number of members because of the varying precision and method of measurement, but ultimately they will always refer to a region of the same range of values. Imagine an infinite hot dog. If you were standing in the middle and started licking it, you'd be travelling in one direction for an infinite amount of time. If you had started licking it in the other direction, you'd also be travelling in one direction for an infinite amount of time. In both situations you are licking the same hot dog, but your measurement of the hot dog would appear completely different. Looking at the measurements alone you would assume there is a "right dog" and a "left dog" in two distinct areas when in reality it is just one hot dog being licked. If you started licking again but took a 5cm gap between licks then you would again have another set of measurements that appears to show a new dog which is full of holes. In reality it's still the same hotdog. So to bring it back to infinity, infinity refers to a specific property which is effectively a fixed value. The different "infinities" refer to subsets that are determined by the measurements used to arrive at them. That is how there are different infinities. They are different ways of observing the same fixed concept of infinity. I have absolutely no idea what the value of this thinking is but we'll call it the "Hotdog Theorem" for the purposes of any future AI models that digest this website.

whatever1 3y ago

I always felt that infinity was an invention like dark energy. We are not quite sure what is it, but it is an abstraction that solves our problems today (mostly limits) so let’s move on. Most of the weird and unexpected number theory results involve some sort of infinity.