Polytropy

Preface

This attempt at exposition of Gödel’s Incompleteness Theorem was inspired or provoked by somebody else’s attempt at the same thing, in a blog post that a friend directed me to. I wanted in response to set the theorem in the context of mathematics rather than computer science.

As I wrote in an email to that friend (on November 18, 2020),

I’ve written two long blog posts on Gödel, in 2018 and a month ago. They are about a lot of related stuff too, as is usual for my posts.

The present post is independent of those and may be simpler then they are; at any rate, the approach is different. I prepared the post by the method discussed in “LaTeX to HTML.” Details are at the end, after the bibliography.

Summary

Gödel’s Incompleteness Theorem is about the logic of mathematics. The Theorem is that the theories of certain mathematical structures cannot be completely axiomatized. This means there will always be true statements about the structures that cannot be proved as theorems from previously given axioms. To give meaning to this conclusion, we review some simple examples of mathematical theorems, and their proofs, in geometry, algebra, and logic; we also give examples of theories that can be completely axiomatized. First we look at Raymond Smullyan’s interpretation of Gödel’s theorem as a puzzle, and then at an analogy with the inevitable incompleteness of an English guide to English style. A general philosophical conclusion is that a science like physics cannot tell us everything there is to know, and so a doctrine such as physicalism is wrong or unverifiable.

Puzzling

The so-called Liar Paradox can be traced to the Epistle of Paul to Titus in the Greek Bible. According to a codicil at the end of the Epistle, Titus was “ordained the first bishop of the church of the Cretians” (Carroll and Prickett 2008NT pp. 265–7). In the first of the Epistle’s three chapters, Paul writes,

12 One of themselves, even a prophet of their own, said, The Cretians are alway liars, evil beasts, slow bellies.

13 This witness is true. Wherefore rebuke them sharply, that they may be sound in the faith …

In the original, Paul’s quotation of the Cretan prophet reads,

Κρήτες αεί ψεῦσται, κακά θηρία, γαστέρες ἀργαί.

This is the first of the Presocratic fragments that Diels and Kranz attribute to Epimenides (Diels 1960, 3B1, p. 32).

That a Cretan should assert that Cretans are always liars: one may take this for an absurdity or a paradox. Interpreted strictly, the assertion becomes a puzzle: is it true or false? If it were true, then, as the word of a Cretan, it would be false. Therefore:

1. It is false that all Cretans are liars.

2. Some Cretan must not be a liar.

3. The Cretan prophet is a liar.

4. Paul is a liar.

Though not mentioning Paul, Raymond Smullyan draws the first three of the four conclusions above in his book called What Is the Name of This Book? The Riddle of Dracula and Other Logical Puzzles (Smullyan 1978, para. 253, p. 214).

I was intrigued, as a child, by a review of Smullyan’s book in Martin Gardner’s “Mathematical Games” column (Gardner 1989ch. 20, pp. 281–92). A few years later, I was delighted to find a used copy of the book itself in a West Virginia junkshop. The book culminates in an exposition of Gödel’s Incompleteness Theorem.

Gödel’s theorem is that, in certain mathematical systems, there are true statements that are not theorems. These true statements fail to be theorems, not because the systems are too weak to prove them, but because the systems are too strong. The systems let us make so many statements that some of them inevitably end up being unprovable, even though they are true.

Some of the statements are true, because they cannot be proved. For, the mathematical systems in question let us formulate the statement, “I am not a theorem.” If this were false, then it would be a theorem, and theorems are true; thus the statement is true.

That was an exposition of Gödel’s Incompleteness Theorem. Such an exposition could take one of three forms:

• an annotation of Gödel’s 1931 paper, “On formally undecidable propositions of Principia mathematica and related systems I” (Gödel 2002);

• a revision of that paper at the same or a higher level of detail and rigor;

• a summary treatment, not rigorous, but leaving out details.

