Examples of automorphisms on structures

Question

For some structure $(M,I)$ with $M$ a set and $I$ the interpretation of the constants, functions, and predicates, what is an example of a such a structure such that for each $a$ of $M$ there are only finitely many $b$ in $M$ such that there is an automorphisms $f$ of $\mathcal{m}$ such that $f(a) = b$, but there are uncountably many automorphisms of $\mathcal{m}$.

Geometrically, I've been told to think of a "complete binary tree" as such a structure. But why? How could one write it in the form above? What about $(R,*)$?

Answer 1

Hint: The complete binary tree is a nice example. Use the binary predicate symbol $M(x,y)$, where $M(x,y)$ holds if $x$ is the mother (immediate predecessor) of $y$. Any automorphism has to preserve level, and for any $a$ there are only finitely many $b$ at the same level as $a$.

Answer 2

An equivalence relation on an infinite set $M$ having exactly one equivalence class of cardinality $n$ for each positive integer $n$, and no infinite equivalence class.

Answer 3

The example $(\mathbb Z,R)$ where $R=\{(x,y)\in\mathbb Z\times\mathbb Z:|x|\lt|y|\}$ is best possible, in the sense that the orbit $\{f(a):f\text{ is an automorphism}\}$ has cardinality at most $2$ for each $a$.