What’s So Shocking About Incompleteness?

Logic & Philosophy of Mathematics
1

I saw this comment on Quanta Magazine from mathematician and logician Jouko Väänänen, contributing to a survey of opinions about the implications of Gödel’s incompleteness theorems:

Incompleteness is an unwelcome but unavoidable fact of life in mathematics, like irrational and transcendental numbers in number theory, or Heisenberg’s uncertainty principle in physics.

There is a kind of “Gödel barrier” that formal language cannot circumvent: The stronger the expressive power of a logic (meaning the more things you can say in the logic), the weaker is its effectiveness (meaning our ability to prove statements true or false in the logic), and the stronger the effectiveness, the weaker is the expressive power.

For example, one of the simplest logical systems is propositional logic, which lets you combine statements with operations such as “and,” “or,” and “not.” It is very effective, but its expressive power is weak. On the other end of the spectrum, there’s second-order logic, which lets you make statements about objects, properties, sets, and relationships. It has tremendous expressive power and very weak effectiveness. It is as if the “product” of effectiveness and expressive power were constant, just as in Heisenberg’s uncertainty principle, which says that there is a limit to the precision with which certain “complementary” pairs of physical properties, such as position and momentum, can be simultaneously known; in other words, the more accurately one property is measured, the less accurately the other property can be known. In logic, in a remarkable analogy, effectiveness and expressiveness are such “complementary” properties. This is the real content of Gödel’s incompleteness theorems.

We stumble forward in mathematics without any certainty of consistency or completeness. This is just how things are.

It is shocking that mathematics, which is the basis of exact sciences, lacks a foundation that can be proved to be consistent and complete. Hilbert can be forgiven for thinking that this cannot be the case. However, it is the case, as certainly as the square root of two is irrational. Mathematics has a puzzling lump of incompleteness which can be pushed from place to place but it will never disappear.

— Jouko Väänänen in What Do Gödel’s Incompleteness Theorems Truly Mean?

I’m curious how this holds up, so I would appreciate some input from the TPF members who are into mathematics and logic.

My maths and logic days are gone and mostly forgotten, but my gut tells me something is off.

First, isn’t the idea that irrational numbers are unwelcome at least 2,000 years out of date? The Pythagoreans may have found them unwelcome, but they became just another useful part of mathematics soon afterwards.

Similarly, Gödel’s incompleteness theorems might be “shocking” only according to unreasonable expectations, in the same way that the lack of an absolutely certain foundation for science was a scandal to Descartes. To be fair, that might be Väänänen’s ultimate point, that what seems shocking need not be if we reject our need for absolutely certain foundations—but my guess is that’s not the point.

Also, he puts propositional logic on one end of a spectrum of expressive power, and ends up with this:

In logic, in a remarkable analogy, effectiveness and expressiveness are such “complementary” properties. This is the real content of Gödel’s incompleteness theorems.

But since the theorems don’t say anything about propositional logic, how is this anything more than vague and impressionistic? Aren’t there other results in mathematics that show there to be a trade-off between expressiveness and effectiveness?

We stumble forward in mathematics without any certainty of consistency or completeness.

This seems to associate a blind, disorganized practice with the results of the incompleteness theorems, as if the latter implied the former. That does not seem legitimate to me at all. Again, it’s possible he is just exaggerating as a kind of dramatizion for popular appeal, but if so it’s quite patronizing and annoying—not least, I’d imagine, to working mathematicians.

As for Heisenberg’s uncertainty principle, it might be ok as an analogy, but when he says “This is the real content of Gödel’s incompleteness theorems,” he seems to be wanting to apply this to the uncertainty principle too.

Am I onto something here or am I talking bollocks?

3 Likes
2

On to something, in my view. Lots of books and videos play up the drama.

Proofs about formal systems are themselves informal. Humans persuade other humans with “proofs.” I come to “see” something, hopefully. But I can also check a bland formal proof for correctness. OK, I guess P is “true” or “proved.” But what does it mean ? Why should I care ? Because it allows me to validly generate another “true” statement that doesn’t say anything to me ?

