Right. So for some they aren’t something to be taken seriously. It depends on how seriously you take measure theory. Or on how seriously you take pure math. To me the “proof” that matters most is that our technology is reliable. But I understand Hume to have made a convincing case that we just a enact a faith in the uniformity of nature. We can’t help ourselves. And even in saying that I assume a uniformity of nature, that humans will continue to expect from the future what they found in the past.
You need the filtering if you are trying to prove the computable numbers are uncountable via diagonalization. Recall that the diagonal number must itself be computable. And this is only ensured if each element on the list is computable.
In another lingo, you need a diagonal total function, which is only guaranteed if the list is all total functions.
Yet we know that the computable numbers (and total functions) are countable, so such a filter isn’t out there.
Well, I now know much more concerning the history of Constructive mathematics. Again, after Wittgenstein, I have some sympathy for such positions, but also some trepidation. Maybe you can help me articulate the problem by working on what it is to be a mathematical entity.
So we have:
The objects of study are constructive processes and constructive objects arising as the results of these processes. The concept of a constructive object is primitive. The main feature of constructive objects is that they are constructed according to definite rules from certain indecomposable elementary objects.
Now I understand this as more or less a definition of what it is to be a mathematical object—they are the products of construction according to certain rules.
I’d like to suggest a contrasting view, a version of Quine’s “To be is to be the subject of a bound variable”.
On the one hand we have mathematical entities as existing only if there is a suitable construction; on the other, a much more liberal approach, all that is required is an existential quantification.
Now it seems to me that such a Quinian approach might accept the existence of real numbers whose decimal expansion is not computable, rejected by Markov.
Anyway, that’s the direction in which I’m wandering. I have a string of new papers to look at.
For Brouwer, this is too “linguistic” in a pejorative sense. We end up with obscure entities that are opaque to a purely mathematical intuition ( or, for Markov perhaps, deficient in operational meaning.)
To me it’s worth noting that proofs are computably checkable in formal systems ( I don’t pretend to be an expert on such things, so buyer beware.) So even in logical-linguistic systems, we insist on some operational/algorithmic core. That keeps everything from blowing away in metaphysical speculation.
Weyl might be worth looking into as someone who felt the value of both paths.
Another mathematical “possible” to which Weyl gave a great deal of thought is the continuum . During the period 1918–1921 he wrestled with the problem of providing the mathematical continuum—the real number line—with a logically sound formulation. Weyl had become increasingly critical of the principles underlying the set-theoretic construction of the mathematical continuum. He had come to believe that the whole set-theoretical approach involved vicious circles[11] to such an extent that, as he says, “every cell (so to speak) of this mighty organism is permeated by contradiction.” In Das Kontinuum he tries to overcome this by providing analysis with a predicative formulation—not, as Russell and Whitehead had attempted, by introducing a hierarchy of logically ramified types, which Weyl seems to have regarded as excessively complicated—but rather by confining the comprehension principle to formulas whose bound variables range over just the initial given entities (numbers).
Also choice sequences or constructions-in-progress are pretty fascinating. Do we admit time into mathematics ? That is perhaps the key question.
In his early thinking Brouwer had held that that the continuum is presented to intuition as a whole, and that it is impossible to construct all its points as individuals. But later he radically transformed the concept of “point”, endowing points with sufficient fluidity to enable them to serve as generators of a “true” continuum. This fluidity was achieved by admitting as “points”, not only fully defined discrete numbers such as 1/9,
e, and the like—which have, so to speak, already achieved “being”—but also “numbers” which are in a perpetual state of “becoming” in that the entries in their decimal (or dyadic) expansions are the result of free acts of choice by a subject operating throughout an indefinitely extended time. The resulting choice sequences cannot be conceived as finished, completed objects: at any moment only an initial segment is known. Thus Brouwer obtained the mathematical continuum in a manner compatible with his belief in the primordial intuition of time—that is, as an unfinished, in fact unfinishable entity in a perpetual state of growth, a “medium of free development”. In Brouwer’s vision, the mathematical continuum is indeed “constructed”, not, however, by initially shattering, as did Cantor and Dedekind, an intuitive continuum into isolated points, but rather by assembling it from a complex of continually changing overlapping parts.
My own view is that the “foundation” of math socially is working technology. So hand-wringing about foundations is aesthetic expression. Does one prefer ( to the point of prioritizing) “linguistic” logic ? Or the numerical-computational ? Is math about formal logic or the positive integers ?
Personally, I think the rational numbers are intensely beautiful. A crystalline triumph of the human mind. But we discover that, if f(x) = x^2 - 2, that we can only solve for 0 <|f(x)| < epsilon. No use trying to solve f(x) = 0.
We can do it with or without filtering. If we don’t filter, then anything nonsense or otherwise undefined yields ‘0’.
So we have a bunch of cases to consider. We’re trying to prove computable numbers are uncountable by providing an example of a computable number not on the list, which by initial intuition cannot happen.
So let’s start out with your filtered list. We have a list of countable numbers, all of which produce some valid output value. We also have our number D (diagonal) which we are building by taking the appropriate digit of each member on the list and adding 1.
If this number is countable, then it is on the list at index N, but what is digit N? It’s undefined, being a self-reference. If it’s undefined, it shouldn’t be on the list. You can’t assign a default value since it would be by definition wrong.
If it isn’t on the list, then it has no index and isn’t one of the countable numbers and you haven’t demonstrated any countable number that’s not on the list.
Now we try the unfiltered list, assinging 0 to all the elements that would have been filtered. Our new D is at a new N now, and again, we run into the problem of an undefined digit. It can’t be zero (default) since that would make the real value D a ‘1’ at digit N. Hence there is no defined computable number that isn’t on the list.
All attempts to prove the computable numbers to be uncountable have failed. Maybe I did that wrong. I encourage you to come up with an example that works. None of mine did, but 3 white swans hardly proves the lack of a black one.
The obvious rejoinder to proof-checking is that, if we presume the validity of reductio arguments, we do have proof of uncomputable reals. Constructivism wants to rule out certain sorts of proofs, by rejecting certain sorts of deductions, and that looks to be more an aesthetic choice than one forced by the maths.
I have considerable sympathy for choice sequences, but I’d reject the suggestion that they involve time; that strikes me as a hangover from Kant’s misguided idea that change requires time. It doesn’t. The notion of an incomplete choice sequence is parallel to the observation that we can have arbitrarily large, consistent yet incomplete systems in compliance with Gödel.
And we might well reduce pure maths to applied maths, but where’s the fun in that?
In the end I don’t see that we are forced to make a choice between classical and intuitionist approaches. It is open to us to say that if “the objects of study are constructive processes and constructive objects arising as the results of these processes” then these will be the realists; or to not restrict our mathematics in this way and allow a differing set of results. If we reject Platonism, dropping the idea of One True Maths, then the choice is again more one of aesthetics. More like an artist choosing between acrylic and watercolour.
All this leaves as a separate issue, which maths we use when building bridges. The test there is indeed pragmatic - the cheapest adequate bridge, by definition, will do.
Again, we are riding rough-shod over the details here. Yet the very fact that the conversation is ongoing lends itself to concluding that there is no right or wrong answer.
From over here, it seems that you are understanding a computable number as something that pre-exists the program that generates it.
That would be a Platonistic approach. Which is fine. But then we aren’t speaking the same language.
Are you imagining/assuming an uncountable infinity of points on the line ? And also that only some of these points are computable ?
For me a computable number is one that is the output of a program. So there are definitely no more computable numbers than programs. The “set” of programs is countably infinite, because we can enumerate them. So it is obvious that the computable numbers are countably infinite if not finite. But it’s obvious that they aren’t finite. I can argue this if necessary.
From my POV, this would be like searching for a fraction p/q such that (p/q)^2 = 2. But I have been convinced that no such fraction is out there to be found.
The “obvious” countability of computable numbers is used by Turing in a slick case against the possibility of a filtering of programs into those that go with computable numbers and those that don’t.
Yes, an aesthetic choice, a philosophical choice. I agree.
Formalizations “encode” philosophical beliefs about math. If you zoom out enough, you get to a metalanguage. You get back to people who do or do not consent to the mechanical criterion.
This is a rich issue. Bishop didn’t like them. I get it. But there’s something deep here. Reality, from the human point of view, is unfinished. Bishop wanted God to do his own mathematics, to leave us alone with ours. Yet he was, for aesthetic reasons, allergic to Brouwer’s most “finite” idea.
Let’s say I get a sequence of bits from outer space. So far I have 200 bits and I don’t expect the transmissions to stop. Maybe the transmission is not perfectly regular. Now imagine a second transmission from some other exoplanet.
Weirdly I have also received 200 bits so far from that source. And, even stranger, both patterns are the same so far. The same 200 bits, so far. But no guarantee that they will remain synchronized.
This is why the equality of two of this kind of real numbers is not computable. We don’t even have the code that generates the sequence. The sequence is a brute fact in progress.
In my view, time is fundamental.
I agree. And that’s how I see my preference for the constructive flavor. From over here, the continuum hypothesis is “not even wrong.” But so what ? The world isn’t governed by my preferences. A tragedy rated gray.
I agree. “The Truth is what God believes.” But I don’t have the luxury of access to that ideal POV.
Not that I find it relevant, but I’m no Planonist, and I don’t find meaning to say ‘X exist’ unless ‘exists’ is defined as a relation, like ‘the moon exists relative to Earth’.
Are you imagining/assuming an uncountable infinity of points on the line ? And also that only some of these points are computable ?
I wasn’t imagining them being on a line, but yes, one can arrange real numbers this way.
For me a computable number is one that is the output of a program.
I was more open than that. π is not a program, but it identifies a number with a single character. So my idea of ‘computable’ is ‘expressible’, and yes, any expressible number can be computed (to arbitrary precision), and any program that outputs a number will output an expressible one. So they’re the same thing, just different shortcuts to getting to them.
Are they the same thing? I write a short program to compute π to 100 digits, but that program is way more than the 100th item on our list of programs. So it’s Nth digit is going to be 0 regardless of what the Nth digit of π is. But that’s correct. 0 is the right answer here. Few programs will yield anything but zero in our diagonalization exercise.
So there are definitely no more computable numbers than programs. The “set” of programs is countably infinite, because we can enumerate them. So it is obvious that the computable numbers are countably infinite if not finite. But it’s obvious that they aren’t finite. I can argue this if necessary.
No need. The proof is pretty trivial.
From my POV, this would be like searching for a fraction p/q such that (p/q)^2 = 2. But I have been convinced that no such fraction is out there to be found.
Also pretty easily proven, but I don’t see the relevance to what I posted. Interesting note is that I think they killed the greek guy who first proved this. Proof of some numbers being irrational was not appreciated.
The “obvious” countability of computable numbers is used by Turing in a slick case against the possibility of a filtering of programs into those that go with computable numbers and those that don’t.
Hard to filter out the programs that don’t output a number given that the halting problem is unsolvable. This has no bearing on the computable numbers being countable, but it definitely has a bearing on the writing of a program to do our diagonalization computation. Such a program cannot exist, with or without filtering.
I think I might be going a step further than you, in that I’m happy for the reals to be continuous, also happy for them not to be continuous; that so long as we are clear about which we choose, and consistent in that choice, both can be so.
OK. Thanks for the clarification. In mainstream set theory, real numbers are sometimes defined as equivalence classes of Cauchy sequences of rational numbers.
I’m still not seeing though why you find it feasible that the computable numbers, as you understand them, are uncountable, as you understand uncountability. Could be I’m not hearing yet what these terms mean to you.
To me the very notion of computable number implies trivially that they are countable.
Yes. To me the situation is like this. Turing uses the obvious countability of the computable numbers to prove that no single method (program) can decide whether any given program will halt.
If there were such a method, then we could diagonalize, which is absurd.
To me this kind of argument in math, which I do find convincing, is strange enough to deserve its own thread. Likewise the proof that sqrt 2 is irrational. We are led to see the absurdity of one idea through its incompatibility with an idea that we refuse to refuse.
I let go of the hope that 2 has a square root, because I refuse to let go of the idea that a number can’t be even and odd at the same time. (I have tried to teach a proof that sqrt 2 is irrational to students without experience with proofs. It is…difficult.)
But this is part of why I emphasize the finite precision of measurement. Real real analysis ( as in applied real analysis ) implicitly features a fundamentally fuzzy world. It’s not equalities but inequalities that matter. Most computation with the flavor of the real number system uses a finite subset of the rational numbers. Floating point numbers are like a ladder where the rungs are more spaced out the higher you climb.
As soon as one cares about measurement and the construction of devices, one is knee-deep in the fuzz. Hence “real numbers are a way of handling rational numbers.” We need not invoke QM here. Any kind of measurement has an overlooked strangeness. Hence Bridgman’s need to emphasize operationalism. He was creating and measuring pressures that no one had ever measured. He had to create devices to do this.
The genius of a symbol for sqrt 2 is that you can carry it through the calculation and get your approximation at the end. If two of them collide, you can erase them and write down a 2.
Wittgenstein is not quite loved as a philosopher of math, but this sounds about right:
Indeed in real life a mathematical proposition is never what we want. Rather, we make use of mathematical propositions only in inferences from propositions that do not belong to mathematics to others that likewise do not belong to mathematics.
It might be better, more concrete, to say that certain signs are connected to action in the world. From measurement, to calculation, to action. Of course measurement and calculation are already concrete actions. But it’s cheaper to throw away ink on paper than to build a bridge.
Where did I ever say that? I agree that they’re countable.
Which means that no program can enumerate such numbers, which does not mean that they cannot be mathematically enumerated. Isn’t the latter enough to ‘diagonalize’?
Forgive me if you already know this. It’s fun for me anyway to use the math functionality finally.
Typically the possibility of enumeration is demonstrated by presenting one. These are implicitly programs. We just often write them informally for humans.
For instance, I can prove that the integers are enumably, informally, by just writing
0,1,-1,2,-2,3,-3,…
I could also write this as f(n) = \frac{(-1)^{n+1}(2n +1) +1}{4}.
I checked this with Julia, having found a slightly erroneous version online. “Don’t trust stupid AI !”
So we have f : \Bbb N \to \Bbb Z. To prove that \Bbb Z is countably infinite ( of the same “infinity” as \Bbb N), we need only prove that f is a bijection.
This means proving that f(n_1) = f(n_2) \implies n_1 = n_2. So f is 1-1.
Then we’d prove f(\Bbb N) = \Bbb Z. So f is onto.
But that’s overkill for something so intuitively clear. It’s obvious that every integer will be “printed” “eventually.”
What impressed me was the enumeration of the positive rationals. There is no least positive rational or greatest, so where do you even start ? And yet it’s pretty easy if someone gives you the main idea. Or one of several.
Well that’s what I first thought, given some of your comments. But you also posted this:
Perhaps I misunderstood you, but to me it sounded like you suggested that I try to prove the computable numbers uncountable. Which would be like trying to prove that \sqrt{2} is rational.
Neither of us were using the math symbols at that point. Hopefully we can avoid ambiguity on either side now.
I was just trying to point out that Cantor’s diagonalization method wouldn’t work. There seems to be a lot of talking past each other, so let me try to lay it out as clearly as I can. I put in headings and everything since it almost reads like an OP.
Expressions vs programs
Your list of integers is not a program. It is you listing a series of integer expressions. You say these are implicitly programs, but you show expressions, not programs. You also show a formula, which works nice for integers, but there isn’t one for say rationals, let alone the so called ‘computable numbers’.
I could write a fairly complex formula which yields every possible n/d where n=integer, d=positive integer. But most of those elements will be improper fractions, which need to be pruned in order to achieve the bijection required for assessment of countability.
Programs
Valid programs output an expression for a number. There are multiple programs that output the same number, so again, pruning is necessary. Most programs are invalid, or don’t output numbers. One cannot write a program to enumerate the valid ones since Turing has proven that there’s no way to determine all the ones which are valid.
Programs are finite. They have to be in order to be countable. Any finite program that outputs a number (say in decimal or binary form) is going to output a rational number. It can run indefinitely, eventually outputting a repeating series of digits after the decimal, or it will stop. All these are rational numbers, and we know those are a finite subset of the infinite set of rationals.
Programs can be written to print out the first N digits of some irrational number (like pi or root 2), but any such program will be higher than N on the enumeration list, so any diagonalization attempt will always yield a digit not printed, defaulting to probably zero.
These are problems with programs that prevent their being meaningfully enumerated
Expressions
‘2’ is a lot simpler way of conveying a number than writing a program to output ‘2’. But there are problems. An irrational number can be specified like ‘pi’, which has an Nth digit unlike the program that prints pi as far as it can.
What about big numbers? Until the decimal point is output, one has no idea of the magnitude of any of the digits. How do we decide if a digit stream is ever going to end? What’s the Nth digit of such a number? N to the right of the decimal? From the big end of the number? I always complained that it was a huge mistake to represent integers in big endian format, which is part of why Intel processors may have prevailed over their early rival Motorola. But with non-integers, big endian seems the only option. You can’t start at the middle where the decimal point goes.
I digress. The endian thing is of minimal importance here.
Ontic vs Epistemic enumeration
When we say there is a bijection between rationals and the positive integers, we’re probably talking about an ontic bijection. Despite the fact that there’s no way to know the quadrilionth rational number, there is one. That’s the difference between ontic and epistemic. The latter requires one to find it, and that can only go so far. There are finite epistemic numbers, but infinite ontic numbers, countable all.
Programs/computations are even more susceptible to this problem. Turing may have proven that there’s no way to know (epistemic) which programs output a valid representation of a number, but that doesn’t detract from the fact that every program either does or doesn’t (ontic). Hence, when discussing uncountable infinity, real programs shouldn’t matter. There need not be a program that enumerates them all since it cannot exist. The fact remains that there’s a list of valid programs, and those can be ordered.
Conclusion
When I talk about ‘computable’ numbers, I mean ‘expressible in principle’, and I’m talking about ontic expressions, not epistemic ones. This is a great deal of the reason why I push back at all this talk about programs being run, which is rarely the most efficient way to express a given number.
Second conclusion is the same as yours: These numbers available to us (expressible?) are countably infinite, and all attempts to prove otherwise will likely prove fallacious per some of the reasoning here expressed.
This is all standard, well-known stuff, and as far as countability goes, pretty trivial.
One might reasonably ask: is there a way of enumerating all rationals in such a way that no rational is repeated, and that every rational appears naturally in its lowest form?
Indeed there is; in fact there are several, of which one of the newest, most elegant, and simplest, is using the Calkin-Wilf tree.
I didn’t say there were not. I said there was no nice neat forumula to print the nth rational. The method you show is clean, and lends itself well to a little program that iterates to the Nth element via binary elimination, essentially meaning the millionth rational needs perhaps 20 iterations of a loop to reach.
You didn’t comment on my reasoning for not using programs to enumerate (real or in principle) said ‘computable numbers’, and why I rely on expressions instead.
