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 there is a single function such that :

Proof :

By taking , , , and is function from to with for all 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 and are functions defined in the Theorem (x). Defined with .

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 there is a single function such that :

Proof : (more…)

## Addition Operation on Natural Numbers – Set Theory

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

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 and the function , then there is a single function such that :

Proof :

Based on the above hypothesis, it can be formed :

with is fuction from to . Obtained, 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 there is a single function such that :

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 ; 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.

## 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 . Consider poset with is the set of all simply ordered subset of poset . By Theorem in the previous post then every simply ordered subset of poset have smallest upper bound. Since is poset that the every simply ordered subset has smallest upper bound then by Zorn’s Lemma, has at least one maximum element. Suppose that the maximum element of is then is also largest simply ordered of poset .

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 that each simply ordered subset has a upper bound then 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 that the every well/simply ordered subset has an upper bound then has at least one maximum element. In other words, for any there is maximum element of such that .

Theorem :

If is the set of all simply ordered subset of poset which are partially ordered by then every simply ordered subset of has the smallest upper bound.

Proof :

Take any simply ordered subset of poset . If then . Next, for , consider :

It will be proved first that is simply ordered subset of . Take any then there is such that and . Since is simply ordered set then apply or . Consequently and are both elements of or . Since and is simply ordered set then apply or . Proved is simply ordered subset of . Consequently is the smallest upper bound of cause for any , it is true that .

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

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 . Consider poset with is the set of all well ordered subset of poset and is a relation that defined as before. By Theorem in this post then all well ordered subset of poset has the smallest upper bound. By Theorem in this post Because of is a poset that every the well ordered subset has the smallest upper bound then has at least one maximum element. Suppose that the maximum element of is , then is also largest well ordered of poset .

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

(y) Theorem :

For non-empty poset that every the well ordered subset has upper bound then 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 that we will use. Happy reading.

Theorem :

Given poset with is the set of all well ordered subsets of poset and is a relation that defined as before. For any simply ordered subset of poset then always have the smallest upper bound.

Proof :

Given simply ordered subset of . Suppose then . Next, let’s say is non-empty simply ordered subset of . Consider :

It will be proved that is a well ordered subset of . Take any with then between the set , there is at least one that the element is on . Suppose the set is . Since is well ordered set then has the smallest element. Suppose the smallest element is . It will be proved that is also the smallest element for .

Take any with . Will be proven . Because of then there is such that . On the other hand, since is simply ordered set then or . If then and if then it is not possible to apply . It because, if then which results in a contradiction with is the smallest element of . In other words, apply for all . So for any , has the smallest element. We get is well ordered set which resulted . Thus, we get cause for any apply .

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

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 with the every non-empty well ordered subset has the smallest upper bound on , then has at least one maximum element.

Proof :

Given is poset with the every non-empty well ordered subset has the smallest upper bound on . Take any function with for all . Next, take any . By Theorema (post sebelumnya) then can be consider well ordered set such that bounded from above and . It will be shown that is one of the maximal elements of . Take any . If or then it is always true that “if then ”. Also if and then it is always true that “if then ”. In other words, is one of the maximal elements of .

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

Theorem :

Given is the set of all well ordered subsets of poset . Then can be partial order by by definition, for any :

Proof : (more…)