Chapter 1

John Baez

This thread is for discussing Chapter 1 of Brendan Fong and David Spivak's, Seven Sketches in Compositionality: An Invitation to Applied Category Theory.

John Baez

You can start by reading the chapter, which is largely an introduction to posets and adjunctions. If you already know this material, please be patient while other participants catch up. In the meantime you can look at this thesis, which the chapter touches on rather lightly:

• Elie M. Adam, Systems, Generativity and Interactional Effects, Ph.D. thesis, Massachusetts Institute of Technology, July 2017.

I think Adam is working on neuroscience!

WebHubTel

The lemon meringue pie diagram is order-preserving. Can't put the meringue on top until the filling is added.

John Baez

Here are some puzzles that people can answer while waiting for the course to officially start. I will call my exercises "puzzles" to distinguish them from the exercises in the book, and number them so we can keep track of them.

Puzzle 1. What is a "poset" according to Chapter 1 of Fong and Spivak's book?

Puzzle 2. How does their definition differ from the usual definition found in, e.g., Wikipedia or the nLab?

Puzzle 3. What do mathematicians usually call the thing that Fong and Spivak call a poset?

I think I want to use the usual mathematical term: I don't want to release 70 students into the world who use a nonstandard definition of "poset".

Puzzle 4. List some interesting and important examples of posets that haven't already been listed in other comments in this thread.

John Baez

I'll give one answer to Puzzle 4: the set real numbers $\mathbb{R}$, with the usual notion of $\le$, is a poset. We use it all the time, for example to say that one person is taller than another, or richer than another.

Shit, LaTeX isn't working. This won't be good. LaTeX used to work here.

Dan Schmidt

Puzzles 1-3 were useful in clarifying my understanding (thanks John) but I will leave the answers to others. For Puzzle 4, my go-to poset example is always the set of pairs \( (x,y) \in \mathbb R^2 \) where \( a \leq b \) when \( a_x \leq b_x \) and \( a_y \leq b_y \).

I guess a good "Fong-Spivak poset" example is triples \( (x,y,z) \) with the same ordering as above (\(z\) is ignored). All triples with the same \(x\) and \(y\) but different \(z\) are equivalent but are not equal.

[Edited to see if the new MathJax recipe works - it does!]

John Baez

Let me try LaTeX with double dollar signs - that still seems to work:

$$ E = mc^2 $$

Joel Sjögren

Re: Proposition 1.88 (Adjoint functor theorem for posets) How is application of 1.81 justified? I thought it required what we are trying to prove, namely that f and g are adjoint.

John Baez

Dan Schmidt - your answer is right! But now I'm not in the mood for talking math until we get the LaTeX fixed.

Joel Sjögren - I will answer your question sometime, but right now I'm just trying to see if LaTeX works here. For some reason Dan's equations didn't work. My own equation, $$E = mc^2$$, didn't work at first, but now mysteriously it has!

I need to do some testing.

This: $E = mc^2$

yields this: $E = mc^2$

This: \(E= mc^2\)

yields this: (E = mc^2)

This: $$E = mc^2$$

yields this: $$E = mc^2$$

This: \[E = mc^2\]

yields this: [E= mc^2]

John Baez

