Hacker News Reader

Comment by mananaysiempre | Hacker News Reader

Dunno. The real numbers, for example, are in the “most things are eldritch abominations” camp[1]: the reals are uncountable, the computable reals are a(n everywhere dense) countable set[2] (that is therefore[3]) of measure zero. Not that there’s a reason to expect these cases to be similar, just that weird things do happen.

[1] https://mathwithbaddrawings.com/2016/12/28/why-the-number-li...

[2] There’s a finite set of programs of a fixed length, thus (countable union of finite sets) a countable set of all programs, thus only at most a countable set of numbers they can compute.

[3] Every countable set has Lebesgue measure zero: cover point #n by a blot of measure ε / 2^n (that could even intersect other blots) to prove all of them have measure at most ε > 0, take ε as small as desired.

View on HN

I've made the argument many times before that the reals are certainly an interesting set of objects, but a poor abstraction for the concept of a number. We should work towards replacing them with a more well-behaved set without eldritch monsters such as uncomputable 'numbers' that you can't add or multiply with. E.g. https://en.wikipedia.org/wiki/Computable_number.

Computable functions do also have some weird behavior. For example: a) all functions are continuous, b) equality is not computable (maybe not so weird for anyone used to floating point), c) differentiation is not computable unless you work over complex numbers (but integration is!)

a) All functions from computable reals to computable reals are continuous. This makes sense, because an arbitrarily small input difference leading to an arbitrarily large output difference is not a good basis for computation. You can still have discontinuities for discrete computable maps.

b) Neither is equality computable for the reals. Nothing is lost here.

c) Differentiation is computable for the functions of computable reals if you have a computable rate of convergence.

How to do (c)? I tried to model the reals as lazily computed sequences of intervals with rational bounds where every next interval is subset of previous one, and couldn't write a higher-order differentiator function because on every step for a given input interval there is output interval with non-zero (in most cases) size and the differentiated function may contain quick enough oscillations that the derivative is unbounded, and thus the derivative will stay unbounded no matter what you do. What do you mean by rate of convergence?

https://en.wikipedia.org/wiki/Modulus_of_convergence

(I assume you refer to the sequence of reals that is used to compute the limit in the definition of derivative) But is there a way to somehow construct this modulus automatically for some functions? And if there isn't, then isn't requiring manual input of the modulus like just requiring manual input of the derivative itself? Can you typically find the modulus manually more easily than the derivative?

> But is there a way to somehow construct this modulus automatically for some functions?

In a sense. You would end up with https://en.wikipedia.org/wiki/Automatic_differentiation.

The amount of functions you can construct in this manner is massive, along with their derivatives, but it is not an operator that given an arbitrary computable function gives you its derivative.

Thank you.

There’s a tradeoff[1] throughout mathematics, not unlike the expressiveness—analyzability one in programming languages: either the set of things you’re working with has nice properties (e.g., for the reals, completeness) and supports nice constructions with no caveats (e.g., for the reals, limits); or each of the things in the set is individually nice and tractable (e.g. computable).

There isn’t a single universally appropriate choice here, and sometimes even the direction of the axis is not obvious (real numbers lack solutions for algebraic equations; complex numbers lack smooth functions nonzero only in a finite region), but usually a simple family of eldritch objects is easier to deal with than an byzantine clan of cuddly objects.

Could you do simple physics and more generally ordinary differential equations over the computable numbers? You probably could to some extent, but it’s unlikely you’d get the nice intuitive geometry you get over the reals (see e.g. Arnold’s ODE textbook). The (basic) geometry of surfaces parametrized by real coordinates is fairly straightforward (differential geometry); the geometry of surfaces parametrized by rational coordinates is famously mind-blowingly abstract (algebraic geometry). The (basic) theory of real or complex functions is mostly understandable (analysis); the theory of natural or rational functions is horrifying (number theory).

Also, as a sibling reply mentions, it’s not like computable numbers will solve every problem: even though arithmetic over them is decidable, order still isn’t, and computable transcendental functions aren’t exactly a cakewalk either.

It doesn’t mean the computable reals aren’t worth knowing about, but, well, we live in a world where mandatory education has violently rejected[2] every advance in mathematical thought since Otto von Bismarck left office, and reduced the ones it accepted to a desiccated husk[3], so there are a great many things in that category. (I cannot help but remember the SMBC patriotism vs nationalism comic[4]: “Now I am mathematics.”)

[1] https://ncatlab.org/nlab/show/dichotomy+between+nice+objects...

[2] http://www.ams.org/notices/201201/rtx120100031p.pdf

[3] https://www.maa.org/external_archive/devlin/devlin_03_08.htm...

[4] https://www.smbc-comics.com/comic/an-important-distinction

The notion of uncountable set assumes certain axioms and classical logic. If instead one assumes rules of constructive mathematics, then one cannot construct uncountable set. Simplifying only computable numbers can exist.

