Logic, Sets, and Maps

Propositional logic, sets, maps, and equivalence classes form the raw language in which the rest of this treatise is written. This chapter fixes that language: what we mean by a definition, an axiom, and a theorem; how propositions combine under logical operators; what sets, numbers, and maps are; and how an equivalence relation partitions a set into classes.

The chapter then turns the language on itself. Comparing infinite sets uncovers a strict hierarchy of infinities (Section 3.5); unrestricted set-building collapses in Russell's paradox, and the Zermelo–Fraenkel axioms repair it (Section 3.6); Hilbert's demand that mathematics certify its own consistency, completeness, and decidability is answered — negatively — by Gödel's incompleteness theorems (Section 3.8) and by Turing's analysis of computation (Section 3.9). We close by asking, with the full twentieth-century record on the table, whether mathematics can be built free of contradiction, and what the honest answer means for a book that intends to derive physics from evidence and proof (Section 3.10). A physics treatise owes its readers this chapter: every derivation in the book is a formal proof in the sense made precise here, and the limits of that method are part of its description.

Logic

Propositions

Definitions

The definition of the word definition is redundant in an obvious sense. We could say instead: the accepted meaning of definition is…{} — but then, what is the definition of accepted meaning? Better still: what is something? And beyond that: why does something exist? Whenever we try to reach a primordial question we run into problems, circular loops, and paradoxes. To avoid entering into philosophical discussion (though such discussion is never wasted), we simply adopt the dictionary meaning [RAE:2014]: a definition is a declarative sentence that states with clarity and exactness the generic and specific characteristics of something, concrete or abstract.

In mathematical notation, when we wish to record a definition — that is, when an equality holds not as the result of other equalities but by fiat — we use the symbol \(:=\). For example, let \(\lozenge\) be an object. We define \(\blacklozenge\) by \(\blacklozenge:=\lozenge^{-1}\), and we define \(\lozenge\lozenge^{-1}\) by \(\lozenge\lozenge^{-1}:=\ \circlearrowleft\). Every time the object \(\blacklozenge\) appears we may replace it by \(\lozenge^{-1}\), since by definition they are exactly the same thing, and likewise we may replace \(\lozenge\lozenge^{-1}\) by \(\circlearrowleft\). For instance,

A definition need not be a fundamental truth. However, for an idea built from definitions — together with the observations made upon them — to be consistent, a definition must be irrevocable within its context (at least, this book demands it). We cannot build an idea on definitions that we later change, much less on new definitions that contradict the earlier ones. In what follows, the definitions we give will not be dictionary entries but will be tailored to the studies we undertake.

Generalization and specification of a definition

It is often necessary to extend a definition so that it covers more concepts; when this happens one usually renames the definition to fit the new context. As a toy example, define first a hydroliving object as an object that lives on Earth and contains at least ten hydrogen atoms. We ourselves are then hydroliving objects. Now extend the definition to an object living anywhere in the Milky Way that contains at least ten hydrogen atoms, which we call locally hydroliving: we have generalized the definition, and we are locally hydroliving. We may also sharpen the parameters of a definition, cutting down the candidates that satisfy it: call submarine hydroliving a hydroliving object that is born, lives, and reproduces in the sea.

We call generalization and specification of a definition, respectively, the definitions obtained by enlarging or reducing the set of candidates satisfying the original one. Both notions are relative to the aspect of the definition being modified; for example, one may generalize and specify simultaneously by defining a locally hydrolivoid object as one living in the Milky Way but containing at least \(1000000\) hydrogen atoms.

For example, let \(p=\text{``Albert Einstein was born in 1879''}\). The truth value of \(p\) is \(T\), since that is indeed what happened. Let \(q=\text{``Paul Adrien Maurice Dirac was born in 1790''}\). The truth value of \(q\) is \(F\), because Dirac was born in 1902.

An axiom, accompanied by the pertinent definitions, allows one to build a self-consistent idea (not necessarily consistent with other ideas). The word axiom is used in mathematics; in physics one uses, depending on the importance of the proposition in its context, the words law, principle, or postulate. As an example, let \(\ltimes\) be given and define \(\rtimes:=-\ltimes\). Separately, enunciate the axiom \(-(-\ltimes)=\ltimes\). We conclude a new, consistent statement: \(-\rtimes=\ltimes\).

In the preceding example it is a theorem that \(-\rtimes=\ltimes\). In the literature it is not customary to call every demonstrated result a theorem: depending on the relevance of the result one speaks of a theorem, a lemma, a corollary, or even a proposition — the last not to be confused with a logical proposition.

Logical operators

Given a proposition, we can form new propositions from it. For example, let \(p=\text{``It is raining outside''}\). The truth value of \(p\) is not settled — until we look outside we do not know whether it is raining — but from \(p\) we may consider the proposition \(q=\text{``It is not raining outside''}\). Moreover, given the proposition \(r=\text{``I put on a coat''}\), from \(p\) and \(r\) we can form \(s=\text{``If it is raining outside, then I put on a coat''}\).

In the trivial case, the truth table of a single proposition \(p\) is

For example, let \(p=\text{``Today is Monday''}\). Its negation is

which we read more naturally as “Today is not Monday”. According to the table, if it is true that today is Monday, then it is false that today is not Monday; conversely, if it is false that today is Monday, it is true that today is not Monday.

For example, let \(p=\text{``I am in Asia''}\) and \(q=\text{``I am in Africa''}\). Then \(p\wedge q=\text{``I am in Asia and I am in Africa''}\). Common sense tells us it is impossible to be in two places at once, i.e. \(p\wedge q\) is false. According to the table this may be because it is false that I am in Asia, false that I am in Africa, or false that I am in either place.

For example, let \(p=\text{``I will arrive at 8:00''}\) and \(q=\text{``I will arrive at 8:05''}\). Then \(p\vee q=\text{``I will arrive at 8:00 or at 8:05''}\).

For example, let \(p=\text{``Today is Sunday''}\) and \(q=\text{``Today I will rest''}\). Then \(p\rightarrow q=\text{``If today is Sunday, then I will rest''}\). From the table: if today really is Sunday but it is false that I will rest, then it is indeed false that “if today is Sunday, then I will rest”. On the other hand, if today is not Sunday but I do rest anyway, the conditional stands. Even if today is neither Sunday nor a day I rest, the proposition is true, because my not resting on a non-Sunday takes nothing away from my resting when Sunday does come.

For example, let \(p=\text{``Wake me up''}\) and \(q=\text{``It is 10:00''}\). Then \(p\leftrightarrow q=\text{``Wake me up if and only if it is 10:00''}\).

For example, given propositions \(p\) and \(q\), a logical expression is

The expression \(s\) can take various truth values depending on the truth values of \(p\) and \(q\). Let us build its truth table. First, from Equation (3.3),

From Equation (3.10),

Then, from Equation (3.5),

Implications and logical equivalences

All the logical operators above generate propositions that are contingencies, as their truth tables show. Indeed, any single proposition is a contingency, since it can be true or false. A more elaborate example is the expression defined in Equation (3.13).

The contrapositive \(\neg q\rightarrow\neg p\) must not be confused with the converse \(q\rightarrow p\), which is not equivalent to \(p\rightarrow q\): rows two and three of Equation (3.10) differ under the exchange of \(p\) and \(q\). Asserting the converse from the conditional is the fallacy of affirming the consequent, and it is a standing hazard in experimental physics: a theory \(p\) predicting an observation \(q\) is not confirmed as true by observing \(q\), since some rival theory may predict the same \(q\). What the observation of \(\neg q\) does establish — by Equation (3.17) — is \(\neg p\). This asymmetry between confirmation and refutation is the logical skeleton of falsificationism [Popper:1959] and of Remark 1.2.

Equation (3.25) is the law of the excluded middle: a proposition is true or its negation is, with no third option. It is a theorem of the two-valued truth tables of Definition 3.1 precisely because we built those tables with two values. Whether it should be assumed when reasoning about infinite collections — where no finite inspection can decide which disjunct holds — is the point at which intuitionism parts company with classical mathematics (Section 3.6.4). This treatise reasons classically, and says so.

Predicates and quantifiers

Propositional logic is too coarse for mathematics or physics. The sentence “\(x\) is greater than \(3\)” has no truth value until \(x\) is supplied; only then does it become a proposition. Such an incomplete sentence is a predicate, and completing it is what quantifiers do.

Over a finite set \(X=\set{x_{1},\ldots,x_{n}}\) the quantifiers are abbreviations for finite connectives,

and this is the way to remember their negations: De Morgan's laws (Proposition 3.20) pass to the limit of infinite \(X\), where the finite reading is no longer available but the rule survives,

To refute a universal claim one exhibits a single counterexample; to refute an existential claim one must argue about every element. This is why “no experiment has ever violated the second law” is a far weaker statement than “the second law holds”, and why the search for a violating experiment is nonetheless the right way to test it.

Methods of proof

Every result asserted in this treatise carries a derivation, by editorial rule. The derivations use a small and closed repertoire of argument forms, each of which is a tautology of Proposition 3.22 put to work.

1. Direct proof. To establish \(p\rightarrow q\), assume \(p\) and derive \(q\) by a chain of previously established implications. The underlying tautology is transitivity of the conditional, \(\left((p\rightarrow r)\wedge(r\rightarrow q)\right)\rightarrow(p \rightarrow q)\), together with modus ponens, \(\left(p\wedge(p\rightarrow q)\right)\rightarrow q\).

2. Contraposition. To establish \(p\rightarrow q\), assume \(\neg q\) and derive \(\neg p\). Legitimate by Proposition 3.21. The proof of injectivity in Definition 3.45 uses exactly this move.

3. Contradiction (reductio ad absurdum). To establish \(p\), assume \(\neg p\) and derive a contradiction \(q\wedge\neg q\), which is false by Equation (3.26); since a false conclusion cannot follow from a true assumption, \(\neg p\) is false and, by Equation (3.18), \(p\) holds.

4. Cases. If \(p_{1}\vee\cdots\vee p_{n}\) is a tautology and each \(p_{i}\rightarrow q\) has been proved, then \(q\) holds. The two-case version rests on Equation (3.25).

5. Induction. To establish \(\forall n\in\N,\ P(n)\), prove \(P(1)\) and prove \(\forall n\in\N,\ P(n)\rightarrow P(n+1)\). This is not a tautology of propositional logic but an axiom about \(\N\) — Axiom 3.34 below — and it is the one place where the structure of the natural numbers enters a proof.

6. Counterexample. To refute \(\forall x\in X,\ P(x)\), exhibit one \(x\) with \(\neg P(x)\), by Equation (3.32). One suffices; no number of confirming instances does the opposite job.

Sets

Set theory descends through Cantor, Frege, Russell, and Zermelo–Fraenkel. In what follows we shall not include all the formalism that the full theory demands; we give only the definitions, axioms, and theorems that allow us to understand the many aspects of mathematical physics whose properties we can link with nature.

Sets

For example, the vowels form the set \(X\) given by

Two sets are equal when they have the same elements, and nothing else about them counts: a set is determined by its extension alone. This is the principle of extensionality, and in the axiomatic treatment of Section 3.6.2 it is promoted to an axiom. It is what licenses the double-inclusion argument Equation (3.47) used throughout this book, and it is the reason \(\set{a,e,i,o,u}\) and \(\set{e,a,u,i,o,a}\) are the same set: order and repetition are features of the notation, not of the object.

Every set has the empty set as a subset: the condition Equation (3.35) quantifies over the elements of \(\varnothing\), of which there are none, so it holds vacuously — an instance of rows three and four of Equation (3.10). Extensionality makes the empty set unique, since any two sets with no elements have the same elements. That so much can be built from nothing at all is the first sign that the naive notion of set carries more weight than it looks able to bear; Section 3.6 shows where it breaks and how the Zermelo–Fraenkel axioms repair it.

Numbers

Number theory is an essential branch of mathematics that studies the properties of numbers. We shall not define number; instead we explain a way of understanding the familiar number sets.

Natural numbers $\N$

The set known as the natural numbers is a set of numbers with which we can identify, for example, a quantity of whole objects. Concretely: take the proposition “a farmer owns cows”, assumed true. We can then assert that the farmer has one, two, three, or more cows. The farmer cannot have infinitely many cows, for they would not fit in the world, and cannot have none, for that would be a contradiction. We write

That description says what \(\N\) is for, not what it is. The axiomatic characterization is Peano's [Peano:1889], and it needs one undefined operation: the successor, “the next one after”.

The two clauses forbid the successor chain from closing back on itself, but by themselves they do not forbid stray elements sitting outside the chain \(1,S(1),S(S(1)),\ldots\) altogether. Excluding those is the work of the fifth and deepest of Peano's axioms, which is also the licence for the induction proofs of Section 3.1.5.

Addition and multiplication are then defined by recursion on the successor — \(n+1:=S(n)\), \(n+S(m):=S(n+m)\), \(n\cdot1:=n\), \(n\cdot S(m):=n\cdot m+n\) — and every familiar arithmetic law is a theorem proved by induction. This matters beyond arithmetic: the axioms above, written in first-order logic with induction restricted to predicates expressible in that language, constitute Peano arithmetic (Definition 3.83), the theory whose incompleteness Gödel proved.

Integers $\Z$

The set known as the integers consists of the natural numbers together with a new element, the number zero, denoted \(0\), which quantifies the existence of nothing: given the proposition “a farmer owns no sheep”, we say the farmer has zero sheep.

The set also contains, for each natural number, a dual element manifesting its opposite. Consider a sport played by two teams, where a team gains a point by stealing a banner from the other and loses a point when a banner is stolen from it. If a team has two banners stolen at the start, what is its score? Clearly it has gained nothing, but we intuit it holds something dual to the number \(2\) — something like “minus 2”. Writing these dual numbers with the minus sign \(-\) on the left, the set of integers is

Several subsets of \(\Z\) are heavily used in mathematics and physics. Among them:

1. Even numbers: the set

   \begin{equation} \set{2n\mid n\in\Z}=\set{\ldots,-4,-2,0,2,4,\ldots}\ec \end{equation}

   that is, the set of all multiples of \(2\) (positive and negative), clearly a subset of \(\Z\).

