On instantiations of variables by terms

Arthur Buchsbaum

Department of Informatics and Statistics
Federal University of Santa Catarina - UFSC
Florianopolis - Brazil

Instantiation is an operation essential for performing logical reasoning, it is placed in the heart of its basis, when dealing with universal and existential quantifiers. In many logics it must appear explicitly in at least three of the four laws of introduction and elimination of quantifiers.

In spite of it, the study and presentation of this operation has been underestimated in most books on logic, usually only half of a page is dedicated to it. Beyond that, when it is presented, it is often wrongly confused with a particular case of another operation, named here replacement, which is used on formulation of some laws related to equivalence and equality. While replacement of a variable by a term considers all occurrences of variables which don’t succeed a quantifier or a qualifier, instantiation consider only free occurrences of this variable; the former does not rename bound variables, while the latter, for a good working, needs renaming of bound variables in many of its forms.

By consequence of lack of carefulness in dealing with instantiation, when there is no renaming of bound variables, the presentation of the basic laws of introduction and elimination of quantifiers needs some patches, and these ones become more difficult reasoning perform from this point on.

In this tutorial all possible alternatives of instantiation are presented, and one of them, maybe the most promising one, is presented in detail, in order to make easier reasoning perform inside a logical system.

References
-
Bell, J. and Machover, M., "A Course in Mathematical Logic", North-Holland, 1977.
- Ebbinghaus, H. D. and Flum, J. and Thomas, W., "Mathematical Logic", second edition, Springer, 1996.
- Enderton, H. B., "A Mathematical Introduction to Logic",Academic Press, 1974.
- Negri, S. and von Plato, J., "Structural Proof Theory", Cambridge University Press, 2001.
- Prawitz, D., "Natural Deduction: A Proof-Theoretical Study", Dover Publications, 2006.
- Shoenfield, J. R., "Mathematical Logic", Addison-Wesley, 1967.