Hacker News new | past | comments | ask | show | jobs | submit | lgdw's comments login

Having a hard time following the lower bound proof, especially this part:

> By the definition of π‘ƒπ‘Ž , we know there are at least as many programs in π‘ƒπ‘Ž as there are artefacts in πœ‹ (𝐺), i.e. |π‘π‘Ž | β‰₯ #πœ‹ (𝐺).

I'm not sure how the definition of P_a leads to |p_a| >= #\pi(G)...


When they say P_a, they must mean all the minimal programs for every artifact generated by G. It’s like the union of p_a over all the artifacts.

P_a definitely can’t be all the maximally compressed programs for specific a. There’s at most 2^|p_a| of them and if G were the identity function on m length binary strings where m>|p_a|..


fifth one down.


I remember this being in a NACLO problem last year.


I'm not very familiar with physics, but if I recall correctly the electromagnetic force can be thought of as a Hopf fibration.


iirc it is just a mirror of libgen.


Great textbook, I learned all the topology I know from it. Previously, Category Theory was taught as a field that connects branches of math, and thus in terms of other concepts. But recently there's a movement to view Category Theory as the definitive underlying field of math (instead of set theory), and teach different fields of math in terms of Category Theory rather than vice versa (a new-new math in a sense). I learned Category Theory well before learning abstract algebra and topology, and the embedding of Topology in Category Theory was seamless and intuitive; I feel as though this book proves that this new CT-centric view of math education has merit.

One of the authors, Tai-Danae Bradley, also runs math3ma [1] and is a prominent figure in Applied Category Theory. I had the pleasure of hearing her talk, and her way of explaining abstractions is very easy to understand despite Category Theory being fairly obtuse at times (looking at you, Mac Lane!)

Also, an obligatory shilling of the Topos Institute [2]. They're a research institution based in Berkeley, and they have weekly talks on Category Theory that they release on youtube. If you're interested in the categorification of mathematics, you need to check them out.

[1] https://www.math3ma.com/

[2] https://topos.site/


> But recently there's a movement to view Category Theory as the definitive underlying field of math

Spoken like a true algebraist.

For anything related to stats, PDEs, and optimization (basically that subset if mathematics that is most useful to other sciences), category theory is a horrible foundation.

While it seems you can recover (with a looot of work) some existing theory, no sane researcher in these fields uses category theory.

And there is also no motivation to do so, since unlike for algebraic topology, algebra etc. the categorical viewpoint doesn't really make it clearer, what, e.g., the weak solution to a PDEs is, and why it coincidences (or not) with the classical solution.


> For anything related to stats, PDEs, and optimization (basically that subset if mathematics that is most useful to other sciences), category theory is a horrible foundation.

For analysis, Peter Scholze and Dustin Clausen would disagree:

> https://en.wikipedia.org/wiki/Condensed_mathematics

To quote from https://www.math.uni-bonn.de/people/scholze/Analytic.pdf linked there:

"Mumford writes in Curves and their Jacobians: β€œ[Algebraic geometry] seems to have acquired the reputation of being esoteric, exclusive, and very abstract, with adherents who are secretly plotting to take over all the rest of mathematics. In one respect this last point is accurate.”

For some reason, this secret plot has so far stopped short of taking over analysis. The goal of this course is to launch a new attack, turning functional analysis into a branch of commutative algebra, and various types of analytic geometry (like manifolds) into algebraic geometry. Whether this will make these subjects equally esoteric will be left to the reader’s judgement.

[...]

The author always had the impression that the highly categorical techniques of algebraic geometry could not possibly be applied in analytic situations; and certainly not over the real numbers. The goal of this course is to correct this impression."


I think OP is really overstating things. "the definitive underlying field of math replacing set theory" is something Lawvere was trying in the 60s and it never really took off.

Category theory isn't really a replacement for set theory any more than order theory is a replacement for set theory. What is important is not what your "foundational system" is, but that just like there are many concepts we learn in the context of set theory but are just very generally useful (equivalence classes, cardinality, injective/surjective functions), there are also similarly very useful concepts in category theory like adjoint functors, limits and universal mapping properties.


