\subsection{The limit case}\label{LimitSection}
Most investigations of rank-to-rank embeddings to date have focused on 
elementary embeddings \(j : V_\alpha\to V_\alpha\) where
\(\alpha = \kappa_\omega(j)\) or \(\alpha = \kappa_\omega(j) + 1\), 
since assuming Choice, these are the only 
rank-to-rank embeddings there are. The following very simple 
fact turns out to 
play a central role in these investigations: if \(\lambda\) is a limit ordinal, 
an elementary embedding from \(V_\lambda\) to \(V_\lambda\) extends in at most 
one way to an elementary embedding from \(V_{\lambda+1}\) to \(V_{\lambda+1}\).

\begin{dfn}
 For a structure $M$, $\mathscr{E}(M)$ denotes the set of all elementary
 embeddings $j:M\to M$.
\end{dfn}

\begin{dfn}\label{CanonicalExtension}
Let \(\lambda\) be a limit ordinal and $j\in \mathscr{E}(V_\lambda)$.
The {\it canonical extension of \(j\)} is the function
$j^+ : V_{\lambda+1}\to V_{\lambda+1}$
defined 
$j^+(X) = \bigcup_{\alpha < \lambda} j(X\cap V_\alpha)$.
\end{dfn}
The canonical extension $j^+$ is a function $V_{\lambda+1}\to 
V_{\lambda+1}$.
However, it is well known that it can fail to be elementary. (For 
example, let $\kappa$ be least
such that there is an elementary $j:V_\lambda\to V_\lambda$
with $\crit(j)=\kappa$,
and show that $j^+$ is not elementary.)
But if \(j\) 
{\it does} extend to some
\(i\in\mathscr{E}(V_{\lambda+1})\), or even just to a $\Sigma_1$-elementary 
$i:V_{\lambda+1}\to V_{\lambda+1}$, then clearly 
\(i(V_\lambda)=V_\lambda\) and \(i = j^+\).

Let $\lambda$ be a limit ordinal.
It follows that every \(j\in\mathscr{E}(V_{\lambda+1})\)
is definable over \(V_{\lambda+1}\) from 
parameters, in fact, from its own restriction \(j\rest 
V_\lambda\). (Since \(V_\lambda\) is closed under 
ordered 
pairs, \(j\restriction V_\lambda\in
V_{\lambda+1}\).) However,
$j$ is not definable over $V_{\lambda+1}$
from any element of $V_\lambda$, and no
\(j\in\Eee(V_\lambda)\) is definable from parameters over 
$V_\lambda$:
\begin{tm}\label{LimitUndefinable}
 Let $\delta$ be an ordinal, $j\in\Eee(V_\delta)$
and  $p\in V_\delta$,
with $j$  definable over $V_\delta$ from the parameter $p$.
 Then $\delta=\beta+1$ is a successor and $\rank(p)=\beta$.
\end{tm}
\begin{proof}
Suppose not. We adapt the proof of Suzuki's Fact.
Fix $(k,\varphi,\beta)$ such that  $k<\om$, $\varphi$ is a $\Sigma_k$ 
formula and
 $\beta<\delta$, and
for some $p\in V_\beta$ we have
 $j_p\in\Eee(V_\delta)$ where
 \[ j_p=\{(x,y)\in V_\delta\cross V_\delta: 
V_\delta\sats\varphi(p,x,y)\}.\]
Say that $q\in V_\beta$ is \emph{$\om$-bad} if $j_q\in\Eee(V_\delta)$.

Let $\mu_0$ be the least critical point
among all such (fully elementary) embeddings $j_q$ (minimizing
over all $\om$-bad parameters $q$).
Let $p_0\in V_\beta$ witness this, so 
$j_{p_0}\in\mathscr{E}(V_\delta)$ and $\crit(j_{p_0})=\mu_0$.

