6 ms·
Category Theory Illustrated – Orders
- arketyp 6mo agoThere 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.
- nineteen999 6mo agoThis is obvious within about 3 seconds of opening the article, noticing it's filled with coloured M&M's, and closing it again.
- dgan 6mo agoI 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
- raincole 6mo agoIs there a "mind-blowing fact" about category theory? Like the first time I've heard that one can prove there is no analytical solution for a polynomial equation with a degree > 5 with group theory, it was mind-blowing. What's the counterpart of category theory?
- tux3 6mo agoSure, category theory can't prove the unsolvability of the quintic. But did you know that a monad is really just a monoid object in the monoidal category of endofunctors on the category of types of your favorite language?
- auggierose 6mo agoPhil?
- SkiFire13 6mo agoIsn't that just the definition?
- wholinator2 6mo agoI think they're making a joke
- U4E4 6mo agoA thing is its relationships. (Yoneda lemma.) Keep track of how an object connects to everything else, and you’ve recovered the object itself, up to isomorphism. It’s why mathematicians study things by probing them: a group by its actions, a space by the maps into it, a scheme in algebraic geometry defined as the rule for what maps into it look like. (You do need the full pattern of connections, not just a list — two different rings can have the same modules, for instance.) [0] 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 https://en.wikipedia.org/wiki/Yoneda_lemma [1] https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon... [2] https://en.wikipedia.org/wiki/Stone_duality https://en.wikipedia.org/wiki/Stone_duality
- deleted 6mo ago[deleted]
- wallhz 6mo ago[dead]
- brador 6mo agoWe should call it “relationship lemma”. That way its function is contained within its name. And would not require the definition step every time. We should strive to name all things by their function not by their inventor or discoverer IMO. But people like their ribbons.
- throw567643u8 6mo agoJust Yoneda Lemma. In fact it feels like the theory just restates Yoneda Lemma over and over in different ways.
- deleted 6mo ago[deleted]
- IsTom 6mo agoI think that CT is more akin to just a different language for mathematics than a solid set of axioms from which you can prove things. The most fact-y proof I've personally seen was that you can't extend the usual definition of functions in set theory to work with parametric polymorphism (not that just some constructions won't work, but that there isn't one at all).
- renticulous 6mo agohttps://en.wikipedia.org/wiki/Abstract_nonsense https://en.wikipedia.org/wiki/Abstract_nonsense https://math.stackexchange.com/questions/823289/abstract-nonsense-proof 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.
- tug2024 6mo ago[dead]
- Chinjut 6mo agoWell, group theory is a special case of category theory. A group is a one object category where all morphisms are invertible. You do group theory long enough and it leads you to start thinking about groupoids and monoids and categories more generally as well.
- pfortuny 6mo agoOne of the most striking things is that cartesian products of objects do not correspond to set-cartesian products. This to me was mind-blowing when studying schemes.
- nagaiaida 6mo agowell, this is more applied and less straightforwardly categorical, but thinking along the lines of solely looking at compositional structure rather than all the properties of functions we usually take as semantic bedrock in functional programming (namely referential transparency) is how you start doing neat arrowized tricks like tracking state in the middle of a big hitherto-functional pipeline (for instance automata, functions which return a new state/function alongside a value, can be neatly woven into pipelines composed via arrow composition in a way they can't be in a pipeline composed via function composition)
- gobdovan 6mo agoYou're more right than you'd think. The whole point of mathematics is precise thinking, yet the article is very inaccurate. 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 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.
- throw5 6mo ago> Nobody seems to care or notice. I'm watching in disbelief how nobody is pointing out the article is full of inaccuracies. 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.
- JPC21 6mo agoYou say pretty obvious, but it took me 2 years during my PhD to be consciously aware of this. And once I did, I immediately knew I wanted to leave my field as soon as I would finish.
- goostavos 6mo ago>so distant from daily routine that it seems completely pointless 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]"
- deleted 6mo ago[deleted]
- gobdovan 6mo agoUnless 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.
- bubblyworld 6mo agoI don't think they are completely wrong - "=>" is just implication. A hidden assumption in their diagrams is that circles of different colours are assumed to be different elements. 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).
- gobdovan 6mo agoIf this is meant to be an explainer, that can't be simply implicit. The text actually seems full of imprecise claims, such as: "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".
- bubblyworld 6mo agoI mean, it's a blog post, those statements are correct in spirit. A taste thing, I think. I agree about the birkhoff theorem though.
- mrkeen 6mo agoIt really isn't a long enough section to get lost in. 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 = y
- somewhereoutth 6mo agoThe first 90% of this is standard set theory. I'm unclear what the last 10% of 'category theory' gives us.
- gobdovan 6mo agoIf 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 https://news.ycombinator.com/item?id=47814213
- zaphar 6mo agoWhy assume it is javascript? The article doesn't indicate the language anywhere that I can see.
- gobdovan 6mo agoOk, 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.
- gopiandcode 6mo ago> 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.html 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.
- adaptit 6mo agoThis resource is a really clear breakdown of order relations; visualizing the structure like this makes the abstract concepts much more digestible
- scotty79 6mo agoI 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.
- seanhunter 6mo agoIf 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. [1] https://arxiv.org/pdf/1612.09375 https://arxiv.org/pdf/1612.09375
- gobdovan 6mo agoDisclaimer 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.
- senderista 6mo ago_Conceptual Mathematics_ is basically category theory for high school students. https://www.amazon.com/Conceptual-Mathematics-First-Introduction-Categories/dp/052171916X https://www.amazon.com/Conceptual-Mathematics-First-Introduc...
- seanhunter 6mo agoThat looks fantastic actually. Thanks very much for the recommendation.
- ashCrafts62 6mo agobinary 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.
- theQuietCliff89 6mo ago[dead]
- eli_dove02 6mo ago[dead]
- throw567643u8 6mo agoThe author's writing style and overuse of parentheses is excruciating. True parenthetic material is rare, good technical writers use them sparely.
- postit 6mo agoI can read a person’s ADHD level by their parentheses usage. Unless they are lisp programmers.
- deleted 6mo ago[deleted]
- kmstout 6mo agoI see parenthetical expressions overused all over the internet, especially in HN comments. (Don't worry, I do it sometimes, too.) A browser extension to collapse or strike through parenthetical text nested beyond a configurable level might be handy.
- ynac 6mo agoI 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?
- susam 6mo ago> 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 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 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.
- cubefox 6mo agoThis 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.
- ralphc 6mo agoI'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?
- beingforthebene 6mo agoThere is a typo in part 2 of your definition of Join. `P` is supposed to be >= `A` and `B`. There are also numerous grammatical and spelling errors