9
$\begingroup$

After reading about the question, I've come to believe that it would suffice to exhibit and automorphism of that is not order preserving. However, I'm unsure of how to construct such an automorphism, and am a bit uncertain if my approach is sound. Any guidance would be appreciated.

The exact question reads: Let N = ⟨N,S,0⟩ where N = {0,1,2,...} and S is the successor function. Show that the binary relation {⟨a, b⟩ | a, b ∈ N and a < b} is not definable over N

  • 2
    $\mathbb{N}$ with successor has no non-trivial automorphisms, so this isn't going to work.2012-10-23
  • 1
    Do you mean in a manner similar to [this MO question](http://mathoverflow.net/questions/110414/methods-for-proving-non-fo-definability) and [this math.SE question](http://math.stackexchange.com/q/214869/8348)?2012-10-23
  • 1
    I would be inclined to try to use the Compactness Theorem with a nicely chosen set of extra statements.2012-10-23
  • 0
    I feel like I'm missing something; can anyone explain intuitively why this can't be done? Or perhaps a definition of constructible over N?2012-10-23
  • 0
    a < b iff exists d, b = a + Sd. so I think it is definable.2012-10-23
  • 0
    @spernerslemma: There is no addition in this context.2012-10-23
  • 0
    @AsafKaragila, what is there then?2012-10-23
  • 2
    @spernerslemma: Read the question. Zero and successor. In fact this is one of the ways to show that addition and multiplication are not definable from only the successor: if they were then the order would be definable as well.2012-10-23
  • 0
    @AsafKaragila, and equality?2012-10-23
  • 0
    @spernerslemma: Commonly equality is part of the language without the need to explicitly say so.2012-10-24

1 Answers 1

9

Suppose that $\varphi ( x , y )$ is a first-order formula defining the relation $<$ in $\mathcal{N} = ( \mathbb{N} , S , 0 )$; that is $$\mathcal{N} \models \varphi ( m,n ) \quad\Leftrightarrow\quad m < n.$$ Note that if $\mathcal{M}$ is any elementary extension of $\mathcal{N}$ it must be that $\varphi (x,y)$ defines a strict total (linear) order on the universe of $\mathcal{M}$. Consider the structure $\mathcal{M} = ( M , s , 0 )$ where

  • $M = \mathbb{N} \cup ( \mathbb{Z} \times \{ 0 , 1 \} )$;
  • $s(m) = m+1$; $s(m,i) = (m+1,i)$.

Then $\mathcal{M}$ is an elementary extension of $\mathcal{N}$. Let $a_0 = (0,0)$ and $a_1 = (0,1)$. As $\varphi$ defines a strict total order on $M$ we may assume without loss of generality that $$\mathcal{M} \models \varphi ( a_0 , a_1 ).$$

Consider the following function $\sigma : M \to M$:

  • $\sigma ( m ) = m$; and
  • $\sigma ( m , i ) = ( m , 1-i )$ (i.e., $\sigma$ switches the two disjoint copies of $\mathbb{Z}$).

It is quite easy to show that $\sigma$ is an automorphism of $\mathcal{M}$, and therefore $$\mathcal{M} \models \varphi ( \sigma(a_0) , \sigma(a_1) ).$$ But as $\sigma ( a_0 ) = a_1$ and $\sigma ( a_1 ) = a_0$ we have that $$\mathcal{M} \models \varphi ( a_1 , a_0 ),$$ contradicting the fact that $\varphi$ defines a strict total order on $M$!

  • 1
    Why must it be that $\varphi$ defines a total order on $\mathcal{M}$ just because it defines one on $\mathcal{N}$?2012-10-23
  • 4
    Because the statement that "$\varphi$ defines a total order" is first order.2012-10-23
  • 0
    related to this, is there a way to show that there is a way to define only integers and nothing else (no reals or rationals) using only the successors function?2018-10-22