Two groups can look completely different on the surface. Yet they can turn out to be the exact same structure wearing different labels. The tool that proves this is nothing more exotic than a bijection. Chapter 10 defines an isomorphism as a bijective function between two groups that also respects each group's operation. The "respects the operation" part is new, but "bijective function" is not. Permutation groups, starting in chapter 4, reuse the idea even more directly. The symmetric group S_n is literally the set of all bijections from \{1,\ldots,n\} to itself, with composition as the operation. This section restates one-to-one, onto, composition, and inverses in that language. That way, chapter 10's isomorphism definition only has to add one new requirement: that the bijection also respects the operation.
Picture a bank of lockers with one key per locker. One-to-one means no two people were handed the same key. Onto means every locker actually got assigned to somebody; none sit empty. A bijection is both at once. Every person has exactly one locker, and every locker has exactly one person. That pairing is exactly what lets you hand back the reverse list, from locker number to person, without any ambiguity. Composing two bijections means swapping key systems twice in a row: assign lockers by last name first, then re-assign by locker color. Follow that chain for any person, and you still land on exactly one final locker. The combined assignment is a bijection too.
A function f: A \to B is injective (also called one-to-one) if distinct inputs always produce distinct outputs. It is surjective (also called onto) if every element of B is hit by some input. A function is bijective if it is both injective and surjective. Such a function is also called a bijection. Being bijective means every element of B has exactly one preimage in A. That is precisely what makes an inverse function f^{-1}: B \to A possible to define at all. Only a bijective function has a genuine inverse. A non-injective function would need f^{-1} to send one output back to two different inputs. A non-surjective one would leave some inputs to f^{-1} undefined. Composition (g \circ f)(a) = g(f(a)) chains two functions into one, applying f first. When both f and g are bijections, so is g \circ f.
Theorem
A Bijection Has a Unique Inverse
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · Inverse functions — first taught there.
If f: A \to B is a bijection, there is exactly one function f^{-1}: B \to A satisfying f^{-1}(f(a)) = a for every a \in A and f(f^{-1}(b)) = b for every b \in B.
Existence. Define f^{-1}(b) for b \in B as follows: since f is onto, some a \in A satisfies f(a) = b; since f is one-to-one, that a is the only one. So b \mapsto a is a well-defined rule, and it is total since every b \in B has such an a. Call this rule f^{-1}. By construction f(f^{-1}(b)) = f(a) = b, and f^{-1}(f(a)) = f^{-1}(b) = a.
Uniqueness. Suppose h: B \to A is another function with h(f(a)) = a for every a and f(h(b)) = b for every b. Fix b \in B and let a = f^{-1}(b), so f(a) = b. Then h(b) = h(f(a)) = a = f^{-1}(b). Since b was arbitrary, h = f^{-1}.
Theorem
Composition of Bijections Is a Bijection
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · Function composition — first taught there.
If f: A \to B and g: B \to C are both bijections, then g \circ f: A \to C is also a bijection.
Two things must be shown: g \circ f is one-to-one, and g \circ f is onto.
One-to-one. Suppose (g\circ f)(a_1) = (g\circ f)(a_2), i.e. g(f(a_1)) = g(f(a_2)). Since g is one-to-one, this forces f(a_1) = f(a_2). Since f is one-to-one, this forces a_1 = a_2. So g\circ f sends distinct inputs to distinct outputs.
Onto. Let c \in C be arbitrary. Since g is onto, there is some b \in B with g(b) = c. Since f is onto, there is some a \in A with f(a) = b. Then (g\circ f)(a) = g(f(a)) = g(b) = c, so every c \in C is hit.
Both properties hold, so g \circ f is a bijection.
Pair every input with its unique output
Match each of the 4 elements on the left to its image on the right, confirming the pairing is one-to-one and onto.
Loading interactive…
Worked example
Classify a function on a finite set
-
1
Let A = \{1,2,3\} and f: A \to A be f(1) = 2, f(2) = 3, f(3) = 1. Is f one-to-one, onto, both, or neither?
-
2
Check one-to-one: the three outputs 2, 3, 1 are all different, so no two inputs share an output.
-
3
Check onto: the outputs \{2,3,1\} equal all of A, so every element of A is hit.
-
4\boxed{f \text{ is a bijection}}
Its inverse reads the table backward: f^{-1}(2)=1, f^{-1}(3)=2, f^{-1}(1)=3.
Loading interactive…
Worked example
Composing two bijections stays a bijection
-
1
Let f,g: \{1,2,3\} \to \{1,2,3\} with f = (1\,2\,3) \mapsto (2,3,1) and g = (1\,2\,3) \mapsto (1,3,2), both bijections. Compute g \circ f and confirm it is also a bijection.
-
2
Apply f first, then g: (g\circ f)(1) = g(2) = 3, (g\circ f)(2) = g(3) = 2, (g\circ f)(3) = g(1) = 1.
-
3
The three outputs 3, 2, 1 are distinct and cover all of \{1,2,3\}.
-
4\boxed{g \circ f \text{ sends } 1,2,3 \mapsto 3,2,1 \text{ — a bijection}}
This is exactly why an automorphism group can exist at all in chapter 10: composing two structure-preserving bijections of a group with itself never breaks bijectivity, so the automorphisms of G close under composition the same way this pair just did.
Loading interactive…
Where this goes next
Chapter 10: Homomorphisms and the isomorphism theorems
Chapter 10 defines an isomorphism between two groups as a bijection that also respects each group's operation. The bijection part is everything reviewed here, unchanged. Chapter 10 adds only one new requirement. The function must also satisfy f(a * b) = f(a) \star f(b), matching up two different operations at once.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
An encryption scheme maps two different plaintext messages to the same ciphertext. What property has failed?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Two distinct inputs producing the same output is exactly a one-to-one failure -- decryption could not tell the messages apart.
From Discrete Mathematics I — Logic, Proof, and Structure
What is the single fastest way to disprove that a function is one-to-one?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
One-to-one is a for-all claim; a single counterexample pair with matching outputs is enough to disprove it completely.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Which best describes why onto does NOT forbid repeated outputs?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Onto's only requirement is coverage of the codomain -- how many inputs share a given output is irrelevant to it.
From Discrete Mathematics I — Logic, Proof, and Structure
Is f: \mathbb{R} \to \mathbb{R}, f(x) = 3x - 7, onto?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
x=(y+7)/3 is always a real number for any real y, so every target y has an input that reaches it.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Is f:\mathbb{Z}\to\{0,1\}, f(n)=n\bmod 2, a bijection?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Both 0 and 1 are hit (onto), but f(0)=f(2)=0 shows a collision (not one-to-one) -- onto only, not a bijection.
From Discrete Mathematics I — Logic, Proof, and Structure
For A={1,2}, B={x,y,z}: f(1)=x, f(2)=y. Classify f.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
z is never reached -- onto fails.
Why
1 and 2 give distinct outputs (one-to-one holds), but z is never hit (onto fails) -- one-to-one only.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
For f(x)=x+3 and g(x)=2x, find (g \circ f)(4).
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
f(4) = 7, then g(7) = 14.
Correct answer
Also accepted:
Why
From Discrete Mathematics I — Logic, Proof, and Structure
For f(x)=x+3 and g(x)=2x, find (f \circ g)(4), the composition that doubles first.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
g(4) = 8, then f(8) = 11 -- note this differs from (g composed with f)(4) = 14, confirming order matters.
Correct answer
Also accepted:
Why
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Restricting f(x)=x^2 to the domain [0,\infty) makes it a bijection onto [0,\infty). What is its inverse on that restricted domain?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Restricted to non-negative inputs, x-squared is now one-to-one, and the standard inverse is the non-negative square root.
From Discrete Mathematics I — Logic, Proof, and Structure
Why does f(x)=x^2 on \mathbb{R} \to \mathbb{R} have no inverse function?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
An inverse at 9 would have to choose between -3 and 3 with no principled way to decide -- exactly the well-definedness failure a non-injective function produces for its would-be inverse.