11 ms·

Category Theory Illustrated – Sets

218 points by boris_m 3y ago

MikeTheGreat 3y ago
Disclaimer: I don't know category theory and I only skimmed the linked page :) This looks great - I love the illustrations, and as far as I know the information looks great! I've got it in my Pocket list and am looking forwards to reading it on the bus. A while back there was a "Group Theory Coloring Book" that someone posted here. I was kinda hoping that this link would be another one of those. (Spoiler: it's an illustrated explanation of category theory - which is great! - not a coloring book). Sorry in advance for hijacking this post, but it's kinda, sorta related to ask: Does anyone have a link to 'fun math/STEM-themed coloring books'?
hackandthink 3y ago
>In particular, a set can contain itself. There are many kinds of mathematics, this is an unusual one. "In Zermelo–Fraenkel set theory, the axiom of regularity and axiom of pairing prevent any set from containing itself." https://en.wikipedia.org/wiki/Universal_set https://en.wikipedia.org/wiki/Universal_set
- axblount 3y ago
  This gives rise to Russell's Paradox: Does the set of "all sets that do not contain themselves" contain itself?
  - tikhonj 3y ago
    You can have set theories that allows sets to contain themselves without allowing Russell's Paradox. You can read about non-well-founded set theory[1] if you're curious. [1]: https://en.wikipedia.org/wiki/Non-well-founded_set_theory https://en.wikipedia.org/wiki/Non-well-founded_set_theory
    - hackandthink 3y ago
      I like the diagram of "the set containing itself". It illustrates non-well-foundedness niceley.
      - l33t7332273 3y ago
        Which diagram are you referring to?
        hackandthink 3y ago
        This one: https://abuseofnotation.github.io/category-theory-illustrated/01_set/set_contains_itself.svg https://abuseofnotation.github.io/category-theory-illustrate...
  - seanhunter 3y ago
    Resolving this paradox is discussed in TFA as being the founding rationale for the Zermelo–Fraenkel set theory in fact.
  - righttoolforjob 3y ago
    simple: there is no such set.
- bmacho 3y ago
  It is mentioned 2 sentences earlier that it was the case in naive set theory.
xjm 3y ago
Nice! Note that this page has no category theory yet since it explains sets, so if you already know sets, set product, etc and want to learn about category theory, my advice is to go directly to the next chapter, more specifically to this section: https://abuseofnotation.github.io/category-theory-illustrated/02_category/#defining-products-in-terms-of-functions https://abuseofnotation.github.io/category-theory-illustrate... which uses set theory terms to define the category theory way of defining products (the corresponding "universal property").
- munchler 3y ago
  I really like this approach, but it contains some confusing mistakes. For example, unless I'm very much mistaken, the illustration of the initial object is backwards: https://abuseofnotation.github.io/category-theory-illustrated/02_category/initial_object.svg https://abuseofnotation.github.io/category-theory-illustrate...
  - JadeNB 3y ago
    > For example, unless I'm very much mistaken, the illustration of the initial object is backwards: https://abuseofnotation.github.io/category-theory-illustrated/02_category/initial_object.svg https://abuseofnotation.github.io/category-theory-illustrate... You are right. (Curiously, the picture of the terminal object is correct, so they didn't just switch them!)
  - slacka 3y ago
    The author said he is just starting on the book, so he's not claiming it's perfect. And the beauty of github, open source is you can fix them with a pull request. For example, the svg is here: https://github.com/abuseofnotation/category-theory-illustrated/blob/master/_chapters/02_category/initial_object.svg https://github.com/abuseofnotation/category-theory-illustrat...
  - haskman 3y ago
    Looks fine to me. What's wrong with it?
