Howdy, Stranger!

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

Options

Chapter 1

edited March 2018

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

Comments

• Options
1.
edited March 2018

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:

I think Adam is working on neuroscience!

Comment Source: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](http://www.mit.edu/~eadam/eadam_PhDThesis.pdf)_, Ph.D. thesis, Massachusetts Institute of Technology, July 2017. I think Adam is working on neuroscience! 
• Options
2.

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

Comment Source:The lemon meringue pie diagram is order-preserving. Can't put the meringue on top until the filling is added.
• Options
3.
edited March 2018

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.

Comment Source: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.
• Options
4.
edited March 2018

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.

Comment Source: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.
• Options
5.
edited March 2018

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!]

Comment Source: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!]
• Options
6.
edited March 2018

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

$$E = mc^2$$

Comment Source:Let me try LaTeX with double dollar signs - that still seems to work: $$E = mc^2$$
• Options
7.

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.

Comment Source: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.
• Options
8.
edited March 2018

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]

Comment Source:Dan Schmidt - your answer is right! But now I'm not in the mood for talking math until we get the LaTeX fixed. <img src = "http://math.ucr.edu/home/baez/emoticons/computer_problems.gif"> 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$
• Options
9.
edited March 2018

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!

Comment Source: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!
• Options
10.

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

Comment Source:Is it obvious where to send typos and other suggestions? I'm guessing this is not the place.
• Options
11.
edited March 2018

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

Comment Source: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"](https://forum.azimuthproject.org/discussion/1750/mistakes-in-seven-sketches-in-compositionality)
• Options
12.
edited March 2018

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?)

Comment Source: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?)
• Options
13.

Is there a timeline for the course?

Comment Source:Is there a timeline for the course?
• Options
14.

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.

Comment Source: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.
• Options
15.
edited March 2018

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

Comment Source:> 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](https://en.wikipedia.org/wiki/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*](https://en.wikipedia.org/wiki/Partially_ordered_set#Formal_definition) 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](https://en.wikipedia.org/wiki/Category_of_preordered_sets). Modal logicians call them "[S4 Kripke Frames](https://ncatlab.org/nlab/show/the+logic+S4%28m%29#relation_to_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](https://en.wikipedia.org/wiki/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 
• Options
16.

Does the answer to Ex 1.3.2 contain 31 arrows?

Comment Source:Does the answer to Ex 1.3.2 contain 31 arrows?
• Options
17.
edited March 2018

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"?

Comment Source: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](https://en.wikipedia.org/wiki/Category_of_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"? 
• Options
18.
edited March 2018

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:

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.

Comment Source: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!](https://forum.azimuthproject.org/discussion/1717/welcome-to-the-applied-category-theory-course#latest) 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.
• Options
19.

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

Comment Source:> 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\$$
• Options
20.
edited March 2018

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.

Comment Source: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. 
• Options
21.
edited March 2018

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.

Comment Source: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. 
• Options
22.
edited March 2018

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

Comment Source:Example of poset: A collection of individuals, ordered by the ancestor relation. (Assuming that X is trivially an ancestor of itself.)
• Options
23.
edited March 2018

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.

Comment Source: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.
• Options
24.
edited March 2018

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

Comment Source:Example of preorder: Any set of propositions, ordered by the implication relation.
• Options
25.
edited March 2018

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

Comment Source: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\$$. 
• Options
26.
edited March 2018

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

Comment Source: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\$$. 
• Options
27.

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?

Comment Source: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?
• Options
28.

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

Comment Source:Other obvious posets: natural numbers, integers, rational numbers, real numbers.
• Options
29.

Any subset of a poset is a poset.

Comment Source:Any subset of a poset is a poset.
• Options
30.

A Cartesian product of posets is a poset.

Comment Source:A Cartesian product of posets is a poset.
• Options
31.

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

Comment Source: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).
• Options
32.

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.

Comment Source: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.
• Options
33.
edited March 2018

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.

Comment Source: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.
• Options
34.
edited March 2018

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

Comment Source: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.)
• Options
35.
edited March 2018

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.

Comment Source: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.
• Options
36.

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?

Comment Source: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?
• Options
37.
edited March 2018

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

Comment Source:We should also pay respects to the trivial poset {}.
• Options
38.

All single element sets are posets.

Comment Source:All single element sets are posets.
• Options
39.
edited March 2018

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

Comment Source:And every set, along with the identity ordering relation, is a poset.
• Options
40.

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

Comment Source:A set of formulas, ordered by the sub-formula relation, is a poset.
• Options
41.
edited March 2018

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

Comment Source:Daniel Cellucci, if \$$q \notin P\$$, then what does \$$A_q\$$ mean?
• Options
42.

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.

Comment Source: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. 
• Options
43.
edited March 2018

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

Comment Source: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) \$$
• Options
44.

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

The states of atoms decaying?

Comment Source:Is the group of states in a non-reversible chemical reaction a poset? The states of atoms decaying?
• Options
45.

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

Comment Source:\$$\\#\$$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](https://en.wikipedia.org/wiki/Category_of_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!). &#35;39 Keith Lewis, this is partly responding to you.
• Options
46.
edited March 2018

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/

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

Comment Source: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/  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...)
• Options
47.

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

Comment Source:Question: forgive my ignorance, but why is it called "preorder" and not just "order"? What is the significance of the "pre"?
• Options
48.

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

Comment Source:I think also that a dataflow in a dataflow architecture is a poset or partially-ordered set.
• Options
49.
edited March 2018

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.

Comment Source: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.
• Options
50.

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.

Comment Source: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_.
Sign In or Register to comment.