Given two enumerations $A:S \to \mathbb{N}$, $B:S \to \mathbb{N}$ on the same countably infinite set $S$, are there infinitely many elements $s \in S$ with $A(s) \geq B(s)$?
My feeling is that there must be, i.e. that it cannot be the case that all but a finite number of elements of S appear in B before A, but I can't come up with a proof to support this feeling.
Am I correct? If so, could I have a hint for a proof?
Answering the version in your 4th comment, Yes. Combining the inverse of B with A the question becomes: if $f:\mathbb N \to \mathbb N$ is a bijection, can there be only finitely many n with $f(n) \geq n$. To see not, suppose there is and let $M = max \{f(n) : f(n) \geq n \} $. Now look at the image of $\{1,2,...,M+1 \}$.