Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: mathematics

Topic: Prove that there are no onto functions like f:[0,1]→[0,1]...

Julius Hamilton (Jun 15 2024 at 15:56):

I want to verbalize related questions I have to this post:

https://math.stackexchange.com/questions/4932904/there-are-no-onto-functions-like-f0-1-rightarrow0-1-that-for-each-x-in0

A function can be defined as a binary relation that is left-total and right-unique. It seems like just by looking at functions as binary relations, it changes the language we use to talk about them. We might say a function $f$ “must be defined on all the elements in its domain” or “must take a value on all elements in the domain”; but as a binary relation, we might say (since a binary relation $R$ is a subset of the product of two sets $X \times Y$), “every element in $X$ must occur in $R$” (and we actually mean, in the first “spot” in each ordered pair in $R$). To say “right unique” from a functional perspective, we could say, “$f$ cannot map the same value to two different values in the codomain”; as a binary relation, we could effectively say “no element of the domain can re-occur in $R$” (where we actually mean “in the first spot of each ordered pair in $R$”). (Because of the axiom of extensionality, we would only see an element re-occur in the first spot in two distinct ordered pairs $a$, $b$, if the elements in the second spots of $a$ and $b$ were different).

It seems like we can simplify the idea of a function. “Left-total” could be called “completeness” (in the sense that the set $X$ from $X \times Y$ must be fully “present” or “represented” in (the first position of each ordered pair in) $R$. “Right-unique” roughly means “non-duplication” (of elements in the first position of each ordered pair in $R$).

So we could say that a function is a subset of a set $S$ that is “complete” and “non-duplicating” (I think). Categorical products are a way of expressing “combinations of things”; maybe we can envision that if you take an $n$-ary product of sets (like $X \times Y \times Z \times …$), and then you take a subset of that set, whichever of the sets is represented “completely and without duplication” (which could be multiple) are the “domain sets” of the function. Metaphorically, it feels like the elements of those sets “anchor” or “index” the other elements, but I need to think more about why.

If we think about the relationship between sets and their subsets, if we allow multiple occurrences of an element (like a multiset subset), it seems clear there is something special about a subset that is complete and non-duplicating. It feels like the convergence point between “less” and “more”. “Less” is a subset that doesn’t contain all the elements of its parent set. As we add more elements, it reaches an “apex” where it maximally contains all the elements in its parent set. Meanwhile, if a “multiset subset” contains various copies of the elements of its parent set, the case where no element is duplicated is “minimal”: we cannot reduce the “arity” of each element any further.

Where am I going with this? Well, I would like to think about the class of properties a binary relation can have, apart from right-uniqueness and left-totality; in order to see the concepts of “function”, “injectivity” and “surjectivity” with a deeper context.

Todd Trimble (Jun 15 2024 at 16:24):

How much have you played with this? There's a slogan that a function (a total well-defined relation) is precisely a relation with a right adjoint. That is to say, a relation $R$ from $X$ to $Y$ is well-defined if for the opposite relation $R^{op}: Y \to X$ the composition $R \circ R^{op}$ is contained in the identity relation on $Y$ (the diagonal subset in $Y \times Y$). And that $R$ is total if the identity relation on $X$ is contained in $R^{op} \circ R$. And if $S: Y \to X$ satisfies both $R \circ S \subseteq 1_Y$ and $1_X \subseteq S \circ R$, then $S = R^{op}$.

All this has been very heavily investigated under the banner of "cartesian bicategory". The concepts of injectivity, surjectivity, etc. can also be treated in these terms.

Eric M Downes (Jun 15 2024 at 16:35):

Julius Hamilton said:

I would like to think about the class of properties a binary relation can have, apart from right-uniqueness and left-totality; in order to see the concepts of “function”, “injectivity” and “surjectivity” with a deeper context.

Here I can recommend pp. 1-13 (starting p. 20 of the pdf) of the book we're using for the Semigroups reading group, esp. Thm 1.8. The terminology is a bit klunky and the presentation non-modern but the concepts are useful, and working them out in detail should give you what you're seeking.

But I have to admit that almost always when I see a binary relation $X\rho Y$, I immediately convert it into a function $\rho':X\times Y\to 2=\set{0,1}$, and I believe this approach better sets you up for topoi, etc. Some people may disagree and view relations as more fundamental. Freyd and Scedrov even cowrote an entire book [[Categories, Allegories]] in which relations are used to define a kind of "arrows only" catgeory theory... but unfortunately the terminology is completely non-standard, almost to the point of being their own private language! See for instance the comments here!

Julius Hamilton (Jun 15 2024 at 16:43):

Thanks @Todd Trimble and @Eric M Downes!! @Todd Trimble I haven’t played with this heavily at all, these thoughts are new to me.

I have many more connected thoughts, but I want to address the original question in the post as well:

For each $x \in [0,1],$ $f^{-1}(x)$ is open.

In topology, “open sets” are effectively a primitive notion. We do not prove that a set is open or closed except by using the topology axioms. A topology is a collection of subsets closed under unions and finite intersections. The elements of the topology are the open sets.

When one thinks about open and closed sets as those that do or do not contain their boundary points, I think this definition makes more sense. Intuitively, it makes sense if the union, or intersection, of two open sets remains open.

I may make some terrible mistakes in the following but here is what I think about the statement to be proved:

If $f : [0,1] \to [0,1]$ is surjective, then it has to be injective (hence bijective). Maybe there is a simple, beautiful way to state this, but clearly if and only if an endomorphism is not injective, the size of the image of the function will be less than the size of the domain. A surjective endormorphism implies the size of the image is the size of the domain.

The next part is hard for me.

Assuming we are working with the “Euclidean metric”, where the distance between two points is the absolute value of their difference, the definition of “open set” is clever, in my opinion: to express “there are no boundary points”, we state that all points are non-boundary points (which means that we can find a neighborhood of nonzero radius of points, around each point). I don’t know if this definition only works for real numbers, though.

What is to be proven is that a surjective endomorphism cannot have “open inverse images” for all its points.

I wonder if the argument for why this is could be made trivial: the inverse image of an element in a codomain is the set of elements in the domain mapped to it. But we know this function $f$ is bijective. We already know that $[0,1]$ is not an open set. I think I am very close to expressing that if a set is closed, of course an automorphism of that set is still closed. I do need to mull it over for a minute, however.

Eric M Downes (Jun 15 2024 at 16:57):

Julius Hamilton said:

If $f : [0,1] \to [0,1]$ is surjective, then it has to be injective (hence bijective).

Unfortunately no! This is an infinite set!

Consider:
$f(x)=\begin{cases}2x & x\in[0,1/2]\\ x & x\in(1/2,1]\end{cases}$

Eric M Downes (Jun 15 2024 at 17:03):

(unless there is some other restriction you are placing on the kinds of $f$ you are considering, but I don't see that on the stackexchange post you referenced. If so, make it explicit.)

Julius Hamilton (Jun 15 2024 at 17:09):

@Eric M Downes Darn! I’ll think that over. :smile:

Excuse any rambling, but this is the first time I’ve been able to do some math in a little while.

I was thinking about how, to say that a topology is a set of elements closed under certain operations, and to say that the elements of that set are “open”, is to say that we have a property, or predicate, which is “preserved” by those operations. But what technically is “preserved”? I think axiomatically it is just this: $P(f(x, y)) \implies P(x) \wedge P(y)$. Which seems similar to a distributivity axiom.

There’s more I want to say about this when my mind is clear. But it feels like there are “two directions” we can go, in defining a property. On the one hand, a set of elements may actually be taken as the definition of the property. The property “open” is a bit superfluous; it’s just a name for the elements of a particular set. That word has no additional meaning. We could do topology by talking about “the elements of $O(X)$” and never call them “open”. On the other hand, the mere fact that these elements are in a particular set is sufficient for us to define - syntactically - property $P$, and then to reason about the dynamics and behavior of this property. In other words, it feels like the property can be defined as the members of some set; or the members of some set can be determined by identifying which ones meet a certain pre-defined property (I think). I’d like to think more about this.

Eric M Downes (Jun 15 2024 at 17:28):

Julius Hamilton said:

I was thinking about how, to say that a topology is a set of elements closed under certain operations, and to say that the elements of that set are “open”, is to say that we have a property, or predicate, which is “preserved” by those operations. But what technically is “preserved”? I think axiomatically it is just this: $P(f(x, y)) \implies P(x) \wedge P(y)$. Which seems similar to a distributivity axiom.

I like thinking this way too, FWIW (although you might have the $\implies$ reversed, or even absent, depending on $P$... this is the kind of oversight that got me in trouble thinking that closures preserve meets more generally than they do, which Todd corrected.)

FWIW The next step I would take is to functionalize everything and turn it into a diagram. (Caveat: More senior people may disagree that this is the best way to approach ideas, so YMMV.) What is $dom(P)$ on the left vs. right? In $\sf Set$ we have internal homs, so it could work there at least, and then you need to figure out what the codomain is, and what minimal algebraic properties we need that codomain to have (express $\land$ as a binary operator etc). This suggests a category where your concept might live. Try to make everything you need to be true about $f,P,x,y$ explicit, and then try to put it in the diagrams, or find a category where the objects have the needed properties. I love approaching things this way, so you might too.

But IMO get that basic surjective/injective stuff down asap though... if you can fit it into your schedule and afford it, I strongly recommend taking a proofs class with a teacher who grades your work and a TA etc. (I assume you're not an undergrad anymore, but are working in industry like me.) That'll force you to really hone and correct your intuitions, and should expand your reach considerably.

Todd Trimble (Jun 15 2024 at 17:32):

Julius, I don't think you need to get too fancy to solve that problem. The key thing is to know how open sets for $[0, 1]$ in the standard topology are defined, combined with the hint that the inverse images of points are disjoint and (especially) nonempty by the surjectivity assumption. Also, some comfort visualizing things is what you'll need. Can $[0, 1]$ be broken up into continuum many disjoint nonempty open sets (open relative to $[0, 1]$)?

That review of Freyd-Scedrov by Mark Dominus is funny. I mean, I can to some degree sympathize, but I would say to anyone that Freyd-Scedrov is studded with gems and insights, all over the place. I find most of it is quite readable with a little patience, but if you give up too soon, there's a lot you'll miss out on. It helps to have a little faith that Freyd is, after all, a master, with quite a unique voice in category theory, and learn from the masters and all that.

dusko (Jun 18 2024 at 21:25):

[sorry i lag behind]
Todd Trimble said:

Julius, I don't think you need to get too fancy to solve that problem. The key thing is to know how open sets for $[0, 1]$ in the standard topology are defined, combined with the hint that the inverse images of points are disjoint and (especially) nonempty by the surjectivity assumption.

do we really need the surjectivity assumption? suppose that $f:[0,1]\to[0,1]$ has at least 2 values $f(x)\neq f(y)$. define $A = f^{-1}(f(x))$ and $B = \bigcup_{z\neq f(x)} f^{-1}(z)$. now $id \subseteq f^{-1}f\implies A\cup B = [0,1]$ and $ff^{-1} \subseteq id\implies A\cap B=\emptyset.$ but since $f^{-1}(f(x))$ and all $f^{-1}(z)$ are open, $A$ and $B$ are open. so extending the view, nicely explained above, of a map $f$ as a relation with a right adjoint, we have decomposed $[0,1]$ into a union of two disjoint open sets, as soon as there are $x$ and $y$ with $f(x)\neq f(y)$. since $[0,1]$ is connected, this is impossible. so a function $f:[0,1]\to [0,1]$ where all $f^{-1}(x)$ are open cannot even cover 2 points, let alone all of $[0,1]$... i think.

Todd Trimble (Jun 18 2024 at 22:07):

Of course you don't need surjectivity. If you click on the link given at the beginning of this thread, you'll see that it's an exercise for a beginner in topology, close to day one. In particular, connectedness of the closed interval is not supposed as something known.

dusko (Jun 19 2024 at 02:04):

oh yes. but in the stackexchange link they did use surjectivity. in fact they did not use topology, just that every open interval must contains a rational number AND that $[0,1]$ is uncountable. i entered the proof without surjectivity there and without using the word "connected". thanks for pointing that out :)

dusko (Jun 19 2024 at 02:06):

(greammarly keeps correcting "surjectivity" to "subjectivity" :)))

