Tuesday, October 3, 2017

Infinite proofs

Consider this fun “proof” that 0=1:

      …

  • So, 3=4

  • So, 2=3

  • So, 1=2

  • So, 0=1.

What’s wrong with the proof? Each step follows from the preceding one, after all, and the only axiom used is an uncontroversial axiom of arithmetic that if x + 1 = y + 1 then x = y (by definition, 2 = 1 + 1, 3 = 1 + 1 + 1, 4 = 1 + 1 + 1 + 1 and so on).

Well, one problem is that intuitively a proof should have a beginning and an end. This one has an end, but no beginning. But that’s easily fixed. Prefix the above infinite proof with this infinite number of repetitions of “0=0”, to get:

  • 0=0

  • So, 0=0

  • So, 0=0

  • So, 0=0

      …

      …

  • So, 3=4

  • So, 2=3

  • So, 1=2

  • So, 0=1.

Now, there is a beginning and an end. Every step in the proof follows from a step before it (in fact, from the step immediately before it). But the conclusion is false. So what’s wrong?

The answer is that there is a condition on proofs that we may not actually bother to mention explicitly when we teach logic: a proof needs to have a finite number of steps. (We implicitly indicate this by numbering lines with natural numbers. In the above proof, we can’t do that: the “second half” of the proof would have infinite line numbers.)

So, our systems of proof depend on the notion of finitude. This is disquieting. The concept of finitude is connected to arithmetic (the standard definition of a finite set is one that can be numbered by a natural number). So is arithmetic conceptually prior to proof? That would be a kind of Platonism.

Interestingly, though, causal finitism—the doctrine that nothing can have an infinite causal history—gives us a metaphysical verificationist account of proof that does not presuppose Platonism:

  • A proof is a sequence of steps such that it is metaphysically possible for an agent to verify that each one followed by the rules from the preceding steps and/or the axioms by observation of each step.

For, given causal finitism, only a finite number of steps can be in the causal history of an act of verification of a proposition. (God can know all the steps in an infinite chain, but God isn’t an observer: an observer’s observational state is caused by the observations.)

2 comments:

Brandon said...

How do you see mathematical induction fitting into this context? It's at least sometimes characterized as if it were an infinite proof. On the other hand, perhaps the actual proof is a finite proof from the nature of the series to the properties of its parts, and not, as it is sometimes treated, as if it were a proof of infinite steps.

Alexander R Pruss said...

It's a finite proof making use of the axiom schema of induction. In fact, mathematical induction should be seen as a way of making something that looks like an infinite proof finite.