13
$\begingroup$

I have some confusion in relation to the following question.

Let $\langle x \rangle = G$, $\langle y \rangle = H$ be finite cyclic groups of order $n$ and $m$ respectively. Let $f : G \mapsto H$ be the mapping sending $x^i$ to $y^i$. Determine the conditions on $n$ and $m$ so that $f$ is going to be a homomorphism.

In verifying the definition of a homomorphism I seem to be able to conclude that there is no restriction on $n$ and $m$ since the definition of a homomorphic mapping is satisfied:

$$ f(x^i x^j) = f(x^{i+j}) = y^{i+j} = y^i y^j = f(x^i) f(x^j) \tag{1} $$

But assuming $n < m$ we would get

$$f(x^n) = f(e) = e \not = y^n$$

So clearly we have to have $m \mid n.$

My questions are

  1. Are there any other conditions on $n$ and $m$ besides $m \mid n.$
  2. What exactly did I do wrong in $(1)$?
  • 0
    For the (1), What would happen if $i+j \ge m$? It always helps to define the map this way: $x^{i(n)} \mapsto x^{i(m)}$. Note that the map may not even be well-defined if $m \nmid n$.2012-03-16
  • 0
    I'll write up a more detailed answer in an hour if it's still unanswered. This has its direct connection to the universal property of the quotient maps.2012-03-16
  • 0
    I see that there are many contradictions if $m \not | n.$ My main concern is that $(1)$ seems like such a innocent algebraic manipulation that I would never suspect that something is wrong with it.I would like to hear an "aha" explanation on why one cannot apply the definition of a homomorphism on $f$ so blindlessly.2012-03-16
  • 0
    Related to http://math.stackexchange.com/questions/108862/how-to-determine-injectivity-and-surjectivity-for-a-map-mathbbz-n-to-mathb2012-03-16
  • 0
    Well, either you use a homomorphism $\mathbb Z \rightarrow G$ (and talk about lifting that homomorphism) or you must face the fact that the Element $x^i$ does NOT determine the number $i$.2012-03-16

5 Answers 5

14

The discussion about "well-defined" is perhaps a bit obscure. Here's the problem:

Remember that in general, an element of $G$ may have many different "names." For example, if $n=10$, then the element $x^{11}$ is equal to $x$; in fact, $x$ has infinitely many different "names" as a power of $x$: $$\cdots = x^{-9} = x^1 = x^{11} = x^{21} = \cdots$$

The problem is that the definition of $f$ as given depends on the name of the element! That is, if we are furiously working and somebody hands us a power of $x$, say, $x^{3781}$, we are supposed to, unthinkingly, map it to $y^{3781}$. The problem is that $x^{3781}$ is the same element as $x$, which we are supposed to send to $y^1$. That means that unless $y^1=y^{3781}$, what we have is not really a function: because the same input, $x$ (who, when being teased by bullies is called "$x^{3781}$") may be sent to $y^1$ or to $y^{3781}$, depending on what "name" we just heard for it.

Checking that the value of the function is the same regardless of what name we are using for an element, even though the function is defined in terms of the name, is called "checking that the function is 'well-defined.'"

An example of a function that is not well-defined would be one in which the input is an integer, and the output is the number of symbols used to express that integer. For example, $f(3)$ would be $1$ (because 3 is only one symbol), but $f(4-1)$ would be $3$ (because we are using 4, -, and 1). This is not well defined as a function of the integers, because $3$ is the same as $4-1$, but $f$ assigns it two different outputs.

So in order for the expression given to actually define a function, we need the following to be true: $$\text{if }x^i=x^j,\text{ then }y^i = f(x^i)\text{ is equal to }y^j=f(x^j).$$ Now, $x^i=x^j$ if and only if $i\equiv j\pmod{n}$; and $y^i=y^j$ if and only if $i\equiv j\pmod{m}$. Therefore, we need: $$\text{if }i\equiv j\pmod{m},\text{ then }i\equiv j\pmod{n}.$$ In other words: every number that is a multiple of $m$ must be a multiple of $n$.

