Arbtirary thoughts on nearly everything from a modernist poet, structural mathematician and functional programmer.

Monday, April 19, 2010

Categories of paths; functors and natural transformations thereon

Remerber when I said I'd post something about natural transformations and path categories? Well, here it is.

I talked briefly about paths in that post. Let's talk about them a little more. We want a way to talk about a path from a to b in an arbitrary topological space. In $\mathbb{R}$, this is easy enough: take any portion of a curve which starts at a and ends at b. While that's easy to understand, it's a bit unwieldy to work with directly. But we do know that a curve is some sort of a function (think back to 8th grade algebra). So, let's decide this curve is a function. And let's say $f(0)=a$, and $f(1)=b$, and for every $c\in [0,1]$, $f(c)$ lies on the curve we just talked about.

There are a two important things to notice here:
  • We now know the domain of our function: the unit interval (let's call it $I$).
  • This curve should be continuous, or else we have to jump... and what kind of a path is that?


There's something great about these two facts: Where did I mention that our path is a path on $\mathbb{R}$? Nowhere. This means that we can replace $\mathbb{R}$ with any topological space.
So: A path on a topological space $X$ is a continuous function $p:I\rightarrow X$, and we call $p(0)$ the starting point, and $p(1)$ the ending point.

I mentioned categories in the titles, so you may be wondering about now where the category comes from. Let our objects be the points of $X$, and let a morphism from $a$ to $b$ be a path with end-points $a$ and $b$. Is this actually a category? let $id_a$ be constant function $\forall c\in I, p(c)=a$, and let the composition be convolution: $q\circ p = p*q$, where $p*q (c) = p(2c)$ if c<1/2 and $q(2(c-1))$ otherwise.

We run into one big problem here: composition isn't associative, and composition with the identity isn't quite right... but they're both close. You hit all the same points in the right order, but the "speeds" aren't quite right.

We can rectify this with homotopies, but if we use just any homotopy, we'll get pretty boring spaces... so we do what topologists always do to their homotopies when they need to restrict them: fix the end points. So, two paths equivalent up to homotopy with fixed endpoints are now the same.

This gives us a topological space as a category. If this is a category, we should be able to get continuous functions as functors. Yep!
If $F:X\rightarrow Y$, a path $p$ will be sent to the path $F\circ p$. (Exercise: Check that this is indeed a functor, with our wishy washy paths.)

I'm not sure if I've talked about natural transformations. A natural transformation intuitively is a way to transform one functor into another, at the objects.
For two functors $F,G:C\irghtarrow D$, a natural transformation $\eta:F\rightarrow G$ is a collection of morphisms $\eta_x : Fx \rightarrow Gx$, one for each object of $C$. These morphisms need to interact properly with $F$ and $G$. Namely, if $f:x\rightarrow y$ in $C$, then
$\eta_y\circ Ff = Gf\circ\eta_x$. In other words-- starting from $Fx$, following $Ff$ and then a component takes you to the same place as following a component, and then following $Gf$. This must happen everywhere.

One way to understand what's going on is this: There are 3 worlds, $C$, and two other worlds living inside of $D$: $F$-world, and $G$-world. The components of a natural transformation allow us to travel from $F$-world to $G$-world, and if $\eta$ is truly a natural transformation, than we can travel from $F$-world to $G$-world, and then around $G$-world, or you can make the same trip in $F$-world, and then cross over to $G$-world, and either way, you end up in the same place.

What do natural transformations look like when our categories are these path-spaces? Let's see if we can't figure out what is going on. First, let $F,G:X\rightarrow Y$, where X and Y are topological spaces. Now let's look at a path p with endpoints a and b. This will give us two paths in Y, $Fp:Fa\rightarrow Fb$, and $Gp:Ga\rightarrow Gb$. We need a way to turn the first path into the second... How do we do this? Take a homotopy $H:X\times I\rightarrow Y$, where $H_0=F,\; H_1=G$. If we take $H\circ (p\times id)$ (I.e., we take our path, and then apply the homotopy), we get a homotopy from $Fp$ to $Gp$. If we further restrict ourselves to $H_0$, we get... a path $Fa\rightarrow Ga$, and likewise, if we look at $H_1$ we get a path $Fb\rightarrow Gb$. So if $H$ is truly a homotopy, it defines a natural transformation from $F$ to $G$. Likewise, if we have such a natural transformation, we can define a homotopy.

So natural transformations are homotopies. I'm going to stop here, but a fun remark: natural transformations turn Cat what's called a 2-category. So our "2-dimensional" homotopy space (i.e., paths as morphisms and homotopies as natural transformations) turn Top into a 2-category. We can keep going: homotopies between homotopies make 3-morphisms, homotopies between homotopies between ... form n-morphisms, and suddenly we have some notion of $\infty$-category. Moreover, homotopies (and paths) are invertible; which means we actually have an $\infty$-groupoid.

And hopefully that helps motivate some of (higher) category theory. Cheers.

(Disclaimer: There may be gross inaccuracies in this post... please let me know if you find any)

Saturday, April 10, 2010

Interesting notes on Dedekind

I'm reading through Dedekind's The Nature and Meaning of Numbers(as translated by W. Beman), an early treatment of set theory. I find the following convention interesting:

A system [set] $A$ is said to be part of a system $S$ when every element of $A$ is also element of $S$. Since this relation between a system $A$ and a system $S$ will occur continually in what follows, we shall express it briefly by the symbol $A\subset S$. The inverse symbol $S\superset A$, by which the same fact might be expressed, for simplicity and clearness I shall wholly avoid, but for lack of a better word, I shall sometimes say $S$ is whole of $A$ [$S$ contains $A$], by which I mean to express that among elements of $S$ are found all the elements of $A$. Since further every element $s$ of a system $S$by (2) can be regarded as a system, we can hereafter emply the notation $s\subset S$.

(The bold is mine, and the symbol used by Dedekind is not, in fact, $\subset$, but the same symbol is used throughout. The [...] is also my own clarification.)

The question is, of course: is he confusing the two notions $A\subset S$ and $s\in S$, or is he just abusing notation? Considering the context, I doubt the latter, so it would appear he is confusing the two notions. On the other hand, his reasoning seems to be clear throughout, and points (1) and (2) (the text of which I will not force upon you), seem to suggest that he well understands the difference between the idea of "system" and "thing" (as he puts it), that I find the first alternative likewise hard to accept. Although perhaps not, as (2) may provide the source of his confusion. He says "For uniformity of expression it is also advantageous to include the special case where a system $S$ consists of a single (one and only one) element $a$, i.e., the thing $a$ is element of $S$, but every thing different from $a$ is not an element of $S$." This seems to suggest that that the confusion is not elementhood versus subsethood (forgive the abuse of the English language...), but rather, $a$ and $\{a\}$. Either way, it's fascinating, and it seems that this confusion (if that's what it is), does not pop up in the rest of the text.

