Finding maximal chain and maximal anti-chain in partially ordered set

We define $$R$$ on $$\mathbb{N}^\mathbb{N}$$ such that: $$\forall f,g:\mathbb{N}\to \mathbb{N}$$, $$fRg$$ if and only if $$\forall n\in \mathbb{N}, f(n)\leq g(n)$$. Then, $$R$$ is partially ordered set on $$\mathbb{N}^\mathbb{N}$$.

We divide the question into two following questions:

1. Find a maximal chain in $$\langle \Bbb{N}^\Bbb{N},R\rangle$$ and prove it.

2. Does there exist a maximal anti-chain in $$\langle \Bbb{N}^\Bbb{N},R\rangle$$ that has infinity elements. Prove your answer.

Im trying to prove this a few days, however I got stuck in some places in my proof.

1. We mark the maximal chain as $$C=$$ {$${f: \forall n>0, f(n)=0}$$}. First, we will show that is a chain. Let be $$f,g\in C$$ we need to show $$fRg$$ or $$gRf$$. We assume, $$g\not R f$$ and will show $$fRg$$. Let be $$n\in \Bbb{N}$$ we need to show $$f(n)\leq g(n)$$. Therere two possible cases: $$n=0$$ or $$n\neq 0$$

• Case 1: $$n\neq 0$$. $$f,g\in C$$ and $$n\neq 0$$ then $$f(n)=0$$ and $$g(n)=0$$ then $$0=0$$ so $$fRg$$.
• Case 2: $$n=0$$. $$g\not R f$$ so exist $$t\in \Bbb{N}$$ such that $$g(t)\not \leq f(t)$$ then $$f(t)\not \neq g(t)$$ and $$f(t). There is two possible cases: $$t=n$$ or $$t\not \neq n$$

• Case 2.1: $$t\not \neq n$$. $$t\not \neq n$$ and $$n=0$$ then $$t\neq 0$$. $$f,g\in C$$ then $$f(n),g(n)=0$$ so $$0\leq 0$$ then $$fRg$$.

• Case 2.2: $$t=n$$ (Here I got stuck)

Now, we will try to prove that C is maximal chain.

Let $$g\in \Bbb{N}^\Bbb{N}$$ and assume $$g\not \in C$$. we need to show $$C\cup$${$$g$$} is not a chain. Let $$f\in C$$ and we need to show $$f\not R g$$ and $$g\not R f$$. First we will show $$gRf$$, we define n>0. we need to show $$g(n)\not \leq f(n)$$. $$f\in C$$ and $$n>0$$ then $$f(n)=0$$ and $$g(m)\not \neq 0$$. $$g\not \in C$$ then exist m>0 so that $$g(m)\not \neq 0$$. $$f(n)=0$$ and $$g(m)\not \neq 0$$ and we choose $$m=n$$ (is it correct?) then $$g(m)\not \leq f(m)$$ then $$g\not R f$$. Now we will show $$f\not R g$$, we choose $$n=0$$. we need to show $$f(n)\not \leq g(n)$$. $$g\not \in C$$ then exist $$m>0$$ so that $$g(m)\neq 0$$ (Here I got stuck)

Now, Lets continue to 2.

1. We mark the maximal anti-chain as $$D=\{f: \exists n\in \Bbb{N}\text{ such that }f(n)=1\text{ and }\forall m\neq n, f(m)=0\}.$$ We need to show: $$D$$ is anti-chain, $$D$$ is maximal anti-chain, $$D$$ has infinity elements.

First we will show that D is anti-chain. Let $$f,g\in D$$ and assume $$f\neq g$$ we need to show $$f\not R g$$ and $$g\not R f$$. $$f\in D$$ so exists $$n\in \Bbb{N}$$ such that $$f(n)=1$$. $$g\in D$$ so exists $$m\in \Bbb{N}$$ such that $$g(m)=1$$. So there are two possible cases: $$m=n$$ or $$m\neq n$$

• Case 1: $$m\neq n$$. $$f,g\in D$$ and $$m\neq n$$ then $$f(m)=0$$ and $$g(n)=0$$. $$f(m)=0$$ and $$g(m)=1$$ then $$g\not R f$$. $$f(n)=1$$ and $$g(n)=0$$ then $$f\not R g$$.

