4
$\begingroup$

Fix $\mathbb N = \{0,1,2,\ldots\}$. I remember reading (a few years back) about a way to define a "dual" or "conjugate" of an unbounded monotone function $f : \mathbb N \to \mathbb N$. But I do not remember the source, nor can I reproduce any nice properties or theorems satisfactorily. The definition I am thinking of goes like this. For an unbounded monotone $f$, define $f^\star$ by:

$$ f^\star (y) = \min \{ x \in \mathbb N \,:\, f(x) \geq y \} \ \ \ \ \ \ \ \ \ \text{(proposed)} $$

It's easy to show that $f^\star$ is also unbounded monotone. I think this definition is more or less correct, but I might very well be wrong on the precise details.

My questions are:

  1. Has this or a similar object been studied before systematically? What is the standard terminology for it?
  2. I remember that the $\star$ operation is involutive: $(f^\star)^\star = f$, and I am looking for a proof or a counter-example. (Note that this property will also make this operation automatically bijective.) I have a weak argument showing it's true, but it's not at all convincing. \\ EDIT: For the above definition, $(f^\star)^\star \neq f$ in general. But it turns out the definition can be tweaked if we want this property to hold. See Arturo's answer for details.

Finally, if this operation makes sense, I feel it should actually be a special case of a more general construction for functions defined on, for instance, lattices. As a bonus question, are any such generalizations known and is there any reference that discusses them? EDIT: Qiaochu's answer gives such a generalization.

  • 2
    Say $f(n) = 10^n$; then your definition is $f^*(m) = \lceil \log_{10}(m)\rceil$. The first few values of $f^*$ are $1,1,1,1,1,1,1,1,1,1,2,2,\ldots$; so $f^*(2)=1$. But $(f^*)^*(1) = \min\{x\mid f^*(x)\geq 1\} = 1$. So $(f^*)^*\neq f$.2011-09-12
  • 0
    @Arturo I was staring at your counterexample for quite some time, and I found the fix that will give us $(f^\ast)^\ast=f$. Make the inequality sign in $f^\ast$ definition strict, and things work. I have (what looks like) a proof, I am writing it up informally to see if there's any bug. Now I would like some advice. I want to edit the question, but I also do not want to invalidate the answers below. What's the best thing I can do at this stage? I still would like to have references, so Question (1.) is still relevant, though Question (2.) may not be relevant. Sorry if I am bothering you.2011-09-12
  • 0
    Srivatsan: First, the justification I wrote above does not actually make sense, though the example still works. What it should be is that $(f^*)^*(2) = \min\{m\mid f^*(m)\geq 2\}=11\neq f(2)$.2011-09-12
  • 0
    Second: to avoid invalidating the answers, why not post an addendum, indicating this is done after the other answers were posted?2011-09-12
  • 0
    By the way, I think that with the definition as you have in the post you get that $(f^*)^*(m) = f(m-1)+1$ for $m\geq 1$, by using an argument similar to the one I used to show the new definition works.2011-09-13
  • 0
    @Arturo Oh, interesting. Nice observation. In retrospect, that makes sense because $y > f(x)$ is the same as saying $y-1 \geq f(x)$.2011-09-13

3 Answers 3

3

This is actually a special case of an adjoint functor. (Recall that posets are categories in which $a \le b$ means there is a single arrow $a \to b$, and that functors between such posets are order-preserving functions.) This is discussed in my blog post on the adjoint functor theorem for posets.

For the special case of posets, adjoint functors are also known as Galois connections, the motivating example being the Galois connection between subextensions of a finite Galois extension and subgroups of a Galois group.

3

With the original definition of $f^*$, the function $f(n)=10^n$ is a counterexample. Note that $$(f^*)^*(2) = \min\{k\in\mathbb{N}\mid f^*(k)\geq 2\} = 11,$$ since $f^*(1)=\cdots=f^*(10)=1$, but $f^*(11)=2$ (since $2$ is the smallest number such that $f(k)\geq 11$). But $f(2)=100\neq 11=(f^*)^*(2)$.


As suggested by Srivatsan in the comments, let us tweak the definition of $f^*$ to: $$f^*(n) = \min\{m\in\mathbb{N}\mid f(m)\gt n\}.$$

I claim that under this definition, $(f^*)^*=f$.

Lemma. $f^*(s)\gt t$ if and only if $f(t)\leq s$.

Proof. Suppose $f^*(s)\gt t$. Then $\min\{ m\in \mathbb{N}\mid f(m)\gt s\}\gt t$. Therefore, $t\notin\{m\in\mathbb{N}\mid f(m)\gt s\}$, so $f(t)\leq s$.

Conversely, assume that $f(t)\leq s$. Because $f$ is monotone increasing, if $k\leq t$, then $f(k)\leq s$. Therefore, $f^*(s)=\min\{m\in\mathbb{N}\mid f(m)\gt s\}\gt t$. $\Box$

Proposition. With the modified definition, $(f^*)^* = f$.

Proof. Let $t\in\mathbb{N}$. We have: $$\begin{align*} (f^*)^*(t) &= \min\bigl\{ s\in\mathbb{N}\mid f^*(s)\gt t\bigr\}\\ &= \min\bigl\{ s\in\mathbb{N}\mid f(t)\leq s\}\\ &= f(t).\quad\Box \end{align*}$$

1

It looks morally like a kind of inverse to me.

Start with any binary relation $R\subseteq \mathbb N\times\mathbb N$ that preserves order in the sense that $$x R y \land x' R y' \Rightarrow (x and such that $R$ is an infinite set.

Then we can derive $f$ from $R$ setting $$f(x) = \min \{ y \mid x' R y \land x' \ge x \}$$

$f^*$ is then the function that would be derived in the same way from the inverse of $R$. Duality would follow by showing under appropriate conditions we can recover $R$ from $f$.

  • 0
    Duality shouldn't be expected, since in general there are arbitrarily long chains of adjoint functors: see http://mathoverflow.net/questions/9849/iterated-adjoint-functors .2011-09-12
  • 0
    Then what I'm constructing is probably not an adjoint. It would still look sufficiently close to Srivatsan's vague description that it could be what he remembers, I think.2011-09-12
  • 0
    @Qiaochu -- also note that I'm working specifically in $\mathbb N$, here not in a general poset.2011-09-12