13 ms·

Why Some Infinities Are Bigger Than Others

55 points by prostoalex 5y ago

crazygringo 5y ago
The idea of "differently sized infinities" has always felt like a mathematical game to me. The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? It seems more like an almost arbitrary puzzle than "fact". I don't disagree with any of the proofs or reasoning... it just kinda bugs me that the way the formal cardinality of infinite sets is communicated is as the commonsense notion of "size". When we make statements such as the size of the set of all natural numbers 1, 2, 3... is the same as the size of the set of all natural even numbers 2, 4, 6..., despite the former containing the latter but not vice-versa... it seems the word "size" -- and associated terminology "larger than", "smaller than", etc. -- is a particularly unhelpful set of words to have chosen for this. The reason I think this is important is because if you go to e.g. the Wikipedia page for "irrational number", it states in the introduction [1]: > "As a consequence of Cantor's proof that the real numbers are uncountable and the rationals countable, it follows that almost all real numbers are irrational." But it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational, as if it had any analogy whatsover to a statement such as e.g. "almost all" values of 1/x are defined. Am I missing anything here? I've never heard of any natural practical application of this concept, in a way that suggests it's "true" in the same way algebra and calculus are considered to be. [1] https://en.wikipedia.org/wiki/Irrational_number https://en.wikipedia.org/wiki/Irrational_number
- lhorie 5y ago
  This seems like just an observation about the less formal nature of colloquial language. We also say things like "70% of people do X", when in actuality the underlying study "extrapolates" from a smaller population via statistical analysis. All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time.
  - mrkramer 5y ago
    >We also say things like "70% of people do X", when in actuality the underlying study "extrapolates" from a smaller population via statistical analysis. Isn't that approximation because we will never really know how many people exactly do X. >All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time. Are they overloading the meaning of "size" or offloading it? Because again nobody really knows what real size or cardinality of anything is so they offload it to some other future term or meaning just like you said "which is one well known mechanism that cause mutations in languages over time." I'm not a mathematician but I heard from them say that it is better to use word unbounded than infinite because infinities are tricky.
- openasocket 5y ago
  Here, terms like "almost all" come to us from measure theory (and its application to probability theory), which tries to define a general notion of the size or volume of sets.
- philipov 5y ago
  I think the problem is that infinity doesn't exist in real life. We don't have access to unbounded quantities, so any discussion of them is necessarily going to be more abstract than the notions we're used to dealing with. The results may be unintuitive, but they follow from very intuitive ways of doing counting. Two piles of rocks are the same size if you can line them up so each rock from one pile matches with a rock from the other pile. But once you combine that with mathematical induction, you start getting into the realm of objects that don't exist in real life and it starts looking weird. I think there's an easy way to draw an analogy between the statements that "almost all" real numbers are irrational and "almost all" values of 1/x are defined. If you were to pick a random real number from the domain of 1/x, the chances of picking one for which 1/x is undefined approaches zero. Similarly, if you pick a random real number, the chances of picking a rational one approaches zero.
  - TuringTest 5y ago
    > We don't have access to unbounded quantities, so any discussion of them is necessarily going to be more abstract than the notions we're used to dealing with. I've always thought of infinite as very concrete unbounded processes, rather than quantities (but then, I'm a computer scientist, not a mathematician). You cannot count the size of an infinite set because you can never stop counting; the process goes on and on. So the way to compare infinities is to map things between them. If you can map all elements from the first infinite to the second, but not the other way around, the second is larger than the first. It makes sense as to define this process as the way to compare sizes, since actually counting all their items is ruled out. "Almost all" elements of an infinite set could be defined similarly, if for each item without a particular property you can create a limitless variety of different items with it.
    - jobigoud 5y ago
      > If you can map all elements from the first infinite to the second, but not the other way around, the second is larger than the first. This seems simple enough but it's still very much counter intuitive when comparing say all the natural numbers with only the even numbers. An intuitive mapping would lead you to think there are more naturals than evens, but math says these two infinites are of the same size.
- js6i 5y ago
  > When we make statements such as the size of the set of all natural numbers 1, 2, 3... is the same as the size of the set of all natural even numbers 2, 4, 6..., despite the former containing the latter but not vice-versa... it seems the word "size" -- and associated terminology "larger than", "smaller than", etc. -- is a particularly unhelpful set of words to have chosen for this. It seems to me, when you're counting things, you wouldn't care what are the things you're counting specifically; while in your example it does matter for determining the subset relation. Whatever way of counting where it matters would be kind of weird. > it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational But the article uses "almost all" in the formal sense? Which, by the way, also has pretty intuitive meaning, in my opinion.
  - vitus 5y ago
    > But the article uses "almost all" in the formal sense? Which, by the way, also has pretty intuitive meaning, in my opinion. By formal sense, do you mean everywhere but a finite-measure set? Zero-measure? I'll use finite-measure because it allows for intuitive constructions like "almost all real numbers are outside the closed unit interval 0 <= x <= 1". But, there are still some constructions that a layperson might expect to hold, like: "almost all real numbers have fractional part < 1e-100", or "almost all positive numbers are of the form x.y with 0.y < 1/x" (thanks, harmonic series). I think that without formal training, we're especially bad at reasoning about dense sets such as the set of rational numbers, compared to, say, the reals.
    - js6i 5y ago
      Maybe not the most formal of meanings, but my favorite is a probabilistic one: given a random element, how likely it is that it satisfies a predicate? If some elements don't, but it's still satisfied with probability 1, that's pretty clearly almost always. EDIT: yeah you guys are right, I wouldn't worry too much about the prior not being a proper distribution, but still - this doesn't seem related to the cardinality of sets in a simple way after all!
