Home » Set Theory

Category Archives: Set Theory

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.

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

Basic of Zorn’s Lemma – Initial Segment Part 2

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

To read this post, you should read the previous post first. It deals with the definition of \ll that we will use. Happy reading.

Theorem :

Given poset \left(Q,\ll\right) with Q is the set of all well ordered subsets of poset \left(P,\leq\right) and \ll is a relation that defined as before. For any simply ordered subset of poset \left(Q,\ll\right) then always have the smallest upper bound.

Proof :

Given S simply ordered subset of \left(Q,\ll\right). Suppose S=\emptyset then sup\, S=\emptyset. Next, let’s say S=\left\{ u,v,\ldots\right\} is non-empty simply ordered subset of \left(Q,\ll\right). Consider :

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

It will be proved that \left(w,\leq\right) is a well ordered subset of \left(P,\leq\right). Take any s\subseteq w with s\neq\emptyset then between the set u,v,\ldots, there is at least one that the element is on s. Suppose the set is u. Since \left(u,\leq\right) is well ordered set then u\cap s has the smallest element. Suppose the smallest element is a. It will be proved that a is also the smallest element for \left(s,\leq\right).

Take any b\in s with b\neq a. Will be proven a<b. Because of b\in s then there is v\in S such that b\in v. On the other hand, since \left(S,\ll\right) is simply ordered set then u\ll v or v\ll u. If v\ll u then a<b and if u\ll v then it is not possible to apply b<a . It because, if b<a then b\in u which results in a contradiction with a is the smallest element of u\cap s. In other words, apply a\leq b for all b\in s. So for any s\subseteq w, s has the smallest element. We get \left(w,\leq\right) is well ordered set which resulted w\in Q. Thus, we get w=sup\, S cause for any u\in S apply u\ll w.

Based on the description above, for the next well ordered subset w of poset P on above is called the greatest ordered subset of P. So w is called the greatest ordered subset of P if w is not the initial segment of a well ordered subset of P.

Thanks for reading. May be useful.

Basic of Zorn’s Lemma – Initial Segment

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

In this post will be discussed about a theorem that will become the basic of Zorn’s Lemma. To remind you of initial segment, you should visit this post first. The definition of the initial segment will be used later.

Theorem :

For any poset \left(P,\leq\right) with the every non-empty well ordered subset has the smallest upper bound on P, then P has at least one maximum element.

Proof :

Given \left(P,\leq\right) is poset with the every non-empty well ordered subset has the smallest upper bound on P. Take any function f:P\rightarrow P with x\leq f\left(x\right) for all x\in P. Next, take any p\in P. By Theorema (post sebelumnya) then can be consider well ordered set W\left(p\right) such that W\left(p\right) bounded from above and m=sup\, W\left(p\right)\in W\left(p\right). It will be shown that m is one of the maximal elements of P. Take any x\in P. If x\in W\left(p\right) or x\leq p then it is always true that “if m\leq x then x=m”. Also if x\notin W\left(p\right) and x\nleq p then it is always true that “if m\leq x then x=m”. In other words, m is one of the maximal elements of P.

Next we will discuss one of the theorems. But before discussing the theorem, will be given a new definition of the symbol \ll which also produces the following theorem.

Theorem :

Given Q is the set of all well ordered subsets of poset \left(P,\leq\right). Then Q can be partial order by \ll by definition, for any u,v\in Q :

    \[ \left(u\ll v\right)\equiv\left(u\mbox{ is the initial segment of }v\mbox{ or }u=v\right)\]

Proof : (more…)