30 ms·

How many real numbers exist? New proof moves closer to an answer

501 points by theafh 5y ago

arduinomancer 5y ago
I don’t get for Cantor’s diagonalization proof, why do we need to use the diagonal digits to form the new number? Would the proof work the same if we instead used the first digit of every number in the list?
- miloignis 5y ago
  There are only 10 possible first digits of the new number, so you can't choose a number that will differ from all other numbers in the first digit. If you do it diagonally, you'll always have 9 other options to choose from, since you just have to make it different from that one number!
  - arduinomancer 5y ago
    Makes sense, thanks
- tpetrina 5y ago
  That wouldn't work because n-th digit differing from 1st digit of n-th number doesn't guarantee that the new number isn't accounted for already.
- pavpanchekha 5y ago
  To fill in some details: Two real numbers are different if in the same place they have different digits. [1] So the idea is to take your infinite, hypothetical list of all real numbers A[] and make a new real number X, where for all i, there's some digit where A[i] and X differ. Easiest way is to make X differ from A[i] at digit i. [1] There's a subtlety here about repeating nines at the end of a number, but it is inessential.
- pfortuny 5y ago
  Then you cannot guarantee that when you change the first digit of the second number, what you get is not the first number.
- erdos4d 5y ago
  You need the diagonal because you are making a new number in (0,1) that can't be in the list by just choosing the nth digit of said number different than the nth digit of the diagonal.
- ceh123 5y ago
  To give a concrete example for you, lets start with the finite set: {0.22, 0.32, 0.33} We now construct a new number in this way: First digit of the first number is 2, so we take 3 which is different as our first digit. First digit of the second number is 3 so we take 2 as our second number. Now we have 0.32 First digit of the third number is 3 so we take 0 as our third number. We've constructed the number: 0.320 = 0.32 which is in the set already. So this construction method doesn't guarantee that it's a new number, only that it's different from the first. With Cantor's Diagonalization argument we guarantee it's different from the first number since it's different in the first digit, then we guarantee it's different from the second since it's different in the second digit, etc. etc. it's different from all the numbers in our list. To take the same set above as an example, we end up creating a number like: 0.318 which is definitely different from the numbers in the set
pavpanchekha 5y ago
Great article. Since it looks like a lot of folks are interested in this article, some extra background. First, what is forcing? The article actually has a great description of ultrapowers (a key part of the construction) but it goes by a little fast, so you might like Tim Chow's "A beginner's guide to forcing" [1] which does a good job not only laying out the mathematical details at a high level, but also really clearly explaining the philosophy of how you prove something independent of the axioms. I found it very illuminating. Second, the article has some interesting notes on how mathematicians go about what axioms to select and which not to. Penelope Maddy's "Believing the Axioms" [2] is the classic on this topic (it has two parts). It is focused on set theory, so it has a nice description of Martin's axiom and the arguments for and against. It was nice to read because it is a deeply technical argument (set theory is hard!) but at the same time there is no "right answer"—all of these axioms, after all, are independent of ZFC, and it's "ok" to add any of them. The arguments are sometimes aesthetic ("rules" versus "surprises"), sometimes pragmatic (what they can and cannot prove), and sometimes involve deep values of what the universe should be like (should higher cardinalities be like lower ones? weirder? simpler?). It might all seem abstract, but if your day job is programming, imagine an argument over how to architect a large and complex system. Perhaps both architectures are possible, but which one is "right"? What arguments would you deploy? Set theorists are also building a large and complex system (the universe of sets) and are having arguments over how it should be built, which things it should make easy and which hard, which technologies should be supported natively (forcing?) and which should not. [1] http://timothychow.net/forcing.pdf http://timothychow.net/forcing.pdf [2] https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf
- BoiledCabbage 5y ago
  Why does forcing work? To me it seems flawed (which obviously means I don't understand it fully). For diagonalization argument: 1) Assume every real can be assigned a natural number. 2) Do a bunch of steps that essentially find a new real that differs from any real you have listed from step 1. 3) Conclude that either your steps are flawed, or your initial assumption is wrong 4). Because your steps aren't flawed then your initial assumption (that every real can map to a natural number) is flawed. That all makes sense to me. Forcing seems broken though: 1) Capture of list/set of all real numbers 2) Do a bunch of steps that essentially find a new real that differs from any real you have listed from step 1. 3) Conclude that either your steps are flawed, or your initial assumption is wrong 4). Because your steps aren't flawed then your initial assumption (that you can produce a list of every real number) is flawed. Now you're left in an odd situation. Didn't you just conclude that it's impossible to have a set of all real numbers? Which isn't what you're trying to prove at all.
jaywalk 5y ago
I'm not trying to be flippant, although it may come off that way: why does any of this matter?
- deleted 5y ago
  [deleted]
- sillysaurusx 5y ago
  It took many years to understand that! It’s not a flippant question at all. The answer is, it doesn’t matter. And that’s the joy of it. It wasn’t until I got into ML that I learned the value of doing unimportant work. When you’re free to think about inconsequential matters very seriously, you end up discovering so many useful things. It was how I independently rediscovered what is apparently called the Discrete Hartley Transform. You have a vague notion that what you’re doing might be important, but it’s not the focus. It matters because it’s fun in a way that nothing else can be. Of course, the more serious folk won’t admit it’s fun. It’s serious work. And they’re not wrong; nobody’s fooling around. Our time is every bit as precious as an executive’s. But their goal is to change the world. Ours — or mine, at least — is to know the truth of a thing that most people don’t know.
  - fighterpilot 5y ago
    > it doesn’t matter It doesn't matter yet. Applications of pure math happen downstream decades or centuries later. It's hard to predict the impact.
    - l33t2328 5y ago
      I don’t like this framing because it implies any piece of pure math becoming useful is just a matter of time, and I see no reason to suspect this is the case.
      - bmitc 5y ago
        > I see no reason to suspect this is the case Isn’t history enough reason?
morpheos137 5y ago
It depends on what you define as a number. For example reals and complex have different properties from integers. Is there a mathematical reason why both are considered numbers? You can count (with) integers but not with reals. Thus one appears to be a number while the other appears to be a measure.
- Rerarom 5y ago
  "Number" is not a mathematical term. "Natural number", "real number", "complex number" are. The fact that they all contain the string "number" is completely irrelevant.
