## Deduction and Induction

In logic, there are two distinct methods of reasoning namely the deductive and the inductive approaches.

Deductive reasoning works from the "general" to the "specific". This is also called a "top-down" approach. The deductive reasoning works as follows: think of a theory about topic and then narrow it down to specific hypothesis (hypothesis that we test or can test). Narrow down further if we would like to collect observations for hypothesis (note that we collect observations to accept or reject hypothesis and the reason we do that is to confirm or refute our original theory). In a conclusion, when we use deduction we reason from general principles to specific cases, as in applying a mathematical theorem to a particular problem or in citing a law of physics to predict the outcome of an experiment.

 Theory Theory ↓ ↑ Hypothesis Hypothesis ↓ ↑ Observation Pattern ↓ ↑ Confirmation Observation Deduction Reasoning Induction Reasoning

An Inductive reasoning works the other way around, it works from observation (or observations) works toward generalizations and theories. This is also called a “bottom-up” approach. Inductive reason starts from specific observations (or measurement if you are mathematician or more precisely statistician), look for patterns (or no patterns), regularities (or irregularities), formulate hypothesis that we could work with and finally ended up developing general theories or drawing conclusion. Note that that is how Newton reached to "Law of Gravitation" from "apple and his head” observation"). In a conclusion, when we use Induction we observe a number of specific instances and from them infer a general principle or law.

These two methods are “sense” very different in nature when use in conducting researches other than being top-down and bottom-up. Inductive reasoning is open-ended and exploratory especially at the beginning. On the other hand, deductive reasoning is narrow in nature and is concerned with testing or confirming hypothesis.

You may already notice that we could merge these two approaches into one circular pattern - from theory to observations and again form observation to theory. When we say some researcher (Einstein) develops a new theory (relativity) we usually mean that he observes some pattern in the data (light).

## Comparison of two Reasoning

### Properties of Deduction

• In a valid deductive argument, all of the content of the conclusion is present, at least implicitly, in the premises. Deduction is nonampliative.
• If the premises are true, the conclusion must be true. Valid deduction is necessarily truth preserving.
• If new premises are added to a valid deductive argument (and none of its premises are changed or deleted) the argument remains valid.
• Deduction is erosion-proof.
• Deductive validity is an all-or-nothing matter; validity does not come in degrees. An argument is totally valid, or it is invalid.

### Properties of Induction

• Induction is ampliative. The conclusion of an inductive argument has content that goes beyond the content of its premises.
• A correct inductive argument may have true premises and a false conclusion. Induction is not necessarily truth preserving.
• New premises may completely undermine a strong inductive argument. Induction is not erosion-proof.
• Inductive arguments come in different degrees of strength. In some inductions, the premises support the conclusions more strongly than in others.

Note Carefully
Some philosophers have doubts that induction is really a method of logical reasoning, since observations of past instances may never be sufficient to give us certainty about what will happen in the future. For example, observing billions of billions of white swans does not imply that all swans are white (Logic: This horse is brown. That horse is brown. The hundredth horse is brown. The hundred and first horse is brown. Therefore, all horses are brown).

As an example of this concept, consider a problem 0.11 from a book "Introduction to the Theory of Computation" by Michael Sipser.

Problem 0.11 Find the error in the following proof that all horses are the same color.

CLAIM:
In any set of h horses, all horses are the same color.

Proof:  By Induction on h.

Basis: For h = 1. In any set containing just one horse, all horses clearly are the same color.

Induction Step: For k 1 assume that the claim is true for h = k and prove that it is true for h = k+1. Take any set H of k+1 horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set H1 with just k horses. By the induction hypothesis, all the horses in H1 are the same color. Now replace the removed horse and remove a different one to obtain the set H2. By the same argument, all the horses in H2 are the same color. Therefore, all the horses in H must be the same color, and the proof is complete. □

Solution:    The case n = 2 does not follow from n = 1 because when a horse is deleted from the pair; the remaining horse is the same color as itself, but not as any other horse; so transitivity does not apply. So, the basis is valid (although degenerate) but the inductive step works only starting at n = 2. If a basis could be proved for n = 2, the proof would be valid; but, of course, it can't.

Remark
In this problem keep in mind that existence of a counterexample to a theorem means any proof must be fallacious proof does not mean that a theorem does not hold.