Does there exist a bijection that is not eventually equal to the identity, but has a finite number of "crosses"?

Consider a bijection $f: \mathbb{N} \to \mathbb{N}$:

We define the (possible infinite) number of "crosses" or "intersections" by the following:

For every pair $i,j$ with $i<j, $ define:

$$ \alpha_{ij}=\begin{cases} 0&\ \text{if} \ f(j) > f(i)\\[8pt] 1&\ \text{if} \ f(j) < f(i)\\[8pt] \end{cases} $$

Then the number of (possibly infinite) intersections is $\ s(f) = \displaystyle \sum_{i=1}^\infty \left( \sum_{j=i+1}^\infty\alpha_{ij} \right)$.

(s depends only on the bijection $f$).

Also, define a bijection eventually equal to the identity to be one in which $ \exists N$ such that $f(n) = n \quad \forall n \geq N$.

My conjecture is that a bijection $f: \mathbb{N} \to \mathbb{N}$ is eventually equal to the identity $ \iff s$ is finite, but I don't know how to prove this formally.

Note that my conjecture would be false with bijections $f: \mathbb{Z} \to \mathbb{Z}$, for example:

The pigeonhole principle came to mind, but I'm not sure if it's useful or necessary for a proof.

Solution 1:

The following is more precise details of the sketch in my comment.

Suppose $s$ is finite. Then this means that eventually there are no crosses. In other words there is some $n_0$ such that $f$ is increasing on $[n_0,\infty)$. Now let $n_1>n_0$ be such that for all $y\leq n_0$ there is some $x\leq n_1$ such that $f(x)=y$. We claim that $f$ is the identity after $n_1$.

So fix $x>n_1$ and suppose $f(x)\neq x$.

Case 1. $f(x)<x$. Then there must be some $y<x$ such that $f(y)\geq x$, since otherwise the interval $[1,x]$ is mapped to $[1,x-1]$. Note that $y>n_0$ since $f$ maps $[1,n_0]$ into $[1,n_1]$ and $n_1<x\leq f(y)$. So $n_0<y<x$ and $f(x)<x\leq f(y)$. This contradicts the assumption that $f$ is increasing after $n_0$.

Case 2. $f(x)>x$. By similar reasoning, this forces $x>n_0$ and there must be $y>x$ such that $f(y)\leq x$. Contradiction.

Solution 2:

In my question, I should have drawn arrows to represent $f$, and not just straight lines without arrows. I intended $f$ to be arrows going from the top row to the bottom row.

$ \implies$ is easy, so we focus on $ \impliedby$: suppose s, the number of crosses, is finite. Then the number of integers in the top row involved in a crossing is finite (reasoning of this is left up to the reader). Because $f$ is a bijection, the number of integers in the bottom row involved in a crossing is the same as the number of integers in the top row involved in a crossing, and is therefore also finite.

Let $M_1 = \max$ { $n: \text{ the arrow } ( n, f(n) )$ is involved in a crossing } $= \max $ { $n:f(n) < f(m)$ for some $m < n$ }, and let $N_1 = \max$ { $f(n):\text{ the arrow } ( n, f(n) )$ is involved in a crossing } $= \max $ { $n:f^{-1}(n) < f^{-1}(m)$ for some $m < n$ }.

Note first that it is not necessarily the case that every $m<M_1$ is involved in a crossing. But $M_1$ and $N_1$ are involved in crossings by definition, so we use this fact in our proof of the Lemma and $(1)$ below.

$\bbox[lightgrey]{\text{Lemma: } f(M_1) < N_1\ \text{ and } f^{-1}(N_1)<M_1.\ }$ Proof of the first half of the Lemma: Suppose $f(M_1) > N_1.\ $ Then $f(M_1)$ is by definition involved in a crossing and is $> N_1$, contradicting the maximality of $N_1.$ If $f(M_1) = N_1,\ $ then since the arrow $(M_1, N_1)\ $ is involved in a crossing, either $M_1$ or $N_1$ will not be maximal, contradicting one of their definitions. The proof of the second half of the Lemma is very similar.

$\bbox[yellow]{(1): \quad m \leq M_1 \implies f(m) \leq N_1; \quad n \leq N_1 \implies f^{-1}(n) \leq M_1}.$ Proof of the first half of $(1)$: We must have $m<M_1 \implies f(m) < N_1+1\ $ else if such an $m'<M_1$ exists (such that $f(m') \geq N_1+1),\ $ then by the Lemma the arrow $(m', f(m'))\ $ crosses the arrow $(M_1, f(M_1)),\ $ and $f(m')>N_1,\ $ contradicting the maximality of $N_1$. The proof of the second half of $(1)$ is very similar.

$\bbox[yellow]{(2): \quad f(M_1+1) = N_1+1}.\ \text{Proof: by (1), }f(M_1+1) > N_1.\ $ Also,$ \ f(M_1+1) \not> N_1+1\ $ because then $N_1+1$ would be dead. This proves the result of $(2)$.

By the same reasoning as in $(2),\ f(M_1+2) = N_1+2,\quad f(M_1+3) = N_1+3,\ $ and so on. This shows that:

$\bbox[yellow]{(3): \quad \forall k \in \mathbb{N},\quad f(M_1+k) = N_1 + k}$, noting that I do not count $0$ as a natural number. Finally, going back to $(1)$, we have:

$\bbox[yellow]{(4): \quad M_1 = N_1 }$, else if $M_1 \neq N_1$ we would have a bijection between $N_1$ and $M_1 \neq N_1$ integers, which isn't possible.

Putting $(3)$ and $(4)$ together $ \implies$

$f(M_1 +k) = M_1 + k \quad \forall k \in \mathbb{N},\ $ i.e. $f$ is equal to the identity $\forall n \geq M_1+1.$