Hom-set
Interfaces, method collections
_ _ ___ __ __ ____ _____ _____ ____
| | | |/ _ \| \/ | / ___|| ____|_ _/ ___|
| |_| | | | | |\/| | _____ \___ \| _| | | \___ \
| _ | |_| | | | | |_____| ___) | |___ | | ___) |
|_| |_|\___/|_| |_| |____/|_____| |_| |____/
Having explored domains and codomains - the starting and ending points of morphisms - we now arrive at the next concept in category theory: the hom-set[1]. If domains and codomains tell us where individual morphisms go, hom-sets reveal the complete picture by collecting all possible morphisms between any two objects.
When we understand domains and codomains, we know that:
- A morphism
f: A -> Bstarts at objectA(domain) and ends at objectB(codomain) - We can compose morphisms when domains and codomains align properly
- Each morphism has exactly one domain and one codomain
But this raises natural questions:
- How many different morphisms exist from
AtoB? - What is the structure of all these morphisms together?
Hom-sets provide the complete answer by organizing all morphisms between two objects into structured collections that reveal the deep patterns underlying category theory. They transform category theory from a study of individual morphisms into a systematic investigation of morphism spaces.
Formal definition #
For any category C and objects A, B in C, the hom-set Hom_C(A, B) (or simply Hom(A, B) when the category is clear) is the collection of all morphisms from A to B[1].
For a category C and objects A, B ∈ Ob(C):
Hom_C(A, B) = {f : A → B | f is a morphism in C}
Hom-set Properties #
-
Disjointness: For distinct pairs of objects, hom-sets are disjoint (morphisms are typed by domain and codomain):
If (A, B) ≠ (A', B'), then Hom(A, B) ∩ Hom(A', B') = ∅ -
Composition: Morphisms in hom-sets can be composed when domains and codomains align:
For f ∈ Hom(A, B), g ∈ Hom(B, C), their composition g ∘ f ∈ Hom(A, C) -
Identity: Each object has an identity morphism:
For any object A, there exists id_A ∈ Hom(A, A) -
Associativity: Composition of morphisms is associative:
For f ∈ Hom(A, B), g ∈ Hom(B, C), h ∈ Hom(C, D): (h ∘ g) ∘ f = h ∘ (g ∘ f)
What makes hom-sets different is that they organize all morphisms systematically:
Individual Morphism Perspective:
f: A -> B - "There exists a morphism from A to B"
Hom-set Perspective:
Hom(A, B) = {f₁, f₂, f₃, ...} - "The complete collection of all morphisms from A to B"
There is a special case of the hom-set we should emphasize as well. It's the case where in Hom(A, B), A and B are the same.
Self-hom-sets #
(Endomorphism Sets)
A self-hom-set or endomorphism set Hom(A, A) is the collection of all morphisms from an object A to itself. These morphisms are called endomorphisms and have special properties that make them particularly important in programming. They represent "operations that transform something while preserving its type" - a pattern that appears everywhere in programming, from data processing pipelines to state management systems.
Definition #
For any object A in category C:
Hom(A, A) = {f : A → A | f is a morphism in C}
Self-hom-set Properties:
-
Always Contains Identity
Every self-hom-set contains the identity morphism:
id_A ∈ Hom(A, A)for any objectAid_A ∘ f = f = f ∘ id_Afor anyf ∈ Hom(A, A)
-
May Contain Invertible Elements
Some endomorphisms have inverses, making them automorphisms[2]:
f ∈ Hom(A, A)is an automorphism if there existsf⁻¹ ∈ Hom(A, A)such thatf ∘ f⁻¹ = id_A = f⁻¹ ∘ f
Examples #
Complete Interface Specification #
In programming, knowing that a function has type string -> number tells us the domain and codomain, but doesn't tell us what functions are actually available:
// Domain: string, Codomain: number
// But what are ALL the possible functions?
const parse: (s: string) => number = s => Number(s);
const getLength: (s: string) => number = s => s.length;
const getCharCode: (s: string) => number = s => s.charCodeAt(0);
const alwaysZero: (s: string) => number = s => 0;
// The hom-set Hom(string, number) contains ALL of these and infinitely more!
Compositional Understanding #
Hom-sets reveal how composition works systematically across entire categories:
-- Choose concrete types for illustration
type A = Int
type B = String
type C = Int
-- Concrete functions
f :: A -> B
f = show
g :: B -> C
g = length
-- Composition example
composed :: A -> C
composed = g . f
-- Hom-set perspective
-- Hom(A, B) contains all functions A -> B
-- Hom(B, C) contains all functions B -> C
-- Composition gives us: Hom(A, B) × Hom(B, C) -> Hom(A, C)
-- This reveals composition as a fundamental operation on hom-sets!
Type System Foundations #
In programming languages, hom-sets correspond directly to function types:
// In C#, this delegate type represents a hom-set
Func<string, int> // represents Hom(string, int)
// All possible functions from string to int:
Func<string, int> parser = s => int.Parse(s);
Func<string, int> length = s => s.Length;
Func<string, int> hash = s => s.GetHashCode();
// The type Func<string, int> IS the hom-set Hom(string, int)
Functions from Type to Itself #
-- Self-hom-set Hom(Int, Int) contains:
import Data.Char (toUpper)
increment :: Int -> Int
increment x = x + 1
double :: Int -> Int
double x = x * 2
negate' :: Int -> Int
negate' x = -x
identity :: Int -> Int
identity x = x -- This is id_Int
-- Composition within the self-hom-set
doubleIncrement :: Int -> Int
doubleIncrement = double . increment -- Still Int -> Int
-- String transformations - Hom(String, String)
reverse' :: String -> String
reverse' = reverse
uppercase :: String -> String
uppercase = map toUpper
addExclamation :: String -> String
addExclamation s = s ++ "!"
-- Composition
shout :: String -> String
shout = addExclamation . uppercase . reverse'
Self-Transforming Functions #
// Self-hom-set Hom(number[], number[])
type ArrayTransform = (arr: number[]) => number[];
const sort: ArrayTransform = (arr) => [...arr].sort((a, b) => a - b);
const reverse: ArrayTransform = (arr) => [...arr].reverse();
const double: ArrayTransform = (arr) => arr.map(x => x * 2);
const identity: ArrayTransform = (arr) => arr; // id_number[]
// Object state transformations - Hom(State, State)
interface State {
count: number;
message: string;
}
type StateTransform = (state: State) => State;
const incrementCount: StateTransform = (state) => ({
...state,
count: state.count + 1
});
const updateMessage: StateTransform = (state) => ({
...state,
message: "Updated!"
});
const reset: StateTransform = (state) => ({
count: 0,
message: ""
});
// Composition of state transformations
const incrementAndUpdate: StateTransform = (state) =>
updateMessage(incrementCount(state));
Self-Transforming Delegates #
// Self-hom-set Hom(List<int>, List<int>)
using System;
using System.Collections.Generic;
using System.Linq;
Func<List<int>, List<int>> sort = list => list.OrderBy(x => x).ToList();
Func<List<int>, List<int>> reverse = list => { var copy = new List<int>(list); copy.Reverse(); return copy; };
Func<List<int>, List<int>> doubleFn = list => list.Select(x => x * 2).ToList();
Func<List<int>, List<int>> identity = list => new List<int>(list);
// String transformations - Hom(string, string)
Func<string, string> upperCase = s => s.ToUpper();
Func<string, string> addPrefix = s => ">> " + s;
Func<string, string> trim = s => s.Trim();
// Chain transformations
Func<string, string> process = s => addPrefix(upperCase(trim(s)));
Triangle Transformations example #
Let's consider the category of triangles in the plane, where objects are specific triangles (three non‑collinear points with their convex hull), and morphisms are invertible transformations of the plane restricted to those triangles (i.e., affine maps sending one triangle exactly onto another).
Objects: Different triangles in the plane
T1: An equilateral triangleT2: A right triangleT3: An isosceles triangleT4: A scalene triangle
Morphisms: Invertible transformations (compositions of linear maps and translations) that map one triangle onto another
Hom(T1, T2): Transformations from equilateral to right triangle
T1 (Equilateral) T2 (Right triangle)
△ |\
/ \ | \
/ \ | \
/ \ |___\
/_______\
For triangles viewed as specific subsets of ℝ², any two triangles are affinely equivalent. The hom‑set consists of exactly 6 affine transformations, one for each permutation of how the three vertices of T1 map to the three vertices of T2. Each choice determines a unique invertible affine map.
f₁: Shear transformation that skews the equilateral trianglef₂: Non-uniform scaling that stretches one sidef₃: Rotation + scaling + shearing combinationf₄: Affine transformation preserving some vertex relationships- ... etc
Hom(T1, T1): Self-transformations of equilateral triangle (Endomorphisms)
T1 (Equilateral triangle)
△
/A\
/ \
/ \
/B_____C\
Self-hom-set Hom(T1, T1) contains:
id: Identity transformation (do nothing)r₁: Rotate 120° clockwise around centerr₂: Rotate 240° clockwise around centers₁: Reflect across altitude through vertex As₂: Reflect across altitude through vertex Bs₃: Reflect across altitude through vertex C- (for an equilateral triangle) exactly the 6 symmetries listed above; no other affine self‑maps send the triangle to itself
Composition
Composing transformations through hom-sets:
T1 --f--> T2 --g--> T3
Where:
f ∈ Hom(T1, T2): Transform equilateral to right triangleg ∈ Hom(T2, T3): Transform right triangle to isosceles triangleg ∘ f ∈ Hom(T1, T3): Direct transformation from equilateral to isosceles
△ shear |\ stretch △
/ \ ------> | \ -------> / \
/ \ | \ / \
/_____\ |___\ /_____\
T1 T2 T3
Composition associativity:
For transformations
f: T1 → T2,
g: T2 → T3,
h: T3 → T4: (h ∘ g) ∘ f = h ∘ (g ∘ f)
This means: applying f, then g, then h gives the same result as
applying f, then (the composition of g and h)
Identity preservation:
For any transformation f: T1 → T2:
f ∘ id_T1 = f = id_T2 ∘ f
This means: doing nothing to T1 then applying f is the same as f,
and applying f then doing nothing to T2 is also the same as f
Automorphisms: Triangle Symmetries:
Automorphisms of equilateral triangle T1:
These are transformations that can be "undone":
r₁: 120° rotation (inverse:r₂, 240° rotation)r₂: 240° rotation (inverse:r₁, 120° rotation)s₁: reflection (inverse:s₁itself)s₂: reflection (inverse:s₂itself)s₃: reflection (inverse:s₃itself)id: identity (inverse:iditself)
These form the dihedral group D₃: {id, r₁, r₂, s₁, s₂, s₃}
Transformations that are not automorphisms of T1 in this category:
- Uniform scaling with factor
≠ 1(mapsT1to a different triangle) - Non‑uniform (anisotropic) scaling or shear (changes shape; image
≠ T1)
Visualizing Hom-sets #
1. Objects A and B with hom-set Hom(A, B):
A ----f₁---> B
│ ↑
│─f₂─────────│
│ │
│─f₃─────────│
│ │
└─f₄─────────┘
Hom(A, B) = {f₁, f₂, f₃, f₄, ...}
2. Category C with three objects A, B, C:
f₁, f₂, f₃
A ═══════════════→ B
║ ║
║g₁ ║h₁, h₂
║g₂ ║h₃
║ ↓
↓ k₁, k₂ C
╚═══════════════════→
Hom(A, B) = {f₁, f₂, f₃}
Hom(A, C) = {g₁, g₂}
Hom(B, C) = {h₁, h₂, h₃}
Hom(A, A) = {id_A, ...}
Hom(B, B) = {id_B, ...}
Hom(C, C) = {id_C, ...}
3. Composition: Hom(A, B) × Hom(B, C) → Hom(A, C)
A -----f---> B ----g ---> C
↗
g ∘ f ╱
╱
╱
╱
A ---------------------> C
Given: f ∈ Hom(A, B) and g ∈ Hom(B, C)
Result: g ∘ f ∈ Hom(A, C)
4. Hom(A, B) as a "space" of functions:
Hom(A, B) = Function Space
┌─────────────────────────────────┐
│ f₁: A → B │
│ f₂: A → B │
│ f₃: A → B │
│ f₄: A → B │
│ ... │
│ fₙ: A → B │
└─────────────────────────────────┘
↓ composition ↓
Hom(A, B) × Hom(B, C) → Hom(A, C)
┌─────────────┐ ┌─────────────┐
│ functions │ × │ functions │
│ A → B │ │ B → C │
└─────────────┘ └─────────────┘
↓
┌─────────────────────────────────┐
│ Hom(A, C) │
│ (composed functions) │
└─────────────────────────────────┘
5. Every object has identity in its self-hom-set:
A ⟲ id_A B ⟲ id_B C ⟲ id_C
Hom(A, A) contains id_A (and potentially other endomorphisms)
Hom(B, B) contains id_B
Hom(C, C) contains id_C
Identity Law: f ∘ id_A = f = id_B ∘ f
For f ∈ Hom(A, B)
6. Self-hom-set Hom(A, A) - Endomorphisms of A:
A ⟲ id_A (identity - always present)
│ ⟲ f₁ (some endomorphism)
│ ⟲ f₂ (another endomorphism)
│ ⟲ f₃ (yet another endomorphism)
└ ⟲ ...
Conclusion #
Hom-sets bridge the gap between the concrete (individual functions we write) and the abstract (the categorical patterns that make functional programming work). Every time we write a function in a programming language, you're working with elements of hom-sets. Every time we compose functions, you're using the fundamental operation that makes hom-sets into a coherent structure.
Source code #
Reference implementation (opens in a new tab)
Notes
- We assume the category C is locally small: for any objects A, B the collection Hom_C(A, B) is a set (not a proper class). · Back