zactato 3y ago
Does anyone else study Category Theory in the hope of finding Revelation/Truth? I'm mostly kidding but for some reason CT scratches a different kind of itch.
- rolisz 3y ago
  I've watched some lectures about CT (and they flew over my head pretty quickly) and I did get the feeling that on one hand there is some deep insight there (that I was barely able to glimpse), but on the other hand it felt like that eagle eye view that CT gives is missing too many details.
  - passion__desire 3y ago
    Physics say it's all probabilities. CT says it's all relationships. CT is related amusingly to abstract nonsense. Basically CT's ability to prove things at such a high level that provides no insights into the going ons in low level details. https://math.stackexchange.com/questions/823289/abstract-nonsense-proof https://math.stackexchange.com/questions/823289/abstract-non...
    - red_trumpet 3y ago
      The term "abstract nonsense" was actually coined in context of category theory: https://en.wikipedia.org/wiki/Abstract_nonsense#History https://en.wikipedia.org/wiki/Abstract_nonsense#History
convolvatron 3y ago
"And they might be right. But mathematical functions have one big advantage over non-mathematical ones — their type signature tells you everything that the function does. This is probably the reason why most functional languages are strongly-typed." I'm confused about this statement. types give you important contextual information about the function in a summarized form, but surely we can have two functions with the same type signature that perform different mappings.
- mrkeen 3y ago
  > surely we can have two functions with the same type signature that perform different mappings. Yes - and you can count the mappings! Enums are sometimes referred to as 'sum types' because you can just add up the number of different states they can be in. Structs are sometimes call 'product types' because you can calculate the number of states they can be in by multiplying the number of states of their members. And functions are 'exponential types'.
- edgyquant 3y ago
  This might be true in a programming language but it’s not for mathematical functions which is what they refer to in the first half of this paragraph. I think what they mean is that two functions won’t have the exact same signature and result typings, though in practice this isn’t normally true for computer systems. Although there’s an argument that if it has those exact same things maybe you don’t need two functions but to improve your one function to be more robust.
- justincredible 3y ago
  I've usually heard this phrased as the signature implies only one possibly function, but that is in a very abstract sense. This phrasing is more intuitive as it's saying the signature constrains what the function could possibly do. For example, if you have a function of type ℕ x ℕ -> ℕ you know it could be doing addition, multiplication or exponentiation, but it can't do division because then it could only be a partial function. A more abstract signature ℕ x ℕ x Op -> ℕ, where Op is the set of binary operations on the natural numbers, can really only do one thing (apply the operands to the operation). Another example, [A] -> A could be any fixed indexing function, but it can't be a function that produces a value of A not found in the list as the true signature of that function is just A per se. As a sibling comment points out, in the context of programming the signature isn't as constraining as it would be in maths as the distinction between total and partial functions is often ignored and you can have side effects. But the more you model your functions to be pure and total the more you can reason about them abstractly.
smokel 3y ago
As much as I like philosophy of mathematics, I never feel quite at ease with sets being some universal foundation. Lists, sets, graphs, all seem quite fundamental to us humans, but where in nature does one observe these weird things? A cave or a jug are highly complex things. Perhaps molecules resemble a graph, but if I understand physics correctly, atoms move like crazy and it's almost accidental that the graph structure is somewhat stable in most molecules. This led me to believe that these fundamental containers are probably a byproduct of how our brains work, more than that they are fundamental outside of those. Thanks to ChatGPT, I now know that this makes me a mathematical fictionalist, or mathematical anti-realist. Anyone care to talk me out of this? :)
- 2snakes 3y ago
  My answer would be: when we distinguish something from something else. This is the root of all logic and cognition.
  - colobas 3y ago
    I like this answer. Been reading “Gödel’s Proof” and for a demonstration where the definition of “tautology” in the main text makes use of the concepts of True and False, there is an appendix explaining that you can arrive at the same result without those concepts, just by treating things as belonging to one class vs another (there is a one to one correspondence with True and False but the meaning is arbitrary)
    - 2snakes 3y ago
      "An engineer, a physicist and a mathematician have to build a fence around a flock of sheep, using as little material as possible. The engineer forms the flock into a tight circular shape and constructs a fence around it. The physicist builds a fence with an infinite diameter and pulls it together until it fits around the flock. The mathematician thinks for a while, then builds a fence around himself and defines himself as being outside.”
      - 3y ago
