Hacker News Re-Imagined

How Many Numbers Exist? Infinity Proof Moves Math Closer to an Answer

  • 501 points
  • 24 days ago

  • @theafh
  • Created a post

How Many Numbers Exist? Infinity Proof Moves Math Closer to an Answer


@daxfohl 24 days

Replying to @theafh 🎙

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.

Reply


@bmitc 24 days

Replying to @theafh 🎙

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.

Reply


@jaywalk 24 days

Replying to @theafh 🎙

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

Reply


@morpheos137 24 days

Replying to @theafh 🎙

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.

Reply


@Decker87 24 days

Replying to @theafh 🎙

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

Reply


@ruggeri 20 days

Replying to @theafh 🎙

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.

Reply


@question000 24 days

Replying to @theafh 🎙

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

Reply


@kibwen 24 days

Replying to @theafh 🎙

> 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.

Reply


@ProfHewitt 23 days

Replying to @theafh 🎙

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.

Reply


@pachico 22 days

Replying to @theafh 🎙

I thought this was already solved decades ago by Mr. Show:

https://m.youtube.com/watch?v=RkP_OGDCLY0

Sorry, I couldn't resist.

Reply


@sharpener 24 days

Replying to @theafh 🎙

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_...

Yes, I'm that guy who wrote that.

Reply


@renanbg 22 days

Replying to @theafh 🎙

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.

Reply


@xvilka 24 days

Replying to @theafh 🎙

There is a good video about that on Numberfile[1]

[1] https://www.youtube.com/watch?v=5TkIe60y2GI

Reply


@joe_the_user 24 days

Replying to @theafh 🎙

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.

Reply


@js8 24 days

Replying to @theafh 🎙

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?

Reply


@tromp 24 days

Replying to @theafh 🎙

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...

Reply


@mmmBacon 24 days

Replying to @theafh 🎙

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.

Reply


@jostmey 24 days

Replying to @theafh 🎙

> "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.

Reply


@devit 23 days

Replying to @theafh 🎙

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.

Reply


@ncmncm 24 days

Replying to @theafh 🎙

> 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.

Reply


@dexwiz 24 days

Replying to @theafh 🎙

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.

Reply


@arduinomancer 24 days

Replying to @theafh 🎙

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?

Reply


@chasing 24 days

Replying to @theafh 🎙

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

Reply


@privatdozent 24 days

Replying to @theafh 🎙

Another great piece from Quanta. Such an important institution

Reply


@btilly 24 days

Replying to @theafh 🎙

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.

Reply


@pavpanchekha 24 days

Replying to @theafh 🎙

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 [2] https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf

Reply


@dwohnitmok 24 days

Replying to @theafh 🎙

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.

Reply


@kkylin 23 days

Replying to @theafh 🎙

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...

(Not technical as these things go, but helps to have a little knowledge of logic / set theory and some amount of "mathematical maturity.")

Reply


@zeven7 24 days

Replying to @theafh 🎙

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

Reply


@phkahler 24 days

Replying to @theafh 🎙

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.

Reply


@pelorat 24 days

Replying to @theafh 🎙

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

Reply


@123pie123 24 days

Replying to @theafh 🎙

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

Reply


@01GOD 24 days

Replying to @theafh 🎙

I suspect the op was trolling the hackernews community to intentionally cause a big mathsturbatory circlejerk.

Golf clap on how amazingly effective that was.

Reply


@MiddleEndian 24 days

Replying to @theafh 🎙



About Us

site design / logo © 2021 Box Piper