The Lumenary · Grades 9–12

Structure-preserving maps: homomorphisms and isomorphisms

Name: ______________________

Date: ______________________

You will learn to

Check whether a map preserves an operation, for example reduction modulo $n$ from $(\Z, +)$ to clock arithmetic, or $\exp$ from $(\R, +)$ to $(\R_{>0}, \times)$
Prove that composites of structure-preserving maps preserve structure, and that the inverse of a bijective operation-preserving map preserves the operation
Give a structure-preserving bijection whose inverse is not structure-preserving, for orders or graphs
Decide whether two small structures are isomorphic, using invariants such as the number of elements with $x \ast x = e$ , and explain what an isomorphism transfers
Count the homomorphisms between two clock arithmetics

1.
Which of these maps $f : \Z \to \Z$ preserve addition, i.e. satisfy $f(x + y) = f(x) + f(y)$ for all $x, y$ ? (Choose all that apply.)
- A. $f(x) = 3x$
- B. $f(x) = x + 1$
- C. $f(x) = 0$
- D. $f(x) = -x$
- E. $f(x) = x^2$
2.
Use reduction modulo $9$ without multiplying out: $47 \equiv 2$ and $85 \equiv 4 \pmod 9$ (digit sums $11 \to 2$ and $13 \to 4$ ). What is the remainder of $47 \times 85$ on division by $9$ ?
3.
$\exp : (\R, +) \to (\R_{>0}, \times)$ is an isomorphism. Under it, the additive inverse $-x$ of $x$ corresponds to which element of $\R_{>0}$ ?
- A. $1/e^x$ , the multiplicative inverse of $e^x$
- B. $-e^x$
- C. $e^{1/x}$
- D. $0$
4.
How many homomorphisms $(\Z/4, +) \to (\Z/6, +)$ are there?
5.
Why is $(\Z/4, +)$ not isomorphic to the symmetry group of a non-square rectangle?
- A.In the rectangle group every element $x$ satisfies $x \circ x = e$ ; in $\Z/4$ the element $1$ has $1 + 1 = 2 \ne 0$ . Isomorphisms preserve this property.
- B.They have different numbers of elements.
- C. $\Z/4$ is commutative but the rectangle group is not.
- D.There is no bijection between them.
6.
In the proof of Theorem 3, $\; g(u \star v) \overset{(1)}{=} g\big(f(g(u)) \star f(g(v))\big) \overset{(2)}{=} g\big(f(g(u) \ast g(v))\big) \overset{(3)}{=} g(u) \ast g(v)$ . Which step uses that $f$ is a homomorphism?
- A.Step (2)
- B.Step (1)
- C.Step (3)
- D.No step — the proof only uses that $g$ is the inverse of $f$ .
7.
Which of these is a structure-preserving bijection whose inverse is not structure-preserving?
- A.The identity on vertices, from the graph with vertices $a, b$ and no edge to the graph with vertices $a, b$ and one edge $ab$
- B. $\exp : (\R, +) \to (\R_{>0}, \times)$
- C.Reduction $\Z \to \Z/5$
- D. $x \mapsto -x$ on $(\Z, +)$
8.
Which Lean proposition says that f : ℤ → ℤ preserves addition?
- A.∀ x y : ℤ, f (x + y) = f x + f y
- B.∀ x : ℤ, f (x + x) = f x + f x
- C.∃ x y : ℤ, f (x + y) = f x + f y
- D.∀ x y : ℤ, f x + f y = x + y
9.
Write preserves_addition(f, m, n), where f is a list of length m with f[k] in range(n), describing a map $\Z/m \to \Z/n$ . Return True if $f((x + y) \bmod m) = (f(x) + f(y)) \bmod n$ for all $x, y$ , else False. Then use it to count the homomorphisms $\Z/6 \to \Z/4$ (the tests do this for you).
Computational — Practice
10.
The map $\Z/6 \to \Z/2 \times \Z/3$ , $x \mapsto (x \bmod 2, \; x \bmod 3)$ is an isomorphism (of rings, even). Which $x \in \Z/6$ is sent to $(1, 2)$ ?
- A. $x = 5$
- B. $x = 3$
- C. $x = 2$
- D. $x = 1$