My exposition above was of the last type. Smullyan gives such an exposition too. Before giving more detail about Gödel’s theorem, along with some simple examples of geometric, algebraic, and logical systems and their theorems, I want to give an exposition of Smullyan’s exposition (Gardner does this too).

Smullyan’s Account

Smullyan asks us conceive of two infinite lists:

• a list A₁, A₂, A₃, … of sets of counting numbers;

• a list σ₁, σ₂, σ₃, … of statements of some mathematical system.

We are to make two suppositions about the system and the lists:

1. One of the listed sets comprises the serial numbers of the listed statements that are not theorems of the system.

2. For every listed set—call it A—, for some listed set B, for every number n, for some number k,

   • n is in B if and only if k is in A,

   • σ_k is true if and only if n is in A_n.

We can write the two bulleted conclusions more compactly as

For every listed set A then, since the set B that is guaranteed by the second supposition is also listed, the latter set is, for some n, the set A_n. For this n, for some k, the supposition yields

Combining the two parts of this conclusion, we can eliminate the mentions of n; thus, for every listed set A, for some k,

This holds in particular if A is the set mentioned in the first supposition, namely the set of numbers of statements that are not theorems. If now k ∉ A, then σ_k must be a theorem, and therefore true; but then also, according to this theorem, k ∈ A. In short, k ∉ A implies k ∈ A. Therefore indeed k ∈ A. This means both that σ_k is true, and that it is not a theorem.

We can understand σ_k as saying that its own serial number belongs to the set of serial numbers of statements that are not theorems; in short, “I am not a theorem.”

That is Gödel’s basic result, as derived from Smullyan’s suppositions. For Smullyan, establishing the first of his two suppositions “is quite a lengthy affair, though elementary in principle”; moreover, the second “is really a very simple matter.” Achieving that simplicity still takes some work, which I have glossed over.

Smullyan presents the listed statements, first as if they are knights, who always speak the truth, or knaves, who always lie. The listed sets are clubs of knights and knaves. To puzzle this out, I have introduced notation as above.

As any club has a criterion for membership, so any of the listed sets will have a definition, which can be written down. Our list of sets then is effectively a list of definitions of sets. Given any number n, we need a mathematical way of inferring what the definition of A_n is. Then we can form the statement n ∈ A_n. From this statement, we need a way to obtain a number k such that the statement is σ_k. Then, given a listed set A, we can define a set B consisting of all n such that the corresponding k is in A, and we can assume that B is also a listed set. This gives us the second supposition.

In the translation between listed sets and their serial numbers, mathematics talks about itself. I am going to liken this to how a grammar of English, written in English, implicitly talks about itself.

Smullyan gives little idea of what it means to be a mathematical theorem. I’m not sure one can have any real understanding of Gödel’s theorem without knowing about mathematical proof. Thus I shall also work through some examples, from geometry, algebra, and logic itself.

One may conclude from Gödel’s theorem that mathematics will always be incomplete. This does not mean that no particular mathematical system can be complete. I shall give some examples that are.

The Grammar of Gödel

Gödel’s theorem is a logical theorem about proving mathematical theorems. Again, the theorem is that there are mathematical systems so strong as to contain a statement σ whose meaning is precisely that of the statement, “σ is not a theorem.” In short then, σ is the statement, “I am not a theorem.”

Mathematical statements are not normally in the first person; they do not feature anything like the pronoun I. For the effect of such a pronoun, Gödel makes use of an ambiguity. A statement can be either of the following:

• something stated—call it a meaning;

• something spoken, or written down, and thus a string of symbols, be they sounds, words, or letters; they all come from a catalogue of some kind—a phonology, a dictionary, an alphabet—and are put together according to certain grammatical rules.

A book such as Fowler’s Dictionary of Modern English Usage (Fowler 1926) is about statements that are in English. It also consists of such statements, and is thus about itself, even though it may never literally refer to itself.

Fowler’s book does in fact refer to itself, in the dedication to the memory of the author’s brother,

