How many real numbers exist? New proof moves closer to an answer • Hacker News Board

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

#351

Post by btilly » Mon, Jul 19, 2021, 3:35 PM UTC

chmod775 wrote: post #342

ummonk wrote: post #326

Earlier quoted context omitted.

"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 U…

The thread already went down that line of argument, you can take this comment as an response to yours: https://news.ycombinator.com/item?id=27851171

And, as I pointed out there, that comment remains wrong.

See https://news.ycombinator.com/item?id=27859355 for why.

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

#352

Post by ummonk » Mon, Jul 19, 2021, 10:35 PM UTC

chmod775 wrote: post #347

ummonk wrote: post #346

Earlier quoted context omitted.

First of all, Pi is not an example of such a number, since it can be defined constructively without requiring physical measurements. Second, even your proposed mechanism of picking out points would be capable of identification (albeit not computation) in a Turing-complete language. Quite simply, to be able to pick out two points you'd need to create some kind of stable structure that identifies those two points - thi…

> First of all, Pi is not an example of such a number It is in its canonical form (i.e. as a numbers, not something that represents it), which is what I said. > Quite simply, to be able to pick out two points you'd need to create some kind of stable structure that identifies those two points. No I don't. I could pick two atoms floating through space somewhere and say "This distance, right now." I could also say: "The…

> It is in its canonical form (i.e. as a numbers, not something that represents it), which is what I said.

This isn't a coherent sentence. A real number is a cauchy sequence of rational numbers. There is no one canonical sequence that defines Pi.

> No I don't. I could pick two atoms floating through space somewhere and say "This distance, right now." > I could also say: "The distance traveled by this particle in a second."

That process of picking out and localizing the atoms (which are not localized to specific points) would entail performing a measurement with a macroscopic apparatus. At that point, the configuration of the apparatus can be encoded.

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

#353

Post by ruggeri » Tue, Jul 20, 2021, 12:45 AM UTC

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.

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

#354

Post by alanbernstein » Tue, Jul 20, 2021, 4:40 AM UTC

DangitBobby wrote: post #344

plus wrote: post #302

Earlier quoted context omitted.

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.

Again, you don't know how to compute the function which creates the mapping, so you don't know the results, so you don't know how to sort the results. I don't follow the logic which claims your inability to compute something is now an intrinsic property to the resulting set. I do understand that sortability is a property intrinsic to integers.

I think the point is that the example with irrational numbers guarantees that this mapping/sort can't be done.

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

#355

Post by ProfHewitt » Tue, Jul 20, 2021, 3:34 PM UTC

pavpanchekha wrote: post #4

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

Note that forcing and the independence results are only for 1st-order logic.

They do not work for theories that characterize mathematical

abstractions such as the Ordinals and Natural Numbers up to a

unique isomorphism.

See the following video:

https://www.youtube.com/watch?v=AJP1VL7shiI

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

#356

Post by rssoconnor » Tue, Jul 20, 2021, 5:11 PM UTC

a1369209993 wrote: post #348

rssoconnor wrote: post #325

Earlier quoted context omitted.

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…

> if the axioms at the start are all true. Axioms are true by definition; that's what "axiom" means. (They might also be false, but (if and) only if your system is inconsistent.) > Case (1) that machine doesn't really halt This is not a state of affairs: all you know at any given time is that the machine hasn't halted yet (after some specific finite number of steps), or that it has aquired some termination-precluding…

Axioms are most certainly not true by definition.

Regardless, the particular technical definition of truth I'm using is Tarski's definition of truth[1]. We don't have to agree whether Tarski's definition is "correct", and I'm happy to qualify my use of the word "truth" here, but I'm referring to a specific technical definition here.

[1] https://en.wikipedia.org/wiki/Semantic_theory_of_truth#Tarsk...

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

#357

Post by logicchains » Sat, Jul 24, 2021, 4:17 AM UTC

kmill wrote: post #245

logicchains wrote: post #241

Earlier quoted context omitted.

>The ultrafilter construction gives one such model. It's worth noting that this construction relies on the axiom of choice, so exists in ZFC but not ZF. Generally a lot of counter-intuitive constructions disappear when eliminating the axiom of choice (such as the Banach–Tarski paradox and non-continuous functions).

> non-continuous functions I think the step function doesn't depend on choice. Say f(x) = 0 if x = 0. Also, suppose we define the reals through Dedekind cuts. We can define f(x) by checking whether 0 is an element of x as a cut. We can prove f is discontinuous in the usual way. What I had heard is that Brouwer proved, using some kind of constructive/intuitionistic logic, that every function is continuous, but ZF is s…

>suppose we define the reals through Dedekind cuts

You can't define the classical reals this way in a constructive setting, only the computable reals.

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

#358

Post by kmill » Sat, Jul 24, 2021, 5:56 PM UTC

logicchains wrote: post #357

kmill wrote: post #245

Earlier quoted context omitted.

> non-continuous functions I think the step function doesn't depend on choice. Say f(x) = 0 if x = 0. Also, suppose we define the reals through Dedekind cuts. We can define f(x) by checking whether 0 is an element of x as a cut. We can prove f is discontinuous in the usual way. What I had heard is that Brouwer proved, using some kind of constructive/intuitionistic logic, that every function is continuous, but ZF is s…

>suppose we define the reals through Dedekind cuts You can't define the classical reals this way in a constructive setting, only the computable reals.

Ok, but I'm not sure what your point is. Throwing out only the axiom of choice (which is the difference between ZFC and ZF) does not make things constructive. If you're thinking of Diaconescu's theorem, it's that choice implies the law of the excluded middle, but the converse is certainly not true.

I was objecting to this:

> Generally a lot of counter-intuitive constructions disappear when eliminating the axiom of choice (such as [...] non-continuous functions).

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

#359

Post by kmill » Sun, Jul 25, 2021, 7:44 PM UTC

Tainnor wrote: post #349

kmill wrote: post #91

Earlier quoted context omitted.

This surprisingly doesn't mean repeatedly adding 1 will exhaust all natural numbers -- there are models for the natural numbers with elements that can't be reached this way! The ultrafilter construction gives one such model. You take the set of all sequences of natural numbers (n1, n2, n3, ...) then use an ultrafilter to decide which of these sequences are considered to be equal. The usual operations of natural numbe…

> This surprisingly doesn't mean repeatedly adding 1 will exhaust all natural numbers -- there are models for the natural numbers with elements that can't be reached this way! Isn't that just true for models of a first-order axiomatisation of the natural numbers? As far as I know, if you write down the Peano axioms in second order logic (as is required), you do get the natural numbers uniquely, and applying the succe…

Yeah, my understanding is that second-order arithmetic picks out the usual natural numbers, but it is a much stronger system since you can additionally quantify over subsets of naturals in your formulas.

The context of the comment is ZFC and its concept of the natural numbers (and what I had in mind in particular was what is its minimal infinite inductive set?). ZFC is a first-order theory, so "model" means model of a first-order theory.

> The reason why you get non-standard models of arithmetic in first-order logic is the Löwenheim-Skolem theorem

The ultrafilter construction I described is a way around the compactness theorem, in that it constructs new models semantically rather than syntactically. Ultrafilters are also a good way to prove the compactness theorem. But in any case, it's essentially the first half of the upwards Löwenheim-Skolem theorem before applying the downwards Löwenheim-Skolem theorem -- I think the significance of that theorem is that you can get models of any infinite cardinality you want, rather than just a strictly larger one. (Though I'm no logician.)