- thaumasiotes 5y ago
  > But it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational, as if it had any analogy whatsover to a statement such as e.g. "almost all" values of 1/x are defined. What's the objection? Almost all values of 1/x are defined. The analogy is... it's the same usage with the same meaning. That's not even an analogy.
  - canjobear 5y ago
    Almost none of the numbers of the form 1/x have definitions. Definitions have finite length, so there is only a countable number of numbers with definitions. But there are uncountable number of numbers of the form 1/x.
  - crazygringo 5y ago
    No, it's an entirely different meaning. Because yes, almost all values of 1/x are defined -- for every real value of x except for one, the number zero. While saying "almost all" real numbers are irrational... is saying that real values are all irrational, except for... the entire infinitely large set of rational numbers. The idea of "almost all" and "except for an infinite number of items" is not even close to the same commonsense meaning, not even remotely. That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly.
    - Dylan16807 5y ago
      I could also mathematically say that "almost all" integers are not powers of 58279. I think that would fit the commonsense meaning, even though there are infinite counterexamples.
    - tshaddox 5y ago
      > While saying "almost all" real numbers are irrational... is saying that real values are all irrational, except for... the entire infinitely large set of rational numbers. You're claiming that the precise mathematical definitions of these terms are ridiculous, and then just repeating those mathematical definitions of the terms to support your claim. > That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly. The whole point is that when you're comparing infinite sets, common sense terms like "size," "almost all," etc. don't make any sense at all, so mathematicians create precise definitions for the terms that are then used among all mathematicians and do make sense. These terms are common among mathematicians and they do make sense. The fact that these definitions don't precisely match the definitions used by non-mathematicians is precisely the goal, because those definitions make no sense whatsoever when referring to infinite sets. It's okay to complain about using jargon in discussions not related to mathematics, although that's not what is happening here (and it's difficult to imagine a conversation about infinite sets that is not also about mathematics). This complaint is comparable to complaining that the definitions of "sharp" and "flat" in music theory don't at all match the definitions of "sharp" and "flat" used in conversations not about music. I suppose another way to approach this is to ask what you would propose the term "almost all" to mean when referring to an infinite set? For that matter, what do you propose that the term "almost all" means to a layperson referring to small finite sets? What percentage do you need in order to use "almost all"?
- bitwize 5y ago
  It's because they kinda follow the same rules as finitely sized sets. Say you have two sets: A and B. A has five elements and B has seven. That means that for each element in A there is a unique corresponding element in B, but the reverse is not true: B has elements that do not map to elements in A. OK, now say A is the set of integers, and B is the set of points on the x-axis. Same deal applies, you can map every integer to a point on the x-axis and still have points on the x-axis that do not map to integers. So we've formalized infinite sets in a way that preserves our intuitive notion of what it means to have more or less of something, without having to count or measure the sets which would be bloody impossible! Yes, it's a game but so is all of math! As for "almost all", in statistics we have this notion of "almost surely", which is formally defined as "with probability 1". It turns out that a probability of 1 doesn't guarantee that something will happen, because 1 less an infinitesimal is still 1! So roll a spherical die that yields a real number between 0 and 1; if you roll a 0, you lose. The probability that you will win is still 1, but you might still roll that goose egg! So we say that you will "almost surely" win at this game. If you think of rational and real numbers in terms of our two sets with different cardinalities, not only is there a real number for every rational number (because the rationals are a subset of the reals), but you can map an infinite number of real numbers to each rational number! Take your pencil and put a dot on a random point on the x-axis; you might hit a point whose coordinate is a rational number, but your chances of doing so are infinitesimal! Therefore, in a formal probabilistic sense, you will "almost surely" choose a point with an irrational coordinate. Therefore, we say that "almost all" the real numbers are irrational.
  - crazygringo 5y ago
    > Take your pencil and put a dot on a random point on the x-axis; you might hit a point whose coordinate is a rational number, but your chances of doing so are infinitesimal! But see, that's precisely the kind of intution I'm arguing against -- the kind of "analogy" that seems indefensible to me. After all, I can select any pixel from an infinitely zoomable number line on my computer and it will always be rational, every time. Or any measurement you take of a pencil on paper will always be bounded by two rational numbers measured by counting off ticks on a ruler, and unknown within that. One could argue it's impossible to even define what it means to point with a pencil to an irrational number on a straight line. What does it even mean to select a value randomly from multiple infinite sets? And if you define that in some particular way, how do you justify that a pencil could ever do that on paper? I understand perfectly everything you describe about mapping -- I'm familiar with the math. It just seems misguided and potentially dangerous to me to draw any practical comparisons to it, such as your pencil-and-paper one, because they seem to break down instantly.
- myWindoonn 5y ago
  Goodstein's theorem comes with a function on the natural numbers. Whether we can prove that the function works correctly, and indeed whether we can implement the function, depends on how big we allow infinities to be. https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Sequence_length_as_a_function_of_the_starting_value https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Sequence...
  - btilly 5y ago
    Sorry, that isn't what that link says. We can implement the function on a Turing machine. Whether we can prove that the function winds up being well-defined depends on which axioms we use. But if you allow transfinite induction up to ε0 (see https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics) https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)) we can prove that the function works correctly. And this statement can be made without any reference to the size of any uncountable infinities. (Indeed the argument can even be made constructively, within mathematical systems where everything is countable.)
    - myWindoonn 5y ago
      Proof-theoretic ordinal ε₀ isn't sufficient to prove Goodstein's theorem; the entire point is that PA has ε₀ as proof-theoretic ordinal and yet is not able to prove it. The better point to make in the context of the parent comment is that ω is the first of many transfinite numbers; our ability to talk about multiple numbers "above infinity" is intimately related to the set theory which underlies Cantor's theorems. Infinities aren't just about some sort of mathematical game, but directly influence what we can define and describe.
      - btilly 5y ago
        The link I gave begs to differ: The smallest epsilon number ε0 appears in many induction proofs, because for many purposes, transfinite induction is only required up to ε0 (as in Gentzen's consistency proof and the proof of Goodstein's theorem). If you trace through the sketch of the proof of Goodstein's theorem at https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Proof_of_Goodstein's_theorem https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Proof_of... you can see for yourself that transfinite induction up to ε₀ is indeed sufficient. As for the rest of your comment, I'm able to talk classical mathematics but my sympathies are firmly Constructivist. So yes, I really do see most discussion of infinities as part of an explicitly meaningless mathematical game known as Formalism.
- mcguire 5y ago
  "The idea of "differently sized infinities" has always felt like a mathematical game to me." How do you feel about negative numbers? There is absolutely no way you can have -3 oranges. There are metaphors, and we're all taught what you can do with a negative number, and there are all those lovely proofs of the properties of negative numbers, but you will never see -3 oranges sitting on someone's dining table. (And I'm not even going to go into the reals---they're just ridiculous.) The commonsense notion of "size" is one of those metaphors, but it's a good one: for non-infinite sets, the idea of a bijection and the idea that two sets have the same size match exactly. Consider three blocks, one labelled "1", another "2", and a third "3", and three oranges. Block "1" goes with that big, fat orange. Block "2" goes with the smaller orange. And Block "3" goes with the orange that's kind of pear-shaped. Now, the extension of "size" to infinite sets is a little weird, mostly because infinite sets are very weird. As is the phrase "almost all"; it's not immediately obvious that, because there are more Rs than Ns, that there are a lot more Rs than Ns. But it's true (in the sense that it's how math works), and you just have to get used to it the same way you got used to -3.
  - GuB-42 5y ago
    Reminds me of a joke: A biologist, an engineer and a mathematician see two people enter a seemingly empty building, and a moment later, three people leave. Biologist: They must have reproduced Engineer: It must have been a measurement error Mathematician: If one person enters the building, it will become empty
  - crazygringo 5y ago
    The difference is that negative numbers are 1) practically useful, and 2) extremely interrelated with other useful mathematical concepts. We build up an entire system of real (and even complex) algebra. While with differently-sized infinite sets, the point is that they aren't (to the best of my knowledge) either 1) directly useful or 2) particularly interrelated with anything else. E.g. they're in addition to the set theory used for real and complex analysis -- not a foundation for it. And so it seems more apt to put the notion of measuring different "sizes" for infinite sets in the same category of, say, quaternions and sedenions. I don't think too many people would say sedenions are "true", just that they're a construction with certain properties. They're not derived from anything, in the way that negative numbers are derived from inverting addition. Yet math textbooks and courses indeed attempt to present the "sizes" of infinite sets as "true" -- as real as negative numbers -- when I still fail to see how they're anything but a relatively arbitrary curiosity like sedenions.
