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

- All Categories 2.3K
- Chat 495
- Study Groups 6
- Biological Models 1
- Categorical Network Theory 1
- Programming with Categories 4
- Review Sections 6
- MIT 2020: Programming with Categories 53
- MIT 2020: Lectures 21
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 64
- Azimuth Code Project 110
- Statistical methods 2
- Drafts 1
- Math Syntax Demos 15
- Wiki - Latest Changes 0
- Strategy 111
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 708

## Comments

A very simple example.

Let \(P = \{ (a,b): a < b \land (a,b) \in \mathbb{R^2} \}\) then following relations are posets:

Since this is applied course one interpretation could be that first number denotes start of some process and the second number its end. So in case of 1. a process is larger than another one if it started after another one started and ended after another one ended. While in case of 2. process is larger than another one if the latter started and ended when the first one was active.

`> **Puzzle 4.** List some interesting and important examples of posets that haven't already been listed in other comments in this thread. A very simple example. Let \\(P = \\{ (a,b): a < b \land (a,b) \in \mathbb{R^2} \\}\\) then following relations are posets: 1. \\((a,b)R(c,d) \iff a \le c \land b \le d \\) 2. \\(xRy \iff x \subseteq y \\) Since this is applied course one interpretation could be that first number denotes start of some process and the second number its end. So in case of 1. a process is larger than another one if it started after another one started and ended after another one ended. While in case of 2. process is larger than another one if the latter started and ended when the first one was active.`

Daniel@30: A typical way to prove \(A = \cup_{p\in P}{A_p} \) is by double inclusion. Since \(A_p\) are all subsets of \(A\) one inclusion is clear. For the other, suppose there is an \(a\in A\) and \(a\not\in\cup_{p\in P}{A_p} \), what can be said about \({a}\) ?

Edit: For some reason the brackets are not showing, both "a" are supposed to be the set containing only "a".

SPOILER: \({a}\) is a \(\sim\)-connected and \(\sim\)-closed subset, contradiction.

`Daniel@30: A typical way to prove \\(A = \cup_{p\in P}{A_p} \\) is by double inclusion. Since \\(A_p\\) are all subsets of \\(A\\) one inclusion is clear. For the other, suppose there is an \\(a\in A\\) and \\(a\not\in\cup_{p\in P}{A_p} \\), what can be said about \\(\{a\}\\) ? Edit: For some reason the brackets are not showing, both "a" are supposed to be the set containing only "a". SPOILER: \\(\{a\}\\) is a \\(\sim\\)-connected and \\(\sim\\)-closed subset, contradiction.`

There can be cycles in a preorder, so it doesn’t look ordered. Consider that the complete relation, where \(x \le y\) for all \(x\), \(y\), is a preorder.

It’s “pre” because further conditions are needed to make an order.

p.s. No need to apologize for asking an honest question. Nobody was born knowing about the definitions of preorders.

`There can be cycles in a preorder, so it doesn’t look ordered. Consider that the complete relation, where \\(x \le y\\) for all \\(x\\), \\(y\\), is a preorder. It’s “pre” because further conditions are needed to make an order. p.s. No need to apologize for asking an honest question. Nobody was born knowing about the definitions of preorders.`

## 56 @David Tanzer

Thanks a lot. Makes sense to me.

`#56 @David Tanzer > It’s “pre” because further conditions are needed to make an order. Thanks a lot. Makes sense to me.`

Example of poset: tasks in a feasible schedule, ordered by the dependency (direct or indirect) relationship.

More generally, every DAG induces a poset, where the ordering is by the ancestor relationship (stipulating X as being trivially an ancestor of itself).

`Example of poset: tasks in a feasible schedule, ordered by the dependency (direct or indirect) relationship. More generally, every DAG induces a poset, where the ordering is by the ancestor relationship (stipulating X as being trivially an ancestor of itself).`