• Case 2: $$m=n$$ (Here I got stuck)

Now we will prove that D is maximal anti-chain. Let $$g\in \Bbb{N}^ \Bbb{N}$$ and assume $$g\not \in D$$. We need to show $$D\cup$${g} is not anti-chain. Let $$f\in D$$ and assume $$f\neq g$$ (Here I got stuck).

Now we need to show that D has infinity elements. How can we prove it? which statement should be proved?

• @ThomasAndrews No, if you will add more, then it will not be a chain. Does my definition for set C is incorrect? – John D Apr 30 at 20:00
• Yes, your definition of $C$ is correct, and it is a maximal chain. But you need to only prove that if $g\notin C$ then there is some $f\in C$ such that neither $fRg$ nor $gRf.$ – Thomas Andrews Apr 30 at 20:25

For (1):

Your definition of $$C$$ is fine.

The proof that $$C$$ is a chain is easier if you prove first:

For $$f,g\in C,$$ we have $$fRg$$ if and only if $$f(0)\leq g(0).$$

Proof:

If $$fRg$$ then $$f(0)\leq g(0)$$ by definition of $$R.$$

On the other hand, if $$f(0)\leq g(0)$$ then, since $$f,g\in C,$$ we also have $$f(k)=0\leq 0=g(k)$$ for $$k\neq 0,$$ so $$f(n)\leq g(n)$$ for all $$n\in\mathbb N,$$ and hence $$fRg.$$

Then, since $$\leq$$ is a total order on $$\mathbb N,$$ either $$f(0)\leq g(0)$$ or $$g(0)\leq f(0)$$, so we must have $$f Rg$$ or $$gRf$$ for any $$f,g\in\mathbb C.$$

To prove that $$C$$ is maximal, we need,

For $$g\notin C,$$ that $$C\cup \{g\}$$ is not a chain. To prove this, show that there is at least one $$f\in C$$ such that neither $$f Rg$$ nor $$gRf.$$

Given $$g\notin C,$$ let $$f(n)\begin{cases}g(0)+1&n=0\\0&n\neq 0\end{cases}$$

By definition $$f\in C.$$

Since $$g\notin C,$$ we must have $$g(k)\neq 0$$ for some $$k\neq 0.$$ Then, since $$0=f(k) we cannot have $$gRf.$$ On the other hand, since $$f(0)>g(0),$$ we h cannot have $$fRg.$$ So $$C\cup \{g\}$$ is not a chain.

For (2):

Showing $$D$$ is an anti-chain: Prove that if $$m=n,$$ then $$f=g.$$

Showing that $$D$$ is maximal For $$g\notin D.$$ Then either $$g(m)=0$$ for all $$m\in\mathbb N,$$ which gives $$g for all $$f\in D$$, or $$g(m)>0$$ and $$g(n)>0$$ for two $$m\neq n.$$ But then you can define $$f(k)=\begin{cases}1&k=m\\0&k\neq m\end{cases}$$

Then $$f\in D$$.

We have $$f\neq g$$ since $$m\neq n$$, so $$f(n)=0< g(n)$$ and we have $$f(k)\leq g(k)$$ for all $$k$$, so $$fRg,$$ and hence $$D\cup\{g\}$$ is not an anti-chain.

In both cases, it is easier start with a sequence of function definitions. In the anti-chain case, for each $$k\in \mathbb N,$$ define $$f_k:\mathbb N\to\mathbb N$$ as:

$$f_k(n)=\begin{cases}1&n=k\\0&n\neq k\end{cases}$$

Then define $$D=\{f\mid \exists k\in\mathbb N: f=f_k\}$$. This is the same as your definition, but it is easier to use.

For example, we can easily show that:

$$f_{k_1}=f_{k_2}$$ iff $$k_1=k_2.$$

Proof: If $$k_1=k_2$$ then clearly $$f_{k_1}=f_{k_2}.$$ And if $$k_1\neq k_2$$, then $$f_{k_1}(k_1)=1\neq 0=f_{k_2}(k_1).$$

