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:
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!
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.
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.
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!]
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.
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\]
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!
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)
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?)
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.
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
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?
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:
reflexive: \(x \le x\) for all \(x \in S\),
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"?
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.
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\\)
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.
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.
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.
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\\).
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\\).
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?
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).
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.
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.
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.)
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.
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?
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.
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) \\)
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!).
#39 Keith Lewis, this is partly responding to you.
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...)
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.
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_.
Comments
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!
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!
The lemon meringue pie diagram is order-preserving. Can't put the meringue on top until the filling is added.
The lemon meringue pie diagram is order-preserving. Can't put the meringue on top until the filling is added.
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.
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.
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.
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.
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!]
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!]
Let me try LaTeX with double dollar signs - that still seems to work:
$$ E = mc^2 $$
Let me try LaTeX with double dollar signs - that still seems to work: $$ E = mc^2 $$
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.
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.
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]
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\]
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!
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!
Is it obvious where to send typos and other suggestions? I'm guessing this is not the place.
Is it obvious where to send typos and other suggestions? I'm guessing this is not the place.
Robert and everyone else: please go here to list typos, other mistakes, and maybe even other suggestions regarding the textbook:
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)
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?)
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?)
Is there a timeline for the course?
Is there a timeline for the course?
I've been thinking about this notion that maps which don't preserve operations lose information:
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.
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.
They define a poset as a set with a preorder.
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 \).
They are usually called preordered sets.
Modal logicians call them "S4 Kripke Frames".
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
> 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
Does the answer to Ex 1.3.2 contain 31 arrows?
Does the answer to Ex 1.3.2 contain 31 arrows?
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:
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:
reflexive: \(x \le x\) for all \(x \in S\),
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"?
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"?
Jonatan Bergquist wrote:
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.
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.
Because for elements \(x\) and \(y\) there are exactly three possibilities:
\(x < y\) or \(y < x\) or \(x = y\)
> 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\\)
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.
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.
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.
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.
Example of poset: A collection of individuals, ordered by the ancestor relation. (Assuming that X is trivially an ancestor of itself.)
Example of poset: A collection of individuals, ordered by the ancestor relation. (Assuming that X is trivially an ancestor of itself.)
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.
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.
Example of preorder: Any set of propositions, ordered by the implication relation.
Example of preorder: Any set of propositions, ordered by the implication relation.
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\).
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\\).
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\).
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\\).
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?
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?
Other obvious posets: natural numbers, integers, rational numbers, real numbers.
Other obvious posets: natural numbers, integers, rational numbers, real numbers.
Any subset of a poset is a poset.
Any subset of a poset is a poset.
A Cartesian product of posets is a poset.
A Cartesian product of posets is a poset.
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).
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).
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.
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.
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.
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.
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.)
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.)
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.
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.
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?
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?
We should also pay respects to the trivial poset {}.
We should also pay respects to the trivial poset {}.
All single element sets are posets.
All single element sets are posets.
And every set, along with the identity ordering relation, is a poset.
And every set, along with the identity ordering relation, is a poset.
A set of formulas, ordered by the sub-formula relation, is a poset.
A set of formulas, ordered by the sub-formula relation, is a poset.
Daniel Cellucci, if \(q \notin P\), then what does \(A_q\) mean?
Daniel Cellucci, if \\(q \notin P\\), then what does \\(A_q\\) mean?
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.
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.
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) \)
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) \\)
Is the group of states in a non-reversible chemical reaction a poset?
The states of atoms decaying?
Is the group of states in a non-reversible chemical reaction a poset? The states of atoms decaying?
\(\#\)18 (John Baez)
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.
\\(\\#\\)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!). #39 Keith Lewis, this is partly responding to you.
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...)
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...)
Question: forgive my ignorance, but why is it called "preorder" and not just "order"? What is the significance of the "pre"?
Question: forgive my ignorance, but why is it called "preorder" and not just "order"? What is the significance of the "pre"?
I think also that a dataflow in a dataflow architecture is a poset or partially-ordered set.
I think also that a dataflow in a dataflow architecture is a poset or partially-ordered set.
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.
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.
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.
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_.