@Bob Haugen (51): Dataflow as a partially ordered set had also occurred to me (as long as it's an acyclic graph).

`@Bob Haugen (51): Dataflow as a partially ordered set had also occurred to me (as long as it's an acyclic graph).`

Section 1.1 says

Is that true of observation in general? Or does it conflate observation with the human approach to it - namely abstraction? Abstraction is necessarily a lossy process; it's not clear to me that observation is.

`Section 1.1 says > observation is inherently lossy: in order to extract information from something, one must drop the details. Is that true of observation in general? Or does it conflate observation with the human approach to it - namely abstraction? Abstraction is necessarily a lossy process; it's not clear to me that observation is.`

Another question on the lossy nature of observation. Re-stating the final paragraph of section 1.1, from an information-theoretic perspective:

Assuming that's valid, is it reasonable to interpret generative effects as

(re)discovery? In other words: we are re-discovering latent properties of \(X\) that were elided by \(f\). An important consequence would seem, therefore, that the information resulting from those generative effects is bounded, pre-determined, and equivalent to \(Ix - Iy\).`Another question on the lossy nature of observation. Re-stating the final paragraph of section 1.1, from an information-theoretic perspective: 1. Let the initial system \\(X\\) have information content \\(Ix\\) 2. Subject \\(X\\) to a lossy observation \\(f\\) producing system \\(Y\\) with information content \\(Iy\\\) 3. By definition, \\(Iy < Ix\\) Assuming that's valid, is it reasonable to interpret generative effects as *(re)discovery*? In other words: we are re-discovering latent properties of \\(X\\) that were elided by \\(f\\). An important consequence would seem, therefore, that the information resulting from those generative effects is bounded, pre-determined, and equivalent to \\(Ix - Iy\\).`

In a lot of math, the prefix "pre-" is added to a structure you want to talk about, but you don't quite have, but you have a general construction to get you there. Given a preorder, there is a general construction which turns it into a partial order. Given a presheaf, there is a general construction which turns it into a sheaf (called sheafification :P). That's why its "pre-" and not "semi-" or some other "half", because its not quite there, but you know it will get there eventually!

`In a lot of math, the prefix "pre-" is added to a structure you want to talk about, but you don't quite have, but you have a general construction to get you there. Given a preorder, there is a general construction which turns it into a partial order. Given a presheaf, there is a general construction which turns it into a sheaf (called sheafification :P). That's why its "pre-" and not "semi-" or some other "half", because its not quite there, but you know it will get there eventually!`

What is the motivation for the authors to use a non-standard definition of poset (and moreover, not call it out as non-standard in the text)?

I definitely appreciate the puzzles and responses calling out the discrepancy!

`What is the motivation for the authors to use a non-standard definition of poset (and moreover, not call it out as non-standard in the text)? I definitely appreciate the puzzles and responses calling out the discrepancy!`

Pablo @ 55: is it fair to say, then, that all elements of \(A\) must belong to a ~-connected and ~-closed subset of \(A\)?

I thought of a few possible examples of posets on the train this morning, that are maybe isomorphic to the ones already described but would represent interesting scientific applications.

1) level of detail in a worldview being generated by mobile agent performing information/feature fusion on a WSN (6.1.4 of Nakamura Et. Al.) \(\leq\) would be an operator comparing "level of detail" or "breadth of knowledge", and would be used to arbitrate conflicts in decisions drawn from different agents

2) the dependency graph of spacecraft failures, where \(\leq\) would indicate "leads to" or "increases the likelihood of"

3) circumstantial evidence in a set of experiments toward a conclusion in a life detection experiment (such as McKay et. al.), where \(\leq\) would indicate that a conclusion is "more likely to be caused by life"

References: Nakamura, Eduardo F., Antonio AF Loureiro, and Alejandro C. Frery. "Information fusion for wireless sensor networks: Methods, models, and classifications." ACM Computing Surveys (CSUR) 39.3 (2007): 9.

McKay, David S., et al. "Search for past life on Mars: possible relic biogenic activity in Martian meteorite ALH84001." Science 273.5277 (1996): 924-930.

`Pablo @ 55: is it fair to say, then, that all elements of \\(A\\) must belong to a ~-connected and ~-closed subset of \\(A\\)? I thought of a few possible examples of posets on the train this morning, that are maybe isomorphic to the ones already described but would represent interesting scientific applications. 1) level of detail in a worldview being generated by mobile agent performing information/feature fusion on a WSN (6.1.4 of Nakamura Et. Al.) \\(\leq\\) would be an operator comparing "level of detail" or "breadth of knowledge", and would be used to arbitrate conflicts in decisions drawn from different agents 2) the dependency graph of spacecraft failures, where \\(\leq\\) would indicate "leads to" or "increases the likelihood of" 3) circumstantial evidence in a set of experiments toward a conclusion in a life detection experiment (such as McKay et. al.), where \\(\leq\\) would indicate that a conclusion is "more likely to be caused by life" References: Nakamura, Eduardo F., Antonio AF Loureiro, and Alejandro C. Frery. "Information fusion for wireless sensor networks: Methods, models, and classifications." ACM Computing Surveys (CSUR) 39.3 (2007): 9. McKay, David S., et al. "Search for past life on Mars: possible relic biogenic activity in Martian meteorite ALH84001." Science 273.5277 (1996): 924-930.`

Scott Fleischman: they do say, at the top of p. 11, "Contrary to the definition we've chosen, the term poset frequently is used to mean partially ordered set, rather than preordered set", but their wording makes it sound like it's more of a convention that they took one choice on, rather than a complete break with standard definitions. I too am curious why they went this route. If preordered sets are somehow easier to work with, they could use them but still call them the right thing.

`Scott Fleischman: they do say, at the top of p. 11, "Contrary to the definition we've chosen, the term poset frequently is used to mean partially ordered set, rather than preordered set", but their wording makes it sound like it's more of a convention that they took one choice on, rather than a complete break with standard definitions. I too am curious why they went this route. If preordered sets are somehow easier to work with, they could use them but still call them the right thing.`

Scott Fleischman, the difference between partial orders and preorders is that partial orders demand equality where preorders only demand equivalence. Equality is sometimes called "evil" in category theory.

https://ncatlab.org/nlab/show/principle+of+equivalence.

`Scott Fleischman, the difference between partial orders and preorders is that partial orders demand equality where preorders only demand equivalence. Equality is sometimes called "evil" in category theory. https://ncatlab.org/nlab/show/principle+of+equivalence.`

Two more puzzles connected to Lecture 3:

Puzzle 6.How do reflexivity and transitivity of \(\le\) follow from the rules of a category, if we have a category with at most one morphism from any object \(x\) to any object \(y\), and we write \(x \le y\) when there exists a morphism from \(x\) to \(y\)?Puzzle 7.Why does any set with a reflexive and transitive relation \(\le\) yield a category with at most one morphism from any object \(x\) to any object \(y\)? That is: why are reflexivity and transitivityenough?`Two more puzzles connected to [Lecture 3](https://forum.azimuthproject.org/discussion/1812/lecture-3-chapter-1-posets): **Puzzle 6.** How do reflexivity and transitivity of \\(\le\\) follow from the rules of a category, if we have a category with at most one morphism from any object \\(x\\) to any object \\(y\\), and we write \\(x \le y\\) when there exists a morphism from \\(x\\) to \\(y\\)? **Puzzle 7.** Why does any set with a reflexive and transitive relation \\(\le\\) yield a category with at most one morphism from any object \\(x\\) to any object \\(y\\)? That is: why are reflexivity and transitivity _enough?_`