Now, if $$f_m,f_n\in D,$$ with $$f_m\neq f_n$$, then we have $$m\neq n$$ and hence $$f_{m}(m)=1>0=f_n(m)$$ and hence that it is not possible for $$f_mRf_n.$$

Proving $$D$$ is infinite is by the map: $$\mathbb N\to D$$ sending $$n\mapsto f_n,$$ which is one-to-one.

Proving that $$D$$ is maximal is the tricky part. If $$g\notin D,$$ we have two cases:

1. $$g(n)=0$$ for all $$n\in\mathbb N.$$ B But then $$gRf$$ for all $$f\in D.$$
2. $$g(n)>0$$ for some $$n.$$ Then show $$f_nRg.$$ It is not possible for $$f_n=g$$ since we assumed $$g\notin D.$$

So $$D\cup\{g\}$$ is not an anti-chain.

There is an uncountably infinite anti-chain in $$(\mathbb N^{\mathbb N},R).$$ For each $$S\subseteq \mathbb N,$$ define a function:

$$f_S(n)=\begin{cases}0&n=2k, k\notin S\\1&n=2k, k\in S\\1&n=2k+1, k\notin S\\0&n=2k+1, k\in S\end{cases}$$

For $$S,T\subseteq \mathbb N$$ that $$f_S R f_T$$ if and only if $$S\subseteq T$$ and $$\mathbb N\setminus S\subseteq \mathbb N\setminus T$$, which proves that $$S=T.$$

[I don't believe this co-chain is maximal, but Zorn's lemma implies that any co-chain can be extended to a maximal co-chain.]

• The claim "For $f,g\in C,$ we have $fRg$ if and only if to $f(0)\leq g(0).$ is exactly where I got stuck, case 2.1 when $n=t=0$, this case is exactly your claim, so any hint how to prove it will be appreciated. Regarding proving C is maximal, when we trying to prove $f\not R g$ you wrote "since $f(0)>g(0)$..." this statement since you define $f(n)$, but is it correct? if yes, why? I ask it since I know we need to let $f\in C$ arbitrary and not to define it. why we are allowed to define $f(n)$? – John D Apr 30 at 21:03
• We defined $f(0)=g(0)+1,$ so $f(0)>g(0).$ As I said, we have to only fine one function $f\in C$ such that neither $fRg$ nor $gRf.$ So, given $g$, I find such an $f$ by defining $f$ in terms of $g.$ – Thomas Andrews Apr 30 at 21:05
• Please note that we discuss regarding infinite on anti-chain and not chain. Also, I have already define one as D. – John D Apr 30 at 21:05
• @JohnD For why the equivalence $fRg\iff f(0)\leq g(0)$ when $f,g\in C$: If $f,g\in C$ then for $n\neq 0,$ we have $0=f(n)\leq g(n)=0.$ So $fRg$ if and only if $f(0)\leq g(0).$ – Thomas Andrews Apr 30 at 21:16
• I`m confused, on the one hand, you wrote for $n\neq 0$, we have $0=f(n)\leq g(n)=0$ which understood since $f,g\in C$ and we got this from definition of C. But, in the other hand you wrote $f(0)\leq g(0)$ which in this case $n=0$ and we did not prove anything for this case, $n=0$. This refers when we try to prove C is chain, before we define $f(n)$ when we prove that C is maximal. – John D Apr 30 at 21:29

For problem one, considering the different cases seems to have sligthly confused you. In case 2, you are only considering the case $$n=0$$ ($$n>0$$ was case 1). So when you correctly conclude that there must exist $$t \in \mathbb N$$ with $$f(t) < g(t)$$, then there are exactly 2 cases

2.1: $$t>0$$, and

2.2: $$t=0$$.

Case 2.1 is easily shown to be impossible, as by definition $$f(t)=g(t)=0$$ for $$t>0$$. So case 2.2 must happen, so we have $$f(0) < g(0)$$. Now this is even a bit more than what you need to prove in case 2: $$f(n) \le g(n)$$.

Together in cases 1) and 2) you proved that from $$g\not R f$$ follows $$\forall n \in \mathbb N:f(n) \le g(n)$$, which means $$fRg$$.