What's the difference between inflationary and monotonic functions?

Every now and then, I cave in and look at the Reddit comments on my blog posts. Recently, someone wanted to know the difference between “inflationary” and “monotonic” functions. I’m glad you asked!

• A function $f$ is inflationary (or an inflation, or a few other synonyms) if, for all $x$, $f(x) \geq x$ according to a given order. If $f$ is inflationary, $f(x)$ will always be at least as “big” as $x$, according to the order.
• A function $g$ is monotonic (or monotone, or a few other synonyms) if $x \leq y$ implies that $g(x) \leq g(y)$. Monotonicity has to do with preservation of an order: if $x$ and $y$ are ordered in a particular way, then $g(x)$ and $g(y)$ will be, too.

There is precedent for the way I’m using “inflationary” here, but the property is also called “progressive” or “extensive”. Confusingly, some authors also use “increasing” to mean inflationary, while others use “increasing” to mean monotonically increasing. For this and other reasons, perhaps it’s better to avoid the word “increasing” entirely.

Not every monotonic function is inflationary. For instance, the function $\textrm{half}$ over positive reals is monotonic, but not inflationary: $x \leq y$ implies that $\textrm{half}(x) \leq \textrm{half}(y)$, but $\textrm{half}(x) \not\geq x$. (Thanks to Carlos Baquero for pointing this out to me a while ago.)

More surprisingly, not every inflationary function is monotonic! Here’s an example: let $M = \lbrace 0, 1, 2 \rbrace$, and let $h$ be a function from the power set of $M$ to the power set of $M$. Suppose $h$ is defined as follows: $h(X) = X$ for $X = M$, and $h(X) = X \cup \lbrace \left\| X \right\| \rbrace$ otherwise.

Let’s spell out all the possibilities for $h$:

$$\begin{array}{ll} h(\lbrace\rbrace) &= \lbrace 0 \rbrace \cr h(\lbrace 0 \rbrace) &= \lbrace 0, 1 \rbrace \cr h(\lbrace 1 \rbrace) &= \lbrace 1 \rbrace \cr h(\lbrace 2 \rbrace) &= \lbrace 1, 2 \rbrace \cr h(\lbrace 0, 1 \rbrace) &= \lbrace 0, 1, 2 \rbrace \cr h(\lbrace 0, 2 \rbrace) &= \lbrace 0, 2 \rbrace \cr h(\lbrace 1, 2 \rbrace) &= \lbrace 1, 2 \rbrace \cr h(\lbrace 0, 1, 2 \rbrace) &= \lbrace 0, 1, 2 \rbrace \end{array}$$

So, assuming that $\leq$ is the usual $\subseteq$ ordering on sets, $\lbrace 0 \rbrace \leq \lbrace 0, 2 \rbrace$, but $h(\lbrace 0 \rbrace) \not\leq h(\lbrace 0, 2 \rbrace)$! (I found this strange little function in an exercise in Finite Model Theory by Ebbinghaus and Flum while searching for “inflationary but not monotone”, saving me from having to try to construct one myself.)

Update (September 1, 2015): Well, I feel sheepish. rntz pointed out a much simpler function that is inflationary but not monotonic: absolute value over the integers! $\textrm{abs}(x) \geq x$, but, for example, $-3 \leq 1$ and $\textrm{abs}(-3) \not\leq \textrm{abs}(1)$. That didn’t occur to me at all! (I guess I don’t have occasion to think about negative numbers very often.)

We didn’t say anything about the domain or codomain of $f$ or $g$ above. For $f$, we have to suppose that $x$ comes from an ordered set $A$ and that $f : A \rightarrow A$. For $g$, though, things could get more interesting: suppose we have $g : A \rightarrow B$, where $A$ and $B$ can be different. Now we’re dealing with two order relations, say, $\leq_A$ on $A$ and $\leq_B$ on $B$. Then, monotonicity of $g$ would mean that if $x \leq_A y$, then $g(x) \leq_B g(y)$! We get preservation of order even though we’re dealing with a different order relation. Apparently, that sort of thing comes up a lot in measure theory.

Finally, when I speak of monotonic data structures, I mean data structures that never shrink over time. Formally, that means there needs to be an order $\leq$ on all the states that the data structure can take on, and that, if the states it takes on over time are $s_0, s_1, s_2, \dots$, then $s_0 \leq s_1 \leq s_2 \dots$. Immutable data structures, and data structures that change once from empty to full, are special cases of monotonic data structures.