1
$\begingroup$

I am reading Mac Lane and Saunders Algebra 3rd Edition Chapter 1 Section 8. After defining the remainder function $\rho:\mathbb{Z}\rightarrow\mathbb{Z}n$ they define modular addition $\oplus:\mathbb{Z}n\rightarrow\mathbb{Z}n$ and note the following identity (29):

$\rho(k+m)=(\rho k)\oplus(\rho m)$.

After proving the commutative law for $\oplus$ explicitly, they write:

Put differently: $\rho:\mathbb{Z}\rightarrow\mathbb{Z}n$ is a surjection; by (29) it carries $+$ to $\oplus$, hence it carries the commutative law for $+$ to the commutative law for $\oplus$."

I don't understand this. Why does $\rho$ being a surjection and (29) help us infer the commutativity of $\oplus$ from the commutativity of $+$?.

Then later they define modular multiplication but instead of explicitly proving that modular multiplication is commutative, associative, distributes over $\oplus$, and has 1 as unit, they just write:

Since $\rho$ is a surjection, identities such as the distributive law valid in $\mathbb{Z}$ are valid in $\mathbb{Z}_n$, Q.E.D.

How this is a valid proof that modular multiplication is commutative, associative, distributes over $\oplus$, and has 1 as unit?

Then they say:

These arguments show that identities valid for addition and multiplication in $\mathbb{Z}$ imply corresponding identities for the new addition and multiplication in $\mathbb{Z}_n$. They do not show that other properties valid in $\mathbb{Z}$ carry over to $\mathbb{Z}_n$.

Note that this is well before morphisms are introduced in the text. I have no doubt that making use of knowledge of morphisms would make all this clear. But I don't see how surjectivity itself allows us to make such arguments. I feel like I'm missing something obvious. To be clear, I don't have any trouble proving all of this stuff explicitly. I just don't understand why the surjectivity of $\rho$ helps prove these things directly.

Thanks in advance!

$\endgroup$
1
  • $\begingroup$ See e.g. here for the standard argument. $\endgroup$ Commented Oct 24, 2020 at 9:46

2 Answers 2

1
$\begingroup$

We can figure this out by making it more abstract.

We have a binary operation $\square:A\rightarrow A$, a function $f:A\rightarrow B$, and binary operation $\bigtriangleup:B\rightarrow B$. We also know (we can prove) that

$$ f(a_1)\bigtriangleup f(a_2) = f(a_1\square a_2). $$

If $f$ is surjective then each element of $B$ can be denoted as $f(a)$ for some $a:A$. This implies that we can rewrite $b_1\bigtriangleup b_2$ as $f(a_1)\bigtriangleup f(a_2)$ where $f(a_1)=b_1$ and $f(a_2)=b_2$. In other words, $f$ being surjective means that the above equation describes any application of $\bigtriangleup$ to any two inputs in its domain.

The relation between $\bigtriangleup$ and $\square$ above is saying "identities valid for $\square$ imply corresponding identities for $\bigtriangleup$ whenever the inputs of $\bigtriangleup$ are both outputs of $f$." Commutativity, associativity, etc. are examples of such identities.

The surjectivity of $f$ and the above identity together then mean "identities valid for $\square$ imply corresponding identities for $\bigtriangleup$," similar to what the authors of the textbook wrote in the text I quoted.

$\endgroup$
1
  • $\begingroup$ You've got it ^_^. This was unfortunately timed, as I just added an answer with similar information. It's great that you figured it out by yourself, though! $\endgroup$ Commented Oct 24, 2020 at 4:53
0
$\begingroup$

Welcome to MSE!

There is some fun model theory happening here, but I'll refrain from mentioning it because you aren't familiar with morhpisms yet. If you're interested, I go into some detail in my answer here.

The idea is that "identities" are preserved under morphisms. Let's work with commutativity first:


Let $x,y \in \mathbb{Z}/n$. Then, by surjectivity, $x = \rho(\tilde{x})$ and $y = \rho(\tilde{y})$. But we know that, in $\mathbb{Z}$,

$$\tilde{x} + \tilde{y} = \tilde{y} + \tilde{x}$$

So when we hit everything in sight by $\rho$, we see

$$ x \oplus y = \rho(\tilde{x}) \oplus \rho(\tilde{y}) = \rho(\tilde{x} + \tilde{y}) = \rho(\tilde{y} + \tilde{x}) = \rho(\tilde{y}) \oplus \rho(\tilde{x}) = y \oplus x $$

So $\oplus$ is commutative too.


In general, this strategy will always work for equations. If $p = q$ is some equation in $\mathbb{Z}$, then $p = q$ will also be true in $\rho[\mathbb{Z}]$, which, by surjectivity, is all of $\mathbb{Z}/n$.

Let's see this again with distributivity. Say we know that $\rho(x \times y) = \rho(x) \otimes \rho(y)$, which is not difficult to show. Then

$$ \begin{align} x \otimes (y \oplus z) &= \rho(\tilde{x}) \otimes (\rho(\tilde{y}) \oplus \rho(\tilde{z}))\\ &= \rho(\tilde{x} \times (\tilde{y} + \tilde{z}))\\ &= \rho(\tilde{x} \times \tilde{y} + \tilde{x} \times \tilde{z})\\ &= \rho(\tilde{x}) \otimes \rho(\tilde{y}) \oplus \rho(\tilde{x}) \otimes \rho(\tilde{z})\\ &= x \otimes y \oplus x \otimes z \end{align} $$

Notice this is the same strategy as before. The idea is to:

  1. Write the left hand side of your desired equation.
  2. Write each element on the left hand side as $\rho$ of something.
  3. Use the fact that $\rho$ preserves all the operations to move the stuff inside of $\rho$
  4. Use the fact that the equation holds in $\mathbb{Z}$ to make the substitution and get the desired right hand side inside of $\rho$
  5. Re-apply $\rho$ to get back to the original operations
  6. Conclude the equation also holds in $\mathbb{Z}/n$.

Here surjectivity is crucial, because it lets us move the equation inside of $\rho$ for any elements we want. Without surjectivity, we would only be able to show that our desired equations hold for elements in the image of $\rho$. At least, with this proof technique. As I said before, there is some model theory happening here, and this proof technique works in much more general settings with arbitrary algebras and homomorphisms.


I hope this helps ^_^

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .