nLab
monotone function

Monotone functions

Idea

A monotone function is a functor between preordered sets.

Explicit definitions

Let SS and TT be preordered sets, that is sets equipped with a reflexive and transitive binary relation \leq. (By convention, the same symbol is used for both sets, even technically it is not the same relation.)

Then a function ff from SS to TT is monotone (increasing), isotone, weakly increasing, or order-preserving if it preserves \leq:

xyf(x)f(y) x \leq y \;\Rightarrow\; f(x) \leq f(y)

for all x,yx, y in SS.

A strictly increasing function is a weakly increasing function that is also injective, at least if SS and TT are partially ordered. Between arbitrary preordered sets, however, it is probably better to accept as strictly increasing any weakly increasing function that is weakly injective in that xyx \leq y whenever f(x)=f(y)f(x) = f(y); such a function must be injective if SS is a partial order (since yxy \leq x will also follow) but not necessarily in general.

Mike Shulman: Is that really the right definition? I think of “strictly increasing” as meaning that x<yx \lt y implies f(x)<f(y)f(x) \lt f(y), which is equivalent to the above for linear orders but weaker for partial orders. But I don’t have much experience with strictly increasing functions between non-linear orders, so maybe that is the right definition for partial orders.

However, I don’t think it is the right definition for preorders; among other things, it’s not invariant under equivalence of categories. It seems to me that what you really want to say is that it is pseudomonic as a functor (whereas my weaker definition would become the statement that it is conservative as a functor.)

Toby: This is the definition in HAF (Section 3.17), which defines it for posets (and is a smart enough book that it wouldn't blindly extend a definition from a special case). Although I don't have a reference, I'm pretty sure that this also used in analysis and topology when thinking about convergence and nets, where they may be prosets. However, I think that you have a good point about preordered sets, so I've changed the wording above. (I'll also try to confirm how covergence theorists define ‘strictly increasing’ functions between directed prosets.)

It occurs to me that, in the absence of the axiom of choice, one ought to accept even anafunctors between prosets as morphisms, even though these may not be representable as strict functions at all. I'll save that for another day, however.

Mike Shulman: Of course, the definition you gave above isn’t the same as pseudomonic unless TT is a partial order; in general you want to say xyx\leq y whenever f(x)f(y)f(x) \cong f(y). The version with == is still not invariant under equivalence of TT.

I don’t know a whole lot about convergence and nets, but I don’t remember seeing strictly increasing functions used there; I look forward to seeing what you find. Does HAF use the poset version for any application that makes clear why this is a good definition? Of course, monomorphisms of posets may quite naturally something to be interested in, but the question is why they should be called “strictly increasing.”

A function ff is monotone decreasing, antitone, weakly decreasing, or order-reversing if it reverses \leq:

xyf(y)f(x) x \leq y \;\Rightarrow\; f(y) \leq f(x)

for all x,yx, y in SS.

A strictly decreasing function is a weakly decreasing function that is also (weakly) injective.

Sometimes the term ‘monotone’ or ‘isotone’ (but rarely both) is used for function from SS to itself such that

xf(x) x \leq f(x)

for all xx in SS.

Is there a widely accepted term for this? I've seen both of these, I think, but the other meaning seems to be more common for both. —Toby

High-level explanation

As a preordered set is the same thing as a category in which any two parallel morphisms are equal, so a monotone function is simply a functor between such categories. An antitone function is a contravariant functor. That ‘monotone’ may be used for both matches that ‘functor’ may be used for both covariant and contravariant functors.

Strictly increasing (and strictly decreasing) functions are particularly important between linearly ordered sets, where are the most natural kind of morphism. Between partially ordered sets in general (and between preordered sets using the stricter definition), the strictly increasing functions are simply the monomorphisms (if weakly increasing functions are taken as the morphisms). If we use the weaker definition between preordered sets, then the strictly increasing functions correspond to pseudomonic functors, which is an appropriate sort of higher monomorphism; this is one reason for preferring that definition.

The alternative sort of monotone function on a single proset SS is rather different; we mention it here largely because of the potential terminological confusion, but it might as well have its own article if we find a nice name for it. As a functor, it is a functor for which every object is an algebra; the condition is part of the requirements of a Moore closure (a monad on SS).

Revised on September 24, 2013 12:13:22 by Toby Bartels (98.23.150.36)