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 \(\leq\). 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)\) for a given order \(\leq\). Monotonicity has to do with preservation of an order: if \(g\) is monotonic and if \(x\) and \(y\) are ordered in a particular way, then \(g(x)\) and \(g(y)\) will be ordered in that way, 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 example out to me a while ago.) To be more precise, not every function that is monotonic with respect to a given order is also inflationary according to that order.

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}\(\)

We can see that \(h\) is inflationary. But it is not monotonic: letting \(\leq\) be 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 in my own work, I mean data structures that never shrink over time, and for which the order of updates is not observable. Formally, “never shrink over time” 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 that. The “order of updates is not observable” property could probably be satisfied in various ways; IVars and LVars accomplish it with reads that block.