Hacker News Reader

Comment by t234oi324324 | Hacker News Reader

I've increasingly come to doubt the utility of all these things.

Real numbers and Lesbesgue integration that stem out of 19th c. analysis came before Computability was a thing... and it turns out that all but a measure 0 set of real-numbers are actually computable.

So all these things that we worry about don't even "exist" in a computational sense.

Mathematicians haven't come to terms with this (barring non-standard analysis etc.), and I suspect this is one of the reasons it's losing mind-share.

View on HN

Note that "computable" just means "computable by a Turing machine or equivalent system", at this time. We don't know if we are missing some other form of computation that goes beyond the abilities of a Turing machine, that could upend the whole concept. And given that we haven't proven that general human thinking is a computable process, there is at least one significant candidate for possible computation beyond Turing machines.

Note that I don't personally think it's likely that our thinking goes beyond the capabilities of a Turing machine, not at all. But I also think it would be premature to throw out all mathematics that doesn't conform to Turing machine computability before we are more sure that this is the best possible model.

And even if it were, there is also the question of whether physical processes are computable or not. Right now there are plenty of physical processes where our best and only reliable models for predicting their behavior require assumptions from calculus, like the existence of all real numbers. For example, there is no successful formulation of quantum mechanics where the distance between two particles moving relative to each other can be constrained to any subset of the [minDistance, maxDistance] interval of the real number line. Which means that, as the particles move away from each other, at some times the distance between them will have to be an uncomputable number (and given their density in the real number line, this will be approximately all the time).

Brownian motion mentioned at the end of the article and more generally Langevin Dynamics are incredibly useful. They're this weird interface between normal physics and statistical mechanics. When a big complex molecule is constantly jostled by smaller molecules, these nowhere-continuous motions are a good way to approximate what happens.

Plus, rather bizarrely, it helps to understand this area to do actual statistics, in software such as Stan.

>> and it turns out that all but a measure 0 set of real-numbers are actually computable.

This is the wrong way around. The computable numbers have measure 0. In fact, they are countable.

The non-computable real numbers have full measure.

(proof: by definition, computable numbers are generated by a program, which can be represented by a finite number of bits. The set of finite numbers is countable).

What could it mean to have full measure but nobody can provide any method of generating the digits to a single element of the set? We can define things like Chaitin's constants, but we don't know very many digits, and Chaitin's constants are countable. We claim there are these bountiful numbers, more numerous than the countables, but can't even specify the value of any of them.

I suspect some future generation is going to decide that diagonalizaation is based on questionable axioms. It leads to invisible pink elephants.

They’re not finitely describable — for any member of that set, no matter how many digits you articulate, you’ve named a rational number.

The same is true even for numbers that have finite predicates defining them — because there’s only measure zero finite predicates.

Most real numbers are indescribable sequences (ie, not finitely describable), so it’s not surprising we can’t describe them. That’s what happens when you construct something by including all possible infinite sequences — almost all of them are total gibberish.

Diagonalization is a consequence of that: we have a schema of descriptions forming our predicate and prove no matter how we index reals by the integers, there’s more stuff out there. To get rid of that, we need to stop completing sequences.

Most people aren’t in favor of that finitism/constructive approach now — so I’m not sure why that would change.

Even Cantor's counterexample, where he traverses the diagonal of an enumerated list of numbers, he has a countable number of choices to pick his digits. So we've built a countable set, and he claims it's incomplete by picking one number from a countable set of counterexamples. So now lets union the original set with Cantor's countable set of counterexamples, and get a combined set which is also countable, right?

But that schema can be applied to your new set, as well — to create yet more counter examples. Your method didn’t exhaust the real numbers outside the original list. You merely added one of them.

For any listable subset of the real numbers, we can provide a counter example. And since we’re proving by contradiction in Cantor’s argument, we assume the original list is exhaustive, ie there’s a bijection between naturals and reals.

We show that assumption leads to a contradiction, because there’s at least one real number for which no natural maps to it. Therefore, there can’t be such a bijection.