For $n<\om$, say that $q\in V_\beta$ is
\emph{$n$-bad} iff
$j_q:V_\delta\to V_\delta\text{ and is }\Sigma_n\text{-elementary}$.
Let
$A_n=\{q\in V_\beta: q\text{ is }n\text{-bad}\}$.
So $A_n\in V_\delta$ and note that $A_n$ is definable over $V_\delta$ from the 
parameter $\beta$.

Since $j=j_{p_0}$ is fully elementary, $j(A_n)\inter V_\beta=A_n$
(note $j(\beta)\geq\beta$).
Let $A=\bigcap_{n<\om}A_n$, so $A\in V_\delta$.
Note that $j_q\in\Eee(V_\delta)$ for every $q\in A$.

The sequence $\left<A_n\right>_{n<\om}$ can easily be coded
by a set in $V_\delta$ (with methods like in the next section; if $\delta$ is a 
limit then it is in fact literally in $V_\delta$), 
and therefore
\[ j(A)=\bigcap_{n<\om}j(A_n), \]
so $p_0\in j(A)$.
Therefore $V_\delta\sats$``$\exists q\in j(A)$
such that $\crit(j_q)<j(\mu_0)$'' (as witnessed by $p_0$).
Pulling this back with the elementarity of $j$,
$V_\delta\sats$``$\exists q\in A$ such that
$\crit(j_q)<\mu_0$.'' But this contradicts the minimality of $\mu_0$.
\end{proof}

\subsection{A flat pairing function}\label{subsec:coding}
If $\delta$ is a limit ordinal then $V_\delta$ is closed under pairs $\{x,y\}$,
and hence, ordered pairs $(x,y)$, represented in the standard fashion as 
$(x,y)=\{\{x\},\{x,y\}\}$.
But this fails in the successor case, at least when we use this standard 
representation: For example, $V_\delta\in V_{\delta+1}$ but the pair 
$\{V_\delta,\emptyset\}\notin V_{\delta+1}$. 
It is therefore useful to employ a different representation or \emph{coding} of 
ordered pairs with the property that for every infinite ordinal $\alpha$, for all $x,y\in 
V_\alpha$, the code \(\lceil x,y\rceil\) for the pair $(x,y)$ is an element
of $V_\alpha$. In this case, the function
\((x,y)\mapsto \lceil x,y\rceil\) is called a {\it flat pairing function}.

There are many different flat pairing functions,
and which one we use will not really be relevant in our applications.
All we will really require of the pairing function is that it be a \(\Sigma_0\)-definable
injection \(\Phi : V\times V\to V\) such that \(\Phi``(V_\alpha\times V_\alpha)\subseteq V_\alpha\)
for all infinite ordinals \(\alpha\).

Nevertheless, let us define the {\it Quine-Rosser pairing function}, which
is officially the pairing function we employ below.
The basic idea is to code a pair \((x,y)\) by a
labeled disjoint union of \(x\) and \(y\).
Somewhat more precisely, we will take two disjoint copies
$V_0$ and $V_1$ of the universe $V$
and  
bijections $f_0 : V\to V_0$ and $f_1: V\to V_1$,
which are both rank-preserving over all sets of rank $\geq\om$.
The ordered pair $(x,y)$ is then coded by the set 
$\lceil x,y\rceil = f_0``x\cup f_1``y$.

