Polytropy

Here is another in the recent spate of mathematics posts. I take up now, as I did in my last post, some material that I had originally drafted for the first post in this series.

Whenever it has been designated for its own post, material can grow, as has the material of this post in the drafting. Large parts of this post are taken up with

1. the notion (due to Collingwood) of criteriological sciences, logic being one of them;

2. Gödel’s logical theorems of completeness and incompleteness.

I have defined mathematics as the science whose findings are proved by deduction. This definition does not say what mathematics is about. We can say however what logic is about: it is about mathematics quâ deduction. This makes logic a criteriological science, since it seeks, examines, clarifies and limits the criteria whereby we can make deductions. As examples of this activity, Gödel’s theorems are that

• everything true in all possible mathematical worlds can be deduced;

• some things true in the world of numbers can never be deduced;

• the latter theorem is one of those things.

The present post has the following sections.

Entailment

My definition of mathematics is like that of Bertrand Russell in The Principles of Mathematics, whereby the subject consists of deductions in the sense of propositions “p implies q.” However, Russell’s definition leaves us out, as would a definition of physics as consisting of the laws of nature.

Kinds of Science

We can classify sciences as empirical, normative, or criteriological, according as they examine how things are, how we want them to be, or how we want ourselves to be. If this classification is exhaustive, then mathematics is empirical; but it is also in a class by itself.

As scientists, we judge whether we achieve the goals that we set for ourselves in our work. Thus we have freedom of will, and criteriological sciences study this freedom.

Physicist Sabine Hossenfelder denies our freedom, as in a video, “You don’t have free will, but don’t worry,” released during the composition of the present post. The video comes with this summary:

In this video I explain why free will is incompatible with the currently known laws of nature and why the idea makes no sense anyway. However, you don’t need free will to act responsibly and to live a happy life, and I will tell you why.

Raymond Smullyan has a good account of why there is free will, in his dialogue “Is God a Taoist?” reprinted

• in Douglas R. Hofstadter and Daniel C. Dennett (editors), The Mind’s I: Fantasies and Reflections on Self & Soul (Basic Books, 1981);

• by me on this blog.

I shall be looking below at Hofstadter’s ideas as expressed in Gödel, Escher, Bach (Basic Books, 1979).

Perhaps Hossenfelder would say Smullyan’s is an argument for responsibility, not freedom. To me it makes no sense to speak of responsibility without freedom, as I said in “Antitheses,” when critiquing Hossenfelder’s 2016 blog post, “Free will is dead, let’s bury it.” By my account now, Hossenfelder is effectively denying that there can be such sciences as history and logic. She might tell me that those sciences do not do what I say they do, or that my understanding of freedom is not hers. My understanding of physics is that it studies things insofar as they do not have free will; thus physics cannot discover an absence of freedom.

Mathematics and Logic

Mathematics is empirical, in its own peculiar way; logic is criteriological, for helping us get straight what we are trying to do with it.

Gödel’s Theorems

Gödel’s one completeness theorem and two incompleteness theorems tell us what we can and cannot hope to prove in mathematics.

Logic of Mathematics

Logic has allowed mathematics to come into its own as the deductive science.

---

Entailment

Mathematics proves that certain conclusions are necessary conditions of certain assumptions. The other way around, the assumptions are sufficient conditions for the conclusions. In other words, certain postulates entail certain theorems; symbolically, for some instances of p and q,

“p implies q.”

Such an account of mathematics resembles Bertrand Russell’s, in The Principles of Mathematics:

Pure Mathematics is the class of all propositions of the form “p implies q,” where p and q are propositions containing one or more variables, the same in the two propositions, and neither p nor q contains any constants except logical constants. And logical constants are all notions definable in terms of the following: Implication, the relation of a term to a class of which it is a member, the notion of such that, the notion of relation, and such further notions as may be involved in the general notion of propositions of the above form.

Timothy Gowers makes that quotation of Russell, along with one more sentence, to be taken up later, in the Preface of the big book called The Princeton Companion to Mathematics (Princeton University Press, 2008; xx + 1034 pages). I referred to this book in

• the blog post called “Şirince January 2018,” about time spent in the Nesin Mathematics Village;

• the blog page called, and about, “Primes in Arithmetic Progressions”; that page was the subject of the post called “LaTeX to HTML.”

According to Gowers himself,

The Princeton Companion to Mathematics could be said to be about everything that Russell’s definition leaves out.

