Can natural numbers with multiplication alone define the order relation?

Question

Consider the set $\mathbb{N}$ of natural numbers, including $0$. The structure $(\mathbb{N};+,\cdot)$ can define the standard order relation $\leq$. In fact, you don't even need multiplication to define the order relation. That raises the question, is it possible to define the standard order relation in the structure $(\mathbb{N};\cdot)$?

Answer 1

Any permutation of the primes extends to an automorphism of $(\mathbb{N};\cdot)$. Since we can permute primes without preserving order (to put it mildly), this means that the ordering is not definable in $(\mathbb{N};\cdot)$ via any logic, let alone first-order logic.

(OK, that's not quite fair - there isn't a universally agreed upon definition of "logic." However, any of the usual notions - e.g. "regular logic" a la Ebbinghaus/Flum/Thomas - have as a required property isomorphism invariance. The above applies to any such logic.)

To put this "logic-independence" claim in perspective, consider $\mathfrak{C}:=(\mathbb{N};\mathsf{suc})$ where $\mathsf{suc}$ is the successor map. The structure $\mathfrak{C}$ is rigid, so automorphism-based arguments cannot be used here. Moreover, $<$, $+$, and $\cdot$ are each definable in $\mathfrak{C}$ via second-order logic. However, none of them is $\mathsf{FOL}$-definable in $\mathfrak{C}$. Showing this latter point requires a more complicated argument. Basically, the point is that while automorphism-based arguments don't always succeed in proving non-definability results, when they do they prove extremely strong non-definability results.