2. Odd numbers: the set

   \begin{equation} \set{2n+1\mid n\in\Z}=\set{\ldots,-5,-3,-1,1,3,5,\ldots}\ec \end{equation}

   that is, the set of all multiples of \(2\), plus or minus \(1\).

3. Prime numbers: the natural numbers that are multiples only of \(1\) and of themselves. For example, \(4\) is a multiple of \(1\), \(2\), and \(4\), so it is not prime; \(5\) is a multiple only of \(1\) and \(5\), so it is prime. By convention \(1\) is not considered prime, since the primes satisfy many properties in number theory that \(1\) does not. The set of primes is denoted \(\mathbb{P}\); its first ten elements are

   \begin{equation} \mathbb{P}=\set{2,3,5,7,11,13,17,19,23,29,\ldots}\ep \end{equation}

   Note that the only even prime is \(2\).

Rational numbers $\Q$

The set known as the rational numbers is a set of numbers with which we can identify portions. If we have a watermelon and eat half of it, we say we have eaten the fraction “one half” of the watermelon, written \(\frac{1}{2}\). We could likewise have eaten \(\frac{1}{3}\) of it, or even \(\frac{2}{2}\), which corresponds to eating the whole watermelon. In a fraction, the upper number is the numerator and the lower one the denominator. These new numbers, together with the integers, form the set of rational numbers

where zero is excluded as a denominator because it leads to complications: there is no practical or canonical way to define how many times zero fits into an arbitrary number.

Irrational numbers $\R\setminus\Q$

Geometry produces new numbers whose infinite decimal expansions follow no known general formula. A classic example is the number \(\pi\), the ratio of the perimeter of a circle to its diameter,

Another example is the length of the diagonal of a unit square, the Pythagorean number \(\sqrt{2}\). These new numbers are called the irrational numbers. That they exist at all — that the rationals do not already exhaust the number line — is not an observation but a theorem, proved for \(\sqrt{2}\) in Example 3.26. That they are in fact the overwhelming majority of the real numbers is a much later and much stranger result, Theorem 3.69.

Real numbers $\R$

The rationals together with the irrationals form the real numbers \(\R\). We have no general symbolic rule for them, but graphically we can represent them by a straight line built out of them, as in Figure 3.1: each \(x\in\R\) is a point of the line.

The number sets assemble into the hierarchy

where \(\mathbb{I}\) denotes the imaginary numbers and \(\C\) the complex numbers, both studied in detail in Complex Analysis.

Operations with sets

The logical operators of Section 3.1.2 induce operations on sets, because a set is the truth set of a predicate and the operators combine predicates. Each definition below pairs one connective with one symbol, and this pairing is the whole content of the subject.

The complement is defined relative to a stated ambient set and never absolutely. There is no set of all things to take complements in: assuming one is exactly the mistake that produces Russell's paradox (Theorem 3.75).

Two properties will be used repeatedly in this book. First, mutual inclusion implies equality — this is extensionality in working form:

Second, intersecting with the empty set yields the empty set:

That proof is the template for the whole algebra of sets: commutativity, associativity, distributivity and absorption of \(\cup\) and \(\cap\) are the set-theoretic shadows of Equations (3.19), (3.20), (3.21), (3.22) and (3.24), obtained by the same translation and proved by the same two lines. We shall use them without further comment.

For families of more than two sets, indexed by an arbitrary set \(I\) — finite, countable, or neither — we write

The pairing of \(\cup\) with \(\exists\) and of \(\cap\) with \(\forall\) is the same one as before, now in its quantified form; the negation rules Equations (3.32) and (3.33) turn into De Morgan's laws for arbitrary families.

Cartesian products are the reason this section belongs in a physics book. Configuration space is a product of position ranges, phase space a product of configuration and momentum spaces (Hamiltonian Mechanics), spacetime a product of a time axis with a spatial manifold in every chart, and a relation — including every equivalence relation of Section 3.4 and every map of Section 3.3 — is formally a subset of a product.

Cardinality

For example, the cardinal of the set of vowels is \(\abs{\set{a,e,i,o,u}}=5\), and \(\abs{\varnothing}=0\). The cardinal of the set of naturals greater than or equal to \(6\) and less than \(15\) is \(\abs{\set{6,7,8,9,10,11,12,13,14}}=9\). Other sets are infinite: \(\N\), \(\Z\), \(\Q\), \(\R\), and even the set of reals between \(0\) and \(1\).

Writing \(\abs{\R}=\infty\), as is often done informally, throws away the most interesting fact in this chapter. Both \(\N\) and \(\R\) are infinite, yet we intuit that \(\R\) is somehow “more” infinite — and that intuition is correct, provable, and the beginning of a whole hierarchy (Section 3.5). Until the tools for comparing infinite sets are in place we confine the arithmetic of cardinals to finite sets.

For example, if \(X=\set{a,b,c}\), then

The exponential notation is not a coincidence of counting. Sending a subset \(A\subset X\) to its indicator function — the map taking the value \(1\) on \(A\) and \(0\) elsewhere — is a bijection between \(\mathcal{P}(X)\) and the set \(\mathcal{F}(X,\set{0,1})\) of Definition 3.52, for finite and infinite \(X\) alike. This is why the power set is also written \(2^{X}\), and why Theorem 3.71 below can be read as the statement that there are always more functions on a set than points in it.

Maps

Maps

Consider two non-empty sets \(X\) and \(Y\). In the everyday sense we can always relate some element of \(X\) with some element of \(Y\) by means of an arbitrary rule: some elements of \(X\) may be related to several elements of \(Y\), others to none. The relations that turn out to be most useful are the more disciplined ones, in which each element of \(X\) is related to one and only one element of \(Y\): we demand both the existence of a related element in \(Y\) and its uniqueness.

We may picture a map as a “machine” to which we feed an element of the domain, and which transforms it into an element of the codomain. For example, the map \(f\) assigning to each natural number its square root is

Not every element of the codomain need be the result of mapping some element of the domain. Note that the image of a map is defined canonically: a map brings its image with it, uniquely determined, which is not the case for the codomain. One must not confuse this with two distinct maps sharing the same assignment formula: the image of

is different from the image of

Injectivity means that two distinct elements of the domain are mapped to distinct elements of the codomain. The definition is equivalent to: \(f:X\longrightarrow Y\) is injective if and only if

since the two implications are contrapositives of one another.

Bijectivity sharpens surjectivity by demanding uniqueness in the existence. A more practical characterization is the following.

The notation is a deliberate abuse: \(f^{-1}(B)\) is defined for every map, bijective or not, and is a set, whereas the inverse map of Definition 3.51 exists only for bijections and returns an element. The two agree, up to the identification of a point with the singleton containing it, exactly when \(f\) is a bijection.

This asymmetry is why preimages, not images, are the right notion in topology (continuity is “preimages of open sets are open”, Topological and Metric Spaces) and in measure theory (a random variable is measurable when preimages of intervals are measurable, Probability and Statistics).