Russell’s book was published in 1903, and many mathematicians at that time were preoccupied with the logical foundations of the subject. Now, just over a century later, it is no longer a new idea that mathematics can be regarded as a formal system of the kind that Russell describes, and today’s mathematician is more likely to have other concerns. In particular, in an era where so much mathematics is being published that no individual can understand more than a tiny fraction of it, it is useful to know not just which arrangements of symbols form grammatically correct mathematical statements, but also which of these statements deserve our attention.

In short, the book gives an idea of what mathematics is about.

Kinds of Science

There is a distinction between descriptive and prescriptive science; alternatively, between empirical science and normative science. I have written about a third kind of science, which Collingwood calls criteriological.

1. Empirical science is about how things are.

2. Normative science is about how we try to make things.

3. Criteriological science is about how we try to make ourselves.

The empirical sciences are the natural sciences: the sciences of things that are natural. Natural things cannot be any other way than they already are. At least, they are not trying to be any other way; or if they are, as when they are animals as studied by Tinbergen and colleagues, then they don’t know it.

Engineering and medicine are normative sciences, because they study how to make things be some way, according to the aims of those persons who want them to be that way.

A criteriological science like aesthetics or jurisprudence studies our aims as such. Having itself an aim, which involves being true or correct, a criteriological science comes under its own purview.

One may want to emphasize that a normative science not only studies how to do things, but also does them. One may then call the science an art or, if that usage is old-fashioned, a skill.

Any scientific pursuit may have empirical, normative, and criteriological aspects. It will have the last when establishing a code of conduct for itself.

A reason for distinguishing the kinds of science is the hope of doing better what we do, when we know what it is.

Richard Feynman tells a story about confirmation bias in replications of the Millikan Oil Drop Experiment. When researchers followed Millikan’s example in inferring from their experimental data a unit of charge (namely the charge on a so-called electron), they threw out results that were too far from Millikan’s, until they understood that his were off.

The story is currently quoted on Wikipedia. Feynman continues it, in “Cargo Cult Science,” as reprinted in “Surely You’re Joking, Mr. Feynman!” (Norton, 1985):

But this long history of learning how to not fool ourselves—of having utter scientific integrity—is, I’m sorry to say, something that we haven’t specifically included in any particular course that I know of. We just hope you’ve caught on by osmosis.

If the ethics of physics is indeed not taught in physics courses, presumably this is because it is not strictly part of physics. Physics is a natural science; ethics is not. However, every scientist needs to be ethicist enough to understand Feynman’s advice:

The first principle is that you must not fool yourself—and you are the easiest person to fool. So you have to be very careful about that. After you’ve not fooled yourself, it’s easy not to fool other scientists. You just have to be honest in a conventional way after that.

I would like to add something that’s not essential to the science, but something I kind of believe, which is that you should not fool the layman when you’re talking as a scientist.

I quoted that last sentence and more in “Be Sex Binary, We Are Not,” because I thought Feynman’s advice was being ignored in a Scientific American blog post.

All of this puts me in mind of Plato’s Gorgias dialogue, in which the title character agrees with the account of his profession that Socrates offers (455A; Lamb’s translation in the Loeb Classical Library; emphasis mine):

And so the rhetorician’s business is not to instruct a law court or a public meeting in matters of right and wrong, but only to make them believe; since, I take it, he could not in a short while instruct such a mass of people in matters so important.

Gorgias boasts that if a town is hiring a physician, then a rhetorician can pad his résumé better than any actual physician, and get the job; however, teachers of rhetoric such as himself should not be blamed when their students misuse what they have learned (456A–D). Socrates presses him (459B–C):

Then the case is the same in all the other arts for the orator and his rhetoric: there is no need to know the truth of the actual matters, but one merely needs to have discovered some device of persuasion which will make one appear to those who do not know to know better than those who know.

Gorgias again boasts in reply (459C):

Well, and is it not a great convenience, Socrates, to make oneself a match for the professionals by learning just this single art and omitting all the others?

Socrates asks if the rhetorician is as ignorant of justice and goodness as he is of medicine and other arts. Gorgias is reluctant to admit it, but says that the student of rhetoric will have to learn the difference between right and wrong (460A). But now Gorgias has contradicted himself, since nobody can do wrong who knows what it is, and yet Gorgias has admitted that his students may do wrong.

Everything that we do, we do initially for its own sake, because we cannot know what will come of it. As infants we have to utter sounds at random before we can learn to control them and use them to get what we want. We do research out of pure curiosity, before learning how the research can serve other interests.