This is equivalent to $n|m$.

In fact, you noticed that in what you wrote, because $x^n=e$, so we need $f(x^n)$ to be the same as $f(x^0)$.

Once we know that $n|m$, then $f$ is well defined. Once it is well-defined, we can start verifying that it is indeed a homomorphism (it is). Technically, it's incorrect to start working to see if it is a homomorphism before you even know whether or not it is a function.

Note that the condition actually works if we allow $G$ or $H$ to be infinite cyclic groups, if we call infinite cyclic groups "groups of order $0$". Then $i\equiv j\pmod{0}$ means $i=j$, every number divides $0$, but the only multiple of $0$ is $0$. So if $G$ is infinite cyclic then the value of $n$ does not matter; if $H$ is infinite cyclic then we must have $G$ infinite cyclic.

  • 0
    I don't agree with your take on well-defined. The rule $x^i\mapsto y^i$ *is* well-defined in the set $\{x^0, x^1, \ldots, x^{n-1}\}$ because every element in this set has a *single* name. The problem is that this rule may *not* be a homomorphism because there is no guarantee that say $x^{2n-3}$ goes to $f(x)^{2n-3}=y^{2n-3}$.2012-03-16
  • 0
    @lhf: I agree that if we were specifying $0\leq i\lt n$, then the rule would yield a well-defined function. However, I don't see any such specification in the statement of the problem. It just says "sending $x^i$ to $y^i$", with no restrictions on $i$. Of course, checking that it is a homomorphism is important: I note it later in the post, I don't ignore it.2012-03-16
  • 0
    Right, I assumed that $0\leq i\lt n$ was a natural implicit assumption.2012-03-16
  • 0
    @lhf: In that case, there is a *different* problem with the definition, which is that it would only make sense if $n\leq m$ (otherwise, $y^i$ for $i\geq m$ would be an "invalid name"). So we would end up with the conclusion that the map only makes sense and is a homomorphism when $m=n$; or else we need to treat the exponent differently in the domain (restricted to a special representation for the elements) but *not* the codomain, which seems somewhat perverse.2012-03-16
  • 0
    I don't think $y^i$ is an invalid name. Just raise $y$ to $i$. The exponent is well defined, isn't it?2012-03-16
  • 1
    @lhf: Again: *if* you are saying that $\langle x\rangle$ consists **only** of $\{x^0,x^1,x^2,\ldots,x^{n-1}\}$, then you must be seeing $\langle y\rangle$ as $\{y^0,y^1,\ldots,y^{m-1}\}$. Then the interpretation of $x^i$ on the LHS is one "thing" (the special name we gave to the elements of the group $\langle x\rangle$), whereas the interpretatio of $y^i$ on the RHS is a different "thing" (the $i$th power of the generator $y$, regardless of the order of $y$). While it *can* be done so, seems to me to be somewhat perverse, as I noted. Same notation, same equation, different contextual meanings.2012-03-16
  • 0
    You do have a point there.2012-03-16
  • 1
    @ArturoMagidin I believe you reversed $m$ and $n$ in "if $i\equiv j (\mod m)\ldots$" and on from there. Your conclusion should be that $m\mid n$.2015-04-27
4

You may want to check first if the map is well defined, ie., if $x^i=x^j$ does it follow that $f(x^i)=f(x^j)$?

  • 0
    +1 Why would anyone downvote this? Ok, it would be better to phrase it: "if $x^i=x^j$ does it follow that $y^i=y^j$?" It is somewhat dangerous to talk about values of $f$ **before** you know that $f$ is well defined.2012-03-16
  • 0
    it is perfectly acceptable to ask whether or not a definition of f makes f a function.2012-03-16
  • 0
    @David, you're right, of course. I was just trying to guess, why there was a downvote for a little while.2012-03-16
2