Todd Trimble (Jun 19 2024 at 02:08):

Yeah, recently I disabled the grammar check in my gmail settings. I do like spell check though.

Julius Hamilton (Jun 19 2024 at 13:11):

Ok. So, we are trying to prove that a surjective endofunction on [0,1] cannot have all open preimages.

I want to come to a personally authentic understanding of this, so I want to explore some of the constituent parts of this claim.

1. Is there a term for “surjective endomorphisms”? Have they been studied in their own right? (Or “epic endomorphisms”?)
2. Is there something about the way the question is phrased that means we can immediately assume $[0,1]$ is an interval in $\mathbb R$, or can this question be interpreted in other number systems / sets?
3. I read that the “standard topology” on real numbers is where the open sets are the unions of open intervals. And that open intervals are those which have an open ball around each of their points. I know that I need to explore this more, but am pressed for time as of writing this. But what this means is that here, “open sets” are “open intervals”. And since this is an endofunction, as Todd said, the question is basically if [0,1] can be partitioned into sets of open intervals. I think. Maybe the question is clearer if we stop thinking about $f^{-1}$ and just think of a non-inverse function $g$. $g$ can take any subset of $[0,1]$ and those points act like an index on sets of open intervals of $[0,1]$.

I’ll come back to this later today.

The main direction my thinking is headed in is the fact that $[0,1]$ is not an open set in the standard topology. I don’t know if that’s the right direction to go in. If we were working with a finite set, I think it would be easier to claim that one of the partitions are going to have to be closed. But Eric pointed out that things are different when working with infinite sets. For example, if we made sure the “boundary” sets are open “on one side”, like $[0, 0.1)$ and $(0.9,1]$, I’m wondering if the rest of the partition sets could be open intervals. Just my thoughts while I continue trying to process this authentically. Thanks.