Then one can find ways to abuse research, or one’s standing as a scientist. “For example,” says Feynman (loc. cit.),

I was a little surprised when I was talking to a friend who was going to go on the radio. He does work on cosmology and astronomy, and he wondered how he would explain what the applications of this work were. “Well,” I said, “there aren’t any.” He said, “Yes, but then we won’t get support for more research of this kind.” I think that’s kind of dishonest.

“Kind of”?

Logic

Logic aims to provide, for science in general, and especially mathematics, a code of conduct that is agreeable to the practitioners: a code not for dealing with the public, but for establishing theories and, in mathematics, proving theorems. That is what I would say, though perhaps the current Wikipedia article called “Conceptions of logic” does not really cover this conception.

In the broad sense, “logic is the analysis and appraisal of arguments,” as the main Wikipedia article on the subject says. I would emphasize that the analysis and appraisal are of arguments as such, arguments quâ arguments. These are intended to have a certain effect, and they may succeed or fail in achieving this end, according to the people making the arguments.

For example, in Propositions 5, 6, 18, and 19 of Book I of the Elements, Euclid proves that, in a triangle,

1. equal sides subtend equal angles,

2. equal angles are subtended by equal sides,

3. the greater side subtends the greater angle,

4. the greater angle is subtended by the greater side.

The last of these follows from the first and third by pure logic, as Euclid’s proof reflects; but so does the second, and it is not needed for the proof of the third. Logically then, Euclid could have dispensed with his proof of the second. If logic were normative, it might convict Euclid of the style error of proving what didn’t need proof. As a criteriological science, logic can only ask whether Euclid would accept style advice on this point.

Logic is called that and not logics, although there are other sciences called ethics and physics, because Aristotle wrote collections of books called, respectively, Ethics and Physics, but not a collection of “logics”; he wrote Analytics instead. Collingwood points this out in a footnote on the first page of An Essay on Metaphysics (Oxford, 1940). He accounts for logic and ethics as criteriological sciences in Chapter X (pp. 108–9; bold emphasis mine):

… the Greeks … constructed a science of theoretical thought called logic and a science of practical thought called ethics. In each case they paid great attention to the task of defining the criteria by reference to which theoretical and practical thought respectively judge of their own success. In view of this … these sciences have been traditionally called normative sciences. But the word ‘normative’ may prove misleading … as if it were for the logician to decide whether a non-logician’s thoughts are true or false and his arguments valid or invalid, and for the student of ethics to pass judgement on the actions of other people as having succeeded or failed in their purpose. This suggestion is incorrect. The characteristic of thought in virtue of which a science of thought is called normative consists … in the necessity that in every act of thought the thinker himself should judge the success of his own act … I propose to substitute for the traditional epithet ‘normative’ the more accurate term ‘criteriological’.

The chapter is called “Psychology as the Science of Feeling,” because that is what psychology was created to be, when people recognized that, not being self-critical, feeling was not thought and therefore must be studied by a science different from logic and ethics. Psychology is non-criteriological, and you can understand this, even if you think that everything in nature behaves “teleologically.” Things can have purposes or ends, but if the things don’t know this, then you won’t be studying them criteriologically.

Collingwood traces the origin of psychology to the sixteenth century, but gives no details. The Oxford English Dictionary traces it more specifically to sixteenth-century Germany, and in particular to Melanchthon, though the earliest recorded use of the term in English is from a 1693 translation of Steven Blanchard’s Lexicon Medicum. Wikipedia spells the author’s surname as Blankaart, but traces the word “psychology” to a Croatian humanist, Marko Marulić, author of Psichiologia de ratione animae humanae, 1510–17.

Collingwood’s next chapter is called “Psychology as the Pseudo-science of Thought,” because a program to study thought empirically can only be a mistake or a fraud. Such a program was nonetheless urged in the eighteenth century, and possibly for the good reason that logic and ethics had ceased being strictly criteriological, but had become normative in the sense of imposing standards from outside (pp. 114–5):

It might very well be true that a revolt against the old logic and ethics had been desirable and had proved beneficial; for it might very well be true that people who professed those sciences had misunderstood their normative character, and had claimed a right of censorship over the thoughts and actions of other people; and for the sake of scientific progress such tyranny might very well have to be overthrown. When it is a case of overthrowing tyranny one should not be squeamish about the choice of weapons. But the tyrannicide’s dagger is not the best instrument for governing the people it has liberated.

I have elsewhere criticized Collingwood’s violent language, along with my own grandfather’s writing that “we were too squeamish” to fight the Vietnam War properly.

