Category Theory: Orders(boris-marinov.github.io)
boris-marinov.github.io
Category Theory: Orders
https://boris-marinov.github.io/category-theory-illustrated/04_order/
54 comments
And if you’re an engineer this idea from relativity can be applied in distributed systems theory as well! See Leslie Lamport’s famous paper Time, Clocks, and the Ordering of Events in a Distributed System (1978)[0].
I believe Lamport wrote a book on General Relativity before getting into computer science, so the connection runs deep.
[0] https://lamport.azurewebsites.net/pubs/time-clocks.pdf
I believe Lamport wrote a book on General Relativity before getting into computer science, so the connection runs deep.
[0] https://lamport.azurewebsites.net/pubs/time-clocks.pdf
Cool. Distributed and asynchronous programming made me think of non-locality a lot, just looking at the clock isn't good enough to determine a sequence of events.
If anyone is interested in digging into this more, there's an absolutely fantastic Leslie Lamport paper related to clocks and ordering of events: https://lamport.azurewebsites.net/pubs/time-clocks.pdf
> But for two events that are separated by a distance than light can't travel in the time by which they are separated
As written, this sounds circular to me. How do the know how far apart in time the two events are?
As written, this sounds circular to me. How do the know how far apart in time the two events are?
That's a good question. The answer is that the time between the two events will vary for different observers, however the property that light can't travel fast enough between the events is invariant and can be agreed upon by all observers.
It's somewhat important that this property remains invariant, simply because all observers should be able to agree whether a flash produced at one point in spacetime is visible at another point in spacetime.
It's somewhat important that this property remains invariant, simply because all observers should be able to agree whether a flash produced at one point in spacetime is visible at another point in spacetime.
How does this work, if you can spare a hand-wavy explanation? If the perceived time between events varies by observer, and if for every observer there is a precise threshold at which events become casually disjoint, naively I would imagine there to always be disagreement.
Just as there is a difference in perceived time there's also a difference in perceived distance. As it turns out these cancel out in a way that ensures the speed of light is the same for all observers. Together with the axiom that everyone agrees whether something travels in a straight line you can figure out most of special relativity.
It's somewhat hard to explain why this works without handwaving or just pointing to the maths, but the youtube channel minute physics at least has some good visualizations: https://www.youtube.com/watch?v=Rh0pYtQG5wI
It's somewhat hard to explain why this works without handwaving or just pointing to the maths, but the youtube channel minute physics at least has some good visualizations: https://www.youtube.com/watch?v=Rh0pYtQG5wI
Thanks!
The separate space and time interval measurements between two events can vary among observers, but they will all measure the same spacetime interval, which in turn determines whether light is "fast enough".
How's this work with multiple paths between things? Like in special relativity, it's all uniquely defined, but how's it work in GR? Shortest spacetime path?
In short, yes.
To expand on that a bit, this shortest path is known as a geodesic and one of the more important axioms of general relativity is that all laws of physics are preserved locally when traveling along a geodesic. In particular all such observers should measure the same speed of light, since it's a simple property of electrodynamics. Interestingly they won't measure the same CMB, showing that the local part is important.
To expand on that a bit, this shortest path is known as a geodesic and one of the more important axioms of general relativity is that all laws of physics are preserved locally when traveling along a geodesic. In particular all such observers should measure the same speed of light, since it's a simple property of electrodynamics. Interestingly they won't measure the same CMB, showing that the local part is important.
That's neat, thanks. When you say it's an axiom that it's all preserved locally, does that mean that all the laws only state local properties (i.e. it's all just differential equations over spacetime)?
If so, is that why stuff like QM has trouble, where something like entangled things at a distance might be hard to express locally, or is it actually easy to transform spooky stuff into a local statement and QM issues are something else entirely?
If so, is that why stuff like QM has trouble, where something like entangled things at a distance might be hard to express locally, or is it actually easy to transform spooky stuff into a local statement and QM issues are something else entirely?
It's a bit too simple to say that that's the problem, it's not that general relativity can't deal with global features of reality, those will simply not look the same to all observers. The reason I mentioned CMB is that space necessarily seems to have a preferred speed (even with general relativity you can't have a distribution of speeds that looks the same from all frames of references), and measuring the blueshift in CMB allows you to measure an absolute speed in some sense (it might still be local to our part of the universe, but that includes pretty much everything we can interact with).
The obstacle to combining general relativity and quantum mechanics is, in short, that general relativity is a classical theory of physics (e.g. exact positions, energy, momentum and all that), whereas quantum mechanics expands classical mechanics to get quantum mechanical laws of physics. Now for whatever reason the techniques we used to turn electromagnetism etc. quantum mechanical fail to work on the (classical) theory of general relativity.
And IMHO that's about as far as we've gotten, a lot of work's gone into it but it's honestly hard to tell if we've gotten a better grasp on why general relativity refuses to 'quantize'. Personally I blame the fact that the mathematical foundations of quantum mechanics aren't strong enough to support a quantum mechanical description of geometry itself, but I may not be the most qualified person to judge this.
The obstacle to combining general relativity and quantum mechanics is, in short, that general relativity is a classical theory of physics (e.g. exact positions, energy, momentum and all that), whereas quantum mechanics expands classical mechanics to get quantum mechanical laws of physics. Now for whatever reason the techniques we used to turn electromagnetism etc. quantum mechanical fail to work on the (classical) theory of general relativity.
And IMHO that's about as far as we've gotten, a lot of work's gone into it but it's honestly hard to tell if we've gotten a better grasp on why general relativity refuses to 'quantize'. Personally I blame the fact that the mathematical foundations of quantum mechanics aren't strong enough to support a quantum mechanical description of geometry itself, but I may not be the most qualified person to judge this.
[deleted]
Is there a somewhat longer (maybe illustrated) example of this principle somewhere? You've captured my interest and I want to read more
The links provided are nice but I will leave a comment here in case it is useful.
If I measure the temporal (dt) and spatial (dx) distance between two events A and B, then I can calculate what another observer would measure (dt' and dx') using the so-called Lorentz transformation, provided that I know his velocity relatively to me (v). The Lorentz transformation is a linear operator, written down as a matrix.
Now, the spacetime interval (ds) between A and B, is computed with the formula ds^2 = dx^2 - c^2 dt^2. The interesting property here is that the Lorentz transformation leaves ds^2 unchanged, i.e. dx^2 - c^2 dt^2 = dx'^2 - c^2 dt'^2. So, it also does not change the sign of ds^2, which determines whether light is fast enough to travel a distance dx within time dt.
The animation in the Wikipedia link by alephu5 shows the Lorentz transformation in action for a smoothly varying value of relative velocity. The events A B C are all separated by positive ('spacelike', light not fast enough) intervals, which graphically means that the line connecting them has a slope of less than 45 degrees in that graph, and the Lorentz transformation can tilt that line both ways and change the ordering of the events in the t axis. If two of these events on that graph were separated by a negative ('timelike') interval, the line connecting them would have a slope larger than 45 degrees and the Lorentz transformation could not alter their relative ordering in the t axis, meaning that all observers would agree on the ordering.
If I measure the temporal (dt) and spatial (dx) distance between two events A and B, then I can calculate what another observer would measure (dt' and dx') using the so-called Lorentz transformation, provided that I know his velocity relatively to me (v). The Lorentz transformation is a linear operator, written down as a matrix.
Now, the spacetime interval (ds) between A and B, is computed with the formula ds^2 = dx^2 - c^2 dt^2. The interesting property here is that the Lorentz transformation leaves ds^2 unchanged, i.e. dx^2 - c^2 dt^2 = dx'^2 - c^2 dt'^2. So, it also does not change the sign of ds^2, which determines whether light is fast enough to travel a distance dx within time dt.
The animation in the Wikipedia link by alephu5 shows the Lorentz transformation in action for a smoothly varying value of relative velocity. The events A B C are all separated by positive ('spacelike', light not fast enough) intervals, which graphically means that the line connecting them has a slope of less than 45 degrees in that graph, and the Lorentz transformation can tilt that line both ways and change the ordering of the events in the t axis. If two of these events on that graph were separated by a negative ('timelike') interval, the line connecting them would have a slope larger than 45 degrees and the Lorentz transformation could not alter their relative ordering in the t axis, meaning that all observers would agree on the ordering.
Light cones helped me understand causality from a slightly different perspective:
https://en.wikipedia.org/wiki/Light_cone
https://www.youtube.com/watch?v=OZv3ycr6Jxg
https://en.wikipedia.org/wiki/Light_cone
https://www.youtube.com/watch?v=OZv3ycr6Jxg
maybe this one? https://en.wikipedia.org/wiki/Ladder_paradox
depending on where you stand, the ladder can fit in the garage, or it can't. If I remember right, it's from the original special relativity paper, which is super accessible. General was always beyond me, but special is just high school math.
If you’re curious about this stuff and don’t know where to begin, the first chapter of Fong & Spivak, “An Invitation to Applied Category Theory: Seven Sketches in Compositionality” [1] also introduces category-theoretic ideas using partial orders.
Edit: After the Fong & Spivak book, the book by Emily Riehl, "Category Theory in Context" is an excellent next step, although it requires some mathematical maturity.
[1]: https://arxiv.org/abs/1803.05316
Edit: After the Fong & Spivak book, the book by Emily Riehl, "Category Theory in Context" is an excellent next step, although it requires some mathematical maturity.
[1]: https://arxiv.org/abs/1803.05316
A few years ago I took a printout of Fong & Spivak with me on vacation to Greece. I really enjoyed the first few chapters---and my wife got to make fun of my leisure reading choices. :-) I wish they sold a bound copy, because at home among so many other things to read, it's tough to remember to pick up that stack of papers.
EDIT: I take it back, you can buy it now!: https://www.amazon.com/Invitation-Applied-Category-Theory-Co...
EDIT: I take it back, you can buy it now!: https://www.amazon.com/Invitation-Applied-Category-Theory-Co...
I highly recommend looking through this for anyone curious. I thought the section on databases was especially interesting. Many database operations (join, schema change, etc) fit very neatly into category theory language.
I agree, the database angle is fascinating! There's an interesting CSTheory.SE answer here [1] with some pointers to further reading, written by one of the creators of the Datafun [2] query language.
[1] https://cstheory.stackexchange.com/questions/38221/is-there-... [2] http://www.rntz.net/datafun/
[1] https://cstheory.stackexchange.com/questions/38221/is-there-... [2] http://www.rntz.net/datafun/
Category Theory in Context is such a great book. Kudos to Dover’s Aurora publishing arm for a great, original book at such a great price. Always love dover and adding additional new contents to the back catalogue of reprints is amazing.
The book does constantly reference other branches of mathematics (algebra, topology, etc) for example. Probably not strictly necessary to have that background to follow the book, but helpful.
The book does constantly reference other branches of mathematics (algebra, topology, etc) for example. Probably not strictly necessary to have that background to follow the book, but helpful.
For non-mathematicians (although some post-secondary maths is probably required), I'd also recommend Spivak's "Category Theory for the Sciences" (MIT Press, 2014) and Milewski's "Category Theory for Programmers" (available online at https://bartoszmilewski.com/2014/10/28/category-theory-for-p...). I liked it enough to buy the hardcover.
The definition of antisymmetric relations is an unusual one. As given, it's incompatible with the definition of reflexivity (presumably there's an implicit assumption on `a ≠ b`).
The usual definition is `x ≤ y AND y ≤ x → x = y`.
The usual definition is `x ≤ y AND y ≤ x → x = y`.
Yeah. That's unfortunate. The discussion on totality makes clear that it subsumes reflexivity when a = b.
The diagram, which indicates implication, is also not consistent with the logical statement, which indicates iff.
The diagram, which indicates implication, is also not consistent with the logical statement, which indicates iff.
There is also a mistake in the discussion of totality and reflexivity.
By the way, this law makes the reflexivity law redundant, as it is just a special case of reflexivity when a and b are one and the same object, but I still want to present it for reasons that will become apparent soon.
This should be as follows.
[...] a special case of totality when a and b are one and the same [...]
By the way, this law makes the reflexivity law redundant, as it is just a special case of reflexivity when a and b are one and the same object, but I still want to present it for reasons that will become apparent soon.
This should be as follows.
[...] a special case of totality when a and b are one and the same [...]
Is there also a mistake in the discussion of joins? At the start, it says:
> The least upper bound of two elements that are connected as part of an order is called the join of these elements...
but then at the end of that section it says
> Like with the maximum element, if two elements have several upper bounds that are equally big, then none of them is a join (a join must be unique). If, however, one of those elements is established as bigger than another, it immediately qualifies.
If the join is the least-upper-bound, shouldn't the final sentence read "...is established as smaller than another"? Or, I guess, the "it" could be referring to "another" rather than "one of". Maybe it's simply unclear rather than incorrect.
> The least upper bound of two elements that are connected as part of an order is called the join of these elements...
but then at the end of that section it says
> Like with the maximum element, if two elements have several upper bounds that are equally big, then none of them is a join (a join must be unique). If, however, one of those elements is established as bigger than another, it immediately qualifies.
If the join is the least-upper-bound, shouldn't the final sentence read "...is established as smaller than another"? Or, I guess, the "it" could be referring to "another" rather than "one of". Maybe it's simply unclear rather than incorrect.
Yeah, antisymmetry would be correct if the order was strict, which the article does mention but only in passing.
Thanks everyone for pointing that and other problems, just made some corrections.
Yes, the property defined on the page is more commonly called asymmetry.
> by the way, most infinite orders are isomorphic to the natural numbers as well, with the exception of the ones for which Cantor’s diagonal argument applies
There are at least two things wrong with this statement.
First, "the ones for which Cantor’s diagonal argument applies" is a bit vague. I assume it's supposed to be a reference to uncountable sets, but as written, it's (probably) referring to the general version of the argument that shows that the powerset of a set is strictly larger than the set itself. Thus, a set "for which Cantor's diagonal argument" applies is a powerset.
But not all uncountable sets (or even all uncountable total orders) are powersets. For example, any strong limit cardinal[0] can't be a powerset. Obviously, no uncountable total order can be isomorphic to a subset of the natural numbers. You can then well-order that strong limit cardinal to get a total order which isn't a powerset and isn't isomorphic to a subset of the natural numbers.
Second, even countable total orders are much more varied than subsets of the natural numbers. For example, the integers form a total order which can't be isomorphic to a subset of the naturals. The integers are unbounded below, but any subset of the naturals is bounded below (by 0, e.g.).
As another counterexample, the set of rational numbers in [0, 1] forms a total order which is dense: between any distinct elements of the total order, there's another distinct element between them.
You can get a nice theorem along these lines, though. Every countable total order is isomorphic to a subset of the rational numbers. [1]
Of course, the word "most" here is ambiguous, but seeing as there are uncountably many non-isomorphic, countable, total orders (for example, the number of countable ordinals is uncountable), but only countably many non-isomorphic subsets of the naturals, I think it's inappropriate.
[0] https://en.wikipedia.org/wiki/Limit_cardinal [1] https://www.whitman.edu/mathematics/higher_math_online/secti...
There are at least two things wrong with this statement.
First, "the ones for which Cantor’s diagonal argument applies" is a bit vague. I assume it's supposed to be a reference to uncountable sets, but as written, it's (probably) referring to the general version of the argument that shows that the powerset of a set is strictly larger than the set itself. Thus, a set "for which Cantor's diagonal argument" applies is a powerset.
But not all uncountable sets (or even all uncountable total orders) are powersets. For example, any strong limit cardinal[0] can't be a powerset. Obviously, no uncountable total order can be isomorphic to a subset of the natural numbers. You can then well-order that strong limit cardinal to get a total order which isn't a powerset and isn't isomorphic to a subset of the natural numbers.
Second, even countable total orders are much more varied than subsets of the natural numbers. For example, the integers form a total order which can't be isomorphic to a subset of the naturals. The integers are unbounded below, but any subset of the naturals is bounded below (by 0, e.g.).
As another counterexample, the set of rational numbers in [0, 1] forms a total order which is dense: between any distinct elements of the total order, there's another distinct element between them.
You can get a nice theorem along these lines, though. Every countable total order is isomorphic to a subset of the rational numbers. [1]
Of course, the word "most" here is ambiguous, but seeing as there are uncountably many non-isomorphic, countable, total orders (for example, the number of countable ordinals is uncountable), but only countably many non-isomorphic subsets of the naturals, I think it's inappropriate.
[0] https://en.wikipedia.org/wiki/Limit_cardinal [1] https://www.whitman.edu/mathematics/higher_math_online/secti...
Thanks for this treatment. The truth is that I wanted to write a full section on this, but I didn't have the time, so I decided to only mark it. I will probably remove the reference, as currently it would not add anything for people who are not already familiar with the result.
I've tried getting into Category Theory many times over the past few years and the only thing that actually worked is Category theory for Programmers by Bartosz Milewski (lectures[1], book[2])
1. https://www.youtube.com/playlist?list=PLbgaMIhjbmEnaH_LTkxLI...
2. https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
1. https://www.youtube.com/playlist?list=PLbgaMIhjbmEnaH_LTkxLI...
2. https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
[deleted]
Thanks for these links! God bless you
Order theory has its own life outside of category theory (and predates category theory by many decades). It often gets lumped into lattice theory, though you also have lots of handy things like semilattices, partial orders, and chain-complete partial orders.
I have gotten far more use out of lattice and order theory than I have out of category theory during my career, but that may be "I have a hammer, so..." bias.
I have gotten far more use out of lattice and order theory than I have out of category theory during my career, but that may be "I have a hammer, so..." bias.
> I have gotten far more use out of lattice and order theory than I have out of category theory during my career
That sounds interesting, can you give some examples?
That sounds interesting, can you give some examples?
Eventual consistency in databases is fully described by "make your merge operation the join of a semilattice." I once watched a whole keynote at Strange Loop which slowly recapitulated that idea over the course of an hour when with lattice theory it's just one obvious sentence.
I haven't written it up, but I used lattices as the starting point for an algebra of genome annotations that I personally found useful. I had to replace one of the two operations with a different one, but guiding it as close to a lattice as possible was a useful heuristic.
The tree of life is usually described as a tree of species. Defining a species is a problem, though, especially for microbes, and there are places where it's not a tree and things hybridize, especially for plants and microbes, so I spent some time trying to define it in terms of individual organisms. I'm still not satisfied with where I had pushed it, but the structure when I had left it took the form of a chain complete partial order.
I haven't written it up, but I used lattices as the starting point for an algebra of genome annotations that I personally found useful. I had to replace one of the two operations with a different one, but guiding it as close to a lattice as possible was a useful heuristic.
The tree of life is usually described as a tree of species. Defining a species is a problem, though, especially for microbes, and there are places where it's not a tree and things hybridize, especially for plants and microbes, so I spent some time trying to define it in terms of individual organisms. I'm still not satisfied with where I had pushed it, but the structure when I had left it took the form of a chain complete partial order.
I keep getting bounced out of the flow by the author describing the relation A<=B as "A is bigger than B". I get that the order relation is arbitrary, but that's just irritating. Perhaps using "precedes" rather than "is bigger" would be helpful. I also don't think the assertion that anti-symmetry excludes equality ("no ties are permitted"). The usual definition of antisymmetry specifically requires equality: a<=b && b<=a -> a==b (i.e. a<=b -> !(b<=a) is a stronger restriction than mere antisymmetry.)
I believe a tie is different from equality.
The reason the above holds is because a and b must both be the same element.
A "tie" in this case assume they are different elements. Ie the author is a different person from his grandmother. If that's the case, then it's false that author == grandmother.
Ie two things can't be "tied" unless they are actually just one thing.
The reason the above holds is because a and b must both be the same element.
A "tie" in this case assume they are different elements. Ie the author is a different person from his grandmother. If that's the case, then it's false that author == grandmother.
Ie two things can't be "tied" unless they are actually just one thing.
Ok. But I still don't agree that the property of antisymmetry implies or requires that restriction.
Ok, how are you defining a tie?
I believe the author is defining a tie as the following:
(a <= b) && (b <= a) && (a != b)
Then a and b are "tied". Where "!=" means a and b are different.
I believe the author is defining a tie as the following:
(a <= b) && (b <= a) && (a != b)
Then a and b are "tied". Where "!=" means a and b are different.
I'm fine with that restriction. But that isn't the axiom of antisymmetry. That's the axiom of antisymmetry plus a rule that holds that equality implies identity (which would be typically described in terms of the axiom of extensionality). My problem is with the implied claim that antisymmetry alone gives you that restriction, which is incorrect. Antisymmetry is entirely consistent with collections that contain equal but distinct elements.
If we agree that the axiom of extensionality applies, then the restriction of no ties is implied. I don't think antisymmetry is necessary or sufficient for it.
Awesome website! Well written and crystal clear.
It's truly a feat to explain simply such a complex topic.
It's truly a feat to explain simply such a complex topic.
Very nice! Since distributed systems are already mentioned itt, I wonder how category theory would map the recently-ish published CALM Theorem [1] which features monotonic ordering as a defining characteristic.
[1]: https://m-cacm.acm.org/magazines/2020/9/246941-keeping-calm/...
[1]: https://m-cacm.acm.org/magazines/2020/9/246941-keeping-calm/...
To anyone looking for a good introductory book, I wholeheartedly recommend Harold Simmon's "An Introduction to Category Theory". The writing is very clear and fun with lots of good examples and exercises.
This website's design immediately reminded me about the children books by Cara Florance and Chris Ferrie [0]:
General Relativity for Babies
Nuclear Physics for Babies
Quantum Computing for Babies
Statistical Physics for Babies
Electromagnetism for Babies
Quantum Information for Babies
Bayesian Probability for Babies
[0] https://shop.sourcebooks.com/for-children/baby-university/
General Relativity for Babies
Nuclear Physics for Babies
Quantum Computing for Babies
Statistical Physics for Babies
Electromagnetism for Babies
Quantum Information for Babies
Bayesian Probability for Babies
[0] https://shop.sourcebooks.com/for-children/baby-university/
My God that site is beautiful. If only every "maths" site could looks like this, I'd have won a field medal!
Could I suggest you limit your use of text in parentheses? Something is either worth saying or it isn't. Truly parenthetic material should be quite rare.
Interesting take, but I am not sure I agree - parentheses are used to denote a thought that is not directly related to the one expressed in the rest of the sentence e.g. additional clarifications. Of which (this being an introductory material) there are a lot.
This fits exactly into the partial ordering system.