Dan wrote:

I hope that's what he meant. Here's what a category theorist would say if they weren't trying to be polite:

We take nothing seriously.

Veryseriously. Math works much more smoothly if you treat degenerate cases, like zero and the empty set, with the same respect as nondegenerate ones.`Dan wrote: > 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 hope that's what he meant. Here's what a category theorist would say if they weren't trying to be polite: > The most reasonable interpretation of "can produce by legal moves" is "can produce by some natural number of legal moves" - and any mathematician who doesn't count 0 as a natural number ought to be taken out and shot, along with those who don't think the empty set is a set. We take nothing seriously. _Very_ seriously. Math works much more smoothly if you treat degenerate cases, like zero and the empty set, with the same respect as nondegenerate ones.`

@BobHaugen wrote:

The original concept of

totally ordered setororder, still dominant today, obeys a bunch of rules:reflexivity: \(x \le x\)transitivity: \(x \le y\) and \(y \le z\) imply \(x \le z\)antisymmetry: if \(x \le y\) and \(y \le x\) then \(x = y\)trichotomy: for all \(x,y\) we either have \(x\le y\) or \(y \le x\).The real numbers with the usual \(\le\) obeys all these. Then people discovered many situations where rule 4 does not apply. If only rules 1-3 hold they called it a

partially ordered setorposet. Then people discovered many situations where rule 3 does not hold either! If only rules 1-2 hold they called it apreordered setorpreorder.Category theory teaches us that preorders are the fundamental thing: see Lecture 3. But we backed our way into this concept, so it has an awkward name. Fong and Spivak try to remedy this by calling them posets, but that's gonna confuse everyone even more! If they wanted to save the day they should have made up a beautiful brand new term.

`@BobHaugen wrote: > Question: forgive my ignorance, but why is it called "preorder" and not just "order"? What is the significance of the "pre"? The original concept of **totally ordered set** or **order**, still dominant today, obeys a bunch of rules: 1. **reflexivity**: \\(x \le x\\) 2. **transitivity**: \\(x \le y\\) and \\(y \le z\\) imply \\(x \le z\\) 3. **antisymmetry**: if \\(x \le y\\) and \\(y \le x\\) then \\(x = y\\) 4. **trichotomy**: for all \\(x,y\\) we either have \\(x\le y\\) or \\(y \le x\\). The real numbers with the usual \\(\le\\) obeys all these. Then people discovered many situations where rule 4 does not apply. If only rules 1-3 hold they called it a **partially ordered set** or **poset**. Then people discovered many situations where rule 3 does not hold either! If only rules 1-2 hold they called it a **preordered set** or **preorder**. Category theory teaches us that preorders are the fundamental thing: see [Lecture 3](https://forum.azimuthproject.org/discussion/1812/lecture-3-chapter-1-posets). But we backed our way into this concept, so it has an awkward name. Fong and Spivak try to remedy this by calling them posets, but that's gonna confuse everyone even more! If they wanted to save the day they should have made up a beautiful brand new term.`

@David Tanzer gave some nice answers to Puzzle 4, where I was asking for examples of preorders and posets:

Yes indeed! Like this:

We could even go all out and consider the collection of

allsets, ordered by the inclusion relation! This collection is too big to be a set. But we can get around that in various ways, e.g. by considering it as a proper class, or using a universe of "small" sets, which itself is a "large" set.A closely related example is Ord, the class of all ordinals. Ordinals form a

totallyordered class. Ord starts out like this:$$ 0, 1, 2, 3, \dots, \omega, \omega + 1, \omega + 2, \dots, \omega \cdot 2, \dots, \omega^2, \dots, \omega^3, \dots, \omega^\omega, \dots, \epsilon_0, \dots $$ but it goes on a lot longer. In fact it goes on

longer than anything!`@David Tanzer gave some nice answers to Puzzle 4, where I was asking for examples of preorders and posets: > Example of poset: Any collection of sets, ordered by the inclusion relation. Yes indeed! Like this: <img src = "https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/500px-Hasse_diagram_of_powerset_of_3.svg.png"> We could even go all out and consider the collection of _all_ sets, ordered by the inclusion relation! This collection is too big to be a set. But we can get around that in various ways, e.g. by considering it as a proper class, or using a [universe](https://en.wikipedia.org/wiki/Grothendieck_universe) of "small" sets, which itself is a "large" set. A closely related example is Ord, the class of all [ordinals](https://en.wikipedia.org/wiki/Ordinal_number). Ordinals form a _totally_ ordered class. Ord starts out like this: $$ 0, 1, 2, 3, \dots, \omega, \omega + 1, \omega + 2, \dots, \omega \cdot 2, \dots, \omega^2, \dots, \omega^3, \dots, \omega^\omega, \dots, \epsilon_0, \dots $$ but it goes on a lot longer. In fact it goes on _longer than anything!_`

Scott Fleischmann wrote:

They're evil. They're trying to spread confusion and destroy mathematics. They're funded by Putin and they're working for Cambridge Analytica.

