## Saturday, February 13, 2010

### Evidentiary and deductive reasoning

Evidentiary and deductive reasoning are two related but substantively different modes of reasoning.

Deductive reasoning is the reasoning mathematicians typically use, at least when they are creating proofs. We use deductive reasoning when we one or more statements as axiomatic*, i.e. "true" a priori or by definition, and we serially apply a specific, finite set of mechanical inference or transformation rules to those statements, one rule at a time. A set of axioms and inference rules comprises a formal system. By definition, the theorems, i.e. any and every statement generated in this manner, regardless of the order the inference rules were applied, is also "true". Douglas Hofstadter goes into the deductive process in great detail in his book, GĂ¶del, Escher, Bach: An Eternal Golden Braid. Simple deductive systems typically use propositional calculus or first-order logic as the inference rules, so we typically distinguish different systems by their axioms. Start with Euclid's axioms and you have plane geometry; start with Peano's axioms and you have natural arithmetic.

*We can also use an axiom schema, a rule for producing axioms. We can, however, consider an axiom schema as a simple formal system with no loss of generality.

Using deductive reasoning, I can write a simple computer program to print out true theorems of any deductive system faster than a roomful of mathematicians. The inference rules are mechanical and deterministic: each inference rule produces exactly one output for any given input. Therefore I can write a computer program that takes the first axiom, and applies the first inference rule on that axiom to generate a theorem and prints the theorem. Then program then applies the second inference rule to the axiom and prints out that theorem. Once we've applied each inference rule to the first axiom, we apply each inference rule to the second axiom, and so forth. We then repeat the process of applying each inference rule to the theorems generated in the first round. If we have an infinite amount of memory (to remember all the theorems we've generated) and an infinite amount of time, we will print every theorem of the formal system.

But of course we don't have infinite memory and time. In fact, with this brute-force method we will quickly exhaust even a universe-scale computer before we ever get to an "interesting" theorem, such as the theorem of arithmetic that there are infinitely many prime numbers. We might never even get to "1+1=2"! Cleverness in deductive reasoning consists of finding the chain of inference rules that leads to "interesting" theorems. (Indeed two extremely clever people, Alfred North Whitehead and Bertrand Russell, require 362 pages to lay the groundwork to prove that 1+1=2, and do not complete the proof until 86 pages into the second volume. We would require Knuth notation to describe the number of universes required to find this proof by brute force.)

The deductive method poses some deep and interesting philosophical problems, but if we use simple enough inference rules , we always know with absolute certainty that our theorems are "true"... or at least they are as "true" as our axioms. (Philosophers typically more-or-less understand and use first-order logic, which is known to be consistent, and known to be insufficiently powerful to express all "interesting" conjectures. Mathematicians, I suspect, roll their eyes in tolerant amusement when philosophers get all excited about the self-referential weirdnesses in more more powerful systems.)

But we don't always know, or cannot arbitrarily specify, a set of axioms and inference rules; all we know are the "theorems". This is basically the situation we're in regarding our experience: our experiences are like theorems, and our goal is to discover the inference rules (basic and abstract natural laws) and/or the starting premises (what happened in the past) that connect these experiences. In these cases, because we do not have well-defined and pre-specified axioms and inference rules, we must use evidentiary reasoning. The experiences or "theorems" are the evidence, and we want to discover the axioms (or at least other theorems) and inference rules that connect and explain that evidence.