- croes 5y ago
  You are confusing numbers with natural numbers. "A number is a mathematical object used to count, measure, and label."
  - morpheos137 5y ago
    You can't count reals or complex numbers. Real numbers by definition describe objects with infinite precision. In the real world infinite precision cannot exist therefore real numbers are the limit of an arbitrary precision measuring process not real themselves. Meanwhile natural numbers like "two" most certainly do exist as a quantitative attribute of a set. Show me how you can count with reals.
    - HelloNurse 5y ago
      In practical terms, "counting and measuring" means well-behaved arithmetic operations like addition, subtraction, multiplication, division, roots etc. (and often specific algebraic structures like rings, fields etc.) Rational and real numbers represent the most intuitive concept of quantity with different cardinality; natural numbers are more basic in theory but a restricted special case in most application (they can only count "countable" objects and they aren't dense); complex numbers compensate unnatural weirdness with important applications; then there are other very number-like niches (e.g. p-adic numbers, quaternions, algebraic extension fields...) and number-based arbitrary constructions (multidimensional vector spaces, matrices and tensors...). > Show me how you can count with reals. Like you count with natural numbers, plus many other possibilities because there are more numbers to count with. The same applies to rational numbers (which exist more than real numbers), complex numbers, etc.
jostmey 5y ago
> "Not all infinities are equal" In other words, there are different categories of infinite, and it might be inappropriate to represent infinity with just one symbol! This article is about how many types of infinity might exist. I was taught there is countably and uncountably infinite. Integers are countably infinite because the number of integers between any two numbers if finite. Real numbers are uncountably infinite because there are infinite numbers between any two real numbers.
- ceh123 5y ago
  >I was taught there is countably and uncountably infinite. Integers are countably infinite because the number of integers between any two numbers if finite. Real numbers are uncountably infinite because there are infinite numbers between any two real numbers. So this isn't exactly right, although I suppose the argument for integers isn't exactly wrong. When we get to the rational numbers however, they are countable but there are an infinite number of rational numbers between any two rationals in the typical way of thinking about "between" numbers. Based on your argument above, this would mean that rationals are uncountable. A better way to think about this is that the set of natural numbers is the first (and smallest) infinite set you can construct. This is the set of all counting numbers so we call it countable. We then say two sets are the same size (cardinality) if you can create a one-to-one mapping between the two that covers both sets (a bijection). This way you exactly pair one element of one set with one element of another. You can do this with the natural numbers and integers by just alternating positive and negative (so 0 -> 0, 1 -> 1, 2 -> -1, 3 -> 2, etc.). All the sets that you can do this sort of mapping with the natural numbers are considered countable. You can't do this sort of mapping from the natural numbers to the reals (see cantor's diagonalization argument) so since you can't "count" the reals, the set is "uncountable."
- jmgao 5y ago
  > I was taught there is countably and uncountably infinite. Integers are countably infinite because the number of integers between any two numbers if finite. Real numbers are uncountably infinite because there are infinite numbers between any two real numbers. This is unsound: a set is countable if there's a mapping that assigns an integer to each element of that set. There are an infinite number of rational numbers between any pair of rational numbers, but you can pretty easily construct a mapping between integers and rationals. Imagine representing a rational x/y as a point on the plane, and draw a square spiral around the origin. Every rational number lays on that spiral, and there's a unique "shortest arc-length of the spiral from the origin" for each rational.
MiddleEndian 5y ago
https://www.smbc-comics.com/comic/the-largest-number-2 https://www.smbc-comics.com/comic/the-largest-number-2 Tangentially related comic
- dwater 5y ago
  I have a degree in math but the first thing this headline made me thing of was still the "24 is the highest number" sketch from Mr. Show: https://www.youtube.com/watch?v=RkP_OGDCLY0 https://www.youtube.com/watch?v=RkP_OGDCLY0 Theoretical mathematics is often absurd, maybe that's why I like the sketch so much.
bmitc 5y ago
If people are interested in this stuff, there’s a great course called Paradox and Infinity going on right now on edX. You’ve missed the first two homework assignments, but there’s still time to get going in the course. The course is based on or supported by the book On the Brink of Paradox.
- bmitc 5y ago
  Some links: https://www.edx.org/course/paradox-and-infinity https://www.edx.org/course/paradox-and-infinity https://ocw.mit.edu/courses/linguistics-and-philosophy/24-118-paradox-and-infinity-spring-2019/ https://ocw.mit.edu/courses/linguistics-and-philosophy/24-11... https://www.amazon.com/Brink-Paradox-Highlights-Intersection-Mathematics/dp/0262039419/ https://www.amazon.com/Brink-Paradox-Highlights-Intersection...
xvilka 5y ago
There is a good video about that on Numberfile[1] [1] https://www.youtube.com/watch?v=5TkIe60y2GI https://www.youtube.com/watch?v=5TkIe60y2GI
privatdozent 5y ago
Another great piece from Quanta. Such an important institution
question000 5y ago
The only thing this proves is that mathematics is a soft science, where concepts like "number" and "infinite" are subjective. There are obviously infinite numbers, if you think there's a finite number of numbers, take that number and add one to that. QED
- creddit 5y ago
  1) Mathematics is in no way a science. 2) I think you didn't read the article at all.
  - question000 5y ago
    Yeah of course I didn't read the article. It's literally was the same as an article saying "Cows are green! If you're smart enough it becomes math!" I can't feed the clickbait machine.
- dang 5y ago
  "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
  - question000 5y ago
    I can't believe you called this shallow and didn't even include an explanation as to why, ironic. There's nothing shallow about this at all, it goes to the heart of this fake intellectualism on this site.
    - dang 5y ago
      It's shallow because (a) contentless denunciations of "soft science" are cliché; (b) reducing serious mathematical work to "obvious" is the worst sort of dismissal. Please don't post like this to HN. We're trying for higher-quality discussion. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