Seriously, as Dan Schmidt suggests in 62, they believe - correctly! - that posets are less fundamental than preorders. However, I think it's misguided for them to tackle this by renaming preorders "posets". They should either call them "preorders", like everyone else does, or make up some brand new term if they think "preorder" is too ugly.

`Scott Fleischmann wrote: > What is the motivation for the authors to use a non-standard definition of poset (and moreover, not call it out as non-standard in the text)? They're evil. They're trying to spread confusion and destroy mathematics. They're funded by Putin and they're working for Cambridge Analytica. Seriously, as Dan Schmidt suggests in 62, they believe - correctly! - that posets are less fundamental than preorders. However, I think it's misguided for them to tackle this by renaming preorders "posets". They should either call them "preorders", like everyone else does, or make up some brand new term if they think "preorder" is too ugly.`

I agree about the natural numbers including 0. I'm trying to think of how to justify the strength of my opinion on this though. Usually I think notation should be adjusted to the situation to facilitate explanation. Why is the definition of the naturals more important though?

`I agree about the natural numbers including 0. I'm trying to think of how to justify the strength of my opinion on this though. Usually I think notation should be adjusted to the situation to facilitate explanation. Why is the definition of the naturals more important though?`

Dan Cellucci gave this answer to Puzzle 4:

Indeed, this kind of example is very important in applications! A PERT chart is a way of planning tasks, where the edges indicate dependencies:

There's more to a PERT chart than a mere preorder, as Simon Willerton has explained. We may get into that later. However, any PERT chart gives rise to a preorder.

`Dan Cellucci gave this answer to Puzzle 4: > the dependency graph of spacecraft failures, where \\(\le\\) would indicate "leads to" or "increases the likelihood of". Indeed, this kind of example is very important in applications! A [PERT chart](https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique) is a way of planning tasks, where the edges indicate dependencies: <img src = "https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Pert_chart_colored.svg/320px-Pert_chart_colored.svg.png"> There's more to a PERT chart than a mere preorder, as [Simon Willerton has explained](https://golem.ph.utexas.edu/category/2013/03/project_planning_parallel_proc.html). We may get into that later. However, any PERT chart gives rise to a preorder.`

Scott Finnie: I prefer to tackles these questions of "lossy observation" and "generative effects" a bit later, after we have some machinery built up. Fong and Spivak dangle them as a lure to get people interested in posets. Then they come back and develop the ideas a bit further. But they seem to be drawing on this thesis, which goes much further:

Systems, Generativity and Interactional Effects, Ph.D. thesis, Massachusetts Institute of Technology, July 2017.So, we may want to dig into that eventually.

`[Scott Finnie](https://forum.azimuthproject.org/discussion/comment/16058/#Comment_16058): I prefer to tackles these questions of "lossy observation" and "generative effects" a bit later, after we have some machinery built up. Fong and Spivak dangle them as a lure to get people interested in posets. Then they come back and develop the ideas a bit further. But they seem to be drawing on this thesis, which goes much further: * 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. So, we may want to dig into that eventually.`

Possibly interesting, didn't see it in SImon WIllerton's article, a PERT chart is usually created from a work breakdown structure by means of https://en.wikipedia.org/wiki/Topological_sorting - just from the name, you would think it should appear in applied cats! Toposorts work on partial orderred sets.

`Possibly interesting, didn't see it in SImon WIllerton's article, a PERT chart is usually created from a work breakdown structure by means of https://en.wikipedia.org/wiki/Topological_sorting - just from the name, you would think it should appear in applied cats! Toposorts work on partial orderred sets.`

git commits appear to form a poset. They don't acquire any of the other properties of ordered sets until after you've resolved all conflicts

andare looking at a particular branch on a particular remote. The lack of a total order is one of the biggest complaints newcomers have about git, and the commit log looking at one particular branch is an observation on the commit history (and it is plenty lossy).`> **Puzzle 4.** List some interesting and important examples of posets that haven't already been listed in other comments in this thread. git commits appear to form a poset. They don't acquire any of the other properties of ordered sets until after you've resolved all conflicts _and_ are looking at a particular branch on a particular remote. The lack of a total order is one of the biggest complaints newcomers have about git, and the commit log looking at one particular branch is an observation on the commit history (and it is plenty lossy).`

Some people call them

quasi orders. In particular, Isabelle/HOL has a`quasi_order`

axiom class in its Orderings theory. Some people working in combinatorics also use this term (here is a short bibliography).Preorder is still far more common. Unlike Isabelle/HOL, Coq uses the conventional term (see Coq.Classes.RelationClasses).

`> They should either call them "preorders", like everyone else does, or make up some brand new term if they think "preorder" is too ugly. Some people call them _quasi orders_. In particular, Isabelle/HOL has a <code>quasi_order</code> axiom class in its [Orderings theory](https://isabelle.in.tum.de/dist/library/HOL/HOL/Orderings.html). Some people working in combinatorics also use this term ([here](https://en.wikipedia.org/wiki/Well-quasi-ordering#Notes) is a short bibliography). Preorder is still far more common. Unlike Isabelle/HOL, Coq uses the conventional term (see [Coq.Classes.RelationClasses](https://coq.inria.fr/library/Coq.Classes.RelationClasses.html)).`

The Agda Standard Library also uses the conventional term(s). See Relation.Binary.

`The Agda Standard Library also uses the conventional term(s). See [Relation.Binary](https://agda.github.io/agda-stdlib/Relation.Binary.html).`