I find in a recent Guardian Weekly an example where a criteriological science, here economics, is treated as normative. Given courtroom evidence, people were asked to make a case, either for the plaintiff or the defense. Then they were asked to predict what the judge had done. According to Tim Harford in “Feeling is believing” (Guardian Weekly vol. 203 no. 14, 18 September 2020; online as “Facts v feelings: how to stop our emotions misleading us”),

Their predictions should have been unrelated to their role-playing, but their judgment was strongly influenced by what they hoped would be true.

Psychologists call this “motivated reasoning”. Motivated reasoning is thinking through a topic with the aim, conscious or unconscious, of reaching a particular kind of conclusion.

I have said it before: all reasoning is motivated reasoning. We engage in it for a reason! In the present “real court case about a motorbike accident,” it was for the judge to decide what “should have” happened; it was for the experimental subjects of Linda Babcock and George Loewenstein to argue, hypothetically, about what “should have” happened; it was not for the two economists to say what those subjects “should have” decided.

Logic has been wrongly made normative if used to “correct” Mick Jagger for singing,

The pedant may assert that what Jagger is “really” saying here, “logically,” is,

That is not what he is saying. He is saying what he means, or what his persona as rock-n-roll singer means; and what that persona means, in “standard” English, is,

And this is only an approximate translation. The full translation, into English, would just be the original lyric, which is already in English.

Mathematics and Logic

In the address that I discussed in “What Mathematics Is,” Euphemia Lofton Haynes identifies logic and mathematics; but there’s a difference. If mathematics is one of the sciences fitting the three-part classification above, it is a descriptive or empirical science. However, again, logic is the criteriogical science of how sciences justify their findings.

My specialty within mathematics is model theory, which is said to be a part of mathematical logic. It is just mathematics though, albeit mathematics made possible by the development of symbolic logic.

A senior colleague in model theory once suggested to me that logic is about something, namely reason, as physics is about the physical world; but mathematics as such is about nothing. This sounded reasonable; however, when I asked this person about it in a later year, he did not particularly remember what he had said (and this is why I am not naming him).

Logic is associated with mathematics, because mathematics is the science that logic has best illuminated. I have written about Wigner’s notion of an “unreasonable effectiveness of mathematics in physics.” One might speak also of the unreasonable effectiveness of logic in mathematics.

I ended “What Mathematics Is” by saying that logically possible worlds are worlds that can be deduced from postulates. This was glib. The properties of a mathematical world are deduced from the postulates of that world. The properties cannot be observed in the conventional sense, by sense, such as hearing, seeing, and touching. To say that a mathematical world exists in the first place is to say that its postulates are consistent; and this we can prove, only by assuming the consistency of some other postulates.

Today those other postulates are normally the Zermelo–Frankel axioms of set theory, with the Axiom of Choice, composing the collection called ZFC. However, by Gödel’s Second Incompleteness Theorem, ZFC does not entail its own consistency, if it is consistent.

Gödel’s Theorems

I have already reviewed both of Gödel’s incompleteness theorems. I do it here now, somewhat differently: usually more tersely, but sometimes in more detail, or in another way.

Gödel’s First Incompleteness Theorem is that there is not, and cannot be, an algorithm for identifying all true statements about numbers. By numbers I mean counting numbers: 1, 2, 3, and so on. By a statement about them, I mean, technically, a formula that has no free variables, in a sense to be made more precise later. Meanwhile, in our context, a formula is an expression built up from polynomial equations by finitely many applications of the logical operations of

• conjunction (forming p ∧ q, “p and q,” from p and q);

• negation (forming ¬p, “not p,” from p);

• disjunction (forming p ∨ q, “p or q”; but this is already ¬(¬p ∧ ¬q));

• implication (forming p ⇒ q; but this is ¬p ∨ q);

• universal quantification (forming ∀x p, “For all x, p,” from p and a variable x).

• existential quantification (forming ∃x p, “For some x, p”; but this is ¬∀x ¬p).

In our polynomial equations, the only parameter is 1. However, from 1 we can build up the other counting numbers as the sums 1 + 1, 1 + 1 + 1, and so on, these themselves being polynomials, namely constant polynomials.

The definition of truth is fairly straightforward. An equation of constant polynomials is true or false in the obvious sense; an equation of arbitrary polynomials is true if it is true for all values of its variables; the definition of truth for more complicated formulas follows accordingly.

There is a stronger notion. A formula is logically true if it is true in the sense above, regardless of how values are assigned to variables, sums, and products. The formula