- - -

Assume f is a bijection between N and [0,1].

Let an be the nth digit of f(n).

Then x = sum(1,inf)[10^-n * (an + 1 % 10)] is a real number in [0, 1] for which there is no f(k) = x. So f is not onto and therefore f is not a bijection.

Therefore, no such bijection can exist — by contradiction.

- - -

You can’t patch that schema up just by adding counter examples to your first choice of bijection — because a counter example is constructable for any bijection attempt.

The fundamental problem is that reals include limits — which is what allows the sum to be a real number.

I won't claim to have any proof in hand, but there's still something fishy about it all. I think things like Banach-Tarsky and such ought to be treated as counter examples to show the absurdity of the Reals.

At times I've thought maybe the problem with diagonalization is forcing me to do a (countably) infinite number of steps before Cantor gets to take an infinite number of steps. For instance, I can give a trivial counting scheme and claim it will eventually generate every number between zero and one, perhaps by writing a program to write programs that generate digits. It's all very deterministic, and I state exactly what I'm doing up front.

So I give the first number (program), and Cantor gives his first digit and says it's not in my list. Then I tell Cantor the countably infinite number of places where his first digit is found, and we select those programs. Then he gives me his second digit, and I select the subset where those are found. So we go back and forth, he keeps saying his number so far is not in my list, and I keep telling him all the places where it is in the list... Feels like stalemate there.

There are other places (such as summing the alternating harmonic series) where you have to be very careful about the ordering of operations. If he really has a higher order infinity of numbers not in my list, maybe I should be able to ask him for his list first, no? It's uncountably infinite, but he can't provide even one of them.

You don’t have to do anything but assume such a bijection does exist, as in my comment: its existence leads to a contradiction in the presence of limits — just like I showed. But without that same limiting to build sets, you can’t construct N from the successor function and you can’t discuss the power set of N.

So we either need to throw out countable limiting to build sets or accept that such set building rules out bijections between reals and naturals.

You think Banach-Taraki is weird (as do most people), but I’d argue a world where you have finite numbers or couldn’t discuss the set of subsets of the naturals is even weirder.

> maybe I should be able to ask him for his list first, no?

There’s no such list indexable by the naturals, as shown by that contradiction. If you allow indexing by the reals, that request is trivial.

You've edited your post a bit from what I originally replied to. Looking at your bijection stuff, I think you're just restating Cantor's diagonalization with `(a_n + 1) % 10` as your mechanism for choosing digits, but maybe I've got that wrong. I appreciate that it's well defined, but I think it ignores my complaint.

Let's say I tell you that I'm building my list of numbers between zero and one by taking the natural numbers, reversing the digits, and just putting a decimal place in front:

     0: 0.0....
     1: 0.1....
     2: 0.2....
    ...
    10: 0.01...
    11: 0.11...
    12: 0.21...

It's a silly mapping, and I'm sure there are a few problems with it, but let's start there. For now it doesn't matter what digits I'll choose afterwards - maybe it's all zeros, maybe it repeats the digits, maybe I'll do something more clever, but skip that for now.

My list has a number that agrees with your number to any number of digits we choose. You and Cantor have to force me to give my infinite list of numbers all at once, and then build your infinite length counter example all at once. What axiom lets either of us do an infinite number of steps and say we're finished? What axiom says you can do an infinite number of steps after I do my infinite number of steps? When we do limits with deltas and epsilons, we say that we will get closer as we keep going, not that we got there.

If you give me the first 1000 digits of your counterexample, I can tell you all the elements in my set that match your number up to the first 1000 digits. If you give me 1001, I can tell you all the places that match that too. A million, a gazillion, I can keep matching. And as you keep adding more digits, I can keep telling you an infinite number of places that match.

So it really seems like there's a problem with the order of operations. It's like playing chess, and you force me to make all my moves and come afterward to checkmate me. But if we take turns, where I make a finite number of steps and you give me your next digit, then it's my turn again, I can keep matching you all day and all night.

