In my book Complexity Theory by C. Papadimitriou he talks about first order axiomations of $\mathbb N$ and non-standard models. But what I do not get is that his examples of non-standard models did not fulfill the axioms he gives later on, and so some points he makes seem unclear to me. To be more specific, he considers the signature with $0, <, \sigma, +, \times, \uparrow$ (the last is exponentiation) and the first order axioms:
NT1: $\forall x( \sigma(x) \ne 0 )$
NT2: $\forall x \forall y (\sigma(x) = \sigma(y) \Rightarrow x = y)$
NT3: $\forall x ( x = 0 \lor \exists y \sigma(y) = x )$
NT4: $\forall x ( x + 0 = x )$
NT5: $\forall x \forall y(x + \sigma(y) = \sigma(x + y))$
NT6: $\forall x (x \times 0 = 0 = 0)$
NT7: $\forall x \forall y(x \times \sigma(y) = (x\times y) + x)$
NT8: $\forall x ( x \uparrow 0 = \sigma(0) )$
NT9: $\forall x\forall y(x \uparrow \sigma(x) = (x\uparrow y)\times x)$
NT10: $\forall x(x < \sigma(x))$
NT11: $\forall x\forall y(x < y \Rightarrow \sigma(x) \le y)$
NT12: $\forall x\forall y(\neg (x < y) \Leftrightarrow y \le x)$
NT13: $\forall x \forall y \forall z((x < y) \land (y < z)) \Rightarrow x < z)$
And a last one related to modulo arithmetic. Then in the section about non standard models, he gives $N_p$ where all operations are interpreted modulo $p$ and the ordering is $0 < 1 < \ldots < p-1$. The other model $N'$ he just defines $\sigma$ on it, and it contains all nonnegative integers, and all complex numbers of the form $n + mi$ where $n,m$ are integers.
But his first model contradicts NT10, as $\sigma(p-1) = 0$. And for the second model, like $\mathbb C$ is not orderable in a linear fashion, the same applies here too as $i$ is contained in it, which contradicts the order axioms given above. Further, he writes that there is no set of first order sentences that differentiate $\mathbb N$ and $N'$, but yes, this also contradict my observations.
So, do I understand something wrong here?
EDIT: Because it was asked for, the last axiom related to modulo reads:
$$ \forall x \forall y \forall z \forall z' ( \mbox{mod}(x,yz) \land \mbox{mod}(x,y,z') \Rightarrow z = z' ) $$ where $\mbox{mod}(x,y,z)$ is an abbreviation for $\exists w(x = y\times w) + z \land z < y)$. Shorthands like $x \le y$ or $x \ne y$ are defined in the usual way.
I took a look at the book, and Papadimitriou never claims the structures $N_p$ and $N'$ are models of the axioms NT1-14.
On p. 92, he writes:
And then he goes on to define $\mathbf{N}_p = \{0,\dots,p-1\}$ and $\mathbf{N}' = \mathbb{N}\sqcup \mathbb{Z}[i]$. Here he's not saying that $N_p$ and $N'$ are models for some set of axioms he hasn't even introduced yet... he's just saying they're "appropriate for the vocabulary of number theory", which just means they come with interpretations of the symbols in the vocabulary $\{0,<,\sigma,+,\times,\uparrow\}$.
But he does make a strong claim about $\mathbf{N}'$:
Unfortunately, he does no such thing in Section 5.6 - instead, he just shows that there is some countable nonstandard model for the complete theory of $\mathbf{N}$. He's also being a bit sneaky here, since he has only defined the interpretation of $\sigma$ on $\mathbf{N}'$ and vaguely alluded to the fact that the other symbols "can be defined in a compatible manner that we omit". For example, he certainly doesn't intend to define $\times$ on $\mathbf{N}'$ as ordinary multiplication of complex numbers! This is where your claim that $\mathbf{N}'$ can't be linearly ordered goes awry - it's true that $\mathbb{Z}[i]$ doesn't admit a linear ordering which is compatible with its standard addition and multiplication operations (since $-1$ is a square)... but the addition, multiplication, and orderings Papadimitriou has in mind on $\mathbf{N}'$ are totally different ones.
What's really going on is that there is a countable nonstandard model $\widehat{\mathbf{N}}$ for the complete theory of $\mathbf{N}$, and in the reduct $\widehat{\mathbf{N}}|_\sigma$ to the vocabulary $\{\sigma\}$ (meaning you forget about the interpretations of the other symbols), you can show that $\widehat{\mathbf{N}}|_\sigma$ is isomorphic to $\mathbf{N}'$ (the $\sigma$-graph has to look like an $\mathbb{N}$-chain followed by countably many $\mathbb{Z}$-chains). Using some isomorphism $f\colon \widehat{\mathbf{N}}|_\sigma \to \mathbf{N}'$ between the $\{\sigma\}$-structures, we can define the interpretations of the other symbols in the vocabulary on $\mathbf{N}'$ to match those on $\widehat{\mathbf{N}}$ [for example, $a\times b = f(f^{-1}(a)\times f^{-1}(b))$]. But it's a consequence of Tennenbaum's Theorem that the resulting structure on $\mathbf{N}'$ has to be extremely weird (not computable). So there's no way that Papadimitriou could have written down the definition of $\times$ on $\mathbf{N}'$, even if he wanted to.
Anyway, in the next chapter, on p. 124, he gives the list of axioms NT1-NT14. But as far as I can tell, he never mentions nonstandard models for them, or says anything about $\mathbf{N}_p$ or $\mathbf{N}'$ again.
It seems like on this point, the book is sloppily written, but not wrong.