The Fabric of Reality David Deutch

particular way always have the same shape as corresponding triangles in

---

another class which we have defined differently. The ‘appropriate
circumstances’ that give this conclusion the status of proof are, in physical
terms, that the symbols appear on a page underneath other symbols (some
of which represent axioms of Euclidean geometry) and that the pattern in
which the symbols appear conforms to certain rules, namely the rules of
inference.
But which rules of inference should we use? This is like asking how we
should program the virtual-reality generator to make it render the world of
Euclidean geometry. The answer is that we must use rules of inference
which, to the best of our understanding, will cause our symbols to behave, in
the relevant ways, like the abstract entities they denote. How can we be sure
that they will? We cannot. Suppose that some critics object to our rules of
inference because they think that our symbols will behave differently from
the abstract entities. We cannot appeal to the authority of Aristotle or Plato,
nor can we prove that our rules of inference are infallible (quite apart from
Gödel’s theorem, this would lead to an infinite regress, for we should first
have to prove that the method of proof that we used was itself valid). Nor
can we haughtily tell the critics that there must be something wrong with their
intuition, because 
our intuition says that the symbols will mimic the abstract
entities perfectly. All we can do is explain. We must explain why we think
that, under the circumstances, the symbols will behave in the desired way
under our proposed rules. And the critics can explain why they favour a rival
theory. A disagreement over two such theories is, in part, a disagreement
about the observable behaviour of physical objects. Such disagreements
can be addressed by the normal methods of science. Sometimes they can
be readily resolved; sometimes not. Another cause of such a disagreement
could be a conceptual clash about the nature of the abstract entities
themselves. Then again, it is a matter of rival explanations, this time about
abstractions rather than physical objects. Either we could come to a common
understanding with our critics, or we could agree that we were discussing
two different abstract objects, or we could fail to agree. There are no
guarantees. Thus, contrary to the traditional belief, it is not the case that
disputes within mathematics can always be resolved by purely procedural
means.
A conventional symbolic proof seems at first sight to have quite a different
character from the ‘hands-on’ virtual-reality sort of proof. But we see now
that they are related in the way that computations are to physical
experiments. Any physical experiment can be regarded as a computation,
and any computation is a physical experiment. In both sorts of proof,
physical entities (whether in virtual reality or not) are manipulated according
to rules. In both cases the physical entities represent the abstract entities of
interest. And in both cases the reliability of the proof depends on the truth of
the theory that physical and abstract entities do indeed share the appropriate
properties.
We can also see from the above discussion that proof is a physical 
process.
In fact, a proof is a type of computation. ‘Proving’ a proposition means
performing a computation which, if one has done it correctly, establishes that
the proposition is true. When we use the word ‘proof’ to denote an 
object,
such as an ink-on-paper text, we mean that the object can be used as a
program for recreating a computation of the appropriate kind.

---

It follows that neither the theorems of mathematics, nor the process of
mathematical proof, nor the experience of mathematical intuition, confers
any certainty. Nothing does. Our mathematical knowledge may, just like our
scientific knowledge, be deep and broad, it may be subtle and wonderfully
explanatory, it may be uncontroversially accepted; but it cannot be certain.
No one can guarantee that a proof that was previously thought to be valid
will not one day turn out to contain a profound misconception, made to seem
natural by a previously unquestioned ‘self-evident’ assumption either about
the physical world, or about the abstract world, or about the way in which
some physical and abstract entities are related.
It was just such a mistaken, self-evident assumption that caused geometry
itself to be mis-classified as a branch of mathematics for over two millennia,
from about 300 BC when Euclid wrote his 
Elements, to the nineteenth
century (and indeed in most dictionaries and schoolbooks to this day).
Euclidean geometry formed part of every mathematician’s intuition.
Eventually some mathematicians began to doubt that one in particular of
Euclid’s axioms was self-evident (the so-called ‘parallel axiom’). They did
not, at first, doubt that this axiom was true. The great German mathematician
Carl Friedrich Gauss is said to have been the first to put it to the test. The
parallel axiom is required in the proof that the angles of a triangle add up to
180°. Legend has it that, in the greatest secrecy (for fear of ridicule), Gauss
placed assistants with lanterns and theodolites at the summits of three hills,
the vertices of the largest triangle he could conveniently measure. He
detected no deviation from Euclid’s predictions, but we now know that that
was only because his instruments were not sensitive enough. (The vicinity of
the Earth happens to be rather a tame place geometrically.) Einstein’s
general theory of relativity included a new theory of geometry that
contradicted Euclid’s and has been vindicated by experiment. The angles of
a real triangle really do 
not necessarily add up to 180°: the true total
depends on the gravitational field within the triangle.
A very similar mis-classification has been caused by the fundamental
mistake that mathematicians since antiquity have been making about the
very nature of their subject, namely that mathematical knowledge is more
certain than any other form of knowledge. Having made that mistake, one
has no choice but to classify proof theory as part of mathematics, for a
mathematical theorem could not be certain if the theory that justifies its
method of proof were itself uncertain. But as we have just seen, proof theory
is not a branch of mathematics — it is a science. Proofs are not abstract.
There is no such thing as abstractly proving something, just as there is no
such thing as abstractly calculating or computing something. One can of
course define a class of abstract entities and call them ‘proofs’, but those
‘proofs’ cannot verify mathematical statements because no one can see
them. They cannot persuade anyone of the truth of a proposition, any more
than an abstract virtual-reality generator that does not physically exist can
persuade people that they are in a different environment, or an abstract
computer can factorize a number for us. A mathematical ‘theory of proofs’
would have no bearing on which mathematical truths can or cannot be
proved in reality, just as a theory of abstract ‘computation’ has no bearing on
what mathematicians — or anyone else — can or cannot calculate in reality,
unless there is a separate, empirical reason for believing that the abstract

---

‘computations’ in the theory resemble real computations. Computations,
including the special computations that qualify as proofs, are physical
processes. Proof theory is about how to ensure that those processes
correctly mimic the abstract entities they are intended to mimic.
Gödel’s theorems have been hailed as ‘the first new theorems of pure logic
for two thousand years’. But that is not so: Gödel’s theorems are about what
can and cannot be proved, and proof is a physical process. Nothing in proof
theory is a matter of logic alone. The new way in which Gödel managed to
prove general assertions about proofs depends on certain assumptions
about which physical processes can or cannot represent an abstract fact in a
way that an observer can detect and be convinced by. Gödel distilled such
assumptions into his explicit and tacit justification of his results. His results
were self-evidently justified, not because they were ‘pure logic’ but because
mathematicians found the assumptions self-evident.
One of Gödel’s assumptions was the traditional one that a proof can have
only a finite number of steps. The intuitive justification of this assumption is
that we are finite beings and could never grasp a literally infinite number of
assertions. This intuition, by the way, caused many mathematicians to worry
when, in 1976, Kenneth Appel and Wolfgang Haken used a computer to
prove the famous ‘four-colour conjecture’ (that using only four different
colours, any map drawn in a plane can be coloured so that no two adjacent
regions have the same colour). The program required hundreds of hours of
computer time, which meant that the steps of the proof, if written down,
could not have been read, let alone recognized as self-evident, by a human
being in many lifetimes. ‘Should we take the computer’s word for it that the
four-colour conjecture is proved?’, the sceptics wondered — though it had
never occurred to them to catalogue all the firings of all the neurons in their
own brains when they accepted a relatively ‘simple’ proof.
The same worry may seem more justified when applied to a putative proof
with an infinite number of steps. But what is a ‘step’, and what is ‘infinite’? In
the fifth century BC Zeno of Elea concluded, on the basis of a similar
intuition, that Achilles will never overtake the tortoise if the tortoise has a
head start. After all, by the time Achilles reaches the point where the tortoise
is now, it will have moved on a little. By the time he reaches 
that point, it will
have moved a little further, and so on 
ad infinitum. Thus the ‘catching-up’
procedure requires Achilles to perform an infinite number of catching-up
steps, which as a finite being he supposedly cannot do. But what Achilles
can do cannot be discovered by pure logic. It depends entirely on what the
governing laws of physics say he can do. And if those laws say he will
overtake the tortoise, then overtake it he will. According to classical physics,
catching up requires an infinite number of steps of the form ‘move to the
tortoise’s present location’. In that sense it is a computationally infinite
operation. Equivalently, considered as a proof that one abstract quantity
becomes larger than another when a given set of operations is applied, it is
a proof with an infinite number of steps. But the relevant laws designate it as
a physically finite process — and that is all that counts.
Gödel’s intuition about steps and finiteness does, as far as we know, capture
real physical constraints on the process of proof. Quantum theory requires
discrete steps, and none of the known ways in which physical objects can
interact would allow for an infinite number of steps to precede a measurable

