Injective function and ultrafilters

Solution 1:

This answer has two parts. The first part deals with (strictly) increasing functions. This seemed to be (and turned out to be) what the OP's question was about. The second and slightly more subtle part deals with non-decreasing functions.

The problem refers to $\mathbb{U}$-equivalence of two functions from $\mathbb{N}$ to $\mathbb{N}$. Unfortunately, this notion is not defined in the problem. I will assume that it is the ordinary notion that is used, for example, in defining the ultrapower. Specifically, let $I$ and $A$ be sets, with $I$ non-empty, and let $\mathbb{U}$ be an ultrafilter on $I$. Let $f$ and $g$ be functions from $I$ to $A$. We will say that $f$ and $g$ are $\mathbb{U}$-equivalent if the set of $i$ such that $f(i)=g(i)$ belongs to $\mathbb{U}$ (more informally, $f$ and $g$ agree "almost everywhere modulo $\mathbb{U}$").

Let $\mathbb{N}$ denote the positive integers, and let $S$ be the set of positive integers of the form $4k+2$. Let $\mathbb{U}$ be any ultrafilter that has $S$ as an element. There are many such ultrafilters, countably many principal ones, and even more non-principal ones. We will show that there is a bijective function $f$ from $\mathbb{N}$ to $\mathbb{N}$ which is not $\mathbb{U}$-equivalent to any increasing function.

If $n$ is an odd positive integer, let $f(n)=2n$. If $n$ is congruent to $2$ modulo $4$, let $f(n)=n/2$. Finally, if $n$ is a positive integer divisible by $4$, let $f(n)=n$. It is clear that $f$ is a bijection, all it does is interchange, for example, $1$ and $2$, $3$ and $6$, and so on. We will show that there cannot be an increasing function $g$ such that $f$ is $\mathbb{U}$-equivalent to $g$.

For suppose that $g$ is $\mathbb{U}$-equivalent to $f$. Then there is a number $s$ of the form $4k+2$ such that $g(s)=f(s)=s/2<s$. This is impossible: any (strictly) increasing function $g$ from $\mathbb{N}$ to $\mathbb{N}$ has the property that $g(n) \ge n$ for all $n$. This is obvious: if $g(a)<a$, there is not enough room below $g(a)$ for the $g(i)$ with $i<a$.

Addendum There has been some back and forth about the meaning of increasing function, with joriki in particular interpreting the term as meaning what, in calculus courses, we often call non-decreasing (and what some people call weakly increasing). After a while, the OP clarified that he meant strictly increasing. But this leaves a possibly interesting question: If $\mathbb{U}$ is a non-principal ultrafilter on $\mathbb{N}$, is it necessarily true that every injective function from $\mathbb{N}$ to $\mathbb{N}$ is $\mathbb{U}$-equivalent to a non-decreasing function?

I will show that the answer is no. The counterexample is a little more complicated than the primitive counterexamples that I produced in response to the OP.

Definition: A non-principal ultrafilter $\mathbb{U}$ on $\mathbb{N}$ is a $q$-point if for every partition of $\mathbb{N}$ as a union of finite sets $A_n$, there is an element $X$ of $\mathbb{U}$ such that $X$ meets each $A_n$ in at most one point.

Alternately, such an ultrafilter is called rare. And they are rare! It is not hard to show in ZFC that there are (a lot of) ultrafilters that are not $q$-points. It is consistent with ZFC that there are no $q$-points.

From now on, suppose that the non-principal ultrafilter $\mathbb{U}$ is not a $q$-point. We show that in that "normal" case there is a function $f$ which is not $\mathbb{U}$-equivalent to a non-decreasing function.

Since $\mathbb{U}$ is not a $q$-point, there is a partition of $\mathbb{N}$ into finite sets $A_n$ such that there is no $X$ in the ultrafilter that meets each $A_n$ in at most one point. One can think of this partition as a witness that the ultrafilter is not rare.

Let $A$ be a "typical" $A_n$ (I am doing this to avoid a multiplicity of subscripts). List the elements of $A$ in increasing order, as $a_0, a_1, \dots,a_k$. Define the function $f$ on $A$ by $f(a_i)=a_{k-i}$. Thus $f$ reverses order on $A$. Do this for all the $A_n$. We now have an injective function $f$ from $\mathbb{N}$ to $\mathbb{N}$. We will show that $f$ cannot be $\mathbb{U}$-equivalent to a non-decreasing function.

Suppose to the contrary that $g$ is such a function, and the element $X$ of the ultrafilter is the set on which $f$ and $g$ agree. For any $A_n$, we show that $X \cap A_n$ has at most one element. This is obvious: if $s$ and $t$ are in $A_n$, and $s<t$, then $f(s)>f(t)$.