John Baez (Jun 19 2024 at 14:05):

I read that the “standard topology” on the real numbers is where the open sets are the unions of open intervals. And that open intervals are those which have an open ball around each of their points. I know that I need to explore this more, but am pressed for time as of writing this. But what this means is that here, “open sets” are “open intervals”.

No - as you said earlier, they are unions of open intervals. Any open interval is a union of open intervals but not conversely. For example, in the standard topology on the real numbers $(0,1/4) \cup (2/4,3/4)$ is an open set that's not an open interval.

John Baez (Jun 19 2024 at 14:09):

Julius Hamilton said:

The main direction my thinking is headed in is the fact that $[0,1]$ is not an open set in the standard topology.

It's not an open set in the standard topology on the real numbers. But it's an open set in the standard topology on $[0,1]$, and I believe that's what matters for your problem.

An open set in the standard topology on $[0,1]$ is defined to be a set of the form $O \cap [0,1]$ where $O$ is an open set in the standard topology on the real numbers. This an example of a standard pattern, the [[subspace topology]].

dusko (Jun 19 2024 at 20:34):

Julius Hamilton said:

Ok. So, we are trying to prove that a surjective endofunction on [0,1] cannot have all open preimages.

I want to come to a personally authentic understanding of this, so I want to explore some of the constituent parts of this claim.

