Live data from Hacker News

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

quantamagazine.org

301–310 of 359 posts

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

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

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

#302

Earlier quoted context omitted.

Because the integers are ordered?

I took well-defined to mean "if it exists, we know what it is." So really I guess what I want to know is why it matters that we can't actually calculate the mapping.

Any finite number of randomly chosen integers can be sorted in increasing order. The quantities invented for the proposed mapping do not share this property, and thus cannot possibly be integers.

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

#303

Earlier quoted context omitted.

They exist in that it is easy to prove "for ALL x there EXISTS y such that (there EXISTS a Turing machine with at most x states M such that (there EXISTS some n such that M prints y 1's and halts after n steps) AND (for ALL Turing machines with at most x states M, if (there EXISTS some n such that M halts after n steps) then (M prints no more than y 1's after n steps))". I expect you can prove this in systems as weak…

> It is true though that various (decidable) proof systems are unable to prove that the Busy Beaver function has any specific value beyond a certain point. Isn't the result stronger than that though? The value of BB(30) might be X. Or it might be Y. Neither value would cause any problems. Thus, "the value" doesn't exist. There is no value that is the value of BB(30).

Yes, what you are saying is indeed the case in the sense that if BB(30)=n for some particular numeral n is independent of whatever proof system we are focusing on, for the sake of argument let's say ZFC, (though 30 feels a a bit on the low side for ZFC), then we can consistently add BB(30)=n or BB(30)≠n as axioms to the system, the same way to can for any other independent statement. And there will be arbitrary large values of n that are independent, so we could add BB(30)=n or we could add BB(30)=m or so forth for any numerals i so long as BB(30)=i is independent of ZFC (or whatever axiom system we are considering).

But! that does not mean that all these systems are sound, for if you add the incorrect value as an axiom, specifically if you add anything but the smallest value 'm' such that BB(30)=m is independent of ZFC, then you are in a similar situation to adding ¬Con(ZFC) whereby you only have non-standard models.

They way this works is that, suppose BB(30)=m for some particular m is independent of ZFC, but BB(30) is not actually equal to m. What we will find is that there is some Turing machine M and some non-standard natural number q such that, while M doesn't actually halt in reality, according to some non-standard model it does halt in 'q' number of steps, and, in this model, when it does halt, it leaves 'm' 1's on the output tape.

That said, your comment did push me towards the limits of my comfort zone, so it might be helpful to double check what I'm saying. I don't see how it could be any other way though.

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

#304
post #285

Earlier quoted context omitted.

Yes they are independent of ZFC but they still exist. From the original article talking about CH which is also independent: > This independence is sometimes interpreted to mean that these questions have no answer, but most set theorists see that as a profound misconception. They believe the continuum has a precise size; we just need new tools of logic to figure out what that is. These tools will come in the form of n…

> but we still cannot ever know them because they are incomputable (??) That doesn't mean you can't know them. We know BB(2). It means there is no single algorithm which is capable of yielding them all. But there could, theoretically, be an algorithm for BB(10), a different algorithm for BB(11), etc. In fact, those individualized algorithms don't exist either.

Yes I was referring to calculating BB(n) for arbitrary n. But certainly these numbers exist even if they’re independent of ZFC (?)

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

#305
post #72

Earlier quoted context omitted.

> he resulting system is unsound (in the sense of Tarski) because it asserts the existence of natural numbers that have no "written form" (i.e. the existance of natural numbers that are larger than any term you can write to denote a natural number). Isn't that basically the definition of the natural numbers, ie. if you write down any natural number (say n) I can always construct a natural number that is larger than i…

I don’t believe a consequence of the axioms discussed is that there exist natural numbers with no “written form.” Do you have a proof or citation?

For this entire argument I will be operating under the assumption that ¬Con(ZFC) is independent of ZFC.

ZFC+¬Con(ZFC) proves "there EXISTS a natural number x such that x is an encoding of a proof in ZFC of 0=1".

Now suppose there is actually a numeral n, i.e. a specific written term written using symbols, e.g. (+,*,1), such that ZFC+¬Con(ZFC) proves that "n is an encoding of a proof in ZFC of 0=1". We can mechanically decode such a n and check if it is indeed a proof that that ZFC proves "0=1" or not.

There are two possibilities: (a) the check is successful and thus we have found proof of a contradiction in ZFC. But if ZFC is inconsistent, then it proves everything. In particular ZFC proves ¬Con(ZFC), which violates our assumption that ¬Con(ZFC) is independent of ZFC.

Alternatively (b) our check fails and n does not encode a proof in ZFC of 0=1. But that statement "n does not encode a proof in ZFC of 0=1" is a true Delta_0 statement, and we can prove by induction that ZFC proves every true Delta_0 statement. Thus we can prove that ZFC proves "n does not encode a proof 0=1", and hence ZFC+¬Con(ZFC) proves "n does not encode a proof 0=1". But now we have found a statement Q such that ZFC+¬Con(ZFC) proves both Q and also ¬Q. This means that ZFC+¬Con(ZFC) is inconsistent. But if ZFC+¬Con(ZFC) is inconsistent, by the deduction theorem, ZFC proves ¬¬Con(ZFC), or equivalently ZFC proves Con(ZFC). This contradicts our assumption that ¬Con(ZFC) is independent of ZFC (it also implies that ZFC is inconsistent).

Thus we are left with the conclusion that there is no such numeral n. However it is still the case that ZFC+¬Con(ZFC) proves "there EXISTS a natural number x such that x is an encoding of a proof in ZFC of 0=1", and the only way this can be the case is any such x is a "natural number" which has no numeral that denotes it.

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

#306

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

PS. There are no ordinals of intermediate cardinality between ω0 and ω1.

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

#307
post #203
post #118

Earlier quoted context omitted.

Yes, there are multiple constructivist approaches possible. However since my objection to classical approaches is that I want "X exists" to be meaningful, I like mathematical objects that can be written down with a finite number of symbols in a finite space. Which means that I'm only interested in a countable universe of possible mathematical things. If you say "exists" about anything else, I'll understand you - I do…

> I like mathematical objects that can be written down with a finite number of symbols in a finite space. Which is fine, but I don't think it justifies the claim that there are only countably many real numbers. The only claim it justifies is that there are only a finite (not even countable, since "countable" implies infinitely many) set of numbers that you find useful.

Every integer can be written down with a finite number of symbols....right?

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

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

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

#310
post #72

Earlier quoted context omitted.

> he resulting system is unsound (in the sense of Tarski) because it asserts the existence of natural numbers that have no "written form" (i.e. the existance of natural numbers that are larger than any term you can write to denote a natural number). Isn't that basically the definition of the natural numbers, ie. if you write down any natural number (say n) I can always construct a natural number that is larger than i…

Dropping down to Peano Arithmetic for a moment. We can consider adding a new constant 'c' for a natural number to the language along with the following infinite list of axioms about this remarkable constant: - 0 - 1 - 2 - 3 ... Adding all these axioms is consistent. I.e. you can do induction upto 'c', whatever it is. Why is it consistent? Because if there was a contradiction, the proof of such a contradiction would b…

This sounds a little bit like an argument against systems with an infinite number of axioms to me. Or maybe it's fine but only under certain conditions?
Post reply on HN