Upon refreshing my browser, just one equation works: the one where I typed this: $$E = mc^2$$. (I hope that's what everyone else sees - the web gets really nerve-racking when different people see different things.)

Okay, so you gotta hit "refresh" to see the math. But I want "in-line" equations, not centered in the page, to also work!

Robert Smart

Is it obvious where to send typos and other suggestions? I'm guessing this is not the place.

John Baez

Robert and everyone else: please go here to list typos, other mistakes, and maybe even other suggestions regarding the textbook:

• Mistakes in "Seven Sketches in Compositionality"

Jason Grossman

Dan Schmidt entered LaTeX above using the following delimiters - both the backslashes and the brackets seem to be necessary:

\\(

\\)

That works for me too, without a wait. E.g., \\(E = mc^2\\) yields \(E = mc^2\). Is anyone NOT seeing this rendered correctly?

(And by the way, is there a word for a language that has all the most useful fragments of LaTeX but isn't actually fully programmable TeX?)

Jonatan Bergquist

Is there a timeline for the course?

David Chudzicki

I've been thinking about this notion that maps which don't preserve operations lose information:

There is no operation on the booleans \( true, false \) that will always follow suit with the joining of systems: our observation is inherently lossy

Any map from more than two elements to \( \{false, true\} \) will lose information in some sense. So that's not the sense of "lossy" we're talking about here. I guess the sense in which we lose information is just this: If you apply the function before joining, you "lose information" about what you would have gotten by joining first and then applying the function.

That's the same as what it says in the chapter, but it helped me a little to put it into those words.

I also really liked that we didn't start with an operation on \( \{false, true\} \), and then ask whether it was preserved. We have a goal (impossible, in this case) of reconstructing what we would have gotten by joining first and then applying the function. Any operation that achieves this goal would be fine. This might help think about how and why we define the operations we do.

Matthew Doty

Puzzle 1: what is a "poset" according to Chapter 1 of Fong and Spivak's book?

They define a poset as a set with a preorder.

Puzzle 2: how does their definition differ from the usual definition found in, e.g., Wikipedia or the nLab?

Ordinarily, a poset is a set with a partial order rather than a preorder.

A partial order satisfies an anti symmetry axiom: if \(x \preceq y \) and \( y \preceq x \) then \( x = y \).

Puzzle 3: what do mathematicians usually call the thing that Fong and Spivak call a poset?

They are usually called preordered sets.

Modal logicians call them "S4 Kripke Frames".

Puzzle 4: list some interesting and important examples of posets that haven't already been listed in other comments in this thread.

Java classes form a preordered set when ordered by inheritance.

Natural numbers \(\mathbb{N}\) form a traditional poset under the relation "\(x\) divides \(y\)", often denoted "\(x\ |\ y\)".

For two sets \(A,B \subseteq \mathbb{N} \), we say \(A\) is Turing reducible to \(B\) if there is an oracle machine with oracle tape containing \(B\) that can compute the characteristic of \(A\). This is denoted \(A \leq_T B\). Under \(\leq_T\), \(\mathcal{P}(\mathbb{N})\) is a preordered set.

EDIT: Cleaning up terminology

Jerry Wedekind

Does the answer to Ex 1.3.2 contain 31 arrows?

John Baez

Matthew Doty answered Puzzles 1-4 correctly! But Puzzle 4 is far from finished: there are zillions of interesting posets - interesting to different people for different reasons. So, I urge people to come up with more examples.

Some comments on Matthew's remarks:

Puzzle 3: what do mathematicians usually call the thing that Fong and Spivak call a poset?

They are usually called preordered sets.

Yes! And category theorists often call them simply preorders. This could be confusing: we're calling a set \(S\) with a preorder \(\le\) simply a "preorder". But in practice it works well, and it's nice and short, so I'm likely to do this.

In summary:

Definition. Given a set \(S\), a preorder on \(S\) is a binary relation \(\le\) that is:

1. reflexive: \(x \le x\) for all \(x \in S\),

2. transitive \(x \le y\) and \(y \le z\) imply \(x \le z\) for all \(x,y,z \in S\).

Fong and Spivak, unlike everyone else on the planet, call a set with a preorder a poset. Category theorists call a set with a preorder simply a preorder.

Definition. A preorder is called a partial order if it's also antisymmetric: if \(x \le y\) and \(y \le x\) then \(x = y\) for all \(x,y\). Everyone except Fong and Spivak call a set with a partial order a partially ordered set or poset. They call it a skeletal poset.

Definition. A partial order is called a total order or linear order if it also obeys trichotomy: for all \(x,y\) we either have \(x\le y\) or \(y \le x\).

Puzzle 5. Why is this property called "trichotomy"?

John Baez

Jonatan Bergquist wrote:

Is there a timeline for the course?

Not really; I'm making this up as I go along. However, I really want it to be done before September 25th, when I start teaching classes at U.C. Riverside again. (I'm taking the spring as a non-teaching quarter, and that quarter has just started. Our summer quarter runs late, until September 25th. )

This raises the question of how to use this time. But I think it's better to discuss the plan of the course, or lack thereof, in comments over here:

• Welcome to the Applied Category Theory Course!

So, in a while I'll try to move your comment and my reply over there. The "Chapter 1", "Chapter 2", etc. threads are best saved for discussions about those chapters.

Jared Summers

Puzzle 5. Why is this property called "trichotomy"?

Because for elements \(x\) and \(y\) there are exactly three possibilities:

\(x < y\) or \(y < x\) or \(x = y\)

Alex Ortiz

An example of posets from analysis. If a measure space \((X,\mu)\) is \(\sigma\)-finite, then its \(L^p\) spaces (the collection of measurable functions \(f\colon X\to\Bbb C\) such that \(\int_X|f|^p\,\rm{d}\mu<\infty\)) can be preordered by set inclusion. In general this is not a total order. However, consider a finite measure space \((X,\mu)\). As a consequence of Hölder's inequality, we can actually put a total order on the \(L^p\) spaces with inclusion: $$ L^q(X,\mu)\subseteq L^p(X,\mu)\qquad\text{if $1\le p\le q\le \infty$.} $$

I would be interested if anybody knew of any interesting follow-up points to this post, since while it's true that we can do this, it feels somewhat contrived.

David Tanzer

Example of poset: Any collection of sets, ordered by the inclusion relation.

More generally, any collection of "set like" things, ordered by inclusion, is a poset:

• The lattice of subspaces of a vector space, ordered by inclusion.

• Any set of algebras of the same type, ordered by inclusion.

David Tanzer

Example of poset: A collection of individuals, ordered by the ancestor relation. (Assuming that X is trivially an ancestor of itself.)

David Tanzer

Exercise: What is the relationship between DAGs and posets?

A directed graph is a pair (Nodes,Edges), where Nodes is a set, and Edges is a binary relation on Nodes, i.e., Edges is a set of ordered pairs of nodes. The graph is acyclic if there is no non-empty path of edges that leads from a node back to itself. A DAG is a directed graph that is acyclic.

David Tanzer

Example of preorder: Any set of propositions, ordered by the implication relation.

David Tanzer

Poset construction: If \(A\) is a set, and \(S\) is a poset, then the set of functions from \(A\) to \(S\) is a poset, where \(f \le g\) is defined by \(f(a) \le g(a)\) for all \(a \in A\).

David Tanzer

Preorder construction: If \(A\) is a set, and \(S\) is a preorder, then the set of functions from \(A\) to \(S\) is a preorder, where \(f \le g\) is defined by \(f(a) \le g(a)\) for all \(a \in A\).

Daniel Cellucci

For exercise 1.12.3, I'm somewhat confused about how to go about proving this (proofs were never my strong suit). Is it not possible that

$$ \bigcup\limits_{p\in P} A_p = A \cap A_q $$ where $$q \notin P$$

I.e. if you union all the partitions, there might be elements of the set in non-closed and non-connected groups?

David Tanzer

Other obvious posets: natural numbers, integers, rational numbers, real numbers.

David Tanzer

Any subset of a poset is a poset.

David Tanzer

A Cartesian product of posets is a poset.

Joel Sjögren

The reflexive-transitive closure of any relation is a poset. Given A, define B inductively by (i) B(x,x) (ii) if B(x, y) and A(y, z) then B(x, z).

The transpose of any poset is a poset. Given A, define B explicitly by B(x, y) = A(y, x).

Adding to David's product construction, more generally the function type A -> S can be made dependent. Given an "index set" A and for each a in A a poset S(a), the set (a:A)->S(a) of functions which to each a in A arrange a unique s in S(a), can be ordered by defining f <= g to mean, as before, for all a, f(a) <= g(a).

Cole D. Pruitt

How about the set of all legal chess positions as a preorder? In this case, \(\leq\) is interpreted as "can produce by legal moves".

This doesn't seem partially ordered, though, because cycles are possible: I can move a bishop back and forth to repeat a position (i.e., \(A \leq B\), \(B \leq A\)) but the positions are not identical.

Ammar Husain

What are the monotone functions out of the reachability in chess positions? Number of pieces left of each type almost always goes down except there is pawn promotion so that doesn't work. Seems like a fun exercise.

Dan Schmidt

I don't believe that the set of all legal chess positions, with \(\leq\) meaning "can produce by legal moves", is a preorder set, since it does not satisfy the reflexivity condition. For example, if the current position \(x\) is a check in which the only legal response is a pawn move, then \(x\nleq x\). (Maybe this can be fixed by allowing the number of intervening legal moves to be 0, and perhaps that's what you meant anyway.)