the difficulty may be arising from the fact that the claim "a surjective endofunction on [0,1] cannot have all open preimages" is analogous to "a dog larger than 10 pounds cannot fly". bringing the weight into the story makes it complicated.

no functions except constants can have all preimages open. nothing to do with the surjectivity. (the teacher who stated the claim involving surjectivity wanted the students to use the cardinality of $[0,1]$, which is a deeper fact, unrelated to open preimages.)

given any $f:[0,1]\to[0,1]$ whatsoever, you can define

• $A$ to be the preimage of $f(x)$ for an arbitrary $x$, and
• $B$ to be the union of the preimages of all other points $z\neq f(x)$.

since $f$ is total, every element of its domain $[0,1]$ must lie in $A$ or in $B$. hence $A\cup B = [0,1]$. since $f$ is single-valued, no point of its domain $[0,1]$ can lie both in $A$ and in $B$. hence $A\cap B = \emptyset$.

now if both $A$ and $B$ are open, then we have a decomposition of $[0,1]$ as a union of two disjoint open sets $A$ and $B$. this is only possible if one of them is empty. we know that $A$ is not empty since we defined it as the preimage of $f(x)$, so $x\in A$. so $B$ must be empty, and $f$ is constant, mapping all of $[0,1]$ to $f(x)$.

$[0,1]$ cannot be decomposed into two nonempty disjoint opens because the closure of any open set $A$ is strictly bigger than $A$, unless $A$ is $\emptyset$ or $[0,1]$. the closure of a set is the intersection of all closed sets containing it.

note that for any set $X$, a function $g:[0,1]\to X$ where all preimages are open must be constant --- lest you decompose $[0,1]$ as above. an important principle of conceptual mathematics is that irrelevant details complicate things. occam's razor :)

Morgan Rogers (he/him) (Jun 20 2024 at 11:54):

dusko said:

$[0,1]$ cannot be decomposed into two nonempty disjoint opens because the closure of any open set $A$ is strictly bigger than $A$, unless $A$ is $\emptyset$ or $[0,1]$. the closure of a set is the intersection of all closed sets containing it.

You need to use a bit of analysis or other facts to prove this claim, that might be the insight you need @Julius Hamilton

Zoltan A. Kocsis (Z.A.K.) (Jun 20 2024 at 12:07):

Back when I taught analysis, and students had to prove that $[0,1]$ is connected (i.e. cannot be decomposed into two nonempty disjoint opens in $[0,1]$), I'd usually suggest the following strategy.