btilly 5y ago
As a constructivist I'll be over in the corner that says that there are only a countable number of real numbers, and the unimaginable number of unimaginable infinities that classical mathematics insiste exists is all made up nonsense. That, in fact, things that can't ever be named, even in principle, don't actually exist. What is interesting is that as shocking as constructivism may be, there is no logical flaw in it. If classical mathematics is consistent, then so is constructivism. And "there exists" is a whole lot more meaningful in constructivism.
- scapp 5y ago
  You sound like you need to read this [0] answer to the question "Are real numbers countable in constructive mathematics?". > You are using the word "constructive" in an unusual way. It is true that, in ZFC, the set of computable real numbers is countable, but that is not directly a statement about constructive mathematics. > Not every school of constructive mathematics identifies real numbers with algorithms; that's a characteristic of the "Russian" school as I understand it. In other schools of constructivism that I am more familiar with, real numbers are coded by elements of 2^ω, or by a certain type of Dedekind cut on the rationals. In such schools it is not universally assumed that every real number is associated with a finite algorithm. > Even in the Russian school, they would not say that the set of real numbers is countable. Because, if you identify real numbers with algorithms, there is no computable enumeration of computable reals that lists all computable reals, and so the translation of "the real numbers are countable" into this setting is false. > That phenomenon also occurs in classical computable analysis. The subsystem RCA0 of second-order arithmetic has a model in which every real number is computable. But this subsystem still proves that there is no surjection N -> R. --- It's worth noting that another answer to that question (Andrej Bauer's) gives a constructive proof that the real numbers are uncountable using with the axiom of countable choice. The question of whether it's provable without the axiom of countable choice is open (though see this [1] fairly recent paper on a proof for MacNeille reals). [0] https://mathoverflow.net/questions/30643/are-real-numbers-countable-in-constructive-mathematics/30657#30657 https://mathoverflow.net/questions/30643/are-real-numbers-co... [1] https://arxiv.org/abs/1902.07366 https://arxiv.org/abs/1902.07366
  - 5y ago
mmmBacon 5y ago
Maybe I misunderstood the article but if the set of real numbers is finite then it should be countable. But I can easily prove that the set of real numbers or any subset of real numbers is not countable. Been a really long time since I’ve thought about this but wondering what I’m missing.
- Sharlin 5y ago
  No, what the article is talking about is the question whether or not the cardinality of real numbers is the smallest uncountable infinity or some other, larger uncountable infinity. The only countable infinity is aleph-0, the cardinality of natural numbers, and Cantor showed that aleph-0 is too small to hold all reals. So reals must be uncountable, but there is an infinite hierarchy of uncountable infinities, and it is not known which one is the cardinality of reals (although in practice it's suspected to be either aleph-1, which is what the Continuum Hypothesis states, or aleph-2).
  - keymone 5y ago
    unrelated: how do we know there are no alephs between 0 and 1?
    - Sharlin 5y ago
      If you assume Axiom of Choice, you can define cardinalities in terms of ordinal numbers (an extension of naturals that generalizes the notion of "counting", or "indexing"). And ordinal numbers are well-ordered, ie. every element has a unique "successor" element.
    - elcomet 5y ago
      That's the definition of aleph-1. The continuum hypothesis is that 2^aleph-0 (number of sets of integers or number of reals) = aleph-1.
  - orangecat 5y ago
    (although in practice it's suspected to be either aleph-1, which is what the Continuum Hypothesis states, or aleph-2) There are some arguments that it's "really" much larger, as in greater than aleph-n for any finite n. See https://risingentropy.com/the-continuum-hypothesis-is-false/ https://risingentropy.com/the-continuum-hypothesis-is-false/ (incidentally an excellent blog if you're interested in these sorts of things).
dwohnitmok 5y ago
Man there's a lot of juicy stuff in this article (Woodin's Ultimate L program gets briefly alluded to at the end of the article). I just want to point out, because the HN crowd seems to generally not be mathematical Platonists, that this entire article is implicitly assuming a Platonist philosophical foundation. This may cause confusion for lay readers who are not mathematical Platonists. In other words the article assumes that mathematical objects have an objective existence: they either exist or they do not. Hence every single logical axiom has a truth value. You do not get to arbitrarily choose what logical axioms you want. If you do, you can end up choosing the "wrong one." Therefore it is an important question to understand whether the Continuum Hypothesis is true or not, even if it's independent of ZFC (and hence requires ultimately philosophical rather than mathematical arguments). If you aren't a Platonist and instead view logical axioms as having no inherent truth value, but rather foundations that you can pick and choose from as necessary (where in one case you may choose to use an axiom and in another you may choose its negation), then all that might sound very strange to you. In that case, you should mentally substitute every instance of "true" or "false" in the article with "agrees or disagrees with the meta model used to examine the semantics of a logical theory." In particular, whenever we talk about a formal treatment of the semantics (i.e. model) of a theory, whether that be something like ZFC or a programming language, we must always make those statements relative to a meta-model. For example if we talk about the formal semantics of a language like C, we must first posit a meta-model which already contains notions of things like "integer" and "natural number" which can be used to give meaning to statements such as "performed an operation n times." If you're not a Platonist then you probably believe that there are multiple possible meta-models you could use.
- goldenkey 5y ago
  Individually, or independently, axioms have no truth value. But when you put together a system of multiple axioms, they can contradict eachother. I see no problem with the question of whether the continuum hypothesis is true, given ZFC as a precondition. All we are asking is if the axiom contradicts ZFC. Axiom independence is very similar to operator commutation in quantum mechanics.
  - 5y ago
pelorat 5y ago
The existence of addition implies that the answer is infinity. Too simple an explanation for mathematicians obviously.
- Sharlin 5y ago
  The whole point of the article is that we don't know which infinity it is.
- howderek 5y ago
  They know it is infinite. They want to understand the cardinality. Any two sets (including infinite sets) A, B have the same cardinality if there exists a bijection from A|->B
- throwawayboise 5y ago
  I didn't read the paper, and have only an undergraduate math background, but it seems to me that for sufficiently large n, n + 1 = n. Vague justifications related to limits.
dexwiz 5y ago
I'm no mathematician, but I have always found it strange infinities are talked about as physical states (towers of tall towers, etc), and not functions. Integer number counting is essentially a successor function; take N, add 1, output N+1. One input, one output. Real number counting is a bit more loose. To find the numbers between .1 and .2, you find all fractionals of a given size, normally 1/10. So we get .10, .11, .12, etc. This function gives more outputs than inputs, thus an increase in cardinality. Forcing just seems like changing the function to increase the cardinality. In my mind, all infinities are equal, it's how you generate them that matters.
- IncRnd 5y ago
  I'm not a mathematician, either, but I believe your comment shows why not all infinities are equal. When you attempt to enumerate .1, .2, .3, .4, etc. you get an infinite count of numbers. However, when you perform that same operation on .05, .15, .2, .25, and so on, you will get "twice as many numbers" as the first time around. In this way, the second infinite sequence has "twice as many numbers" as the first infinite sequence.
  - gowld 5y ago
    No, it doesn't. Then have the same number, as can be plainly seen by lining them up and counting the elements in order.
- zeugmasyllepsis 5y ago
  > Real number counting is a bit more loose. To find the numbers between .1 and .2, you find all fractionals of a given size, normally 1/10. Unfortunately the fractionals method does not work, since there are numbers (in fact, uncountably infinitely many!) irrational numbers which cannot be expressed as fractions, which are nonetheless real numbers (such as the square root of two and pi).
- drdeca 5y ago
  There is a way of mapping different ordinal numbers which are less than some large countable ordinal (idr how high up it goes. I suspect it isn’t well defined at least past the church kleene ordinal, but I think it is much before that, but also I could be totally wrong) to different functions from integers to integers which increase at different rates. These methods include the Hardy hierarchy, and the fast growing hierarchy. (But regarding all infinities being equal, that’s just incorrect, sorry.)
123pie123 5y ago
I've always been brought up to realise that math(s) is not real. It's more of a (extremely) good system to model stuff, say like a map isn't real, but just a representation so this proof is pushing the system of this math(s) system
- svachalek 5y ago
  The deeper physics goes, the more apparent it is that our perception of reality is a good model for what is happening at our scale in the universe and the forces that are dominant at that scale. Our intuition breaks down at larger and smaller scales, but the math still works. So in some sense, math is the truest access we have to reality.
kibwen 5y ago
> Woodin named the axiom (*), pronounced “star,” because it was “like a bright source — a source of structure, a source of light,” he told me. There are only two hard problems in mathematics: infinity and naming things.
phkahler 5y ago
You can map all the real numbers to the interval 0 <= x < 1. To map one of those reals to an integer, simply write it's trailing digits in reverse order on the left side of the decimal point. You may then drop any leading zeros. 0.0 => 0 0.1 => 1 0.2 => 2 ... 0.14159 => 95141 The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? Can there be an "infinitely large integer?" or are there just infinitely many of them? I think this question gets to the core of the problem.
- question000 5y ago
 "Can there be an infinitely large integer" No there can't there's always a larger integer. Anyone who claims otherwise is just making stuff up. It's just mind blowing to me that anyone think otherwise, it's like asking what the final digit of pi is, you'd get laughed out of any college class for insisting there might be one, rightly so.
- victorbojica 5y ago
 But if you assign them randomly, then it should work 1->5.85916 2->8.7599 ... Or even randomize the order for the integers 5->7.52256951 77->848.455 ...
 - bonzini 5y ago
 You can't, this is Cantor's diagonal counterexample.
- gowld 5y ago
 > Can there be an "infinitely large integer?" What could that even mean? Aren't integers all defined as Succ^n(x) for a finite n and a base x?
- red_trumpet 5y ago
 > You can map all the real numbers to the interval 0 <= x < 1. Even easier use a well-established function such as arctan to map the reals bijectively to the interval -π/2 < x < π/2, and then scale and shift the interval to 0 < x < 1.
daxfohl 5y ago
A related thing that occurred to me the other day: there's some number in [0, 1] that encodes every state of every possible Turing machine (the number of Turing machines is countable, the duration of its run is countable, and the states at each step are countable, so you can diagonalize that and make a real number out of it). I'm pretty sure you can take that further and show that all possible mathematical proofs, including the Godel unsolvable ones (I think...they're just proofs that are infinitely long but countably so), can also be encoded in a single real number. That makes it feel like the reals are pretty big.
- Rinum 5y ago
  I think you'll like this - https://youtu.be/HeQX2HjkcNo https://youtu.be/HeQX2HjkcNo
- ttctciyf 5y ago
  This sounds a little like Chaitin's constant Omega (Ω), which is very roughly a number in [0, 1] which is the probability that a randomly chosen program (for a universal Turing machine, U) will halt. This has the interesting property that knowing the first n bits of Ω allows you to determine whether any program (for U) of length up to n will halt, in other words you could solve the halting problem for programs of length up to n. As Wikipedia puts it: > Because many outstanding problems in number theory, such as Goldbach's conjecture, are equivalent to solving the halting problem for special programs (which would basically search for counter-examples and halt if one is found), knowing enough bits of Chaitin's constant would also imply knowing the answer to these problems. But as the halting problem is not generally solvable, and therefore calculating any but the first few bits of Chaitin's constant is not possible, this just reduces hard problems to impossible ones, much like trying to build an oracle machine for the halting problem would be. - https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
sharpener 5y ago
The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0] Being charitable one might argue that the meanings of terminology had been lost in translation over time and that perhaps Cantor was trying to create non-standard analysis, but then the diagonal argument seems to represent nothing more than the truism that finite numbers are smaller than transfinite ones. Hence I worry about people who are still worrying about this issue, and I worry for the future of science and AI in particular if folks can't get clear of it. [0] https://www.researchgate.net/publication/328568169_The_Case_Against_Cantor's_Diagonal_Argument https://www.researchgate.net/publication/328568169_The_Case_... Yes, I'm that guy who wrote that.
- myWindoonn 5y ago
  Hi, Lawvere pummelled your position into the ground a while ago: http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf Your critique involves repeatedly crossing the boundary between the inside and outside of the system in question; Lawvere works entirely inside the system, and shows that the paradoxes of self-reference arise from our interpretations. https://arxiv.org/abs/math/0305282v1 https://arxiv.org/abs/math/0305282v1 explains with many examples. Hi downvoters: Use your words when somebody is wrong. Your downvotes aren't helpful here for finding the truth.
  - sharpener 5y ago
    I'm not seeing this yet. Perhaps you could explain it to me in plain terms.
    - myWindoonn 5y ago
      Pick any Cartesian closed category. Says Lawvere: If there exists t : Y -> Y such that t;y != y for all y : 1 -> Y then for no A does there exist a surjection A -> (A -> Y). (He actually says something much stronger.) Note that the first half of this is saying "if there exists t such that t has no fixed points..." Let our category be Set, the category of sets and functions; it is well-known to be Cartesian closed. Let A be the set of natural numbers and let Y be the Booleans. Then Lawvere is saying that there is no surjection N -> (N -> 2), and thus definitely no bijection, because there is a function 2 -> 2 with no fixed points: the negation function which swaps true and false has no fixed point. It does not get much plainer without actually reading Lawvere and/or Yanofsky directly, sorry. I hope that this helps explain how inescapable this sort of theorem is.
Decker87 5y ago
Honest question, what is the usefulness of proving such an obvious thing?
joe_the_user 5y ago
For 50 years, mathematicians have believed that the total number of real numbers is unknowable. It's an established result that the Continuum Hypothesis is independent of Zermelo–Fraenkel axioms of set theory. No proof is going change that. So whatever has been proved here doesn't change that. It will take a second to get the reference but Raymond Smullyan says essentially that "we're not looking for a proof or disproof of CH, we're looking for an assumption that can be shown to be natural enough that we can take it as an axiom". Just sayin' since the (subheading) writer seems to be playing fast and loose with the concepts involved. Edit: article goes on to give rigorous explanation but still starting "no one knew" confuses what's going on.
ncmncm 5y ago
> How many real numbers exist? You might be tempted to say "lots". And you would be right, as far as that goes. But that doesn't satisfy a real mathematician. The question that immediately arises is whether "lots" is "enough". And that leads the better sort of mathematician inevitably to: "enough for what?" That is what mathematicians are deep in the middle of exploring, now. For example, when you are asked, "Does this skirt make my butt look too big?", you obviously must not say "yes", but you just as obviously cannot, with an entirely clear conscience, say "no", either. But for anyone with an intact survival instinct, the counter-question, "too big for what?" should spring immediately to mind. And it's a good one, but it depends intimately on the true size of the set of real numbers. So, this is not an idle pursuit.
- 90minuteAPI 5y ago
  Answering “Does this skirt make my butt look too big?” with something that “depends intimately on the true size of the set of real numbers” seems to be among the worst strategies.
  - ncmncm 5y ago
    The mathematics of infinities are nothing if not counterintuitive.
- rkagerer 5y ago
  "Does this skirt make my butt look too big?" "Too big for what?" Yeah let me know how that works out.
  - philipswood 5y ago
    Yes, the call for more experimentation to keep theorists honest.
- whoaisme 5y ago
  Ken M is that you?
01GOD 5y ago
I suspect the op was trolling the hackernews community to intentionally cause a big mathsturbatory circlejerk. Golf clap on how amazingly effective that was.
zeven7 5y ago
What online class should I take to learn more about this topic in particular?
chasing 5y ago
There are exactly 1,837 real numbers and anyone who tells you any different is just trying to sell you something.
js8 5y ago
I have a question, so assuming that we adopt the axiom(s) that cause real numbers to be cardinality Aleph_2 and not Aleph_1, is then there some intuitive explanation how does the set of size Aleph_1 looks like, and what it could be used for?
tromp 5y ago
The explanation of Cohen's filter for making new reals reminds me of surreal numbers {L | R} but in this case every real is in either L or R. Still, I fail to see how that gives you more than restricting L and R to contain only rational numbers...
kkylin 5y ago
Those with a bit more math background may enjoy Cohen's own perspective on the discovery of forcing: https://projecteuclid.org/journals/rocky-mountain-journal-of-mathematics/volume-32/issue-4/The-Discovery-of-Forcing/10.1216/rmjm/1181070010.full https://projecteuclid.org/journals/rocky-mountain-journal-of... (Not technical as these things go, but helps to have a little knowledge of logic / set theory and some amount of "mathematical maturity.")
ProfHewitt 5y ago
The results in the article are based on 1st-order logic, which is inadequate for the foundations of mathematics. Mathematical abstractions need to be characterized up a unique isomorphism as in the theory Ordinals described in the following article: "Theory Ordinals can Replace ZFC in Computer Science" https://papers.ssrn.com/abstract=3457802 Mathematical questions can be properly addressed only by using adequate foundations.
- ProfHewitt 5y ago
 PS. There are no ordinals of intermediate cardinality between ω0 and ω1.
devit 5y ago
In addition to adding the continuum axiom or its negation, there's also the approach of restricting oneself to computable sets and thus only having countable infinities.
renanbg 5y ago
I find this very much fascinating, although I can't understand it. I hope I can, eventually, fully appreciate "higher math" questioning like this one, and would be really grateful if someone could point me what to study, as an "amateur mathematician" with only background on engineering calculus.
pachico 5y ago
I thought this was already solved decades ago by Mr. Show: https://m.youtube.com/watch?v=RkP_OGDCLY0 https://m.youtube.com/watch?v=RkP_OGDCLY0 Sorry, I couldn't resist.
ruggeri 5y ago
I should finish reading the linked article. But I have a quick initial question. Proofs in ZFC can be enumerated by a machine. In theory, we could devise a machine that (1) will certainly eventually halt iff ZFC is inconsistent (proves two contradictory statements), or (2) will never halt iff ZFC is consistent. (Caveats: naturally, if ZFC is consistent, we'll never learn whether we should just keep waiting for the machine to find a contradiction. And our machine will require unbounded storage space.) Can we build a corresponding device that would have different behaviors depending on whether the continuum hypothesis is "true" (whatever that means)? I suppose the computational model would be Turing machine as above.

501 points by theafh 5y ago

I don’t get for Cantor’s diagonalization proof, why do we need to use the diagonal digits to form the new number? Would the proof work the same if we instead used the first digit of every number in the list?

miloignis 5y ago
There are only 10 possible first digits of the new number, so you can't choose a number that will differ from all other numbers in the first digit. If you do it diagonally, you'll always have 9 other options to choose from, since you just have to make it different from that one number!
- arduinomancer 5y ago
  Makes sense, thanks
tpetrina 5y ago
That wouldn't work because n-th digit differing from 1st digit of n-th number doesn't guarantee that the new number isn't accounted for already.
pavpanchekha 5y ago
To fill in some details: Two real numbers are different if in the same place they have different digits. [1] So the idea is to take your infinite, hypothetical list of all real numbers A[] and make a new real number X, where for all i, there's some digit where A[i] and X differ. Easiest way is to make X differ from A[i] at digit i. [1] There's a subtlety here about repeating nines at the end of a number, but it is inessential.
pfortuny 5y ago
Then you cannot guarantee that when you change the first digit of the second number, what you get is not the first number.
erdos4d 5y ago
You need the diagonal because you are making a new number in (0,1) that can't be in the list by just choosing the nth digit of said number different than the nth digit of the diagonal.
ceh123 5y ago
To give a concrete example for you, lets start with the finite set: {0.22, 0.32, 0.33} We now construct a new number in this way: First digit of the first number is 2, so we take 3 which is different as our first digit. First digit of the second number is 3 so we take 2 as our second number. Now we have 0.32 First digit of the third number is 3 so we take 0 as our third number. We've constructed the number: 0.320 = 0.32 which is in the set already. So this construction method doesn't guarantee that it's a new number, only that it's different from the first. With Cantor's Diagonalization argument we guarantee it's different from the first number since it's different in the first digit, then we guarantee it's different from the second since it's different in the second digit, etc. etc. it's different from all the numbers in our list. To take the same set above as an example, we end up creating a number like: 0.318 which is definitely different from the numbers in the set

pavpanchekha 5y ago

Great article. Since it looks like a lot of folks are interested in this article, some extra background. First, what is forcing? The article actually has a great description of ultrapowers (a key part of the construction) but it goes by a little fast, so you might like Tim Chow's "A beginner's guide to forcing" [1] which does a good job not only laying out the mathematical details at a high level, but also really clearly explaining the philosophy of how you prove something independent of the axioms. I found it very illuminating. Second, the article has some interesting notes on how mathematicians go about what axioms to select and which not to. Penelope Maddy's "Believing the Axioms" [2] is the classic on this topic (it has two parts). It is focused on set theory, so it has a nice description of Martin's axiom and the arguments for and against. It was nice to read because it is a deeply technical argument (set theory is hard!) but at the same time there is no "right answer"—all of these axioms, after all, are independent of ZFC, and it's "ok" to add any of them. The arguments are sometimes aesthetic ("rules" versus "surprises"), sometimes pragmatic (what they can and cannot prove), and sometimes involve deep values of what the universe should be like (should higher cardinalities be like lower ones? weirder? simpler?). It might all seem abstract, but if your day job is programming, imagine an argument over how to architect a large and complex system. Perhaps both architectures are possible, but which one is "right"? What arguments would you deploy? Set theorists are also building a large and complex system (the universe of sets) and are having arguments over how it should be built, which things it should make easy and which hard, which technologies should be supported natively (forcing?) and which should not. [1] http://timothychow.net/forcing.pdf http://timothychow.net/forcing.pdf [2] https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf

BoiledCabbage 5y ago
Why does forcing work? To me it seems flawed (which obviously means I don't understand it fully). For diagonalization argument: 1) Assume every real can be assigned a natural number. 2) Do a bunch of steps that essentially find a new real that differs from any real you have listed from step 1. 3) Conclude that either your steps are flawed, or your initial assumption is wrong 4). Because your steps aren't flawed then your initial assumption (that every real can map to a natural number) is flawed. That all makes sense to me. Forcing seems broken though: 1) Capture of list/set of all real numbers 2) Do a bunch of steps that essentially find a new real that differs from any real you have listed from step 1. 3) Conclude that either your steps are flawed, or your initial assumption is wrong 4). Because your steps aren't flawed then your initial assumption (that you can produce a list of every real number) is flawed. Now you're left in an odd situation. Didn't you just conclude that it's impossible to have a set of all real numbers? Which isn't what you're trying to prove at all.