I am not sure if this completely explains why the naive calculations in $(1)$ are not valid. Here is my go at it:

I'll list down several points of concern.

  • Firstly your map $x^i \mapsto y^i$ is very naive that it misses some essential details.

For convenience of notation, I prefer to look at this as $\varphi(\bar i)=\bar i$ if you'll allow me to do so. This is also naive but to some extent captures what is happening.

So, an equivalence class $\bmod n$ is mapped to the same equivalence class $\bmod m$ under $\varphi$. This bit of information is missed in $x^i \mapsto y^i$. This explains my comment under your question that you will want to write your maps as $x^{i(n)} \mapsto y^{i(m)}$. This notation makes things more transparent.

That you have dicovered that $m \mid n$, it can be obtained through the universal property of the quotients, which I will write about later.

The quotient map $G \to G/H$ factors over $G \to G/K$ if and only if $K \subseteq H$. That is there is a map from $G/H$ to $G/K$ if and only if $K \subseteq H$.

Proof: Please Go through Dummit and Foote's description in their Abstract Algebra in the section $\S3.3$ Isomorphism Theorems.

Now consider your cyclic groups as $\Bbb Z/n\Bbb Z$ and $\Bbb Z/m\Bbb Z$ and observe that above condition will tell you, $m\Bbb Z \subseteq n \Bbb Z$ whic happens if and only if...


As you had earlier in your comments observed, the map won't even be well defined if $m \nmid n$.


I'll leave it to you as a challenge to use this blooper to prove that two groups of same order are isomorphic, which really is not the case. Hint: Cyclic groups exist for any given order.

  • 0
    Will the down voter explain why?2012-03-16
  • 0
    Why do you say that $y^{i+j}$ might not be an element of $H$? Of course it is an element of $H$! A group is a set closed under the group operation, so if $y$ is in there, so are all its powers. Also, are you sure that $i(m)$ is a standard notation for the remainder? Color my old-fashioned, but I think that binary mod should stay in programming classes. This last bit is just a pet-peeve of mine :-)2012-03-16
  • 0
    Firstly, understand that $y^{i+j}$ as it stands is not an element of the group. You need to read that modulo the order of the group. As for the notation, I am pretty sure it is not a very bad notation.2012-03-16
  • 2
    Well, $y^{i+j}$ **is** an element of the group. For example, if $H$ is a subgroup of the multiplicative group of complex numbers generated by the imaginary unit $i$, you seem to be saying that $i^5$ is not an element of $H$. Well, you are wrong: $$i^5=i^{4+1}=i^4\cdot i=1\cdot i=i.$$ Looks like it is in there! The same holds for all cyclic groups. I just picked a concrete one to make you realize your error.2012-03-16
  • 0
    Well, I am not sure I am at fault. $i^5$ is not an element in the group without reading it modulo the order. Let's wait for someone else to clarify.2012-03-16
  • 0
    $i^5=i$ true or false? If true, then you must admit that $i^5$ is in the group. Similarly in the group $\mathbf{Z}_5^*$ we have $2^1=2$, $2^2=4$, $2^3=2^2\cdot2=4\cdot2=8\equiv3$, $2^4=8\cdot2=16\equiv1$, $2^5=2^4\cdot2=1\cdot2=2$ et cetera (all the congruence modulo 5).2012-03-16
  • 0
    True. But, when doing a symbol pushing, you are prone to making a mistake!2012-03-16
  • 1
    No. I'm not prone to making a mistake. I check that my mappings are well-defined. If (granted, a big if in some cases) $y^i=y^j$ whenever $x^i=x^j$, then the mapping $x^i\mapsto y^i$ is trivially a homomorphism: $$f(x^i*x^j)=f(x^{i+j})=y^{i+j}=y^i*y^j=f(x^i)f(x^j)$$ AFTER I have checked that it is well-defined, then the above always makes sense, because in a cyclic group the power of an element is defined in such a way that we always have $y^{i+j}=y^i*y^j$ and so forth.2012-03-16
  • 0
    @KannappanSampath: I don't agree with your reading. By definition, $i^5$ means $ii^4$, which mean $iii^3$, which means $iiii^2$, which means $iiiii$. If you are in a group (in fact, in a semigroup) and $i$ is in the group, then $i^5$ is in the group, period. The issue is indeed well-definedness *of the map*, not of the expression on the right hand side.2012-03-16
  • 0
    @Arturo I understand quite the fact that it is misleading. But is the whole answer wrong?2012-03-16
  • 0
    @Jykri I have got rid of the paragraph but I am not buying your point about the notation, though. I am sorry about pushing hard on something which is quite misleading,2012-03-16
  • 0
    @ArturoMagidin I have edited it now. I'd appreciate your comments.2012-03-16
  • 1
    as a matter of fact, it IS true that $(i+j)$ (mod n) = $i$ (mod n) + $j$ (mod n). the problem is that $(i+j)$ (mod n) may not equal $i+j$ (mod m).2012-03-16
  • 0
    @JyrkiLahtonen I am sorry I spelt your name wrongly. I'll explain the notation and Thank you for removing the downvote.2012-03-16
  • 0
    and I don't get that part about presumptuousness. Please go ahead and edit it if you feel necessary (or you feel that I might not understand what you want to say.) I once again apologise sincerely. I didn't intend to be rude. And, I usually am not rude, as might be evident from my being here at the site.2012-03-16
