Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An exercise left by my teacher let me think that the following statement is true:

Let $\mathcal{U}$ be an ultrafilter on $\mathbb{N}$. Then every injective function $g:\mathbb{N}\rightarrow\mathbb{N}$ is $\mathcal{U}$-equivalent to an increasing function.

Is it true? If yes, how can I prove it?

EDIT: ok, it's false. I wanted to prove that (1) implies (2)

1)Every $f:\mathbb{N}\rightarrow\mathbb{N}$ is $\mathcal{U}$-eq. to a constant or an injective function.

2)Every $f:\mathbb{N}\rightarrow\mathbb{N}$ is $\mathcal{U}$-eq. to a weakly increasing function.

I wanted to prove this by proving that every injective function is equivalent to an increasing one. If this is false how I can prove that (1) implies (2)?

I have to prove that every injective function is equivalent to a weakly increasing one.

share|improve this question
First you should look at the definition of $\mathcal{U}$-equivalence. –  David Kohler Apr 23 '11 at 23:14
I think that for Ramsey ultrafilters you can use the coloring $\{a,b; a<b, f(a)<f(b)\}$. There is a homogeneous set $A$ from the filter, which means $f|_A$ is monotone. It cannot be decreasing, since this would give an infinite deecreasing sequence of integers. I do not know, whether the result is true for arbitrary filters, though. –  Martin Sleziak Apr 24 '11 at 5:30
@Jacob Fox: It is in general not true. –  André Nicolas Apr 24 '11 at 11:38
That (1) implies Ramsey is easy. For any $b$ in the range of $f$, construct the set $f^{-1}(b)$. That partitions $\mathbb{N}$. To say that $f$ is not almost everywhere constant says that the $f^{-1}(b)$ are not in the ultrafilter. To say that $f$ is equivalent to a injective $g$ says basically that some set which meets each $f^{-1}(b)$ in $1$ point belongs to the ultrafilter. –  André Nicolas Apr 25 '11 at 20:22
@Jacob: I can't tell because you replied neither to my comment under that answer asking you to clarify how you're using "increasing", nor to Yuval's comment. In the meantime you've edited the answer using both the terms "increasing" and "weakly increasing", and in a comment you've defined "weakly increasing" as the concept that "increasing" usually refers to. (BTW, such clarifications should preferably be made in the question so people don't have to rummage through the comments to understand the question.) Are we to conclude that by "increasing" you mean "strictly increasing"? –  joriki Apr 26 '11 at 4:40
show 13 more comments

1 Answer

up vote 10 down vote accepted

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

share|improve this answer
Very good! This explains why I was stumped trying to prove it for the past few hours! –  Asaf Karagila Apr 24 '11 at 12:29
I didn't understand "increasing" in the question to mean "strictly increasing". I was under the impression that there were counterexamples for "strictly increasing" and therefore interpreted the question to literally mean what it says, just "increasing". @Jacob: Please clarify which of the two you meant. –  joriki Apr 24 '11 at 12:34
In particular, take the principal ultrafilter rooted at $2$, and choose $f(2) = 1$. However, the relaxed claim is trivially true for principal ultrafilters. –  Yuval Filmus Apr 24 '11 at 21:08
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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