- btilly 5y ago
  Actually the proofs depend on philosophical assumptions that both can and have been questioned. The conclusions likewise. If you go down that path, then "uncountable" can mean something closer to, "a self-referential tangle is involved" than it does to "more". For example you can't enumerate the reals. But there is a countable list that DOES include every possible real - you just can't always figure out whether things on that list are reals! See https://news.ycombinator.com/item?id=27847353 https://news.ycombinator.com/item?id=27847353 for previous discussion on this.
  - analog31 5y ago
    Does that imply that the reals are a subset of a countable list?
    - btilly 5y ago
      Well, not necessarily. One of the standard constructions of the reals is via sequences of rationals. A sequence of rationals that looks like it should be converging is called a Cauchy sequence. (I'm avoiding the technical definitions, but they are easy to find.) Two Cauchy sequences that look like they are converging to the same thing, are equivalent. And reals are defined as equivalence classes of Cauchy sequences. This translates pretty well to a constructive approach. For example we can build our mathematics out of things expressible in a programming language. We can define a Cauchy sequence as a function that can be proven by our favorite axiom system to produce a sequence of rationals converging at a specified rate. Again, two functions are equivalent if they can be proven to produce sequences converging to the same thing. We can certainly enumerate all possible programs. But we cannot, thanks to the Halting problem, write a program that is able to select out which possible programs represent reals. Nor can we reliably identify which pairs of programs are equivalent. So in this construction there is really no actual set of reals that can be identified. Nor can we tell whether a real has been listed already. But there is a countable list that has all possible things that might possibly represent a real. Which will include each real many times. Does that clarify what I meant by "self-referential tangle"?
      - 5y ago
- jyounker 5y ago
  > The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? It seems more like an almost arbitrary puzzle than "fact". The field of numerical analysis depends on formal treatments of calculus. Formal treatments of calculus don't work in sets smaller than the reals.
  - crazygringo 5y ago
    When I studied real analysis, I don't recall anything regarding real numbers that seemed to depend on assigning different sizes to infinite sets. Is there something I'm missing, something that the formal treatment of calculus depends on them for?
    - dnautics 5y ago
      Dedekind cuts (which are necessary for epsilon-delta proofs) or alternatively Bolzano Weierstrass theorem (if you use sequential convergence definition) imply multiple sizes of infinity, so the logical arrow is in the other direction, roughly: "real analysis implies assigning different sizes to sets", not "assigning different sizes to sets implies real analysis". It's been a while but iirc there are other constructions (such as p-adic numbers) which create multiple sizes of infinities out of the rationals which aren't real analysis.
      - SAI_Peregrinus 5y ago
        The Surreal Numbers are a particularly intuitive sort that create different sizes of infinities. All the ordinals, really. They're isomorphic (in NBG) to a maximal-class hyperreal field of nonstandard analysis.
- amelius 5y ago
  > The idea of "differently sized infinities" has always felt like a mathematical game to me. It's a hack. Mathematicians can come up with hacks too.
- hansvm 5y ago
  > cardinals are mathematical games Totally agreed, as with 2+2=4. It's an interesting topic in philosophy that we often gloss over because the naturals are exceptionally predictive of so many things in the real world. > cardinals aren't necessarily commonsense Maybe. The two notions being applied are (1) that if you just rename everything in your set you haven't changed it's size, and (2) that if all renaming attempts necessarily leave some elements out then the set containing those elements must be bigger. Any "size" capturing those two ideas is equivalent to a renaming of the cardinals. > naturals vs even naturals Any topological sort of the infinite subsets of the naturals preserving the set inclusion partial order is going to have some weird oddities. In particular, you'll have a lot of incomparable sets (like the evens and odds, or like all the vertex-deleted N-{x} sets) which are artificially bigger/smaller than each other or artificially the same size, despite the order superficially looking like one based on set inclusion. > other more commonsense alternatives to cardinals Even just looking at infinite subsets of the naturals, any ordering you choose must necessarily have the property that there exist infinitely many sizes which each either do not have a next bigger element or do not have a next smaller element. That's a decidedly weird property that doesn't manifest for finite sizes, and it's entirely unavoidable. I'm potentially okay with "size" not being used as the name, but as a counterpoint the motivation is to extend the notion of "size" for finite sets as best as possible. > cardinals aren't useful They're often used to prove things that you do use directly. Sometimes those proofs can get convoluted, but a surprisingly effective technique in many domains is just arguing that two sets have different sizes so they can't be the same (or can't map to each other in the desired way or whatever). Cardinalities agree with our intuition about size on finite sets well enough to directly extend to those sorts of proofs. As one example, the math leading up to the fixed point theorems proving the optimal solution to a GAN yields the desired probability distribution is usually done (and originally done iirc) via infinite counting arguments. I'll be the first to admit that my day-to-day as a programmer doesn't often do much with infinite cardinalities, but given that the mathematical world we've constructed for ourselves happens to often line up nicely with the real world, "mathematical games" that leverage existing intuition to expand our knowledge of that mathematical world still seem valuable.
- cscurmudgeon 5y ago
  I am sure you repeat the same argument with practical application when you go and tell a caveman that the earth is not flat.
- l33t2328 5y ago
  It should be noted that “almost all” is a probability term, meaning that (under a uniform probability measure on the 0-1 interval), the probability that a randomly chosen number is rational is 0. The probability that that a randomly chosen number is irrational is 1.
- fogof 5y ago
  > is there any practical constraints or applications around it? To speak to this question: Suppose you were going to build a calculator program on your computer. You might start with integers and have addition multiplication and subtraction. All perfectly fine. Even if the numbers are very big you can still represent them by using multiple memory slots. The you add division, and since you don’t want rounding errors in your calculator, you add rational numbers. Can rational numbers still be represented by a computer? Yes, because they are a countable infinity, you can represent them just as easily as you can represent integers. You would like your calculator to be as complete as possible so you keep adding functions like roots, exp, log, sin, et cetera. But no matter how many functions you add, you’ll never be able to represent every real number. This is useful to know so that nobody ever tries to build a computer that does this.
- jhanschoo 5y ago
  > The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? Yes. There exist libraries that allow us to do arithmetic with arbitrarily large integers with exact precision in a computer, but none that allow us to do arithmetic with arbitrary real numbers. This is because you cannot ever find an encoding that assigns each element of an uncountable set a finite-length string, but you always can find one such for countable sets, no exceptions. So in practical day-to-day, the programmer (and computational modeller) has to settle for all the quirks of imprecision when dealing with floats, and this imprecision makes a lot of algorithms more complex and limited than the mathematical computation they are trying to model.
  - WastingMyTime89 5y ago
    > that allow us to do arithmetic with arbitrary real numbers Of course there are. You can symbolically encode and manipulate real numbers with exact precision. Sure it might become unwieldy and is fundamentaly constrained by the physical limits of your computer but the same is true with large integers computation. People don't do it usually because it's useless not because it's impossible. Bounded precision is fine most of the time.
    - anchpop 5y ago
      That doesn’t let you work with arbitrary real numbers because the vast majority of real numbers cannot by symbolicly encoded, even on a turing machine with infinite memory
      - Firadeoclus 5y ago
        If they cannot be symbolically encoded why would you ever _need_ to encode them?
        anchpop 5y ago
        Not being able to do something has never stopped people from needing to do it :P That said, with Google's paper "towards an api for the real numbers", you get close enough for many practical purposes
- addicted 5y ago
  2 + 2 = 4 is arguably less fundamental than the theories around different infinities.
  - jobigoud 5y ago
    How so? 2+2=4 was known before humans even existed, many animal species understand this concept.
- kevinventullo 5y ago
  Note: although the phrase “almost all” sounds like an intuitive English-sentence idea, it actually has a very precise mathematical meaning: it means the complement has Lebesgue measure zero. It sounds like maybe you take issue with this phrase. I kind of think about it probabilistically: if you start uniformly sampling decimal digits 0-9 at random d1,d2,d3,… then the corresponding number 0.d1d2d3… (with the digits going on forever) will be irrational with probability 1.
- create_comment 5y ago
  The following frames Cantor's argument in a more computational way, maybe it is of use: https://bartoszmilewski.com/2019/11/06/fixed-points-and-diagonal-arguments/ https://bartoszmilewski.com/2019/11/06/fixed-points-and-diag... Some of the references found in the above make for interesting reading as well.
- WastingMyTime89 5y ago
  > just kinda bugs me that the way the formal cardinality of infinite sets is communicated is as the commonsense notion of "size". It's not in any place doing maths sensibly. It's just that both the USA and the UK have a terribly unrigorous way of teaching maths even at university level. If you take a look at the French Wikipedia article on cardinality, you will see that the world size is never used and the closest thing you will find to it is that cardinality can intuitively be seen as the "number" of elements in a set with actual quotes around. The article then compare multiple very rigorous definitions. I expect a translation of it would be unreadable by most American however. The average French reader will have been exposed to significantly more formal mathematics. Using the world "size" when talking about infinities is just sloppy.
zkmon 5y ago
The fallacy of Cantor (and his supporters such as Hilbert) lies in mixing the mathematical logic which is meaningful only for finite numbers, with the infinity as if it were a number that obeys comparison operations such as bigger, smaller etc. Almost anything can be proved/disproved or debated when one assumes such validity of the logical concepts to infinity. The acceptance of multiple infinities and some concepts around continuum (Dedekind cuts etc) are questionable due to this assumption.
- mcguire 5y ago
  "Almost anything can be proved/disproved or debated when one assumes such validity of the logical concepts to infinity." I strongly believe that statement to be false. Can you provide a contradiction that is provable using Cantor's definition of the cardinality of sets?
- zkmon 5y ago
  Many logical concepts which we take for granted, might not be meaningful in the realm of infinite. For example, something being equal to itself, some statement being true or false (no third state), things having unique identity or location, the concept or possibility of multiple things (and distinguishability), being able to compare one thing with another etc. All these make sense only in finite contexts but not in infinite or infinitesimal contexts. If we accept infinity as a participant in the mathematical logic, the infinitesimal also deserves a role as a counter-party.
  - thaumasiotes 5y ago
    > If we accept infinity as a participant in the mathematical logic, the infinitesimal also deserves a role as a counter-party. Infinitesimals have a much bigger role in widely-known mathematics than infinities do; they are the basis for calculus.
    - qweqwweqwe-90i 5y ago
      Series play a big role in all of math...
criloz2 5y ago
This feels really arbitrary to me, I am more found to think that exist two additional disjoint categories just unbounded and bounded, and we can have unbounded countable sets and bounded countable sets, and an order relation between the cardinalities of unbounded countable sets just don't exist, it doesn't make any logical sense. In which point you stop walking both sets to compare their size?
- mcguire 5y ago
  You don't actually walk the sets to compare their sizes. You establish a 1-1 relationship between their elements. Take the natural numbers 0,1,2,3... (call that N) and the even counting numbers 0,2,4,6... (call that E). Here's a function between N -> E: f(n) = n * 2. You can prove that f maps every element of N to an element of E, and that every element of E is mappable from an element of N. f is 1-1. And therefore, N and E are the same "size".
- brianpan 5y ago
  An integral can be used to find the area under a curve by summing infinitesimally small areas. The point isn't to walk to the end of the infinity. It's to use it as a tool to calculate something in a different or previously impossible way. All tools are arbitrary without an application. But sometimes you have to figure out what's possible before you can try to find an application.
  - Kranar 5y ago
    That's one interpretation but it's kind of shaky without a theory of infinitesimals, and when you do work with a theory of infinitesimals it turns out not to be all that much better than working with the more traditional delta/epsilon approach, which is really quite rigorous and can be explained without the use of any infinities.
nonameiguess 5y ago
"Bigger" is poor wording when discussing cardinality. I can see other comments here are struggling with this. Cardinality should not be thought of as "size." Cardinality is purely a functional property. If you can define a bijective function between two sets, then they have the same cardinality. If you can't, then you take the set which has all of its elements paired, place it before the set that has unpaired elements, and there you go, you've defined a partial order over all possible sets, including infinite sets. But it doesn't really match what we usually mean by "size." The size of a set is more properly associated with measure. This is why we rely on measure to coherently formalize continuous probability. The sets (0, 0.1) and (0, 0.9) have exactly the same cardinality, but the latter has greater measure, which is why we can say an event space defined by the latter is more probable than one defined by the former. Both event spaces are infinite, but one is "bigger" than the other, in this case in a way that captures intuition about size much better than cardinality does.
- contravariant 5y ago
  If you were hoping to make size more intuitive by using measures then immeasurable sets kind of pose a problem. With Banach-Tarski as the ultimate example.
- syops 5y ago
  One can define an order relation using cardinality. Cardinality does capture a notion of size of sets that corresponds to intuition for finite sets and captures the idea of one infinite set being “smaller” or the same size as another. In general sets don’t have a measure on them in the sense of measure theory. Indeed, assuming the Axiom of Choice there are non measurable sets of the real numbers. But every set has a cardinality. And there is a well defined linear order of the hierarchy of cardinal numbers. I’m assuming the axiom of choice.
- akira2501 5y ago
  > Cardinality is purely a functional property. Is something like "granularity" an appropriate intuition? Both sets are of infinite size, but one has more points with which to take measurements against than the other. It isn't "bigger" so much as it is "finer?"
david38 5y ago
Ah, sweet memories of discrete math.
GolDDranks 5y ago
"a subset of the x-y plane with a large cardinality need be neither measurable nor of large measure. For example, the entire plane with its 2^ℵ0 elements has an infinite measure." This should be ℵ0^2, since we are talking about plane defined by two axes, x * y, each with measure ℵ0, so the measure becomes ℵ0 * ℵ0 = ℵ0^2, which is the same as ℵ0, right? Edit: maybe they don't mean elements as points in plane, but subsets of the plane, in which case the statement would apply?
- kevinventullo 5y ago
  No, they really did mean 2^ℵ0. Note the earlier sentence “The set ℝ of real numbers (also called the real line) is as large as the power set of ℕ, and this cardinality is denoted 2^ℵ0, or “continuum.”” So the x-y plane has cardinality 2^ℵ0 * 2^ℵ0 = 2^ℵ0.
  - GolDDranks 5y ago
    Ah, indeed. Thanks for the correction. I read there, for some reason, an implication that a plane would have a larger cardinality than a line, which isn't true. But indeed, both are 2^ℵ0.
anikan_vader 5y ago
Many of the comments here are critical of Cantor or his proofs… it’s reminiscent of the reaction that the poor guy received from his contemporaries, who basically shunned him for many years. It’s a fundamental mathematical fact that there does not exist a bijection between the naturals and the reals. This is what provides genuine distinction between the discrete and the continuous, the countable and the uncountable. It certainly is a mind-blowing fact. But many facts blow the human mind, and it isn’t Cantor’s fault that he was brilliant enough to discover one such.
- xscott 5y ago
  There is however a bijection between the natural/countable numbers and every number that mathematicians, physicists, and any other scientist have every used in all of human history (or will ever use). Start with the computable numbers, and then generalize to anything that has been written down in symbolic text. It's very hard to point to a real number which is not in the set of computable numbers, and for the few examples (Chaitin's constant(s) etc...), there are countably many of them. From this point of view, I'm curious whether the computable numbers are sufficient to do integral and differential calculus etc... (basically all "normal" math that engineers or applied scientists might use) Maybe it requires a different definition of limits, I dunno. What number are we interested in that can't be done with computable numbers? At what point do we need Real numbers and their mind-blowingly weird properties?
  - adenadel 5y ago
    I am certainly not an expert on this, but my guess is that there will be be challenges to doing calculus since you won't have the standard foundational properties of the reals (like the least upper bound property). That being said, it looks like mathematicians have investigated this.[0] 0. https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis
  - dooglius 5y ago
    It's not individual numbers that matter, but the properties of sets of them and functions over them. You can define a Reimann integral over computable numbers without changing much, but not the more general Lebesgue integral. This means you won't get e.g. the nice properties of L2 spaces which are used heavily in quantum mechanics.

55 points by prostoalex 5y ago

The idea of "differently sized infinities" has always felt like a mathematical game to me. The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? It seems more like an almost arbitrary puzzle than "fact". I don't disagree with any of the proofs or reasoning... it just kinda bugs me that the way the formal cardinality of infinite sets is communicated is as the commonsense notion of "size". When we make statements such as the size of the set of all natural numbers 1, 2, 3... is the same as the size of the set of all natural even numbers 2, 4, 6..., despite the former containing the latter but not vice-versa... it seems the word "size" -- and associated terminology "larger than", "smaller than", etc. -- is a particularly unhelpful set of words to have chosen for this. The reason I think this is important is because if you go to e.g. the Wikipedia page for "irrational number", it states in the introduction [1]: > "As a consequence of Cantor's proof that the real numbers are uncountable and the rationals countable, it follows that almost all real numbers are irrational." But it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational, as if it had any analogy whatsover to a statement such as e.g. "almost all" values of 1/x are defined. Am I missing anything here? I've never heard of any natural practical application of this concept, in a way that suggests it's "true" in the same way algebra and calculus are considered to be. [1] https://en.wikipedia.org/wiki/Irrational_number https://en.wikipedia.org/wiki/Irrational_number

lhorie 5y ago
This seems like just an observation about the less formal nature of colloquial language. We also say things like "70% of people do X", when in actuality the underlying study "extrapolates" from a smaller population via statistical analysis. All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time.
- mrkramer 5y ago
  >We also say things like "70% of people do X", when in actuality the underlying study "extrapolates" from a smaller population via statistical analysis. Isn't that approximation because we will never really know how many people exactly do X. >All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time. Are they overloading the meaning of "size" or offloading it? Because again nobody really knows what real size or cardinality of anything is so they offload it to some other future term or meaning just like you said "which is one well known mechanism that cause mutations in languages over time." I'm not a mathematician but I heard from them say that it is better to use word unbounded than infinite because infinities are tricky.
openasocket 5y ago
Here, terms like "almost all" come to us from measure theory (and its application to probability theory), which tries to define a general notion of the size or volume of sets.
philipov 5y ago
I think the problem is that infinity doesn't exist in real life. We don't have access to unbounded quantities, so any discussion of them is necessarily going to be more abstract than the notions we're used to dealing with. The results may be unintuitive, but they follow from very intuitive ways of doing counting. Two piles of rocks are the same size if you can line them up so each rock from one pile matches with a rock from the other pile. But once you combine that with mathematical induction, you start getting into the realm of objects that don't exist in real life and it starts looking weird. I think there's an easy way to draw an analogy between the statements that "almost all" real numbers are irrational and "almost all" values of 1/x are defined. If you were to pick a random real number from the domain of 1/x, the chances of picking one for which 1/x is undefined approaches zero. Similarly, if you pick a random real number, the chances of picking a rational one approaches zero.
- TuringTest 5y ago
  > We don't have access to unbounded quantities, so any discussion of them is necessarily going to be more abstract than the notions we're used to dealing with. I've always thought of infinite as very concrete unbounded processes, rather than quantities (but then, I'm a computer scientist, not a mathematician). You cannot count the size of an infinite set because you can never stop counting; the process goes on and on. So the way to compare infinities is to map things between them. If you can map all elements from the first infinite to the second, but not the other way around, the second is larger than the first. It makes sense as to define this process as the way to compare sizes, since actually counting all their items is ruled out. "Almost all" elements of an infinite set could be defined similarly, if for each item without a particular property you can create a limitless variety of different items with it.
  - jobigoud 5y ago
    > If you can map all elements from the first infinite to the second, but not the other way around, the second is larger than the first. This seems simple enough but it's still very much counter intuitive when comparing say all the natural numbers with only the even numbers. An intuitive mapping would lead you to think there are more naturals than evens, but math says these two infinites are of the same size.