is logically true. The statement

is true, but not logically true, since it is false if every variable, and in particular x and y, can take only the same value. However,

is logically true.

There are algorithms for generating some true statements about numbers:

1. Start with some statements known to be true of numbers: these statements are now postulates.

2. Derive new formulas by means of some rules of inference that are known to preserve truth. Such rules will normally include

   • modus ponens: from p and p ⇒ q, derive q;

   • generalization: from p, derive ∀x p;

   • logical axioms: from nothing at all, derive

     • tautologies, such as p ∨ ¬p (these are the logically true formulas that involve no quantifiers);

     • other formulas that are logically true, such as

       • laws of equality such as x = x,

       • ∀x p ⇒ p(c), where p(c) is the result of replacing each free occurrence of x in p with c, this being a constant polynomial.

The derived formulas that are statements are theorems, because they have proofs, which show how to derive them from the postulates by means of the rules of inference. The theorems constitute a theory of the counting numbers.

We are now using the word “theorem” in two ways.

1. Gödel’s theorems are logical theorems.

2. The statements about numbers that are theorems in the sense just defined are mathematical theorems.

One may distinguish between

• the logical axioms, which derive mathematical theorems from nothing;

• the other rules of inference, which have to start with something.

The logical axioms and the rules of inference then constitute a proof system. Before the incompleteness theorems came Gödel’s Completeness Theorem, whereby there are proof systems that yield every logically true statement as a theorem.

We shall henceforth assume that our proof system is complete in this sense.

Gödel’s First Incompleteness Theorem is now that from no postulates can all true statements about numbers be derived as theorems.

We are not allowed to take all of those true statements as postulates in the first place. I meant to suggest this by saying that our postulates must be known to be true of the counting numbers. In particular, though the postulates may be infinitely numerous, there has to be a mechanical rule for writing them down. In technical terminology, to be made a bit more precise later, the postulates have to be recursively enumerable.

The proof of Gödel’s First Incompleteness Theorem relies on the possibility of turning every formula into a number itself. This number is the Gödel number of the formula. Strictly, it is the set of Gödel numbers of our postulates that has to be recursively enumerable.

Instead of assigning to every formula a number, we could assign a set; then, by Gödel’s method, we could prove that no theory of sets, such as ZFC, is complete. The method applies to any mathematical structure whose elements we can manipulate in a way that mimics how we form postulates and apply rules of inference to them.

Assigning Gödel numbers to formulas is then like assigning letters to sounds, the way the Phoenicians did in creating the alphabet.

A better metaphor is turning grammatical sentences into nouns, as with use of quotation marks or a determiner such as “that” or “whether”:

• Are you coming?

• I said, “Are you coming?”

• I want to know whether you are coming.

• I know that you are coming.

We assign Gödel numbers to formulas quâ strings of symbols, and we can recover the formulas from the numbers. In the same way, we assign Gödel numbers to lists of formulas. Such a list could be a proof. Whether it is a proof is something that can be recognized from the Gödel number. Saying that a certain formula about numbers has a proof now means saying that a number with a certain property exists; that the formula has no proof means the number doesn’t exist.

In describing logical axioms, I said p(c) was the result of replacing each free occurrence of x in p with c. The rules are:

1. Every occurrence of a variable in a polynomial equation is free.

2. Being a free occurrence in a formula is preserved when the formula is negated or conjoined with another, but not when the variable is quantified.

Thus in the formula x = x ⇒ ∃x x ⋅ x = x, the first two occurrences of x are free; the remaining four are not free. To say that a variable is free in a formula is to say that it has a free occurrence in the formula; it may also have a non-free occurrence, though we can usually arrange for this not to happen, as for example by writing the formula above as x = x ⇒ ∃y y ⋅ y = y.

A formula with a free variable is effectively a predicate with unspecified subject. Given a formula p with a free variable, we can take any counting number a and, using Gödel numbers, form the statement that p(a) has no proof. We shall be interested in the case where a is the Gödel number of p.

Another level of abstraction is possible. We write the Gödel number of any formula p as ⌜p⌝. There is a formula φ with one free variable such that, for all statements s,

There is now a formula ψ with a free variable such that, for all formulas p with a free variable,

If we think of forming the Gödel number of a formula as quoting the formula, then ψ is the predicate, “yields an unprovable statement when predicated of the quotation of itself.”