One partial order more, on the set of functions of the natural numbers on themselves. One function is bigger than another, when it is bigger in all natural numbers of the domain except at finite quantity at worst. The order is not total. Plotkin has translated the german papers of Hausdorff on order theory in a beautiful book and this order appears there nontrivially.

`One partial order more, on the set of functions of the natural numbers on themselves. One function is bigger than another, when it is bigger in all natural numbers of the domain except at finite quantity at worst. The order is not total. Plotkin has translated the german papers of Hausdorff on order theory in a beautiful book and this order appears there nontrivially.`

Here are two more examples of preorders. Take your favorite set X.

1) For all x in X, setting \(x \leq x\) gives you a preorder.

2) For all x,y in X, setting \(x \leq y \) gives you a preorder.

`Here are two more examples of preorders. Take your favorite set X. 1) For all x in X, setting \\(x \leq x\\) gives you a preorder. 2) For all x,y in X, setting \\(x \leq y \\) gives you a preorder.`

here is my take on the question.

1) In a operating system (or language env. like nodejs) -- a set of packages.

For example all versions of all packages form a set. There is a dependency relation between some packages, and in some other cases -- there is no dependency relation at all

The dependency relation is uni-directional (in the sense that Package B depends on package A, can be viewed as PackageB < PackageA ).

Because the relation does not exist across all the entities, this is partially ordered set.

2)[This example is not correct. See comments below. ] In Borrower-Lender business relation. Same thing. There are some borrowers and lenders that can be represented as B1<B2 meaning that B1 borrows from B2. Of course, not everybody borrows from everybody. So just like example 1) above, this binary relation does not exist across all the members. Therefore this is partially ordered, just like the above.

`> Puzzle 4. List some interesting and important examples of posets that haven't already been listed in other comments in this thread. here is my take on the question. 1) In a operating system (or language env. like nodejs) -- a set of packages. For example all versions of all packages form a set. There is a dependency relation between some packages, and in some other cases -- there is no dependency relation at all The dependency relation is uni-directional (in the sense that Package B depends on package A, can be viewed as PackageB < PackageA ). Because the relation does not exist across all the entities, this is partially ordered set. 2)[This example is not correct. See comments below. ] In Borrower-Lender business relation. Same thing. There are some borrowers and lenders that can be represented as B1<B2 meaning that B1 borrows from B2. Of course, not everybody borrows from everybody. So just like example 1) above, this binary relation does not exist across all the members. Therefore this is partially ordered, just like the above.`

Daniel Michael Cicala wrote:

Nice! This leads to some other puzzles:

Puzzle 8.What simple law do Daniel's preorders obey, that does not hold for the real numbers with its usual notion of \(\leq\)?Puzzle 9.What do you call preorders that obey this law?Clearly Puzzle 9 relies on getting the "right" answer to Puzzle 8, meaning the one that I'm thinking of. There could be other correct answers to Puzzle 8 that I haven't thought of.

`Daniel Michael Cicala wrote: > Here are two more examples of preorders. Take your favorite set X. > 1) For all x in X, setting \\(x \leq x\\) gives you a preorder. > 2) For all x,y in X, setting \\(x \leq y \\) gives you a preorder. Nice! This leads to some other puzzles: **Puzzle 8.** What simple law do Daniel's preorders obey, that does not hold for the real numbers with its usual notion of \\(\leq\\)? **Puzzle 9.** What do you call preorders that obey this law? Clearly Puzzle 9 relies on getting the "right" answer to Puzzle 8, meaning the one that I'm thinking of. There could be other correct answers to Puzzle 8 that I haven't thought of.`

Joseph wrote:

This is an interesting question. The natural numbers are the free monoid on one generator. The "bad" natural numbers, without 0, are the free semigroup on one generator. So, this question is related to another: "why are monoids better than semigroups?"

One answer is that, contrary to what you might think, the category of semigroups and semigroup homomorphisms embeds as a subcategory of the category of monoids and monoid homomorphisms in a very nice way. That is, there's a very real sense in which monoids are

more general!How does this work?

I'll let you ponder this puzzle. It's a special case of another puzzle: why do we demand categories have identity morphisms? Shouldn't we focus on more general "semicategories", where we don't demand the existence of identities?

When you put the puzzle this way, another answer rises into view: in a semicategory, you can't define what it means for objects to be isomorphic! (Well, okay, you can, since