l__l 3y ago
I'm surprised to see no mention of topos theory in this page? The sense in which category theory is a generalisation of set theory is pretty weak imo until you bring in concepts like subobject classifiers. This isn't the only thing topoi generalise, but is a pretty significant one
tarkin2 3y ago
I still don't know how category theory will help me as a programmer. I understand, and agree, that small functions, composed, are easier to understand and maintain, easier to port and easier to build upon than large monolithic functions. But, aside from that, I'm not sure of the tangible day-to-day benefits of reciting parts of category theory. I admit I don’t know category theory in much detail but I just can’t see the tangible benefit. Any hints would be appreciated.
- Jensson 3y ago
  Its useful when you have uber structured data. Think when programming a programming language for example, the input is extremely structured but you need to handle so many things in so many structured ways. for wishy washy data like you have in almost every other case it isn't useful, unless you want to solve those problems by making a programming language. But in most cases you already have languages there, like SQL for relational data etc, so you don't have to solve those problems.
- kweingar 3y ago
  I studied category theory for a while, and frankly it plays zero role in my day-to-day programming. It would maybe be a different story if I were writing libraries in Haskell or something, but as it is, it’s really not that relevant to me. Programmers use monads all the time without knowing it, but there is little need to understand the deep math-y concepts or proofs that underlie them.
  - tarkin2 3y ago
    I worry this is often the case. I like the idea of learning maths for maths sake. And I would love the time to do that. But knowing I have a limited amount of time, I often suspect a lot of people extolling the benefits of understanding the mathematical underpinning of concepts are more showing off and in love with their own understanding than offering real benefits to programmers.
    - edgyquant 3y ago
deepsun 3y ago
> A function is a relationship between two sets Ok then what is relationship? There's a whole theory of relations, and I'd rather not dive into that for the article. Also, drawing arrows can give misleading intuition. It's better to define a function as a set of pairs, then you don't need to use anything else not introduced yet.
- smohare 3y ago
  [dead]
- JadeNB 3y ago
  > It's better to define a function as a set of pairs, then you don't need to use anything else not introduced yet. If you're looking towards category theory, it may arguably be better to think in terms of abstract arrows as much as possible, so as not to get confused by non-"concrete" categories where there's no obvious "function semantics" for morphisms.
  - SantalBlush 3y ago
    Is there a simple example you could use to illustrate the point? This is interesting.
    - ginnungagap 3y ago
      Let (X,≤) be a partially ordered set. Define a category C whose objects are the elements of X, while for the morphisms there is a single arrow x→y iff x≤y. Those are called posetal categories and are often used as examples
      - boris_m 3y ago
        Relevant chapter from the book: https://abuseofnotation.github.io/category-theory-illustrated/04_order/ https://abuseofnotation.github.io/category-theory-illustrate...
      - SantalBlush 3y ago
erehweb 3y ago
Set theory has the big unexpected results of the reals being bigger than the natural numbers, the independence of the Axiom of Choice, and the undecidability of the Continuum Hypothesis. What are some similarly big results in category theory, for a novice?
- rozgo 3y ago
  Yoneda Lemma, an object is entirely determined by its relationships to other objects.
- contravariant 3y ago
  I'd say the Yoneda lemma should be in there. It's hard to explain without going through all the definitions but very broadly speaking it gives a precise way to characterize a object by its relations to other objects. Though mostly I consider category theory useful not for its results but because its concepts generalize well. If you can relate something to a category then most of the concepts a category has (functors, limits etc.) will have some useful meaning. This makes it easy to come up with good concepts and gives some of their properties for free, which honestly is more practically useful than some clever theorem.
  - JadeNB 3y ago
    > I'd say the Yoneda lemma should be in there. It's hard to explain without going through all the definitions but very broadly speaking it gives a precise way to characterize a object by its relations to other objects. To add a bit to that, Yoneda's lemma says that you know everything about an object if you know the ways that it can be mapped to other objects. The "co-Yoneda's lemma", while often less useful in practice (in my practice, anyway), is maybe easier to understand in this intuitive way: you know everything about an object if you know the ways that other objects can be mapped to it, which I have heard phrased as something like "you can learn everything about an object by probing it with other objects."
    - solomonb 3y ago
      Coyoneda comes up with algebraic effects systems as the "Freer Monad." `Free (Coyoneda f)` gives you `Freer` which allows you to build Monads without even a `Functor` on `f`.