Most mathematicians enact the assumption that meaningful statements are already true or false, even if they don’t or can’t know which. This is tempting if you say that a large positive integer is either prime or composite. But why does this feel right ? Because we have obvious algorithm for deciding it, if it isn’t too large. I could know, if I’m willing to pay for it with time and energy.

But the continuum hypothesis ?

Cantor immediately tried to determine whether there were any infinite sets of real numbers that were of intermediate size, that is, whether there was an infinite set of real numbers that could not be put into one-to-one correspondence with the natural numbers and could not be put into one-to-one correspondence with the real numbers. The continuum hypothesis (under one formulation) is simply the statement that there is no such set of real numbers.

Is this “true” or “false” ? Well the official machine of the time wouldn’t decide.

The pluralists (like Cohen) maintained that the independence results effectively settled the question by showing that it had no answer . On this view, one could adopt a system in which, say CH was an axiom and one could adopt a system in which ¬CH was an axiom and that was the end of the matter—there was no question as to which of two incompatible extensions was the “correct” one.

But what does the continuum hypothesis “mean” ? For many, these completed infinite sets are already out there, as timeless truthmakers. Yet Cantor’s proof that the reals are uncountable already makes them strange and elusive. The computable real numbers are countable, so the noncomputable real numbers are uncountable. A black and seamless sea of unnamable numbers, flooding the boat, but you can’t point out a single one. Some love this result. It’s sublime. For others it’s fishy.

My gripe might be that the foundations are/were already a swamp, if you consider Brouwer, Markov, Bishop, and others. So the article’s hype of this issue, while understandable, occludes all kinds of rich disagreement about fundamental issues.

Groups of human beings agree on what counts as meaningful and what counts as a proof. If you don’t agree, maybe you start another group.

There’s a personal element, my own appropriation, that often gets left out. So we get a fear of AI making math meaningless, because it can generate proofs and theorems that humans wouldn’t find. But I share math with others, like poetry. I “meet them in the meaning” of the math. Or I try.

AI will only be important, in this sense, if it generates something that speaks to me and others human at the same time.
Alpha Go made a strange and beautiful move that fascinated expert human players. It had an alien character for them. But most of us would not experience a sharing in that meaning with the AI itself. This could change, though I’m not so eager for that.

Away from the wild “pure” stuff, we use math to build things that work. This is a candidate for the “foundation” of math. “Real numbers” are “just” ways of handling fractions.

1 Like
3

Isn’t it more just a matter that there are things which we know, which we don’t know how we know them? That some axioms can’t be further explained or rationalised in terms of further or deeper axioms? So uncertainty and incompleteness both seem to signify limits in principle to mathematical and objective knowledge. You might think goes without saying, but recall Hawking’s aspiration in his Brief History of Time that through science we will come to know ‘the mind of God’.

1 Like
4

As I understand it, the desired formal axiomatic system could be straightforwardly converted into a machine that prints out all mathematical “truths.” No contradictions. No ambiguity. P or not P but never both, for every P. It would never finish, but in principle it would get to each truth eventually.

It’s like enumerating the positive fractions. You can’t print them “all.” But you intuit that the method will get to each one individually, given “time.”

5

Then you’d have the ‘the halting problem’? :grinning_face: Although to tell the truth, I’ve never understood that, either. (There used to be a very learned maths philosopher TonesintheDeepFreeze, on the old forum, haven’t seen him around. He would take everyone to task for pop interpretations of Gödel.)

6

I remember TonesintheDeepFreeze. Very serious and knowledgable about logic. A little reluctant to get philosophical about it though.

Please ignore the nerdy stuff below if you’re not in the mood for it. It’s for you and anyone else who is curious.

Here’s a summary of an elegant proof in Turing’s famous paper. Is there a program in the space of possible programs that can tell us whether any program whatsoever will halt ? No.

If you understand the famous diagonal proof — the best version just uses 1s and 0s — then it very weirdly gets you there by building on that basic idea. I lightly edit what’s below.

If a computing machine never writes down more than a finite number of symbols of the first kind, it will be called circular [ not associated with a computable number ] . Otherwise it is said to be circle-free [ and so it prints the infinite decimal expansion of a therefore computable number. ]

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

