Stanley Tennenbaum
American Original

4. Logic versus Arithmetic

At this point I’m going to leave the stories of Stan and Errett to interject a simple explanation of the central issue, the incompatibility of two core mathematical structures: classical logic with LEM, and numbers with their arithmetic. All the numbers we consider will be positive integers. Bishop, and Brouwer before him, saw numbers as objects that can be added, multiplied, divided, subtracted by expressing them in standard decimal notation. In his farewell address of 1973, Bishop put it like this:

The Constructivist Thesis. Every integer can be converted in principle to decimal form by a finite, purely routine, process.

Bishop didn’t want to sound like a computer scientist, so he always said “finite, purely routine, process” instead of “algorithm”,

I’d prefer to put the Thesis in a style that Bishop often used, where one asks, What must be done to construct a number? and answers with:

The Constructivist Thesis-Algorithmic Style. To construct a number you must provide data along with an algorithm which will convert—at least in principle—the data into a decimal representation, a finite sequence of the digits 0 through 9. The simplest case is when the data itself is a decimal representation, which the algorithm just passes along.

“In principle” means that while you can describe the algorithm, it might not be realistic to start it running and wait for the result. In practice the algorithm is often obvious and not mentioned, as in: Let n be the number of prime numbers less than 1010.

In either formulation the point is that numbers can be put in decimal form, which allows us to do arithmetic with them (provided we remember our tables and algorithms). We’re now going to verify what Brouwer first showed: the conflict between classical logic and arithmetic. LEM introduces numbers that you can’t do arithmetic with.

Theorem. LEM and the Constructivist Thesis are Inconsistent.
Brouwer’s Proof:
Brouwer uses LEM to construct a number q that cannot be converted to decimal notation because it encodes ignorance:

  • Take your favorite unsolved mathematical problem. There are zillions of them. I’ll pick the Riemann Hypothesis about the zeros of the zeta function.
  • If the Riemann Hypothesis is true, then let q = 1.
  • If the Riemann Hypothesis is false, then let q = 0.
  • LEM says that the Riemann Hypothesis is either true or false.
  • So either q = 0 or q = 1.
  • Since 0 and 1 are numbers, q is a number in either case.
  • Proof by cases: q is a number, period.
  • But we have no algorithm to compute the decimal representation of q. No algorithm to determine if the Riemann Hypothesis is true.
  • Contradiction, coming from the Thesis and LEM.

It may be worth noting that our construction of q does construct something, just not a number. It can be described as a non-empty subset of {0, 1} with at most one element. Knowing that the statement “q is empty” is false is of no help in constructing an element of q. Close, but no cigar.

This completes the proof that the Constructivist Thesis and LEM are contradictory: you can’t have both of them. If you accept LEM, you must admit numbers which do not appear in the tables. Thus the split.

Brouwer’s intuitionists and Bishop’s constructivists chose the Thesis, which gives a clear understanding of numbers. A new logic for doing constructive mathematics was needed. Brouwer defined the proper logic, called intuitionist, for Brouwer’s philosophy. But the definition lacked a compelling structure comparable to the truth tables that give shape to classical logic. In the 1930s a beautiful foundation was found for intuitionist logic, called Natural Deduction, which describes the logical connective in terms of rules for introduction and elimination.

Most mathematicians have chosen to remain with LEM, and accept that it admits numbers with which we cannot compute, and to try to avoid such numbers on an ad hoc basis.

A this point I’m going to return to Stan in Las Cruces and consider some qualities of Stan that enabled him to succeed, sometimes with corresponding qualities of Errett that led to his failure.