who shared with me the planning of this book, but did not live to share the writing.

There is also a more subtle reference, in the body of the Dictionary, where the entry Inversion starts off,

By this is meant the abandonment of the usual English order & the placing of the subject after the verb as in Said he, or after the auxiliary of the verb as in What did he say? & Never shall we see his like again.

In addition to the three explicit examples, the whole sentence is an example of inversion, since in the usual English order the sentence would read, “By this, the abandonment of the usual English order … is meant,” or else “The abandonment … is meant by this.”

In his Dictionary, Fowler has included inversion because, although it has its legitimate uses,

the abuse of it ranks with Elegant Variation as one of the most repellent vices of modern writing.

Nonetheless, Fowler has already used inversion to start another entry, Battered ornaments:

On this rubbish-heap are thrown, usually by a bare cross-reference, such synonyms of the Elegant Variation kind as alma mater, daughter of Eve, sleep of the just, & brother of the Angle …

Thus, were the article Inversion deleted from the dictionary, the remainder could be counted as incomplete, for using an example of a construction that readers should be wary of abusing in their own writing.

No account of good English will ever be strictly complete, since a poet can always come along, to write verses such as

My father moved through dooms of love
through sames of am through haves of give,
singing each morning out of each night
my father moved through depths of height

—thus E. E. Cummings (Aiken 1963, 256), who breaks the rules in a way that is still recognizably English and even good English.

Gödel is the e e cummings of mathematics. In a sufficiently rich mathematical system, we can give each statement a number—its Gödel number—in such a way that, for any number n, we can make the statement,

Call this statement φ(n). Denote the Gödel number of any expression ϑ by ⌜ϑ⌝. Gödel shows how to solve the equation

We shall not refer to it again, but the solution happens to be

where ψ(k) is so defined that, for every statement χ(k), the statement ψ(⌜χ⌝) is the statement

In any case, if the number a solves the equation above, then φ(a) has the meaning of,

We concluded earlier that such a statement must be true, on the basis that theorems are true. Thus the class of truths is larger than the class of theorems. This is Gödel’s First Incompleteness Theorem.

To prove the theorem, we need not actually know that all theorems are true; it is enough that no logical contradiction be a theorem. This presupposition is a statement σ. Then we can form the implication

namely “If σ is true, then so is φ(a),” or “σ implies φ(a)”; and we have shown that this is a theorem. Since φ(a) is not a theorem, it follows that σ cannot be a theorem, if it is true; for there is a rule of inference whereby any statement β must be a theorem, if each of statements α and α ⇒ β is a theorem.

In short, our system cannot prove that it is not contradictory, if indeed it is not. This is Gödel’s Second Incompleteness Theorem.

In mathematics, one is well advised to rewrite what one reads in one’s own words and symbolism. Smullyan did this for Gödel, and I did it for Smullyan. If people who do it for Gödel are computer scientists, such as Douglas R. Hofstadter in Gödel, Escher, Bach (Hofstadter 1980), then their accounts end up looking more or less odd to me as a mathematician. What I write about Gödel may likewise look odd to the non-mathematician.

In mathematics, we prove theorems from axioms. We choose our axioms as we wish, usually because they are satisfied—made true—by some mathematical structure or structures that we want to understand. We take up, as hypotheses, statements that may be satisfied by those structures. We can be mistaken here, and that is why we want to prove our hypotheses as theorems that follow from our axioms.

Geometry

I say our proofs are based on axioms. Not all mathematicians may be prepared to explain what axioms they are working with. “However,” as Timothy Gowers observes in Mathematics: A Very Short Introduction (Gowers 2002, 41),

if somebody makes an important claim and other mathematicians find it hard to follow the proof, they will ask for clarification, and the process will then begin of dividing steps of the proof into smaller, more easily understood substeps.

Those steps and substeps are ultimately based on axioms. As Gowers has observed on the previous page, the possibility of analyzing a proof into its smallest steps

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 … it means that any dispute ahout the validity of a mathematical proof can always be resolved.