We can predicate ψ of the quotation of itself in this sense, forming the statement ψ(⌜ψ⌝). If we write this statement as σ, then it is also ¬φ(⌜σ⌝). Briefly, σ says, “I have no proof.” It doesn’t really have a first-person pronoun though; what σ says is,

“Yields an unprovable statement when predicated of the quotation of itself” yields an unprovable statement when predicated of the quotation of itself.

Upon reflection, we see that the particular predication that this statement is about—which is a predication that has no proof—is just the statement σ itself. If σ were false, then φ(⌜σ⌝) would be true, and thus σ would be a theorem. Since theorems are true, σ must be true; but then it cannot be a theorem. This proves Gödel’s First Incompleteness Theorem.

My use of the quotation of predicates is based on the dialogue that begins on page 431 of Douglas R. Hofstadter’s book of xxii + 778 pages called Gödel, Escher, Bach: An Eternal Golden Braid (Basic Books, 1979). The dialogue is called “Air on G’s String,” and in it, the Tortoise recounts to Achilles the receiving of an “obscene” phone call. Written out and punctuated correctly, what the caller says is,

“Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.

It’s a way of saying “I am lying,” without actually saying “I.” It seems I have remembered it from reading Hofstadter’s book when the paperback edition came out, in 1980, when I turned fifteen.

I enjoyed reading the book then. Its main benefit may have been to lead to me to learn more about Zen Buddhism, first through Reps and Senzaki, Zen Flesh, Zen Bones (1957).

I cannot have understood Gödel’s Theorem from Hofstadter. I am still trying to understand it now. In graduate school, a professor told me he hoped Hofstadter himself had not understood Gödel’s Theorem, because teaching it with a book like Hofstadter’s would be unconscionable.

I am not naming the professor, because I may not have thoroughly understood and properly recalled his meaning. For the same reason, I am not naming the tutor who told me, in my freshman year at college, that Gödel’s Theorem need not rely on self-reference, contrary to Hofstadter’s evident belief.

That tutor may have been alluding to how Gödel’s Theorem derives from the Halting Problem, as follows.

In principle we can make a list of all computer programs that can be set to work on single numbers as input. We can denote the nth program on the list by {n}. Working on a number k, this program may halt and produce some output, or it may never stop running. For example, the program may seek the least twin prime that is greater than k; if the Twin Prime Conjecture is false, and k is large enough, then the program will never halt.

The set of all numbers at which a given program halts is, by definition, a recursively enumerable set. For example, the set of twin primes is recursively enumerable, whether it is finite or infinite. We can list the elements of a recursively enumerable set in stages. At stage k, on all numbers that do not exceed k, we have run the program for k steps, and we have written down the numbers for which the program has halted so far.

There is a recursively enumerable set of numbers whose complement is not recursively enumerable. This means, by definition, that the original set is not recursive. I looked at this set at the end of “Hypomnesis,” which is about a logic meeting in Delphi in 2017; but let me define the set again here. There is a program that does at k what {k} does. This program must be {m} for some m. But then the set of numbers where {m} does not halt cannot be recursively enumerable; for if it were, then it would be, for some k, the set of numbers where {k} halted. In this case {k} would halt at k if and only if it did not.

For each number k, there is a statement p_k that the program {k} does not halt at k. Then the set of k for which p_k is true is not recursively enumerable. Hence also the set of Gödel numbers ⌜p_k⌝ of the statements p_k that are true is not recursively enumerable. However, the set of Gödel numbers of all of the statements p_k is recursively enumerable. Therefore the set of Gödel numbers of all true statements about the counting numbers cannot be recursively enumerable.

Now we have proved Gödel’s First Incompleteness Theorem a second time. The second proof does not involve a proof system. In particular, it does not give us a particular statement that cannot be proved; it just shows that such a statement will always exist, regardless of our proof system. Much less does the proof give us a statement that says, “I cannot be proved.” The proof still uses self-reference, in the sense of applying a program to its own number. It doesn’t really need Gödel numbers in the precise sense; however, the whole notion of a computer program is an analogue of Gödel numbering.

After the dialogue of the Tortoise and Achilles that I have referred to, Hofstadter has a chapter called “On Formally Undecidable Propositions of TNT and Related Systems.” The title comes from that of Gödel’s 1931 paper by substitution of TNT (“typographical number theory”) for Principia Mathematica. Hofstadter says his chapter will be “more intuitive” than Gödel’s article, and

