0
$\begingroup$

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.

  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?

$\endgroup$
  • $\begingroup$ @ThomasAndrews No, if you will add more, then it will not be a chain. Does my definition for set C is incorrect? $\endgroup$ – John D Apr 30 at 20:00
  • $\begingroup$ 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.$ $\endgroup$ – Thomas Andrews Apr 30 at 20:25
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – John D Apr 30 at 21:03
  • $\begingroup$ 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.$ $\endgroup$ – Thomas Andrews Apr 30 at 21:05
  • $\begingroup$ Please note that we discuss regarding infinite on anti-chain and not chain. Also, I have already define one as D. $\endgroup$ – John D Apr 30 at 21:05
  • $\begingroup$ @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).$ $\endgroup$ – Thomas Andrews Apr 30 at 21:16
  • $\begingroup$ 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. $\endgroup$ – John D Apr 30 at 21:29
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.