Category Theory Illustrated – Orders(abuseofnotation.github.io) |
Category Theory Illustrated – Orders(abuseofnotation.github.io) |
Category theory is also not that impressive unless you already understand some of the semantics it is trying to unify. In this regards, the book itself presents, for example, the initial property as trivial at first hand, unless you notice that it does not simply hold for arbitrary structures.
https://www.amazon.com/Conceptual-Mathematics-First-Introduc...
[1, 3, 2].sort((a, b) => { if (a > b) { return true
} else {
return false
} This is not a valid comparator. It returns bools where the API expects a negative, zero or positive result, on my Chrome instance it returns `[1, 3, 2]`. That is roughly the level of correctness of the mathematics in the article as well, which I'm trying to present in sibling comment: https://news.ycombinator.com/item?id=47814213
And to tie it down to the mathematics: if a sorting algorithm asks for a full comparison between a and b, and your function returns only a bool, you are conflating the "no" (a is before b) with the "no" (a is the same as b). This fails to represent equality as a separate case, which is exactly the kind of imprecision the author should be trying to teach against.
Unfortunately acyclicity isn't called an "order" so people assume it's something unrelated. But "orders" are just second-order properties that binary relations can fulfill, and acyclicity is also such a property.
Acyclicity is a generalization of strict (irreflexive) partial orders, just like strict partial orders are a generalization of strict total (linear) orders. Every strict partial order relation is acyclic, but not every acyclic relation is a strict partial order.
A strict partial order is a binary relation that is both acyclic and transitive, i.e. a strict partial order is the transitive closure of an acyclic relation.
Binary relations of any kind can be represented as sets of pairs, or as directed graphs. If the binary relation in the directed graph is acyclic, that graph is called a "directed acyclic graph", or DAG. In a DAG the transitive closure (strict partial order) is called the reachability relation.
Examples of common acyclic relations that are not strict partial orders: x∈y (set membership), x causes y, x is a parent of y.
This article is like living there for few months. You see things, some of them you recognize as something similar to what you have at home, then you learn how the locals look at them and call them. And suddenly you can understand what somebody means when they say:
"Each distributive lattice is isomorphic to an inclusion order of its join-irreducible elements."
Having a charitable local (or expat with years there under their belt) that helps you grasp it because they know where you came from, just like the person who wrote this article, is such a treasure.
I have been engaged in some work on s-arc transitive graphs in algebraic graph theory. You'd be surprised how rarely I have to draw an actual graph. Most of the time my work involves reasoning about group actions, automorphisms, arc-stabilisers, etc.
For anyone curious what this looks like in practice, I have some brief notes here: <https://susam.net/26c.html#algebraic-graph-theory>. They do not cover the specific results on s-arc-transitivity I have been working on but they give a flavour of the area. A large part of graph theory proceeds without ever needing to draw specific graphs.
I'm unclear what the last 10% of 'category theory' gives us.
A morphism from orange to yellow means "O <= Y". From this, antisymmetry (and the hidden assumption) implies that "Y not <= O".
Totality is just the other way around (all two distinct elements are comparable in one direction).
"All diagrams that look something different than the said chain diagram represent partial orders"
"The different linear orders that make up the partial order are called chains"
The Birkhoff theorem statement, which is materially wrong. A finite distributive lattice is not isomorphic to "the inclusion order of its join-irreducible elements".
Nobody seems to care or notice. I'm watching in disbelief how nobody is pointing out the article is full of inaccuracies. See my sibling thread for a (very) incomplete list, which should disqualified this as a serious reading: https://news.ycombinator.com/item?id=47814213
My conclusion cannot be other than this ought to be useless for the general practitioner, since even wrong mathematics is appreciated the same as correct mathematics.
I don't know. I finished my graduate studies in math a few years ago, and pretty much every textbook by well-known mathematicians was packed with errors. I just stopped caring so much about inaccuracies. Every math book is going to have them. Human beings are imperfect, and great mathematicians are no exception. I'd just download the errata from the uni website and keep it open while reading.
Writing a program and proving a theorem are the same act. (Curry–Howard–Lambek.) For well-behaved programs, every program is a proof of something and every proof is a program. The match is exact for simple typed languages and leaks a bit once you add general recursion (an infinite loop “proves” anything in Haskell), but the underlying identity is real. Lambek added the third leg: these are also morphisms in a category. [1]
Algebra and geometry are one thing wearing different costumes. (Stone duality and cousins.) A system of equations and the shape it cuts out aren’t related, they’re the same object seen from opposite sides. Grothendieck rebuilt algebraic geometry on this idea, with schemes (so you can do geometry on the integers themselves) and étale cohomology (topological invariants for shapes with no actual topology). His student Deligne used that machinery to settle the Weil conjectures in 1974. Wiles’s Fermat proof lives in the same world, though it leans on much more than the categorical foundations. [2]
[0] https://en.wikipedia.org/wiki/Yoneda_lemma
[1] https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
https://math.stackexchange.com/questions/823289/abstract-non...
Sometimes the proof in category theory is trivial but we have no lower dimension or concrete intuition as to why that is true. This whole state of affairs is called abstract nonsense.
imo, this is a problem with how it's taught! Order theory is super useful in programming. The main challenge, beyond breaking past that barrier of perceived "pointlessness," is getting away from the totally ordered / "Comparator" view of the world. Preorders are powerful.
It gives us a different way to think about what correct means when we test. For example, state machine transitions can sometimes be viewed as a preorder. And if you can squeeze it into that shape, complicated tests can reduce down to asserting that <= holds. It usually takes a lot of thinking, because it IS far from the daily routine, but by the same rationale, forcing it into your daily routing makes it familiar. It let's you look at tests and go "oh, I bet that condition expression can be modeled as a preorder on [blah]"
The 'not accurate' diagram says that orange-less-than-yellow implies yellow-not-less-than-orange. Hard to find fault with.
> NO. Antisymmetry doesn't exclude `x = y`. Ties are permitted in the equality case. Antisymmetry for a non-strict order says that if both directions hold, the two elements must in fact be the same element. The author is describing strict comparison or total comparability intuition, not antisymmetry.
I like the article's "imprecise prose" better:
You have x ≤ y and y ≤ x only if x = yThe prose "It also means that no ties are permitted - either I am better than my grandmother at soccer or she is better at it than me" is inaccurate for describing antisymmetry. In the same short section, you first state the correct condition:
You have x ≤ y and y ≤ x only if x = y
from which it doesn't follow that "It also means that no ties are permitted". The "no ties" idea belongs to a stronger notion such as a strict total order, not to antisymmetry.
We should strive to name all things by their function not by their inventor or discoverer IMO. But people like their ribbons.
Anyways, the discussion begins with these people. Who all use the name to reference the paper which contains the result. As the discussion expand, it remains centered on this group and you have to talk _with_ them and not at them so you use the name they do. This usage slowly expands, until eventually it gets written in a textbook, taught to grad students, then to undergrads, and it becomes hopeless to change the name.
I share the frustration with naming, we can come up with such better names for things now. But until we give stipend bonuses for good naming, the experts will never care to do so. But i wholeheartedly disagree that the problem as a whole can be reduced to "people like their ribbons". Naming something after yourself is so gauche and would not be tolerated in my field at least. The other professors would create a better name simply out of spite for your greed.
You (presumably) aren't your grandmother, so we have x=/=y. Therefore by the biimplication, (x ≤ y and y ≤ x) is false i.e. either x ≤ y (I am better than my grandmother) or y ≤ x (my grandmother is better than me). The "neither" case is excluded by the law of totality.
We literally said the same thing. It doesn't follow from antisymmetry.
My point is precisely that:
(x <= y /\ y <= x) -> x = y
does not entail
x <= y \/ y <= x
The second statement is totality/comparability, not antisymmetry.
Let's scroll up a little bit and read from the section you're finding fault with:
the most straightforward type of order that you think of is linear order i.e. one in which every object has its place depending on every other object
If the author wanted to describe a 'no ties' scenario where every object has its own unique place, they should have defined a strict total order.
They may know everything about mathematics for all I care. I am critiquing what I am reading, not the author's knowledge.
Edit: for anyone wanting a basic example, ["aa", "aa", "ab"] under the usual lexicographic <=. All elements are comparable, so "every object has its place depending on every other object." It also "leaves no room for ambiguity in terms of which element comes before which": aa = aa < ab. Linear order means everything is comparable, not that there are no ties. By claiming "no ties are permitted" while defining the order as a reflexive, antisymmetric relation, the author is mixing a strict-order intuition into a non-strict-order definition.
Definition: An order is a set of elements, together with a binary relation between the elements of the set, which obeys certain laws.
the relationship between elements in an order is commonly denoted as ≤ in formulas, but it can also be represented with an arrow from first object to the second.
"aa" ≤ "aa"
"ab" ≤ "ab"
"aa" ≤ "ab"
> By claiming "no ties are permitted" while defining the order as a reflexive, antisymmetric relation, the author is mixing a strict-order intuition into a non-strict-order definition.
There aren't any ties to permit or reject.
we can formulate it the opposite way too and say that each object should not have the relationship to itself, in which case we would have a relation than resembles bigger than, as opposed to bigger or equal to and a slightly different type of order, sometimes called a strict order.Extremely strange to see a sort that returns bool, which is one of two common sort comparator APIs, and assume it's a wrong implementation of the other common sort API.
I do see why you're assuming JS, but you shouldn't assume it's any extant programming language. It's explanatory pseudocode.
Ah! You're talking about Racket or Scheme!
```
> (sort '(3 1 2) (lambda (a b) (< a b)))
'(1,2,3)
```
I suppose you ought to go and tell the r6rs standardisation team that a HN user vehemently disagrees with their api: https://www.r6rs.org/document/lib-html-5.96/r6rs-lib-Z-H-5.h...
To address your actual pedantry, clearly you have some implicit normative belief about how a book about category theory should be written. That's cool, but this book has clearly chosen another approach, and appears to be clear and well explained enough to give a light introduction to category theory.
As for your 'light introduction' comment: even ignoring the code, these are not pedantic complaints but basic mathematical and factual errors.
For example, the statement of Birkhoff’s Representation Theorem is wrong. The article says:
> Each distributive lattice is isomorphic to an inclusion order of its join-irreducible elements.
That is simply not the theorem. The theorem says "Theorem. Any finite distributive lattice L is isomorphic to the lattice of lower sets of the partial order of the join-irreducible elements of L.". You can read the definition on Wikipedia [0]
The article is plain wrong. The join-irreducibles themselves form a poset. The theorem is about the lattice of down-sets of that poset, ordered by inclusion. So the article is NOT simplifying, but misstating one of the central results it tries to explain. Call it a 'light introduction' as long as you want. This does not excuse the article from reversing the meaning of the theorem.
It's basically like saying 'E=m*c' is a simplification of 'E=m*c^2'.
[0] https://en.wikipedia.org/wiki/Birkhoff%27s_representation_th...
> The article is plain wrong.
> This does not excuse the article from reversing the meaning of the theorem.
What's with this hyperbole? Even the best math books have loads of errors (typographical, factual, missing conditions, insufficient reasoning, incorrect reasoning, ...). Just look at any errata list published by any university for their set books! Nobody does this kind of hyperbole for errors in math books. Only on HN do you see this kind of takedown, which is frankly very annoying. In universities, professors and students just publish errata and focus on understanding the material, not tearing it down with such dismissive tone. It's totally unnecessary.
I don't know if you've got an axe to grind here or if you're generally this dismissive but calling it "simply not the theorem" or "plain wrong" is a very annoying kind of exaggeration that misses all nuance and human fallibility.
Yes, the precise statement of Birkhoff's representation theorem involves down-sets of the poset of join-irreducibles. Yes, the article omits that. I agree that it is imprecise.
But it's not "reversing the meaning". It still correctly points to reconstructing the lattice via an inclusion order built from join-irreducibles. What's missing is a condition. It is sloppy wording but not a fundamental error like you so want us to believe.
Feels like the productive move here is just to suggest the missing wording to the author. I'm sure they'll appreciate it. I don't really get the impulse to frame it as a takedown and be so dismissive when it's a small fix.