14
$\begingroup$

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

enter image description here

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:

enter image description here

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

$\endgroup$
8
  • 4
    $\begingroup$ Side note: that's a poor use of the word "constant". Constant means that the function takes the same value regardless of its argument. The function $f(n)=3$ is constant. In the same spirit, the function, $f(n)=n+1$ for $n<10$ and $f(n)=3$ for $n≥10$ is "eventually constant". Better to say, e.g., "eventually equal to the identity". $\endgroup$ – lulu Oct 28 '20 at 11:42
  • $\begingroup$ Good point, lulu. My mistake $\endgroup$ – Adam Rubinson Oct 28 '20 at 11:43
  • $\begingroup$ In the spirit of your question: You might be interested in the notion of "permutations" of an infinite set. People mean two different things by that term, hence my use of quotes. The most natural interpretation is to say it means bijections from the set to itself. However, those turn out to be hard to study...it is often useful to consider instead bijections of the form you want. That is, bijections which fix every element except for a finite subset. To be sure, these are different definitions. There are more permutations of the first type than there are of the second type. $\endgroup$ – lulu Oct 28 '20 at 11:47
  • 1
    $\begingroup$ @lulu, I think those functions (in your first comment) have an infinite number of “crosses”, so they don’t work. $\endgroup$ – Adam Rubinson Oct 28 '20 at 11:54
  • $\begingroup$ Sketch: Find $n_0$ such that there are no more crosses after $n_0$. Find $n_1$ such that every number up to $n_0$ is in the image of $\{1,\ldots,n_1\}$. Then argue that $f$ preserves $[1,n_1]$ and $[n_1,\infty)$ setwise (otherwise there would be a cross after $n_0$). Now view $f$ on $[n_1,\infty)$ as it's own permutation with no crosses. This forces $f$ to be the identity on $[n_1,\infty)$. $\endgroup$ – halrankard2 Oct 28 '20 at 12:00
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$ }.

enter image description here

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.$

$\endgroup$
3
  • $\begingroup$ No one likes my proof? Is it hard to parse? Is it wrong? Is the highlighting annoying? Well, in any case, I like my proof. Sorry, my ego needed to be stroked a little bit after spending so much time on it... $\endgroup$ – Adam Rubinson Oct 28 '20 at 23:53
  • $\begingroup$ Your proof is actually interesting $\endgroup$ – user815114 Oct 29 '20 at 5:06
  • $\begingroup$ I'm sure there are shorter proofs, but this seems fine to me. $\endgroup$ – Adam Rubinson Jan 27 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.