Rigid structure with a non-trivial embedding Definition 


*

*A structure $M$ is rigid if the only automorphism $f:M\rightarrow M$ is the identiy. 

*An embedding $f:M\rightarrow M$ is non-trivial, if $f$ is not the identity.


Question Is there an example of a rigid structure $M$ with a non-trivial embedding? 
 A: Sure, $(\mathbb{N},<)$ is rigid, but $n\mapsto n+1$ is an embedding in the order language.
A: Recall the standard example for two well-founded ordered sets which embed into one another, but are not isomorphic.
$A=\{(n,k)\mid n<2k\}$ and $B=\{(n,k)\mid n<2k+1\}$, both ordered by $(n,k)\prec(n',k')\iff k=k'$ and $n<n'$.
Each of $A$ and $B$ is of course rigid, but they have many self-embeddings.
You can also construct a rigid tree of height $\omega$, and then embed it into practically any subtree: construct the levels by induction, and index the nodes. The root has index $2$; now suppose that that the $n$-th level was constructed, the node with index $k$ will have $k$ successors indexed by the first $k$ numbers still available.
Convince yourself this is a rigid tree; and it is easy to see that you can embed this tree above any node inside the tree itself.
A: Note that we can do even better: there is an ordinal $\alpha=(A, <)$ such that there is a nontrivial elementary embedding from $\alpha$ to itself!
Proof: let $\alpha=\epsilon_0\cdot\omega$ (using $\epsilon_0$ here is overkill, but I'm lazy). For $\beta\in\alpha$, let $[\beta]$ be the greatest $n$ such that $\epsilon_0\cdot n<\beta$. Now consider the following map $f$:


*

*If $[\beta]<17$, then $f(\beta)=\beta$.

*If $[\beta]\ge17$, then $f(\beta)=\epsilon_0+\beta$.
(Obviously $17$ here is arbitrary.) Using Ehrenfeucht-Fraisse games, it's not hard to show that this is indeed an elementary embedding. Basically, the first point missed can't be described in a first-order way, so the structure can't see (in a first-order way) what's been changed.

If you want a really silly overkill method of showing this, assume a measurable cardinal $\kappa$ and look at the embedding of $ON$ into itself induced by the ultrapower . . .
EDIT: Actually, it just occurred to me that this approach isn't completely silly! It (or variants) let you prove (precise versions of) "Every reasonable class of rigid structures has an element which has a nontrivial elementary embedding into itself." So that's nice.
A: For a bijective example, consider metric spaces and contraction mappings. The space of nonnegative real numbers is rigid, and division by $2$ gives an embedding.