js6i 5y ago
> When we make statements such as the size of the set of all natural numbers 1, 2, 3... is the same as the size of the set of all natural even numbers 2, 4, 6..., despite the former containing the latter but not vice-versa... it seems the word "size" -- and associated terminology "larger than", "smaller than", etc. -- is a particularly unhelpful set of words to have chosen for this. It seems to me, when you're counting things, you wouldn't care what are the things you're counting specifically; while in your example it does matter for determining the subset relation. Whatever way of counting where it matters would be kind of weird. > it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational But the article uses "almost all" in the formal sense? Which, by the way, also has pretty intuitive meaning, in my opinion.
- vitus 5y ago
  > But the article uses "almost all" in the formal sense? Which, by the way, also has pretty intuitive meaning, in my opinion. By formal sense, do you mean everywhere but a finite-measure set? Zero-measure? I'll use finite-measure because it allows for intuitive constructions like "almost all real numbers are outside the closed unit interval 0 <= x <= 1". But, there are still some constructions that a layperson might expect to hold, like: "almost all real numbers have fractional part < 1e-100", or "almost all positive numbers are of the form x.y with 0.y < 1/x" (thanks, harmonic series). I think that without formal training, we're especially bad at reasoning about dense sets such as the set of rational numbers, compared to, say, the reals.
  - js6i 5y ago
    Maybe not the most formal of meanings, but my favorite is a probabilistic one: given a random element, how likely it is that it satisfies a predicate? If some elements don't, but it's still satisfied with probability 1, that's pretty clearly almost always. EDIT: yeah you guys are right, I wouldn't worry too much about the prior not being a proper distribution, but still - this doesn't seem related to the cardinality of sets in a simple way after all!