> Great textbook, I learned all the topology I know from it.

The kind of topology this book focuses on is what I learned as "point-set topology". I guess the parent considers topology to not contain algebraic topology, since they go on to say they know more than this book contains.

You could turn this statement around - what if you learned all of the category theory you knew out of this book? Maybe someone can comment.

The start of the book and their take on point-set topology seems reasonable. I saw all of the familiar theorems without any eye-popping machinery being used. I was very happy to see some technically important items in the book (the compact-open topology, and the corresponding topology on Hom).

I would be very interested in a semi-experienced reader's take on Chapter 5. [1] If you don't already know category theory, is this a reasonable introduction? (Is the on ramp ever smooth?)

I can't vouch for what kind of intro to (point-set) topology the book gives, but I can certainly say that I would prefer this book over MacLane's "Categories for the Working Mathematician" as an introduction to category theory, for what it's worth.

[1] https://assets.pubpub.org/6d1dqgg9/51597355090422.pdf


Yes, this textbook is a great introduction to point-set topology. I'm not very familiar with algebraic topology so I can't comment on anything regarding that. I did learn a fair bit of category theory that I didn't know prior, like a formal explanation of deriving the Yoneda Lemma (I read this book before I read CWM). I think it's definitely possible to learn category theory from this book, especially if you already have a strong intuition for Topology.


What does it mean, that it's replacing set theory? Is it more fundamental than set theory, in the sense that the latter can be defined in terms of it? Or is it different from set theory entirely, meaning different math comes from each?


I never understood this either...

Category theory works with collections, which can be modeled as sets -- or if you want to deal with categories of sets and other "large" categories -- as proper classes. And you can use a set theory that incorporates classes, like Morse-Kelley, to model this. IOW, it seems like category theory can be modeled in set theory.

On the other hand, I've not seen a rigorous set of axioms for category theory that didn't presuppose a notion of set or category or "collection".

Set theory also sheds a lot of light on what feel like foundational issues: sizes of sets, independence of axioms, etc.; I haven't seen something similar out of category theory.

Love for a category theory partisan to chime in with more here -- I'm definitely not an expert.


> On the other hand, I've not seen a rigorous set of axioms for category theory that didn't presuppose a notion of set or category or "collection".

I'm no expert, but I do want to point out that you'll never see a set of axioms for set theory that doesn't also presuppose some realm from which sets themselves are drawn. The question is not whether sets exist; it's whether the collection of them can be represented within the theory. It is well-known (in certain circles...) that the realm of all sets cannot itself be described by a set.

In the same way, category theory may assume the existence of collections of objects and arrows, but these collections are not themselves represented within category theory. The category of all categories encounters exactly the same size issues as does the set of all sets.

There are different ways around these size issues. I think a lot of people go with something like Russell's stratified hierarchy of universes -- but this is also done in set theory, like with the alternative to ZFC based on sets and classes. (But what is the class of all classes!? You just keep building bigger universes.)


> I'm no expert, but I do want to point out that you'll never see a set of axioms for set theory that doesn't also presuppose some realm from which sets themselves are drawn.

Huh? Of course you do; ZFC itself is such a set of axioms. There's no particular requirement on objects that can be members of sets (at least, nothing really goes wrong if they're not all sets), so the theory doesn't depend on anything else, in a very intuitive sense.


To get a little bit technical, the axioms of ZFC, as a "first-order theory", make use of universal and existential quantifiers. These quantifiers have to quantify over some universe, whose constituents we call "sets". Take the axiom of the empty set as an example:

    exists x. forall y. y not in x
The meaning of the "exists" quantifier is that it runs over the universe of entities; the formula it quantifies over must be true when instantiated on at least one such entity. The meaning of the "forall" quantifier is similar, except it must be true for every such instantiation. Notably, since the universe of all sets is not a set on pain of paradox, the universe itself cannot be a set. It is a primitive "sort", part of the logical signature of the theory.

These quantifiers only "work" when there's a universe of entities to run over. This universe is not internal to set theory as an axiomatic system; the whole point of "non-standard models" is that we're looking for universes where the axioms of set theory hold, and yet are not what we normally think of when we reason using those axioms (e.g. "large cardinal" models).

