Multiplication and Exponentiation (Power) on Natural Numbers – Set Theory

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

The previous post we have discussed about the definition of addition on natural numbers. You can visit this link to read the previous post. This time, we will be discuss about the definition of the multiplication of two natural numbers. But before, the theorem will be given as a tool for defining the multiplication of two natural numbers. Happy reading.

(x) Theorem :

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

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

Proof :

By taking E=\omega, e=0, g=P_{n}, and f is function from \omega to \omega with f\left(y\right)=y+n 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 multiplication of natural numbers.

Definition :

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

In the defined of sum and multiplication above (and previous post), it applies associative, commutative, and distributive. But in this post will not be proved these. You can try it yourself to prove the above definition applies these characteristic.

Next will be discussed about the definition of the exponentiation (power) on natural numbers. But before that, will be given the theorem as a tool to define the powers.

(y) Theorem :

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

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

Proof : (more…)

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 (more…)

Finite Recursion Theorem

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

In this post will discuss about 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. 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.

2=1? Is that true?

Often we see the evidence mathematically that 2=1. They show very logically. Some people who cannot know this mistake then they blindly assume that math is flawed.

I believe that mathematics is one of the perfect sciences. Because until now I have not found a defect in this science. Which I love, this science is connected to each other. Some people even consider that mathematics is the language of Deity.

Back to the topic of conversation. Ever seen evidence like this?

    \begin{eqnarray*} a & = & b\\ a^{2} & = & ab\\ a^{2}-b^{2} & = & ab-b^{2}\\ \left(a+b\right)\left(a-b\right) & = & b\left(a-b\right)\\ a+b & = & b\\ 2b & = & b\\ 2 & = & 1\end{eqnarray*}

Or something like this?

    \begin{eqnarray*} a & = & b\\ a^{2} & = & ab\\ a^{2}+a^{2} & = & a^{2}+ab\\ 2a^{2} & = & a^{2}+ab\\ 2a^{2}-2ab & = & a^{2}+ab-2ab\\ 2a^{2}-2ab & = & a^{2}-ab\\ 2\left(a^{2}-ab\right) & = & \left(a^{2}-ab\right)\\ 2 & = & 1\end{eqnarray*}

Lots of evidence like this is scattered on the internet. If we do not look closely, we will be caught in logical traps and as if they are true.

So, where is the error of evidence above?

It’s simple. The error of the above evidence is in the step that makes \frac{0}{0}=1. And we know that \frac{0}{0} is undefined.

I do not see the \frac{0}{0} . Where is it? (more…)

Well Ordering Theorem

Hello, infinite-set reader. Set theory is back.

This post is the last post about Zorn’s Lemma. The next post will be different from the previous post. But in the end, all the discussion of set theory will be interrelated. My imagination, our discussion will lead to the discussion of cardinality. Pray I write diligently. Happy reading.

(x) Theorem :

Every poset has largest simply ordered subset.

Proof :

Given  poset \left(P,\leq\right). Consider poset \left(Q,\subseteq\right) with Q is the set of all simply ordered subset of poset \left(P,\leq\right). By Theorem in the previous post then every simply ordered subset of poset \left(Q,\subseteq\right) have smallest upper bound. Since \left(Q,\subseteq\right) is poset that the every simply ordered subset has smallest upper bound then by Zorn’s Lemma, Q has at least one maximum element. Suppose that the maximum element of Q is r then r is also largest simply ordered of poset P.

As already mentioned, the following theorem explains that for any set, the set can be formed as a well ordered set. This theorem is often called the Well Ordering Theorem.

Theorem : (Well Ordering Theorem)

Every set can be well ordered.

Proof (more…)

Zorn’s Lemma Part 2

Hello, infinite-set reader. Set theory is back.

Finally. Today we will discuss about Zorn’s Lemma. This lemma is also often referred to as Kuratowski’s Lemma. Lemma’s name is taken ‘the inventor’, i.e Max Zorn and Kazimierz Kuratowski. May be sometime I will post about the history of Zorn’s Lemma. The previous post is on this link. Happy reading.

(x) Theorem : (Zorn’s Lemma / Kuratowski’s Lemma)

For any non-empty poset P that each simply ordered subset has a upper bound then P has at least one maximum element.

Proof :

Since each well ordered set is simply ordered set then the proof is analog like a proof of Theorem in the previous post.

At Theorem (x) above and Theorem (y) at this link, the theorem is equivalent to saying that for any non-empty poset P that the every well/simply ordered subset has an upper bound then P has at least one maximum element. In other words, for any x\in P there is maximum element of m\in P such that x\leq m.

Theorem :

If S is the set of all simply ordered subset of poset \left(P,\leq\right) which are partially ordered by \subseteq then every simply ordered subset of S has the smallest upper bound.

Proof :

Take any R=\left\{ u,v,\ldots\right\} simply ordered subset of poset \left(S,\subseteq\right). If R=\emptyset then sup\, R=\emptyset. Next, for R\neq\emptyset, consider :

    \[ r=\cup R=\cup\left\{ u,v,\ldots\right\} =\bigcup_{u\in S}u\]

It will be proved first that r is simply ordered subset of \left(P,\leq\right). Take any a,b\in r then there is u,v\in R such that a\in u and b\in v. Since \left(R,\subseteq\right) is simply ordered set then apply u\subseteq v or v\subseteq u. Consequently a and b are both elements of u or v. Since \left(u,\leq\right) and \left(v,\leq\right) is simply ordered set then apply a\leq b or b\leq a. Proved r is simply ordered subset of P. Consequently r is the smallest upper bound of \left(R,\subseteq\right) cause for any u\in R, it is true that u\subseteq r.

Based on the above description, then simply ordered subset r of poset P above is called largest simply ordered subset of P. So r is called largest simply ordered subset of P if r is not proper subset of the other simply ordered subset of P.

Thanks for reading. See you in the next post. May be useful.

Zorn’s Lemma Part 1

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

The previous post about set theory is on this link. If you visit this website for the first time, you should read the previous posts.

(x) Theorem :

Any poset has the largest well ordered subset.

Proof :

Given any poset \left(P,\leq\right). Consider poset \left(Q,\ll\right) with Q is the set of all well ordered subset of poset \left(P,\leq\right) and \ll is a relation that defined as before. By Theorem in this post then all well ordered subset of poset \left(Q,\ll\right) has the smallest upper bound. By Theorem in this post Because of \left(Q,\ll\right) is a poset that every the well ordered subset has the smallest upper bound then Q has at least one maximum element. Suppose that the maximum element of Q is m, then m is also largest well ordered of poset P.

Next will be discussed about the theorem that became the basic of Zorn’s Lemma.

(y) Theorem :

For non-empty poset P that every the well ordered subset has upper bound then P has at least one maximum element.

Proof : (more…)

Proof / Disclaimer With Example

I think my post is a bit long and a lot of hassle lately. Today I will make a basic article. This is for website refreshment as well. Happy reading.

Most people use the equivalent method to prove mathematical statements. Even to prove the error of a statement. Though there are other ways to prove error statement, ie with an example of denial. This is considered sufficient because a statement must be perfect. Also because the truth must be perfect in mathematics.

Suppose there is a statement “If n\in\mathbb{N} then n^{2}+n+1 is prime”. Suppose we want to deny the statement. We have a presumption that n^{2}+n+1 not always prime. Then simply indicated there is a number n=k such that k^{2}+k+1 is not prime. For this case, we take n=4 then n^{2}+n+1=4^{2}+4+1=21 is not prime. This example is sufficient to prove that the above statement is false.

Thanks for reading.