> What axiom lets either of us do an infinite number of steps and say we're finished?

The same one that says we can build the naturals from successors — without that, we don’t have all of the naturals. As I’ve been saying repeatedly, this is due to building sets from induction.

A limit L for an infinite sequence (an) is such that for any epsilon, there’s some n where after that n, | L - an | < epsilon. You have a set of rationals indexed by naturals building towards that real number — but you can do it the other way and define reals as those sets which converge to it.

> And as you keep adding more digits, I can keep telling you an infinite number of places that match.

The reals that are indescribable are truly weird: they look like subsets of N that are infinitely large but exclude infinitely many as well, without any pattern to inclusion or exclusion. And you can show this power set definition matches [0,1] by taking the binary 0 or 1 at position n to be if n is included in that subset.

To get rid of the weird reals, you need to force sequences like that out. What makes the reals larger is that they’re defined to include the limits of all converging sequences. Rationals don’t, eg, sqrt(2) or pi.

> But if we take turns, where I make a finite number of steps and you give me your next digit, then it's my turn again, I can keep matching you all day and all night.

But this doesn’t end in a bijection, because after you follow this construction for an infinite number of turns, I can name a real number not in your list — as my final move. That’s what the schema says: no matter how we construct the list, after it’s built, I can name a number outside of it. You’re not showing the list is complete, ie includes all reals, merely that we can include a particular number if I tell you it digit by digit — but we knew that by construction (ie, there will always be some countable converging sequence of rationals).

Every real is constructed by some countable sequence of digits; but there’s more real numbers than countable infinity.

> The reals that are indescribable are truly weird [...]

Well, I appreciate your patience. I'm certain I won't find a hole in any of your arguments or the conventional wisdom, but the Reals outside of the Computables (or Defineables might be a better choice) are more than weird, they're absurd. They're dense in the number line but only a countable number of them are anywhere to be found, named, or described past a few digits.

Additionally there is always a Computable number between any two Reals and a Real between any two Computables. *This* ought to imply a one-to-one correspondance, but I'm certain I can't defend that argument either.

As for applied math, any situation where we claim the Reals are required (perhaps as the position of a particle or the coefficients of a wave function or something) is uncomputable. So saying the Reals apply to reality probably says something very weird about determinism too.

> are more than weird, they're absurd

They’re a consequence of subsets being more complicated to talk about than the set itself.

Real numbers are weird compared to naturals because the indescribable ones match to subsets with infinite complexity. But functions on the real numbers are similarly large compared to the reals themselves — because they can have any subset of reals as their output, including infinitely complex ones.

> This ought to imply a one-to-one correspondance, but I'm certain I can't defend that argument either.

The interval is like a fractal: between any two points is a full copy of it. And for any prefix there’s a lot more “and then the tail is infinitely weird” than coherent tails.

> So saying the Reals apply to reality probably says something very weird about determinism too.

Math is a model.

Nothing we compute can’t be don’t purely over computable numbers — but you simplify a lot of proofs if you work in the space where every convergent sequence has a limit, then just approximate. Including proving that approximations work nicely.

You’re not making a claim about reality; you’re simplifying your mathematical machinery by packing all of the badness into a few technical axioms about induction — and then just shrugging because Banach-Tarski paradoxes are probably unphysical and purely a construction of the model.

Btw, I wasn't saying to just add one of Cantor's numbers. His mechanism for picking diagonals, whatever it is, is a countable list. He picks a first digit to disagree with the first digit of my first number: That gives him 9 choices. He picks a second digit, another 9 choices. It grows exponentially, but I can make a one-to-one mapping for all (any) of his choices, so ALL of his numbers come from a countable set.

> I suspect some future generation is going to decide that diagonalizaation is based on questionable axioms. It leads to invisible pink elephants.

Past generations of course were not always comfortable with it either, but.. No one shall expel us from the paradise that Cantor has created for us.

https://en.m.wikipedia.org/wiki/Cantor%27s_paradise