Category theory can also be framed as a first-order theory. In its most common incarnation, it's a two-sorted first-order theory, with separate universes for objects and for arrows. This isn't essential; we can actually dispense with objects and work only with arrows. (Objects are then encoded as their identity arrows.) But it's a first-order theory either way; all the axioms of a category can be given with quantified formulas.

Group theory is also a first-order theory. When you specify a particular group, you give the universe over which its axioms quantify, and then prove(!) that those axioms hold on that universe. If you interpret group theory internal to set theory, then your universe will be a set; but the axioms don't care as long as quantification can be interpreted appropriately.


The idea that you can do category theory over any kind of thing as an arrow may be true as a matter of formal mathematical logic, but it's very much not intuitive in the way that it is for sets. If we wanted to work with tables, chairs, and beer mugs, it's very natural and easy to think about forming sets of beer mugs - a beer mug might either be a member of a set, or not, and this doesn't seem to require anything of it. For a group you need a binary operation and inverses, so this feels a bit more complex and abstract than a set (indeed the way I was taught, a group is a set plus some additional structure), but it's still fairly direct and understandable what kind of things satisfy the group axioms (if I had some rule for merging two beer mugs, and some kind of inverse - obviously this is unphysical, but it's at least imagineable). Whereas for a category it's just impossible to get started - should my beer mugs be objects or arrows? Presumably objects (since beer mugs are objects in the conventional sense), but then what are the arrows?


> Presumably objects (since beer mugs are objects in the conventional sense), but then what are the arrows?

This is definitely one of the most unintuitive parts of early category theory. The "objects" are not automatically the things you're studying; often they're best modeled as the arrows. It took me a really long time to internalize that.

Put it this way: the arrows are the actually interesting things, from a categorical perspective. The objects literally only exist to tell you which arrows you can fit together. The objects don't contain any other information. We often say that sets are objects, or topological spaces are objects, but that's only because we're studying functions or homeomorphisms, and if we want to chain those together, we need to make sure that one ends where the other begins or else the composition isn't well-defined.

No, we don't expect everything to be modeled directly as a category. That's not how the abstraction pays for itself.


What kind of relationships between beer mugs are you interested in? "can contain more beer than"? "is both at least as deep and at least as wide"?

What about beer mugs are you trying to model?


I'm not trying to model anything about beer mugs. I'm trying to construct some nontrivial, intuitively understandable categories to play around with.


I like to take example categories from order theory, like with lattices and preorders and such. All such orders are also categories; the objects are the elements of the order, and the arrows are the relationships. However, if x <= y in the order, then there's only one arrow x -> y -- the order doesn't distinguish the different ways two objects can be related, only the mere fact that they are. (This is the difference between an order and a category: categories do allow us to distinguish the multiple ways two things can be related.)

Lots of category theory has direct analogues in order theory. Functors are monotone functions, for instance; monads are closure operators; and presheafs are lower sets. But since there's at most one arrow between any two objects, you don't have to worry about all the coherence conditions you end up seeing in category theory. Their whole purpose is to make sure that you pick "the right" arrow in various circumstances; but when there's only one arrow, it is trivially the right one.


I think this is an interesting topic worth discussing, but also I don't think it's related to your post I replied to, which claimed that ZFC doesn't presuppose any more primitive kind of collection.

> sets of beer mugs

Set theory doesn't admit anything other than sets. Based on the way you're describing things, you'll need to encode each mug as a set, just as we encode numbers themselves as sets. But that's rather unnatural, and mathematicians generally go about their business without worrying about such encodings. They work with the axioms of their setting instead, comforted merely that they could find a model of their constructions in set theory if they really cared to carry out the encodings required.

Confusingly, the "group" and "set" in "group theory" and "set theory" are referring to different parts of the theory. Group theory posits a universe with entities called elements, which when used in certain ways do nice things. Set theory posits a universe with entities called sets, which when used in certain ways do nice things. In one, a "group" is the universe; in the other, a "set" is a constituent of the universe.

If you wanted your mugs to be a model of set theory, the same way we say that something is a group (is a model of group theory), you'd need to somehow prove that your collection of mugs satisfies the ZFC axioms. I don't think "is this mug an element of that mug" is the kind of question you're hoping to model, so your mugs are probably not a model of set theory.

Your mugs might be a model of the theory of preorders, if you deign to order them by their fluid capacity.

> Whereas for a category it's just impossible to get started - should my beer mugs be objects or arrows?

It sounds like what you want is some kind of "mug theory", and the sibling comment has it right in asking what you want to model about mugs. The common thread with all of these theories is that you state first-order axioms, and then work with those axioms freely ignorant of whatever choice of model somebody might come along with that satisfies those axioms.

This is really no different than what we do in something like Java. We define interfaces (theories) capturing the things we want to be able to do with objects, and worry later about what implementations (models) actually meet the requirements. If you want to work with mugs in Java, what are you going to do but define a new type with the operations you need?

There's no reason to expect that some other interface is going to just happen to meet your needs. Not even set theory; not even category theory.


Well, I guess what I'm technically doing is building a non-standard model of set theory in which my beer mugs are some kind of inaccessible sets that are not members of each other. And yes, that doesn't let me study the mugs themselves in any useful way, since I'm not interested in which mugs are members of which other mugs - but it does let me play around with sets of beer mugs and get comfortable with set theory. And it makes it feel like a simple theory if the entities it studies are just opaque "things".


> The meaning of the "exists" quantifier is that it runs over the universe of entities; the formula it quantifies over must be true when instantiated on at least one such entity.

This much is true when we start assigning semantics to formulas - which is what leads to model theory, where you assume that a mathematical universe already exists and you're trying to figure out which sets of formulas describe which parts of it (to oversimplify).

If you look at the ZFC axioms purely syntactically, there aren't many presuppositions. Essentially we only posit that we should be able to coherently reason about finite sequences of strings - because a first-order proof is nothing more than that. That seems easy enough to believe. And it's what allows us to write proofs with computers.


> On the other hand, I've not seen a rigorous set of axioms for category theory that didn't presuppose a notion of set or category or "collection".

I never worked through the details, and I'm not a category theory partisan, but I think that's what this is: https://ncatlab.org/nlab/show/fully%20formal%20ETCS


Yes, this is essentially what I'm getting at in my cousin comment -- although the nlab is typically rather impenetrable to non-specialists.


Category theory might be easier to think about as a different way to think about the same objects we've always studied in mathematics. Since it's a formal theory (just like set theory), we can also study category theory mathematically. In fact, we can study set theory categorically and we can study categories set-theoretically -- they aren't really at odds with each other.

If you wanted to study set theory from a categorical perspective, you would likely be interested in topos theory, which captures essential properties of set theory and generalizes them to a variety of interesting settings. There's also a really good (and IMHO approachable) paper by Tom Leinster [1] on how to see set theory from a categorical perspective, without going all the way out to toposes. I think it's a good way to understand what category theorists try to emphasize.

If you wanted to study categories from a set-theoretic perspective, you're in luck -- that's probably the most common approach to learning category theory in the first place! Studying categories with categories is also possible, but you already need to be fairly comfortable with categories in order to model them internally. (Studying set theory with set theory is much the same -- models of ZFC can get wild.)

(You can also learn category theory from first principles, without thinking in terms of sets. This isn't really any different from set theory, either -- set theory is often peoples' first introductions to abstract mathematics at the undergraduate level, so there isn't really much choice in the matter. For my money, though, I think category theory from first principles is a little less weird.)

[1]: https://arxiv.org/abs/1212.6543


Category theory is not replacing set theory. It's also not the case that entirely different math comes from each. Both can be defined in terms of each other to a large degree. It's probably better to think of them complementing each other. You might find the following thread interesting to read: https://mathoverflow.net/questions/360578/category-theory-an...


> there's a movement to view Category Theory as the definitive underlying field of math

Category theory doesn't have much to say about most of analysis.


There's definitely some connections between analysis and category theory though! There are "self-adjoint operators" in analysis and there are "adjoint functors" in category theory, and it is sort of fun to think about the analogy there.


I forgot to add that Algebra Chapter 0 takes a similar (albeit slightly different) approach of teaching Abstract Algebra in terms of Category Theory. I don't have a link right now but I'm sure you can find it on libgen. (I've only read the first few chapters of Algebra Chapter 0 yet, but from what I've heard the rest of the textbook is as good as the first bit.)


"I learned Category Theory well before learning abstract algebra and topology, and the embedding of Topology in Category Theory was seamless and intuitive; I feel as though this book proves that this new CT-centric view of math education has merit."

Could you tell us a bit more about your educational history and motivations for studying these topics in this order?


While I was in highschool I attended a lecture by David Spivak on a whim and was fascinated by the field ever since. Before really discovering Category Theory, I was more interested in low-level computer architecture and design (although I'm not very knowledgeable by any means) so I didn't really encounter Category Theory through the means that most Computer Science people do (FP, Haskell, etc). Once I learned Category Theory I became more interested in other fields of math.


If one was a young or returning adult with interest but little background in mathematics, would you suggest learning category theory first (assuming the adult is interested)? How would you suggest going about doing this as a path?


Although it would depend on what kind of fields of math you are interested in (algebra, analysis, topology, etc), I think that you can't really _go wrong_ per se by learning Category Theory first, even if many of the examples/uses of category theory won't make sense at first. Of course, learning Category Theory first is definitely unorthodox; at least in college, you usually first learn basic algebra (Abstract Algebra, Linear Algebra) along with analysis (Complex Analysis, Real Analysis) and "advanced calculus" (Differential Equations, Multivariable Calculus). Fields like Category Theory usually come after that and are taught mostly in grad school, but at its core learning Category Theory doesn't require knowing a lot of prerequisites so I think in terms of accessibility it resides alongside fields like Linear Algebra or Group Theory. An advantage of learning Category Theory first is that once you have a decent grasp of it, you'd have the mathematical vocabulary to describe concepts learned in different fields; a homotopy is a 2-morphism in the category of topological spaces, for example.

That being said, if you like algebra the most, learn algebra first. If you enjoy topology, learn topology. There really isn't a "right place" to start with mathematics, and as long as you avoid fields of math that build heavily on other fields of math like K-theory or representation theory, you'll have a decent starting background in math. Most fields of math, not just Category Theory, have analogues to other fields (and Category Theory acts only to really formalize this connection), so you can't really go wrong with starting with something like Linear Algebra or Group Theory.


Thanks for the recommendations!

> Great textbook, I learned all the topology I know from it.

Hatcher's Algebraic Topology was that book for me. https://pi.math.cornell.edu/~hatcher/AT/ATpage.html


> the embedding of Topology in Category Theory was seamless and intuitive

It is no surprise that it is a good fit, category theory first emerged out of topology.


Why are you capitalizing "category theory" and not "topology", "algebra", or "math"?


Sorry, force of habit.


It's the actual process of translating everything into boxes and arrows that's the core of ACT.


If anyone is interested in Applied Category Theory, definitely check out the Topos Institute in Berkeley [1]. They do weekly seminars that they post on youtube and a really intriguing blog. I must say that David Spivak is a treasure to hear speak. 7 Sketches in Compositionality [2] was my introduction into Category Theory (written by Spivak and Brendan Fong, another member of Topos), and it really sold the idea of Category Theory as a field that's not just a mathematical meta-language but also a field that can stand on its own. I recommend it over Mac Lane's CWM if you're not a mathematician.

[1] https://topos.site/ [2] https://arxiv.org/abs/1803.05316


The nLab https://ncatlab.org/nlab/show/HomePage is a useful reference for category theory terminology and results.


Agreed on the institute and Spivak. But CWM is, er, for working mathematicians. Leinster's Basic Category Theory, or Awodey Category theory are more unassuming.


Yes, that's why I recommend starting out with 7 Sketches.


Right, my mistake.


Yes, it's this one! Thank you so much.


Very interesting but I think the original thread was at least a month ago.


Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: