Mathematics and Computer Science

Integer Construction by Induction

Anthony R. Fressola

Spring 2003

Mathematics and Computer Science Department

Denison University

Advisor: Dr. Joan Krone

Abstract: In 1889, Giuseppe Peano inductively defined the natural numbers by using the empty set along with a successor function. The natural numbers can be defined inductively primarily because they are well-ordered, a property which is equivalent to that of induction [1]. Inductive systems are especially useful in the area of computing for both reasoning about and implementing algorithms. Moreover, induction lends itself well to certain aspects of automated proving.

The natural numbers are just one example of inductive systems. Other inductive systems include string induction, tree induction, and transfinite induction [2, 3]. Although it would seem reasonable to describe sets containing the natural numbers inductively, such as the integers and rational numbers, traditional approaches have not done so. These systems have traditionally been defined as equivalence classes of natural numbers [4]. One reason may be that the integers and rationals are not well-ordered under the usual ordering. This leaves us with an intriguing question: Can the integers and rationals be described inductively? Here we present one possible well-ordering that allows us to define the integers inductively. By introducing several definitions, we are able to prove the common additive properties of the integers, including the associativity and commutativity of addition. This work motivates the future investigation of other systems, such as the rational numbers.

[1] Fejer, Peter A. and Dan A. Simovici. Mathematical Foundations of Computer Science. New York: Springer-Verlag, 1991.
[2] Ogden, W.F. CIS680 Course Notes. The Ohio State University, 2002.
[3] Suppes, Patrick. Axiomatic Set Theory. New York: Dover Publications, 1972.
[4] Mendelson, Elliott. Number Systems and the Foundations of Analysis. New York: Academic Press, 1973.