The computable numbers are “countable.” We can list them in order. We can list all programs in order, which gives us all the computable numbers and lots of junk mixed together on one list.

If we could filter out the junk, we could diagonalize what’s left, proving that the computable numbers are uncountable after all, a contradiction.

The proof is informal. A person has to “get it” to be convinced that a certain machine or program is “logically” impossible.

7

Thanks for the replies—to what is a rather unfocused OP.

I woke up this morning wondering why I had become momentarily interested in the foundations of mathematics, and why I had gone to the trouble of creating a new topic just to pedantically and uncharitably pick apart some comments meant for a general audience, that didn’t pretend to be technically precise.

I think it’s that something in Väänänen’s comments rubbed me up the wrong way. Maybe two things: (a) naive foundationalism as the assumed philosophical motivation and orientation; and (b) the confusing and misleading nature of so many attempts at popularization.

Anyway, I did what I should have done originally and kept on reading beyond the part I quoted. The next contribution is interesting, in that it reframes incompleteness (and Gödel himself) as hopeful, rather than as an “unwelcome” fact that, alas, we just have to live with:

Rachael Alvir explains that Gödel maintained the dream of a formal logical system that could settle the continuum hypothesis and all other questions about sets, the building blocks of modern mathematics. His incompleteness theorems tell us that any such system, so long as it consists of a finite list of axioms, will give rise to new statements that are undecidable within that system. But he wondered about the possibility of an infinite succession of ever-larger axiomatic systems that could settle every question.

Gödel had no qualm with the claim that mathematics could prove or disprove every well-posed statement. Rather, Gödel took issue with Hilbert’s restrictive methods. Why should we believe there is a single, finite set of axioms, from which every truth will follow in a finite number of logical steps? Gödel believed that it was possible to redefine what we mean by a formal mathematical framework, or allow for alternative frameworks. He often discussed an infinite sequence of acceptable logical systems, each more powerful than the last. Every well-formulated mathematical question might be answerable within one of them.
[…]
For me, Gödel’s theorems do not show that mathematics is limited, but rather that mathematics is much wider and more powerful than Hilbert’s finitistic view.

— What Do Gödel’s Incompleteness Theorems Truly Mean?

And one question arising from that is what is the lowest level in the infinite sequence of acceptable logical systems that a theorem can be proven? (in the words of a friend of mine with more knowledge of mathematical foundations than me).

This is the question of reverse mathematics, apparently. I take the larger point to be that though this is in a sense foundational, i.e., related to foundations in mathematics, it abandons Hilbert’s ambition to find a single set of axioms on which the entire edifice of mathematics is built.

EDIT: But that’s not the best way of putting it, since abandoning Hilbert’s program was not a matter of choice. The better way of putting it is that investigating the foundations of mathematics did not have to be abandoned entirely just because it had turned out to be impossible to get consistency and completeness out of a finite set of self-evident axioms. In other words, reverse mathematics shows there’s a way of doing the foundations of mathematics without any naive foundationalism.

And according to Alvir, Gödel could see this possibility. Therefore Väänänen’s framing of incompleteness might owe too much to (1) a philosophy of mathematics that Gödel had perhaps already surpassed, and (2) a pessimism about incompleteness that Gödel himself had not endorsed in the original 1931 paper.

1 Like
8

Actually there’s two concepts here. Any “enumeration” of a countably infinite set never finishes. For instance, I can prove informally that the integers are countable this way:

0,1,-1,2,-2,3,-3,…

You can grasp that no integer is left out, but the process will never terminate. This is basically an informal program that will clearly go on running smoothly, ignoring limits of time and space. It prints a therefore computable sequence. Other arrangements of the integers would also prove that they are countable. You just need at least one.

But imagine ten thousand lines of Python code, with lots of loops and branches. Does it terminate ? You can follow it step by step, and maybe it will stop. But is there a short cut ? Not a one-size-fits-all short cut.

9

An interesting and very well expressed OP and so far out of my cliche wheelhouse I can’t see it from here. But still—a thought.

The relentless pragmatist inside me says “So what” to Godel. What difference does it make? I have the same response to Russell’s paradox. The quote is from this article.