1. Have them write the rational interval $\mathbb{Q}\cap [0,1]$ as a pair of disjoint opens in $\mathbb{Q}\cap [0,1]$. Many of the students could do this alone, the rest after a hint to think about the number $\frac{\sqrt{2}}{2}$)
2. Have them explain why an analogous construction fails to disconnect $[0,1]$ itself. They get the insight that there's a special point that can go "neither here nor there".
3. Urge them to consider whether some distinguished property of $\mathbb{R}$ always guarantees the existence of a similar special point.

Morgan Rogers (he/him) (Jun 20 2024 at 15:53):

I think those hints are explicit enough that @Julius Hamilton can figure it out for themselves from here (or maybe can revise some defining properties of the real numbers if they get stuck ;) )

Julius Hamilton (Jun 21 2024 at 14:31):

Sure, yes - but I’ll comb through the above and dwell on some points that were made.

A function (a total, well-defined relation) is a relation with a right adjoint.

I am wondering what it means for a relation to “have an adjoint”, since only functors have adjoints. Am I supposed to view the relation as a functor, or am I supposed to view it as an element in a category where any functor on that category that has an adjoint will effectively “preserve” all the functions?

Todd Trimble (Jun 21 2024 at 14:47):

This refers to the fact that there is a 2-category whose 0-cells are sets $X$, whose 1-cells $r: X \to Y$ are relations from $X$ to $Y$, and whose 2-cells $r \to s$ are inclusions $r \subseteq s$ between relations.

The notion of adjunction $f \dashv g$ makes sense in any 2-category: it means a pair of 1-cells $f: X \to Y$, $g: Y \to X$, and a pair of 2-cells $\eta: 1_X \to gf$, $\varepsilon: fg \to 1_Y$, satisfying triangular equations. In the case of $\mathsf{Rel}$, the triangular equations hold automatically, because there is at most one 2-cell between any pair of parallel 1-cells. So an adjunction in this case amounts to a pair of relations $r: X \to Y$, $s: Y \to X$ such that there are inclusions $1_X \subseteq s \circ r$ and $r \circ s \subseteq 1_Y$.

Given all this, it's actually quite fun to work out that left adjoints in $\mathsf{Rel}$ are the same thing as functions!

Julius Hamilton (Jun 21 2024 at 15:11):

Cool. So in a 2-category, 2-cells are functors. Two functors are adjoint not if their composition (in both directions) equals an identity functor, but more “loosely”: if there is a certain “correspondence”, not between $fg$ and $gf$, but even “looser” (I think) - a correspondence between a map from the identity functor $1_X$ to $gf$, and a map from $fg$ to $1_Y$. This “correspondence” is given by “triangular equations”. Could you remind me what they are - is it expressible as a commutative diagram? (Also, is there an intermediate condition between isomorphism of categories (where two functors compose to the identity) and adjunction: something like a “correspondence between fg and gf”, as I brushed past above? Thanks.)

Julius Hamilton (Jun 21 2024 at 15:47):

I think it’s this. D849A1ED-DBE3-4F1D-A860-C788704DEC70.jpg

Todd Trimble (Jun 21 2024 at 15:50):

So in a 2-category, 2-cells are functors.

No, and I'd better say some more about this.

The 2-category that most everyone first learns about when studying category theory is $\mathsf{Cat}$, where the 0-cells are categories $\mathbf{C}$, where the 1-cells $F: \mathbf{C} \to \mathbf{D}$ are functors, and where the 2-cells $\theta: F \to G$ are natural transformations between functors. This is parallel to how practically the first category people learn about is the category of sets, where the objects (or 0-cells) are sets and the morphisms (or 1-cells) are functions.

Todd Trimble (Jun 21 2024 at 15:50):

But people who take categories seriously learn pretty early on that while, yes, many large categories consist of structured sets (groups, rings, topological spaces, what have you) as 0-cells, and structure-preserving functions as 1-cells, not all categories are of that type. For example, any group can be considered as a category with one object, whose elements give you the morphisms. Another example is a partially ordered set, where the objects are elements of that set, and the morphisms $x \to y$ are instances $x \leq y$ of the order relation. For either of these examples, there is no presupposition that the morphisms have to be "structure-preserving functions". There is much more flexibility as to what categories can be, a point that Bourbaki (Weil in particular) didn't fully appreciate when there was early debate over what role categories might play in their grand opus.

Likewise, when it comes to 2-categories, while many large 2-categories consist of structured categories and suitable structure-preserving functors between them (and further natural transformations between those, that are suitably compatible with this structure), not all 2-categories have to be considered that way. One should think of the axioms for 2-categories as permitting a lot of flexibility in what the 0-cells, 1-cells, and 2-cells could be. One example is $\mathsf{Rel}$, as described above. There is not an automatic sense that the 1-cells (you said 2-cells, but the same point applies) should be considered functors of some type.

