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

Prove or Disprove:

For all $f:\mathbb{N}\to\mathbb{N}$ exists $g:\mathbb{N}\to\mathbb{N}$ such that $g$ is immediate successor of $f$ in ${R}$.

I think this is correct so I`m trying to prove it, however I stuck in my proof.

Here is how I tried to prove it:

Let be $f:\mathbb{N}\to\mathbb{N}$ a function and we define $g:\mathbb{N}\to\mathbb{N}$, $g(n)=f(n)$ if n $\neq$ 0. and $g(n)=f(n)+1$ if n=0.

According to the definition, an immediate successor $g \in \mathbb{N}^\mathbb{N}$ of $f \in \mathbb{N}^\mathbb{N}$ is such that $f\neq g$ and $fRg$ and if $h\in \mathbb{N}^\mathbb{N}$ satisfies $fRh$ and $hRg$, then either $h=f$ or $h=g$.

please let me know if how I start is correct but I don`t have any idea how to continue if that is correct.


You're well on your way.

Since $fRh$ and $hRg$, we have for any $n\in \Bbb N$ that $f(n)\leq h(n)\leq g(n)$. Now, for any $n\geq 1$ we have $f(n) = g(n)$, which means that we must also have $h(n) = f(n) = g(n)$.

Then for $n = 0$, we have $$f(n)\leq h(n) \leq g(n) = f(0) + 1$$No matter what $h(0)$ is, it must be either $f(0)$ or $g(0)$, meaning $h$ is either the same function as $f$ or the same function as $g$.


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.