(Least) upper bounds for order-preserving maps

A map f:P\to Q between non-empty partially ordered sets is said to be order-preserving if x, y \in P, x\leq_P y entails f(x) \leq_Q f(y). The collection Mor(P,Q) of order-preserving maps f:P\to Q can be endowed with an ordering relation in a natural way by setting

f \leq g in Mor(P,Q) iff f(x) \leq g(x) for all x\in P.

When considering any partially ordered set, or poset, for short, a natural question arising is that of the existence of (least) upper bounds, and dually, (greatest) lower bounds. A subset S of a poset (P,\leq) is said to have an upper bound if there exists z \in P such that z \geq s for all s\in S. The collection of upper bounds of S is denoted by S^u.

The basic question of this post is: When do f, g \in Mor(P,Q) have a (least) upper bound?

When you start tinkering with Mor(P,Q) and its elements, you notice that the existence of bounds in the codomain Q is more important than in the domain P. This can be illustrated by two examples:

(1) If f(x) and g(x) have no upper bound in Q for some x \in P, then f,g are not bounded in Mor(P,Q).

(2) If Q is a lattice, then so is Mor(P,Q).

As for the proof of statement (2), let us denote the supremum of a,b \in Q by a\vee b and the infimum by a\wedge b. Let f,g \in Mor(P, Q). Then it is easy to verify that the map h:P \to Q given by

h(x) = f(x) \vee g(x) for all x \in P

is the supremum of f,g; the infimum is constructed in a similar manner.

Let’s have a look at the converse statements of (1) and (2).

The converse of (1) would say that if \{f(x), g(x)\}^u \neq \emptyset for all x\in P, then f, g have an upper bound in Mor(P,Q). We can construct a finite counterexample to this statement by letting V = \{b, 0, 1\} ordered by b < 0, b < 1 and Q = \{0,1\}^2 ordered by (0, j) < (1,k) for j,k \in \{0,1\}. So if we draw V we get a v-shaped figure, and Q looks like a butterfly.

Let f,g: V\to Q be the maps given by f(b) = (0,0) and g(b) = (0,1) and f(0) = g(0) = (1,0) and f(1) = g(1) = (1,1). Then \{f(x), g(x)\}^u \neq \emptyset for all x\in V, but it is easily seen that there is no order-preserving map that is an upper bound of f, g.

The converse of (2), on the other hand, is true. In order to tackle this, we need the concept of a retract. We say that a poset S is a retract of a poset T if there are order-preserving maps i:S\to T and r:T \to S such that r\circ i: S\to S is the identity map.

Lemma 1. Q is a retract of Mor(P,Q).
Proof. Let i:Q \to Mor(P,Q) be defined by i:q \mapsto c_q where c_q:P\to Q is the constant map that maps everything from P to q\in Q. For defining r:Mor(P,Q) \to Q, fix a_0 \in P and for f\in Mor(P,Q) let r(f) = f(a_0). A routine check shows that i, r are order-preserving and r\circ i = \textrm{id}_Q.

Lemma 2. Any retract of a lattice is a lattice.
Proof. Let L be a lattice and P a poset and i:P\to L and r:L \to P such that r\circ i: P\to P is the identity map. For a, b \in P it suffices to check that r(i(a) \vee i(b)) is the least upper bound of a,b. It clearly is an upper bound. Suppose v \in \{a,b\}^u. Then i(v) \in \{i(a), i(b)\}^u since i is order-preserving, therefore i(a)\vee i(b) \leq i(u). Using the fact that r is order-preserving we get that r(i(a) \vee i(b)) \leq r(i(u)) = u, so r(i(a) \vee i(b)) is the least upper bound.

In summary, we get that Mor(P,Q) is a lattice if and only if Q is a lattice. (Note that this equivalence only works for P \neq \emptyset).

We gave partial answers, but are still lacking a full one, to the main question of this post: When do f, g \in Mor(P,Q) have a (least) upper bound?

About dominiczypen

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Order theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s