Another interesting point is that I see the first (that I know of) use of a few common words and notations. A few that come to mind:


  • The word identity to mean what is commonly meant in the mathematical community. That is
    The simples transformation of [function from] a system is that by which each element of its elements is transformed into itself; it will be called the identical transformation of the system.

  • . for composition: "This transformation [the composition] can be denoted briefly by the symbol $\psi .\phi$ or $\psi\phi$." This same paragraph has the first proof I've seen that sets with functions forms a category... albeit, not in those words, and as his set theory is naive, it is not technically correct (as it is not even a consistent system!)


There also appears to be (at least) two flawed proofs.
He shows first that $f(A)\subset f(B)\Rightarrow A\subset B$, and from this concludes that $f(\cap_{i\in I} A_i) = \cap_{i\in I} f(A_i)$. (You can show the first is false by taking some $s\in S\setminus B$, and mapping it into $f(B)$. Then $A=\{s\}$ is a counterexample. Actually, the second is quite correct, assuming the first statement...) Although again, I'm not quite certain: This theorem appears where he is discussing bijections (which he calls "similar transformations"), which might lead one to believe he means only in the case of bijective functions, but in every other theorem in the section he is clear to point out if the function is supposed to be bijective. Further, it appears every function is a priori surjective up until the next section.

While I'm picking apart such a crucial text, I might as well continue complaining: the translation is also infuriating at times as it translates phrases such as dann ist $A$ and dann gibt es as "then is $A$" and "then is there", rather than the more natural "then $A$ is" and "then there is". I do like Miltonic inversion, but this is hardly poetic writing...

Sunday, April 4, 2010

On algebra

Here, someone posted a question about "what algebraists do."

I think the question is interesting, and I like my response (man, does my voice sound good... or something), so I'm posting it here. As the discussion progresses, I'll continue to update this post.