someobjects will have identity morphisms, and you can use those when they're available. But then you'll get objects that aren't isomorphic to themselves, which is annoying.)`Joseph wrote: > I agree about the natural numbers including 0. I'm trying to think of how to justify the strength of my opinion on this though. Usually I think notation should be adjusted to the situation to facilitate explanation. Why is the definition of the naturals more important though? This is an interesting question. The natural numbers are the free monoid on one generator. The "bad" natural numbers, without 0, are the free semigroup on one generator. So, this question is related to another: "why are monoids better than semigroups?" One answer is that, contrary to what you might think, the category of semigroups and semigroup homomorphisms embeds as a subcategory of the category of monoids and monoid homomorphisms in a very nice way. That is, there's a very real sense in which monoids are _more general!_ How does this work? I'll let you ponder this puzzle. It's a special case of another puzzle: why do we demand categories have identity morphisms? Shouldn't we focus on more general "semicategories", where we don't demand the existence of identities? When you put the puzzle this way, another answer rises into view: in a semicategory, you can't define what it means for objects to be isomorphic! (Well, okay, you can, since _some_ objects will have identity morphisms, and you can use those when they're available. But then you'll get objects that aren't isomorphic to themselves, which is annoying.)`

Let's see if I'm thinking along the same lines as John...

Puzzle 8: \(x \leq y \rightarrow x \cong y\). That is, the only way for elements to be related is to be in the same equivalence class.

Puzzle 9: Partitions.

`Let's see if I'm thinking along the same lines as John... Puzzle 8: \\(x \leq y \rightarrow x \cong y\\). That is, the only way for elements to be related is to be in the same equivalence class. Puzzle 9: Partitions.`

Daniel #27: In Exercise 1.12, to prove that the specified union = A (no more no less), show that every element in the union is in A (ez by definition of the sets making up the union), and that every element x of A is in the union (by describing the ~-closed, ~-connected subset of A which contains x)

`Daniel #27: In Exercise 1.12, to prove that the specified union = A (no more no less), show that every element in the union is in A (ez by definition of the sets making up the union), and that every element x of A is in the union (by describing the ~-closed, ~-connected subset of A which contains x)`

Dan Schmidt wrote:

You're definitely on the right track, but your proposed answer to Puzzle 8 isn't really a law obeyed by the relation \(\le\). You're writing a law that involves some

otherconcept \(\cong\) which we're supposed to have in mind already. I want a law that you can write down using just the relation \(\le\), sort of like reflexivity and transitivity and those other laws.`Dan Schmidt wrote: > Let's see if I'm thinking along the same lines as John... You're definitely on the right track, but your proposed answer to Puzzle 8 isn't really a law obeyed by the relation \\(\le\\). You're writing a law that involves some _other_ concept \\(\cong\\) which we're supposed to have in mind already. I want a law that you can write down using just the relation \\(\le\\), sort of like reflexivity and transitivity and those other laws.`

I thought they were calling lattices posets. Just enjoying following along. Reading a biography of my mathematical hero John von Neumann. What an amazing man. Voevodesky was the closest recent approximation.

`I thought they were calling lattices posets. Just enjoying following along. Reading a biography of my mathematical hero John von Neumann. What an amazing man. Voevodesky was the closest recent approximation.`

Both obey the

symmetryrule: if \(x \leq y\) then \(y \leq x\)They are

equivalence relations.`> **Puzzle 8.** What simple law do Daniel's preorders obey, that does not hold for the real numbers with its usual notion of \\(\leq\\)? Both obey the *symmetry* rule: if \\(x \leq y\\) then \\(y \leq x\\) > **Puzzle 9.** What do you call preorders that obey this law? They are [*equivalence relations*](https://en.wikipedia.org/wiki/Equivalence_relation).`

Another example of a preorder is the Specialization preorder for a topology \(\tau\). This is defined:

$$ x \leq y \Longleftrightarrow x \in \mathbf{cl}(\{y \}) $$ Where \(\mathbf{cl}(\cdot)\) is the closure operator for \(\tau\).

As Daniel Michael Cicala mentioned:

(1) is the specialization preorder of the discrete topology over \(X\).

(2) is the specialization preorder of the trivial topology over \(X\).

`Another example of a preorder is the [Specialization preorder](https://en.wikipedia.org/wiki/Specialization_(pre)order) for a topology \\(\tau\\). This is defined: $$ x \leq y \Longleftrightarrow x \in \mathbf{cl}(\\{y \\}) $$ Where \\(\mathbf{cl}(\cdot)\\) is the [closure](https://en.wikipedia.org/wiki/Closure_(topology)) operator for \\(\tau\\). As Daniel Michael Cicala mentioned: > Here are two more examples of preorders. Take your favorite set \\(X\\). > 1) For all \\(x\\) in \\(X\\), setting \\(x\leq x\\) gives you a preorder. > 2) For all \\(x, y\\) in \\(X\\), setting \\(x\leq y\\) gives you a preorder. (1) is the specialization preorder of the [discrete topology](https://en.wikipedia.org/wiki/Discrete_space) over \\(X\\). (2) is the specialization preorder of the [trivial topology](https://en.wikipedia.org/wiki/Trivial_topology) over \\(X\\).`

Since preorders don't guarantee antisymmetry, I'm a little concerned that meets and joins might not be unique. Is this a case in which category theory only concerns itself with "uniqueness up to isomorphism"? That seems reasonable enough at first, but it's at odds with phrases like "the meet" or "the join" and when considering the proof of Proposition 1.88, f, defined pointwise as a meet, doesn't seem like it's well-defined.

`Since preorders don't guarantee antisymmetry, I'm a little concerned that meets and joins might not be unique. Is this a case in which category theory only concerns itself with "uniqueness up to isomorphism"? That seems reasonable enough at first, but it's at odds with phrases like "the meet" or "the join" and when considering the proof of Proposition 1.88, f, defined pointwise as a meet, doesn't seem like it's well-defined.`

John, if you "prefer to tackle these questions of "lossy observation" and "generative effects" a bit later", should we skip straight to the poset part? I was able to follow everything up to 1.1.2 and do the exercises, but felt rather unclear about what the author was saying.

`John, if you "prefer to tackle these questions of "lossy observation" and "generative effects" a bit later", should we skip straight to the poset part? I was able to follow everything up to 1.1.2 and do the exercises, but felt rather unclear about what the author was saying.`

Matthew Doty wrote:

Right! This is what I was looking for. But Dan Schmidt was on the right track, because any partition determines an equivalence relation, and vice versa. They are two ways of thinking about the same thing.

This sort of preorder is sort of the extreme opposite case from a total order, since total orders obey the

antisymmetryrule: if \(x \leq y\) and \(y \leq x\) then \(x = y\).What are all the total orders that are also equivalence relations?

`Matthew Doty wrote: > > > **Puzzle 8.** What simple law do Daniel's preorders obey, that does not hold for the real numbers with its usual notion of \\(\leq\\)? > > Both obey the *symmetry* rule: if \\(x \leq y\\) then \\(y \leq x\\) > > **Puzzle 9.** What do you call preorders that obey this law? > They are [*equivalence relations*](https://en.wikipedia.org/wiki/Equivalence_relation). Right! This is what I was looking for. But Dan Schmidt was on the right track, because any partition determines an equivalence relation, and vice versa. They are two ways of thinking about the same thing. This sort of preorder is sort of the extreme opposite case from a total order, since total orders obey the **antisymmetry** rule: if \\(x \leq y\\) and \\(y \leq x\\) then \\(x = y\\). What are all the total orders that are also equivalence relations?`

Chris Goughnor wrote:

You're right, they're not. They're unique when our preorder is a poset. (They may still not

exist, but they're unique.)Yes. (If we think of preorders as categories, we can even show off and define a poset to be a preorder where isomorphic objects are equal, but we're getting way ahead of ourselves here.)

