"Conjugate" of a monotone unbounded function $f : \mathbb N \to \mathbb N$

Question

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.

Answer 1

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.

Answer 2

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*}$$

Answer 3

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<x' \Leftrightarrow y<y')$$ 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$.