Bluntly,
looks to be almost exactly wrong. We can, and do, have consistency, but not completeness. But incompleteness is a glory; what can be said mathematically will always be more than what can be proved; so mathematicians will never be out of work.
Bits of my post disappeared - multiple windows, perhaps.
Here’s a paper by Vaananen on Second order logic and Foundations of Mathematics. It has more detail on his ideas of the power of expression. One direction of recent work has been towards using second order logic as a foundation for maths, as an alternative to set theory. The paper appears to be saying that Second Order Logic is itself dependent on set theory, somewhat surreptitiously, and so doesn’t help as much as might have been supposed.
Well beyond my ken. But our logicians are absent without leave. There’s a play on the difference between formal and informal arguments in the article that might be reflected in the exposition in the OP’s article.
Basically agree, a glory, and Chaitin sees it this way. My understanding is that “we” can’t prove consistency in systems like ZFC. Not saying we need to.
Personally I don’t care much about set theory. I was trained to use it in writing proofs, and it has some advantages as a language, but I find the numerical/computational core of mathematics more solid than what would prop it up.
Very meta.
I think maybe he is thinking in terms of later related findings, Lindstrom’s Theorem, etc., and so it’s not a total non-sequitur, it just isn’t explained very well (probably for brevity)?
A bit of overkill, perhaps. There is enough undecidability and incompleteness in ZFC to keep us going. Indeed, we can get to the inexhaustibility of mathematics from simple diagonalisation. That is the fundamental idea here.
And again, I’ll point to my thread on aesthetics:
No sooner is some foundation offered for mathematics, than some mathematician will find a way to undermine it, in the name of mathematics.
Diagonalisation as the core of creativity… 
Indeed, although we can get asymptotically close to doing so…
What we don’t have is inconsistency - and we do have an overall coherence that is quite stunning.
I’m with you on the sense of coherence, and I don’t think many worry about a contradiction arising.
Though maybe we could discuss what kind of math seems most secure for each of us. I can’t take non-computable real numbers seriously. Set theory is too platonistic for my taste.
Yeah, diagonalization is great. Definitely one of the key items that got me fascinated with math.
I mean I can understand the connection he’s drawing between the Incompleteness Theorems and the Uncertainty Principle but I think perhaps what may be “off” so to speak is if they’re understood to interpret the Incompleteness Theorems as directly tied to the Uncertainty Principle such that the Uncertainty Principle is a result or prediction of the Incompleteness Theorems.
As far as I can tell its more likely the case that the connection shared between the Theorems of Incompleteness and the Principle of Uncertainty is just a result of both cases being inherently self referential and thus exhibiting some similar properties which are common in self referential systems.
The Uncertainty Principle relies on methods of measurement which interfere with the information thats being measured, meanwhile the Incompleteness Theorems rely on showing the limitations of a mathematical system’s ability to account for itself. (As a greatly simplified way of putting it)
I also predict this is relevant as to why there appears to be an inverse correlation between expressive power and effectiveness in logical systems. The more expressive the system the more easily you can formulate a self referential statement within that system which has the potential (though not always a guarantee) to cause some confusion in that system, meanwhile a less expressive system might have fewer ways to reference itself and thus fewer ways to potentially go wrong but it also has fewer ways to describe situations which might otherwise require exemptions from the limitations of the system’s rigidity.
yet
Curious. We can never have a complete list of the reals. The constructivist claim is that for any real there is some computation that produces it. But setting that out is itself setting out a computation, and so offering a complete list of the reals - those numbers for which there is some computation. So we diagonalise that, and hence show that there are reals which are not the result of some computation.
The constructivist insistence: For every real, there is a computation that produces it collapses into contradiction.
I recognize you as someone who also knows some math, but here I think you’ve made a mistake.
The computable numbers are countable. This is trivial, because we can enumerate all Turing machines : 0 , 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, …
Some of the these Turing machines give us a computable real number.
If we could tell which ( decide the halting problem, etc.), then we could indeed diagonalize the computable real numbers, having filtered out the junk, proving them uncountable. But this contradicts their countability.
Therefore the halting problem is not decidable.
This is in Turing’s paper, and I quoted it above, but here it is again:
It may be thought that arguments which prove that the real numbers are not enumerable would also prove that the computable numbers and sequences cannot be enumerable…[W]e might apply the diagonal process. [But the ] fallacy in this argument lies in the assumption that [ whether a machine is circle-free ] is computable [by a single circle free machine ]…In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process [ to decide whether any given machine is circle-free or not.] … This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that “there must be something wrong”.
Disclaimer : There are many equivalent encodings of Turing machines, and there is nothing special about Turing machines. Or the computable real numbers. The same point — that we can’t solve the halting problem — can be made via computable sequences. I’d call the proof “informal” in the sense that it appeals to a big picture understanding of the situation.
I may indeed have made a mistake, but I don’t see where from what you wrote - indeed, you seem to be repeating what I said.
Perhaps the structure wasn’t clear. What I offered was a sort of reductio, from your comment supporting diagonalisation but not non-computable reals. We obtain non-computable reals by diagnoalising the computable reals, so showing that there are real numbers that are not the output of any calculation.
There are computable reals, and there is diagonalistaion; so there are uncomputable reals.
Turing’s proof is very brief, and I quoted it out of context.
Here’s the gist. To diagonalize on the computable numbers, you need a list that contains only computable numbers. The diagonal computable number, which is not on that list, must itself be computable. Because the point is to show that any list of computable numbers fails to include at least one computable number.
So let’s say I am eager to do this. What I have immediately is a list of all Turing machines. This won’t give me what I need. Some of the machines will print a finite number of symbols. Some none at all. All the computable number Turing machines are on this list, of course, but I need a way to distinguish between Turing machines associated with computable numbers and those that are not.
If I had such a method, then I could indeed diagonalize on a second list that only includes computable numbers. But such a method is therefore absurd. Because computable numbers are obviously countable, given that they are a subset of a countable set.
I don’t love the set theory language, and I’m not being careful about trivial technicalities. I’m just giving an imperfect informal proof.
Oh, ok, so you are pointing out that the list of computable numbers can’t be complete? That’s true, but a parallel point.
Start again. Suppose all reals are computable. The we can list them. Then we can diagonalise that list, showing that there are reals not included i the list. So not all reals are computable.
So we have I think three alternatives: reject proof by contradiction entirely; reject that programs are countable; or accept non-computable reals.
So I conclude that there are uncountable reals.
I like that we are including philosophy in this discussion. To me these number systems don’t float above life.
Informally, we are enumerating the computable numbers. Because they are scattered throughout our enumeration of Turing machines. This is why they are countable. But because we can’t isolate the computable numbers, we can’t diagonalize. Which is proof that we can’t isolate. In my view, the countability of the computable numbers is obvious like 2 + 2 = 4.
But I think you are coming from a difference sense of the real numbers, perhaps the mainstream view, as something like a completed infinite set. For a constructivist, the real numbers are constructed as “programs” that output a convergent sequence of rational numbers. That’s Bishop’s approach. You define sums, products, etc., to generate new sequences that are also computable numbers, because the operations are defined to ensure that.
Sure. But you have to “believe in” the real numbers as something other than programs for generating rational numbers in the first place. (I oversimplify here for clarity.)
The easier way to prove that there are uncountable reals in mainstream math is just to note that the measure of a countable set is 0. Since the interval [0,1] of real numbers has measure 1, and the computable numbers within that interval have measure 0, the uncomputable numbers have measure 1.
In short, “most” or “almost all” real numbers are uncomputable. Yet the real world runs on computable real numbers. So this quirk of real analysis is annoying for some. Yet I once found it dazzling.
Or we insist on construction. I like Markov and Post on this stuff.
OK, so I understand you reject the classical inference from “not all reals are computable” to “there exist non-computable reals.” Fair, a position for which I have some sympathy.
I need to do more reading. Cheers.
I was going to bring up computable numbers. It’s an interesting list that includes all the rationals and much more, but yes, they’re still countable, meaning the majority of reals (uncountable) are beyond the ability to be expressed and are thus inaccessible to say humans. The ‘typical’ number in nature is almost certainly of this sort, inexpressible. Any digital simulation of such a universe would have to use finite precision approximations which would over time behave noticeably different than reality.
If we could filter out the junk, we could diagonalize what’s left, proving that the computable numbers are uncountable after all, a contradiction.
Don’t see the necessity of the filtering. Sure, most random strings don’t resolve to a number or a workable program, but that’s no more a problem than needing to say filter out the improper rational numbers while counting them.
But by doing such a diagonalization, aren’t you just proving that some numbers are not on the list and thus cannot be computed?
No, you’re not. Take Cantor’s number: List the digital representation of all the rational numbers in order and diagonalize that. You get a number that isn’t on the list, but guess what? That number is computable! (a self-referencing paradox?) The diagonal method seems to not be a valid one for generating a non-computable number. In fact, them all being inaccessible, it seems that there cannot be such a method. The proof needs to use different means than giving instructions on how to generate an example.
I hadn’t appreciated the size of the Markov family. I presume you mean Andrey jnr? What in particular - Markov’s rule?
I mean the son, yes, basically the central figure of Russian constructivist mathematics. His whole approach interests me. I taught his string algorithms ( analogous to Turing machines) in a class not long ago. A very beautiful and simple programming language. Very close to formal grammars. The math is intensely concrete. The tension between the discrete and the continuous is not swept under the rug.
A good intro here.
Cheers. It appears to be a clear enough article. I’ll have a read and a think.