Associativity with a two-sided identity is precisely the axiom system of a monoid, and the bijections of a set onto itself — which by Proposition 3.57 are closed under composition and by Definition 3.51 under inversion — form a group, the symmetric group of the set. That is the bridge from this chapter to Algebraic Structures, and through it to every symmetry argument in the physical parts of this treatise.

Equivalence classes

Equivalence relations

By reflexivity, \(a\in[a]\). Moreover, let \(b\in[a]\); then \(b\sim a\) and, by symmetry, \(a\sim b\). Now let \(x\in[a]\); then \(x\sim a\) and, by transitivity, \(x\sim b\). Since \(x\) is arbitrary in \([a]\), every element of \([a]\) is equivalent to \(b\), and we conclude that any element of \([a]\) may serve as its representative.

Two examples:

• On the set \(\R\), define the relation

  \[ x\sim y\iff \exists\ n\in\Z \mid y=x+2\pi n,\qquad x,y\in\R\ec \]

  which is indeed an equivalence relation:

  1. \(x\sim x\), since there exists \(0\in\Z\) such that

     \[ x=x+2\pi\cdot0\ep \]

  2. Suppose \(x\sim y\). Then there exists \(n\in\Z\) such that

     \begin{align*} y & = x+2\pi n\\ \implies x & = y-2\pi n\\ \implies x & = y+2\pi m,\quad m\in\Z\ec \end{align*}

     hence \(y\sim x\) and symmetry holds.

  3. Suppose \(x\sim y\) and \(y\sim z\). Then there exist \(n,m\in\Z\) such that

     \[ y=x+2\pi n,\quad z=y+2\pi m\ep \]

     Adding the equations gives

     \[ z=x+2\pi(n+m),\quad n+m\in\Z\ec \]

     hence \(x\sim z\) and transitivity holds.

  One says that \(x\) and \(y\) are congruent modulo \(2\pi\); in particular \(0\) and \(2\pi\) are congruent, i.e. they belong to the same equivalence class. If you know the trigonometric functions, this is surely something you had always intuited.

• In a non-leap year of the Gregorian calendar, define the relation

  \[ x\sim y\iff x \text{ has their birthday on the same day as } y\ec \]

  which is an equivalence relation, very direct to verify. There are clearly 365 equivalence classes.

Quotient space

Quotienting is how physics disposes of descriptive surplus. Angles are real numbers modulo \(2\pi\), the example above. States in quantum mechanics are vectors of a Hilbert space modulo nonzero complex scaling, which is why the state space is the projective space \(\mathcal{P}(\mathcal{H})\) and why the global phase of a wavefunction is unobservable (The Postulates of Quantum Mechanics). Gauge fields related by a gauge transformation are the same physical configuration, and the physical configuration space is the quotient by the gauge group (Generalized Classical Field Theory). In each case the equivalence relation encodes exactly what no measurement can distinguish, and Theorem 3.60 guarantees that this notion of “same physical situation” is consistent: the classes never partly overlap.

The infinite

Cardinality was defined in Section 3.2.4 by counting, which works only for finite sets. Cantor's insight was that comparison does not require counting: two shepherds can agree that they have equally many sheep by pairing the animals off, without either of them knowing how to count. The pairing is a bijection, and it makes sense whether the flocks are finite or not [Cantor:1874].

Equipotence and countability

Being countably infinite means precisely that the elements can be arranged in an infinite list \(x_{1},x_{2},x_{3},\ldots\) in which every element appears exactly once: the list is the bijection. The natural numbers are trivially countable, via \(n\longmapsto n\). Three less obvious examples follow, and each is a warning that infinite sets do not behave like finite ones.

That a proper subset can be equipotent to the whole is impossible for finite sets and characteristic of infinite ones — indeed Dedekind took it as the definition of infinite [Dedekind:1888]. It is the content of the parable of Hilbert's hotel: a hotel with rooms \(1,2,3,\ldots\), all occupied, still accommodates a new guest by moving the occupant of room \(n\) to room \(n+1\).

So the rationals, dense though they are — between any two of them lies another — are no more numerous than the integers. At this point one might guess that all infinite sets are equipotent, and that “infinite” admits no useful gradation. Cantor showed otherwise.

The diagonal argument

The pattern of the proof, not its arithmetic, is what matters. A list is given; a new object is built by disagreeing with the \(n\)-th listed object in its \(n\)-th feature; the new object cannot be on the list. This diagonal argument reappears at every turn in the rest of the chapter: in Cantor's theorem immediately below, in Russell's paradox (Theorem 3.75), in Gödel's undecidable sentence (Theorem 3.87), and in Turing's halting problem (Theorem 3.96). They are four faces of one idea.

Theorem 3.71 generalizes Proposition 3.42 from finite sets to all sets, and it strengthens Theorem 3.69: taking \(X=\N\) gives an uncountable set directly, and one can show \(\abs{\mathcal{P}(\N)}=\abs{\R}\), the cardinal of the continuum, written \(\mathfrak{c}=2^{\aleph_{0}}\). Comparison of cardinals is made rigorous by the following theorem, whose proof is long enough to belong in the appendix.

Full derivation in Appendix A.

Derives Theorem 3.72.

The continuum hypothesis

Cantor found \(\aleph_{0}=\abs{\N}\) and \(\mathfrak{c}=\abs{\R}\) with \(\aleph_{0}<\mathfrak{c}\), and could not settle the obvious next question: is there anything strictly in between?

Hilbert placed the question first on his list of twenty-three problems for the new century [Hilbert:1900], and its resolution took two thirds of that century and came in two halves, neither of them an answer in the sense Hilbert expected.

1. Gödel showed in 1938 that if ZF is consistent, then so is ZFC together with the continuum hypothesis [Goedel:1938]. He did it by constructing the universe \(L\) of constructible sets, an inner model of ZF in which both the axiom of choice and Axiom 3.73 come out true. So Axiom 3.73 cannot be refuted from the axioms.

2. Cohen showed in 1963 that if ZF is consistent, then so is ZFC together with the negation of the continuum hypothesis [Cohen:1963]. His method, forcing, adjoins to a model new sets constructed by finite approximations, in such a way that the cardinal \(\mathfrak{c}\) can be pushed above \(\aleph_{1}\) while every axiom of ZFC survives. So Axiom 3.73 cannot be proved from the axioms either.

Together: the continuum hypothesis is independent of ZFC. It is not that we do not yet know whether it is true; it is that the axioms we use for mathematics do not decide it, as the parallel postulate is not decided by the other axioms of geometry. One may adjoin it or its negation and get consistent mathematics either way.

The crisis of foundations

Definition 3.28 says a set is a grouping of elements satisfying the same logical propositions. Taken at face value this is the principle of unrestricted comprehension: every predicate \(P\) determines a set \(\set{x\mid P(x)}\). It is the natural reading; it is, in the guise of Basic Law V on value-ranges, what Frege built his reduction of arithmetic to logic upon [Frege:1893]; and it is false.

Russell's paradox

Russell communicated the argument to Frege in June 1902, while the second volume of Frege's Grundgesetze was at the printer; Frege appended a note beginning “Hardly anything more unwelcome can befall a scientific writer than that one of the foundations of his edifice be shaken after the work is finished”. The exchange is reprinted in [vanHeijenoort:1967].

