# Finite Recursion Theorem

Hello, infinite-set readers. Set Theory is back.

In this post will discuss about finite recursion theorem. It’s used to define the operation on natural numbers. Why does this need to be discussed?

Back to the previous sense, any natural number is seen as a set (if you don’t know about this, you can read from my first post in this link). This will cause problems in the operations that occur in natural numbers. Hence, it will be discussed about the operations of addition, multiplication and, power in natural numbers. Happy reading.

**Theorem : (Finite Recursion Theorem)**

Given binary predicate ; relation in such that for any there exists with a unique , that denoted by , such that is true. Then for any set there is a single function that defined on such that :

**Proof :**

Will be proven there is a function that defined on such that and for . Suppose for natural numbers , defined function with and for all . Then defined on . For example, for natural numbers , defined on .

It will then be proven that the function applies to all . Suppose it does not apply to any then there is with being the smallest natural number such that is undefined at . Note that . Since is the smallest natural number such that is undefined at , then is defined in and since is true then is defined in . There was a contradiction. Which means for all there is a function such that and for all . Next, defined functions with then the function proven to be defined in . It because .

Will prove the unity of . Suppose there is with such that

and

Therefore then there are such that . It’s clear that because if then . Choose is the smallest natural number such that . As a result, so obtained if and only if . There was a contradiction. Which means is unique.

See you in the next post. Thanks for reading.