I will stress the two key ideas which are at the core of [Gödel’s] proof. The first key idea is the deep discovery that there are strings of TNT which can be interpreted as speaking about other strings of TNT; in short, that TNT, as a language, is capable of “introspection”, or self-scrutiny. This is what comes from Gödel-numbering. The second key idea is that the property of self-scrutiny can be entirely concentrated into a single string; thus that string’s sole focus of attention is itself. This “focusing trick” is traceable, in essence, to the Cantor diagonal method.

We used the diagonal method to produce a recursively enumerable set that is not recursive. Indeed, we can think of a table in which the entry in row k and column m is

• 1, if {k} halts at m;

• 0, otherwise.

Each row then is a string of 0s and 1s. The string of entries on the diagonal is also row m, if again {m} is the program that does at each k what {k} does. The string that we get from that row by interchanging 0 and 1 can therefore occur as no row; thus there is no program that halts precisely where {m} does not.

Hofstadter continues:

In my opinion, if one is interested in understanding Gödel’s proof in a deep way, then one must recognize that the proof, in its essence, consists of a fusion of these two main ideas. Each of them alone is a master stroke; to put them together took an act of genius. If I were to choose, however, which of the two key ideas is deeper, I would unhesitatingly pick the first one—the idea of Gödel-numbering, for that idea is related to the whole notion of what meaning and reference are, in symbol-manipulating systems. This is an idea which goes far beyond the confines of mathematical logic, whereas the Cantor trick, rich though it is in mathematical consequences, has little if any relation to issues in real life.

One could question Hofstadter’s (or anybody’s) presumption to

• understand Gödel’s proof “in a deep way,”

• be able to recognize a master and a genius,

• know all about “real life.”

For one thing, mathematics is a part of real life, as opposed to illusory life, unless indeed one harbors illusions about what one knows, or tries to create illusions in others’ minds about what one knows.

In his article “Gödel’s Theorem” in the Princeton Companion, Peter J. Cameron also says that the theorem is based on two ideas. Cameron’s first idea is Hofstadter’s, which is Gödel numbering; but Cameron’s second is just self-reference, as in the forming of the statement ψ(⌜ψ⌝).

I don’t know that either person’s “two ideas” are really two. Gödel numbering is an embedding of the logic of arithmetic in arithmetic itself. Embeddings as such are everywhere in mathematics: there’s the embedding of the plane in space for example, or of the counting numbers in the integers or the positive rational numbers. Gödel numbering is special for letting arithmetic be about not just numbers, but itself. Our second proof of Gödel’s theorem seemingly used diagonalization in place of Gödel numbering; but a diagonal argument relies on the possibility that rows and columns of the same table can “speak” about one another in the sense of bearing the same serial number. Moreover, the numbering of programs is like Gödel numbering in the sense that we can mechanically obtain the program {k} from k; this is why there can be a statement, in our formal sense, that {k} does not halt at k.

It remains to establish Gödel’s Second Incompleteness Theorem, that the consistency of our postulates for the numbers is not a theorem. The consistency is a statement though, namely the statement that Λ has no proof, where Λ is a logically false statement, such as ∃x x ≠ x.

We want then to show that

is not a theorem, since this is the statement that Λ has no proof. We already know that

is not a theorem, where σ is ψ(⌜ψ⌝), where ψ(⌜p⌝) is ¬φ(⌜p(⌜p⌝)⌝), so that ¬φ(⌜σ⌝) is just σ. Thus it is enough to show that the implication

is a theorem. There is a proof of this statement from

and of this statement from

This last statement is a theorem, regardless of what σ is. So Gödel’s Second Incompleteness Theorem holds. (The sketch of the proof is based on that of C. Smorynski in “The Incompleteness Theorems” in Jon Barwise, editor, Handbook of Mathematical Logic, Elsevier, 1977.)

As telling us what we can and cannot prove in mathematics, Gödel’s Completeness Theorem and First Incompleteness Theorem are theorems of logic. We can turn the latter into a mathematical theorem, and this is how the Second Incompleteness Theorem is proved.

Logic of Mathematics

In the first section, “Entailment,” I left off the last sentence of Gowers’s quotation of Russell:

In addition to these [propositions of the form “p implies q”], mathematics uses a notion which is not a constituent of the propositions which it considers, namely the notion of truth.

That was in 1903, Russell having been born in 1872; Gödel would be born in 1906.

What Russell says about truth in the book is provoked by a paradox concerning the rule of modus ponens that Lewis Carroll presented in the dialogue, “What the Tortoise Said to Achilles.” Along with his own dialogues involving the same characters, Hofstadter will reprint Carroll’s dialogue in Gödel, Escher, Bach. The paradox is that modus ponens is about implication, but is also itself an implication. It is that p and the implication p ⇒ q together imply q. If we now write the rule as the same kind of implication, namely