jaywalk 5y ago

I'm not trying to be flippant, although it may come off that way: why does any of this matter?

deleted 5y ago
[deleted]
sillysaurusx 5y ago
It took many years to understand that! It’s not a flippant question at all. The answer is, it doesn’t matter. And that’s the joy of it. It wasn’t until I got into ML that I learned the value of doing unimportant work. When you’re free to think about inconsequential matters very seriously, you end up discovering so many useful things. It was how I independently rediscovered what is apparently called the Discrete Hartley Transform. You have a vague notion that what you’re doing might be important, but it’s not the focus. It matters because it’s fun in a way that nothing else can be. Of course, the more serious folk won’t admit it’s fun. It’s serious work. And they’re not wrong; nobody’s fooling around. Our time is every bit as precious as an executive’s. But their goal is to change the world. Ours — or mine, at least — is to know the truth of a thing that most people don’t know.
- fighterpilot 5y ago
  > it doesn’t matter It doesn't matter yet. Applications of pure math happen downstream decades or centuries later. It's hard to predict the impact.
  - l33t2328 5y ago
    I don’t like this framing because it implies any piece of pure math becoming useful is just a matter of time, and I see no reason to suspect this is the case.
    - bmitc 5y ago
      > I see no reason to suspect this is the case Isn’t history enough reason?

