[HN Gopher] Category Theory: Orders
___________________________________________________________________
Category Theory: Orders
Author : todsacerdoti
Score : 185 points
Date : 2021-04-01 08:54 UTC (14 hours ago)
(HTM) web link (boris-marinov.github.io)
(TXT) w3m dump (boris-marinov.github.io)
| dwhitney wrote:
| My God that site is beautiful. If only every "maths" site could
| looks like this, I'd have won a field medal!
| scapp wrote:
| > 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...
| madhadron wrote:
| 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.
| layer8 wrote:
| > 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?
| jackhalford wrote:
| An example of a partial order that blew my mind recently are the
| ordering of "events" in special relativity. Two events can be
| ordered in time (i.e A happened before B) if their spacetime
| interval is positive. But for two events that are separated by a
| distance than light can't travel in the time by which they are
| separated, then nobody can give a before/after order to these
| events.
|
| This fits exactly into the partial ordering system.
| captaindiego wrote:
| 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
| libraryofbabel wrote:
| 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
| gugagore wrote:
| > 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?
| contravariant wrote:
| 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.
| walleeee wrote:
| 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.
| contravariant wrote:
| 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
| d_tr wrote:
| 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".
| 6gvONxR4sf7o wrote:
| 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?
| contravariant wrote:
| 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.
| [deleted]
| caminocorner wrote:
| Is there a somewhat longer (maybe illustrated) example of
| this principle somewhere? You've captured my interest and I
| want to read more
| d_tr wrote:
| 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.
| shaunpersad wrote:
| 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
| jfoutz wrote:
| 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.
| alephu5 wrote:
| https://en.m.wikipedia.org/wiki/Relativity_of_simultaneit
| y
| benrbray wrote:
| 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
| pjungwir wrote:
| 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...
| ajarmst wrote:
| 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.
| ABeeSea wrote:
| 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.
| ironSkillet wrote:
| 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.
| benrbray wrote:
| 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/
| linkdd wrote:
| Awesome website! Well written and crystal clear.
|
| It's truly a feat to explain simply such a complex topic.
| douglaswlance wrote:
| 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...
| max_ wrote:
| Thanks for these links! God bless you
| infogulch wrote:
| 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/...
| _e wrote:
| 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/
| ajarmst wrote:
| 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.)
| BoiledCabbage wrote:
| 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.
| ajarmst wrote:
| Ok. But I still don't agree that the property of antisymmetry
| implies or requires that restriction.
| ajarmst wrote:
| 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.
| BoiledCabbage wrote:
| 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.
| ajarmst wrote:
| 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.
| d_tr wrote:
| 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.
| bah_humbug wrote:
| 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`.
| boris_m wrote:
| Thanks everyone for pointing that and other problems, just made
| some corrections.
| Sharlin wrote:
| Yeah, antisymmetry would be correct if the order was _strict_ ,
| which the article does mention but only in passing.
| 13415 wrote:
| Yes, the property defined on the page is more commonly called
| asymmetry.
| gugagore wrote:
| 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.
| danbruc wrote:
| 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 [...]_
| scubbo wrote:
| 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.
___________________________________________________________________
(page generated 2021-04-01 23:02 UTC)