One of the characteristics of human reasoning is that we form generalizations based on our experience or observations. But,

• What is the relation between a generalization and the observations on which it is based?
• What should be the relation between a generalization and the observations on which it is based?
• What can be the relation between a generalization and the observations on which it is based?

     The first question is an empirical question and is the focus of psychological research. In the first half of this century psychologists simply referred to this question as one of learning...and the term induction was rarely encountered in the psychological literature.

     The second question became of particular interest with the rise of empirical science. What should be the relation between the concepts and laws developed by a science and the observations on which the laws and concepts are based and to which they apply? One might think that the scientific concepts and laws should follow from or be implied by the observations....thus, if the observations are true, and if the laws follow deductively from the observations, then the laws are true since deduction is truth preserving! Life is wonderful, science is the way to truth, ...

     But, almost everyone who carefully thought about this problem became convinced that things weren't this simple. Induction could not be reduced to deduction. (If it could, then once a law was established it could never be defeated by any new observations if it in fact was simply a deductive truth.) So, whereas deduction seemed like a nice dream about what the relation should be, it was only a dream. And, this whole idea of induction had to be looked at and studied quite carefully.

     Around the middle of this century, it became possible to pose the last question. By posing the question as well as the induction process as a mathematical system, it became possible to say something about the kinds of "theories" that could be learned from observations. This mathematical area is known as "learnability theory".

     Now, as mentioned above, it appears that induction cannot be reduced to deduction. But, if the relation isn't deductive, then what else might it be? It certainly shouldn't be arbitrary!

     The figure to the right provides an initial way to think about this question. Recall that observations (or examples) of a concept or law are distinguished. Thus, one place to begin is to assume that we have a set of examples; some of which are positive--that is, they exemplify the concept; and some of which may be negative--that is, they are not examples of the concept.

     How do we get these sets? We don't say...we simply assume that we have them or we invent a "teacher" who presents them to our induction process.

     Further, since the induction process is supposed to yield a theory of the observations, we will assume that the induction process has some language suitable for forming theories. Usually, we simply assume that language is a logic...but this is done for generality and to simplify the development of the ideas. Again, where the language comes from we don't say. The induction process simply has it. Finally, there is the training sequence, TS, which consists of some of the examples presented in some sequence to the induction process.

     With these givens, we can now say a little bit about the relation that should exist between observations(examples) and our theory. We wish our theory, S in the above figure, to allow the positive examples of the concept to be derived or deduced and not to allow the negative examples of the concept to be derived.

     Now comes the tricky part. If you think about it a bit you will recognize that this is a very weak criterion. It can be easily satisfied. The set TS is always finite. Consequently, one can simply write down in the language each of the examples. Thus, S is just the examples that have been seen together with the appropriate logical connective to the concept that allows each example to be derived from S. Less carefully stated, S is just a memorization of the examples of the training sequence.

     But this doesn't allow one to make any predictions about new examples! Consequently, the requirement is added that we have some procedure that generalizes S to S'. And S' then is required to make the correct predictions for all possible future examples. To do this S' must "go beyond the information given" and consequently S' can not be deductively related to S. This is one way to view what is known as the induction problem. And, we know that we can not guarantee that we can find an inductive procedure that meets this criterion for any concept that can be imagined.