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 p\left(x,y\right); relation in x such that for any x there exists with a unique y, that denoted by p\left(x\right), such that p\left(x,p\left(x\right)\right) is true. Then for any set s there is a single function g that defined on \omega such that :

    \[ g\left(0\right)=s\mbox{ and }g\left(m^{+}\right)=p\left(g\left(m\right)\right)\mbox{ for all }m\in\omega\]

Proof :

Will be proven there is a function g that defined on \omega such that g\left(0\right)=s and g\left(m^{+}\right)=p\left(g\left(m\right)\right) for m\in\omega. Suppose for natural numbers n, defined function g_{n} with g_{n}\left(0\right)=s and g_{n}\left(m^{+}\right)=p\left(g_{n}\left(m\right)\right) for all m^{+}\in n^{+}. Then g_{n} defined on n^{+}. For example, for natural numbers 0, g_{0}=\left\{ \left(0,s\right)\right\} defined on 0^{+}.

It will then be proven that the function g_{n} applies to all n\in\omega. Suppose it does not apply to any n\in\omega then there is h\in\omega with h being the smallest natural number such that g_{h} is undefined at h^{+}. Note that g_{h}=g_{h^{-}}\cup\left\{ \left(h,p\left(g_{h^{-}}\left(h^{-}\right)\right)\right)\right\}. Since h is the smallest natural number such that g_{h} is undefined at h^{+}, then g_{h^{-}} is defined in \left(h^{-}\right)^{+}=h and since \left(h,p\left(g_{h^{-}}\left(h^{-}\right)\right)\right) is true then g_{h} is defined in h^{+}. There was a contradiction. Which means for all n\in\omega there is a function g_{n} such that g_{n}\left(0\right)=s and g_{n}\left(m^{+}\right)=p\left(g_{n}\left(m\right)\right) for all m^{+}\in n^{+}. Next, defined functions g=\cup G with G=\left\{ g_{n}|n\in\omega\right\} then the function g proven to be defined in \omega. It because \mbox{dom}g=\cup\left\{ \mbox{dom}g_{n}|g_{n}\in G\right\} =\cup\left\{ n^{+}|n^{+}\in\omega\right\} =\omega.

Will prove the unity of g. Suppose there is g,h with g\neq h such that

    \[ g\left(0\right)=s\mbox{ and }g\left(m^{+}\right)=p\left(g\left(m\right)\right)\mbox{ for all }m\in\omega\]

and

    \[ h\left(0\right)=s\mbox{ and }h\left(m^{+}\right)=p\left(h\left(m\right)\right)\mbox{ for all }m\in\omega\]

Therefore g\neq h then there are m\in\omega such that g\left(m\right)\neq h\left(m\right). It’s clear that m\neq0 because if m=0 then g\left(m\right)=h\left(m\right). Choose m is the smallest natural number such that g\left(m\right)\neq h\left(m\right). As a result, g\left(m^{-}\right)=h\left(m^{-}\right) so obtained g\left(m\right)=p\left(g\left(m^{-}\right)\right)=p\left(h\left(m^{-}\right)\right)=h\left(m\right) if and only if g\left(m\right)=h\left(m\right). There was a contradiction. Which means g is unique.

See you in the next post. Thanks for reading.

One Comment

Add a Comment

Your email address will not be published. Required fields are marked *