This chapter will bring a wider view of formal systems by introducing those that have an infinite number of axioms. We shall later see the consequences of such systems and the power of proof against an exhaustive truth-value check (as introduced here) of all the theorems, usually infinite in number, that are generated by the production rules of the system. The discussion is set into motion by an interesting formal system called a pq-system consisting of a definition and a rule of production:

  • DEFINITION: {x}p-q{x}– is an axiom, whenever {x} is composed of hyphens only.
  • RULE: Suppose {x\text{, } y} and {z} all stand for particular strings containing only hyphens. And suppose that {x}p{y}q{z} is known to be a theorem. Then {x}p{y}-q{z}– is also a theorem.

Since the definition above conveys the symbol {x} as a string consisting only of hyphens of any arbitrary amount, there does exist an infinite number of axioms. Examples of some of the axioms of the system are {-p--q---} and {---p----q-------}. If one tries to produce a sizable amount of possible axioms and theorems, then a pattern emerges that gives a criteria for theoremhood. A string qualifies as a theorem when it obeys the pattern such that the first two hyphen groups add up to the third. For example, the strings {--p---q----} and {-p---q----} are both qualified as theorems since the number of hyphens before and after p is equal to the number of hyphens after q.

As a bit of a digression, the chapter discusses two ways of how formal systems are constructed or extended. The first is the bottom-up approach where one starts from the bottommost axioms then constructs the system towards higher levels by producing all the other statements of the system. The second way is called the top-down approach which is the opposite of the bottom-up method. One instead starts from a given set of theorems then makes a step-back to find a smaller set of statements that could have produced the larger initial set. This is usually done by finding the common properties that the initial set of theorems have. Once these properties are found, one can create a smaller set of theorems pertaining to the properties that were found. The process is repeated until the current set of theorems cannot be broken down further to produce more fundamental ones. The most fundamental set will then be established as the axioms of the system.

The top-down approach reminds me of the remarkable progress in the history of our understanding of the universe and the physical processes within it. It has been a common state of affairs in physics when seemingly different physical phenomena can actually be explained by a few rules governing their paradigms. Isaac Newton, in probably one of the most important discoveries of all time, concluded that the force that makes the planets move around the sun is the same force that makes everything fall back to the Earth. James Clerk Maxwell unified, what seemed to be in his time, the independent phenomena of electricity and magnetism into a set of four equations that describes all conceivable electromagnetic phenomena. Albert Einstein reckoned that accelerated reference frames are no different to ones experiencing gravitational fields. Finally, all the observed particles in physics experiments can be classified and explained by a more general theory about the elementary particles called the Standard Model.

Notice that the criteria for theoremhood given above for the pq-system gives a correspondence with the addition of integers in mathematics. This correspondence happens when we map each of the symbols in the system as follows:

  • p {\Leftrightarrow} plus
  • q {\Leftrightarrow} equals
  • {-} {\Leftrightarrow} one
  • {--} {\Leftrightarrow} two.. and so on.

The mappings described above are called isomorphisms. Isomorphisms play a major role in mathematics and physics because it allows seemingly different systems to be expressed and interpreted in many ways. Thus it is through isomorphisms that systems acquire meaning, just as how the pq-system illustrates the addition of integers. A formal system standing on its own and having no relationship at all with other formal systems or some aspect of reality is deemed to be meaningless. If it weren’t for Newton who brought into being an isomorphism between the rates of change and constant quantities of calculus as signifying the state variables and conserved quantities in classical mechanics, then physics as it stands today could not be done. Furthermore, if it weren’t also for the same guy whose isomorphism that the force that makes things fall down towards the earth is the same force that drives the planets in their orbits, then our understanding of the cosmos would be bleak.

An important point to make at this point is that there can be any number of plausible isomorphisms among many formal systems. This alludes to the idea that a formal system can have many interpretations. Consider the formalism of quantum mechanics governed by the language of Hilbert spaces and non-commutative algebra. Different interpretations and formulations have been found for the field as a whole. To name a few, we have the Copenhagen interpretation, the Many-Worlds interpretation, the Heisenberg matrix formulation and the Schrodinger dynamical formulation. These give different meanings for the same physical reality that quantum mechanics dominates on.

How can we be sure that all the theorems of the pq-system will be isomorphic to the operation of addition, i.e. the first two hyphen groups will always add up to the third one? As was stated in a previous post, one will have to go through an infinite amount of inconvenience checking an infinite number of theorems to prove this. But is this proof-by-evidence always necessary? Not at all. Let me illustrate a proof that any integer is either a prime or a product of primes without having to check each of the infinite number of integers. (An integer {n} is called a prime if {n > 1} and if the only positive divisors of {n} are 1 and {n}.

Theorem. Every integer n > 1 is either a prime or a product of primes.
Proof: We use induction on n. The theorem holds trivially for n = 2. Assume it is true for every integer {k} with {1 < k < n}. If {n} is not prime, it has a positive divisor {d} with {1 < d < n}. Hence {n = cd}, where {1 < c < n}. Since both {c} and {d} are less than {n}, each is a prime or a product of primes; hence {n} is a product of primes and is therefore not a prime. This proves our initial assumption and thus proves the theorem. \Box

The proof above applies to all the integers by using the symbols {n}, {k}, {c} and {d} as placeholders for any integer. There was no need to verify the theorem for every integer to arrive at its truth, and the proof does this well. This is why it is called proof rather than just hard evidence. I would just like to mention that in physics, the proofs of theories are done by having their predictions agree with experiments. This manner of proof isn’t as clear cut and exact as those in mathematical proofs where pure logic is used. We have to introduce errors and statistical outliers in our measurements, but nevertheless, the average data must agree with the values predicted by theory.

At the bottom of it all, we are guided by rules which we never make explicit. Our brains fire a huge number of neurons in order to execute even the simplest thought processes. Clearly, our reasoning seems to be governed by an utterly complex formal system that we have yet still to find or read about further in the book. The chapter ends by an outrageous and humorous dialogue of Achilles talking to himself. Most of the statements are barely comprehensible since I think the author is trying to show two Achilleses that are trying to interpret themselves and their thought processes by conversing with each other, but to no avail. Finding the reasons behind one’s reasoning is indeed a difficult, if not impossible, intellectual undertaking. We hope to learn more about this in the next chapters.

References:
Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books.
Apostol, Tom M. (1977), Mathematical Analysis, 2nd ed., Addison-Wesley.