morpheos137 5y ago

It depends on what you define as a number. For example reals and complex have different properties from integers. Is there a mathematical reason why both are considered numbers? You can count (with) integers but not with reals. Thus one appears to be a number while the other appears to be a measure.

Rerarom 5y ago
"Number" is not a mathematical term. "Natural number", "real number", "complex number" are. The fact that they all contain the string "number" is completely irrelevant.
croes 5y ago
You are confusing numbers with natural numbers. "A number is a mathematical object used to count, measure, and label."
- morpheos137 5y ago
  You can't count reals or complex numbers. Real numbers by definition describe objects with infinite precision. In the real world infinite precision cannot exist therefore real numbers are the limit of an arbitrary precision measuring process not real themselves. Meanwhile natural numbers like "two" most certainly do exist as a quantitative attribute of a set. Show me how you can count with reals.
  - HelloNurse 5y ago
    In practical terms, "counting and measuring" means well-behaved arithmetic operations like addition, subtraction, multiplication, division, roots etc. (and often specific algebraic structures like rings, fields etc.) Rational and real numbers represent the most intuitive concept of quantity with different cardinality; natural numbers are more basic in theory but a restricted special case in most application (they can only count "countable" objects and they aren't dense); complex numbers compensate unnatural weirdness with important applications; then there are other very number-like niches (e.g. p-adic numbers, quaternions, algebraic extension fields...) and number-based arbitrary constructions (multidimensional vector spaces, matrices and tensors...). > Show me how you can count with reals. Like you count with natural numbers, plus many other possibilities because there are more numbers to count with. The same applies to rational numbers (which exist more than real numbers), complex numbers, etc.

jostmey 5y ago

> "Not all infinities are equal" In other words, there are different categories of infinite, and it might be inappropriate to represent infinity with just one symbol! This article is about how many types of infinity might exist. I was taught there is countably and uncountably infinite. Integers are countably infinite because the number of integers between any two numbers if finite. Real numbers are uncountably infinite because there are infinite numbers between any two real numbers.

ceh123 5y ago
>I was taught there is countably and uncountably infinite. Integers are countably infinite because the number of integers between any two numbers if finite. Real numbers are uncountably infinite because there are infinite numbers between any two real numbers. So this isn't exactly right, although I suppose the argument for integers isn't exactly wrong. When we get to the rational numbers however, they are countable but there are an infinite number of rational numbers between any two rationals in the typical way of thinking about "between" numbers. Based on your argument above, this would mean that rationals are uncountable. A better way to think about this is that the set of natural numbers is the first (and smallest) infinite set you can construct. This is the set of all counting numbers so we call it countable. We then say two sets are the same size (cardinality) if you can create a one-to-one mapping between the two that covers both sets (a bijection). This way you exactly pair one element of one set with one element of another. You can do this with the natural numbers and integers by just alternating positive and negative (so 0 -> 0, 1 -> 1, 2 -> -1, 3 -> 2, etc.). All the sets that you can do this sort of mapping with the natural numbers are considered countable. You can't do this sort of mapping from the natural numbers to the reals (see cantor's diagonalization argument) so since you can't "count" the reals, the set is "uncountable."
jmgao 5y ago
> I was taught there is countably and uncountably infinite. Integers are countably infinite because the number of integers between any two numbers if finite. Real numbers are uncountably infinite because there are infinite numbers between any two real numbers. This is unsound: a set is countable if there's a mapping that assigns an integer to each element of that set. There are an infinite number of rational numbers between any pair of rational numbers, but you can pretty easily construct a mapping between integers and rationals. Imagine representing a rational x/y as a point on the plane, and draw a square spiral around the origin. Every rational number lays on that spiral, and there's a unique "shortest arc-length of the spiral from the origin" for each rational.