Note that there are multiple versions[1] of “constructive mathematics”, so for example what Bishop’s constructive real analysis book considers constructive is not what Markov’s “constructive = computable” tradition does.

You are also going to encounter other funny things. One of De Morgan’s laws failing could seem troubling but ultimately theoretical—how, then, about the distinction about countable and constructively countable[3]? The set of all programs is countable; the set of all terminating programs is a subset of it, but can’t constructively be proven to itself be countable—after all, that would imply a solution to the halting problem! (Neither can it constructively be proven to not be such, as it is such in a consistent extension, namely classical mathematics.) Thus you get the new and exciting notion of subcountable sets. And that’s one of the mildest things that you’re going to encounter in your shiny new theory of cardinals.

(Anybody who can explain to me what the hell constructive Hahn—Banach[4] is about gets a beverage of their choice if we are ever in the same city. Without HB, you cannot do any functional analysis worth a damn, and without that you can’t really talk about Green’s functions / fundamental solutions to linear PDEs, which are in turn a basic tool for any electodynamics or quantum mechanics worth speaking about. Unless you want to forgo proof or the natural sciences, you need it, is my point.)

None of this is to say that I think intuitionistic logic is useless, mind you. It’s interesting and useful[5]! But so far it seems that you need to learn at least some logic (as a piece of mathematics and not mere terminology, so including scary words like “metalogic”) before you can really understand how it comes together.

[1] It seems categorical logic[2] says useful things about what the One True Definition should be? But I don’t understand it well enough to tell, and in any case the constructivist tradition predates not only it but category theory in general.

[2] https://mikeshulman.github.io/catlog/catlog.pdf

[3] https://ncatlab.org/nlab/show/constructive+mathematics

[4] https://www.cse.chalmers.se/~coquand/hahn1.pdf

[5] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...

> the distinction about countable and constructively countable? The set of all programs is countable; the set of all terminating programs is a subset of it, but can’t constructively be proven to itself be countable—after all, that would imply a solution to the halting problem!

I thought this had to do with the difference between being computable and computably enumerable.

Markov’s variety of the constructive mathematics is just what Bishop did plus the assumption that Church-Markov-Turing thesis holds. One does not need to assume that to recover any result of classical mathematics applicable in the real world. Also all those weird results of Markov’s approach that apparently “contradict” the classical mathematics is a consequence of Church thesis. Without that one cannot prove them. So Bishop’s approach is always compatible with classical mathematics.

As for Hahn—Banach I can only site the book “Techniques of Constructive Analysis” by Douglas S. Bridges:

For example, our proof of the Hahn-Banach theorem (Theorem 5.3.3) is, as it stands, a valid algorithmic proof of the classical Hahn Banach theorem. Moreover and this is one advantage of a constructive proof in general our proof embodies an algorithm for the construction of the functional whose existence is stated in the theorem. This algorithm can be extracted from the proof, and, as an undeserved bonus, the proof itself demonstrates that the algorithm is correct or, in computer science parlance, "meets its specifications". …

The Hahn-Banach theorem enables us to extend a normed linear functional, with an arbitrarily small increase in norm, from a subspace of a normed space to the entire space. This fundamental result has numerous applications throughout functional analysis.

In the constructive context we deal only with the extension of linear functionals on subspaces of a separable normed space. The standard classical proofs extending the theorem to nonseparable normed spaces depend on Zorn's lemma and are therefore nonconstructive. … The classical Hahn-Banach theorem says that we can extend a bounded linear functional v from Y to a functional u on the whole space X with exact preservation of norm. In general, as Exercise 5 shows, we cannot do this constructively. But, as we shall see, if we impose extra conditions on the norm of X, then we can make the extension norm-preserving.

tl;dr : Maybe the reals are far more mysterious. All we ever have handle over are the countable sets.

[0] Looking back, the core of my confusion was this. I had thought: I can visualize what ℵ0 means; that’s just the infinity of integers. I can also visualize what C=2^ℵ0 means; that’s the infinity of points on a line. Those, therefore, are the two bedrocks of clarity in this discussion. By contrast, I can’t visualize a set of intermediate cardinality between ℵ0 and C. The intermediate infinity, being weird and ghostlike, is the one that shouldn’t exist unless we deliberately “force” it to.

Turns out I had things backwards. For starters, I can’t visualize the uncountable infinity of real numbers. I might think I’m visualizing the real line—it’s solid, it’s black, it’s got little points everywhere—but how can I be sure that I’m not merely visualizing the ℵ0 rationals, or (say) the computable or definable reals, which include all the ones that arise in ordinary math?

The continuum C is not at all the bedrock of clarity that I’d thought it was. Unlike its junior partner ℵ0, the continuum is adjustable, changeable—and we will change it when we build different models of ZFC. What’s (relatively) more “fixed” in this game is something that I, like many non-experts, had always given short shrift to: Cantor’s sequence of Alephs ℵ0, ℵ1, ℵ2, etc.

[0] https://scottaaronson.blog/?p=4974

Reply on news.ycombinator.com