Feeds:
Posts

Regular and effective monomorphisms and epimorphisms

Previously we observed that although monomorphisms tended to give expected generalizations of injective function in many categories, epimorphisms sometimes weren’t the expected generalization of surjective functions. We also discussed split epimorphisms, but where the definition of an epimorphism is too permissive to agree with the surjective morphisms in familiar concrete categories, the definition of a split epimorphism is too restrictive.

In this post we will discuss two other intermediate notions of epimorphism. (These all give dual notions of monomorphisms, but their epimorphic variants are more interesting as a possible solution to the above problem.) There are yet others, but these two appear to be the most relevant in the context of abelian categories.

My current top candidate for a mathematical concept that should be and is not (as far as I can tell) consistently taught at the advanced undergraduate / beginning graduate level is the notion of a groupoid. Today’s post is a very brief introduction to groupoids together with some suggestions for further reading.

Monomorphisms and epimorphisms

Previously we discussed categories with finite biproducts, or semiadditive categories. Today, partially as a further warmup for the axioms defining an abelian category, we’ll discuss monomorphisms and epimorphisms.

Monomorphisms and epimorphisms are supposed to be a categorical generalization of the familiar notion of an injective resp. surjective structure-preserving map (such as an injective resp. surjective group homomorphism or an injective resp. surjective continuous function). This idea more or less works out for monomorphisms, but epimorphisms are somewhat infamous for behaving in unexpected ways, and even monomorphisms can behave unexpectedly sometimes.

Internal equivalence relations

For the last few weeks I’ve been working as a counselor at the PROMYS program. The program runs, among other things, a course in abstract algebra, which was a good opportunity for me to get annoyed at the way people normally introduce normal subgroups, which is via the following unmotivated

Definition: A subgroup $N$ of a group $G$ is normal if $gNg^{-1} \subset N$ for all $g \in G$.

It is then proven that normal subgroups are precisely the kernels $N = \phi^{-1}(e)$ of surjective group homomorphisms $\phi : G \to G/N$. In other words, they are precisely the subgroups you can quotient by and get another group. This strikes me as backwards. The motivation to construct quotient groups should come first.

Today I’d like to present an alternate conceptual route to this definition starting from equivalence relations and quotients. This route also leads to ideals in rings and, among other things, highlights the special role of the existence of inverses in the theory of groups and rings (in the latter I mean additive inverses). The categorical setting for this discussion is the notion of a kernel pair and of an internal equivalence relation in a category, but for the sake of accessibility we will not use this language explicitly.

The “correct” definition of a homomorphism

(Warning: I’m trying to talk about things I don’t really understand in this post, so feel free to correct me if you see a statement that’s obviously wrong.)

Why are continuous functions the “correct” notion of homomorphism between topological spaces?

The “obvious” way to define homomorphisms for a large class of objects involves thinking of them as “sets with extra structure,” and then homomorphisms are functions that preserve that extra structure. In category theory this is formalized by the notion of a concrete category, i.e. a category with a good notion of forgetful functor. For topological spaces this is the functor which gives the set of points.

However, a naive interpretation of “preserving additional structure” suggests that homomorphisms between topological spaces should be open maps, and this isn’t the case. So what gives?

I’m not sure. But rather than take the concrete perspective I’d like to talk about another general principle for defining a good notion of homomorphism.

Little insight: If you can realize a structure as a small category, homomorphisms should be functors.

The problems from IMO 2009 are now available. I haven’t had much time to work on them, though.

There are two classical geometry problems, which I already know I won’t attempt. While I am well aware that classical geometry often requires a great deal of ingenuity, I am also aware of the existence of the field of automatic geometric theorem proving. On this subject I largely agree with Doron Zeilberger: it is more interesting to find an algorithm to prove classes of theorems than to prove individual theorems. The sooner we see areas like classical geometry as “low-level,” the sooner we can work on the really interesting “high-level” stuff. (Plus, I’m not very good at classical geometry.)

Zeilberger’s typical example of a type of theorem with a proof system is the addition or multiplication of very large numbers: it is more interesting to prove $(a + 1)(a - 1) = a^2 - 1$ symbolically than it is to prove individual “theorems” such as $999 \cdot 1001 = 999999$. Zeilberger himself played a significant role in the creation of another proof system, but for the far less trivial case of hypergeometric identities (which includes binomial identities as a special case).

But so I can make my point concretely, I’d like to discuss some examples based on the types of problems most of us had to deal with in middle or high school.

GILA I: Group actions and equivalence relations

Sometimes I worry that I should be more consistent or more lenient about the background I expect of my readers. (Readers, I have to admit that I still don’t really know who you are!) Considering how important I think it is that mathematicians value communicating their ideas to non-specialists (what John Armstrong calls the Generally Interested Lay Audience (GILA)), I should probably be putting my money where my mouth is.

So, inspired by the Unapologetic Mathematician, I have decided on a little project: to build up to a discussion of the Polya enumeration theorem without assuming any prerequisites other than a passing familiarity with group theory. Posts in this project, or any subsequent similar projects, will be labeled “GILA.” The general plan is to talk about group actions in general, the orbit-stabilizer theorem, the lemma formerly known as Burnside’s, and generating functions on the way. Much of this discussion can be found in Section 7 of Stanley’s lectures on algebraic combinatorics.

The PET is a very general way to think about questions of the following nature:

1. How many ways are there to paint the faces of a cube if we consider two colorings related by some rotation to be the same?
2. How many ways are there to paint the beads on a necklace if we consider two colorings related by a rotation of the necklace to be the same?
3. How many ways are there to place some balls into some urns if we consider two placements related by a relabeling of the balls to be the same? (In other words, we want the balls to be “indistinguishable.”)
4. How many graphs with a fixed number of vertices and edges are there if we consider two graphs related by a relabeling of the vertices to be the same? (In other words, we want the graphs to be “non-isomorphic.”)

The general situation is that we have a (finite) set $S$ of slots and another (for now, finite) set $C$ of objects we want to put into those slots, which it is useful to think of as a set of colors that we can “paint” the slots. We also have a (finite) group $G$ of symmetries that controls when we consider two colorings to be “the same.” To understand this situation, it is first necessary to understand something about group actions.