Finding the codomain of a monoid homomorphism - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:44:01Z http://mathoverflow.net/feeds/question/11797 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11797/finding-the-codomain-of-a-monoid-homomorphism Finding the codomain of a monoid homomorphism Harrison Brown 2010-01-14T23:13:37Z 2010-01-15T13:28:39Z <p>We have a monoid M, and a function $f: M \rightarrow \{0, 1\}$. We're promised that this function factors through a (surjective) homomorphism to a finite abelian group (considered as a commutative monoid), $M \rightarrow G \rightarrow \{0, 1\}$, but not told what the group is.</p> <p>Can we recover any information about the structure of G, just given $f$? I'm particularly interested in the case where M is the monoid of positive integers under multiplication.</p> <p>[Edit: As I realized after reading Mariano's comment, we can take f = 0 identically and obtain no information whatsoever about G. So a better question might be, under what assumptions on f can we recover G? Or information about G? In particular, if the function from $G \rightarrow \{0, 1\}$ takes on its two values approximately equally often, can we say anything?]</p> <p>More generally, and more interestingly: Can we recover any information about the structure of G, <em>assuming that the black-box is allowed to lie about a small fraction of values of the function</em>?</p> http://mathoverflow.net/questions/11797/finding-the-codomain-of-a-monoid-homomorphism/11799#11799 Answer by Mariano Suárez-Alvarez for Finding the codomain of a monoid homomorphism Mariano Suárez-Alvarez 2010-01-14T23:21:05Z 2010-01-14T23:21:05Z <p>Every morphism $M\to G$ into a group factors through the group completion $\hat M$ (a.k.a. Grothendieck construction) of $M$. It follows that $G$ is a quotient of $\hat M$ and that $f$ factors through $\hat M$.</p> <p>If $f$ is an arbitrary function, I don't think you can get any information about the structure of $G$, except that it is a quotient of $\hat M$---and this information is not really provided by $f$, of course.</p> http://mathoverflow.net/questions/11797/finding-the-codomain-of-a-monoid-homomorphism/11844#11844 Answer by Justin Shih for Finding the codomain of a monoid homomorphism Justin Shih 2010-01-15T10:58:25Z 2010-01-15T13:28:39Z <p>As has been stated, $M \rightarrow G$ factors via the group completion $\hat{M}$. Furthermore, since $G$ is abelian, the map $\hat{M} \rightarrow G$ factors via the abelianization $\hat{M}/[\hat{M},\hat{M}]$ of $\hat{M}$. Since the composite of the maps $M \rightarrow \hat{M} \rightarrow \hat{M}/[\hat{M},\hat{M}]$ is already known, $f$ is uniquely determined by the map $\hat{M}/[\hat{M},\hat{M}] \rightarrow G$, so we may assume $M$ to be an abelian group.</p> <p>Since $f = 0$ gives us no information, we may assume that $f$ is onto. Suppose we have a $G$ so that $f$ factors via it, and let us write $f = pg$, where $g \colon M \rightarrow G$ and $p \colon G \rightarrow \{0,1\}$.</p> <p>By $f = pg$ we must necessarily have $\ker(g) \subset \ker(f)$, so that $g$ is isomorphic to the canonical projection $M \rightarrow M/N$, where $N$ is a subgroup of $\ker(f)$. In addition, $|G|$ must be even. (If $f$ is onto, $p$ must take on the values $0$ and $1$ equally, since $|G| = 2|ker(p)|$.)</p> <p>I claim this is all $f$ tells you. Given $f$, we've just shown that we must have that $g$ is isomorphic to modding out by a subgroup of $\ker(f)$, and that $|G|$ is even. </p> <p>Conversely, given any map $g \colon M \rightarrow G$, whose kernel is a subgroup of $\ker(f)$, and such that $|G|$ is even, then the image of $\ker(f)$ will be of index 2 in $G$, so we can just compose this map with the map that mods out the image of $\ker(f)$ in $G$.</p> <p>Edit: Oops, $G \rightarrow \{0,1\}$ is only a set map! Well then, let me at least try to contribute to the discussion! In this case, we can still assume $M$ to be an abelian group. If you can recover $G$ (assuming $G = M$ is not allowed), then certainly the kernel of $M \rightarrow G$ cannot have any subgroups, hence must be a cyclic group of order $p$. In the case where <code>$M = \mathbb{Z}_+$</code>, then <code>$\hat{M} = \mathbb{Q}_+$</code> which is torsion free, so no maps $f$ exist which allow you to recover $G$ entirely, unless we allow $G = \hat{M}$.</p>