*****
(forcesofodin)
Seems like most of the math majors at my school call themselves algebraist. I really am unsure what an algebraist does. It seems like they're the mathematical equivalent of biologists, observing, categorizing, all the while linking categorizations and members thereof together in new (sometimes surprising ways). But having a name and label for everything (it's been done with finite groups I believe) seems to uninteresting a goal for so many people to be algebraist. Indeed, over categorization and labeling breeds repugnant amounts of technical terms. I know some people like to name-drop with technical terms, but to me it seems more beneficial working to not use the technical terms, to be able to explain to those without the background. Even our major tools, the morphisms, are just ways of categorizing new groups/rings into a variety of already encountered sub types of rings/groups. Such a goal would be wholly useless for someone doing analysis on differential equations.

*****

(me)
In the grand scheme of things, what mathematicians do is categorize and describe increasingly abstract structures. This isn't a pursuit unique to algebraists. The Poincare conjecture was part of a classification movement which is similar in spirit to the classification of finite groups: What manifolds are diffeomorphic to R^n? To S^n? Through the 20th century, you saw the same push for this classification as you did for FSGs. You also see similar attempts to classify things in graph theory-- there are two "forbidden" minors for planarity, but there are 33 (I think?) for the projective plane, and hundreds for other spaces; graph theorists are spending a good deal of time categorizing embeddability.
When you look at category theorists (who I consider to be algebraists...) you see that they aren't categorizing (uh... sorry) anything any more than anyone else-- in fact higher dimensional category theorists are just starting to really figure out what exactly it is they're trying to talk about; they don't have a whole lot of time to worry about how to taxonomize these things.

Regarding term-dropping: Think of terms like Hausdorff, regular, normal, and compact in topology (and continuous, uniformly continuous in analysis); these are all convenient shorthands that say "the object we are looking at satisfies some extra properties." These extra properties give us information about the structure we are looking at. Would you really rather I say "Let G be a topological space for which every open cover has a finite subcover" every time I talk about compact spaces, or would you rather I say "Let G be compact" and move on to what I'm trying to say?
Yes, there are people who like to drop big words to feel good about themselves, but the point of these abstract, esoteric definitions is not to be esoteric or precocious-- the point is to get past the things we see over and over again, and move onto what we're trying to talk about. The words, like any word, are a way for us to communicate information efficiently. Because mathematicians work with new structures all the time, we have to also be in the business of creating language. Since we are trying to describe structures for which there has never been a need for words, by using other structures for which there has never been a need for words, anything we tried to say would very quickly become unruly if we didn't have a quick way of saying it.

My favorite example recently is from ETCS (a structuralist set theory): the axioms for it can be very conveniently stated "The category of sets is a well-pointed topos with a natural number object satisfying the axiom of choice." If you know what a well-pointed topos is, what a natural number object is, and what the axiom of choice is, then you understand the axiom system. Compare that to ZFC-- while the ZFC axioms might be easier to pick apart (explaining the whole axiom system for ETCS in words that "any" mathematician could understand immediately would take... a while), a number of mathematicians are familiar with all 3 of the things needed to understand that axiom (at least, as familiar as they are with the formalism of ZFC) from other areas, so this sentence conveys a good deal of information-- so long as you have the language. It allows someone talking about ETCS to move past the definition, and get to "real" mathematics quicker.

Anyway, onto your question "what does an algebraist do?"
That's a difficult question, in large part because "algebraist" is a much vaguer term than "analyst" or "topologist". A category theorist could be called an algebraist, someone doing finite group theory will be using very different methods than someone doing infinite group theory, and they work with completely different structures than someone doing ring theory or galois theory.
So the question becomes: what about a pursuit makes it "algebraic"? I would say the focus is on some notion of transformation. An action is "algebraic" if it involves pushing some object through a transformation to see what happens. An algebraist studies the way these transformations interact with each other. Turning it around "algebraic [insert mathematical field here]" is the study of a given class of objects (those of the mathematical field we are "algebra-izing") by studying how the objects move under these transformations.

So, I would say an algebraist studies transformations. This is my principal reason for calling category theorist algebraists: when it comes down to it, they aren't studying categories, they are really studying functors and natural transformations-- ways that categories can be transformed.

Also, you say