MiddleEndian 5y ago

https://www.smbc-comics.com/comic/the-largest-number-2 https://www.smbc-comics.com/comic/the-largest-number-2 Tangentially related comic

dwater 5y ago
I have a degree in math but the first thing this headline made me thing of was still the "24 is the highest number" sketch from Mr. Show: https://www.youtube.com/watch?v=RkP_OGDCLY0 https://www.youtube.com/watch?v=RkP_OGDCLY0 Theoretical mathematics is often absurd, maybe that's why I like the sketch so much.

bmitc 5y ago

If people are interested in this stuff, there’s a great course called Paradox and Infinity going on right now on edX. You’ve missed the first two homework assignments, but there’s still time to get going in the course. The course is based on or supported by the book On the Brink of Paradox.

bmitc 5y ago
Some links: https://www.edx.org/course/paradox-and-infinity https://www.edx.org/course/paradox-and-infinity https://ocw.mit.edu/courses/linguistics-and-philosophy/24-118-paradox-and-infinity-spring-2019/ https://ocw.mit.edu/courses/linguistics-and-philosophy/24-11... https://www.amazon.com/Brink-Paradox-Highlights-Intersection-Mathematics/dp/0262039419/ https://www.amazon.com/Brink-Paradox-Highlights-Intersection...

xvilka 5y ago

There is a good video about that on Numberfile[1] [1] https://www.youtube.com/watch?v=5TkIe60y2GI https://www.youtube.com/watch?v=5TkIe60y2GI

privatdozent 5y ago

Another great piece from Quanta. Such an important institution

question000 5y ago

The only thing this proves is that mathematics is a soft science, where concepts like "number" and "infinite" are subjective. There are obviously infinite numbers, if you think there's a finite number of numbers, take that number and add one to that. QED

creddit 5y ago
1) Mathematics is in no way a science. 2) I think you didn't read the article at all.
- question000 5y ago
  Yeah of course I didn't read the article. It's literally was the same as an article saying "Cows are green! If you're smart enough it becomes math!" I can't feed the clickbait machine.
dang 5y ago
"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- question000 5y ago
  I can't believe you called this shallow and didn't even include an explanation as to why, ironic. There's nothing shallow about this at all, it goes to the heart of this fake intellectualism on this site.
  - dang 5y ago
    It's shallow because (a) contentless denunciations of "soft science" are cliché; (b) reducing serious mathematical work to "obvious" is the worst sort of dismissal. Please don't post like this to HN. We're trying for higher-quality discussion. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html

btilly 5y ago

As a constructivist I'll be over in the corner that says that there are only a countable number of real numbers, and the unimaginable number of unimaginable infinities that classical mathematics insiste exists is all made up nonsense. That, in fact, things that can't ever be named, even in principle, don't actually exist. What is interesting is that as shocking as constructivism may be, there is no logical flaw in it. If classical mathematics is consistent, then so is constructivism. And "there exists" is a whole lot more meaningful in constructivism.

