Options

Chapter 1

24

Comments

  • 51.

    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.

    Comment Source:> **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.
  • 52.
    edited March 28

    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.

    Comment Source: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.
  • 53.
    edited March 28

    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.

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

    56 @David Tanzer

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

    Thanks a lot. Makes sense to me.

    Comment Source:#56 @David Tanzer > It’s “pre” because further conditions are needed to make an order. Thanks a lot. Makes sense to me.
  • 55.
    edited March 28

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

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

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

    Comment Source:@Bob Haugen (51): Dataflow as a partially ordered set had also occurred to me (as long as it's an acyclic graph).
  • 57.
    edited March 28

    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.

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

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

    Comment Source: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\\).
  • 59.

    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!

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

    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!

    Comment Source: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!
  • 61.
    edited March 28

    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.

    Comment Source: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.
  • 62.
    edited March 28

    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.

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

    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.

    Comment Source: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.
  • 64.
    edited March 28

    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 transitivity enough?

    Comment Source: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?_
  • 65.
    edited March 28

    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.

    Comment Source: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.
  • 66.
    edited March 28

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

    Comment Source:@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.
  • 67.
    edited March 28

    @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:

    image

    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 of "small" sets, which itself is a "large" set.

    A closely related example is Ord, the class of all ordinals. 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!

    Comment Source:@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!_
  • 68.
    edited March 28

    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.

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

    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?

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

    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 is a way of planning tasks, where the edges indicate dependencies:

    image

    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.

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

    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:

    So, we may want to dig into that eventually.

    Comment Source:[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.
  • 72.

    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.

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

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

    Comment Source:> **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).
  • 74.

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

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

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

    Comment Source:The Agda Standard Library also uses the conventional term(s). See [Relation.Binary](https://agda.github.io/agda-stdlib/Relation.Binary.html).
  • 76.
    edited March 28

    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.

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

    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.

    Comment Source: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.
  • 78.
    edited April 1

    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.

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

    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.

    Comment Source: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.
  • 80.
    edited March 29

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

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

    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.

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

    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)

    Comment Source: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)
  • 83.
    edited March 29

    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.

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

    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.

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

    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.

    Comment Source:> **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).
  • 86.

    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:

    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 over \(X\).

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

    Comment Source: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\\).
  • 87.
    edited March 29

    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.

    Comment Source: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.
  • 88.
    edited March 29

    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.

    Comment Source: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.
  • 89.
    edited March 29

    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.

    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?

    Comment Source: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?
  • 90.
    edited March 29

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

    Comment Source: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").
  • 91.

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

    Comment Source: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 $$
  • 92.
    edited March 29

    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]

    Comment Source: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]
  • 93.
    edited March 29

    David #23 wrote:

    What is the relationship between DAGs and posets?

    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.

    Comment Source:[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.
  • 94.

    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.

    Comment Source: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.
  • 95.
    edited March 29

    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.

    Comment Source:**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.
  • 96.

    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?

    Comment Source: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?
  • 97.
    edited March 29

    David Tanzer wrote

    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.

    Comment Source:[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.
  • 98.

    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.

    Comment Source: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.
  • 99.
    edited March 29

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

    Comment Source: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\\).
  • 100.
    edited March 29

    Vladislav wrote:

    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.

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