"Conjugado" de una monótona y acotada función de $f : \mathbb N \to \mathbb N$

Question

Fix $\mathbb N = \{0,1,2,\ldots\}$. Recuerdo haber leído (un par de años atrás) acerca de una manera de definir un "doble" o "conjugado" de una desenfrenada monotonía de la función $f : \mathbb N \to \mathbb N$. Pero no recuerdo la fuente, ni puedo reproducir cualquier agradable propiedades o teoremas de manera satisfactoria. La definición que yo me refiero es así. Para una desenfrenada monotono $f$, definir $f^\star$ por:

$$ f^\estrella (y) = \min \{ x \in \mathbb N \,:\, f(x) \geq y \} \ \ \ \ \ \ \ \ \ \texto{(propuesto)} $$

Es fácil demostrar que los $f^\star$ también es monótona y acotada. Creo que esta definición es más o menos correcto, pero podría muy bien estar equivocado en los detalles precisos.

Mis preguntas son:

1. Tiene este o un objeto similar sido estudiado antes sistemáticamente? ¿Cuál es la terminología estándar?
2. Recuerdo que el $\star$ operación es involutiva: $(f^\star)^\star = f$, y estoy en busca de una prueba o un contraejemplo. (Tenga en cuenta que esta propiedad también hacer esta operación de forma automática bijective.) Tengo un débil argumento que muestra de ello es cierto, pero no es en absoluto convincente. \\ EDIT: Para la definición de arriba, $(f^\star)^\star \neq f$ en general. Pero resulta que la definición puede ser ajustado si queremos que esta propiedad para contener. Véase Arturo respuesta para más detalles.

Por último, si esta operación tiene sentido, creo que debería ser en realidad un caso especial de una forma más general de construcción para las funciones definidas en, por ejemplo, las rejillas. Como un bono de la pregunta, son tales generalizaciones se conoce y se hace ninguna referencia que les discute? EDIT: Qiaochu la respuesta da una generalización.

Answer 1

Con la definición original de $f^*$, la función de $f(n)=10^n$ es un contraejemplo. Tenga en cuenta que $$(f^*)^*(2) = \min\{k\in\mathbb{N}\mid f^*(k)\geq 2\} = 11,$$ desde $f^*(1)=\cdots=f^*(10)=1$, pero $f^*(11)=2$ (desde $2$ es el menor número tal que $f(k)\geq 11$). Pero $f(2)=100\neq 11=(f^*)^*(2)$.

---

Como sugiere Srivatsan en los comentarios, nos deja modificar la definición de $f^*$ a: $$f^*(n) = \min\{m\in\mathbb{N}\mid f(m)\gt n\}.$$

Yo reclamo que en virtud de esta definición, $(f^*)^*=f$.

Lema. $f^*(s)\gt t$ si y sólo si $f(t)\leq s$.

Prueba. Supongamos $f^*(s)\gt t$. A continuación,$\min\{ m\in \mathbb{N}\mid f(m)\gt s\}\gt t$. Por lo tanto, $t\notin\{m\in\mathbb{N}\mid f(m)\gt s\}$, lo $f(t)\leq s$.

Por el contrario, asumir que $f(t)\leq s$. Debido a $f$ es monótona creciente, si $k\leq t$,$f(k)\leq s$. Por lo tanto, $f^*(s)=\min\{m\in\mathbb{N}\mid f(m)\gt s\}\gt t$. $\Box$

La proposición. Con la modificación de la definición, $(f^*)^* = f$.

Prueba. Deje $t\in\mathbb{N}$. Tenemos: $$\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 2

Esto es en realidad un caso especial de un functor adjunto. (Recordemos que el de posets son las categorías en las que $a \le b$ significa que no hay una sola flecha $a \to b$, y que functors entre el parque natural posets son el fin de la preservación de las funciones.) Esto se discute en mi blog en el functor adjunto teorema de posets.

Para el caso especial de posets, adjunto functors son también conocidas como conexiones de Galois, la motivación por ejemplo, la conexión de Galois entre subextensions de un finita de Galois de la extensión y de subgrupos de un grupo de Galois.

Answer 3

Parece moralmente como una especie de inversa para mí.

Comience con cualquier relación binaria $R\subseteq \mathbb N\times\mathbb N$ que conserva el orden en el sentido de que $$x R y \land x' R y' \Rightarrow (x<x' \Leftrightarrow y<y')$$ y de tal manera que $R$ es un conjunto infinito.

Entonces podemos derivar $f$ $R$ $$f(x) = \min \{ y \mid x' R y \land x' \ge x \}$$

$f^*$ es la función que se derive de la misma manera a partir de la inversa de $R$. La dualidad seguiría mostrando en condiciones adecuadas, podemos recuperarnos $R$$f$.