omginternets 3y ago
One thing I would like to understand is what limitations of set theory made it necessary to invent/discover category theory. Can someone enlighten me? What do categories let us do that we can’t do with sets?
- hackandthink 3y ago
  Jean-Pierre Marquis' article may be helpful: https://plato.stanford.edu/entries/category-theory/ https://plato.stanford.edu/entries/category-theory/ >what limitations of set theory made it necessary to invent/discover category theory? Category theory did not start as alternative to set theory. But: "Category theory even leads to a different theoretical conception of set and, as such, to a possible alternative to the standard set theoretical foundation for mathematics." >What do categories let us do that we can’t do with sets? "At minimum, it is a powerful language, or conceptual framework, allowing us to see the universal components of a family of structures of a given kind, and how structures of different kinds are interrelated" Some category theory constructions like adjoints and monads are higher level and more powerful than basic set theory constructions like power set. "The number of mathematical constructions that can be described as adjoints is simply stunning."
  - omginternets 3y ago
    Thank you!
- zzo38computer 3y ago
  I know how it relates to monoids, rather than to sets. For example, you cannot just multiply together any two matrices (like you can with monoids); they need to have the correct dimensions. So, in category theory, this corresponds to the composition of morphisms, so in this case, the objects are the number of rows/columns and the morphisms are the matrices.
- agrounds 3y ago
  Category theory was not a response to any limitations of set theory, but rather a collection of new abstractions, still grounded in set theory (originally anyway). The first paper introducing these abstractions was by Eilenberg and Mac Lane [1], who formalized for the first time the idea of natural functions between mathematical objects. For a long time prior to E&M, mathematicians had used an informal notion of “natural” or “canonical” mapping, which meant something like one special mapping out of several available ones. Especially important is the idea of natural isomorphisms. Just knowing that two objects are isomorphic is often not good enough to prove results about them because you have to make a choice about which isomorphism of several you’re using, and you might have to make such an arbitrary choice about infinitely many pairs of objects all at once. Having a canonical choice solves this problem. Prior to E&M, mathematicians couldn’t formalize this idea of canonical choice. They would hand wave about how natural their choice of isomorphism was and how this allowed them to avoid making arbitrary choices. Then E&M defined categories, functors, and natural transformations to formalize this idea of naturality. Their motivation was algebraic topology, but the abstractions they defined turned out to be extremely broadly useful across all much of mathematics. [1] https://www.ams.org/journals/tran/1945-058-00/S0002-9947-1945-0013131-6/S0002-9947-1945-0013131-6.pdf https://www.ams.org/journals/tran/1945-058-00/S0002-9947-194...
tanvach 3y ago
This short youtube video really helped with me to understand the big pictures of category theory with concrete examples. The Mathematician's Weapon | An Introduction to Category Theory, Abstraction and Algebra https://www.youtube.com/watch?v=FQYOpD7tv30 https://www.youtube.com/watch?v=FQYOpD7tv30
dhosek 3y ago
One of the most powerful things I learned in topology was that functions can be viewed as sets of ordered pairs with the restriction that the first item in each ordered pair can only appear once.
- layer8 3y ago
  Relations between sets are generalizations of functions, which is another way to realize that. I think this was taught in my first CS semester. Also, in the context of automata theory, functions = deterministic and relations = nondeterministic.
rthnbgrredf 3y ago
If you're interested in category theory, I have compiled a list of resources quite recently: https://github.com/madnight/awesome-category-theory https://github.com/madnight/awesome-category-theory
ethics-gradient 3y ago
New to set/category theory here, so this is most likely a failure on my part to understand what the diagram is actually depicting but, why does the Identity function diagram contain two sets? Shouldn't it'd be just the one set with one arrow "turning back on itself"?
- boris_m 3y ago
  They are not 2 sets they are two diagrams, depicting the same set. You can present it like this or in the way you mentioned.

