#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Exercise 55 - Chapter 1

edited August 2018

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}$$.

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