Homomorphisms and Isomorphisms

Why This Matters

How do you tell when two groups are "the same" even though they look different? The integers mod 2 under addition (the set of 0 and 1, with +) and the set of 1 and -1 under multiplication seem unrelated, but they have identical structure. A homomorphism is a function between groups that preserves the operation: applying the function after combining elements gives the same result as combining the images. When a homomorphism is also a bijection (one-to-one and onto), it is an isomorphism, and the two groups are structurally identical.

The kernel of a homomorphism — the set of elements that map to the identity — tells you exactly how much information the map loses. If the kernel contains only the identity, no information is lost and the map is injective (one-to-one).

Programmers encounter homomorphisms constantly. Hash functions are homomorphisms from strings to integers (they preserve concatenation in a loose sense). The map from a program to its type signature is a homomorphism that forgets implementation details while preserving compositional structure. Serialization formats that preserve object relationships are isomorphisms. Understanding these structure-preserving maps clarifies when two representations are interchangeable and when they are not.

Define Terms

Visual Model

Code Example

// Homomorphisms between groups

// Example 1: phi: Z -> Z_n defined by phi(x) = x mod n
// This maps integers under addition to Z_n under addition mod n

function phiModN(x, n) {
  return ((x % n) + n) % n;
}

// Verify homomorphism property: phi(a + b) === phi(a) + phi(b) mod n
const n = 5;
const a = 7, b = 13;
const lhs = phiModN(a + b, n);           // phi(7 + 13) = phi(20) = 0
const rhs = phiModN(phiModN(a, n) + phiModN(b, n), n); // phi(2 + 3) = phi(5) = 0
console.log("phi(a+b) =", lhs);
console.log("phi(a)+phi(b) =", rhs);
console.log("Preserves operation?", lhs === rhs);

// Example 2: phi: Z_6 -> Z_3 defined by phi(x) = x mod 3
// Verify for all pairs in Z_6
console.log("\nVerifying Z_6 -> Z_3 homomorphism:");
let allPreserved = true;
for (let i = 0; i < 6; i++) {
  for (let j = 0; j < 6; j++) {
    const left = (i + j) % 6 % 3;       // phi(i + j mod 6)
    const right = (i % 3 + j % 3) % 3;  // phi(i) + phi(j) mod 3
    if (left !== right) allPreserved = false;
  }
}
console.log("All pairs preserve operation?", allPreserved);

// Find the kernel: elements that map to 0
const kernel = [];
for (let i = 0; i < 6; i++) {
  if (i % 3 === 0) kernel.push(i);
}
console.log("Kernel:", kernel);  // [0, 3]
console.log("Kernel is subgroup?", kernel.length > 0 && 6 % kernel.length === 0);

// Find the image
const image = new Set();
for (let i = 0; i < 6; i++) {
  image.add(i % 3);
}
console.log("Image:", [...image].sort());  // [0, 1, 2] = all of Z_3
console.log("Surjective?", image.size === 3);

// Example 3: Check if phi is an isomorphism
console.log("\nInjective (kernel = {0} only)?", kernel.length === 1);
console.log("This map is NOT an isomorphism (kernel has 2 elements).");

Interactive Experiment

Try these exercises:

• Define phi: Z_4 -> Z_2 by phi(x) = x mod 2. Verify it is a homomorphism by checking all 16 pairs. What is the kernel?
• Is the map phi: Z_5 -> Z_5 defined by phi(x) = 2x mod 5 a homomorphism? Is it an isomorphism?
• Define phi: Z_6 -> Z_6 by phi(x) = 2x mod 6. Check all pairs. Is this a homomorphism? What is the kernel and image?
• Find a homomorphism from Z_4 to Z_2 and determine its kernel. Does the kernel size times the image size equal |G|?
• Can there be a homomorphism from Z_5 to Z_3? (Hint: what would the kernel size have to be?)

Quick Quiz

Coding Challenge

Real-World Usage

Homomorphisms and isomorphisms appear throughout computing:

• Cryptography: Hash functions are (loosely) homomorphic — they map large inputs to fixed-size outputs while partially preserving structure. Fully homomorphic encryption allows computation on encrypted data, a direct application of algebraic homomorphisms.
• Database normalization: Schema mappings that preserve relational structure are isomorphisms. Two schemas are equivalent when an isomorphism exists between them.
• Type systems: Type constructors in programming languages often form functors (a generalization of homomorphisms). The map function on arrays is a homomorphism from function composition to array transformation.
• Data serialization: JSON.parse and JSON.stringify are (approximate) isomorphisms — they convert between object structure and string representation while preserving relationships.
• Category theory in software: Interfaces and adapters in software design are homomorphisms that translate between different APIs while preserving operational semantics.

Connections