Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

quantamagazine.org

Post reply on HN
Print view View original

321–330 of 359 posts

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

#321

Post by ummonk »

dwohnitmok wrote: post #121

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 a…

Yeah, I tend to lean towards the side of realism (and constructivism), explicitly for the reasons exemplified by your rock / bottle analogy downthread.

But even from that perspective, I found the article's discussion of "true" / "false" rather weird, since it seemed to be taking certain positions (namely regarding the continuum hypothesis) for granted even though those positions don't seem to be grounded in any material fact.

It's as if people are conjuring up imaginary fictional entities and then asserting certain attributes about those entities as obvious and objective.

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

#322

Post by ummonk »

rpearl wrote: post #235
TameAntelope wrote: post #227

Earlier quoted context omitted.

> sophomore level Real Analysis Hmm?

We did this first semester freshman year at my school in a single lecture in a 100 level "concepts of mathematics" course. I get that there's a certain amount of "it's hard to wrap your head around infinity" but really this proof is pretty well trodden by students not far into learning mathematics.

I was homeschooled, so I was shown this in middle school hah. I think math camps and the like also tend to teach it before college.

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

#323

Post by ummonk »

pdonis wrote: post #204
btilly wrote: post #193

Earlier quoted context omitted.

The problem is that exists comes to mean something technical that doesn't match common usage. Let's take my favorite example. In graph theory, a minor of a graph is a graph you can get by removing vertices, removing edges, or by replacing an edge-vertex-edge triple with a single edge. Many categories of graphs are closed under the act of taking minors. For example planar graphs, graphs you can draw on the plane with…

These concerns don't apply to the claim that the set of real numbers is uncountable. Cantor's diagonal proof is constructive: given any countable set of real numbers, it tells you how to construct a real number that is not in the set. That is sufficient to show that the set of real numbers cannot be countable. Also, even though many real numbers cannot be written down with a finite set of symbols, Cantor's diagonal p…

You're assuming you've been able to construct all those real numbers in the first place, using arbitrary imaginary cauchy sequences (i.e. cauchy sequences that cannot be constructed but rather rely on some magic axiom of infinite choice).

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

#324

Post by [deleted] »

ummonk wrote: post #313
rssoconnor wrote: post #222

Earlier quoted context omitted.

ZFC+¬Con(ZFC) either wrongly proves that the machine that searches for an inconsistency in ZFC halts, or it wrongly proves that `while(true)` halts. Either way ZFC+¬Con(ZFC) is wrong about something.

Why is it wrong to say that the machine halts?

[deleted]

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

#325

Post by rssoconnor »

ummonk wrote: post #313
rssoconnor wrote: post #222

Earlier quoted context omitted.

ZFC+¬Con(ZFC) either wrongly proves that the machine that searches for an inconsistency in ZFC halts, or it wrongly proves that `while(true)` halts. Either way ZFC+¬Con(ZFC) is wrong about something.

Why is it wrong to say that the machine halts?

ZFC+¬Con(ZFC) definitely proves that the machine that searches for an inconsistency in ZFC halts. That is a direct consequnce of ¬Con(ZFC). Keep in mind that by "proves" I'm only saying that there exists a logical deduction from the axioms. I'm not saying that it is true or false. Remember that logical deductions are "truth preserving", but we can only conclude that the conclusions are true if the axioms at the start are all true.

So again, we have a proof in some sketchy axiom system that the machine that searches for an inconsistency in ZFC halts. The question is whether that conclusion is a true statement or not, whether that machine actually does or does not halt. You can start up that program on your laptop while we consider it. Maybe it will halt during our discussion. I also want to point out that whether that conclusion is a true statement or not has no bearing on whether the deduction system was sound to begin with. Unsound systems can prove true statement, simply by accident rather than by design.

Case (1) that machine doesn't really halt, then ZFC+¬Con(ZFC) proves an untrue statement, and we thus the system is unsound.

Case (2) that machine does really halt. Then this particular conclusion wasn't untrue, but we have another problem. We can take the output of that machine, decode it, and we have a proof of an inconsistency in ZFC. Again this is just a deduction, it doesn't mean that math is wrong or the world ends. Just that the ZFC axiom system is so unsound that it is inconsistent, and it has some untrue axioms. Nevertheless we can use such a proof and derive a proof that ZFC prove `while(true)` halts, and in turn transform that into a proof in ZFC+¬Con(ZFC) that `while(true)` halts. And it is definitely the case that `while(true)` doesn't halt. So in this case we have found a different but still untrue statement that ZFC+¬Con(ZFC) proves. Our conclusion is the same: ZFC+¬Con(ZFC) is unsound.

