We know that in the language $L=\{+,*\}$, it is possible define the natural order $\geq$ on $(\mathbb{Z},+,*)$ in the following way:

$a\geq b$ if and only if $a-b$ is a sum of 4 squares.

In fact, by the theorem of 4 squares, we have that each positive natural number can be written as sum of 4 squares. In this way we get a necessary and sufficient condition of an integer number to be positive and this condition depends only by the language $L$.

The question is the following: Is it true a sort of inverse implication?

Is it possibile define the sum operation of $\mathbb{Z}$ in the language $\{\geq\}$?

  • $\begingroup$ I believe one can define the predecessor and successor of an integer using only $\leq$. Is that enough? $\endgroup$ – user512346 Aug 13 at 16:16
  • $\begingroup$ Is it possible define a successor because you can use the well-ordering principle? Infact for each $k\in Z$ you can consider the set $A=\{a>k\}$ that it’s isomorphic to $(\mathbb{N},>)$ that it is well-ordered. So there exists a minimum for $A$ and we can define $k+1:=min A$. $\endgroup$ – Federico Fallucca Aug 13 at 16:32
  • $\begingroup$ @FedericoFallucca You still need to pick a $0$ to define addition in terms of successor. $\endgroup$ – eyeballfrog Aug 13 at 17:15
  • $\begingroup$ @eyeballfrog Even including $0$ isn't enough - first-order logic doesn't in general allow recursive definitions. (But this is harder to show, since $(\mathbb{Z}, 0,\le)$ is rigid.) $\endgroup$ – Noah Schweber Aug 13 at 17:17
  • 1
    $\begingroup$ @eyeballfrog Yes, that's correct. Note that this is what we mean when we talk about a function being (un)definable in a structure: that there is (no) formula in the language of that structure which, in that structure, defines the graph of the function in question. $\endgroup$ – Noah Schweber Aug 13 at 17:31

No. For instance, let $X=\{0,1\}\times\mathbb{Z}$ with the lexicographic order. Identifying $\mathbb{Z}$ with $\{0\}\times\mathbb{Z}$ in $X$, then $(\mathbb{Z},\geq)$ is elementarily embedded in $(X,\geq)$ (you can prove this using Ehrenfeucht–Fraïssé games, for instance). If addition were definable (even with parameters) in $(\mathbb{Z},\geq)$, the same definition would give an addition operation that makes $(X,\geq)$ into an ordered abelian group. But that is impossible since $X$ has elements greater than every integer but not any elements less than every integer to be their negatives.

If you more strongly want addition to be definable without parameters, then there's a much simpler argument that it's impossible: the map $f(x)=x+1$ is an automorphism of $(\mathbb{Z},\geq)$. If addition were definable without parameters, then $f$ would preserve addition, but $f(x+y)=x+y+1$ whereas $f(x)+f(y)=x+y+2$.

  • $\begingroup$ Why did you delete your original automorphism answer (which I just saw after posting mine)? Is there something obvious I'm missing there? It seems to work ... $\endgroup$ – Noah Schweber Aug 13 at 17:16
  • $\begingroup$ It works only for definability without parameters. $\endgroup$ – Eric Wofsey Aug 13 at 17:18
  • $\begingroup$ That's worth saying explicitly, since it's not part of the question (and explains the value of your answer over the simpler automorphism argument). $\endgroup$ – Noah Schweber Aug 13 at 17:19

No, this is not possible. (Although things like successor and predecessor are definable - e.g. $Pred(x)=y$ iff $y< x$ and $\forall z(z<x\implies z\le y)$.) One way to see this is by considering automorphisms of the structure in question. The map $$f:\mathbb{Z}\rightarrow\mathbb{Z}: z\mapsto z+14$$ (say) is an automorphism of the structure $(\mathbb{Z},\le)$, and hence must preserve any relation or function definable in $(\mathbb{Z},\le)$. However, we have $$3+1=4\quad\mbox{ but }\quad f(3)+f(1)=3+14+1+14=32\color{red}{\not=}18=f(3+1).$$ We can also prove stronger results, concretely classifying all possible relations and functions definable in $(\mathbb{Z},\le)$ (and then just checking that $+$ isn't on the list). But such an approach takes more work.

Of course, this method has drawbacks. For example, consider the expansion $(\mathbb{Z},0,\le)$. This structure is rigid (= no nontrivial automorphisms), so we can't use the argument above to show that anything is undefinable. Yet addition is still undefinable in this structure - it just requires a more intricate argument, such as Eric Wofsey's answer. Relevant tools for proving general undefinability results include Ehrenfeucht-Fraisse games and quantifier elimination (of expansions).


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.