2

I'm reading Applied Category Theory. In chapter 1, they describe "systems" that are undirected graphs. Two systems (with the same sets of vertices) can be "joined" (∨) by taking the union of their edges. They point out that after joining two systems, vertices that were not connected might have become connected. Here we consider only systems with vertices $v_1, v_2, v_3$.

Let $\phi(A)$ denote the Boolean observation of whether $v_1$ and $v_2$ are connected in system A. They say:

"[The] observation ($\phi$) fails to preserve the join operation."

At first this sounded backward to me. Isn't it that joining fails to preserve the (connectedness) observation? So I continued. They define an ordering on systems, and an ordering on Booleans, and point out that

$\phi$ preserves order but not join

What does it mean for $\phi$ to preserve order? By the usual interpretation, it means:

A ≤ B ⇒ Φ(A) ≤ Φ(B)

This makes sense because they've defined ≤ on systems (are all connections in A present in B?) and on Booleans (True > False). So, returning to whether observation preserves join, we should replace order (≤) with join (∨):

A ∨ B ⇒ Φ(A) ∨ Φ(B)

But what on earth could A ∨ B mean as a Boolean?

The text explains with an example of two systems (A and B) for which Φ(A) is false and Φ(B) is false yet Φ(A ∨ B) is true. This seems to suggest that the meaning might be:

Φ(A ∨ B) $\nRightarrow$ (or $\neq$?) Φ(A) ∨ Φ(B)

This works, but seems like the wrong interpretation for two reasons:

  1. They haven't defined join on Booleans at this point in the book. Surely they wouldn't expect that we've predicted this operation.
  2. It doesn't fit the same pattern as for order.

Alternatively, if this is the expression for "Φ fails to preserve ∨," then "Φ preserves ≤" seems like it ought to be:

Φ(A ≤ B) ⇒ (or =) Φ(A) ≤ Φ(B)

But this makes no sense either. So what is it that they mean?

A_P
  • 1,007

1 Answers1

4

When they say "the observation $\Phi$ fails to preserve the join operation, they mean that in general $\Phi(A \vee B) \neq \Phi(A) \vee \Phi(B)$.

It can be a little bit confusing because "$\Phi$ preserves joins" means that an equality ($\Phi(A \vee B) = \Phi(A) \vee \Phi(B)$) holds, while "$\Phi$ preserves order" means that an implication ($A \leq B \Rightarrow \Phi(A) \leq \Phi(B)$) is true, but this is the standard usage in mathematics.

Charlie
  • 1,597
  • Ah, thanks! So for the order implication, $\phi$ is not applied on the left. I also updated my question to indicate that they hadn't defined join on Booleans at that point, which made me even less likely to interpret the join preservation correctly. It seems like "preservation" generally means what it does for joins above, except for a few special cases like order? – A_P Jul 12 '19 at 01:40
  • 3
    In general, a function $F$ preserves a binary operation $\star$ if $F(A \star B) = F(A) \star B(A)$, and it preserves a relation $\lhd$ if $A \lhd B$ implies $F(A) \lhd F(B)$. Note that "$F(A \lhd B)$" doesn't make any sense at all. – John Baez Aug 10 '19 at 02:54
  • @JohnBaez Thanks. Responding to this way late, but I guess issues like this are assumed to be cemented in the reader's mind before tackling a book like Applied Category Theory? – A_P Jan 06 '22 at 17:35
  • It depends what issues you mean. On page 6 they say "it preserves order but not join." They define Booleans earlier on that page, at least in the version I got by clicking the link you gave. So they only problem I see is that some readers might not be familiar with the idea of a function preserving a binary operation. I suppose this, and various other ideas, are implicit prerequisites. – John Baez Jan 07 '22 at 18:12
  • 2
    @JohnBaez It seems that $f(a * b) = f(a) \cdot f(b)$ is equivalent to $(a * b = c) \Rightarrow f(a) \cdot f(b) = f(c)$, right? That may be a strange way to write things, but it looks more like the relation case. More generally, whenever I see "preserves," I should keep in mind what the structure is in the relevant category, and what it would mean to preserve that. Thanks to another Math SE question, I also realized that "preserves the group (or whatever) structure" finally made things click while "preserves the group operation" felt awkward and unintuitive for some reason. Anyway, thanks! – A_P Mar 12 '22 at 00:09