In 1939, Wittgenstein held thirty-one weekly lectures on the Foundations of Mathematics (LFM)…When Wittgenstein asked [Turing] what harm should come from an inconsistency in a calculus, Turing replied that this harm might materialize later, when a bridge falls down that had been constructed with the help of this calculus. In the lecture, Wittgenstein did not give in. He recognized that Turing had formulated an important objection that would require special effort to refute. Wittgenstein remarked that this effort would have to touch upon the fundamental conception of scientific rationality and would be “the most important thing” he lectured about.

I find the whole issue fascinating, but as an engineer, I know that, if the bridge falls down, it’s because I was a mediocre student in my structural engineering classes.

1 Like
10

Yes, but Godel is the wrong target. The target should probably be people like Väänänen, quoted in the OP, who represent the incompleteness theorems as more wide-ranging and more disastrous than Godel himself believed—which is pretty much the point I was making in my follow-up post.

So I agree: Godel’s result may be profound, but it’s only profound regarding the nature of formal systems, which turned out to work quite differently from the way people assumed, viz., beyond a certain level of expressiveness, a formal system will have more true statements than can be proved from its own axioms. So the way people thought about the relationship between truth and provability had to change, and thus mathematics itself began to look different: we had to drop the idea that we could capture everything mathematics could do inside a complete system.

That’s quite interesting, at the very least, but you’re right that it doesn’t affect everyday mathematics.

I’m struggling with this analogy. Do you mean it won’t fall down because of a lack of piles and caissons but because the everyday practices have failed somehow, i.e., engineering standards, professional competence, etc.?

EDIT: Ah, it’s not an analogy. You’re pointing out that your use of mathematics in designing a bridge is unaffected by Godel.

11

I didn’t intend for him to be a target at all. As I wrote, I’m intrigued by this type of argument, but I try to put it into a context relevant to my life. That’s my standard philosophical approach to many of the issues we discuss. Sometimes that just doesn’t work, which I find interesting in itself.

Edit—It’s Turing’s reaction that surprises me, not anything Wittgenstein or Godel said.

Yes.

12

Hamming is pretty great on this stuff, as you may already know, and I think you’d relate to his approach.

13

Do you have a more specific reference? He was a pretty busy guy.

1 Like
14

I’ll try to dig out a few favorite passages too.

1 Like
15

More recently, we have had an intense study of what is called the foundations of mathematics - which in my opinion should be regarded as the top battlements of mathematics and not the foundations. It is an interesting field, but the main results of mathematics are impervious to what is found there - we simply will not abandon much of mathematics no matter how illogical it is made to appear by research in the foundations.
…
I hope that I have shown that mathematics is not the thing it is often assumed to be, that mathematics is constantly changing and hence even if I did succeed in defining it today the definition would not be appropriate tomorrow. Similarly with the idea of rigor - we have a changing standard. The dominant attitude in science is that we are not the center of the universe, that we are not uniquely placed, etc., and similarly it is difficult for me to believe that we have now reached the ultimate of rigor. Thus we cannot be sure of the current proofs of our theorems. Indeed it seems to me:
..
It is necessary to emphasize this. We begin with a vague concept in our minds, then we create various sets of postulates, and gradually we settle down to one particular set. In the rigorous postulational approach the original concept is now replaced by what the postulates define. This makes further evolution of the concept rather difficult and as a result tends to slow down the evolution of mathematics. It is not that the postulation approach is wrong, only that its arbitrariness should be clearly recognized, and we should be prepared to change postulates when the need becomes apparent.
..
Mathematics has been made by man and therefore is apt to be altered rather continuously by him. Perhaps the original sources of mathematics were forced on us, but as in the example I have used we see that in the development of so simple a concept as number we have made choices for the extensions that were only partly controlled by necessity and often, it seems to me, more by aesthetics. We have tried to make mathematics a consistent, beautiful thing, and by so doing we have had an amazing number of successful applications to the real world.
..
The idea that theorems follow from the postulates does not correspond to simple observation. If the Pythagorean theorem were found to not follow from the postulates, we would again search for a way to alter the postulates until it was true. Euclid’s postulates came from the Pythagorean theorem, not the other way. For over thirty years I have been making the remark that if you came into my office and showed me a proof that Cauchy’s theorem was false I would be very interested, but I believe that in the final analysis we would alter the assumptions until the theorem was true. Thus there are many results in mathematics that are independent of the assumptions and the proof.
..
How do we decide in a “crisis” what parts of mathematics to keep and what parts to abandon? Usefulness is one main criterion, but often it is usefulness in creating more mathematics rather than in the applications to the real world! So much for my discussion of mathematics.

