## Thursday, January 31, 2013

### Modes of Reasoning: Deductive, Inductive, and Abductive

Basically, there's three ways of reasoning about things: deductively, inductively, and abductively.

In this post I'll explain the difference between them and how they fit into mathematics, science, and the scientific method.

Deduction: Given assumptions, reach a conclusion.
Example. We know (Prolog code shown in brackets):
1. All men are mortal. [ mortal(X) :- man(X). ]
2. Socrates is a man. [ man(socrates). ]
Thus, we can conclude:
Socrates is mortal. [ mortal(socrates). ]

Put differently, whenever we look at a logical entailment of the form P => Q, deduction is the process of reaching Q (whatever that may be) given P.

Mathematics is largely deductive: we start with a set of assumptions (called axioms). At the lowest level these encode the nature of numbers, sets, or other objects that are fundamental to whatever branch of mathematics we want to study (the most well studied axioms are Peano Arithmetic and ZFC).

This set of axioms is our P. In Peano Arithmetic, for example, one axiom is:
A1. "0 is a natural number" [ natural(0). ].
Another is:
A2. "if X is a natural number, so is its successor" [ natural(s(X)) :- natural(X). ]

Taken together, these define a sequence (0,s(0),s(s(0)),s(s(s(s(0)))),...) which correspond to the natural numbers (0,1,2,3,4,...). Thus 4 is just seen as a convenient way to express the object s(s(s(s(0)))).

From these two axioms, we can prove "2 is a natural number" [ natural(s(s(0))). ], as follow:
Assume 2 is not a natural number [ not natural(s(s(0))). ]
Then (by A2), 1 is not a natural number [ not natural(s(0)). ]
Then (by A2), 0 is not a natural number [ not natural(0). ]
But by A1, 0 is a natural number, a contradiction.
Thus, 2 is a natural number.
(I choose a proof by contradiction rather than the more obvious direct proof to also illustrate exactly how Prolog would prove it mechanically.)

So from our axioms A1 and A2 (our P in P => Q), we have prove that "2 is a natural number" (our Q).

Here's an important point: mathematical induction is not inductive reasoning. Mathematical induction, in fact, is a form of deduction. More specifically, mathematical induction is a rule for drawing a conclusion from known facts (called an inference rule), of the following form:
For any predicate p(X) (here p(X) could stand for "X is prime" or pretty much anything), if we know that:
1. p(0) [ p(0). ]
2. For all naturals X, if p(X), then P(X+1). [ p(s(X)) :- natural(X), p(X). ]
Then, we may conclude that:
For all naturals X, P(X). [ p(X) :- natural(X). ]

For example, take p(X) to mean "X is equal or greater than 0". First, we observe that p(0) is trivially true (since 0 is equal to 0"). Next, assume we know that X is equal or greater than 0. Then, since X+1 is bigger than X, which in turn is equal or greater than 0, will also be equal or greater than 0 (in fact, always greater).
Thus, if p(X), it is also true that p(X+1). These are the two conditions that must be satisfied to apply mathematical induction. Now we may conclude that p(X) is true for all natural numbers X, that is, that all natural numbers are equal or greater than 0. (Put differently, the natural numbers are lower bounded by 0, in contrast to, say, the integers which have infinite descent.)

So deductive reasoning is finding the Q in the entailment "P => Q".
Abductive reasoning, is the opposite: finding the P given the Q.
Simply put: Looking at "P => Q":
Deductive reasoning: P known. Goal: find Q.
Abductive reasoning: Q known. Goal: find P.

Example:
1. All men are mortal. [ mortal(X) :- man(X). ]
2. ???
Conclusion:
Socrates is mortal. [ mortal(socrates). ]

Abductive reasoning finds that the ??? might be: Socrates is a man [ man(socrates). ]

Note that, unlike deductive reasoning, abduction doesn't guarantee that we get the right hypothesis P.
It may very well be that Socrates is a cat, and, since all cats are mortal too (but this is never stated above), Socrates is mortal.

Mathematicians sometimes employ abductive reasoning too. This is because in practice mathematics is not (at least not as of now) done purely deductively, especially not when dealing with very abstract math. For example, to prove the Hahn-Banach theorem in its most general form, one needs to employ an axiom known as the Axiom of Choice (the C in ZFC). This can be considered a form of abductive reasoning:

We know that the Q (conclusion) should be the Hahn-Banach theorem (what it says exactly is not relevant here). The P is the ZF axiom system, which is a set of assumptions upon which mathematics is founded.
So we have "ZF + ? => Hahn-Banach Theorem". We are asking for something "?" that needs to be added to ZF in order to prove the Hahn-Banach Theorem. One such "?" is the Axiom of Choice.

Abductive reasoning, in its more formal sense, can thus be seen as the question "What assumption needs to be made in order for this proof to go through?". Or, more informally: "What assumption would explain these observations?".

This leads us to the third mode of reasoning: inductive reasoning. This one's easy now: inductive reasoning is a special case of abductive reasoning, namely, the case where you want to add an assumption which is, logically speaking, the same predicate as the conclusion. Example:

1. All men are mortal. [ mortal(X) :- man(X). ] <-- predicate is "mortal"
2. ??? <-- part of P.
Conclusion:
Socrates is a mortal [ mortal(socrates). ] <-- Q is about mortality

Possible explanation: ??? should be "Socrates is a man" [ man(socrates). ] <-- P is about manhood.
As you can see, our explanation P is about manhood (the predicate man), whereas the conclusion deals with mortality (the predicate mortal). This is an example of abductive reasoning that is NOT inductive reasoning.

Here's one that is inductive (and also abductive, as all induction is abduction):

1. ??? <--- P
Conclusion
1. Swan1 is white. <-- first part of Q, about whiteness
2. Swan2 is white. <-- second part of Q, about whiteness
3. Swan3 is white. <-- last part of Q, about whiteness

One possible explanation P is "All swans are white" [ white(X) :- swan(X). ].
As the explanation is also about whiteness, just like the conclusions, we have an instance of inductive reasoning.

The scientific method creates hypothesis (P's) from observations (Q's). Thus, it is a form of abductive reasoning. It tries to find explanations (P) for what is observed (Q).

However, these explanations (P) are then tested in experiments in an attempt to falsify them or give them more credibility. The experiment must then test for a specific prediction that can be drawn from this hypothesis P. Thus, we need to produce a prediction (conclusion) C from P, i.e. we are doing P => C, where we know P and are looking for C. In other words, this is a deductive step.

The act of performing the experiment on C is not covered by reasoning: it is usually an empirical task covered by engineering skills. The hypothesis P is then either rejected (if the experiment shows that C is not true) or further refined (more abduction) and new predictions made (more deduction). Thus, the scientific method interleaves abduction and deduction, as well as requires that "step into reality" during experimentation.