Options

Chapter 1

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

«134

Comments

  • 1.
    edited March 27

    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!
  • 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.
  • 3.
    edited March 27

    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.
  • 4.
    edited March 26

    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.
  • 5.
    edited March 27

    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!]
  • 6.
    edited March 26

    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 $$
  • 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.
  • 8.
    edited March 26

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

    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\]
  • 9.
    edited March 26

    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!
  • 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.
  • 11.
    edited March 27

    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)
  • 12.
    edited March 27

    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?)
  • 13.

    Is there a timeline for the course?

    Comment Source:Is there a timeline for the course?
  • 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.
  • 15.
    edited March 27

    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
  • 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?
  • 17.
    edited March 27

    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"?
  • 18.
    edited March 27

    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.
  • 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\\)
  • 20.
    edited March 27

    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.
  • 21.
    edited March 27

    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.
  • 22.
    edited March 27

    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.)
  • 23.
    edited March 27

    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.
  • 24.
    edited March 27

    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.
  • 25.
    edited March 27

    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\\).
  • 26.
    edited March 27

    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\\).
  • 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?
  • 28.

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

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

    Any subset of a poset is a poset.

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

    A Cartesian product of posets is a poset.

    Comment Source:A Cartesian product of posets is a poset.
  • 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).
  • 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.
  • 33.
    edited March 27

    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.
  • 34.
    edited March 28

    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.)
  • 35.
    edited March 28

    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.
  • 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?
  • 37.
    edited March 28

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

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

    All single element sets are posets.

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

    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.
  • 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.
  • 41.
    edited March 28

    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?
  • 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.
  • 43.
    edited March 28

    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) \\)
  • 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?
  • 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.
  • 46.
    edited March 28

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

    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/ [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...)
  • 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"?
  • 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.
  • 49.
    edited March 28

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