thaumasiotes 5y ago
> But it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational, as if it had any analogy whatsover to a statement such as e.g. "almost all" values of 1/x are defined. What's the objection? Almost all values of 1/x are defined. The analogy is... it's the same usage with the same meaning. That's not even an analogy.
- canjobear 5y ago
  Almost none of the numbers of the form 1/x have definitions. Definitions have finite length, so there is only a countable number of numbers with definitions. But there are uncountable number of numbers of the form 1/x.
- crazygringo 5y ago
  No, it's an entirely different meaning. Because yes, almost all values of 1/x are defined -- for every real value of x except for one, the number zero. While saying "almost all" real numbers are irrational... is saying that real values are all irrational, except for... the entire infinitely large set of rational numbers. The idea of "almost all" and "except for an infinite number of items" is not even close to the same commonsense meaning, not even remotely. That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly.
  - Dylan16807 5y ago
    I could also mathematically say that "almost all" integers are not powers of 58279. I think that would fit the commonsense meaning, even though there are infinite counterexamples.
  - tshaddox 5y ago
    > While saying "almost all" real numbers are irrational... is saying that real values are all irrational, except for... the entire infinitely large set of rational numbers. You're claiming that the precise mathematical definitions of these terms are ridiculous, and then just repeating those mathematical definitions of the terms to support your claim. > That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly. The whole point is that when you're comparing infinite sets, common sense terms like "size," "almost all," etc. don't make any sense at all, so mathematicians create precise definitions for the terms that are then used among all mathematicians and do make sense. These terms are common among mathematicians and they do make sense. The fact that these definitions don't precisely match the definitions used by non-mathematicians is precisely the goal, because those definitions make no sense whatsoever when referring to infinite sets. It's okay to complain about using jargon in discussions not related to mathematics, although that's not what is happening here (and it's difficult to imagine a conversation about infinite sets that is not also about mathematics). This complaint is comparable to complaining that the definitions of "sharp" and "flat" in music theory don't at all match the definitions of "sharp" and "flat" used in conversations not about music. I suppose another way to approach this is to ask what you would propose the term "almost all" to mean when referring to an infinite set? For that matter, what do you propose that the term "almost all" means to a layperson referring to small finite sets? What percentage do you need in order to use "almost all"?
bitwize 5y ago
It's because they kinda follow the same rules as finitely sized sets. Say you have two sets: A and B. A has five elements and B has seven. That means that for each element in A there is a unique corresponding element in B, but the reverse is not true: B has elements that do not map to elements in A. OK, now say A is the set of integers, and B is the set of points on the x-axis. Same deal applies, you can map every integer to a point on the x-axis and still have points on the x-axis that do not map to integers. So we've formalized infinite sets in a way that preserves our intuitive notion of what it means to have more or less of something, without having to count or measure the sets which would be bloody impossible! Yes, it's a game but so is all of math! As for "almost all", in statistics we have this notion of "almost surely", which is formally defined as "with probability 1". It turns out that a probability of 1 doesn't guarantee that something will happen, because 1 less an infinitesimal is still 1! So roll a spherical die that yields a real number between 0 and 1; if you roll a 0, you lose. The probability that you will win is still 1, but you might still roll that goose egg! So we say that you will "almost surely" win at this game. If you think of rational and real numbers in terms of our two sets with different cardinalities, not only is there a real number for every rational number (because the rationals are a subset of the reals), but you can map an infinite number of real numbers to each rational number! Take your pencil and put a dot on a random point on the x-axis; you might hit a point whose coordinate is a rational number, but your chances of doing so are infinitesimal! Therefore, in a formal probabilistic sense, you will "almost surely" choose a point with an irrational coordinate. Therefore, we say that "almost all" the real numbers are irrational.
- crazygringo 5y ago
  > Take your pencil and put a dot on a random point on the x-axis; you might hit a point whose coordinate is a rational number, but your chances of doing so are infinitesimal! But see, that's precisely the kind of intution I'm arguing against -- the kind of "analogy" that seems indefensible to me. After all, I can select any pixel from an infinitely zoomable number line on my computer and it will always be rational, every time. Or any measurement you take of a pencil on paper will always be bounded by two rational numbers measured by counting off ticks on a ruler, and unknown within that. One could argue it's impossible to even define what it means to point with a pencil to an irrational number on a straight line. What does it even mean to select a value randomly from multiple infinite sets? And if you define that in some particular way, how do you justify that a pencil could ever do that on paper? I understand perfectly everything you describe about mapping -- I'm familiar with the math. It just seems misguided and potentially dangerous to me to draw any practical comparisons to it, such as your pencil-and-paper one, because they seem to break down instantly.
myWindoonn 5y ago
Goodstein's theorem comes with a function on the natural numbers. Whether we can prove that the function works correctly, and indeed whether we can implement the function, depends on how big we allow infinities to be. https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Sequence_length_as_a_function_of_the_starting_value https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Sequence...
- btilly 5y ago
  Sorry, that isn't what that link says. We can implement the function on a Turing machine. Whether we can prove that the function winds up being well-defined depends on which axioms we use. But if you allow transfinite induction up to ε0 (see https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics) https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)) we can prove that the function works correctly. And this statement can be made without any reference to the size of any uncountable infinities. (Indeed the argument can even be made constructively, within mathematical systems where everything is countable.)
  - myWindoonn 5y ago
    Proof-theoretic ordinal ε₀ isn't sufficient to prove Goodstein's theorem; the entire point is that PA has ε₀ as proof-theoretic ordinal and yet is not able to prove it. The better point to make in the context of the parent comment is that ω is the first of many transfinite numbers; our ability to talk about multiple numbers "above infinity" is intimately related to the set theory which underlies Cantor's theorems. Infinities aren't just about some sort of mathematical game, but directly influence what we can define and describe.
    - btilly 5y ago
      The link I gave begs to differ: The smallest epsilon number ε0 appears in many induction proofs, because for many purposes, transfinite induction is only required up to ε0 (as in Gentzen's consistency proof and the proof of Goodstein's theorem). If you trace through the sketch of the proof of Goodstein's theorem at https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Proof_of_Goodstein's_theorem https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Proof_of... you can see for yourself that transfinite induction up to ε₀ is indeed sufficient. As for the rest of your comment, I'm able to talk classical mathematics but my sympathies are firmly Constructivist. So yes, I really do see most discussion of infinities as part of an explicitly meaningless mathematical game known as Formalism.
mcguire 5y ago
"The idea of "differently sized infinities" has always felt like a mathematical game to me." How do you feel about negative numbers? There is absolutely no way you can have -3 oranges. There are metaphors, and we're all taught what you can do with a negative number, and there are all those lovely proofs of the properties of negative numbers, but you will never see -3 oranges sitting on someone's dining table. (And I'm not even going to go into the reals---they're just ridiculous.) The commonsense notion of "size" is one of those metaphors, but it's a good one: for non-infinite sets, the idea of a bijection and the idea that two sets have the same size match exactly. Consider three blocks, one labelled "1", another "2", and a third "3", and three oranges. Block "1" goes with that big, fat orange. Block "2" goes with the smaller orange. And Block "3" goes with the orange that's kind of pear-shaped. Now, the extension of "size" to infinite sets is a little weird, mostly because infinite sets are very weird. As is the phrase "almost all"; it's not immediately obvious that, because there are more Rs than Ns, that there are a lot more Rs than Ns. But it's true (in the sense that it's how math works), and you just have to get used to it the same way you got used to -3.
- GuB-42 5y ago
  Reminds me of a joke: A biologist, an engineer and a mathematician see two people enter a seemingly empty building, and a moment later, three people leave. Biologist: They must have reproduced Engineer: It must have been a measurement error Mathematician: If one person enters the building, it will become empty
- crazygringo 5y ago
  The difference is that negative numbers are 1) practically useful, and 2) extremely interrelated with other useful mathematical concepts. We build up an entire system of real (and even complex) algebra. While with differently-sized infinite sets, the point is that they aren't (to the best of my knowledge) either 1) directly useful or 2) particularly interrelated with anything else. E.g. they're in addition to the set theory used for real and complex analysis -- not a foundation for it. And so it seems more apt to put the notion of measuring different "sizes" for infinite sets in the same category of, say, quaternions and sedenions. I don't think too many people would say sedenions are "true", just that they're a construction with certain properties. They're not derived from anything, in the way that negative numbers are derived from inverting addition. Yet math textbooks and courses indeed attempt to present the "sizes" of infinite sets as "true" -- as real as negative numbers -- when I still fail to see how they're anything but a relatively arbitrary curiosity like sedenions.