(Philosophers made a valiant effort to put science on a purely deductive footing with Naive Empiricism (a.k.a. Logical Positivism): our observations are axioms, we use the "universal" a priori rules of logic as our inference rules, and attempt to deduce the underlying natural laws and earlier conditions using this formal system. Unfortunately, it didn't work, for a lot of reasons.)

We still use deduction in evidentiary reasoning, because we want to express the connections and explanations with the same sort of mechanistic, deterministic rigor that characterizes deductive reasoning. But in evidentiary reasoning, deduction is only a part of the process; it's not helpful to say that the deductive theorems are just as "true" as the axioms, because we're in doubt about the axioms and inference rules themselves.

We find it convenient to separate evidentiary reasoning into two primary modes. The first mode is to discover inference rules. A convenient and efficient way to discover inference rules is to use experimental science: very precisely observe (or experience) what's "true" at one point in time, wait, then observe what's true a little later, and propose inference rules ("laws of nature") that would rigorously explain the transformation. The controlled experiment refines this process even further, since it's very difficult to actually observe everything that's true at any point in time. Instead we create two situations that are as alike as possible in all but one element, and then a little later observe what's true about those situations, and propose inference rules to rigorously explain the difference in the outcomes in terms of the difference in the initial conditions.

The second mode is to discover the initial or preceding conditions when we can observe only the resulting conditions. A convenient and efficient way to discover preceding conditions is historical science: take the inference rules we have discovered from experimental science and propose initial conditions that those inference rules would have transformed into what we presently observe.

Evidentiary reasoning appears much more difficult that deductive reasoning, at least to do consciously. In every literate culture, we see the development of mathematics follow almost instantly on the heels of literacy. It took Western European culture, however, nearly two thousand years of literacy and mathematics to develop and codify evidentiary reasoning, and (AFAIK) no other culture independently developed and codified evidentiary reasoning and used it on a large scale.

On the other hand, perhaps paradoxically, evidentiary reasoning does not require consciousness or codification. Biological evolution itself is an "evidentiary" process: we try out different "formal systems" (biological arrangements of brains) at random; organisms with brains that fail to accurately model reality do not survive to reproduce and are selected against.

With simple enough inference rules (which do give us considerable power) we can be rigorously certain not only that all of our deductions do correctly follow from our axioms, but also that our inference rules never produce a contradiction (eliminating half the possible statements as non-theorems, statements that cannot be generated from the axioms and inference rules) and that all possible statements are definitely theorems or non-theorems. Philosophy typically uses propositional calculus (provably consistent and complete) or first-order logic (consistent and semicomplete). Higher-order logic, however, confuses most philosophers.

Evidentiary reasoning also does not give us the kind of confidence we can get from deductive reasoning. We have only a finite amount of evidence (our actual observations and experience), but there are an infinite number of possible formal systems that would account for that evidence (i.e. the facts in evidence are theorems of the formal system). Furthermore, it might be the case that there is no formal system that accounts for the evidence. It might be the case, for example, that the universe is infinite and truly random, in which case a set of observations and experiences that looks like the workings of every underlying set of natural laws modeled by a formal system will occur at one point or another.

Therefore we have to apply additional formal criteria to evidentiary reasoning for it to have any utility. The additional criteria are simplicity and falsifiability. The criteria of simplicity specifies that if more than one formal system accounts for the evidence, we prefer the formal system with the fewest axioms and inference rules. (A corollary of the simplicity criterion is that two formal systems with the same theorems are equivalent.) But the simplicity criterion isn't enough, otherwise we would prefer the simplest "degenerate" explanation that all statements are true: obviously all statements about evidence follow from this explanation. The criterion of falsifiability specifies that only formal systems where statements that contradict true statements about observation or experience are non-theorems are interesting.

Note that simplicity is not a criterion of deductive reasoning: the most complicated proof in the world (such as the four color theorem or Fermat's last theorem) are just as good as the most elegant, compact proof. The criterion of falsifiability has an analog in the deductive criterion of non-contradiction, but it's more trivial: it specifies that exactly half of all decidable statements are theorems and the other half non-theorems (i.e. if X is a theorem, then not-X is a non-theorem, and vice-versa. There are some interesting exceptions to this rule, sadly beyond the scope of this post.)

Although related, deductive and evidentiary reasoning work in "opposite" directions. Deduction asks the question: what interesting statements are theorems of this formal system? Evidentiary reasoning asks the opposite question: in what formal system are these interesting statements theorems?

1. Interesting to speculate that if Fermat really did fit a clever proof of his last theorem in the margin of his book (instead of the book-length proof that eventually solved it), it might not be beyond the ability of a supercomputer to generate it from a number theory production system. The trouble, of course, would be in recognizing the theorem for what it was amongst the billions and billions.

2. [I]t might not be beyond the ability of a supercomputer to generate [Fermat's last theorem] from a number theory production system.

Based on my understanding of combinatorial math and number theory, I'm not holding my breath. Even today, supercomputer implementations of AI topics depend on speed and brute force, not cleverness.

"Billions and billions" is very misleading. Combinatorial numbers speed past orders of magnitude before they have their first cup of coffee, get past exponents and towers of exponents by lunch, and we have to invent new systems of notation before they've finished their first day of work.

Please pick a handle or moniker for your comment. It's much easier to address someone by a name or pseudonym than simply "hey you". I have the option of requiring a "hard" identity, but I don't want to turn that on... yet.

With few exceptions, I will not respond or reply to anonymous comments, and I may delete them. I keep a copy of all comments; if you want the text of your comment to repost with something vaguely resembling an identity, email me.

No spam, pr0n, commercial advertising, insanity, lies, repetition or off-topic comments. Creationists, Global Warming deniers, anti-vaxers, Randians, and Libertarians are automatically presumed to be idiots; Christians and Muslims might get the benefit of the doubt, if I'm in a good mood.

See the Debate Flowchart for some basic rules.

Sourced factual corrections are always published and acknowledged.

I will respond or not respond to comments as the mood takes me. See my latest comment policy for details. I am not a pseudonomous-American: my real name is Larry.

Comments may be moderated from time to time. When I do moderate comments, anonymous comments are far more likely to be rejected.