Compare Equation (3.80) with the set \(D\) of Theorem 3.71. They are the same construction: Russell's paradox is Cantor's diagonal argument applied to the map that sends each set to itself. Cantor's theorem is a theorem because \(D\) is carved out of an existing set \(X\); Russell's is a paradox because \(R\) is carved out of nothing at all. That distinction is the entire repair.

The Zermelo–Fraenkel axioms

Zermelo's response [Zermelo:1908], completed by Fraenkel and Skolem [Fraenkel:1922], was to abandon comprehension as a general principle and to legislate instead exactly which set formations are permitted. Sets are then not defined at all: like “point” in geometry or “event” in relativity, “set” and “\(\in\)” are primitive notions (Section 1.5), constrained only by axioms.

Separation is the repair. It permits \(\set{x\in A\mid P(x)}\) but never \(\set{x\mid P(x)}\): a set may only be sieved out of a set already known to exist. Russell's \(R\) is unobtainable, since no prior set is available to sieve. What survives of his argument is a theorem.

The universe of sets is thus not itself a set — it is a proper class, and Remark 3.64 was an instance of the same fact. Foundation goes further and rules out \(x\in x\) outright, so that the sets form a cumulative hierarchy built up from \(\varnothing\) by iterated power sets. Nothing in physics ever reaches beyond the first few dozen levels of that hierarchy.

The axiom of choice

The ninth axiom is different in kind from the other eight. Each of those gives an explicit recipe for the set it asserts; choice asserts that a selection exists without providing any rule for making it. For finitely many non-empty sets the selection can be made one at a time and choice is a theorem; for infinitely many it is a genuine assumption.

Choice is equivalent, over ZF, to a list of statements that look nothing like it and are used constantly: Zermelo's well-ordering theorem (every set admits a well ordering), Zorn's lemma (a partially ordered set in which every chain has an upper bound has a maximal element), the statement that every vector space has a basis (Linear Algebra and Representation Theory), Tychonoff's theorem on products of compact spaces (Topological and Metric Spaces), and the claim that every surjection has a right inverse.

Its cost is that it produces objects no construction could reach. Vitali's non-measurable subset of \(\R\) and the Banach–Tarski decomposition — a solid ball cut into five pieces and reassembled, by rigid motions alone, into two balls of the original size — both follow from choice, and both are immune to physical interpretation precisely because the pieces have no volume. The lesson for physics is not that choice is false but that measure-theoretic hygiene is mandatory: probability is defined on a \(\sigma\)-algebra of measurable sets, and the pathological sets are simply not in it (Probability and Statistics).

Three answers to the crisis

The paradoxes forced a question that mathematics had never needed to ask: what are its statements about, and what makes a proof valid? Three programmes answered differently, and their disagreement is the direct ancestor of the results in the remainder of this chapter.

1. Logicism (Frege, Russell, Whitehead). Mathematics is a branch of logic: numbers are definable in purely logical terms and arithmetic truths are logical truths. Principia Mathematica [Whitehead:1910] carried the reduction out in three volumes: the cardinal groundwork for \(1+1=2\) is proposition *54.43, midway through the first volume, and the arithmetical proposition itself is *110.643, on page 86 of the second. The paradoxes were blocked with a ramified theory of types forbidding a collection to contain itself. The programme foundered on its own repairs: the axioms of infinity and of reducibility, needed to make the development work, are not plausibly logical truths, so the reduction relocated the problem rather than dissolving it.

2. Formalism (Hilbert). Mathematics is the manipulation of finite strings of symbols according to stated rules; questions of what the symbols denote are set aside. Infinite objects are “ideal elements”, admissible so long as reasoning with them never yields a false statement about finite ones [Hilbert:1926]. Hilbert's programme is the demand that this be proved, by finitary means, once and for all. It is the subject of Sections 3.8 and 3.10.

3. Intuitionism (Brouwer). Mathematics is a mental construction, and a mathematical object exists only when it has been constructed [Brouwer:1913]. On this view \(\forall x\,P(x)\) asserts a method producing a proof of \(P(x)\) for each \(x\), and \(\exists x\,P(x)\) asserts a construction exhibiting a witness. The law of the excluded middle Equation (3.25) then fails for infinite domains: to assert \(p\vee\neg p\) over \(\N\) is to claim a decision procedure one may not possess. Proof by contradiction survives for refutations but not for existence claims — an intuitionist rejects a proof that some \(x\) exists which merely shows that the non-existence of \(x\) is absurd.

This treatise reasons classically, uses ZFC without apology, and states the fact rather than assuming it. But the intuitionist objection has an afterlife the physicist should recognize: a constructive existence proof yields an algorithm, and a classical one need not. When a physical theory guarantees that a solution, a ground state, or an equilibrium exists, only the constructive version tells anyone how to compute it — and Section 3.9 shows that the gap between the two is not always bridgeable, even in principle. Bishop's constructive redevelopment of analysis [Bishop:1967] shows how much of the working mathematics of physics can be had on those terms, which is more than the classical mathematician expects and less than the physicist would like.

The analytical perspective

The same decades that produced the paradoxes produced a movement in philosophy that took the new logic as its instrument: analytical philosophy. Its founding conviction was that philosophical problems are to be attacked by analysing the logical structure of the language in which they are posed — and its central case study was physics. This treatise's first editorial rule, that only physics with observational evidence is in scope, is a philosophical commitment, not a mathematical one. It deserves an argument rather than an assertion, and the argument was worked out here.

The linguistic turn

Frege's Begriffsschrift [Frege:1879] introduced quantifiers, variables and a rigorous notion of proof, replacing two millennia of syllogistic; Section 3.1.4 is his legacy. His Grundlagen [Frege:1884] then asked what a number is, and answered by analysing the sentences numbers occur in rather than by introspecting about quantity. That reversal — study the statement, not the thing — is the linguistic turn.

Frege's distinction between the sense of an expression and its reference is the part a physicist uses daily. “The morning star” and “the evening star” refer to the same object, Venus, but differ in sense, which is why their identity was a discovery and not a triviality. The pattern recurs throughout this book. Inertial mass and gravitational mass have entirely different senses — one is the resistance to acceleration in Newtonian Dynamics, the other the coupling to a gravitational field — and their identity is an empirical finding, tested to parts in \(10^{15}\) and elevated to the equivalence principle (The Equivalence Principle and Classical Tests). Energy and mass, inertia and curvature, temperature and mean kinetic energy: each is an identity of reference across a difference of sense, each was an experimental result, and none is a definition.

Russell's theory of descriptions supplied the second tool. The sentence “the present King of France is bald” is not about a bald man; analysed, it asserts that exactly one thing kings France and that it is bald — a perfectly meaningful claim, and false, with no ghostly monarch required. The grammatical form of a sentence can thus misrepresent its logical form. This is precisely what happened to the aether: “the frame in which the aether is at rest” is a definite description whose presupposition fails, and special relativity did not find that frame moving oddly, it denied that the description picks anything out (Experiments: Light, the Aether, and Time). A physicist who keeps the distinction in view is protected against a whole family of pseudo-questions — “what is the wavefunction really made of”, “where was the particle before measurement” — which may or may not have answers, but which certainly do not have them merely because the grammar of the question is well formed.

Logical positivism and its collapse

Wittgenstein's Tractatus [Wittgenstein:1922] pushed the programme to its limit: propositions picture facts, the sense of a proposition is the state of affairs it depicts, and what cannot be depicted cannot be said. Its closing proposition — whereof one cannot speak, thereof one must be silent — was read by the Vienna Circle as a mandate. Their manifesto [Carnap:1929] proposed the verification principle: the meaning of a statement is the method of its verification, and a statement admitting no verification is not false but meaningless. Metaphysics was to be eliminated, not refuted.

For a while physics appeared to vindicate them, because physics had just done it. Einstein's 1905 analysis of simultaneity is the operationalist move in its purest form: instead of asking what simultaneity is, he asked what procedure establishes it, found that the procedure is frame-dependent, and derived the Lorentz transformations from that (Lorentz Transformations). Heisenberg's 1925 matrix mechanics was motivated by the resolve to build a theory from observable transition frequencies and intensities alone, discarding unobservable electron orbits (Atomic Models and Spectra). Two revolutions in twenty years, both achieved by discarding a quantity no experiment could reach.

The principle nonetheless failed, in three distinct ways, and the failures are as instructive as the successes.

1. Self-refutation. The verification principle is not itself verifiable by any observation, so by its own criterion it is meaningless. No repair commanded agreement.

2. Holism. Quine argued that no individual statement can be confronted with experience on its own [Quine:1951]: a prediction follows only from a theory together with auxiliary hypotheses about apparatus, background and approximation, so a failed prediction refutes the conjunction and never says which conjunct to abandon. The analytic–synthetic distinction on which the positivists relied — truths of meaning versus truths of fact — does not survive the analysis either. Every anomalous result in this book illustrates the point: the anomalous perihelion of Mercury could in principle have been an unseen planet, and deciding otherwise took decades and independent evidence.

3. Verification is the wrong relation. A universal law has infinitely many instances and can never be verified by finitely many observations, but a single counterinstance refutes it. Popper therefore replaced verifiability by falsifiability as the criterion of scientific status [Popper:1959]. This is nothing but Equation (3.17) taken seriously, as Section 3.1.3 already noted.

Kuhn added the historical objection [Kuhn:1962]: observations are theory-laden, the auxiliary hypotheses are supplied by the reigning framework, and scientists abandon a framework not when a refutation arrives but when a better framework does.

The position this treatise takes

The programme did not survive, but its residue is the working philosophy of modern physics, and it is worth stating explicitly what this book has adopted from the wreckage.

1. Demarcation by testability, not by verifiability. Editorial rule 1 admits a subject when observation could in principle decide against it. That is why the Standard Model is in and string theory, supersymmetry and speculative quantum gravity are named only in Quantum Gravity: The Honest Status and only to record that the evidence is absent.

2. Operational meaning of quantities. A physical quantity is individuated by the procedure that measures it and the unit that reports it, which is why the SI is treated as axiomatic here (Measurement, SI Units, and the Theory of Errors) and why every experiment in this book carries apparatus, procedure and uncertainty.

3. Holism, taken as a bookkeeping obligation. Since no prediction confronts data alone, the auxiliary assumptions must be visible. That is the real function of editorial rule 2: a derivation is the complete list of what a prediction depends on, and a pending derivation is an admission that the list is not yet complete.

4. No final truth. Survival under attempted refutation is what the method certifies, never truth (Remark 1.2).

What this treatise does not do is settle the question the positivists thought they had dissolved: whether the unobservable structures of a successful theory — quantum states, gauge fields, spacetime curvature — are real, or are instruments for organizing observations. Where an interpretive dispute has observable consequences, it is an experimental question and is treated as one (Experiment: Bell Tests); where it has none, this book reports the competing readings and stops (Interpretations (Evidence-Anchored)). That restraint is itself the analytical inheritance: not every well formed question has an answer, and one of the uses of logic is to tell which.

There is a last, sharper lesson, and the following sections prove it rather than argue it. The Vienna Circle's ambition was a language for science in which every meaningful question could be settled by inspection of the world plus computation. Within four years of the manifesto, Gödel had shown that no such language exists even for arithmetic.

Formal systems and incompleteness

Hilbert's answer to the paradoxes (Section 3.6.4) was to make mathematical reasoning itself a mathematical object. Strip the meaning from a proof and what remains is a finite sequence of finite strings, each obtained from earlier ones by stated rules. Such an object can be studied with the same rigour as a triangle, and the study of it is metamathematics.

Formal systems

Everything in Definition 3.80 is finite and mechanical. Whether a given string is a formula, whether a given formula is an axiom, whether a given sequence is a derivation: each is settled by inspection, without understanding what the symbols mean. This is the whole point. A formal system is a game with tokens, and its trustworthiness rests on the fact that a clerk who understands nothing can check a proof.

“Mechanical procedure” is made precise in Section 3.9; until then the intuitive reading suffices. The condition excludes a cheap evasion of the theorems below — taking as axioms all true statements of arithmetic gives a complete theory, but no clerk could ever recognize its axioms, and it is therefore no use to anyone.

Consistency is indispensable, because an inconsistent system proves everything: from \(\varphi\) and \(\neg\varphi\) the tautology \((\varphi\wedge\neg\varphi)\rightarrow\psi\) — vacuously true since its antecedent is false by Equation (3.26) — yields any \(\psi\) whatever by modus ponens. A theory that proves everything distinguishes nothing and says nothing.

Equation (3.84) is weaker than Axiom 3.34. The axiom of Section 3.2.2 quantifies over all predicates on \(\N\), of which there are uncountably many by Theorem 3.71; Equation (3.84) provides one axiom for each of the countably many formulas of a first-order language. That gap between second-order and first-order induction is exactly where incompleteness will enter.

Completeness — what logic does deliver

Before the negative results, the positive one, and it is easy to confuse them because both are called “completeness”.

Full derivation in Appendix A.

Derives Theorem 3.84.

This says that the proof calculus of first-order logic misses nothing: semantic consequence and syntactic derivability coincide. Note carefully what it is about — the logic, not any particular theory. It says that whatever follows from the axioms of a theory can be proved from them. It does not say the axioms settle every question, and the theorem of the next subsection says they do not.

Arithmetization

Gödel's decisive move was to make arithmetic talk about itself. Assign to every symbol a number, to every finite string of symbols the number coding its sequence of symbols, and to every finite sequence of strings — that is, every derivation — a number coding it. Any injective coding with mechanically computable encoding and decoding will do; the choice matters as little as the choice of Kuratowski pairs in Remark 3.39. Write \(\ulcorner\varphi\urcorner\) for the numeral denoting the code of the formula \(\varphi\): its Gödel number.

