12
$\begingroup$

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.

  • 1
    First you should look at the definition of $\mathcal{U}$-equivalence.2011-04-23
  • 1
    I think that for Ramsey ultrafilters you can use the coloring $\{a,b; a. 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.2011-04-24
  • 0
    @Jacob Fox: It is in general not true.2011-04-24
  • 0
    @user6312: could you please elaborate?2011-04-24
  • 0
    @Theo Buehler: Done.2011-04-24
  • 0
    @Jacob: The answer below doesn't refute your conjecture, since it refers to *strongly* increasing functions.2011-04-25
  • 0
    What do you mean by weakly and strongly increasing? Is it non-decreasing and strinctly increaxsing? Isn't condition 1) equivalent to $\mathcal U$ being Ramsey? (See the part I copied in http://math.stackexchange.com/questions/34769/problem-on-ultrafilters from the book Argyros-Todorcevic.)2011-04-25
  • 0
    Yes, condition (1) is equivalent to $\mathcal{U}$ being Ramsey. By weakly increasing I mean that if $i then $f(i)\leq f(j)$.2011-04-25
  • 0
    @Jacob: I still think that my comment (the second one bellow the post) provides the proof for Ramsey ultrafilters. Am I missing somethings?2011-04-25
  • 0
    No no, it's right. If we know that (1) is equivalent to Ramsey then ok, but i proved only that Ramsey implies (1). Now I'd like to prove that (1) imples (2) without assuming to know that (1) is equivalent to Ramsey.2011-04-25
  • 1
    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.2011-04-25
  • 0
    @Martin: So I Have $A\in\mathcal{U}$ such that $f|_A$ is increasing. So I want to extend $f|_A$ to $\mathbb{N}$ keeping it increasing, why can I do this?2011-04-25
  • 0
    @Jacob: For $b\notin A$, define $f(b)=\max\{f(a)\mid a\in A,a.2011-04-25
  • 0
    @Jacob: Why do you write "ok, it's false"? Do you have a counterexample?2011-04-25
  • 0
    @Joriki: the answer 1 of user 6312 gives the counterexample, am I wrong?2011-04-25
  • 1
    @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"?2011-04-26
  • 0
    You're right. In another question someone made me the same question, there I clarified and so I forgot to clarify also here. By increasing I mean strictily increasing. However from now on I will use the terms "strictly" and "weakly" so there won't be any doubts, and I will define it in every question.2011-04-26
  • 0
    @joriki: I added a more elaborate example to deal with your question about non-decreasing functions.2011-04-26

1 Answers 1

10

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. 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), there is not enough room below $g(a)$ for the $g(i)$ with $i.

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, then $f(s)>f(t)$.

  • 0
    Very good! This explains why I was stumped trying to prove it for the past few hours!2011-04-24
  • 4
    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.2011-04-24
  • 1
    In particular, take the principal ultrafilter rooted at $2$, and choose $f(2) = 1$. However, the relaxed claim is trivially true for principal ultrafilters.2011-04-24