218 points by boris_m 3y ago

Disclaimer: I don't know category theory and I only skimmed the linked page :) This looks great - I love the illustrations, and as far as I know the information looks great! I've got it in my Pocket list and am looking forwards to reading it on the bus. A while back there was a "Group Theory Coloring Book" that someone posted here. I was kinda hoping that this link would be another one of those. (Spoiler: it's an illustrated explanation of category theory - which is great! - not a coloring book). Sorry in advance for hijacking this post, but it's kinda, sorta related to ask: Does anyone have a link to 'fun math/STEM-themed coloring books'?

hackandthink 3y ago

>In particular, a set can contain itself. There are many kinds of mathematics, this is an unusual one. "In Zermelo–Fraenkel set theory, the axiom of regularity and axiom of pairing prevent any set from containing itself." https://en.wikipedia.org/wiki/Universal_set https://en.wikipedia.org/wiki/Universal_set

axblount 3y ago
This gives rise to Russell's Paradox: Does the set of "all sets that do not contain themselves" contain itself?
- tikhonj 3y ago
  You can have set theories that allows sets to contain themselves without allowing Russell's Paradox. You can read about non-well-founded set theory[1] if you're curious. [1]: https://en.wikipedia.org/wiki/Non-well-founded_set_theory https://en.wikipedia.org/wiki/Non-well-founded_set_theory
  - hackandthink 3y ago
    I like the diagram of "the set containing itself". It illustrates non-well-foundedness niceley.
    - l33t7332273 3y ago
      Which diagram are you referring to?
      - hackandthink 3y ago
        This one: https://abuseofnotation.github.io/category-theory-illustrated/01_set/set_contains_itself.svg https://abuseofnotation.github.io/category-theory-illustrate...
- seanhunter 3y ago
  Resolving this paradox is discussed in TFA as being the founding rationale for the Zermelo–Fraenkel set theory in fact.
- righttoolforjob 3y ago
  simple: there is no such set.
bmacho 3y ago
It is mentioned 2 sentences earlier that it was the case in naive set theory.

xjm 3y ago

Nice! Note that this page has no category theory yet since it explains sets, so if you already know sets, set product, etc and want to learn about category theory, my advice is to go directly to the next chapter, more specifically to this section: https://abuseofnotation.github.io/category-theory-illustrated/02_category/#defining-products-in-terms-of-functions https://abuseofnotation.github.io/category-theory-illustrate... which uses set theory terms to define the category theory way of defining products (the corresponding "universal property").

munchler 3y ago
I really like this approach, but it contains some confusing mistakes. For example, unless I'm very much mistaken, the illustration of the initial object is backwards: https://abuseofnotation.github.io/category-theory-illustrated/02_category/initial_object.svg https://abuseofnotation.github.io/category-theory-illustrate...
- JadeNB 3y ago
  > For example, unless I'm very much mistaken, the illustration of the initial object is backwards: https://abuseofnotation.github.io/category-theory-illustrated/02_category/initial_object.svg https://abuseofnotation.github.io/category-theory-illustrate... You are right. (Curiously, the picture of the terminal object is correct, so they didn't just switch them!)
- slacka 3y ago
  The author said he is just starting on the book, so he's not claiming it's perfect. And the beauty of github, open source is you can fix them with a pull request. For example, the svg is here: https://github.com/abuseofnotation/category-theory-illustrated/blob/master/_chapters/02_category/initial_object.svg https://github.com/abuseofnotation/category-theory-illustrat...
- haskman 3y ago
  Looks fine to me. What's wrong with it?

zactato 3y ago

Does anyone else study Category Theory in the hope of finding Revelation/Truth? I'm mostly kidding but for some reason CT scratches a different kind of itch.