So in either case `ZFC+¬Con(ZFC)` proves some machine halts that doesn't. I haven't concluded which of the two machines it is wrong about though I have my personal suspicions, but it is definitely wrong about one of them.

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

#326

Post by ummonk »

chmod775 wrote: post #135
btilly wrote: post #88

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…

> there are only a countable number of real numbers Then you should be able to come up with a function that assigns a natural number uniquely to each real number. Of course if you tried that I could immediately name you a real number, or a pair of them, for which your rule doesn't work.

"Then you should be able to come up with a function that assigns a natural number uniquely to each real number. Of course if you tried that I could immediately name you a real number, or a pair of them, for which your rule doesn't work"

I can give you a function that will never output the same natural number on any two real numbers unless those two real numbers are equal.

My function outputs the binary value of the Unicode encoding of the description of the number that you provide.

Go ahead, name me a pair of real numbers for which my rule doesn't work.

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

#327

Post by ummonk »

pdonis wrote: post #205
skoodge wrote: post #157

Earlier quoted context omitted.

That depends on what you mean by "assigns uniquely", "rule" and "doesn't work", which is why this question is deeply entangled with philosophical issues that cannot be settled purely mathematically. It is obvious that all expressions in the English language can be ordered from smallest to largest and lexicographically, which makes these expressions trivially countable. We can thus assign natural numbers to real numbe…

> We can thus assign natural numbers to real numbers by assigning numbers to their expressions in a natural or formal language This doesn't work because not all real numbers have expressions in a natural or formal language. This is easily shown by an obvious variation on Cantor's diagonal proof, applied to your lexicographically ordered list of expressions in any natural or formal language.

If you're claiming the existence of entities that you are unable to identify or express, you're veering into religion and faith.

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

#328

Post by rssoconnor »

ummonk wrote: post #316
rssoconnor wrote: post #102

Earlier quoted context omitted.

Mostly because it implies that some Turing machines halt that actually do not halt. That is unless you are willing to accept that a Turing machine can halt in some number of steps that is beyond any number that can be written. And I don't mean can't be written in the sense that we don't have enough paper. Just cannot be written in principle at all by our notation for numbers.

Why is that wrong? If you actually ran a Turing machine for a number of steps that is beyond any number that can be written, maybe it would halt.

By number that cannot be written, I don't mean cannot be written due to lack of paper; I mean a value that there is no notation for.

You cannot run a machine for "that many" steps because such a value is unreachable by steps. Non-standard models have a set of values that begin with a copy of the actual natural numbers, followed by some ordered set of copies of the integers in the sense that any values "beyond" the initial natural numbers have an infinite number of successors and an infinite number of predecessors, like integers do. By counting in steps it is not possible to move from a value in the initial natural number fragment to one of these non-standard values, because there are an infinite number of values in between them that you would be required to step through.

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

#329

Post by rssoconnor »

Someone wrote: post #199
rssoconnor wrote: post #65

Earlier quoted context omitted.

> 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. Minor quible: Just because a potential axiom is independent of ZF(C) doesn't make it necessarily "okay" to add. Potential axioms can be unsound, for example if they prove new / untrue Sigma_1 statements. As an example, even in the likely circumstance that ¬Con(ZFC) is independent…

> because it asserts the existence of natural numbers that have no "written form" I don’t see why that should imply it wouldn't be "okay" to add ¬Con(ZFC). It may be highly counterintuitive, but the history of mathematics is full of counterintuitive results that nowadays are accepted as true in mainstream mathematics. Well-known examples are the existence of irrational numbers, the claim that the set of natural numbe…

ZFC+¬Con(ZFC) proves "ZFC+¬Con(ZFC) is inconsistent".

So if were the case that ZFC+¬Con(ZFC) was sound then what it proves would be true, and "ZFC+¬Con(ZFC) is inconsistent" would be true. But that would mean ZFC+¬Con(ZFC) is actually inconsistent, and thus ZFC+¬Con(ZFC) would actually be unsound after all.

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

#330

Post by rpearl »

TameAntelope wrote: post #236
rpearl wrote: post #235

Earlier quoted context omitted.

We did this first semester freshman year at my school in a single lecture in a 100 level "concepts of mathematics" course. I get that there's a certain amount of "it's hard to wrap your head around infinity" but really this proof is pretty well trodden by students not far into learning mathematics.

Which school?

Carnegie Mellon
Post reply on HN