Todd Trimble (Jun 21 2024 at 15:50):

Two functors are adjoint not if their composition (in both directions) equals an identity functor, but more “loosely”: if there is a certain “correspondence”, not between fg and gf, but even “looser” (I think) - a correspondence between a map from the identity functor 1X​ to gf, and a map from fg to 1Y​. This “correspondence” is given by “triangular equations”.

The background story takes a while to set out. You may be most familiar with adjoint functors, where you have two functors $F: \mathbf{C} \to \mathbf{D}$ and $G: \mathbf{D} \to \mathbf{C}$ and a natural bijection of the form

$\hom_\mathbf{D}(Fc, d) \cong \hom_\mathbf{C}(c, Gd)$

and already it takes a concerted effort to really grok the conceptual meaning of all this. But there's another way of presenting and understanding adjunctions, involving this business of units and counits and triangular equations, which may be less familiar to you. I'm going to take a break and will come back in a while, although others are welcome to jump in and help explain this, if they want.

Todd Trimble (Jun 21 2024 at 15:51):

Julius Hamilton said:

I think it’s this. D849A1ED-DBE3-4F1D-A860-C788704DEC70.jpg

Yes, this is very much related. There's a lot of gold in those diagrams.

John Baez (Jun 21 2024 at 16:04):

Julius Hamilton said:

Cool. So in a 2-category, 2-cells are functors.

No, not at all. In a 2-category, 2-cells are just 2-cells. In the 2-category $\mathbf{Cat}$, 1-cells are functors and 2-cells are natural transformations.

A good habit in math is to not make definitive proclamations when you don't really know if they're true. You can vastly decrease the number of mistakes you make simply by reflecting on how sure you are of something before you say it. It doesn't mean you have to stay silent. You can turn remarks into questions, like "So in a 2-category, 2-cells are functors?" Or you can add phrases like "I think", or "Maybe".

Kevin Carlson (Jun 21 2024 at 20:16):

Seconding that's a highly under-practiced skill (very much including by me!) Pretty soon noticing when we're not sure may be the only advantage we have over the robots.

Todd Trimble (Jun 21 2024 at 20:58):

Returning now to adjoint functors: the familiar way of defining them in terms of isomorphisms of hom-sets says that there is an isomorphism of two $\mathsf{Set}$-valued functors:

$\hom_\mathbf{D}(F-, -) \cong \hom_\mathbf{C}(-, G-)$

This is not wholly within the language of category theory, since it brings in an "extraneous" category of sets which is not itself definable in the language of category theory. Fortunately, by a clever application of the Yoneda lemma, there's a way to circumvent this.

Todd Trimble (Jun 21 2024 at 20:58):

Fix an object $c$ of $C$. Then, given an adjunction as above, we have an isomorphism

$\theta_{c, -}: \hom_\mathbf{D}(Fc, -) \cong \hom_\mathbf{C}(c, G-)$

but by the Yoneda lemma, this isomorphism is captured in terms of the element $\theta_c(1_{Fc}) \in \hom_\mathbf{C}(c, GFc)$. This element is a morphism of the form $c \to GFc$, which I will denote by $\eta_c: c \to GFc$. From $\eta_c$ you can recapture how the isomorphism

$\theta_{c, d}: \hom_\mathbf{D}(Fc, d) \cong \hom_\mathbf{C}(c, Gd)$

works for any $d$. Namely, you walk through the proof of the Yoneda lemma. If you do this (and I strongly recommend you do), you find that the naturality in $d$ forces a general map $f: Fc \to d$ to be taken to the composite

$c \overset{\eta_c}{\longrightarrow} GFc \overset{Gf}{\longrightarrow} Gd$.

Todd Trimble (Jun 21 2024 at 20:59):

The fact of the bijection means additionally that for any map $g: c \to Gd$, there exists a unique map $f: Fc \to d$ such $g$ equals the composite on display above. This corresponds to one of the commutative triangles that you had in your link.

This property is expressed in other language by saying that $\eta_c: c \to GFc$ is universal among maps of type $c \to Gd$, or is a universal element for the functor $\hom_\mathbf{C}(c, G-)$.

Todd Trimble (Jun 21 2024 at 20:59):

Because the isomorphism $\theta_c: \hom_\mathbf{D}(Fc, d) \cong \hom_\mathbf{C}(c, Gd)$ is natural in both arguments, $d$ and $c$, it follows that $\eta_c: c \to GFc$ is natural in $c$. This means we have a natural transformation $\eta: 1_\mathbf{C} \to GF$. It is called the unit of the adjunction.

