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

Road to Zorn’s Lemma Part 3

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

As I said in the previous post, today we will discuss about the theorem of any poset that the every non-empty well ordered subset has the smallest bound on the poset. Happy reading.

Theorem :

Given any poset \left(P,\leq\right) with the every non-empty well ordered subset has the smallest bound in P. Given fuction f:P\rightarrow P with x\leq f\left(x\right) for all x\in P. For any p\in P then W\left(p\right) is well ordered set such that :

    \[ sup\, W\left(p\right)\in W\left(p\right)\]

and if m=sup\, W\left(p\right) then apply :

    \[ f\left(m\right)=m\]

Proof :

To prove the above theorem is sufficiently proved that W\left(p\right)=C\left(p,m\right) because if applicable W\left(p\right)=C\left(p,m\right) then m\leq f\left(m\right) by fuction definiton of f. On the other hand , since m\in W\left(p\right) then by Theorem (ii) in this post applies f\left(m\right)\in W\left(p\right). Since m is sup\, W\left(p\right) then f\left(m\right)\leq m. Thus, we get f\left(m\right)=m.

It will be proven that W\left(p\right)=C\left(p,m\right) with m=sup\, W\left(p\right). Given any H\subseteq W\left(p\right) with H\neq\emptyset. Further taken any r\in H then by Theorem (y) in this post can be consider C\left(p,r\right). Furthermore, r\in H\cap C\left(p,r\right). Because of C\left(p,r\right) has the smallest element then H\cap C\left(p,r\right) also has the smallest element. Furthermore, inf\, H\cap C\left(p,m\right)=inf\, H. In other words, for any H\subseteq W\left(p\right) with H\neq\emptyset then H has the smallest element which resulted W\left(p\right) is well ordered set. Next, by Theorem (i) in this post then C\left(p,r\right)\subseteq W\left(p\right). Thus, we get p\in W\left(p\right) and if r\in W\left(p\right) then p\leq r. In other words, p is the smallest element of W\left(p\right).

It will then be proved that W\left(p\right) satisfy the p-chain C\left(p,m\right) axioms. It has been proved that W\left(p\right) is well ordered set. According to the hypothesis on the proof of this theorem, then W\left(p\right) has the largest element. Let’s say m=sup\, W\left(p\right). Defined V=W\left(p\right)\cup\left\{ m\right\}. Will be shown V is p-chain. Since W\left(p\right) is well ordered set then V also well ordered set with p is the smallest element and m is the largest element. Condition (i) of definition p-chain is fulfilled.

Next, take any z\in V with z\neq m then z\in W\left(p\right). Since z\neq m then z^{+}\in V. Note that z and z^{+} are the last two elements on p-chain C\left(p,z^{+}\right). The result is valid z^{+}=f\left(z\right) for all z^{+}\in V. Condition (ii) of definition p-chain is fulfilled.

Next, take any U\subseteq V with U\neq\emptyset then m is the upper bound U. There are two possibilities. The first possibility, if there is no r\in W\left(p\right) such that x\leq r for all x\in U then sup\, U=m\in V. Second possibility, if there is r\in W\left(p\right) such that x\leq r for all x\in U then sup\, U=r\in W\left(p\right)\subseteq V. Condition (iii) of definition p-chain is fulfilled. In other words V is a p-chain with m being its largest element.

Since W\left(p\right) is the set of all elements p-chain then V=W\left(p\right). Then we get W\left(p\right) is p-chain C\left(p,m\right).

You should reopen my previous post to get a good understanding. This is because my posts are related to each other. If you forget a little definition or theorem, you will be confused. I try to make this discussion easier by providing links. I hope this makes it easier for you to understand this discussion.

Thanks for reading. May be useful.

Road To Zorn’s Lemma Part 2

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

Before reading this post, you should read the previous post first. It deals with the definition of C\left(p,r\right) and W\left(p\right). As a reminder only if you forget. The post is still about the character of C\left(p,r\right) and W\left(p\right). Happy reading.

(x) Theorem :

If r,s\in W\left(p\right) then either of the following two applies, s\in C\left(p,r\right) or r<s.

Proof :

Defined S=C\left(p,r\right)\cap C\left(p,s\right) then S is well ordered set because S is subset of C\left(p,r\right) and C\left(p,s\right) both of which are well ordered set. Further, by definition p-chain condition (i) then S\neq\emptyset and by definition p-chain condition (iii) then x=sup\, S are in C\left(p,r\right) and also in C\left(p,s\right) which resulted x\in S. Next, assume s\notin C\left(p,r\right) then x\neq s. if x\neq r then by definition p-chain condition (ii) x^{+}=f\left(x\right)\in S. Contradictions with x=sup\, S. In other words, if s\notin C\left(p,r\right) then r=x\in S which resulted r\in C\left(p,s\right). Because of r\neq s then by definition p-chain condition (i) we get r<s. Even though s\in C\left(p,r\right) and r<s are two things that are contradictory then the assumption is rejected. Theorem is proven.

(y) Theorem :

If r\in W\left(p\right) then there is a unique C\left(p,r\right) such that C\left(p,r\right)=\left\{ s\in W\left(p\right)|s\leq r\right\}.