btilly 5y ago
Actually the proofs depend on philosophical assumptions that both can and have been questioned. The conclusions likewise. If you go down that path, then "uncountable" can mean something closer to, "a self-referential tangle is involved" than it does to "more". For example you can't enumerate the reals. But there is a countable list that DOES include every possible real - you just can't always figure out whether things on that list are reals! See https://news.ycombinator.com/item?id=27847353 https://news.ycombinator.com/item?id=27847353 for previous discussion on this.
- analog31 5y ago
  Does that imply that the reals are a subset of a countable list?
  - btilly 5y ago
    Well, not necessarily. One of the standard constructions of the reals is via sequences of rationals. A sequence of rationals that looks like it should be converging is called a Cauchy sequence. (I'm avoiding the technical definitions, but they are easy to find.) Two Cauchy sequences that look like they are converging to the same thing, are equivalent. And reals are defined as equivalence classes of Cauchy sequences. This translates pretty well to a constructive approach. For example we can build our mathematics out of things expressible in a programming language. We can define a Cauchy sequence as a function that can be proven by our favorite axiom system to produce a sequence of rationals converging at a specified rate. Again, two functions are equivalent if they can be proven to produce sequences converging to the same thing. We can certainly enumerate all possible programs. But we cannot, thanks to the Halting problem, write a program that is able to select out which possible programs represent reals. Nor can we reliably identify which pairs of programs are equivalent. So in this construction there is really no actual set of reals that can be identified. Nor can we tell whether a real has been listed already. But there is a countable list that has all possible things that might possibly represent a real. Which will include each real many times. Does that clarify what I meant by "self-referential tangle"?
    - 5y ago
jyounker 5y ago
> The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? It seems more like an almost arbitrary puzzle than "fact". The field of numerical analysis depends on formal treatments of calculus. Formal treatments of calculus don't work in sets smaller than the reals.
- crazygringo 5y ago
  When I studied real analysis, I don't recall anything regarding real numbers that seemed to depend on assigning different sizes to infinite sets. Is there something I'm missing, something that the formal treatment of calculus depends on them for?
  - dnautics 5y ago
    Dedekind cuts (which are necessary for epsilon-delta proofs) or alternatively Bolzano Weierstrass theorem (if you use sequential convergence definition) imply multiple sizes of infinity, so the logical arrow is in the other direction, roughly: "real analysis implies assigning different sizes to sets", not "assigning different sizes to sets implies real analysis". It's been a while but iirc there are other constructions (such as p-adic numbers) which create multiple sizes of infinities out of the rationals which aren't real analysis.
    - SAI_Peregrinus 5y ago
      The Surreal Numbers are a particularly intuitive sort that create different sizes of infinities. All the ordinals, really. They're isomorphic (in NBG) to a maximal-class hyperreal field of nonstandard analysis.
amelius 5y ago
> The idea of "differently sized infinities" has always felt like a mathematical game to me. It's a hack. Mathematicians can come up with hacks too.
hansvm 5y ago
> cardinals are mathematical games Totally agreed, as with 2+2=4. It's an interesting topic in philosophy that we often gloss over because the naturals are exceptionally predictive of so many things in the real world. > cardinals aren't necessarily commonsense Maybe. The two notions being applied are (1) that if you just rename everything in your set you haven't changed it's size, and (2) that if all renaming attempts necessarily leave some elements out then the set containing those elements must be bigger. Any "size" capturing those two ideas is equivalent to a renaming of the cardinals. > naturals vs even naturals Any topological sort of the infinite subsets of the naturals preserving the set inclusion partial order is going to have some weird oddities. In particular, you'll have a lot of incomparable sets (like the evens and odds, or like all the vertex-deleted N-{x} sets) which are artificially bigger/smaller than each other or artificially the same size, despite the order superficially looking like one based on set inclusion. > other more commonsense alternatives to cardinals Even just looking at infinite subsets of the naturals, any ordering you choose must necessarily have the property that there exist infinitely many sizes which each either do not have a next bigger element or do not have a next smaller element. That's a decidedly weird property that doesn't manifest for finite sizes, and it's entirely unavoidable. I'm potentially okay with "size" not being used as the name, but as a counterpoint the motivation is to extend the notion of "size" for finite sets as best as possible. > cardinals aren't useful They're often used to prove things that you do use directly. Sometimes those proofs can get convoluted, but a surprisingly effective technique in many domains is just arguing that two sets have different sizes so they can't be the same (or can't map to each other in the desired way or whatever). Cardinalities agree with our intuition about size on finite sets well enough to directly extend to those sorts of proofs. As one example, the math leading up to the fixed point theorems proving the optimal solution to a GAN yields the desired probability distribution is usually done (and originally done iirc) via infinite counting arguments. I'll be the first to admit that my day-to-day as a programmer doesn't often do much with infinite cardinalities, but given that the mathematical world we've constructed for ourselves happens to often line up nicely with the real world, "mathematical games" that leverage existing intuition to expand our knowledge of that mathematical world still seem valuable.
cscurmudgeon 5y ago
I am sure you repeat the same argument with practical application when you go and tell a caveman that the earth is not flat.
l33t2328 5y ago
It should be noted that “almost all” is a probability term, meaning that (under a uniform probability measure on the 0-1 interval), the probability that a randomly chosen number is rational is 0. The probability that that a randomly chosen number is irrational is 1.
fogof 5y ago
> is there any practical constraints or applications around it? To speak to this question: Suppose you were going to build a calculator program on your computer. You might start with integers and have addition multiplication and subtraction. All perfectly fine. Even if the numbers are very big you can still represent them by using multiple memory slots. The you add division, and since you don’t want rounding errors in your calculator, you add rational numbers. Can rational numbers still be represented by a computer? Yes, because they are a countable infinity, you can represent them just as easily as you can represent integers. You would like your calculator to be as complete as possible so you keep adding functions like roots, exp, log, sin, et cetera. But no matter how many functions you add, you’ll never be able to represent every real number. This is useful to know so that nobody ever tries to build a computer that does this.
jhanschoo 5y ago
> The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? Yes. There exist libraries that allow us to do arithmetic with arbitrarily large integers with exact precision in a computer, but none that allow us to do arithmetic with arbitrary real numbers. This is because you cannot ever find an encoding that assigns each element of an uncountable set a finite-length string, but you always can find one such for countable sets, no exceptions. So in practical day-to-day, the programmer (and computational modeller) has to settle for all the quirks of imprecision when dealing with floats, and this imprecision makes a lot of algorithms more complex and limited than the mathematical computation they are trying to model.
- WastingMyTime89 5y ago
  > that allow us to do arithmetic with arbitrary real numbers Of course there are. You can symbolically encode and manipulate real numbers with exact precision. Sure it might become unwieldy and is fundamentaly constrained by the physical limits of your computer but the same is true with large integers computation. People don't do it usually because it's useless not because it's impossible. Bounded precision is fine most of the time.
  - anchpop 5y ago
    That doesn’t let you work with arbitrary real numbers because the vast majority of real numbers cannot by symbolicly encoded, even on a turing machine with infinite memory
    - Firadeoclus 5y ago
      If they cannot be symbolically encoded why would you ever _need_ to encode them?
      - anchpop 5y ago
        Not being able to do something has never stopped people from needing to do it :P That said, with Google's paper "towards an api for the real numbers", you get close enough for many practical purposes
addicted 5y ago
2 + 2 = 4 is arguably less fundamental than the theories around different infinities.
- jobigoud 5y ago
  How so? 2+2=4 was known before humans even existed, many animal species understand this concept.
kevinventullo 5y ago
Note: although the phrase “almost all” sounds like an intuitive English-sentence idea, it actually has a very precise mathematical meaning: it means the complement has Lebesgue measure zero. It sounds like maybe you take issue with this phrase. I kind of think about it probabilistically: if you start uniformly sampling decimal digits 0-9 at random d1,d2,d3,… then the corresponding number 0.d1d2d3… (with the digits going on forever) will be irrational with probability 1.
create_comment 5y ago
The following frames Cantor's argument in a more computational way, maybe it is of use: https://bartoszmilewski.com/2019/11/06/fixed-points-and-diagonal-arguments/ https://bartoszmilewski.com/2019/11/06/fixed-points-and-diag... Some of the references found in the above make for interesting reading as well.
WastingMyTime89 5y ago
> just kinda bugs me that the way the formal cardinality of infinite sets is communicated is as the commonsense notion of "size". It's not in any place doing maths sensibly. It's just that both the USA and the UK have a terribly unrigorous way of teaching maths even at university level. If you take a look at the French Wikipedia article on cardinality, you will see that the world size is never used and the closest thing you will find to it is that cardinality can intuitively be seen as the "number" of elements in a set with actual quotes around. The article then compare multiple very rigorous definitions. I expect a translation of it would be unreadable by most American however. The average French reader will have been exposed to significantly more formal mathematics. Using the world "size" when talking about infinities is just sloppy.

zkmon 5y ago

The fallacy of Cantor (and his supporters such as Hilbert) lies in mixing the mathematical logic which is meaningful only for finite numbers, with the infinity as if it were a number that obeys comparison operations such as bigger, smaller etc. Almost anything can be proved/disproved or debated when one assumes such validity of the logical concepts to infinity. The acceptance of multiple infinities and some concepts around continuum (Dedekind cuts etc) are questionable due to this assumption.

mcguire 5y ago
"Almost anything can be proved/disproved or debated when one assumes such validity of the logical concepts to infinity." I strongly believe that statement to be false. Can you provide a contradiction that is provable using Cantor's definition of the cardinality of sets?
zkmon 5y ago
Many logical concepts which we take for granted, might not be meaningful in the realm of infinite. For example, something being equal to itself, some statement being true or false (no third state), things having unique identity or location, the concept or possibility of multiple things (and distinguishability), being able to compare one thing with another etc. All these make sense only in finite contexts but not in infinite or infinitesimal contexts. If we accept infinity as a participant in the mathematical logic, the infinitesimal also deserves a role as a counter-party.
- thaumasiotes 5y ago
  > If we accept infinity as a participant in the mathematical logic, the infinitesimal also deserves a role as a counter-party. Infinitesimals have a much bigger role in widely-known mathematics than infinities do; they are the basis for calculus.
  - qweqwweqwe-90i 5y ago
    Series play a big role in all of math...

criloz2 5y ago

This feels really arbitrary to me, I am more found to think that exist two additional disjoint categories just unbounded and bounded, and we can have unbounded countable sets and bounded countable sets, and an order relation between the cardinalities of unbounded countable sets just don't exist, it doesn't make any logical sense. In which point you stop walking both sets to compare their size?

mcguire 5y ago
You don't actually walk the sets to compare their sizes. You establish a 1-1 relationship between their elements. Take the natural numbers 0,1,2,3... (call that N) and the even counting numbers 0,2,4,6... (call that E). Here's a function between N -> E: f(n) = n * 2. You can prove that f maps every element of N to an element of E, and that every element of E is mappable from an element of N. f is 1-1. And therefore, N and E are the same "size".
brianpan 5y ago
An integral can be used to find the area under a curve by summing infinitesimally small areas. The point isn't to walk to the end of the infinity. It's to use it as a tool to calculate something in a different or previously impossible way. All tools are arbitrary without an application. But sometimes you have to figure out what's possible before you can try to find an application.
- Kranar 5y ago
  That's one interpretation but it's kind of shaky without a theory of infinitesimals, and when you do work with a theory of infinitesimals it turns out not to be all that much better than working with the more traditional delta/epsilon approach, which is really quite rigorous and can be explained without the use of any infinities.

nonameiguess 5y ago

"Bigger" is poor wording when discussing cardinality. I can see other comments here are struggling with this. Cardinality should not be thought of as "size." Cardinality is purely a functional property. If you can define a bijective function between two sets, then they have the same cardinality. If you can't, then you take the set which has all of its elements paired, place it before the set that has unpaired elements, and there you go, you've defined a partial order over all possible sets, including infinite sets. But it doesn't really match what we usually mean by "size." The size of a set is more properly associated with measure. This is why we rely on measure to coherently formalize continuous probability. The sets (0, 0.1) and (0, 0.9) have exactly the same cardinality, but the latter has greater measure, which is why we can say an event space defined by the latter is more probable than one defined by the former. Both event spaces are infinite, but one is "bigger" than the other, in this case in a way that captures intuition about size much better than cardinality does.

contravariant 5y ago
If you were hoping to make size more intuitive by using measures then immeasurable sets kind of pose a problem. With Banach-Tarski as the ultimate example.
syops 5y ago
One can define an order relation using cardinality. Cardinality does capture a notion of size of sets that corresponds to intuition for finite sets and captures the idea of one infinite set being “smaller” or the same size as another. In general sets don’t have a measure on them in the sense of measure theory. Indeed, assuming the Axiom of Choice there are non measurable sets of the real numbers. But every set has a cardinality. And there is a well defined linear order of the hierarchy of cardinal numbers. I’m assuming the axiom of choice.
akira2501 5y ago
> Cardinality is purely a functional property. Is something like "granularity" an appropriate intuition? Both sets are of infinite size, but one has more points with which to take measurements against than the other. It isn't "bigger" so much as it is "finer?"

david38 5y ago

Ah, sweet memories of discrete math.

GolDDranks 5y ago

"a subset of the x-y plane with a large cardinality need be neither measurable nor of large measure. For example, the entire plane with its 2^ℵ0 elements has an infinite measure." This should be ℵ0^2, since we are talking about plane defined by two axes, x * y, each with measure ℵ0, so the measure becomes ℵ0 * ℵ0 = ℵ0^2, which is the same as ℵ0, right? Edit: maybe they don't mean elements as points in plane, but subsets of the plane, in which case the statement would apply?

kevinventullo 5y ago
No, they really did mean 2^ℵ0. Note the earlier sentence “The set ℝ of real numbers (also called the real line) is as large as the power set of ℕ, and this cardinality is denoted 2^ℵ0, or “continuum.”” So the x-y plane has cardinality 2^ℵ0 * 2^ℵ0 = 2^ℵ0.
- GolDDranks 5y ago
  Ah, indeed. Thanks for the correction. I read there, for some reason, an implication that a plane would have a larger cardinality than a line, which isn't true. But indeed, both are 2^ℵ0.

anikan_vader 5y ago

Many of the comments here are critical of Cantor or his proofs… it’s reminiscent of the reaction that the poor guy received from his contemporaries, who basically shunned him for many years. It’s a fundamental mathematical fact that there does not exist a bijection between the naturals and the reals. This is what provides genuine distinction between the discrete and the continuous, the countable and the uncountable. It certainly is a mind-blowing fact. But many facts blow the human mind, and it isn’t Cantor’s fault that he was brilliant enough to discover one such.

xscott 5y ago
There is however a bijection between the natural/countable numbers and every number that mathematicians, physicists, and any other scientist have every used in all of human history (or will ever use). Start with the computable numbers, and then generalize to anything that has been written down in symbolic text. It's very hard to point to a real number which is not in the set of computable numbers, and for the few examples (Chaitin's constant(s) etc...), there are countably many of them. From this point of view, I'm curious whether the computable numbers are sufficient to do integral and differential calculus etc... (basically all "normal" math that engineers or applied scientists might use) Maybe it requires a different definition of limits, I dunno. What number are we interested in that can't be done with computable numbers? At what point do we need Real numbers and their mind-blowingly weird properties?
- adenadel 5y ago
  I am certainly not an expert on this, but my guess is that there will be be challenges to doing calculus since you won't have the standard foundational properties of the reals (like the least upper bound property). That being said, it looks like mathematicians have investigated this.[0] 0. https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis
- dooglius 5y ago
  It's not individual numbers that matter, but the properties of sets of them and functions over them. You can define a Reimann integral over computable numbers without changing much, but not the more general Lebesgue integral. This means you won't get e.g. the nice properties of L2 spaces which are used heavily in quantum mechanics.