Cole D. Pruitt

Dan, I agree: as far as I can tell, it hinges on the compelled move question with respect to the only non-reversible piece (pawn), and/or whether 0 legal moves is included in the definition of \(\leq\). I think if pawns are all removed from the board at the start of the game, the question is sidestepped and the reachable positions are strictly preordered, but there might be another corner case I am missing.

Keith Lewis

So can we use the L word now? Or maybe I am missing why they are using posets for that. Is it a cute way of introducing Category Theory?

David Tanzer

We should also pay respects to the trivial poset {}.

Matthew Johnson

All single element sets are posets.

David Tanzer

And every set, along with the identity ordering relation, is a poset.

David Tanzer

A set of formulas, ordered by the sub-formula relation, is a poset.

Joseph Moeller

Daniel Cellucci, if \(q \notin P\), then what does \(A_q\) mean?

Joseph Moeller

I don't think trying to restrict the pieces so that every position can be altered and returned to in a positive number of steps is the right way to go. I think if you are in a checkmate position, then there is no way to return to that position in a positive number of steps, for one counterpoint.

It seems most natural to mean that a position is less than or equal to another if you can get from one to the other in a natural number of steps.

Alex Kreitzberg

Real numbers between 0 and 1 are a poset. The map from events to their probabilities is then Monotonic. \(A \leq B \Rightarrow P(A) \leq P(B) \)

