Ein Funktionssymbol/Bijektiv/Permutation/Zykel/Beispiel

Das Symbolalphabet ${}S$ bestehe (neben Variablen) aus einem einstelligen Funktionssymbol ${}f$. Die Ausdrucksmenge ${}\Gamma$ bestehe aus einem Satz, der inhaltlich besagt, dass eine erfüllende Menge genau ${}n$ Elemente besitzen muss, und einen Satz, der besagt, dass die Funktion bijektiv ist. Ein Modell für ${}\Gamma$ ist also eine ${}n$-elementige Menge ${}M$ zusammen mit einer fixierten Permutation

$f^{M}\colon M\longrightarrow M$

auf dieser Menge. Eine Teilmenge ${}T\subseteq M$ der Form (wir schreiben ${}f$ statt ${}f^{M}$)

${}T=\{m,f(m),f^{2}(m),\ldots ,f^{k-1}(m)\}\,$

mit ${}f^{k}(m)=m$ und mit ${}f^{i}(m)\neq m$ für alle ${}i$, ${}1\leq i\leq k-1$, nennt man Zykel zu ${}f$ der Länge ${}k$. Die Menge ${}M$ ist die disjunkte Vereinigung von Zykeln unterschiedlicher Länge. Zwei Elemente ${}m,n\in M$ sind genau dann elementar äquivalent, wenn sie beide in einem gleichlangen (aber nicht unbedingt im gleichen) Zykel liegen: Einerseits lässt sich die Zykellänge ${}k$ erststufig formalisieren, etwa durch

$f^{k}x=x\wedge f^{k-1}x\neq x\wedge \ldots \wedge fx\neq x,$

wobei die Potenzen ausgeschrieben werden müssen. Andererseits kann man einfach Automorphismen angeben, indem man aus jedem Zykel ${}Z_{j}$ ein Element ${}m_{j}$ auswählt und dieses auf ein beliebiges Element ${}n_{j}=\psi (m_{j})$ eines Zykels gleicher Länge schickt, wobei jeder Zykel genau einmal getroffen wird. Durch

${}\psi (f^{i}(m_{j})):=f^{i}(\psi (m_{j}))\,$

erhält man einen wohldefinierten Automorphismus. Insbesondere kann man einen Automorphismus konstruieren, der ${}m$ auf ${}n$ abbildet. Wenn man ${}m$ auf ${}n$ (elementar äquivalent zu ${}m$) abbilden möchte, so ist dadurch schon bestimmt, wohin man die Elemente aus dem Zyklel zu ${}m$ abbilden muss. Es muss nämlich ${}\psi (f(m))=f(\psi (m))$, ${}\psi (f(f(m)))=f(f(\psi (m)))$, u.s.w. gelten.