---

conclusion. (It might, however, be possible for an infinite number of steps to
be completed in the whole history of the universe — as I shall explain in
Chapter 14.) Classical physics would not have conformed to these intuitions
if (impossibly) it had been true. For example, the continuous motion of
classical systems would have allowed for ‘analogue’ computation which did
not proceed in steps and which had a substantially different repertoire from
the universal Turing machine. Several examples are known of contrived
classical laws under which an infinite amount of computation (infinite, that is,
by Turing-machine or quantum-computer standards) could be performed by
physically finite methods. Of course, classical physics is incompatible with
the results of countless experiments, so it is rather artificial to speculate on
what the ‘actual’ classical laws of physics ‘would have been’; but what these
examples show is that one cannot 
prove, independently of any knowledge of
physics, that a proof must consist of finitely many steps. The same
considerations apply to the intuition that there must be finitely many rules of
inference, and that these must be ‘straightforwardly applicable’. None of
these requirements is meaningful in the abstract: they are physical
requirements. Hilbert, in his influential essay ‘On the Infinite’,
contemptuously ridiculed the idea that the ‘finite-number-of-steps’
requirement is a substantive one. But the above argument shows that he
was mistaken: it is substantive, and it follows only from his and other
mathematicians’ 
physical intuition.
At least one of Gödel’s intuitions about proof turns out to have been
mistaken; fortunately, it happens not to affect the proofs of his theorems. He
inherited it intact from the prehistory of Greek mathematics, and it remained
unquestioned by every generation of mathematicians until it was proved
false in the 1980s by discoveries in the quantum theory of computation. It is
the intuition that a proof is a particular type of 
object, namely a sequence of
statements that obey rules of inference. I have already argued that a proof is
better regarded not as an object but as a process, a type of computation. But
in the classical theory of proof or computation this makes no fundamental
difference, for the following reason. If we can go through the process of a
proof, we can, with only a moderate amount of extra effort, keep a record of
everything relevant that happens during that process. That record, a physical
object, will constitute a proof in the sequence-of-statements sense. And
conversely, if we have such a record we can read through it, checking that it
satisfies the rules of inference, and in the process of doing so we shall have
proved the conclusion. In other words, in the classical case, converting
between proof processes and proof objects is always a tractable task.
Now consider some mathematical calculation that is intractable on all
classical computers, but suppose that a quantum computer can easily
perform it using interference between, say, 10 500 universes. To make the
point more clearly, let the calculation be such that the answer (unlike the
result of a factorization) cannot be tractably verified once we have it. The
process of programming a quantum computer to perform such a
computation, running the program and obtaining a result, constitutes a proof
that the mathematical calculation has that particular result. But now there is
no way of keeping a record of everything that happened during the proof
process, because most of it happened in other universes, and measuring the
computational state would alter the interference properties and so invalidate

---