then, to use the rule, we need another rule, that p and p ⇒ q and the rule just given together imply q: in short,

But now this is not enough. If we define propositions p_n recursively so that

then all of these together cannot compel us to accept q.

That is so, I would say, because logic is not normative, but criteriological. It cannot tell us what we must do; it observes what we do do. One thing we do is draw conclusions that accord with the rule called modus ponens.

In the first proposition of the first book of the Elements, given a segment ΑΒ and the possibility of drawing circles, Euclid constructs a triangle ΑΒΓ in which ΑΓ = ΑΒ and ΒΓ = ΒΑ. Since ΑΒ and ΒΑ are the same segment, we know that ΑΓ = ΒΓ. Thus the sides are all equal to one another, and therefore, by definition, the triangle is equilateral.

The sides ΑΓ and ΒΓ are equal to one another, because

• each is equal to the same side, written indifferently as ΑΒ or ΒΑ;

• equals to the same are equal to one another.

This is only an explanation of something that we already know.

We have to know too that the point Γ exists in the first place as an intersection of the circles, each of which has one of Α and Β as center and passes through the other.

Some modern readers complain that Euclid applies no explicit rule whereby those circles must intersect. Such readers are like the visitors that Ruth Fuller Sasaki describes in “Zen: A Method for Religious Awakening” (1959; reprinted in The World of Zen, edited by Nancy Wilson Ross, 1960; I bought the book in 1981):

How many hours have I not spent in my Kyoto temple listening to people, usually Americans recently come to Japan, tell me just what Zen is. To such visitors I have nothing to say; to those who do not understand, I am always searching for a way to give a clue to what Zen is about.

Mathematicians such as Timothy Gowers are keen on searching for a way to give a clue to what mathematics is about. To me the most important clue lies in a chapter of Gowers’s little book called Mathematics: A Very Short Introduction (Oxford, 2002; xiv + 133 pages). Chapter 3 is called “Proof,” and there Gowers observes,

the steps of a mathematical argument ean be broken down into smaller and therefore more clearly valid substeps. These steps can then be broken down into subsubsteps, and so on. A fact of fundamental importance to mathematics is that this process eventually comes to an end. In principle, if you go on and on splitting steps into smaller ones, you will end up with a very long argument [that] starts with axioms that are universally accepted and proceeds to the desired conclusion by means of only the most elementary logical rules (such as ‘if A is true and A implies B then B is true’).

I would propose a couple of adjustments.

1. Some axioms, such as the Axiom of Choice, are not universally accepted. If you prove a proposition P using this axiom, then everybody will agree that at least you have proved the proposition that AC implies P.

2. Possibly not everybody will agree, even then, if for example you have used the logical rule of the excluded middle (“either Q or not-Q”). Intuitionism rejects this rule. But an Intuitionist should still be able to tell whether an argument is correct within a system that does allow use of the rule of the excluded middle. The Intuitionist will then prefer to find an argument, a “constructive” argument, that does not need this rule, and a mathematician of any school can confirm the construction.

Gowers goes on to say:

What I have just said in the last paragraph is far from obvious: in fact it was one of the great discoveries of the early 20th century, largely due to Frege, Russell, and Whitehead (see Further reading). This discovery has had a profound impact on mathematics, because it means that any dispute ahout the validity of a mathematical proof can always be resolved …

… the fact that disputes can in principle be resolved does make mathematics unique. There is no mathematical equivalent of astronomers who still believe in the steady-state theory of the universe, or of biologists who hold, with great conviction, very different views about how much is explained by natural selection, or of philosophers who disagree fundamentally about the relationship between consciousness and the physical world, or of economists who follow opposing schools of thought such as monetarism and neo-Keynesianism.

I have become an exponent of this idea, that there is one field of human endeavor where all disputes can be settled amicably.

My wife used the idea in her courtroom defense against the accusation of being a terror-propagandist.

I would summarize the idea as being that mathematics is the deductive science. Gowers doesn’t say it that way, though he uses the word deduction:

No mathematician would ever bother to write out a proof in complete detail—that is, as a deduction from basic axioms using only the most utterly obvious and easily checked steps.

It seems to me that everybody who learns anything about mathematics should learn its deductive nature. Otherwise they haven’t really learned mathematics. The idea of deduction will however need building up over the years of one’s education. It has already needed building up in the millenia since Euclid.