I'll have to check this out - thanks!

Category theorists often use the word "the" in a more sophisticated way where we can talk about "the" object with some property if that property determines the object up to a unique isomorphism. For example, they talk about "the" direct sum of vector spaces, or "the" 1-element set. If we talk this way, we can talk about "the" meet or join of elements in a preorder. But it would be risky for Fong and Spivak to talk this way without explaining why it's okay. Maybe they just slipped... or maybe they're talking about "the" meet or join in a situation where it's really unique, namely a poset (which they call a "skeletal poset").

`Chris Goughnor wrote: > Since preorders don't guarantee antisymmetry, I'm a little concerned that meets and joins might not be unique. You're right, they're not. They're unique when our preorder is a poset. (They may still not _exist_, but they're unique.) > Is this a case in which category theory only concerns itself with "uniqueness up to isomorphism"? Yes. (If we think of preorders as categories, we can even show off and define a poset to be a preorder where isomorphic objects are equal, but we're getting way ahead of ourselves here.) > That seems reasonable enough at first, but it's at odds with phrases like "the meet" or "the join" and when considering the proof of Proposition 1.88, f, defined pointwise as a meet, doesn't seem like it's well-defined. I'll have to check this out - thanks! Category theorists often use the word "the" in a more sophisticated way where we can talk about "the" object with some property if that property determines the object up to a unique isomorphism. For example, they talk about "the" direct sum of vector spaces, or "the" 1-element set. If we talk this way, we can talk about "the" meet or join of elements in a preorder. But it would be risky for Fong and Spivak to talk this way without explaining why it's okay. Maybe they just slipped... or maybe they're talking about "the" meet or join in a situation where it's really unique, namely a poset (which they call a "skeletal poset").`

Jesus Lopez wrote:

