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

#311

Post by rssoconnor » Sat, Jul 17, 2021, 6:32 PM UTC

thaumasiotes wrote: post #289

rssoconnor wrote: post #263

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

To elaborate a little further on why BB(30) does have a true value.

If BB(30) truly equals some particular numeral m, then there actually does exist a Turing machine M that has no more than 30 states and does halt with m 1's on its tape. Not only does this machine really exist, but the fact that it halts in this state is true Delta_0 statement, and thus it is trivially provable, you don't even need induction. It is provable in Robinson Arithmetic, it is provable in Peano Arithmetic, and it is provable in ZFC. Thus we have that RA proves "BB(30) ≥ m" and PA proves "BB(30) ≥ m" and ZFC proves "BB(30) ≥ m", etc.

By transitivity each of these systems also proves "BB(30) ≥ m₀" for every numeral m₀ less than m. But if m₁ is a numeral larger than m, it is no longer the case that RA proves "BB(30) ≥ m₁" and PA doesn't prove "BB(30) ≥ m₁" and (assuming ZFC is sound) ZFC doesn't prove "BB(30) ≥ m₁"

Thus we "can tell" what the true value of BB(30) is because it is the greatest value in which RA (or PA or (presumably) ZFC) proves "BB(30) ≥ m" for the numeral m denoting that value. Equivalently the value of BB(30) is the least value m for which RA, PA, or any other sound system, does not prove "BB(30) ≠ m".

We "can tell" this value even if we might not be able prove it in PA, or ZFC, or "ZFC + there exists a Mahlo cardinal". Indeed each different proof system likely can extend the range of BB values that are provable.

