Exercise about orderings

Question

Prove that the following ordering (defined on Fun$(\mathbb{N},\mathbb{N})$): $$f \prec g \Longleftrightarrow f(k)<g(k) \quad \text{where }k=\min\{n \mid f(n) \neq g(n)\}$$ is a total ordering and not a well-ordering.

This is what I've done: First of all, we observe that $\prec$ on Fun$(\mathbb{N},\mathbb{N})$ is a strict ordering, because is irreflexive ($\min \{n \mid f(n) \neq f(n)\} \subset \mathbb{N}$ is by definition the empty set, and so the minimum $k$ doesn't exists. This means that $f \nprec f$), asymmetric and transitive. In facts:

• Asimmetry: We have that $f \prec g \Longleftrightarrow f(k)<g(k)$. Therefore it can't be $g \prec f$, because $k$ is always the same, since it is the minimum of the same set, and so also $g(k)$ and $f(k)$ are the same and, since < is a strict ordering on $\mathbb{N}$, we have that $f(k)<g(k) \Longrightarrow g(k) \not < f(k)$, that means $g \nprec f$.

For transitivity (and the rest of the demonstration) I really don't know what to do, because I have to demonstrate that: $$f(k)<g(k) \land g(i)<h(i) \Longrightarrow f(k)<h(i) \land k=i=\min\{n \mid f(n) \neq h(n)\}$$ Where obviously $k=\min\{n \mid f(n) \neq g(n)\}$ and $i=\min\{n \mid g(n) \neq h(n)\}$.

Answer 1

Suppose $f \prec g \land g \prec h$. Then there are $k$ and $i$ such that $f(n) = g(n)$ for $n < k$ and $f(k) < g(k)$ and $g(n) = h(n)$ for $n < i$ and $g(i) < h(i)$

There are then two cases to consider

1. $k\le i$: you have

   • $f(n) = g(n)=h(n)$ for $n < k$ and $f(k) < g(k) \le h(k)$,
   • so $f(n) = h(n)$ for $n < k$ and $f(k) < h(k)$,
   • implying $f \prec h$

2. $k\gt i$: you have

   • $f(n) = g(n)=h(n)$ for $n < i$ and $f(i) = g(i) \lt h(i)$,
   • so $f(i) = h(i)$ for $n < i$ and $f(i) < h(i)$,
   • implying $f \prec h$

and thus $f \prec g \land g \prec h \implies f \prec h$