You mean except on a finite set of natural numbers? ("At finite quantity" isn't quite how English-speaking mathematicians talk.)

Right: if we take the characteristic function of the even numbers versus the characteristic function of the odd numbers, neither is \(\le\) the other.

Hmm, interesting! Gordon Plotkin? I know him, he's a great guy...but I have trouble imagining him translating the German papers of Hausdorff.

There's another great partial order on the set of functions \(f : \mathbb{N} \to \mathbb{N} \) - did anyone here talk about it yet? In this one we say \(f \le g\) if and only if

$$ \mathrm{limsup}_{n \to \infty} \frac{f(n)}{g(n)} \le 1 $$

`Jesus Lopez wrote: > One partial order more, on the set of functions of the natural numbers on themselves. One function is bigger than another, when it is bigger in all natural numbers of the domain except at finite quantity at worst. You mean except on a finite set of natural numbers? ("At finite quantity" isn't quite how English-speaking mathematicians talk.) > The order is not total. Right: if we take the characteristic function of the even numbers versus the characteristic function of the odd numbers, neither is \\(\le\\) the other. > Plotkin has translated the German papers of Hausdorff on order theory in a beautiful book and this order appears there nontrivially. Hmm, interesting! Gordon Plotkin? I know him, he's a great guy...but I have trouble imagining him translating the German papers of Hausdorff. There's another great partial order on the set of functions \\(f : \mathbb{N} \to \mathbb{N} \\) - did anyone here talk about it yet? In this one we say \\(f \le g\\) if and only if $$ \mathrm{limsup}_{n \to \infty} \frac{f(n)}{g(n)} \le 1 $$`

David #23: Re: Exercise: What is the relationship between DAGs and posets?

I think the Hasse diagram of a preordered set is a DAG if the preorder is also antisymmetric, i.e. if the preorder is a poset (a partially ordered set).

[additional incorrect statements deleted, though perhaps this is overkill]

`David #23: Re: Exercise: What is the relationship between DAGs and posets? I think the Hasse diagram of a preordered set is a DAG if the preorder is also antisymmetric, i.e. if the preorder is a poset (a partially ordered set). [additional incorrect statements deleted, though perhaps this is overkill]`

David #23 wrote:

Jerry just said the Hasse diagram of a poset is a DAG. That sounds correct to me, and it's very nice.

He also said that any DAG is the Hasse diagram of a poset. That makes me very nervous.

`[David #23 wrote](https://forum.azimuthproject.org/discussion/comment/15975/#Comment_15975): > What is the relationship between DAGs and posets? Jerry just said the [Hasse diagram](https://en.wikipedia.org/wiki/Hasse_diagram) of a poset is a [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph). That sounds correct to me, and it's very nice. He also said that any DAG is the Hasse diagram of a poset. That makes me very nervous.`

Sidenote: everyone feel free to edit your comments after you have made them. When the cursor is in your post, a gear will appear at the top right corner of your comment.

`Sidenote: everyone feel free to edit your comments after you have made them. When the cursor is in your post, a gear will appear at the top right corner of your comment.`

Puzzle 6.How do reflexivity and transitivity of \(\le\) follow from the rules of a category, if we have a category with at most one morphism from any object \(x\) to any object \(y\), and we write \(x \le y\) when there exists a morphism from \(x\) to \(y\)?Answer. Reflexivity follows from the existence of identity morphisms in a category. Transitivity follows from the fact that given morphisms f: A -> B, and g: B -> C, the composite morphism taking A -> C is provided by the category.

`**Puzzle 6.** How do reflexivity and transitivity of \\(\le\\) follow from the rules of a category, if we have a category with at most one morphism from any object \\(x\\) to any object \\(y\\), and we write \\(x \le y\\) when there exists a morphism from \\(x\\) to \\(y\\)? Answer. Reflexivity follows from the existence of identity morphisms in a category. Transitivity follows from the fact that given morphisms f: A -> B, and g: B -> C, the composite morphism taking A -> C is provided by the category.`

Jerry wrote:

Good! I think you wrote #93 while I was figuring out how to phrase #94. Here's a puzzle I considered posing:

What is the smallest DAG that is not the Hasse diagram of a poset?

`Jerry wrote: > I no longer believe anything in #92 after the first sentence of my answer. Good! I think you wrote #93 while I was figuring out how to phrase #94. Here's a puzzle I considered posing: What is the smallest DAG that is not the Hasse diagram of a poset?`

David Tanzer wrote

Right! So reflexivity in a preorder is secretly the identity morphisms in a specially simple sort of category, while transitivity is really just composition! This is one of those nice little "aha!" moments where category theory starts unifying concepts and eliminating redundancy, freeing up neurons for deeper thoughts.

`[David Tanzer wrote](https://forum.azimuthproject.org/discussion/comment/16164/#Comment_16164) > Reflexivity follows from the existence of identity morphisms in a category. Transitivity follows from the fact that given morphisms \\(f: A \to B\\), and \\(g: B \to C\\), the composite morphism taking \\(A \to C\\) is provided by the category. Right! So reflexivity in a preorder is secretly the identity morphisms in a specially simple sort of category, while transitivity is really just composition! This is one of those nice little "aha!" moments where category theory starts unifying concepts and eliminating redundancy, freeing up neurons for deeper thoughts.`

Yes, I meant \( \forall f,g \in \mathbb{N}^\mathbb{N}, f \leq g \Leftrightarrow \{n \in \mathbb{N} | f(n) > g(n)\} \) is finite. And you are right, It happens to be other Plotkin! But I thank him the effort no less.

`Yes, I meant \\( \forall f,g \in \mathbb{N}^\mathbb{N}, f \leq g \Leftrightarrow \\{n \in \mathbb{N} | f(n) > g(n)\\} \\) is finite. And you are right, It happens to be other Plotkin! But I thank him the effort no less.`

Belatedly, yet another preorder: In an \(n\)-player non-cooperative game, outcomes live in \(\mathbb R^n\). Player \(i\) has a preference relation \(\geq_i\) on \(\mathbb R^n\) given by \(x \geq_i y\) iff \(x_i \geq y_i\), i.e. they prefer to maximise their own payoff and are indifferent about everyone else's. This makes \(\geq_i\) a preorder. Then \(x \cong_i y\) iff \(x_i = y_i\), which means that player \(i\) is indifferent between \(x\) and \(y\).

`Belatedly, yet another preorder: In an \\(n\\)-player non-cooperative game, outcomes live in \\(\mathbb R^n\\). Player \\(i\\) has a preference relation \\(\geq_i\\) on \\(\mathbb R^n\\) given by \\(x \geq_i y\\) iff \\(x_i \geq y_i\\), i.e. they prefer to maximise their own payoff and are indifferent about everyone else's. This makes \\(\geq_i\\) a preorder. Then \\(x \cong_i y\\) iff \\(x_i = y_i\\), which means that player \\(i\\) is indifferent between \\(x\\) and \\(y\\).`

Vladislav wrote:

Is this really a preorder? If you borrow from me and I borrow from Brendan, does that mean you borrow from Brendan? I suppose this could be true in

somesense, but do you owe money to Brendan?This made me realize it's very good to find examples of relations that

seem like they might be preorders but aren't. Well-chosen counterexamples are often just as revealing as examples, since they indicate thelimitsof a concept.`[Vladislav wrote](https://forum.azimuthproject.org/discussion/comment/16120/#Comment_16120): > In Borrower-Lender business relation. Same thing. There are some borrowers and lenders that can be represented as B1<B2 meaning that B1 borrows from B2. Of course, not everybody borrows from everybody. So just like example 1) above, this binary relation does not exist across all the members. Therefore this is partially ordered, just like the above. Is this really a preorder? If you borrow from me and I borrow from Brendan, does that mean you borrow from Brendan? I suppose this could be true in _some_ sense, but do you owe money to Brendan? This made me realize it's very good to find examples of relations that _seem like they might be preorders but aren't_. Well-chosen counterexamples are often just as revealing as examples, since they indicate the _limits_ of a concept.`