Of course the adjunction is a two-way street, so we could start from the other end $\hom_\mathbf{C}(c, Gd) \cong \hom_\mathbf{D}(Fc, d)$. In other words, now fix an object $d$ of $\mathbf{D}$. There is an isomorphism

$\theta_{-, d}^{-1}: \hom_\mathbf{C}(-, Gd) \cong \hom_\mathbf{D}(F-, d)$

and we can apply the Yoneda lemma again: the element $\theta_{-, d}^{-1}(1_{Gd})$ of $\hom_\mathbf{D}(FGd, d)$ is a morphism that I will denote as $\varepsilon_d: FGd \to d$. This is universal (or some people might say "co-universal") among maps of the form $Fc \to d$. The situation is completely dual to the story told earlier. This $\varepsilon_d: FGd \to d$ is natural in $d$, and so defines a natural transformation $FG \to 1_\mathbf{D}$. It is called the counit of the adjunction.

Todd Trimble (Jun 21 2024 at 21:00):

The two directions of the bijection

$\theta_{c, d}: \hom_\mathbf{D}(Fc, d) \cong \hom_\mathbf{C}(c, Gd)$

are completely determined from the unit $\eta$, counit $\varepsilon$, and the functors $F$ and $G$. However, we have not yet expressed in terms of this data the fact that these two directions are inverse to each other. However, we can figure this out, again basically by the Yoneda lemma which gives the recipe for going back and forth. Let's try one of these: let's see what it means to have the composite

$\hom_\mathbf{D}(Fc, d) \to \hom_\mathbf{C}(c, Gd) \to \hom_\mathbf{D}(Fc, d)$

be the identity. By Yoneda, it's enough to take $d = Fc$ and chase the element $1_{Fc}$ through. We know the first half:

$1_{Fc} \mapsto \eta_c \mapsto \text{??}$

The second half takes $\eta_c: c \to GFc$ to, if you've been following the recipe, the composite

$Fc \overset{F\eta_c}{\longrightarrow} FGFc \overset{\varepsilon_{Fc}}{\longrightarrow} Fc$

and the requirement is that this is $1_{Fc}$, since we need to return to the starting point. This is one of the triangular equations.

Todd Trimble (Jun 21 2024 at 21:00):

The other triangular equation (for forth and back) can be left as an exercise to see whether you've been following all this, but the answer in the back of the book is that the composite

$Gd \overset{\eta_{Gd}}{\longrightarrow} GFGd \overset{G\varepsilon_d}{\longrightarrow} Gd$

must equal $1_{Gd}$.

The slight miracle is that this apparatus -- functors $F$ and $G$, natural transformations $\eta: 1_\mathbf{C} \to GF$ and $\varepsilon: FG \to 1_\mathbf{D}$, satisfying the two triangular equations -- is equivalent to having an adjunction $F \dashv G$, but look Ma: no category of sets! For example, the categories didn't even need to be locally small (i.e., have homs valued in some prior category of sets) -- we can still make sense in this way of an adjoint pair of functors. Lawvere would say that this apparatus is an elementary definition of adjunction. It is certainly given wholly in the language of categories, functors, and natural transformations.

Todd Trimble (Jun 21 2024 at 21:00):

We can abstract even further. The basic algebra of categories, functors, and natural transformations is captured in terms of the "five rules of Godement", which you can look up on the nLab. The notion of a 2-category takes the Godement rules as axioms. Long story short, the notion of adjunction internalizes to any 2-category.

But I've spoken long enough, so I should stop here for now.

Julius Hamilton (Jun 22 2024 at 02:00):

I am going to have to break this into very small pieces and understand them one by one.

I would like to start with a very simple focus on the idea of a bijection between Hom-sets for two adjoint functors.

I think adjoint functors are pairs of functors $F: C \to D, G: D \to C$ which have a bijection between the Hom-sets of let us say “corresponding pairs of objects” between the two categories. So in category $C$, let’s choose any object $X$. I think for any $X$, $FX$ is defined, because I think a functor is defined as a mapping on the objects of a category and the arrows of a category, and since I think a mapping is a synonym for a function, I think $F$ has to map every object in $C$ to an object in $D$.

I have not yet taken the time to explore functors as well as I would like. I wonder what patterns there are, regarding what mappings on objects a functor can and cannot have in the target category. For example, I think I can call the category with three objects and only identity morphisms “the discrete category with three objects”, and I think I can also refer to this category with the symbol $3$. Consider analogously calling what I think is called “the discrete category with 2 objects” simply $2$. I think a map from the three objects of $3$ to a single object of $2$ will always be functorial. (I wonder if a functor sending all objects to a single object has a name.) I think functoriality can be thought about in terms of the property “preserves composition of morphisms”, and this diagram:

6CD2F0AA-2D40-48B4-B54A-D8F209F2CA38.jpg

I think I can check if my proposed functor is actually a functor by checking if it preserves composition of morphisms. In what I think is called a discrete category, I think the only possible compositions of morphisms are identity morphisms with themselves. And since I think the definition of a functor requires us to map identity morphisms to identity morphisms, I think it follows that, for example, $F(id_X \circ id_X) = F(id_X) \circ F(id_X)$. I want to keep exploring what mappings on objects make functoriality possible, and which don’t, but I’ll do that later.

Returning to 2 paragraphs above: since I think that $FX$ is defined for all $X$, and $GY$ is defined for all $Y$, I think we can consider the relationship between all $X$ in $C$ and all $GY$ in $C$. I think we can refer to all the $GY$ as the “image” of the functor $G$. I think the collection of all $GY$ is a subcategory of $C$ (which I think includes what I think is called the “proper” or “improper” case, meaning it could be a proper subset of the objects of $C$, or it could be all of them).

I think that when we want to “consider their relationship”, there may be a more direct way to describe that. I think that there are probably different kinds of subcategories with different properties. However, I think that for adjoint functors, regardless of what I called the “direct” relationship of all $GY$ to all $X$, we want to know if that relationship “mirrors” that of the relationship of all $FX$ and all $Y$.

I think that we require that every possible Hom-set between all pairs $FX, Y$ and $X, GY$ is in bijection. I think that normally, a bijection between two individual Hom-sets is not very remarkable or interesting. I think that sets do not have a lot of structure, and I think that a bijection between sets is a rather trivial condition, which I think is equivalent to saying that they are the same size. However, I think that to say that there is a bijection between all Hom-sets in the categories increases the chances of a non-trivial or interesting correspondence. I think that adjoint functors are comparable to the concept of “analogy”. For what I think is the pair of adjoint functors where one takes a set to a free group generated by that set, and one takes a group to its underlying set, I think that since there is a bijection between the relationship between the underlying set of a group, and some other set; and the relationship between the free group generated by that set, and that group, we have a way of saying “A is to B as C is to D”. However, I would like to study this adjunction in more detail.

I have still not yet considered the condition that the bijection must be “natural”, which I will do later.

Thanks everyone for helping me.

Todd Trimble (Jun 22 2024 at 06:12):

I hope I may interpose this question to Julius. Can you give a rough idea of your background in mathematics? Have you taken courses that require you to write out mathematical proofs?

Julius Hamilton (Jun 22 2024 at 20:09):

I have taken some math classes but I don’t think I ever took serious college level classes where I constantly had to prove lots of things. I want to get better at that though.

Julius Hamilton (Jun 22 2024 at 20:10):

Like I can go back to everything I wrote above with “I think” and try to prove or disprove all those claims so I can be more confident.

Patrick Nicodemus (Jun 26 2024 at 03:20):

John Baez [said](https://categorytheory.zulipchat.com/#narrow/stream/411257-theory.3A-mathematics/topic/

A good habit in math is to not make definitive proclamations when you don't really know if they're true.  You can vastly decrease the number of mistakes you make simply by reflecting on how sure you are of something before you say it.  It doesn't mean you have to stay silent.   You can turn remarks into questions, like "So in a 2-category, 2-cells are functors?"  Or you can add phrases like "I think", or "Maybe".

Honestly I think it's fine to just state your understanding of an explanation back to the person who was explaining it to you. It's not the same as confidently asserting something wrong to someone who would take your word for it.

John Baez (Jun 26 2024 at 05:18):

That's certainly fine if you're talking mainly to one person, the person who was explaining something to you. In a public forum like this a bunch of people read everything you write, and they might not notice that you're not seriously claiming what you're saying is true, unless you say something so like "Oh, so..." or "I guess...".

Of course it's up to everyone to do what they want. Personally I've found advantages to putting work into making my public statements reliable unless I preface them with a disclaimer. Of course I don't always succeed - and then I pay a price. In a way there's a vicious circle at work here: the more reliable you are, the more people expect you to be reliable, and the more upset they become when it turns out you were just guessing and you guessed wrong. Maybe there are two stable phases: one in which people perceive you as a "student" who makes wild guesses out loud, and one in which they perceive you as an "expert" who states facts they can trust. Luckily, "experts" can make wild guesses without getting in trouble if they make it clear that's what they're doing.