Last month’s column talked about the mathematical and philosophical aspects of that one special mapping out of all the ones that exist: the isomorphism.  An isomorphism is special because only this mapping possesses the property that it can be ‘run in reverse’ and, like watching a movie played backwards, the end state (the codomain) returns exactly to the domain.  When this occurs, the original mapping has an inverse.

Lawvere and Schanuel (see here for details) emphasize that much like the arithmetic inverse of 2 is 1/2, so too can we interpret the mapping inverse as a sort of division problem.  Along those lines they introduce the reader to two types of ‘division’ problems – known as the determination and choice problems, respectively – within the context of mappings and category theory.  The fact that there are two types of ‘division mappings’ that one must contend with, in contrast to only one ‘division number’ in the arithmetic case, is a consequence of the fact that we don’t require, in general, an equal number of elements in the two sets being mapped.  The authors fail to explore this last point sufficiently, which leads to their discussion being somewhat impenetrable (a cursory search on the web leads me to conclude that this is a universal finding of people who study their text).  They also add insult to injury by interleaving the discussion of the two problems without much of an organized plan and with several smaller pedagogical no-nos. 

So, to address these shortcomings, this post will look at the first of these two problems, the determination problem, while deferring the choice problem to next month’s column.  In each case, the abstract definition of the problem will be given first follow by a concrete example.  The only remaining question is what specific concrete example to use.  Combining a bit of whimsey with the fact that I just introduced a friend to the 1979 movie The Warriors, led me to pull my examples from it.

For those unfamiliar with the movie, the plot centers around a group from gang called the Warriors who must fight their way through a host of rival gangs as they try to travel from the Bronx to Coney Island.  Each of the rival gangs has a particular set of colors and trademark approach to their violence.  Police officers and ordinary people also show up but in limited roles.  The finite sets based on this story are: a set of some of the gangs, a set of some of the characters, a set of some of the uniforms/colors worn by the gangs, and a set of some of the weapons. (Credit is due to The Warriors Gangs – The Warriors Movie Site which provided some of the finer details about the gangs).

Division Problem 1 – Determination Problem

Abstractly, the determination problem asks the following question.  If $A$, $B$, and $C$ are sets and $f:A \rightarrow B$ and $h:A \rightarrow C$ do we have enough information to determine what mapping, if any, exists between $B$ and $C$.

Pictorially, the question amounts to asking if a mapping $g$ exists such that the following triangle picture closes.

For our concrete example, let’s take the set $A$ to be three members of the titular gang, the set $B$ to be each member’s weapon of choice, and the set $C$ the gang each member most hates. Each member has his own unique weapon of choice (as seen by the mapping $f:A \rightarrow B$): $f(Ajax)=Bat$, $f(Cochise)=Pipe$, and $f(Swan)=Knife$. However, two of the Warriors rank the Rogues at the top of their most-hated lists ($h(Cochise)=Rogues=h(Swan)$ while another member views the Baseball Furies as easily the most detestable ($h(Ajax)=Furies$). Pictorially, the situation looks like:

The question is: can we generate a mapping $g$ from the set of preferred weapons to the set of most-hated gangs such that $g \circ f = h$.  In the parlance of category theory finding $g$ means that ‘$ h$ is a function of $f$’. 

A little bit of thought should convince the reader that a mapping $g$ defined in the following diagram fits the bill.

Of course we can check each case separately as well by the following list:

  • $ h(Ajax) = Furies = g \circ f (Ajax) = g(Bat) = Furies$
  • $h(Cochise) = Rogues = g \circ f (Cochise) = g(Pipe) = Rogues$
  • $h(Swan) = Rogues = g \circ f (Swan) = g(Knife) = Rogues$

Since we’ve exhausted all the elements of the set $A$ and, in each case, found that $h = g \circ f$, we can say that we’ve found a solution to the retraction problem for our little gang-warfare scenario.

Before we interpret that solution in plain language, let’s look at a related situation where a retraction can never be found.  We imagine that Cochise now prefers the Bat as his weapon of choice but that he maintains his deep and abiding hatred for the Rogues.  Let’s make the same list as above and see if anything is now amiss:

  • $h(Ajax) = Furies = g \circ f (Ajax) = g(Bat) = Furies$
  • $h(Cochise) = Rogues = g \circ f (Cochise) = g(Bat) = Rogues$
  • $h(Swan) = Rogues = g \circ f (Swan) = g(Knife) = Rogues$

By the time we got to the second line, we see that we have a problem.  Ajax’s case requires that $g(Bat) = Furies$ while Cochise’s situation requires $g(Bat)=Rogues$.  Under the rules of set mapping, one, and only one, arrow can start on an element in the domain set.  Pictorially, we have a situation where, to reconcile Ajax’s mode-de-guerre with that of Cochise requires two arrows starting off their favorite weapon the baseball bat (note extraneous line have been omitted for clarity).

The mathematical/philosophical machinery invoked leaves us with a clear picture of why a retraction doesn’t work in the latter case even though it works in the former case. The key difference is that in the first scenario $f$ had each element in $A$ point to a unique element in $B$. This requirement makes $f$ an injective mapping and this will be the central aspect of all mappings that possess a retraction. An important correllary is that the size of set $B$ must be at least as big as $A$ so that an injection can be setup (compare with the case if there were only two types of weapons; then one of the Warriors would, necessarily, need to favor the same weapon as another member).

Interestingly, while the category theory explanation of the contrast between the two cases is clear, finding plain language to describe the difference is quite hard.  One might think that a successfully constructed retraction in the first case would mean that we could conclude with certainty that if we see Ajax reach for Bat then he’s coming after one of the Furies.  But a good defense lawyer could argue that he merely wants to go to the batting cage.  Likewise, the lack of a retraction might seem daunting in the second case but if we find a Rogue beaten up with a baseball bat, any NYPD detective would have probable cause to talk to Cochise.  It seems that this aspect of category theory doesn’t adapt itself very well to real-world situations with nearly unlimited possibilities, uncertainties, and confounding variables, despite Lawvere’s and Schanuel’s attempts at doing so.  But the jury is still out in this exploration and maybe new ideas will emerge that force a reassessment.

Next month we’ll look at the choice problem but we’ll drop the gang violence in favor of more prosaic sets.