It’s useful I think to have a conservative impulse somewhere as a counterpoint to wild invention, and math has benefited a lot from the constructivist vs formalist debate.

Curiously enough, the Downward Löwenheim-Skolem theorem proves that if any first-order theory has an infinite model, then it also has a countable model, assuming the theory itself is countable.

So even though ZFC talks about uncountable real numbers, there is actually a countable model of ZFC that satisfies the same axioms.

This isn’t an inconsistency, but it really does blur the lines between what we think of as mathematical objects that are “out there” in some sense (like uncomputable real numbers) or whether mathematics is just a game of symbol manipulation that also happens to predict the physical world pretty well.

It is not /really/ countable in a computable sense; it is undecidable whether or not a program generates a real number or diverges (as a consequence of Rice's theorem). Thus you cannot compute a function that enumerates all programs that compute real numbers.

I'm not sure what you mean exactly by "countable in a computable sense." Sure, certainly you can't generate one program that enumerates all the programs that compute real numbers.

But the set of programs that compute real numbers is a subset of all programs, and the set of all programs is countable. Therefore the set of computable numbers is countable.

edit: I think maybe it wasn't clear that I'm talking about cardinality and measure? To be a little clearer - I'm saying that the computable numbers have (standard) measure 0 because they have countable cardinality. Any subset of the real numbers with countable cardinality has measure 0. And the set of all real numbers, of course, has uncountable cardinality.

I get what you are saying. My point is that someone who is philosophically disinclined to buy into the "existance" of non-computable real numbers, e.g. constructivists, because they are not effectively computable, are also going to be, by the same logic, disinclined to buy into your argument that the computable real numbers are countable, because in order to count the computable real numbers you would need a function to enumerate them, at that function is also not computable.

> But the set of programs that compute real numbers is a subset of all programs, and the set of all programs is countable. Therefore the set of computable numbers is countable.

A constructivist is also not going to buy into your argument that a subset of a countable set is countable. Heck, the constructivists are not even going to buy into an argument that a subset of a finite set is necessarily finite (they have a term for such subsets: 'subfinite').

Yes, I know that this constructivism feels so bizarre that it cannot possible be coherent; the whole notion of cardinality appears to become useless. But you get used to it after a while.

Heck, even in classical mathematics, trichotomy of cardinally requires (or rather /is/) the axiom of choice. So cardinality wasn't really super well behaved to begin with.

No because Mathematics still has power. It would be awful if we couldn't dream beyond floating points or Mathematics were ties to the financial and physical forces that shape processor architectures.

That measure 0 set of computable real numbers includes (nearly) every real number you'd ever describe – including all the reals on this page so far. The only exceptions are things like Chaitin's constant, which isn't really interesting for real analysis.

This post reminds me of: https://old.reddit.com/r/mathmemes/comments/g3kolt/stop_doin...

As a constructivist, I somewhat agree with your viewpoint, though my views are a bit more nuanced. (e.g. Dedekind's construction of the continuum as a collection of points is perhaps the primary source of corrupted thinking, which muddles even well-meaning thinkers into thinking that it is even possible to separate computable points from non-computable points. The real numbers form a /continuum/, and a continuum cannot be described as simply a collection of points.)

That said I believe your comments are off the mark in regards to the topic of the Weierstrass function. The Weierstrass function is completely well behaved from a constructive point of view[0]; it is uniformly continuous and everything. In particular we can (constructively) map (constructive) real numbers to (constructive) real numbers via this function.

[0]https://mathoverflow.net/a/43904

>So all these things that we worry about don't even "exist" in a computational sense.

They directly lead to weak derivatives which have certainly saved 10s of thousand of lives.

True. You could partition math with the question "Could a computer do that?" If the answer is yes, "that" is practical. If the answer is no, "that" is probably useless.

You could also partition roads to drive on base on "can I see a city with my naked eye". Seas to explore by "can I see land on the horizon" and so on.

Reply on news.ycombinator.com