Jonatan Bergquist

Is the group of states in a non-reversible chemical reaction a poset?

The states of atoms decaying?

Simon Willerton

\(\#\)18 (John Baez)

Puzzle 3: what do mathematicians usually call the thing that Fong and Spivak call a poset?

They are usually called preordered sets.

Yes! And category theorists often call them simply preorders.

Other times category theorists call them categories enriched in the Boolean category, \(\{ \mathrm{true}, \mathrm{false}\}\).

Don't worry if you don't know what that means! I suspect we might be heading in the direction of understanding what this means, in particular understanding what Galois connections have to do with adjunctions (for those who know what adjunctions are!).

#39 Keith Lewis, this is partly responding to you.

Bob Haugen

I think that a material or process flow, where the outputs of one process become inputs to other processes until no more processes have yet occurred, can be a poset or or a partially-ordered set, depending on the configuration. However, such a flow can also contain cycles (where byproducts feed back into previous processes, like food waste becoming compost which is used to grow more food). Here's a diagram of that flow: http://locecon.org/clusters/network/8/

[edit] per clarifications from Artur Grzesiak and David Tanzer on the next page, I now understand that the flow with the cycle is a preorder, but without the cycle, it would be a partial order. (Hope I understood correctly...)

Bob Haugen

Question: forgive my ignorance, but why is it called "preorder" and not just "order"? What is the significance of the "pre"?

Bob Haugen

I think also that a dataflow in a dataflow architecture is a poset or partially-ordered set.

Dan Schmidt

Cole@38 + Joseph@45: Yes, I realized the same thing about terminal positions after sleeping on it. More trickily, we also would run into problems with forced captures (e.g., it's the only way to answer a check, or artificial "almost-stalemate" positions). I think there's no shame in allowing 0 moves between positions for \( \leq \): after all, it is \( \leq \) and not \( < \).

By the way, as long as we're being picky, I'm assuming we're including all state (castling rights, en passant ability) in the definition of a position.

Artur Grzesiak

Preorder relation is reflexive and transitive only, whereas partial order is anti-symmetric as well. In case of preorder if you follow arrows you may come back to your starting point, but in case of partial order you can only go in one direction (apart from following identity). It seems that if for each cycle of preorder you collapse it to a single object you will end up with a partial order. From that perspective partial order is isomorphic to a tree, and pre-order is a kind of tree structure with some local eddies allowed.