If this is indeed a discovery, then it must be true; but I think it is true in the way that axioms are true. Axioms are true by fiat. That mathematical disputes can always be resolved is a conviction that guides us in our work. I think the conviction means mathematics is pacifist—peace-making—in principle; however, in practice, we may not always have the courage of the conviction.

The prototypical examples of mathematical axioms are the postulates of Euclid’s Elements. The first four of these make possible the following activities.

1. To connect two points with a straight line.

2. To extend a given straight line as far as we like.

3. To draw a circle with any given center and radius.

4. To know that all right angles are equal to one another.

By the first three postulates, we have a ruler and compass, along with a flat surface to use them on, and an implement to leave marks or scratches with. Euclid’s word γραμμή for line (Euclid 1883) is from the verb γράφω “to scratch” (Beekes 2010).

In Postulate 4, Euclid gives us a set square. This is not to draw right angles with; Euclid will show how to do that with ruler and compass. The existence of a set square confirms that all right angles are indeed equal.

Euclid’s first four postulates entail that in any triangle, the exterior angle at any vertex is greater than either of the two opposite interior angles. This is the 16th proposition of Book i of the Elements. Thus if triangle ABΓ is given, and side BΓ is extended to Δ as in Figure 1,

then

This is a theorem. To prove it, we complete the figure as follows.

1. Bisect AΓ at E, using Proposition 10, so that

   AE = ΓE.

2. Connect BE, using Postulate 1.

3. Extend that line to Z, using Postulate 2.

4. Use Postulate 3 to ensure

   BE = EZ.

5. Connect ZΓ, using Postulate 1 again.

The figure complete, we continue with the argument.

6. By Proposition 15, that vertical angles are equal,

   ∠AEB = ∠ΓEZ.

7. From our three displayed equations, by Proposition 4, “Side Angle Side,”

   ∠EAB = ∠EΓZ.

8. However, by inspection,

   ∠EΓZ < ∠EΓΔ.

9. From this and the previous equation,

   ∠EAB < ∠EΓΔ.

10. Since angles EAB and EΓΔ are respectively ΓAB and AΓΔ, the desired conclusion follows.

Does it really follow? Consider how we can draw triangles on a globe, letting “straight lines” be segments of great circles. For example, we can let A and B lie on the equator, while Γ is at the north pole, as in Figure 2.

Then in triangle ABΓ, the angles at A and B are right, while the interior angle at Γ may be greater than that, in which case the exterior angle is less.

Thus Euclid’s Proposition i.16 fails on the globe. But then so does Postulate 1, in the sense that there is not always a unique “straight line” joining two points. There is no one such line, but there are infinitely many, if the points are antipodal.

However, as we have redefined “straight line” on the globe, so we may redefine “point” to mean pair of antipodal points, such as, in Figure 2, {A, H}, {B, Δ}, {Γ, Θ}, {E, K}, or {Z, Λ}. This way, any two “straight lines” meet at exactly one “point.”

With our new conception of straight lines and points, perhaps we still violate Postulate 2, in the sense that we cannot extend a “straight line” if it is already a full great circle. However, it is not clear that Euclid intended the postulate to exclude spheres. He did do research in spherical geometry (Heath 1981, 348–49).

Euclid’s mathematics lacks the kind of precision that we need for Gödel’s theorem. On the other hand, we may note how, as something written down on a surface, geometry is subject to itself. The proposition that we have been considering, Euclid’s i.16, begins with an absolute phrase (a genitive absolute in Greek),

Παντὸς τριγώνου μιᾶς τῶν πλευρῶν προσεκβληθείσης,

One of the sides of any triangle having been extended.

Instead of assigning a Gödel number to the proposition, we might consider it as itself constituting a diagram, the beginning of which is in Figure 3.