Answer key — Structure-preserving maps: homomorphisms and isomorphisms

1.
$3x$ , $0$ and $-x$ preserve addition: $3(x+y) = 3x + 3y$ , $0 = 0 + 0$ , $-(x+y) = -x + (-y)$ . $x + 1$ fails at $x = y = 0$ ( $1 \ne 2$ ), and $x^2$ fails at $x = y = 1$ ( $4 \ne 2$ ). In fact the homomorphisms $(\Z, +) \to (\Z, +)$ are exactly the maps $x \mapsto cx$ , since $f(x) = x f(1)$ by the argument of Theorem 5.
2.
Because reduction mod $9$ preserves multiplication, $47 \times 85 \equiv 2 \times 4 = 8 \pmod 9$ . Check: $47 \times 85 = 3995$ , and $3 + 9 + 9 + 5 = 26$ , $2 + 6 = 8$ . ✓ If someone claimed $47 \times 85 = 3985$ , the digit sum $25 \to 7$ would expose the error; but $3959$ (two digits swapped) has digit sum $26 \to 8$ and would slip through — casting out nines cannot detect swapped digits.
3.
$e^{-x} \cdot e^{x} = e^{-x + x} = e^0 = 1$ , so $e^{-x}$ is the multiplicative inverse of $e^x$ : $e^{-x} = 1/e^x$ . Additive inverses in $(\R, +)$ correspond to reciprocals in $(\R_{>0}, \times)$ .
4.
If $a = f(1)$ then $f(k) = ka \bmod 6$ , and we need $4a \equiv 0 \pmod 6$ . Testing: $4 \cdot 0 = 0$ ✓, $4$ , $8 \equiv 2$ , $12 \equiv 0$ ✓, $16 \equiv 4$ , $20 \equiv 2$ . So $a = 0$ or $a = 3$ : $\gcd(4, 6) = 2$ homomorphisms, as Theorem 5 predicts. The nonzero one sends $0, 1, 2, 3$ to $0, 3, 0, 3$ .
5.
In the rectangle group $e \circ e = h \circ h = r \circ r = s \circ s = e$ : four elements satisfy $x \circ x = e$ . In $\Z/4$ only $0$ and $2$ satisfy $x + x = 0$ . An isomorphism $f$ would satisfy $x \ast x = e \iff f(x) \star f(x) = f(e)$ , giving a bijection between these two sets of elements — impossible, since $4 \ne 2$ .
6.
Step (1) uses $f(g(u)) = u$ and $f(g(v)) = v$ ; step (2) uses $f(x \ast y) = f(x) \star f(y)$ with $x = g(u)$ , $y = g(v)$ ; step (3) uses $g(f(a)) = a$ . Only step (2) uses that $f$ is a homomorphism.
7.
Theorem 3 rules out (b) and (d) — bijective homomorphisms between sets with operations are always isomorphisms — and (c) is not bijective. In (a) the structure is a relation (adjacency). The identity map preserves it vacuously, since the first graph has no edges, but its inverse does not. So the two graphs are not isomorphic despite the structure-preserving bijection.
8.
∀ x y : ℤ, f (x + y) = f x + f y. The other options restrict to special pairs (x + x; the map $|x|$ passes that test without preserving addition), ask for only one pair (∃; $x^2$ passes at $(0, 0)$ ), or state a different equation (which forces $f(x) = x$ ).
9.
```
def preserves_addition(f, m, n):
    for x in range(m):
        for y in range(m):
            if f[(x + y) % m] != (f[x] + f[y]) % n:
                return False
    return True
```
The two homomorphisms $\Z/6 \to \Z/4$ are $f(1) = 0$ (the zero map) and $f(1) = 2$ , the values $a$ with $6a \equiv 0 \pmod 4$ — in agreement with Theorem 5, $\gcd(6, 4) = 2$ .
10.
The images are $0 \mapsto (0,0)$ , $1 \mapsto (1,1)$ , $2 \mapsto (0,2)$ , $3 \mapsto (1,0)$ , $4 \mapsto (0,1)$ , $5 \mapsto (1,2)$ . All six pairs appear exactly once, so the map is a bijection, and $(1, 2)$ comes from $x = 5$ . This is the Chinese remainder theorem for $6 = 2 \cdot 3$ .