Limits of Logic #4: Recursion Theorem
Definition
Let be a set of operations on a set .
- A subset is closed iff for each place function , and for any elements we also have that
- A subset has the inductive property iff for any closed set , .
- A subset is recursive iff is both closed and inductive.
That is to say, the recursive set is the smallest closed set.
This definition formalizes recursive definitions which are "a way of defining an infinite set or relation, or a function with an infinite domain."
An example of a recursive definition of a set is the set of even numbers:
- is even
- is even is even.
Here, we have recursively defined the property of "evenness" . Ultimately, a property really just is a set of all and only those elements which have that property. So the property really is the set of all even numbers.
In putting our recurvise definition of in context with the formal definition of recursiveness, we see that here contains two functions and :
- A zero place function that outputs .
- A one place function .
What does an closed set look like? The even numbers are not the only closed set. Note how the set of all natural numbers is also closed; and .
Along with the closure property (that is closed), also has the inductive property. Intuitively, the inductive proeprty tells us that if for any :
- For any we have that
Then really, alll even numbers are in .
In other words, if any is closed, then . Note how can represent any property (e.g. "nice") and since we know that is closed, we can prove by induction that every even number is "nice".
Now see that is the smallest closed set -- which we define as being recursive. Intuitively, tells us that is necessarily in an closed set, and takes to , which takes us to , ... and eventually all and only even numbers.
Exercise 2.3.2
For any set of operations on a set , there is exactly one recursive set.
Proof:
Let be arbitrary recursive sets.
Both and are closed. But then, by definition, is inductive which means that . Similarly, we have that . Therefore, i.e. there is exactly one recursive set.
Definition
The relation is less than or equal to is recursively defined as follows:
Note that this definition of a relation defines a set of ordered pairs .
In the context of the formal definition recursive definitions, here contains a one place function that takes , and a two place function that takes . Therefore, the relation is the recursive set on these operations.
Example 2.2.6
Prove that for any numbers and such that , either or .
Proof:
Call nice iff either or .
We are trying to prove that for every such that holds, is nice.
We shall prove this by induction on the relation.
Base Case .
By the first rule of the recursive definition, is a -pair. Clearly, is nice since .
Inductive Case .
By the second rule of our recursive definition of , we have that if is a -pair, then so is .
So, we'll assume that is nice and show that it follows that is also nice.
So, assume that is nice, that is, .
Case :
. Therefore, based on the first rule of the definition, and so, is nice.
Case :
based on the second rule of the definition, and so, is nice.
In either case, is nice.
Hence, we have proved that for any numbers and such that , either or .
Exercise 2.2.7
Prove by induction that for all numbers if and then .
Proof:
Let be any number and be a -pair.
We want to show by induction on the relation that for any -pair , we have .
Base Case -pair
By the first rule of the recursive definition, is a -pair. Clearly, . The base case is satisfied.
Inductive case
By the second rule of our recursive definition of , we have that if is a -pair, then so is .
So, we'll assume that holds, and show that it follows that .
So, let . But then it follows from our assumption that and by the the second rule of the recursive definition of , we have that .
Therefore, .
2.3.4 The Recursion Theorem
Let be a set. Let be an element of , and let be a function. Then there is a unique function with these two properties:
Call these Recursive Properties.
We prove this theorem in parts. Particularly we prove that following relation "selects" is functional:
For a number and an element we define the relation selects recusrively as follows:
- selects .
- selects selects .
We want to show that each number selects exactly value. Once we have done this, we will check the function for Recursive properties.
2.3.5 Exercise
Prove each of the following by induction on the definition of selects:
- If selects then .
- If selects then there is some such that selects and .
Proof of 1:
By induction on the selects relation, we want to show that for every selects-pair , it holds that .
Base case: is a selects-pair
Here, . Therefore, it holds that If selects then .
Inductive case: selects selects .
Here, we assume that for it holds that .
We now show that it follows that for , it holds that .
Note how is always false. Therefore, trivially holds.
Therefore, we have shown by induction on the selects relation that if selects , then .
Proof of 2:
We want to show that for every selects pair , it holds that .
Base case: is a selects-pair
Here, . Note how is always false.
Therefore, holds trivially.
Inductive case: selects selects .
We assume that for , it holds that .
We show that it follows for that .
Note that clearly is a successor of some , particularly it is the successor of , and is such that .
Therefore, that holds trivially.
We have shown by induction on the selects relation that If selects then there is some such that selects and .
2.3.6 Exercise
Prove the following:
- For each number there is at least one such that selects .
- For each number there is at most one such that selects .
Proof for 1:
We prove by induction on the natural numbers that For each number there is at least one such that selects .
Base case:
By definition of the selects relation, we have that selects . Therefore, the base case is satisfied.
Inductive case: Assume there is some such that selects .
We show that there is some such that selects . Note by definition of the selects relation, selects . Therefore the inductive case is satisfied.
We have shown by induction that for each number there is at least one such that selects .
Proof for 2:
We prove by induction on the natural numbers that For each number there is at most one such that selects .
Base case:
By the result of 2.3.5 - 1, we have shown that if selects some , then . Therefore, selects at most one value. The base case is satisfied.
Inductive case: Assume there is at most one such that selects .
We show that there is at most one b \in A$ such that selects .
Note by definition of the selects relation, selects .
Now let's say that selects some . Then by the result in 2.3.5-2, there is some such that selects and .
But by our assumption, selects at most one . Therefore, and where selects .
Therefore, selects at most one value, that is, .
We have proved by induction that for each number there is at most one such that selects .
Completing the proof of Recursion theorem
Based on our results in 2.3.5 and 2.3.6 we can pick out a unique function such that:
iff selects for every and .
We now prove that:
- For each , iff .
- For each , iff .
Proof for 1:
Let for some . Then, by the definition of , we have that selects . But exclusively selects . This implies that .
For the other direction, let . We know selects . Therefore, by definition of , we have that .
Therefore, we have proved that for each , iff .
Proof for 2:
Let . But then, we know that there is some such that selects and . By the definition of , .
Therefore, .
For the other direction, assume . By definition of , we have that selects . By the definition of the selects relation, we have that selects . But again by definition of , we have that .
Therefore, .
We have proved that for each , iff .
This completes the proof of the recursion theorem.