total order on all functions of natural numbers

248 Views Asked by At

My discrete math textbook has a question: let $f$ be a set of all functions from $\mathcal{N}$ to $\mathcal{N}$. $K$ is a relation onto $f$. For $(f,g) \in f$: $(f,g) \in K$ iff for all $n\in \mathcal{N}$, $f(n) \le g(n)$. We need to prove that $K$ is not a total order onto $f$. I can define a function $f$ such that $$f(1) = 2; f(2)=1;f(n)=n$$ where $n \notin\{1,2\}$. Similarly, we can define a function $g$ such that $$g(1) = 1; g(2)=2;g(n)=n$$ where $n \notin\{1,2\}$. Does this prove that the function is not a total order?

1

There are 1 best solutions below

8
On BEST ANSWER

Yes, it does. $f$ and $g$ are incomparable according to $R$ since $g(1)<f(1)$ but $f(2)<g(2)$.