Exercise 55 - Chapter 1

David Lambert

Recall the notion of upper set from Example 1.45, and let \((P,\leq)\) be a preorder.

1. Show that the set \(\uparrow p:=\{p'\in P\mid p\leq p'\}\) is an upper set, for any \(p\in P\).

2. Show that this construction defines a monotone map \(\uparrow:P^\mathrm{op}\to\mathcal{U}P\).

3. Draw a picture of the map \(\uparrow\) in the case where \(P\) is the preorder \((b\geq a\leq c)\) from Exercise 1.48.

Example 1.45:

Given a preorder \((P,\le)\), an upper set in \(P\) is a subset \(U\) of \(P\) satisfying the condition that if \(p \in U\) and \(p \le q\), then \(q \in U\). ``If \(p\) is an element then so is anything bigger.'' Write \(\mathcal U(P)\) for the set of upper sets in \(P\). We can give the set \(\mathcal{U}\) an order by letting \(U \le V\) if \(U\) is contained in \(V\).

For example, if \((\mathbb{B},\leq)\) is the booleans (Example 1.33), then its preorder of uppersets \(\mathcal U\mathbb{B}\) is \[\boxed{\begin{matrix}\lbrace\mathrm{false},\mathrm{true}\rbrace\\\uparrow\\\lbrace\mathrm{true}\rbrace\\\uparrow\\\varnothing\end{matrix}}\]

Just \(\{\mathrm{false}\}\) by itself is not an upper set, because \(\mathrm{false}\leq\mathrm{true}\).

David Lambert

1. Let \(x\in\uparrow p\), \(y\in P\), and \(x\leq y\). By definition of \(\uparrow p\), \(p\leq x\). By transitivity, this implies that \(p\leq y\). So, \(y\in\uparrow p\).
2. \(P^\mathrm{op}\) has the same elements as \(P\), so \(\uparrow\) maps \(P^\mathrm{op}\) to \(\mathcal{U}(P)\). Let \(p,q\in P\) with \(q\leq_P p\). By definition of \(^\mathrm{op}\), \(p\leq_{P^\mathrm{op}}q\). For every \(x\in\uparrow q\), \(q\leq x\). By transitivity, \(p\leq x\). So, \(\uparrow q\subseteq\uparrow p\). Thus, \(\uparrow q\leq\uparrow p\). Conclude that \(\uparrow:P^\mathrm{op}\to\mathcal{U}(P)\) is a monotone map.
3. \(\uparrow(a)=\{a,b,c\}\), \(\uparrow(b)=\{b\}\), \(\uparrow(c)=\{c\}\), \(\varnothing\leq\uparrow(b)\leq\uparrow(a)\), and \(\varnothing\leq\uparrow(c)\leq\uparrow(a)\).