Next: 3.4 Summation. Up: 3. Induction and Integers Previous: 3.2 Integers and Rationals.   Index

# 3.3 Recursive Definitions.

Our definition of function involved the undefined word rule". If I define by

the rule is perfectly clear. I will often want to define functions by rules" of the following sort: is given by
 (3.50)

It is not quite so clear that this is a rule, since the right side of (3.50) involves the function I am trying to define. However, if I try to use this rule to calculate , I get
 (3.51)

and by this example, you recognize that (3.50) defines the familiar factorial function. In fact, I make this my definition of the factorial function.

3.52   Definition (Factorial function.) We define by the rules.

We call the factorial function, and denote by . By definition,

I could use the same rule (3.50) to define a factorial function . The calculation (3.51) shows that then

and

but in , so I have , contradicting . So I see that (3.50) is not a rule". How do I know that (3.50) is a rule" when considered as a function from ?; i.e., how do I know that no contradiction arises when I use (3.50) to calculate values for ? I have decided not to worry about this question, and to treat definitions analogous to (3.50) where functions on are defined by giving explicitly, and expressing in terms of and for values of , as valid rules". Such defintions are called definitions by recursion. A discussion of, and justification for definitions by recursion can be found in [27].

3.53   Definition (Powers.) Let be a field, and let . Define a function

by
 (3.54)

Thus,

We denote the value of by . Then we can rewrite (3.54) as

Note that and .

3.55   Theorem. Let be a field and let . Then for all ,

Proof: Define a proposition form on by

Then which is true, since both sides of the equation are equal to . For all ,

and

Hence for all ,

By induction, is true for all , i.e.

3.56   Exercise. Let be a field, and let be elements of . Show that

3.57   Exercise. A Let be a field and let . Show that

The following results are easy to show and we will assume them.

3.58   Remark. Let be a field, let and let . We know that where . Suppose we also have where .

I need this remark for the following definition to make sense.

3.59   Definition (Integer powers.) Let be a field. If and , we define

Note that this definition of is consistent with our use of for multiplicative inverse. Also, this definition implies that

3.60   Theorem. Let be a field and let . Then

Proof: Let , and write

then and and

3.61   Remark. If is a field, and , then by definition 3.59 we know that

It follows from theorem 3.60 that for all , and hence

3.62   Exercise. Let be a field, and let . Show that

3.63   Corollary (to Exercise 3.62)Let be a field, and let . Then

Proof: By exercise 3.62

If we multiply both sides of this equation by , we get

i.e.

3.64   Exercise. Let be a field, and let . Show that

Next: 3.4 Summation. Up: 3. Induction and Integers Previous: 3.2 Integers and Rationals.   Index