Proof : (more…)

p-Chain – Road To Zorn’s Lemma Part 1

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

Starting this post, we’ve entered about Zorn’s Lemma. This discussion will start from several definitions and theorems that later lead to Zorn’s Lemma. Happy reading.

***

For any poset it is not guaranteed that every non-empty well ordered subset has an upper bound. It automatically does not have the smallest upper bound too. As an example \left\{ \left(a_{1};a_{2};a_{3};\ldots\right),\left(b_{1};b_{2};b_{3};\ldots\right)\right\}. Any non-empty well ordered subset of the poset does not have the smallest upper bound.

In this discussion, we will discuss about posets that each of the non-empty well ordered subset have the smallest upper bound.

Definition :

Given any poset \left(P,\leq\right) with each of the non-empty well ordered subset having the smallest upper bound on P. Given function f:P\rightarrow P with x\leq f\left(x\right) for all x\in P. For any p\in P defined p-chain that denoted byC\left(p,r\right) under the condition :

(i) C\left(p,r\right) is well ordered subset with p being the smallest element and r is the largest element.

(ii) For all x^{+}\in C\left(p,r\right) apply x^{+}=f\left(x\right)

(iii) The smallest upper bound of any non-empty subset of C\left(p,r\right) is in C\left(p,r\right)

In the above definition, the condition (ii), such terms clearly apply only tox\in C\left(p,r\right)-\left\{ r\right\}. It because, if x=r is always true that r\leq r^{+}. On the other hand, r^{+}\in C\left(p,r\right). Then there is a contradiction with the definition of p-chain conditions (i) that r is the largest element of C\left(p,r\right). Next defined

    \[W\left(p\right)=\left\{ r\in P|\exists p\in P\mbox{ such that }C\left(p,r\right)\right\}\]

Next will be given properties about p-chain C\left(p,r\right) and W\left(p\right) which is presented in the theorems below.

Theorem : (more…)

Well Ordered Set

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

As I said in the previous post, this post will discuss about the well ordered set. Happy reading.

In a poset, not necessarily the poset has the smallest element. So it is with the subsets. This gives rise to a new understanding which is a special occurrence of a poset.

Definition :

A poset is said to be well ordered set if for any non-empty subset of the poset, it has the smallest element.

Example :

(i) Poset \left\{ \left(\ldots,a_{3};a_{2};a_{1}\right),\left(\ldots;b_{3};b_{2};b_{1};\ldots;c_{3};c_{2};c_{1}\right)\right\} does not have the smallest element. In the subset there are also those that do not have the smallest element. For the example , simply ordered subset \left\{ a_{1},a_{2},a_{3},\ldots\right\}, \left\{ b_{1},b_{2},b_{3},\ldots\right\}, and \left\{ c_{1},c_{2},c_{3},\ldots\right\} none of them has the smallest element. So the poset is not a well ordered set.

(ii) Poset \left\{ \left(a_{1};a_{2};a_{3};\ldots\right)\right\} is well ordered set.

Theorem :

Every well ordered set is simply ordered set.

Proof : (more…)

Simply/Linearly/Totally Ordered Set

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

Today we will discuss about simply ordered set. Sometimes also called linearly or totally ordered set. To read this post, you should read this post first. You need the definition of an initial segment to understand the theorem we are going to discuss. Happy reading.

In a poset is not necessarily between one element with another can be compared. For example \left\{ \left(a;b\right),\left(c;d\right)\right\} is a poset but between b and c is incommensurable.

Definition :

Partial order \leq in the set S it says simple (linear, total) order in S if for any x,y\in S apply :

    \[ x\leq y\mbox{ or }y\leq x\]

Then any poset \left(S,\leq\right) it says simply (linearly, totally) ordered set if \leq is a simple (linear, total) order in S.

Example :

(i) \left(\left\{ a,b,c\right\} ,\left\{ \left(a,a\right),\left(b,b\right),\left(c,c\right),\left(a,b\right),\left(b,c\right),\left(a,c\right)\right\} \right) is simply ordered set.

(ii) Poset of the set of all natural numbers\left(\omega,\left(\in\mbox{ or }=\right)\right) it’s also simply ordered set.

Theorem :

Given any simply ordered set \left(S,\leq\right). Then the set of all initial segments of S is simply ordered by \subseteq.

Proof : (more…)

Initial Segment

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

In this post will be introduced about the initial segment. Definition of initial segment will be used in the process of proving Zorn’s Lemma. So you have to make a special mark for this post. It will be important for the future.

Definition :

Given any poset \left(S,\leq\right). For any a\in P defined I\left(a\right) with :

    \[ I\left(a\right)=\left\{ x|\left(x\in S\right)\wedge\left(x<a\right)\right\} \]

Furthermore I\left(a\right) is called the initial segment of P defined by a. If I\left(a\right) is not empty set then I\left(a\right) is called \emph{proper initial segment} of P.

Example :

Given poset \left\{ \left(a;b;c\right),\left(m;n;o\right)\right\} then I\left(c\right)=\left\{ a,b\right\}, I\left(n\right)=\left\{ m\right\}, and I\left(a\right)=\emptyset. (more…)