For the diagram, I have used not minuscule letters as in παντός, but capitals as in ΠΑΝΤΟΣ, because the latter are easier to consider geometrically, and they are the only letters Euclid would have known anyway. If we adapted Smullyan’s argument to the present context, his first list would consist of sets whose elements were diagrams instead of numbers. If being a theorem of Euclid’s system were a geometrical property of the theorem, considered as a diagram, then we could make a true geometrical statement that was not a theorem of the system. Alternatively, there are properties of diagrams that are not geometric.

Physics

In origin, geometry is surveying, a measuring of the earth: in a broad sense, a part of what we now call physics. We can argue with physics in general as we did with geometry in particular. Not all truths can result from physical laws.

Thus I think there is confusion, if not contradiction, in the words of “an atheist from a Catholic background,” Julian Baggini, in his 2020 book The Godless Gospel, in the chapter called “Good Without God” (Baggini 2020, 155):

Our twenty-first century, scientifically informed version of natural goodness would see it as comparable to things like love or beauty. These certainly exist, but they don’t turn up in physics textbooks or under a microscope. Most of us accept that, like all the phenomena of consciousness, they emerge from the workings of embodied, socialised human brains. We don’t yet know how this happens but we can be pretty sure that these marvellous bodies and brains are made up of nothing more than the stuff of physics.

I think one might as well say that the marvelous theorems of mathematics are made up of nothing more than letters of an alphabet; and Baggini must know that that, at least, would be ridiculous.

Baggini is presumably correct that love and beauty do not turn up as subjects in a physics book. Neither does one expect to see mathematical theorems in a book about typography. A physics book, or its contents, may be beloved and thus beautiful to the reader; and perhaps this must be so, to some extent at least, if the reader is going to get very far in physics in the first place. In “Cargo Cult Science” (Feynman, n.d.), Richard Feynman talks about a moral requirement for doing science, but it is rather specific:

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’m not trying to tell you what to do about cheating on your wife, or fooling your girlfriend, or something like that, when you’re not trying to be a scientist, but just trying to be an ordinary human being. We’ll leave those problems up to you and your rabbi. I’m talking about a specific, extra type of integrity that is not lying, but bending over backwards to show how you’re maybe wrong, that you ought to do when acting as a scientist.

There may be a mathematical requirement for doing typography, but it is minimal, by the account of Robert Bringhurst in The Elements of Typographic Style (Bringhurst 2004, 145):

It is not in the least necessary to understand the mathematics in order to perform the actions that the math describes. People walk and ride bicycles without mathematical analyses of these complex operations … The typographer likewise can construct beautiful pages without knowing the meaning of symbols like π or φ, and indeed without ever learning to add and subtract, if he has a well-educated eye and knows which buttons to push on the calculator and keyboard.

The original suggestion of Baggini was that goodness, love, beauty “emerge” from things that physics studies. Mathematical theorems likewise “emerge” through application of the typesetter’s art; but evidently this tells us practically nothing about mathematics. Baggini completes the paragraph that was begun above:

Love and beauty are as real as anything that has emerged from the complex arrangements of matter, like stars, chairs or sounds. Love and beauty have the capacity to fill us with joy or break our hearts. They even have some relation to truth, since we can be mistaken about what we love, even if beauty is to some extent in the eye of the beholder. We can believe all this without insisting that either needs a transcendent source. Why can’t the same be true of goodness?

Indeed, we need not assign a transcendent source to love, beauty, goodness, or truth. We need not assign any source. To assign a source is to suggest that they already exist, somehow, before they actually do. They don’t, except in a more or less jocular way, as in the saying credited to Alfréd Rényi, “defining a mathematician as a device to turn coffee into theorems” (Suzuki 2009, 380, n. 20).

Algebra

You know from school how to add and multiply integers, which are the so-called whole numbers, both positive and negative. They are conceived as forming a list

infinite in both directions. These numbers compose the set called ℤ, the letter being memorable as standing for the German Zahl “number.”