2

The rule $x^i\mapsto y^i$ gives a perfectly well-defined function in the set $\{x^0, x^1, \ldots, x^{n-1}\}$. However, for that rule to be a homomorphism we need that $x^{i+j} \mapsto y^{i+j}$ for all $i$ and $j$. To find where $x^{i+j}$ goes we need to reduce $i+j \bmod n$ to a $k$ in $\{0,1,\ldots,n-1\}$ and we need that $k \equiv i+j \bmod m$. In other words, we need $k \equiv k' \bmod n \implies k \equiv k' \bmod m$ and this can only happen when $m\mid n$.

0

THEOREM:

Define $f:\langle x \rangle \to \langle y \rangle$, where the orders of $\langle x \rangle$ and $\langle y \rangle$ are n and m respectively, by $f(x) = y^u$. Then f is a well-defined homomorphism if and only if $\frac{m}{\gcd(m,n)} \mid u$.

PROOF: Suppose that the mapping $f:\langle x \rangle \to \langle y \rangle$ is a well-defined homomorphism.

Let $f(x) = y^u$ for some non negative integer u.

We must also have $ 1 = f(x^n) = y^{un}$

Then $ m \mid un$. Let $g = \gcd(m, n)$. Then $\frac m g \mid u \frac n g$. It follows that $\frac m g \mid u$.

The converse is pretty straightforward.

Suppose we define $f:\langle x \rangle \to \langle y \rangle$ by $f(x) = y^u$ where $\frac{m}{\gcd(m,n)} \mid u$

The only real problem with this definition is "Is it well defined?" Since the order of $\langle x \rangle$ is $n$:

\begin{align*} x^a = x^b &\Rightarrow a \equiv b \mod n \cr &\Rightarrow ua \equiv ub \mod {un} \cr &\Rightarrow ua \equiv ub \mod {\frac{mn}{\gcd(m,n)}} \cr &\Rightarrow ua \equiv ub \mod {m} \cr &\Rightarrow y^{ua} = y^{ub}\cr &\Rightarrow f(x^a) = f(x^b) \end{align*}

Linearity is pretty obvious, so $f$ is a well-defined homomorphism.

So, if you want $f(x^i) = y^i$, then you want $f(x) = y$. You must therefore have $\frac{m}{\gcd(m,n)} \mid 1$. Which implies $m \mid n$.

Conversely, if $m \mid n$ and $f(x) = y$, it follows that $f(x^i) = y^i$.