If you add an axiom "BB(30) = m" for some particular numeral m as an axiom to ZFC and it is the wrong value of m, you will either get an inconsistent system if "m" is too small, or you will get an unsound system if "m" is too large. In case "m" is to large, the unsound system will wrongly prove that certain Turing machines halt that do not actually halt. Specifically it will falsely prove that the Turing machine that searches for (a Turing machine with no more than 30 states that halts with "m" 1's on it tape) will halt, when such a machine does not actually halt.

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

#312

Post by ummonk » Sat, Jul 17, 2021, 6:47 PM UTC

rssoconnor wrote: post #65

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…

> 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 mean, mainstream axiomatic systems assert the existence of real numbers that have no written form (after all, only countably many entities can have a written form), so how is this any different?

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

#313

Post by ummonk » Sat, Jul 17, 2021, 6:48 PM UTC

rssoconnor wrote: post #222

a1369209993 wrote: post #220

Earlier quoted context omitted.

> such a system proves that various particular Turing machines halt when, [ ]in fact[ ], those machines do not halt. Er, no. The fact is that there is no fact of the matter as to whether those particular Turing machines either a: do not halt at all, or b: halt after a (colloquially) infinite number of steps. (A implication of there being no fact of the matter is that, empirically, we can't tell the difference by runn…

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?

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

#314

Post by ummonk » Sat, Jul 17, 2021, 6:54 PM UTC

pavpanchekha wrote: post #152

lupire wrote: post #90

Earlier quoted context omitted.

why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.

I wonder what you mean by "what's wrong with an unwritable natural"... It is sound to assume one! And it doesn't make any true mathematical facts false. But of course it's sound to assume many silly things. But why assume those things? The reality is that mathematicians didn't first come up with the Peano axioms and then study the interesting consequences of them. Both as a matter of history and also as a matter of w…

"But of course it's sound to assume many silly things. But why assume those things?"

This goes to the parent comment's point about real numbers though. It's silly to assume unwritable real numbers. Why do we do so?

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

#315

Post by ummonk » Sat, Jul 17, 2021, 6:58 PM UTC

dwohnitmok wrote: post #110

lupire wrote: post #90

Earlier quoted context omitted.

why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.

This is not unsound in the usual sense of "logical soundness" (which applies to logical systems such as first-order logic, rather than specific theories in the system such as ZFC). This is unsound in that it runs counter to certain philosophical commitments, namely that there should be some tangible, physical realization of all the natural numbers (although if you really go far in that direction you end up with ultra…

As you allude, it's rather ridiculous to make certain philosophical commitments but only apply them to natural numbers. I think ordinary finitism will do fine though, no need to go to ultrafinitism.

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

#316

Post by ummonk » Sat, Jul 17, 2021, 6:59 PM UTC

rssoconnor wrote: post #102

lupire wrote: post #90

Earlier quoted context omitted.

why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.

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.

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

#317

Post by cevi » Sat, Jul 17, 2021, 7:24 PM UTC

HotHotLava wrote: post #277

BoiledCabbage wrote: post #28

Earlier quoted context omitted.

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…

The illustration in the article doesn't start with the whole set of all real numbers, but with just "a" set containing an uncountable number of reals, so there is no contradiction in that sense. I'm assuming there's some unmentioned technical condition on which sets you are allowed to choose in order for the procedure to work, otherwise the argument would indeed seem to lead to a contradiction when choosing the set o…

This assumption is correct - the quanta article left out quite a bit of detail about how forcing actually works, while trying to give some hint of the philosophy behind it.

As it turns out, you can still apply the forcing technique even if you start with the whole set of all real numbers. What happens in this case is a bit surprising: since there's no legitimate way to add new real numbers that weren't there previously, the forcing procedure cheats by pretending that real numbers have nonstandardly long decimal expansions.

To make the way it cheats a bit more concrete, we start by first imagining that there are "nonstandard integers" n which are bigger than all of the "true" integers from our starting model. Once we assume that these integers exist, we have to commit ourselves to providing answers to questions like, "what is the nth digit of pi?", "what is the n+1th digit of pi?", and so on in a consistent way. By answering these questions, we embed all of the original real numbers from our starting universe into the new universe. But the point is that now that we have all of these extra digits to play with, all of the original real numbers only fill up a tiny subset of the potential "real" numbers in the new universe, and we can happily go back to forcing new ones in.

Of course, adding nonstandard integers to our universe is quite a violent change, so we also have to worry about whether we've accidentally screwed up the way that the ordinals work in the process (for instance, the "first infinite ordinal" in the new universe now contains all of the nonstandard integers we added), and we need to worry about this again when we get around to forcing the new reals in. So a whole lot of technical details need to be ironed out carefully, using a few clever combinatorial arguments, to make the whole charade come together.

All of this cheating happens under the hood in a way that is not obvious at all when you first go through the technical details of the forcing construction. I only learned about the full perspective from Joel David Hamkins's "naturalistic account of forcing".

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

#318

Post by gwf » Sat, Jul 17, 2021, 9:24 PM UTC

hutzlibu wrote: post #255

Someone wrote: post #199

Earlier quoted context omitted.

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

"the claim that the set of natural numbers has the same size as that of the rational numbers" Where can I read more about that? Because, both are infinite, but there still should be more rational numbers, than natural numbers?

  for a in range(1, Infinity):
      for b in range(a):
          print(a-b, "/" , b+1)

Will print out:

      1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, ...

Hence, we've just mapped all rationals (with duplicates) to a single linear list. Since any linear list can always be mapped to the naturals (1, 2, 3, ...), they have the same cardinality.

QED

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

#319

Post by ummonk » Sat, Jul 17, 2021, 10:54 PM UTC

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…

Constructivism (including the kind that precludes uncountable infinities) is not inherently more shocking than classical mathematics. It only seems surprising because classical mathematics has become the default formalism.

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

#320

Post by ummonk » Sat, Jul 17, 2021, 10:57 PM UTC

scapp wrote: post #105

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…

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…

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

Huh? It's trivial to create an injection R -> N, by encoding each computational algorithm - whether valid or invalid - as a number.