Elements of Set Theory: Recursion on Natural Numbers

Consider the situation where I want you to guess the function such that I only give you two information; that is,

1. a starting value
2. a function such that for all

This gives away all the information where you can compute successively,

Now for a harder question: Suppose we are given a set A, an element , and a function , then how can we show that there exists a function such that

1. 
2. 

We can prove that there exists a set h that is a function meeting the above conditions.

Recursion Theorem on Let A be a set, and . Then there exists a unique function such that

and for every

---

Proof

First, we will let h be the union of many approximating functions. For the purpose of this proof, call a function v acceptable iff , and the following conditions hold:

(i) If

(ii) If then also

Let be the set of all acceptable functions and the union of this set is the h function:

We claim that this h meets the demands of the theorem, breaking it down into four parts.

1. h is a function
2. h is acceptable
3. dom h is all of
4. h is unique

Example Let be the set of all integers, positive, negative, and zero:

There is no function such that for every ,

If you notice,

has no starting point similar to the 0 starting point of the recursion on .

---

Our first application of the recursion theorem will be to show that any Peano system is "just like" . There are other Peano systems; for example, let N be the set of powers of 2, let , and let . Then is a Peano system.

The following theorem expresses the structural similarity between this Peano system and the .

Theorem 4H Let be a Peano system. Then is isomorphic to , i.e., there is a function h mapping one-to-one onto N in a way that preserves the successor operation.

and the zero element

Remark: The equation together with implies that . This can be shown as follows,

Theorems 4D and 4H relate the constructive approach to the natural numbers and the axiomatic approach. Theorem 4D shows that Peano's postulates are true of the number system we have constructed. And theorem 4H shows that the number system we have constructed is, "to within isomorphism," the only system satisfying Peano's postulates.

---

^{Disclaimer: this is a summary of section 4.3 from the book "Elements of Set Theory" by Herbert B. Enderton, the content apart from rephrasing is identical, most of the equations are from the book and the same examples are treated. All of the equation images were screenshots from generated latex form using typora}

1. Elements of Set Theory by Herbert B. Enderton

Thank you for reading ...