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

Question

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.

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

Here is what I already prove for 1,2. Let`s start with 1.

---

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)$. There`re 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)<g(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, Let`s continue to 2.

2. 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?

Answer 1

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)<g(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<f$ 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.]

Answer 2

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