rolisz 3y ago
I've watched some lectures about CT (and they flew over my head pretty quickly) and I did get the feeling that on one hand there is some deep insight there (that I was barely able to glimpse), but on the other hand it felt like that eagle eye view that CT gives is missing too many details.
- passion__desire 3y ago
  Physics say it's all probabilities. CT says it's all relationships. CT is related amusingly to abstract nonsense. Basically CT's ability to prove things at such a high level that provides no insights into the going ons in low level details. https://math.stackexchange.com/questions/823289/abstract-nonsense-proof https://math.stackexchange.com/questions/823289/abstract-non...
  - red_trumpet 3y ago
    The term "abstract nonsense" was actually coined in context of category theory: https://en.wikipedia.org/wiki/Abstract_nonsense#History https://en.wikipedia.org/wiki/Abstract_nonsense#History

convolvatron 3y ago

"And they might be right. But mathematical functions have one big advantage over non-mathematical ones — their type signature tells you everything that the function does. This is probably the reason why most functional languages are strongly-typed." I'm confused about this statement. types give you important contextual information about the function in a summarized form, but surely we can have two functions with the same type signature that perform different mappings.

mrkeen 3y ago
> surely we can have two functions with the same type signature that perform different mappings. Yes - and you can count the mappings! Enums are sometimes referred to as 'sum types' because you can just add up the number of different states they can be in. Structs are sometimes call 'product types' because you can calculate the number of states they can be in by multiplying the number of states of their members. And functions are 'exponential types'.
edgyquant 3y ago
This might be true in a programming language but it’s not for mathematical functions which is what they refer to in the first half of this paragraph. I think what they mean is that two functions won’t have the exact same signature and result typings, though in practice this isn’t normally true for computer systems. Although there’s an argument that if it has those exact same things maybe you don’t need two functions but to improve your one function to be more robust.
justincredible 3y ago
I've usually heard this phrased as the signature implies only one possibly function, but that is in a very abstract sense. This phrasing is more intuitive as it's saying the signature constrains what the function could possibly do. For example, if you have a function of type ℕ x ℕ -> ℕ you know it could be doing addition, multiplication or exponentiation, but it can't do division because then it could only be a partial function. A more abstract signature ℕ x ℕ x Op -> ℕ, where Op is the set of binary operations on the natural numbers, can really only do one thing (apply the operands to the operation). Another example, [A] -> A could be any fixed indexing function, but it can't be a function that produces a value of A not found in the list as the true signature of that function is just A per se. As a sibling comment points out, in the context of programming the signature isn't as constraining as it would be in maths as the distinction between total and partial functions is often ignored and you can have side effects. But the more you model your functions to be pure and total the more you can reason about them abstractly.

smokel 3y ago

As much as I like philosophy of mathematics, I never feel quite at ease with sets being some universal foundation. Lists, sets, graphs, all seem quite fundamental to us humans, but where in nature does one observe these weird things? A cave or a jug are highly complex things. Perhaps molecules resemble a graph, but if I understand physics correctly, atoms move like crazy and it's almost accidental that the graph structure is somewhat stable in most molecules. This led me to believe that these fundamental containers are probably a byproduct of how our brains work, more than that they are fundamental outside of those. Thanks to ChatGPT, I now know that this makes me a mathematical fictionalist, or mathematical anti-realist. Anyone care to talk me out of this? :)

2snakes 3y ago
My answer would be: when we distinguish something from something else. This is the root of all logic and cognition.
- colobas 3y ago
  I like this answer. Been reading “Gödel’s Proof” and for a demonstration where the definition of “tautology” in the main text makes use of the concepts of True and False, there is an appendix explaining that you can arrive at the same result without those concepts, just by treating things as belonging to one class vs another (there is a one to one correspondence with True and False but the meaning is arbitrary)
  - 2snakes 3y ago
    "An engineer, a physicist and a mathematician have to build a fence around a flock of sheep, using as little material as possible. The engineer forms the flock into a tight circular shape and constructs a fence around it. The physicist builds a fence with an infinite diameter and pulls it together until it fits around the flock. The mathematician thinks for a while, then builds a fence around himself and defines himself as being outside.”
    - 3y ago

l__l 3y ago