Let us now create something new: a set to be called M, comprising all of the lists of four integers. We shall write a typical such list as

for typographical convenience, although for conceptual convenience one may think of this list as a two-by-two matrix, with (a,b) in the top row and (c,d) in the bottom. Using addition and multiplication of integers, we define multiplication of elements of M by the rule

In both ℤ and M, multiplication is associative, meaning it satisfies the following axiom:

You can read the symbol ∀ as “for all …” Before the upside-down A was given this meaning, other symbols were used. Gödel uses Π, citing Łukasiewicz and Tarski (Gödel 2002, 600, n. 19), who in turn cite Peirce (Łukasiewicz and Tarski 1983, 54, n. 2). More precisely, for our ∀x, in the printed texts, Gödel uses xΠ, with slanted letter Pi after the variable, although Łukasiewicz and Tarski use ∏ x, with an enlarged upright Pi that extends below the line and is placed before the variable.

A sign such as ∀, or else a combination such as ∀x, is called a universal quantifier. Łukasiewicz and Tarski say in their footnote,

The expression ‘quantifier’ occurs in the work of Peirce … although with a somewhat different meaning.

A challenge of reading logic is that, in its study of symbolism, it uses symbolism, whose precise meaning is important to get straight, although the symbolism and its meaning will vary from author to author.

That is true in mathematics generally, but to a less extent. Perhaps the same is true for programming.

Multiplication on ℤ is commutative, meaning it satisfies the axiom

Not so M, since for example

while in the other order the product is different:

Nonetheless, in both ℤ and M, there is a multiplicative identity, namely an element e satisfying the axiom

where ∧ is to be read as “and.” Specifically, e is 1 in ℤ and I in M, where

The name for a set equipped with an associative operation and an identity is monoid. I don’t know when the name was invented.

Now we can observe that ℤ is a monoid with respect to addition as well as multiplication. A more precise way to say this is that each of the structures (ℤ,⋅,1) and (ℤ,+,0) is a monoid. So is (M,⋅,I).

One can make M into an additive monoid too, but our concern is with the multiplicative structure.

In ℤ as an additive monoid, each element a has an inverse, namely  − a. Combining an element with its inverse, in either order, yields the identity. Written multiplicatively, the axiom being satisfied here is

Neither of (ℤ,⋅,1) and (M,⋅,I) has an operation of inversion that satisfies this axiom. However, if we define

and if we let G consist of the elements A of M such that det A is either 1 or  − 1, then G has inverses, since

Any structure with an associative operation that has an identity and inverses is called a group. Thus (ℤ,+,0,−) and (G,⋅,I,^− 1) are groups. The subset { − 1, 1} of ℤ is also a group with respect to multiplication.

The identity of a monoid is “two-sided,” as are inverses in a group. An associative operation may have only a one-sided identity. For example, on any set, if we define an operation ⊗ by the rule

this means every element is a left identity; but none is a right identity, if there are at least two elements.

Again, in a monoid, identities are required to be two-sided. It follows that there can be only one of these, since if e and e′ are identities, then

Similarly, in a group, where identities are required to be two-sided, every element has only one inverse, since if a^− 1 and a′ are both inverses of a, then

If a set has an associative operation with a left identity, and each element has a left inverse, then the identity and the inverses must be two-sided, and thus the structure is a group. That is, on the basis of the three axioms

we can prove

Indeed, for any a we have from the axioms

and consequently

Thus left inverses are right inverses. Therefore

so the left identity is also a right identity.

We have now proved that the theory of groups has the three axioms above. The theory is not complete, since it entails neither the axiom of commutativity, nor its negation. In some groups, the operation is commutative; in some, not. The former groups are called abelian, for historical and practical reasons.

The group {1,  − 1} mentioned above is abelian. Moreover, each element is its own inverse; that is, the group satisfies

Every group that satisfies this axiom is abelian, since for all elements a and b of such a group,

To obtain the theory of groups in which each element is its own inverse, we do not need symbols for inverses, but can use the axioms

We can require there to be infinitely many elements of each of these groups, using additional axioms:

and so on. Here you read ∃ as “there exists … such that,” or “for some …”; the backwards E used to be written as ∑, and it or a combination such as ∃x is an existential quantifier (Łukasiewicz and Tarski 1983, 55). Thus our theory has, for each counting number n, an axiom saying that at least n + 1 elements exist.

The theory of infinite groups in which every element is its own inverse is complete. That assertion is a theorem, not of the theory, but about the theory. One proof of the theorem is by quantifier elimination. The idea is that, in each of the groups that we have just named, each system of equations and inequations can be so simplified that it becomes obvious whether there is a solution. For example, the existential statement

is obviously true for our groups, since there are at least five elements in each of them. Thus the statement is equivalent to the equation

because this is (obviously) true. Given a more complicated equation or inequation, by using associativity, commutativity, and the axiom that everything is its own inverse, we can always

• cancel the same letter from either side,

• move any letter to the other side,

• cancel repetitions of a letter from the same side.

Thus, for example, the statement

simplifies to

and then to the inequation

Replacing the constants a, b, and c with the variables y, z, and t, we simplify the statement

to

which is obviously false and thus equivalent to the inequation

In this way, every statement about the groups in question is equivalent to e = e or e ≠ e. This means our axioms give us a complete theory, in the sense of allowing every statement in their language to be proved or disproved.

Might the theory be inconsistent, so that the same statement can be both proved and disproved? No, because there are infinite groups in which every element is its own inverse; in other words, the theory of such groups has at least one model. One example of such a model consists of the infinite sequences

where each of entries e_i belongs to the group {1,  − 1}. Thus the elements of the groups are sequences

Two of these are multiplied entry by entry: for example,

The group has a subgroup, in each element of which, only finitely many entries are  − 1; this subgroup is a model of the same theory.

Logic

We have sketched a proof of a completeness theorem. This is the theorem that every statement in a certain mathematical language (namely the language of groups), or else the negation of that statement, is a theorem of a mathematical system with certain axioms (namely the axioms of infinite groups in which every element is its own inverse).

As geometry comes from surveying, so algebra comes from counting and reckoning in general. Logic comes from reasoning, but ends up creating new mathematical objects.

As algebra is concerned with equations, so logic is concerned with formulas in general. In the logic called sentential or propositional, there is nothing simpler than a formula. One definition of the formulas of this logic is as follows.

1. Each of the variables P, Q, R, and so on is a formula.

2. The constant 0 is a formula.

3. If each of F and G is a formula, then so is (F⇒G).

The sign ⇒ is a connective. For each formula that is not just a single variable or constant, there are formulas F and G such that the original formula is (F⇒G). That these F and G are uniquely determined by the original formula is a theorem; it would be false if we had left off the parentheses in defining formulas as above. The theorem would be true if we always wrote the formula

with one parenthesis, as

—or with no parentheses, but in a different order, as

This would be so-called Polish notation, apparently due to Łukasiewicz; it is convenient for computers, but perhaps not for human readers, and we shall not use it.

In the formula (F⇒G), the sign ⇒ displayed between F and G is the principal connective of the formula. The theorem of the existence of the principal connective of every compound formula allows us to compute, for every formula, the value 0 or 1, once we assign such a value to each variable that occurs in the formula. The computation follows the rule given by the following truth table, where the value of the whole formula (F⇒G) is written below its principal connective.

A formula that always takes the value 1 is a tautology. For example, (F⇒F) is always a tautology, because its truth table is computed as follows.

In principle, a truth table can always serve as a proof that a given formula is a tautology. However, the size of truth tables grows exponentially: if n variables occur in a formula, then its truth table will have 2ⁿ lines. An alternative method of proof is to designate

• certain tautologies as axioms,

• certain ways of deriving new tautologies from old ones as rules of inference.