But having a name and label for everything (it's been done with finite groups I believe) seems to uninteresting a goal for so many people to be algebraist.


Interestingly, there was a discussion about the classification of finite simple groups on the FOM mailing list, in which someone said John Conway was "pessimistic" about the classification: he meant that Conway was pretty sure the classification was complete. So mathematicians spend a good deal of time classifying things, but really, the goal isn't to classify things, it is to understand the structures that we see. The classification is a (possibly unfortunate, possibly fortunate) side effect.

Cheers,
Cory

*****

I failed to respond to the following statement in the above, and I'm feeling rather philosophical (and not particularly sleepy... and also, apparently, verbose) today, so I'll say something about this.

Even our major tools, the morphisms, are just ways of categorizing new groups/rings into a variety of already encountered sub types of rings/groups. Such a goal would be wholly useless for someone doing analysis on differential equations.


that's not all what morphisms are; A morphism from an object A to an object B is a way of saying that you have a relation between to objects-- it means you can say something about B by looking at A (or just as often, you can say something about A by looking at B). The beautiful thing about morphisms is that they show up everywhere: functions are morphisms of sets, homomorphisms are morphisms of (algebraic) structures, continuous functions are morphisms of (topological) spaces, paths are morphisms of points (in a topological space), homotopies are morphisms of continuous functions, proofs are morphisms of propositions, functors are morphisms of categories, natural transformations are morphisms of functors (in more than one way)... the list goes on; an example which is close to home at the moment is morphisms of graphs: a k-coloring of G is a morphism from G to the k-clique*.

In fact, whenever you have a transitive, reflexive relation, you have morphisms, and vice versa. The idea of morphism has very much permeated all of math. Even if it's not (explicitly) being used in an algebraic sense, this categorical language is becoming more and more common, because it very nicely captures something all of matehmaticians do: apply a certain type of function to our objects. What type of function? One that preserves the "interesting" structures of our object. I find it hard to believe that such a general and pliable notion is useless for any mathematician.


*There are some really great results that prove the colorability of whole classes of graphs, simply by making use of composition of morphisms, and apparently graph homomorphisms are being used to precisely and neatly say things that could only be said using rather messy and approximate arguments before.

*****
(forcesofodin)
fair enough, I wish you had taught me algebra.

*****
(pseudonym)
There's so much more to algebra than groups, rings and fields! In broad terms an algebra is just a pair $(X,\Omega)$, where $X$ is a set and $\Omega$ is a set of operations of finite arity on , in which a number of additional rules may hold governing the actions of the operations. The additional structure that can be placed on a general algebra, such as demanding that certain identities hold in the application of sequences of operators (e.g. associativity etc.) make the concept of an algebra very flexible in what it can be used to model. Along with the familiar objects mentioned above algebras have applications in order theory (lattices), logic (boolean algebras with operators, cylindric algebras etc.), theoretical computer scientists can even use algebra to describe the way computer programs work (Kleene algebras), and there is plenty more besides these examples.

With regards the terminology, on an undergrad course it can seem like its just there for its own sake. You prove a lot of stuff that seems like busywork. But this is just because even relatively advanced undergrad/beginning grad courses are really only introductions. They're trying to give you an overview of the tools that are available but they rarely have time to motivate them by going into the problems from which the definitions emerged.

*****
(me)
fair enough, I wish you had taught me algebra.


No you don't, I really don't have the background in algebra I should considering the amount of time I spend raving about it...
(If only I spent that time doing it...)

Thanks for your post, pseudonym, that's a really important point; it also explains why "algebraic combinatorics" focuses so much on lattice theory. (At least, if my description of "algebaric ___" is correct in general.)

Also,

But this is just because even relatively advanced undergrad/beginning grad courses are really only introductions. They're trying to give you an overview of the tools that are available but they rarely have time to motivate them by going into the problems from which the definitions emerged.


This is definitely the hardest part of math education, and is also one of the biggest problems (although there may not be a good solution to it.) The step from solving exercises to original math is really more of a leap, and one with which I am currently floundering. Were it somehow possible to introduce these motivating situations sooner, I think this leap would be easier to make, as students would get to see why we do it that way instead of some other way.

I think this shows up in topology a lot; the definition is signficiantly more abstract than anything most students have seen in analysis at that point, and some understanding seems to get lost along the way. The number of questions on math overflow revolving around "Why is topology definted this way" is some interesting evidence for this.

*****

(pseudonym)
When I look back at my undergrad days I can see how several of the tutors tried to work motivation and exposition into their problem sets, but at the time a lot of it went over my head. I was fairly good at solving problems but I was a long way from seeing them in a wider context. I think the problem is that often the motivating issues are too complex to get across to people who haven't aquired the mathematical maturity gained from a few years of grappling with terminology and educational 'toy' problems.

*****

(jason.chase)
You all sound very intimidating. I am just about to leave my world of problem sets for this wider, terrifying world. I don't know whether reading this is inspirational of scary.

*****

(me)
Hmm... that very well could be the problem... And I do know that my instructors seem to have gotten better at communicating motivation over the past couple of years... perhaps I've just gotten better at understanding it.

You all sound very intimidating. I am just about to leave my world of problem sets for this wider, terrifying world. I don't know whether reading this is inspirational of scary.


Heh. :)
I can promise it is much more requarding and enjoyable once you start trying to break out of problem sets-- pursuing an idea (even a fruitless one!) is very exciting, and gives you a much deeper understanding of the thing you're working with than any problem set can. Suddenly seeing a connection (such as noticing a surprising structure show up "in the wild") is a wonderful feeling that is very difficult to get across with problem sets. (Although I certainly have had this happen while working on a problem set.)