I'm surprised to see no mention of topos theory in this page? The sense in which category theory is a generalisation of set theory is pretty weak imo until you bring in concepts like subobject classifiers. This isn't the only thing topoi generalise, but is a pretty significant one

tarkin2 3y ago

I still don't know how category theory will help me as a programmer. I understand, and agree, that small functions, composed, are easier to understand and maintain, easier to port and easier to build upon than large monolithic functions. But, aside from that, I'm not sure of the tangible day-to-day benefits of reciting parts of category theory. I admit I don’t know category theory in much detail but I just can’t see the tangible benefit. Any hints would be appreciated.

Jensson 3y ago
Its useful when you have uber structured data. Think when programming a programming language for example, the input is extremely structured but you need to handle so many things in so many structured ways. for wishy washy data like you have in almost every other case it isn't useful, unless you want to solve those problems by making a programming language. But in most cases you already have languages there, like SQL for relational data etc, so you don't have to solve those problems.
kweingar 3y ago
I studied category theory for a while, and frankly it plays zero role in my day-to-day programming. It would maybe be a different story if I were writing libraries in Haskell or something, but as it is, it’s really not that relevant to me. Programmers use monads all the time without knowing it, but there is little need to understand the deep math-y concepts or proofs that underlie them.
- tarkin2 3y ago
  I worry this is often the case. I like the idea of learning maths for maths sake. And I would love the time to do that. But knowing I have a limited amount of time, I often suspect a lot of people extolling the benefits of understanding the mathematical underpinning of concepts are more showing off and in love with their own understanding than offering real benefits to programmers.
  - edgyquant 3y ago

deepsun 3y ago

> A function is a relationship between two sets Ok then what is relationship? There's a whole theory of relations, and I'd rather not dive into that for the article. Also, drawing arrows can give misleading intuition. It's better to define a function as a set of pairs, then you don't need to use anything else not introduced yet.

smohare 3y ago
[dead]
JadeNB 3y ago
> It's better to define a function as a set of pairs, then you don't need to use anything else not introduced yet. If you're looking towards category theory, it may arguably be better to think in terms of abstract arrows as much as possible, so as not to get confused by non-"concrete" categories where there's no obvious "function semantics" for morphisms.
- SantalBlush 3y ago
  Is there a simple example you could use to illustrate the point? This is interesting.
  - ginnungagap 3y ago
    Let (X,≤) be a partially ordered set. Define a category C whose objects are the elements of X, while for the morphisms there is a single arrow x→y iff x≤y. Those are called posetal categories and are often used as examples
    - boris_m 3y ago
      Relevant chapter from the book: https://abuseofnotation.github.io/category-theory-illustrated/04_order/ https://abuseofnotation.github.io/category-theory-illustrate...
    - SantalBlush 3y ago

erehweb 3y ago

Set theory has the big unexpected results of the reals being bigger than the natural numbers, the independence of the Axiom of Choice, and the undecidability of the Continuum Hypothesis. What are some similarly big results in category theory, for a novice?

rozgo 3y ago
Yoneda Lemma, an object is entirely determined by its relationships to other objects.
contravariant 3y ago
I'd say the Yoneda lemma should be in there. It's hard to explain without going through all the definitions but very broadly speaking it gives a precise way to characterize a object by its relations to other objects. Though mostly I consider category theory useful not for its results but because its concepts generalize well. If you can relate something to a category then most of the concepts a category has (functors, limits etc.) will have some useful meaning. This makes it easy to come up with good concepts and gives some of their properties for free, which honestly is more practically useful than some clever theorem.
- JadeNB 3y ago
  > I'd say the Yoneda lemma should be in there. It's hard to explain without going through all the definitions but very broadly speaking it gives a precise way to characterize a object by its relations to other objects. To add a bit to that, Yoneda's lemma says that you know everything about an object if you know the ways that it can be mapped to other objects. The "co-Yoneda's lemma", while often less useful in practice (in my practice, anyway), is maybe easier to understand in this intuitive way: you know everything about an object if you know the ways that other objects can be mapped to it, which I have heard phrased as something like "you can learn everything about an object by probing it with other objects."
  - solomonb 3y ago
    Coyoneda comes up with algebraic effects systems as the "Freer Monad." `Free (Coyoneda f)` gives you `Freer` which allows you to build Monads without even a `Functor` on `f`.