Syntactic properties become arithmetical properties under this coding. “\(n\) codes a well formed formula”, “\(m\) codes a derivation of the formula coded by \(n\)” — these are conditions on numbers, decidable by finite computation, and for an effectively axiomatized theory they can be expressed by formulas of the language of arithmetic and proved of the right numbers inside PA. In particular there is a formula \(\mathrm{Prov}_{T}(x)\) of one free variable, the provability predicate, such that

The construction is elementary but long; it is carried out in Arithmetization and the Incompleteness Theorems.

Full derivation in Appendix A.

Derives Lemma 3.86.

The sentence \(\sigma\) asserts of its own Gödel number that it has the property \(\psi\); informally, \(\sigma\) says “I am \(\psi\)”. This is the diagonal argument of Section 3.5.2 once more, now applied to formulas indexed by their own codes, and it is the only sleight of hand in the entire subject. Nothing self-referential is smuggled in: \(\sigma\) is an ordinary arithmetical sentence about numbers, which happens to be true exactly when a certain number — its own code — has a certain computable property.

The first incompleteness theorem

Note what the theorem does not permit: patching. Adjoin \(G_{T}\) to \(T\) as a new axiom and the resulting theory \(T'=T+G_{T}\) is still effectively axiomatized, still consistent, still arithmetically adequate — so the theorem applies again and produces \(G_{T'}\), undecided by \(T'\). The gap cannot be closed by adding axioms, one at a time or infinitely many, so long as a clerk can recognize the axioms.

The second incompleteness theorem

Consistency is itself an arithmetical statement: \(T\) is consistent exactly when some particular sentence has no derivation, say

What the theorems do not say

Few results have been abused more, so the boundaries deserve stating as plainly as the theorems.

1. They do not exhibit an unknowable truth. We know \(G_{T}\) is true — Theorem 3.87 proves it, in a metatheory. The sentence is unprovable in \(T\), and provable in any reasonable stronger system; PA's Gödel sentence is a theorem of ZFC. Incompleteness is always relative to a fixed system.

2. They do not apply to every formal system. A theory must be effectively axiomatized, consistent, and strong enough to represent computation. Drop the last and complete decidable theories abound: the theory of dense linear orders, Presburger arithmetic — the naturals with addition but not multiplication [Presburger:1930] — and, most strikingly, Tarski's result that the first-order theory of the real closed fields, and with it all of elementary algebra and Euclidean geometry, is complete and decidable [Tarski:1951]. Multiplication together with addition on the integers is what tips a theory over the edge.

3. They do not show mathematics is inconsistent, or unreliable. They show a specific ambition — self-certification — is unattainable. See Section 3.10.

4. They do not settle whether minds exceed machines. Arguments that a human “sees” the truth of \(G_{T}\) while a machine cannot assume that the human's own reasoning is a consistent formal system and that we know which one; neither premise is available. The question is open and these theorems do not close it.

5. They do not by themselves make physics incomplete. A physical theory is not a formal system in the required sense, and its content is fixed by measurement rather than derivation. Genuine undecidability results in physics exist, and they come from computability (Section 3.9), not from Gödel numbering.

The sentence \(\lambda\) says “I am false”: it is the liar paradox, made into a theorem instead of a contradiction by locating the fault correctly. Truth for a language is definable, but only in a richer metalanguage — exactly the stratification anticipated in Remark 3.18. Provability, by contrast, is expressible in the object language, which is why Equation (3.86) exists. That asymmetry between truth and provability is the substance of incompleteness.

Computability and decidability

Two of Hilbert's demands survived Theorem 3.87: even if a theory cannot prove every truth, one might still hope for a mechanical procedure that decides, of any given sentence, whether it is provable. Hilbert and Ackermann posed this as das Entscheidungsproblem — the decision problem — and called it the principal problem of mathematical logic [Hilbert:1928]. Answering it required saying what a mechanical procedure is, a question nobody had needed to make precise. Three answers arrived within a year of one another, and they turned out to define the same class.

Turing machines

Turing's analysis began not with mathematics but with a description of a human computer at work: a person with a pencil, an unlimited supply of ruled paper, a finite number of states of mind, and a finite book of rules, attending to one square at a time [Turing:1937]. Idealizing this gives the following.

Nothing about this device is electronic, and nothing about it is fast. Its significance is that it is manifestly mechanical and just as manifestly unrestricted in the memory it may use — and that the machine itself, being finite, can be written down as a finite string and so coded by a number \(\ulcorner M\urcorner\), exactly as formulas were coded in Section 3.8.3.

Definition 3.81 can now be read literally: a theory is effectively axiomatized when its set of axioms is decidable. And a theory that is effectively axiomatized has a semi-decidable set of theorems — enumerate all finite derivations in order and watch for one ending in the target sentence — which is why \(\mathrm{Prov}_{T}\) of Equation (3.86) exists.

This is not a theorem and cannot be one, since “mechanical procedure” on the left is informal. It is an empirical and conceptual claim, and its support is the convergence of independent attempts: Church's \(\lambda\)-definable functions [Church:1936a], Kleene's general recursive functions [Kleene:1936], Post's combinatory processes [Post:1936] and Turing's machines all define the same class, and every model of computation proposed since — register machines, cellular automata, the physical computers on our desks, quantum computers — has been proved no more powerful in what it can compute at all, whatever the differences in efficiency.

Full derivation in Appendix A.

Derives Theorem 3.95.

The universal machine is why a computer is a general-purpose device rather than a special-purpose one, and it is the technological content of [Turing:1937]. For the present chapter its importance is that programs are data: a machine can be fed to a machine, including to itself.

The halting problem

That is the diagonal argument for the fourth time, and the family resemblance is now unmistakable: replace “does not contain itself” by “does not halt on its own code” and Russell becomes Turing; replace it by “is not provable” and Russell becomes Gödel.

Rice's theorem is the sweeping form of the bad news: no non-trivial question about what a program computes — as opposed to how it is written — is answerable by a general algorithm. Not “does it ever output zero”, not “does it compute the same function as this other program”, not “does it terminate on all inputs”.

The Entscheidungsproblem answered

Full derivation in Appendix A.

Derives Theorem 3.98.

The proof encodes the behaviour of a Turing machine into a first-order sentence which is valid if and only if the machine halts, reducing Theorem 3.96 to the decision problem. Hilbert's principal problem of mathematical logic thus has a negative answer, and the two negative answers fit together: by Theorem 3.84 the valid sentences are exactly the provable ones, so they are semi-decidable — search all derivations — but by Theorem 3.98 not decidable. A search that will succeed if there is anything to find, but that gives no sign of when to stop, is the best any general procedure can do.

The corresponding statement for arithmetic is sharper still: the set of true sentences of arithmetic is not even semi-decidable, which is Theorem 3.91 in computational dress.

Where decision procedures do exist

The negative results are about general procedures over all sentences of a sufficiently rich language. Restrict the language and algorithms reappear, sometimes spectacularly.

1. Propositional logic is decidable: build the truth table, as in Proposition 3.22. The cost is \(2^{n}\) rows for \(n\) propositions, and whether an essentially faster method exists is the P versus NP problem, still open.

2. Presburger arithmetic — the naturals with addition and order but without multiplication — is consistent, complete and decidable [Presburger:1930]. Multiplication is what makes arithmetic able to encode syntax, and hence what makes it incomplete.

3. Real closed fields. Tarski proved that the first-order theory of \((\R,+,\cdot,<)\) admits elimination of quantifiers and is therefore complete and decidable [Tarski:1951]. Every statement of elementary algebra and of Euclidean and analytic geometry expressible with real variables, polynomials, equalities, inequalities and quantifiers can be settled by algorithm. This is the technical foundation of computer algebra and of automated geometry; it also means that the real-number algebra a physicist actually manipulates sits on the decidable side of the line. The decision procedure is doubly exponential and rarely practical, but it exists.

The boundary between these islands and the undecidable ocean is sharp and somewhat surprising: the reals with addition and multiplication are decidable, the integers with addition are decidable, but the integers with addition and multiplication are not.

Undecidability inside physics

Physical questions can be phrased so as to encode computations, and when they are, they inherit undecidability. Three results, in increasing order of physical relevance.

1. Hilbert's tenth problem. There is no algorithm deciding whether an arbitrary polynomial equation in several variables with integer coefficients has an integer solution. Davis, Putnam and Robinson reduced the question to the arithmetic definability of exponential growth, and Matiyasevich completed the proof in 1970 by showing the Fibonacci sequence is Diophantine [Matiyasevich:1970] [Davis:1973]. Diophantine constraints are not exotic in physics — they govern commensurability of orbital periods, lattice matching conditions and anomaly-cancellation conditions on integer charges.

2. Tilings and ground states. Whether a finite set of tile shapes tiles the plane is undecidable [Berger:1966], and a tiling problem can be rewritten as the problem of finding the ground-state configuration of a classical lattice model with finite-range interactions. The ground-state energy density of a general such model is therefore not computable by any algorithm uniform in the model.

3. The spectral gap. Cubitt, Pérez-García and Wolf constructed a family of translationally invariant, nearest-neighbour Hamiltonians on a two-dimensional lattice of spins, depending on a parameter, such that determining whether the model is gapped or gapless in the thermodynamic limit is undecidable [Cubitt:2015]. The construction embeds a universal Turing machine in the low-energy physics: the model is gapped exactly when the encoded machine fails to halt.

Can mathematics be built without contradictions?

The question that opened the crisis can now be asked precisely, and answered precisely — though not in the form anyone wanted.

What Hilbert asked for

Hilbert's programme had a definite shape [Hilbert:1926]. Mathematics was to be split into a finitary part, concerning concrete finite configurations of symbols, whose meaning and reliability nobody doubts, and an ideal part — infinite sets, arbitrary real numbers, the whole Cantorian apparatus — introduced because it makes the theory smooth, in the way that points at infinity make projective geometry smooth. The programme demanded a proof, carried out by finitary means alone, that the ideal part never yields a false finitary statement. Consistency was the crux: an inconsistent system proves everything, so a consistency proof would license the entire ideal apparatus at one stroke, and the mathematician could then use infinite sets with a clear conscience while regarding them as convenient fictions.

Hilbert put the case in an address broadcast from Königsberg on 8 September 1930, ending with the words carved on his gravestone: we must know, we shall know [Hilbert:1930]. The previous day, at a conference in the same city, Gödel had mentioned to a roundtable that he could construct true but unprovable arithmetical statements. Almost nobody present grasped what they had heard.

1. Theorem 3.87 killed the hope that a single effectively axiomatized system could settle every arithmetical question.

2. Theorem 3.88 killed the programme proper: since finitary reasoning is certainly formalizable within PA, and PA cannot prove its own consistency, no finitary proof of the consistency of PA — let alone of analysis or set theory — can exist.

3. Theorem 3.98 killed the remaining hope of a mechanical decision procedure.

What survived: relative consistency

What did not die is the mathematical study of consistency, which became one of the most productive branches of logic. The trick is to stop demanding absolute certification and to measure systems against each other instead.

Gentzen proved in 1936 that Peano arithmetic is consistent [Gentzen:1936]. There is no contradiction with Theorem 3.88, because his proof is not carried out inside PA: it uses finitary reasoning plus one transfinite ingredient, induction along the ordinal

the first ordinal not reachable from \(\omega\) by finitely many exponentiations. Every proper initial segment of \(\varepsilon_{0}\) admits an induction principle provable in PA; \(\varepsilon_{0}\) itself does not, and that single step beyond is exactly what a consistency proof costs. The number \(\varepsilon_{0}\) is thereby a measurement of the strength of PA, and assigning such proof-theoretic ordinals to theories is now a discipline in its own right.

The same relativization organizes set theory. None of the following results asserts consistency outright; each transfers it:

The first two are Gödel's, by the constructible universe [Goedel:1938]; the third is Cohen's, by forcing [Cohen:1963]. Equation (3.102) runs one way only: ZFC proves the consistency of PA — it constructs a model, namely \(\N\) — and by Theorem 3.88 PA cannot return the favour, nor can ZFC certify itself. Stronger axioms of infinity extend the ladder upward indefinitely, each rung provably consistent relative to the ones above and never to itself.

The honest answer

Can mathematics be constructed without contradictions? The precise answers are these.

1. Almost certainly yes — but this cannot be proved from within, and never will be. Any proof of the consistency of a system strong enough for ordinary mathematics must use assumptions strictly stronger than the system it certifies, whose own consistency is then open. The regress does not terminate. Absolute self-certification is not merely undone; it is impossible.

2. Consistency is not an unknowable, though. It is a mathematical statement with a definite truth value, provable in stronger systems, refutable in principle by a single explicit derivation of \(0=1\), and studied quantitatively by ordinal analysis. What is unavailable is a proof using nothing but means we are already certain of.

How much of this reaches physics

Very little, and the reason is worth stating precisely rather than comfortingly.

The heavy axioms of ZFC — power set applied without limit, replacement, full choice — are what generate the exotic cardinals and the independence phenomena. Physics uses almost none of that. The programme of reverse mathematics determines, for each classical theorem, exactly which axioms are needed to prove it [Simpson:2009], and the answer for the mathematics of physics is consistently: far less than ZFC. The convergence of sequences, the intermediate value theorem, the existence and uniqueness of solutions to ordinary differential equations (Ordinary Differential Equations and Sturm–Liouville Theory), the Riemann and Lebesgue integrals, the spectral theorem for separable Hilbert spaces (Hilbert Spaces) — these live in weak subsystems of second-order arithmetic whose consistency strength is at or below that of PA itself. Physics never leaves the lower reaches of the hierarchy, and its mathematics is certified by Gentzen's theorem, not left waiting on the consistency of ZFC.

Suppose, nonetheless, that a contradiction in ZFC were found tomorrow. What would happen to physics? Essentially nothing. Every measured value in this book would still be what the apparatus reported, since a measurement is a physical event and not a theorem. The derivations would be re-examined and, in overwhelming likelihood, re-derived in a repaired system, because they never used the offending strength in the first place — exactly as the discovery that unrestricted comprehension is inconsistent (Theorem 3.75) invalidated not one line of Newtonian mechanics or one entry in a laboratory notebook. Foundations are the plumbing of mathematics; when plumbing fails it is replaced, and the building stands.