To implement this idea without leaving \(V\),
let $V_0$ be the class of sets that do not contain the empty set
and let $V_1$ be the class of sets that do.
Let $s : V\to V$ be defined by setting
\(s(n) = n+1\) for all \(n < \omega\) and \(s(u) = u\) for all \(u\notin 
\omega\). Then let $f_0: V\to V_0$ be defined by $f_0(X)=s``X$
and  \(f_1 : V\to V_1\) be defined by
\(f_1(u) = (s``X)\cup\{\emptyset\}$.

\begin{dfn}
  For sets $x,y\in V$, let 
\[\lceil x,y\rceil = f_0``x\cup f_1``y,\]
where \(f_0\) and \(f_1\) are as defined above.
The set $\lceil x,y\rceil$ is the {\it Quine-Rosser pair}
coding $(x,y)$.
\end{dfn} 
The Quine-Rosser pairing function \((x,y)\mapsto \lceil x,y\rceil\)
establishes a bijection from \(V\times V\) to \(V\) whose inverse is the function
\(z\mapsto (f_0^{-1}[z],f_1^{-1}[z])\).
It is easy to show that for any set \(u\),
\(\rank(f_0(u))\) and \(\rank(f_1(u))\)
are bounded by \(1+\text{rank}(u)\), which implies
\[\rank(\lceil x,y\rceil ) \leq 1 + \max \{\rank(x),\rank(y)\}.\]
In particular, for any infinite ordinal \(\alpha\),
the Quine-Rosser pairing function restricts to a bijection from 
\(V_{\alpha}\times V_\alpha\)
to \(V_\alpha\).
Moreover, this function is
$\Sigma_0$-definable over the structure $(V_\alpha,\in)$.\footnote{
Of course we can't presuppose another notion of pairing
when we discuss the definability. So to be clear,
the definability means
there is a $\Sigma_0$ formula $\varphi$ of 3 variables such
that $\lceil x,y\rceil =z\iff \varphi(x,y,z)$.}

From now on, we shift notation, and whenever we talk about ordered pairs,
we mean Quine-Rosser pairs, and whenever we talk about
binary relations $R$ on $V_\alpha$ (where $\alpha\geq\om$)
we will literally mean that $R$ is a set of Quine-Rosser pairs,
and similarly for $n$-ary relations. Therefore 
 $R\in V_{\alpha+1}$. Moreover, note that there is a $\Sigma_0$ formula
in the language of set theory such that for any such
$\alpha$ and binary relation $R$ on $V_\alpha$ and $x,y\in V_\alpha$,
we have $xRy$ iff $V_{\alpha+1}\sats\varphi(R,x,y)$. This will be used
in particular for functions $f:V_\alpha\to V_\alpha$.

\subsection{The successor case}
Our observations so far suggest the following natural 
questions. Suppose \(\xi\) is an ordinal and
$j\in\Eee(V_{\xi+2})$.
Can $j$ be definable over $V_{\xi+2}$ from some parameter
(necessarily of rank $\xi+1$)?
And if $n\geq 1$, then more specifically, can $j$ be definable over 
$V_{\xi+2}$ from $j\rest V_{\xi+1}$? Note here that, because
we are using Quine-Rosser pairs, $j\rest V_{\xi+1}\in V_{\xi+2}$.
In this section, we answer these questions.
It turns out that most of the results from the limit case generalize
to the case of arbitrary even ordinals.

At first glance, it seems that the definition
of the canonical extension operation ({Definition \ref{CanonicalExtension}})
makes fundamental use of the assumption that \(\lambda\) is a limit ordinal.
In particular, this definition exploits the
hierarchy \(\langle V_\alpha\rangle_{\alpha < \lambda}\) stratifying
\(V_{\lambda}\); 
this hierarchy seems to have no analog at the successor even levels.
But on further thought, we could have defined \(j^+(X)\) for \(X\in V_{\lambda+1}\)
as follows: 
\[j^+(X) = \bigcup \{j(a) : a\in V_\lambda\text{ and }a\subseteq X\}\]
Thus \(j^+(X)\) is the union of the image of \(j\) on all the subsets of \(X\)
that belong to \(V_\lambda\).

At successor ordinals we must generalize this slightly, instead
taking the union of the image of \(j\) on all the subsets of \(X\) 
that are {\it coded} in \(V_\lambda\).
\begin{dfn}\label{dfn:coding}
  Suppose \(a\) and \(b\) are sets.
  For any set \(x\),
  let \((a)_x\) 
  denote the set \(\{y : \lceil x,y\rceil \in a\}\),
  and let \((a \mid b) = \{(a)_x : x\in b\}\).
\end{dfn}
Thus for \(a,b\in V_\lambda\), \((a \mid b)\) is the subset of \(V_{\lambda}\)
whose elements are the sections \((a)_x\in V_\lambda\) of the 
binary relation coded by \(a\)
that are indexed by some \(x\in b\). 
Say a set \(X\subseteq V_\lambda\) is {\it coded in \(V_\lambda\)}
if \(X = (a \mid b)\) for some \(a,b\in V_\lambda\).
For \(\lambda\) a limit ordinal, every set coded in \(V_\lambda\) belongs to \(V_\lambda\),
but if \(\lambda\) is a successor ordinal, then the sets coded in \(V_\lambda\)
are precisely those \(X\subseteq V_\lambda\) such that
there is a partial surjection from \(V_{\lambda-1}\) onto \(X\). 
\begin{dfn}
Suppose \(\lambda\) is an ordinal. For any function \(j : V_\lambda \to V_\lambda\), 
the {\it canonical extension of \(j\)} is the function \(j^+ : V_{\lambda+1}\to V_{\lambda+1}\)
defined by 
\[j^+(X) = \bigcup \{(j(a) \mid j(b)) : a,b\in V_{\lambda}\text{ and }(a \mid b)\subseteq X\}
\qedhere\]
\end{dfn}
While \(j^+\) is well-defined for any function \(j\), it is not of much interest
unless \(j\) has the property that \((j(a) \mid j(b)) = (j(a') \mid j(b'))\)
whenever \((a \mid b) = (a' \mid b')\).

Suppose \(a,b\in V_\lambda\), \(X\in V_{\lambda+1}\), 
and \((a \mid b)\subseteq X\).
The fact that \((a \mid b)\) is included in \(X\) is a first-order expressible property of \(a,b,\) and \(X\) 
in \(V_{\lambda+1}\), so
for any \(k \in \mathscr E(V_{\lambda+1})\),
\((k(a) \mid k(b))\subseteq k(X)\).
It follows that \((k\restriction V_\lambda)^+(X)\subseteq k(X)\), whether \(\lambda\) is even or odd.
The reverse inclusion, however, will be true if and only if \(\lambda\) is even.
\begin{dfn}
  Suppose \(\lambda\) is an ordinal. An embedding \(j : V_\lambda\to V_\lambda\) is
  {\it cofinal} if for any set \(c\in V_\lambda\), there exist sets \(a,b\in V_\lambda\) such that
  \(c\in (j(a) \mid j(b))\).
\end{dfn}
Equivalently, \(j : V_\lambda\to V_\lambda\) is cofinal if \(j^+(V_\lambda) = V_\lambda\).
It follows immediately that if \(k\in \mathscr E(V_{\lambda+1})\) and
\(k = (k\restriction V_\lambda)^+\), 
then \(k\restriction V_\lambda\) must be cofinal. The converse is also true:

\begin{lem}\label{CofinalEmbeddingsExtendCanonically}
  Suppose \(k\in \mathscr E(V_{\lambda+1})\)
  and \(k\restriction V_\lambda\) is cofinal. Then \(k = (k\restriction V_\lambda)^+\).
  \begin{proof}
    Fix \(X\in V_{\lambda+1}\). Our comments above show that
    \((k\restriction V_\lambda)^+(X)\subseteq k(X)\). For the reverse
    inclusion, fix \(c\in k(X)\). We will show \(c\in (k\restriction V_\lambda)^+(X)\).

    Since \(k\restriction V_\lambda\) is cofinal,
    there are sets \(a,b\in V_\lambda\) such that \(c\in (k(a) : k(b))\).
    Let \(b' = \{x\in b : (a)_x\in X\}\), so that \((a \mid b') = (a \mid b)\cap X\).
    Now  \[c\in  (k(a)  \mid  k(b))\cap k(X) = 
    k((a  \mid  b)\cap X) = k\left(a  \mid  b'\right)\subseteq (k\restriction V_\lambda)^+(X)\]
    This shows \(k(X)\subseteq (k\restriction V_\lambda)^+(X)\), completing the proof.
  \end{proof}
\end{lem}

The periodicity phenomenon is driven by the following lemma:
\begin{lem}\label{AutoCofinal}
  Suppose \(j : V_{\lambda+2}\to V_{\lambda+2}\) is an elementary embedding
  such that \((j\restriction V_\lambda)^+ = j\restriction V_{\lambda+1}\).
  Then \(j\) is cofinal.
  \begin{proof}
    Fix \(j : V_{\lambda+2}\to V_{\lambda+2}\) and \(C\in V_{\lambda+2}\).
    We must show that there exist \(A,B\in V_{\lambda+2}\) such that
    \(C\in (j(A)  \mid  j(B))\). Let \(B\) consist of those sets \(x\in V_{\lambda+1}\)
    such that the binary relation \(\{(a,b) : \lceil a,b\rceil\in x\}\) coded by \(x\)
    is the graph of a function \(f_x : V_{\lambda}\to V_{\lambda}\). 
    By elementarity, \(j(B) = B\).

    Now define
    \(A = \{\lceil x,y\rceil \in B\times V_{\lambda+1} : f_x^+(y)\in C\}\).
    In other words, for each \(x\in B\), \((A)_x = (f_x^+)^{-1}[C]\).
    Now \[j(A) = \{\lceil x,y\rceil \in B\times V_{\lambda+1} : f_x^+(y)\in j(C)\}.\]
    Let \(w = \{\lceil a, j(a)\rceil: a\in V_\lambda\}\), so that 
    \(f_w = j\restriction V_\lambda\). Then \(w\in B\) and
    \[(j(A))_w = (f_w^{+})^{-1}(j(C)) = ((j\restriction V_\lambda)^+)^{-1}[j(C)] = 
    (j\restriction V_{\lambda+1})^{-1}[j(C)] = C.\]
    Therefore \(C= (j(A))_w \in (j(A)  \mid  B) = (j(A)  \mid  j(B))\), as desired.
  \end{proof}
\end{lem}

\begin{tm}\label{LocalPeriodicity}
  Suppose \(\lambda\) is an even ordinal and \(j : V_\lambda \to V_\lambda\) is an
  elementary embedding. Then \(j\) is cofinal. Suppose in addition that
  \(j\) extends to an elementary embedding \(k : V_{\lambda+1}\to V_{\lambda+1}\).
  Then \(k = j^+\).
  \begin{proof}
    Assume by induction that the corollary is true for ordinals smaller than \(\lambda\).
    If \(\lambda\) is a limit ordinal, then \(j\) is trivially cofinal.
    If \(\lambda\) is a successor ordinal, then by our induction hypothesis applied to \(\lambda-2\),
    \(j\restriction V_{\lambda+1} = (j\restriction V_\lambda)^+\), so
    \(j\) is cofinal by Lemma \ref{AutoCofinal}.
    Since \(j\) is cofinal, 
    Lemma \ref{CofinalEmbeddingsExtendCanonically} implies
    that if \(j\) extends to an elementary embedding \(k : V_{\lambda+1}\to V_{\lambda+1}\),
    then \(k = j^+\). This completes the proof.
  \end{proof}
\end{tm}

The requirement that \(\lambda\) be even in the previous theorem is unusual, 
but one can show that the theorem fails whenever \(\lambda\) is odd.
The proof given here is an elaboration on that of 
{Theorem \ref{LimitUndefinable}}.
\begin{tm}\label{EvenUndefinable}
Suppose \(\alpha\) is an ordinal,
\(j \in \mathscr E(V_\alpha)\),
and \(a,b\in V_{\alpha}\). Then \(j\) is not definable over
\(V_\alpha\) from parameters in \((j(a)  \mid  j(b))\).
\begin{proof}
Suppose towards a contradiction that the theorem fails.
Then there is
a formula \(\varphi(v_0,v_1,v_2)\) and a parameter \(p\in (j(a)  \mid  j(b))\) such that
\[j(u) = w\iff V_{\alpha}\sats \varphi(u,w,p)\] for all \(u,w\in 
V_{\alpha}\).
For \(q\in V_{\alpha}\), define a relation
\[j_q = \{(u,w)\in V_{\alpha}^2 :  V_{\alpha}\sats\varphi(u,w,q)\}.\]

For \(n \leq \omega\), \(q\in V_\alpha\) is {\it \(n\)-bad}
if $j_q : V_{\alpha}\to V_{\alpha}$ is a nontrivial \(\Sigma_n\)-elementary embedding
and there exist \(a',b'\in V_\alpha\) such that \(q \in (j_q(a')  \mid  j_q(b'))\).

So $p$ is $\om$-bad. Let $\kappa = \min \{\crit(j_q) :  q\text{ is 
}\omega\text{-bad}\}$.
Fix an \(\omega\)-bad parameter \(r\) such that \(\crit(j_r) = \kappa\).

Fix \(c,d\in V_\alpha\) with \(r \in (j_r(c) \mid j_r(d))\).
For each \(n \leq \omega\), let \[d_n = \{x\in d :  (c)_x\text{ is 
\(n\)-bad}\}\]
By the elementarity of \(j_r\),
\[j_r(d_n) = \{x\in j_r(d) :  (j_r(c))_x\text{ is }n\text{-bad}\}.\]
Let \(e = \{\lceil n,x\rceil : x\in d_n\}\), so that \((e)_n = d_n\).
Since \(d_\omega = \bigcap_{n < \omega} (e)_n\),
\(j_r(d_\omega) = \bigcap_{n < \omega} (j_r(e))_n = \bigcap_{n <\omega} j_r(d_n)\).
It follows that 
\[j_r(d_\omega) = \bigcap \{x \in j_r(d) : j_r(c)_x \text{ is 
}\omega\text{-bad}\}.\]
In particular, \(r\in (j_r(c)  \mid  j_r(d_\omega))\) 
and every \(q\in (j_r(c)  \mid  j_r(d_\omega))\) is \(\omega\)-bad, so
\[\min \{\crit(j_q) : q\in (j_r(c)  \mid  j_r(d_\omega))\}= \kappa.\]
Therefore letting \(\bar \kappa = \min \{\crit(j_q) : q\in (c 
\mid d_\omega)\}\),
\(j_r(\bar \kappa) = \kappa\), which contradicts that \(\kappa\) is the
critical point of \(j_r\).
\end{proof}
\end{tm}

Putting everything together, we can
now prove Theorem \ref{tm:cumulative_periodicity};
that is, given 
$j\in\mathscr{E}(V_\lambda)$,
then $j$ is definable from parameters
over $V_\lambda$ iff $\lambda$ is odd:

\begin{proof}[Proof of Theorem \ref{tm:cumulative_periodicity}]
Suppose \(\lambda\) is even. Then by Theorem \ref{LocalPeriodicity},
\(j\) is cofinal, which means that every \(p\in V_\lambda\)
belongs to \((j(a):j(b))\) for some \(a,b\in V_\lambda\).
Therefore by Theorem \ref{EvenUndefinable},
\(j\) is not definable from any parameter in \(V_\lambda\).

On the other hand, if \(\lambda\) is odd, then \(j = (j\restriction V_{\lambda-1})^+\)
by Theorem \ref{LocalPeriodicity}, and therefore \(j\) is definable over \(V_\lambda\)
from \(j\restriction V_\lambda\), or more precisely from 
the set \(\{\lceil x,j(x)\rceil : x\in V_{\lambda-1}\}\), which belongs to \(V_\lambda\).
\end{proof}
{"config": "arxiv", "file": "2006.01103/extensionandcofinality2.tex"}