Of course, problem sets will always be important-- I never expect to understand a book until I work the problems, and never expect to understand a lecture or paper without working out the proofs on my own, even when they are "trivial"-- so you'll be able to comfortably hide inside a cozy problem set for a bit whenever you get too afraid of the wilderness.

*****

What I meant by overuse of terminology is when a fellow mathematics student throws in technical terms specific to their expertise that they know I don't know, instead of trying to offer possibly longer explanations in terms that are appropriate to my background. In my experience it is the algebra whiz kids that are the most likely to do this, but perhaps it's only a mistake of not realizing that they at one point didn't know these words. I wish I could remove this statement altogether though as it's a gross generalization fueled by finitely many cases of personal frustration.

With regards the terminology, on an undergrad course it can seem like its just there for its own sake. You prove a lot of stuff that seems like busywork. But this is just because even relatively advanced undergrad/beginning grad courses are really only introductions. They're trying to give you an overview of the tools that are available but they rarely have time to motivate them by going into the problems from which the definitions emerged.


Yes this is an excellent point, and a topic that should be explored in its own thread (but not on the algebra forum of course). It's interesting to look back at high school books, and early undergrad books at the problems to see how they were really setting you up for later material. Like integral convergence questions in my calc book use for the exponent the power p, as a primer to showing the difference between convergence in the different Lp spaces. That's a bad example perhaps, but you know what I mean.

I think a good professor will tell the students why something will be important later. The downfall to this, is that it can lead to students ignoring other "less relevant" parts of the course material. But if only I knew how important Taylor's theorem was when I was learning integral calculus as a freshman. Something I know consider to be the most important tool in applied mathematics is something I used to think was busy work to fill the end of the semester.

Of course, problem sets will always be important-- I never expect to understand a book until I work the problems, and never expect to understand a lecture or paper without working out the proofs on my own


This is an excellent point as well. In the transition to theoretical mathematics I foolishly began overlooking the importance of "drill work". However, in studying for the GRE math subject test I've seen an amazing improvement in my problem solving skills as a whole, that are no doubt a result of repeated drill work. Tools I knew about but in practice never thought to use are now actively surfacing in my consciousness , and I feel so much more empowered.

Above all the foundations of your knowledge base need to be practiced over and over again as you progress (i.e. algebra, geometry, trig. , calculus calculus calculus). A building is only ever as strong as its foundation, and an A grade almost never implies true mastery. I can't tell you how many kids who get A's in algebra can't apply the same tricks in the calculus setting or beyond.

even when they are "trivial"-- so you'll be able to comfortably hide inside a cozy problem set for a bit whenever you get too afraid of the wilderness. :D


This can help build confidence and help alleviate some of the fear of mathematics, it's important for the student to realize 'hey, I CAN do this stuff'. Fear of mathematics is such a powerfully negative force for some people. In tutoring calculus I have seen near brilliant people fail to answer the simplest of questions, only because of the fear and preconceptions of calculus. If I had asked the same questions without calculus floating in the air, they would have thought I was belittling them. So in learning mathematics an air of confidence (but not over confidence or self importance) is powerful and necessary. Maybe I should really say an understanding of one's own potential. I have a saying I made up about this:

Knowledge is only useful if you know you have it
But only a fool thinks himself otherwise
So praise not what you think you know
And embrace only the potential to grow
Creative Commons License Cory Knapp.