Options

Exercise 55 - Chapter 1

edited August 13 in Exercises

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

Comments

  • 1.
    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)\).
    Comment Source: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)\\).
Sign In or Register to comment.