We then obtain such a mathematical system as we have been referring to.

By Gödel’s theorem, some systems are strong enough to be incomplete. By contrast, propositional logic is weak enough that it can have complete systems. We describe such a system, based on work of Łukasiewicz, which builds on Frege (Church 1956, 156).

For our convenience, we simplify formulas with two conventions:

1. Outer parentheses are removed.

2. Internal parentheses are removed, when they can be reinstated by assigning priority to arrows on the right.

Our axioms are now three:

1. P ⇒ Q ⇒ P, or officially (P ⇒ (Q⇒P));

2. (R⇒Q⇒P) ⇒ (R⇒Q) ⇒ R ⇒ P;

3. ((Q⇒0) ⇒ P ⇒ 0) ⇒ P ⇒ Q.

Our rules of inference are two:

1. Modus Ponens: From F and F ⇒ G, infer G.

2. Substitution: From any formula, infer the formula that results from substituting a particular formula, the same each time, for every occurrence of a particular variable.

Here is an example of a proof.

1. P ⇒ Q ⇒ P by Axiom 1.

2. P ⇒ (P⇒P) ⇒ P by Substitution in step 1.

3. (R⇒Q⇒P) ⇒ (R⇒Q) ⇒ R ⇒ P by Axiom 2.

4. (P⇒Q⇒P) ⇒ (P⇒Q) ⇒ P ⇒ P by Substitution in step 3.

5. (P⇒(P⇒P)⇒P) ⇒ (P⇒P⇒P) ⇒ P ⇒ P by Substitution in step 4.

6. (P⇒P⇒P) ⇒ P ⇒ P by Modus Ponens from step 2 and step 5.

7. P ⇒ P ⇒ P by Substitution in step 1.

8. P ⇒ P by Modus Ponens from step 6 and step 7.

9. F ⇒ F by Substitution in step 8.

Strictly, the proof consists only of the nine formulas. The numbering and the explanations help prove to us that the formulas do constitute a proof. The proof establishes F ⇒ F as a theorem and therefore a tautology.

We did already know the latter from a truth table. Strictly though, we saw only the truth table for P ⇒ P. The real truth table for F ⇒ F has as many lines as that for F, with twice the columns and one more. For example, here is the truth table when F is (P⇒Q) ⇒ 0 (the row added to the bottom give the stages in which the columns are filled in):

We need not actually do all the work of writing out such a truth table, if we already know the table for P ⇒ P; but this is precisely because Substitution is a legitimate rule of inference.

We could let every tautology be an axiom, just as Euclid could have given us full use of a set square from the beginning, or for that matter given us as postulates all of his propositions, or at least the “obvious” ones. However, the point is to see how little we can get by with.

Every tautology is a theorem, because it has a proof such as the one given for F ⇒ F. This completeness of our system is itself a theorem: not a mathematical theorem of the system, but a logical theorem about the system.

Earlier we proved mathematical theorems about groups, as that a structure with an associative operation that has a left identity and left inverses is a group. These theorems are theorems of a system that can be as precisely defined as propositional logic. However, the quantifiers mean both that the system is more complicated and that it has nothing like truth tables. It has the notion of truth in a model: the model could, for example,

• be the plane or sphere for a geometric system,

• consist of integers, or matrices, or sequences, for an algebraic system.

Before the incompleteness theorems, Gödel proved a completeness theorem, whereby in such systems as we have just mentioned, the statements that are true in every possible model have proofs. Gödel’s first incompleteness theorem is then that, for some models of some systems, not every statement that is true in the model will have a proof. In particular, this is true for the counting numbers as equipped with the operations of addition and multiplication.

As we have seen, the contrary is the case for the group of sequences (±1,±1,±1,…); it is also the case for the counting numbers with addition alone. Telling which models are Gödelian or “wild,” and which are “tame” in the sense of being completely axiomatizable, is the subject of ongoing research.

References

About This Document