scapp 5y ago
You sound like you need to read this [0] answer to the question "Are real numbers countable in constructive mathematics?". > You are using the word "constructive" in an unusual way. It is true that, in ZFC, the set of computable real numbers is countable, but that is not directly a statement about constructive mathematics. > Not every school of constructive mathematics identifies real numbers with algorithms; that's a characteristic of the "Russian" school as I understand it. In other schools of constructivism that I am more familiar with, real numbers are coded by elements of 2^ω, or by a certain type of Dedekind cut on the rationals. In such schools it is not universally assumed that every real number is associated with a finite algorithm. > Even in the Russian school, they would not say that the set of real numbers is countable. Because, if you identify real numbers with algorithms, there is no computable enumeration of computable reals that lists all computable reals, and so the translation of "the real numbers are countable" into this setting is false. > That phenomenon also occurs in classical computable analysis. The subsystem RCA0 of second-order arithmetic has a model in which every real number is computable. But this subsystem still proves that there is no surjection N -> R. --- It's worth noting that another answer to that question (Andrej Bauer's) gives a constructive proof that the real numbers are uncountable using with the axiom of countable choice. The question of whether it's provable without the axiom of countable choice is open (though see this [1] fairly recent paper on a proof for MacNeille reals). [0] https://mathoverflow.net/questions/30643/are-real-numbers-countable-in-constructive-mathematics/30657#30657 https://mathoverflow.net/questions/30643/are-real-numbers-co... [1] https://arxiv.org/abs/1902.07366 https://arxiv.org/abs/1902.07366
- 5y ago

mmmBacon 5y ago

Maybe I misunderstood the article but if the set of real numbers is finite then it should be countable. But I can easily prove that the set of real numbers or any subset of real numbers is not countable. Been a really long time since I’ve thought about this but wondering what I’m missing.

Sharlin 5y ago
No, what the article is talking about is the question whether or not the cardinality of real numbers is the smallest uncountable infinity or some other, larger uncountable infinity. The only countable infinity is aleph-0, the cardinality of natural numbers, and Cantor showed that aleph-0 is too small to hold all reals. So reals must be uncountable, but there is an infinite hierarchy of uncountable infinities, and it is not known which one is the cardinality of reals (although in practice it's suspected to be either aleph-1, which is what the Continuum Hypothesis states, or aleph-2).
- keymone 5y ago
  unrelated: how do we know there are no alephs between 0 and 1?
  - Sharlin 5y ago
    If you assume Axiom of Choice, you can define cardinalities in terms of ordinal numbers (an extension of naturals that generalizes the notion of "counting", or "indexing"). And ordinal numbers are well-ordered, ie. every element has a unique "successor" element.
  - elcomet 5y ago
    That's the definition of aleph-1. The continuum hypothesis is that 2^aleph-0 (number of sets of integers or number of reals) = aleph-1.
- orangecat 5y ago
  (although in practice it's suspected to be either aleph-1, which is what the Continuum Hypothesis states, or aleph-2) There are some arguments that it's "really" much larger, as in greater than aleph-n for any finite n. See https://risingentropy.com/the-continuum-hypothesis-is-false/ https://risingentropy.com/the-continuum-hypothesis-is-false/ (incidentally an excellent blog if you're interested in these sorts of things).

dwohnitmok 5y ago

Man there's a lot of juicy stuff in this article (Woodin's Ultimate L program gets briefly alluded to at the end of the article). I just want to point out, because the HN crowd seems to generally not be mathematical Platonists, that this entire article is implicitly assuming a Platonist philosophical foundation. This may cause confusion for lay readers who are not mathematical Platonists. In other words the article assumes that mathematical objects have an objective existence: they either exist or they do not. Hence every single logical axiom has a truth value. You do not get to arbitrarily choose what logical axioms you want. If you do, you can end up choosing the "wrong one." Therefore it is an important question to understand whether the Continuum Hypothesis is true or not, even if it's independent of ZFC (and hence requires ultimately philosophical rather than mathematical arguments). If you aren't a Platonist and instead view logical axioms as having no inherent truth value, but rather foundations that you can pick and choose from as necessary (where in one case you may choose to use an axiom and in another you may choose its negation), then all that might sound very strange to you. In that case, you should mentally substitute every instance of "true" or "false" in the article with "agrees or disagrees with the meta model used to examine the semantics of a logical theory." In particular, whenever we talk about a formal treatment of the semantics (i.e. model) of a theory, whether that be something like ZFC or a programming language, we must always make those statements relative to a meta-model. For example if we talk about the formal semantics of a language like C, we must first posit a meta-model which already contains notions of things like "integer" and "natural number" which can be used to give meaning to statements such as "performed an operation n times." If you're not a Platonist then you probably believe that there are multiple possible meta-models you could use.

goldenkey 5y ago
Individually, or independently, axioms have no truth value. But when you put together a system of multiple axioms, they can contradict eachother. I see no problem with the question of whether the continuum hypothesis is true, given ZFC as a precondition. All we are asking is if the axiom contradicts ZFC. Axiom independence is very similar to operator commutation in quantum mechanics.
- 5y ago

pelorat 5y ago

The existence of addition implies that the answer is infinity. Too simple an explanation for mathematicians obviously.

Sharlin 5y ago
The whole point of the article is that we don't know which infinity it is.
howderek 5y ago
They know it is infinite. They want to understand the cardinality. Any two sets (including infinite sets) A, B have the same cardinality if there exists a bijection from A|->B
throwawayboise 5y ago
I didn't read the paper, and have only an undergraduate math background, but it seems to me that for sufficiently large n, n + 1 = n. Vague justifications related to limits.

dexwiz 5y ago

I'm no mathematician, but I have always found it strange infinities are talked about as physical states (towers of tall towers, etc), and not functions. Integer number counting is essentially a successor function; take N, add 1, output N+1. One input, one output. Real number counting is a bit more loose. To find the numbers between .1 and .2, you find all fractionals of a given size, normally 1/10. So we get .10, .11, .12, etc. This function gives more outputs than inputs, thus an increase in cardinality. Forcing just seems like changing the function to increase the cardinality. In my mind, all infinities are equal, it's how you generate them that matters.

IncRnd 5y ago
I'm not a mathematician, either, but I believe your comment shows why not all infinities are equal. When you attempt to enumerate .1, .2, .3, .4, etc. you get an infinite count of numbers. However, when you perform that same operation on .05, .15, .2, .25, and so on, you will get "twice as many numbers" as the first time around. In this way, the second infinite sequence has "twice as many numbers" as the first infinite sequence.
- gowld 5y ago
  No, it doesn't. Then have the same number, as can be plainly seen by lining them up and counting the elements in order.
zeugmasyllepsis 5y ago
> Real number counting is a bit more loose. To find the numbers between .1 and .2, you find all fractionals of a given size, normally 1/10. Unfortunately the fractionals method does not work, since there are numbers (in fact, uncountably infinitely many!) irrational numbers which cannot be expressed as fractions, which are nonetheless real numbers (such as the square root of two and pi).
drdeca 5y ago
There is a way of mapping different ordinal numbers which are less than some large countable ordinal (idr how high up it goes. I suspect it isn’t well defined at least past the church kleene ordinal, but I think it is much before that, but also I could be totally wrong) to different functions from integers to integers which increase at different rates. These methods include the Hardy hierarchy, and the fast growing hierarchy. (But regarding all infinities being equal, that’s just incorrect, sorry.)

123pie123 5y ago

I've always been brought up to realise that math(s) is not real. It's more of a (extremely) good system to model stuff, say like a map isn't real, but just a representation so this proof is pushing the system of this math(s) system

svachalek 5y ago
The deeper physics goes, the more apparent it is that our perception of reality is a good model for what is happening at our scale in the universe and the forces that are dominant at that scale. Our intuition breaks down at larger and smaller scales, but the math still works. So in some sense, math is the truest access we have to reality.

kibwen 5y ago

> Woodin named the axiom (*), pronounced “star,” because it was “like a bright source — a source of structure, a source of light,” he told me. There are only two hard problems in mathematics: infinity and naming things.

phkahler 5y ago

You can map all the real numbers to the interval 0 <= x < 1. To map one of those reals to an integer, simply write it's trailing digits in reverse order on the left side of the decimal point. You may then drop any leading zeros. 0.0 => 0 0.1 => 1 0.2 => 2 ... 0.14159 => 95141 The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? Can there be an "infinitely large integer?" or are there just infinitely many of them? I think this question gets to the core of the problem.

question000 5y ago
"Can there be an infinitely large integer" No there can't there's always a larger integer. Anyone who claims otherwise is just making stuff up. It's just mind blowing to me that anyone think otherwise, it's like asking what the final digit of pi is, you'd get laughed out of any college class for insisting there might be one, rightly so.
victorbojica 5y ago
But if you assign them randomly, then it should work 1->5.85916 2->8.7599 ... Or even randomize the order for the integers 5->7.52256951 77->848.455 ...
- bonzini 5y ago
  You can't, this is Cantor's diagonal counterexample.
gowld 5y ago
> Can there be an "infinitely large integer?" What could that even mean? Aren't integers all defined as Succ^n(x) for a finite n and a base x?
red_trumpet 5y ago
> You can map all the real numbers to the interval 0 <= x < 1. Even easier use a well-established function such as arctan to map the reals bijectively to the interval -π/2 < x < π/2, and then scale and shift the interval to 0 < x < 1.

daxfohl 5y ago

A related thing that occurred to me the other day: there's some number in [0, 1] that encodes every state of every possible Turing machine (the number of Turing machines is countable, the duration of its run is countable, and the states at each step are countable, so you can diagonalize that and make a real number out of it). I'm pretty sure you can take that further and show that all possible mathematical proofs, including the Godel unsolvable ones (I think...they're just proofs that are infinitely long but countably so), can also be encoded in a single real number. That makes it feel like the reals are pretty big.

Rinum 5y ago
I think you'll like this - https://youtu.be/HeQX2HjkcNo https://youtu.be/HeQX2HjkcNo
ttctciyf 5y ago
This sounds a little like Chaitin's constant Omega (Ω), which is very roughly a number in [0, 1] which is the probability that a randomly chosen program (for a universal Turing machine, U) will halt. This has the interesting property that knowing the first n bits of Ω allows you to determine whether any program (for U) of length up to n will halt, in other words you could solve the halting problem for programs of length up to n. As Wikipedia puts it: > Because many outstanding problems in number theory, such as Goldbach's conjecture, are equivalent to solving the halting problem for special programs (which would basically search for counter-examples and halt if one is found), knowing enough bits of Chaitin's constant would also imply knowing the answer to these problems. But as the halting problem is not generally solvable, and therefore calculating any but the first few bits of Chaitin's constant is not possible, this just reduces hard problems to impossible ones, much like trying to build an oracle machine for the halting problem would be. - https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant

sharpener 5y ago

The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0] Being charitable one might argue that the meanings of terminology had been lost in translation over time and that perhaps Cantor was trying to create non-standard analysis, but then the diagonal argument seems to represent nothing more than the truism that finite numbers are smaller than transfinite ones. Hence I worry about people who are still worrying about this issue, and I worry for the future of science and AI in particular if folks can't get clear of it. [0] https://www.researchgate.net/publication/328568169_The_Case_Against_Cantor's_Diagonal_Argument https://www.researchgate.net/publication/328568169_The_Case_... Yes, I'm that guy who wrote that.

myWindoonn 5y ago
Hi, Lawvere pummelled your position into the ground a while ago: http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf Your critique involves repeatedly crossing the boundary between the inside and outside of the system in question; Lawvere works entirely inside the system, and shows that the paradoxes of self-reference arise from our interpretations. https://arxiv.org/abs/math/0305282v1 https://arxiv.org/abs/math/0305282v1 explains with many examples. Hi downvoters: Use your words when somebody is wrong. Your downvotes aren't helpful here for finding the truth.
- sharpener 5y ago
  I'm not seeing this yet. Perhaps you could explain it to me in plain terms.
  - myWindoonn 5y ago
    Pick any Cartesian closed category. Says Lawvere: If there exists t : Y -> Y such that t;y != y for all y : 1 -> Y then for no A does there exist a surjection A -> (A -> Y). (He actually says something much stronger.) Note that the first half of this is saying "if there exists t such that t has no fixed points..." Let our category be Set, the category of sets and functions; it is well-known to be Cartesian closed. Let A be the set of natural numbers and let Y be the Booleans. Then Lawvere is saying that there is no surjection N -> (N -> 2), and thus definitely no bijection, because there is a function 2 -> 2 with no fixed points: the negation function which swaps true and false has no fixed point. It does not get much plainer without actually reading Lawvere and/or Yanofsky directly, sorry. I hope that this helps explain how inescapable this sort of theorem is.

Decker87 5y ago

Honest question, what is the usefulness of proving such an obvious thing?

joe_the_user 5y ago

For 50 years, mathematicians have believed that the total number of real numbers is unknowable. It's an established result that the Continuum Hypothesis is independent of Zermelo–Fraenkel axioms of set theory. No proof is going change that. So whatever has been proved here doesn't change that. It will take a second to get the reference but Raymond Smullyan says essentially that "we're not looking for a proof or disproof of CH, we're looking for an assumption that can be shown to be natural enough that we can take it as an axiom". Just sayin' since the (subheading) writer seems to be playing fast and loose with the concepts involved. Edit: article goes on to give rigorous explanation but still starting "no one knew" confuses what's going on.

ncmncm 5y ago

> How many real numbers exist? You might be tempted to say "lots". And you would be right, as far as that goes. But that doesn't satisfy a real mathematician. The question that immediately arises is whether "lots" is "enough". And that leads the better sort of mathematician inevitably to: "enough for what?" That is what mathematicians are deep in the middle of exploring, now. For example, when you are asked, "Does this skirt make my butt look too big?", you obviously must not say "yes", but you just as obviously cannot, with an entirely clear conscience, say "no", either. But for anyone with an intact survival instinct, the counter-question, "too big for what?" should spring immediately to mind. And it's a good one, but it depends intimately on the true size of the set of real numbers. So, this is not an idle pursuit.

90minuteAPI 5y ago
Answering “Does this skirt make my butt look too big?” with something that “depends intimately on the true size of the set of real numbers” seems to be among the worst strategies.
- ncmncm 5y ago
  The mathematics of infinities are nothing if not counterintuitive.
rkagerer 5y ago
"Does this skirt make my butt look too big?" "Too big for what?" Yeah let me know how that works out.
- philipswood 5y ago
  Yes, the call for more experimentation to keep theorists honest.
whoaisme 5y ago
Ken M is that you?

01GOD 5y ago

I suspect the op was trolling the hackernews community to intentionally cause a big mathsturbatory circlejerk. Golf clap on how amazingly effective that was.

zeven7 5y ago

What online class should I take to learn more about this topic in particular?

chasing 5y ago

There are exactly 1,837 real numbers and anyone who tells you any different is just trying to sell you something.

js8 5y ago

I have a question, so assuming that we adopt the axiom(s) that cause real numbers to be cardinality Aleph_2 and not Aleph_1, is then there some intuitive explanation how does the set of size Aleph_1 looks like, and what it could be used for?

tromp 5y ago

The explanation of Cohen's filter for making new reals reminds me of surreal numbers {L | R} but in this case every real is in either L or R. Still, I fail to see how that gives you more than restricting L and R to contain only rational numbers...

kkylin 5y ago

Those with a bit more math background may enjoy Cohen's own perspective on the discovery of forcing: https://projecteuclid.org/journals/rocky-mountain-journal-of-mathematics/volume-32/issue-4/The-Discovery-of-Forcing/10.1216/rmjm/1181070010.full https://projecteuclid.org/journals/rocky-mountain-journal-of... (Not technical as these things go, but helps to have a little knowledge of logic / set theory and some amount of "mathematical maturity.")

ProfHewitt 5y ago

The results in the article are based on 1st-order logic, which is inadequate for the foundations of mathematics. Mathematical abstractions need to be characterized up a unique isomorphism as in the theory Ordinals described in the following article: "Theory Ordinals can Replace ZFC in Computer Science" https://papers.ssrn.com/abstract=3457802 Mathematical questions can be properly addressed only by using adequate foundations.

ProfHewitt 5y ago
PS. There are no ordinals of intermediate cardinality between ω0 and ω1.

devit 5y ago

In addition to adding the continuum axiom or its negation, there's also the approach of restricting oneself to computable sets and thus only having countable infinities.

renanbg 5y ago

I find this very much fascinating, although I can't understand it. I hope I can, eventually, fully appreciate "higher math" questioning like this one, and would be really grateful if someone could point me what to study, as an "amateur mathematician" with only background on engineering calculus.

pachico 5y ago

I thought this was already solved decades ago by Mr. Show: https://m.youtube.com/watch?v=RkP_OGDCLY0 https://m.youtube.com/watch?v=RkP_OGDCLY0 Sorry, I couldn't resist.

ruggeri 5y ago

I should finish reading the linked article. But I have a quick initial question. Proofs in ZFC can be enumerated by a machine. In theory, we could devise a machine that (1) will certainly eventually halt iff ZFC is inconsistent (proves two contradictory statements), or (2) will never halt iff ZFC is consistent. (Caveats: naturally, if ZFC is consistent, we'll never learn whether we should just keep waiting for the machine to find a contradiction. And our machine will require unbounded storage space.) Can we build a corresponding device that would have different behaviors depending on whether the continuum hypothesis is "true" (whatever that means)? I suppose the computational model would be Turing machine as above.