Module 3: Knowledge Check
Six questions on functors, functor laws, and natural transformations.
Question 1 of 6
A functor F: C → D must satisfy F(g ∘ f) = F(g) ∘ F(f). This law ensures that:
Correct. The composition law F(g ∘ f) = F(g) ∘ F(f) ensures that the "route" of composition is preserved: composing in C and then applying F gives the same result as applying F to each morphism and then composing in D. This is what makes F a structure-preserving map — it does not just map objects and morphisms but respects how those morphisms interact.
Incorrect. The correct answer is B. F(g ∘ f) = F(g) ∘ F(f) says that the compositional structure of C is preserved in D: the "path" from c to c'' via c' in C becomes the same "path" in D after applying F. Note: identity preservation (A) is a separate functor law (F(id_c) = id_{F(c)}); injectivity on objects (C) is a property called "injective on objects" and is not required of all functors.
Question 2 of 6
The forgetful functor U: Grp → Set sends a group homomorphism φ: G → H to the same function φ: |G| → |H| on underlying sets. This functor is:
Correct. U is faithful: if two group homomorphisms φ, ψ: G → H are equal as functions on the underlying sets, then φ = ψ as group homomorphisms (since a group homomorphism is just a function satisfying extra conditions — U "remembers" which function it came from). U is not full: not every function between the underlying sets of two groups is a group homomorphism. For example, the function that sends every element of ℤ to 1 ∈ ℤ is a set function but not a group homomorphism.
Incorrect. The correct answer is C. Faithful means injective on hom-sets — different group homomorphisms give different set functions, so U is faithful. Full means surjective on hom-sets — not every set function between groups is a group homomorphism, so U is not full. This is the generic behavior of forgetful functors: they remember structure (faithful) but do not add it back (not full).
Question 3 of 6
The naturality square for η: F ⟹ G at a morphism f: c → c' commutes when:
Correct. The naturality square says: going from F(c) to G(c') via η_c then G(f) is the same as going via F(f) then η_{c'}. In symbols: η_{c'} ∘ F(f) = G(f) ∘ η_c. This is the coherence condition: the transformation η is "uniform" across all morphisms in C, not just defined componentwise at objects. A family of morphisms that satisfies this condition for every f is natural; one that doesn't is not.
Incorrect. The correct answer is B: η_{c'} ∘ F(f) = G(f) ∘ η_c. The naturality square has four vertices (F(c), F(c'), G(c), G(c')) and four arrows. Commutativity means the two paths from F(c) to G(c') agree. The components η_c need not be equal to each other (A); the functors F and G need not agree on f (C).
Question 4 of 6
The polymorphic Haskell function reverse :: [a] -> [a] is a natural transformation between which functors?
Correct.
reverse has type [a] -> [a] for all types a, which is precisely a natural transformation η: [] ⟹ [] from the list functor to itself. The component η_a = reverse_a: [a] → [a] is the reverse function at type a. Naturality says: for any function f: a → b, reversing a list and then applying f to each element equals applying f to each element and then reversing. This is the naturality square: reverse ∘ fmap f = fmap f ∘ reverse.
Incorrect. The correct answer is B.
reverse :: [a] -> [a] maps lists to lists, so both the source and target functor are the list functor []. It is a natural transformation [] ⟹ []. The naturality condition says: fmap f ∘ reverse = reverse ∘ fmap f — applying a function to each element commutes with reversing the list.
Question 5 of 6
In the functor category [C, D], what are the morphisms?
Correct. In the functor category [C, D]: objects are functors F: C → D, and morphisms are natural transformations η: F ⟹ G between such functors. Composition of natural transformations is componentwise: (β ∘ α)_c = β_c ∘ α_c. This is the key example of category theory's recursive depth: categories organize functors just as they organize objects, and natural transformations are the morphisms between functors.
Incorrect. The correct answer is B. In [C, D], functors are the objects (not the morphisms). The morphisms are natural transformations between functors. This is the core of the three-level structure: categories have objects; functors map between categories; natural transformations map between functors. The functor category makes this structure itself into a category.
Question 6 of 6
A graph homomorphism φ: G → H that maps adjacent vertices to adjacent vertices is a functor between which categories?
Correct. Viewing a directed graph G as a free category (vertices as objects, directed paths as morphisms), a graph homomorphism φ: G → H becomes a functor: it maps objects (vertices) to objects and morphisms (edges, and by extension paths) to morphisms, preserving composition (path concatenation). The functor law F(g ∘ f) = F(g) ∘ F(f) corresponds to φ mapping the concatenation of two paths to the concatenation of their images — which holds because φ maps edges to edges.
Incorrect. The correct answer is A. A directed graph G, when viewed as a free category, has vertices as objects and directed paths (including length-0 paths for identities) as morphisms. A graph homomorphism φ sends vertices to vertices and edges to edges, which extends to a functor between the corresponding free categories: it sends each path to the corresponding path in H. This is why graph homomorphisms are the morphisms in the category Graph.