Module 2 Quiz - Categorical Foundations of ML

Question 1 of 6

Which of the following is NOT a valid category?

Sets with total functions as morphisms
Natural numbers with "divides" as morphisms (n → m if n divides m)
Graphs with graph homomorphisms as morphisms
Real numbers as objects, with a morphism x → y whenever x > y (strict greater-than)

Correct. Strict greater-than is not reflexive: there is no morphism x → x since x > x is false. Therefore there is no identity morphism for any object, violating the category axioms. The other three are valid categories: Set (functions compose associatively), divisibility (reflexive and transitive), and Graph (homomorphisms compose).

Incorrect. The correct answer is D. Strict greater-than fails because it is not reflexive: x > x is never true, so there is no identity morphism id_x: x → x. Every category requires an identity morphism for every object. The other options all satisfy the category axioms.

Question 2 of 6

A monoid can be viewed as a category. The single object of this category represents:

The identity element of the monoid
A placeholder — it carries no intrinsic meaning; only the morphisms (monoid elements) matter
The carrier set of the monoid
The monoid operation itself

Correct. In the one-object category corresponding to a monoid (M, ·, e), the single object ★ is a formal placeholder. The monoid elements are the morphisms ★ → ★, the monoid operation is composition of morphisms, and the monoid identity e is the identity morphism id_★. The object itself has no intrinsic content — it exists only to serve as the source and target for morphisms.

Incorrect. The correct answer is B. The single object is a formal placeholder with no intrinsic meaning. The structure of the monoid lives entirely in the morphisms: elements become morphisms ★ → ★, multiplication becomes composition, and the identity element becomes id_★. This shows that monoids are "categories with amnesia about the distinction between objects."

Question 3 of 6

In the category corresponding to a relational database schema, what do the morphisms represent?

SQL queries that join two tables
Foreign key relationships between tables
Rows in each table
Indexes defined on the tables

Correct. In the schema-as-category interpretation, tables are objects and foreign key relationships are morphisms. A foreign key from table A to table B is a morphism A → B. Composition of morphisms corresponds to following a chain of foreign keys. Identity morphisms are the implicit self-references. A database instance is then a functor from this schema category into Set.

Incorrect. The correct answer is B. Tables are objects; foreign key relationships are morphisms. Rows are part of the instance (a functor into Set), not the schema (the category). SQL queries are more like natural transformations between instances. Indexes are an implementation detail not captured in the categorical schema.

Question 4 of 6

Given morphisms f: A → B, g: B → C, and h: C → D, the associativity law states:

h ∘ g ∘ f = f ∘ g ∘ h (commutativity)
(h ∘ g) ∘ f = h ∘ (g ∘ f) (associativity of composition)
g ∘ f = f ∘ g (commutativity of any two morphisms with matching types)
h ∘ (g ∘ f) = id_D (every composition is eventually an identity)

Correct. Associativity says that when composing three morphisms in sequence, it does not matter which pair you compose first: (h ∘ g) ∘ f = h ∘ (g ∘ f). This is critical because it means that a chain of morphisms f₁; f₂; ...; fₙ has a unique composite regardless of how you parenthesize the computation. Note: categories are generally NOT commutative — f ∘ g ≠ g ∘ f in most categories.

Incorrect. The correct answer is B: (h ∘ g) ∘ f = h ∘ (g ∘ f). Associativity says the order of parenthesization does not matter. Commutativity (f ∘ g = g ∘ f) is a much stronger property that most categories do not have. Categories have associativity but not commutativity in general.

Question 5 of 6

Two objects A and B in a category are isomorphic (A ≅ B) if and only if:

They have the same number of morphisms going out of them
There exist morphisms f: A → B and g: B → A such that g ∘ f = id_A and f ∘ g = id_B
They are the same object (strict equality)
Every morphism from A to any object C has a corresponding morphism from B to C

Correct. Isomorphism requires a two-sided inverse: morphisms f: A → B and g: B → A such that going from A to B to A gives id_A, and going from B to A to B gives id_B. In Set, this is exactly a bijection. The key point is that isomorphic objects are categorically indistinguishable — they satisfy all the same universal properties. Category theory works "up to isomorphism" rather than up to equality.

Incorrect. The correct answer is B. Isomorphism requires the existence of morphisms f: A → B and g: B → A satisfying g ∘ f = id_A and f ∘ g = id_B. This is the categorical generalization of a bijection. Note that D describes a weaker property (a natural transformation at one level), not isomorphism. Strict equality (C) is too strong — category theory intentionally works up to isomorphism, not equality.

Question 6 of 6

The free category on a directed graph G has as morphisms:

Only the edges of G
All finite directed paths in G, including empty paths (length-0) at each vertex
All subsets of edges of G
Only the paths of length at most 2

Correct. The free category on G has all finite directed paths as morphisms, including the length-zero paths at each vertex (which serve as identity morphisms). Composition is path concatenation. The word "free" means no additional equations are imposed — two different paths from A to B are different morphisms even if they represent "the same relationship" in some intended interpretation. To add equations, you take a quotient of the free category.

Incorrect. The correct answer is B. The free category on G takes all finite directed paths (including length-0 paths as identities) as morphisms, with composition given by path concatenation. Just taking the edges (A) would not give a category because edges cannot be composed unless you add paths. The free category is the "most general" category with G as its underlying graph.