1 Like
16

It looks really interesting, which is saying a lot coming from someone like me. I will definitely read it.

1 Like
17

Interestingly, Heisenberg had a unpublished paper that advanced a theory that says that language mirrors the uncertainty principle. When we try to describe a thing in more detail, fixing it systematically, we invariably face a trade off where we lose meaning as we gain precision. Works of poetry (or the philosophical poetry that was once popular) cover a lot of ground through their need to not be specific, whereas formalizations often lead to deflations, where—in our quest for precision—our descriptions start to be of the formalism itself.

I had originally considered that this might simply be a difficulty about the “bandwidth” of consciousness. A description that is too long cannot be pulled into the mind at once without being “compressed.” But I am not very hot on computational theories of mind anymore, and I think the phenomenology of dianoia/noesis (or intellectus/ratio) makes more sense of this.

The basic idea there is that the mind goes out to the diverse “many” (in the senses, in discursive reason, dialectic, etc.) and returns to a unifying one (the grasp of principles, understanding) in a sort of back and forth. And, because these are distinct moments phenomenologically and descriptively, they get codified as two distinct “faculties” of the intellect (although note that being specific has already caused us to collapse nuance and lose something). This looks something like the hermeneutical circle, although the image Dionysius the Areopagite uses differs because rest (the attainment of knowledge) lies in the center of the circle, with reason going out to the many in the circumference, and then moving back to the center in a unifying motion.

There is probably an easier formal example here with computable functions. If you stick to what is computable, you can, in theory, always get a decisive output, but you’re cutting off a great deal of what might be expressed. Likewise, if you want to stick to functions you can compute in a realistic amount of time, you need to keep adding on constraints on what can be “said.”

But there are also obviously changes in degree here and something like “phase transitions” that are large leaps, as between the computable and non-computable, or between the strict univocity of formalism and the analogy the dominates natural language.

1 Like
18

Väänänen’s comments concerning expressive power against weak effectiveness appear unrelated to Gödel. A separate issue. That’s odd—a non sequitur.

Now he is a serious logician. So I wonder how much of what is here is a misappropriation for pop effect.

We have undecidability and incompleteness on the one side; and that equation of “effectiveness” and expressive power on the other. It’s as if he were somehow equating expressive power and lack of decidability. Isn’t that an equivocation?

And drawing in Heisenberg is most unfortunate. The Uncertainty Principle is exactly, mathematically, specified:

image
image288×144 2.63 KB

Perhaps the article sacrificed precision for accessibility; if so, for me at least, it failed. A non sequitur, a failed analogy and an equivocation don’t do much to help understand Gödel.

1 Like
19

Of course it is, as is Schrödinger’s wave equation. But it’s the implications for the nature of objective reality that are profound. Why do the books about it have subtitles such as ‘The Struggle for the Soul of Science’ (1) or ‘The Great Debate about the Nature of Reality’? (2) What is at issue?

20

Hilbert’s intention was to find the axiom set from which all mathematical truths could be derived.

Godel showed that given any consistent axiom set, there will be mathematical truths that are true but unprovable with those axioms. An axiom set that’s consistent will be incomplete or, contrapositively, if an axiom set is complete, it’ll be inconsistent.

I believe you’re misattributing human haphazardness to mathematical haphazardness, the latter being an oxymoron. We quite often see mathematicians in the throes of awe and wonder when they find what they call a “deep connection” between different mathematical objects. My own such moment came when I was told that we could represent a straight line with an equation. A minor mathematical truth but still quite mind-blowing at that time, kind courtesy of a musca domestica; Descartes isn’t famous for cleanliness. Historically arithmetic was considered distinct from geometry (re Quadrivium: Geometry, Arithmetic, Astronomy, Music).