1

I'm having trouble making sense of a definition from Seven Sketches in Compositionality.

Exercise 1.66. Let (P, ≤) be a preorder, and recall the notion of opposite preorder from Example 1.58.

  1. Show that the set $\uparrow p := \{p' \in P | p ≤ p'\}$ is an upper set, for any p ∈ P.
  2. Show that this construction defines a monotone map $\uparrow: P_{op} \rightarrow U(P)$

...

In (1), they're defining a map $\uparrow: P \rightarrow \mathcal{P}(P)$. Or perhaps it's more accurate to say they're defining a family of maps (or a way to construct maps).

Now, if we are asked to use this construction to "define a map" on a new domain (as (2) seems to be doing), there seems to be only one obvious way to do so: $\uparrow: Q \rightarrow \mathcal{P}(Q) := \{q' \in Q | q ≤_{Q} q'\}$. Applying this to the domain $P_{op}$, we get:

$$\uparrow : P_{op} \rightarrow \mathcal{P}(P_{op})$$ $$p \mapsto \{p' \in P_{op} | p \leq_{op} p'\}$$

But then the monotonicity condition is false. For example, $3 \leq_{op} 2$ but $\{3, 2, 1\} \nsubseteq \{2, 1\}$.

What they apparently want is for us to use $\leq$ when constructing the upper set, but $\leq_{op}$ when checking monotonicity. Somehow this possibility never even crossed my mind. Even knowing now that this is the correct interpretation, I literally cannot read it that way.

Should it have been obvious? How would I know to interpret the question this way, other than the fact that it's false otherwise (which I wouldn't be able to detect before interpreting the question)? Is there another way to phrase their question to make it more precise and unambiguous?

I'm having tremendous difficulty getting through the text because of descriptions like this (see also here, and also my confusion here from another book).

(Edited to be more painfully clear what I'm asking.)

A_P
  • 1,007

1 Answers1

2

In (1) we are indeed taking about an arrow $\uparrow: P \to \mathcal{P}(P)$. Assuming that $U(P)$ denotes the set of upper sets on $P$, we have that $U(P) \subseteq \mathcal{P}(P)$, and the image of $\uparrow$ is included in $U(P)$. So we may view it as a map $\uparrow: P \to U(P)$.

Now, $P$ is a pre-order by assumption. The powerset $\mathcal{P}(P)$ carries a natural order, namely the inclusion (making it into a partial order). Then $U(P)$ inherits this order. There is a link between the order on $P$ and the one on $U(P)$. For any $p, q \in P$ we have $$ p \leq q \implies \uparrow q \subseteq \uparrow p. $$ This is precisely the wrong way around for $\uparrow$ to be monotone. So we just flip the order on $P$ to make $\uparrow$ monotone: $$ q \leq_{op} p \implies \uparrow q \subseteq \uparrow p. $$ Note that we did not change the definition of the map $\uparrow$, so we still calculate $\uparrow p$ with respect to the original order.

If you know any category theory, then you know that we can view $P$ and $U(P)$ as categories. This is then saying precisely that $\uparrow: P \to U(P)$ is a contravariant functor.

Mark Kamsma
  • 12,935
  • First, thanks for taking the time to write this out! Let me try to reword my confusion. If (2) had said something like "show that this defines a map $\uparrow: Q \rightarrow \ldots$", should the reader have thought "that's nonsense, because we haven't defined Q? I imagine not: they should just apply the given construction to Q ($q' \in Q|q \leq_{Q}q')$. After all, they clearly say we are defining a map here. So how would we know not to reinterpret it similarly for $P_{op}$ (other than the fact that the statement is wrong if we don't)? – A_P Jul 30 '19 at 15:44
  • 1
    @A_P I guess that you could interpret it that way, although I do think that the way it is written now is precise enough. This might just be because I'm used to reading texts like this, but here are a few things that 'give it away' for me (aside from the fact that other interpretations simply don't work). This is by far the easiest interpretation, and often that is the right interpretation. Also, we agree that it is clear in (1) what is happening, and (2) refers to "this" construction (i.e. the construction in (1)), so the map is already defined. – Mark Kamsma Jul 30 '19 at 16:22
  • So we already have the map in (2) and we are only interested in the property of it being monotone or not now. You do make a valid point that if it said "... a map $\uparrow: Q \to \ldots$" it could not refer to the map in (1) but rather to the construction in (1). However, this is not what it says. Part (2) is about a map $\uparrow: P_{op} \to U(P)$, so there is a clear link with what has happened before. – Mark Kamsma Jul 30 '19 at 16:23
  • Finally, part (1) is defining a map between sets. Even though that map uses a certain structure on a set to define it, that information is kind of lost once we have the map (footnote), so we end up with just a map between sets. Then only in the next part we start caring about this map respecting a certain structure on the sets. (footnote = of course, the point of this entire exercise is to show that we can actually recover the original structure on $P$ from just that map) – Mark Kamsma Jul 30 '19 at 16:23
  • Thanks very much for the explanation. I think what's (still) bothering me is the phrasing "this construction defines a (...) map." So I have a hard time seeing, as you do, that "the map is already defined." My mind desperately wants to use the construction to define a map. The second part is that to check monotonicity, we do of course need to use $\leq_{op}$. For some reason I have a very hard time imagining using two different $\leq$'s to check one thing. Hopefully I'll improve at inferring meaning over time, but so far it's not looking good! – A_P Jul 30 '19 at 22:16
  • @A_P well, the fact that you are trying to be as precise as you can is actually looking good! You could also keep the order on $P$ the same and look at $U(P)_{op}$ instead. As I said before, this is an example of a contravariant functor, and these come up a lot (if you Google that, I'm sure you'll find a lot of examples). It's just a fact that we sometimes have to take the dual (the "op") on one side. Which side that is doesn't really matter. – Mark Kamsma Jul 30 '19 at 22:51
  • Thanks. I've actually learned about contravariant functors! Somehow, unless the wording of a statement is very precise and unambiguous (in a way that suits me), I seem to be completely unable to process it -- even if I already know about the point it's trying to make. I've updated the question to include two other examples of that. What's worse is that generally I can't even phrase my confusion in a way that others can recognize and help with! I guess keep on truckin'.... – A_P Jul 31 '19 at 03:41
  • 1
    If a statement is ambiguous, pick the simplest way to make it unambiguous, and see if that unambiguous statement seems correct and consistent with everything else being said. If it's not, try the second simplest way, etc. After you do this for a few years, it all happens so automatically you don't even notice it - except when it takes a lot of tries to come up with something reasonable. There are always going to be some difficult cases. – John Baez Aug 10 '19 at 06:13
  • Thanks Prof @JohnBaez! Since it still takes me a while to make sense of new statements, and there are sometimes multiple axes of ambiguity, I've been trying to save effort by getting it right the first time. I see this is counterproductive. BTW, I realized the other reason this confused me: I find it strange to identify elements from $P$ and $P_{op}$. That is, since a statement like $p (\in P_{op}) = p (\in P)$ feels formally incorrect, the process of taking an element from the domain $P_{op}$ and applying the given construction within $P$ also felt invalid. – A_P Oct 15 '19 at 15:13
  • It can be helpful to give the elements of $P_{op}$ different names from those of $P$, like $p_{op}$ instead of $p$. But the usual convention is to say $P_{op}$ has the exact same elements as $P$, so people often don't do this. It's just a convention, not a necessity. – John Baez Oct 16 '19 at 04:38