If you want to learn category theory in a way that is more orthodox, a lot of people recommend Tom Leinster’s Basic Category Theory, which is free[1]. I’m going to be working through it soon, but the bit I’ve skimmed through looks really good if more “mathsy” than things like TFA. It also does a better job (imo) of justifying the existence of category theory as a field of study.
Disclaimer for the book, and for category theory in general: most books are optimized for people who already master mathematics at an undergraduate level. If you're not familiar with algebraic structures, linear algebra, or topology, be prepared to learn them along the way from different resources.
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.
If someone does not want to check the mathematics line by line and prefers to give the article the benefit of the doubt, note that it also presents this JavaScript:
[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
Ok, let's say that it is not JS, but an untyped, closure-based programming language with a strikingly similar array and sort API to JS. Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case.
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.
> Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case.
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
Rather than the usual "harrumph! This writer knows NOTHING of mathematics and has no business writing about it," maybe a simple counter-example would do, i.e. present an ordering "in which every object has its place depending on every other object" and "leaves no room for ambiguity in terms of which element comes before which" but also satisfies your requirement of allowing 'equal' ordering.
It's obviously not a general 3-way comparison API, _because_ it's returning bool!
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.
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.
I think it is pretty obvious that at the challenge with all abstract mathematics in general and the category theory in particular isnt the fact that people dont understand what a "linear order" is, but the fact it is so distant from daily routine that it seems completely pointless. It's like pouring water over pefectly smooth glass
This does the standard thing of treating preorders as the default generalization of partial orders. But an (arguably) more natural, and more useful, generalization of partial orders is acyclicity.
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.
I love how math is like a new language, in a new country, of culture you are not exactly familiar with.
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.
There is a way to frame category theory such that it's all just arrows -- by associating the identity arrow (which all objects have by definition) with the object itself. In a sense, the object is syntactic sugar.
I once saw a man with a notebook and pencil drawing these kinds of diagrams, at the time I saw them as graph theory. I wasn't in an extrovert moment and missed my chance to ask. He seemed to be working recreationally on them. I'm wondering about puzzles that could be easily created using these theories / maths. You, practitioners, any suggestions?
I've barely read about Category Theory, but isn't it a just a slightly more mathy version of what programmers have been doing all along? Going up and down levels of abstraction, graphs, functions that transform one type of "object" into another?
Unless there's some idiosyncratic meaning for the =>, the Antisymmetry one basically says Orange -> Yellow => Yellow -/> Orange. The diagram is not acurate. The prose is very imprecise. "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." 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.
binary relations defining order are more nuanced than they seem; a linear order isn't just about ranking, it's about the structure of the relationships themselves.
61 comments
[1] https://arxiv.org/pdf/1612.09375
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
})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=47814213And 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.
> Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case.
Let's scroll up a little bit and read from the section you're finding fault with:
Rather than the usual "harrumph! This writer knows NOTHING of mathematics and has no business writing about it," maybe a simple counter-example would do, i.e. present an ordering "in which every object has its place depending on every other object" and "leaves no room for ambiguity in terms of which element comes before which" but also satisfies your requirement of allowing 'equal' ordering.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.
> an untyped closure-based programming language with a similar array and sort api to JS
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.
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'm unclear what the last 10% of 'category theory' gives us.
Pis supposed to be >=AandB. There are also numerous grammatical and spelling errors=>, the Antisymmetry one basically saysOrange -> Yellow => Yellow -/> Orange. The diagram is not acurate. The prose is very imprecise. "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." NO. Antisymmetry doesn't excludex = 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.