omginternets 3y ago

One thing I would like to understand is what limitations of set theory made it necessary to invent/discover category theory. Can someone enlighten me? What do categories let us do that we can’t do with sets?

hackandthink 3y ago
Jean-Pierre Marquis' article may be helpful: https://plato.stanford.edu/entries/category-theory/ https://plato.stanford.edu/entries/category-theory/ >what limitations of set theory made it necessary to invent/discover category theory? Category theory did not start as alternative to set theory. But: "Category theory even leads to a different theoretical conception of set and, as such, to a possible alternative to the standard set theoretical foundation for mathematics." >What do categories let us do that we can’t do with sets? "At minimum, it is a powerful language, or conceptual framework, allowing us to see the universal components of a family of structures of a given kind, and how structures of different kinds are interrelated" Some category theory constructions like adjoints and monads are higher level and more powerful than basic set theory constructions like power set. "The number of mathematical constructions that can be described as adjoints is simply stunning."
- omginternets 3y ago
  Thank you!
zzo38computer 3y ago
I know how it relates to monoids, rather than to sets. For example, you cannot just multiply together any two matrices (like you can with monoids); they need to have the correct dimensions. So, in category theory, this corresponds to the composition of morphisms, so in this case, the objects are the number of rows/columns and the morphisms are the matrices.
agrounds 3y ago
Category theory was not a response to any limitations of set theory, but rather a collection of new abstractions, still grounded in set theory (originally anyway). The first paper introducing these abstractions was by Eilenberg and Mac Lane [1], who formalized for the first time the idea of natural functions between mathematical objects. For a long time prior to E&M, mathematicians had used an informal notion of “natural” or “canonical” mapping, which meant something like one special mapping out of several available ones. Especially important is the idea of natural isomorphisms. Just knowing that two objects are isomorphic is often not good enough to prove results about them because you have to make a choice about which isomorphism of several you’re using, and you might have to make such an arbitrary choice about infinitely many pairs of objects all at once. Having a canonical choice solves this problem. Prior to E&M, mathematicians couldn’t formalize this idea of canonical choice. They would hand wave about how natural their choice of isomorphism was and how this allowed them to avoid making arbitrary choices. Then E&M defined categories, functors, and natural transformations to formalize this idea of naturality. Their motivation was algebraic topology, but the abstractions they defined turned out to be extremely broadly useful across all much of mathematics. [1] https://www.ams.org/journals/tran/1945-058-00/S0002-9947-1945-0013131-6/S0002-9947-1945-0013131-6.pdf https://www.ams.org/journals/tran/1945-058-00/S0002-9947-194...

tanvach 3y ago

This short youtube video really helped with me to understand the big pictures of category theory with concrete examples. The Mathematician's Weapon | An Introduction to Category Theory, Abstraction and Algebra https://www.youtube.com/watch?v=FQYOpD7tv30 https://www.youtube.com/watch?v=FQYOpD7tv30

dhosek 3y ago

One of the most powerful things I learned in topology was that functions can be viewed as sets of ordered pairs with the restriction that the first item in each ordered pair can only appear once.

layer8 3y ago
Relations between sets are generalizations of functions, which is another way to realize that. I think this was taught in my first CS semester. Also, in the context of automata theory, functions = deterministic and relations = nondeterministic.

rthnbgrredf 3y ago

If you're interested in category theory, I have compiled a list of resources quite recently: https://github.com/madnight/awesome-category-theory https://github.com/madnight/awesome-category-theory

ethics-gradient 3y ago

New to set/category theory here, so this is most likely a failure on my part to understand what the diagram is actually depicting but, why does the Identity function diagram contain two sets? Shouldn't it'd be just the one set with one arrow "turning back on itself"?

boris_m 3y ago
They are not 2 sets they are two diagrams, depicting the same set. You can present it like this or in the way you mentioned.