the proof. So creating an old-fashioned proof 
object would be infeasible;
moreover, there is not remotely enough material in the universe as we know
it to make such an object, since there would be vastly more steps in the
proof than there are atoms in the known universe. This example shows that
because of the possibility of quantum computation, the two notions of proof
are not equivalent. The intuition of a proof as an object does not capture all
the ways in which a mathematical statement may in reality be proved.
Once again, we see the inadequacy of the traditional mathematical method
of deriving certainty by trying to strip away every possible source of
ambiguity or error from our intuitions until only self-evident truth remains.
That is what Gödel had done. That is what Church, Post and especially
Turing had done when trying to intuit their universal models for computation.
Turing hoped that his abstracted-paper-tape model was so simple, so
transparent and well defined, that it would not depend on any assumptions
about physics that could conceivably be falsified, and therefore that it could
become the basis of an abstract theory of computation that was independent
of the underlying physics. ‘He thought,’ as Feynman once put it, ‘that he
understood paper.’ But he was mistaken. Real, quantum-mechanical paper
is wildly different from the abstract stuff that the Turing machine uses. The
Turing machine is entirely classical, and does not allow for the possibility that
the paper might have different symbols written on it in different universes,
and that those might interfere with one another. Of course, it is impractical to
detect interference between different states of a paper tape. But the point is
that Turing’s intuition, because it included false assumptions from classical
physics, caused him to abstract away some of the 
computational properties
of his hypothetical machine, the very properties he intended to keep. That is
why the resulting model of computation was incomplete.
That mathematicians throughout the ages should have made various
mistakes about matters of proof and certainty is only natural. The present
discussion should lead us to expect that the current view will not last for
ever, either. But the confidence with which mathematicians have blundered
into these mistakes and their inability to acknowledge even the possibility of
error in these matters are, I think, connected with an ancient and widespread
confusion between the 
methods of mathematics and its subject-matter. Let
me explain. Unlike the relationships between physical entities, relationships
between abstract entities are independent of any contingent facts and of any
laws of physics. They are determined absolutely and objectively by the
autonomous properties of the abstract entities themselves. Mathematics, the
study of these relationships and properties, is therefore the study of
absolutely necessary truths. In other words, the truths that mathematics
studies are absolutely certain. But that does not mean that our knowledge of
those necessary truths is itself certain, nor does it mean that the methods of
mathematics confer necessary truth on their conclusions. After all,
mathematics also studies falsehoods and paradoxes. And that does not
mean that the conclusions of such a study are necessarily false or
paradoxical.
Necessary truth is merely the 
subject-matter of mathematics, not the reward
we get for doing mathematics. The objective of mathematics is not, and
cannot be, mathematical certainty. It is not even mathematical truth, certain
or otherwise. It is, and must be, mathematical explanation.

---

Why, then, does mathematics work as well as it does? Why does it lead to
conclusions which, though not certain, can be accepted and applied
unproblematically for millennia at least? Ultimately the reason is that 
some of
our knowledge of the physical world is also that reliable and uncontroversial.
And when we understand the physical world sufficiently well, we also
understand which physical objects have properties in common with which
abstract ones. But in principle the reliability of our knowledge of mathematics
remains subsidiary to our knowledge of physical reality. Every mathematical
proof depends absolutely for its validity on our being right about the rules
that govern the behaviour of some physical objects, be they virtual-reality
generators, ink and paper, or our own brains.
So mathematical intuition is a species of physical intuition. Physical intuition
is a set of rules of thumb, some perhaps inborn, many built up in childhood,
about how the physical world behaves. For example, we have intuitions that
there are such things as physical objects, and that they have definite
attributes such as shape, colour, weight and position in space, some of
which exist even when the objects are unobserved. Another is that there is a
physical variable — time — with respect to which attributes change, but that
nevertheless objects can retain their identity over time. Another is that
objects interact, and that this can change some of their attributes.
Mathematical intuition concerns the way in which the physical world can
display the properties of abstract entities. One such intuition is that of an
abstract law, or at least an explanation, that underlies the behaviour of
objects. The intuition that space admits closed surfaces that separate an
‘inside’ from an ‘outside’ may be refined into the mathematical intuition of a
set, which partitions everything into members and non-members of the set.
But further refinement by mathematicians (starting with Russell’s refutation
of Frege’s set theory) has shown that this intuition ceases to be accurate
when the sets in question contain ‘too many’ members (too large a degree of
infinity of members).
Even if any physical or mathematical intuition were inborn, that would not
confer any special authority upon it. Inborn intuition cannot be taken as a
surrogate for Plato’s ‘memories’ of the world of Forms. For it is a
commonplace observation that many of the intuitions built into human beings
by accidents of evolution are simply false. For example, the human eye and
its controlling software implicitly embody the false theory that yellow light
consists of a mixture of red and green light (in the sense that yellow light
gives us exactly the same sensation as a mixture of red light and green light
does). In reality, all three types of light have different frequencies and cannot
be created by mixing light of other frequencies. The fact that a mixture of red
and green light appears to us to be yellow light has nothing whatever to do
with the properties of light, but is a property of our eyes. It is the result of a
design compromise that occurred at some time during our distant ancestors’
evolution. It is just possible (though I do not believe it) that Euclidean
geometry or Aristotelian logic are somehow built into the structure of our
brains, as the philosopher Immanuel Kant believed. But that would not
logically imply that they were true. Even in the still more implausible event
that we have inborn intuitions that we are constitutionally unable to shake
off, such intuitions would still not be necessary truths.

