Addition Operation on Natural Numbers – Set Theory

Hi, infinite-set readers. Set theory is back.

The previous post is on this link. Please read in advance to easily understand this post. Today we will discuss about the addition operation on natural numbers. Happy reading.

The consequence of the Finite Recursion Theorem raises a theorem. The theorem is also called Finite Recursion Theorem because the same in the rationale.

Theorem : (Finite Recursion Theorem)

Given any e\in E and the function f:E\rightarrow E, then there is a single function g:\omega\rightarrow E such that :

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

Proof :

Based on the above hypothesis, it can be formed :

    \[ p\left(x,y\right)\equiv\left(\left(x\in E\right)\wedge\left(y=f\left(x\right)\right)\right)\vee\left(\left(x\notin E\right)\wedge\left(y=0\right)\right)\]

with f is fuction from E to E. Obtained, p\left(x,y\right) is a binary predicate. With the previous proof of Finite Recursion Theorem in the previous post, then this theorem is proved.

(x) Theorem :

For any n\in\omega there is a single function S_{n}:\omega\rightarrow\omega such that :

    \[ S_{n}\left(0\right)=n\mbox{ and }S_{n}\left(x^{+}\right)=\left(S_{n}\left(x\right)\right)^{+}\]

Proof :

By taking E=\omega, e=n, g=S_{n}, and f is function from \omega to \omega with f\left(y\right)=y^{+} for all y\in\omega then by Finite Recursion Theorem, this theorem is proven.

The above Theorem (x) then becomes a tool for defining the sum of natural numbers.

Definition :

Given any n,m\in\omega and S_{n} are functions defined in the Theorem (x). Defined n+m with n+m=S_{n}\left(m\right).

Theorem :

For all n\in\omega and S_{n} are functions defined in the Theorem (x) then apply that x\leq S_{n}\left(x\right) for all x\in\omega.

Proof :

Will be proved using mathematical induction. For x=0 then 0\leq n=S_{n}\left(0\right) is true. Suppose that is true for n=k then apply k\leq S_{n}\left(k\right). Consequently, for n=k^{+} then k^{+}\leq\left(S_{n}\left(k\right)\right)^{+}=S_{n}\left(k^{+}\right).

In the next post will be given the definition of multiplication and power. See you in the next post. Thanks for reading. May be useful.

If there is any criticism and suggestion, please comment below or email me. Hope you like this ‘story’.


Add a Comment

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