Rigid structure with a non-trivial embedding

Question

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?

Answer 1

Sure, $(\mathbb{N},<)$ is rigid, but $n\mapsto n+1$ is an embedding in the order language.

Answer 2

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.

Answer 3

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.

Answer 4

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.