---

The fabric of reality, then, does have a more unified structure than would
have been possible if mathematical knowledge had been verifiable with
certainty, and hence hierarchical, as has traditionally been assumed.
Mathematical entities are part of the fabric of reality because they are
complex and autonomous. The sort of reality they form is in some ways like
the realm of abstractions envisaged by Plato or Penrose: although they are
by definition intangible, they exist objectively and have properties that are
independent of the laws of physics. However, it is physics that allows us to
gain knowledge of this realm. And it imposes stringent constraints. Whereas
everything in physical reality is comprehensible, the comprehensible
mathematical truths are precisely the infinitesimal minority which happen to
correspond exactly to some physical truth — like the fact that if certain
symbols made of ink on paper are manipulated in certain ways, certain other
symbols appear. That is, they are the truths that can be rendered in virtual
reality. We have no choice but to assume that the incomprehensible
mathematical entities are real too, because they appear inextricably in our
explanations of the comprehensible ones.
There are physical objects — such as fingers, computers and brains —
whose behaviour can model that of certain abstract objects. In this way the
fabric of physical reality provides us with a window on the world of
abstractions. It is a very narrow window and gives us only a limited range of
perspectives. Some of the structures that we see out there, such as the
natural numbers or the rules of inference of classical logic, seem to be
important or ‘fundamental’ to the abstract world, in the same way as deep
laws of nature are fundamental to the physical world. But that could be a
misleading appearance. For what we are really seeing is only that some
abstract structures are fundamental 
to our understanding of abstractions.
We have no reason to suppose that those structures are objectively
significant in the abstract world. It is merely that some abstract entities are
nearer and more easily visible from our window than others.
TERMINOLOGY
mathematics The study of absolutely necessary truths.
proof A way of establishing the truth of mathematical propositions.
(Traditional definition:) A sequence of statements, starting with some
premises and ending with the desired conclusion, and satisfying certain
‘rules of inference’.
(Better definition:) A computation that models the properties of some
abstract entity, and whose outcome establishes that the abstract entity has a
given property.
mathematical intuition (Traditionally:) An ultimate, self-evident source of
justification for mathematical reasoning.
(Actually:) A set of theories (conscious and unconscious) about the
behaviour of certain physical objects whose behaviour models that of
interesting abstract entities.
intuitionism The doctrine that all reasoning about abstract entities is
untrustworthy except where it is based on direct, self-evident intuition. This is

---

the mathematical version of solipsism.
Hilbert’s tenth problem To ‘establish once and for all the certitude of
mathematical methods’ by finding a set of rules of inference sufficient for all
valid proofs, and then proving those rules consistent by their own standards.
Gödel’s incompleteness theorem A proof that Hilbert’s tenth problem cannot
be solved. For any set of rules of inference, there are valid proofs not
designated as valid by those rules.
SUMMARY
Abstract entities that are complex and autonomous exist objectively and are