Every category embeds fully and faithfully into its presheaf category [Cop, Set]. The Yoneda embedding Y sends each object a to its hom-functor C(a, –), and no information is lost: distinct morphisms stay distinct, and every natural transformation between hom-functors comes from a morphism in C.
The embedding: objects become hom-functors
Fix a category C. For each object a, the mapping C(a, –) is a covariant functor from C to Set. The Yoneda embedding Y maps each object a to this functor, and each morphism f : a → b to a natural transformation between the corresponding hom-functors. We build a small category (a 3-object graph) and embed it.
Scheme
; A small category with 3 objects: A, B, C; Morphisms: f: A->B, g: B->C, gf: A->C (composition); Plus identity morphisms.
(define objects '(A B C))
; hom(x, y): list all morphisms from x to y
(define (hom x y)
(cond
((and (eq? x 'A) (eq? y 'A)) '(id-A))
((and (eq? x 'B) (eq? y 'B)) '(id-B))
((and (eq? x 'C) (eq? y 'C)) '(id-C))
((and (eq? x 'A) (eq? y 'B)) '(f))
((and (eq? x 'B) (eq? y 'C)) '(g))
((and (eq? x 'A) (eq? y 'C)) '(gf))
(else '())))
; The Yoneda embedding sends object a to the functor C(a, -).; That functor maps each object x to the set hom(a, x).
(define (yoneda-embed a)
(lambda (x) (hom a x)))
; Embed each object and display its functor's values
(for-each
(lambda (a)
(display "Y(") (display a) (display "): ")
(for-each
(lambda (x)
(display x) (display "->")
(display ((yoneda-embed a) x)) (display " "))
objects)
(newline))
objects)
; Each row is a different functor. Distinct objects give distinct functors.
Python
# 3-object category: A, B, C# Morphisms: f: A->B, g: B->C, gf: A->C, plus identitiesdef hom(x, y):
table = {
("A","A"): ["id_A"], ("B","B"): ["id_B"], ("C","C"): ["id_C"],
("A","B"): ["f"], ("B","C"): ["g"], ("A","C"): ["gf"],
}
return table.get((x, y), [])
def yoneda_embed(a):
"""Y(a) = the functor C(a, -)"""return {x: hom(a, x) for x in ["A", "B", "C"]}
for a in ["A", "B", "C"]:
row = " ".join(f"{x}->{yoneda_embed(a)[x]}"for x in ["A","B","C"])
print(f"Y({a}): {row}")
Fully faithful: no information lost
A functor is faithful if it's injective on hom-sets (distinct morphisms stay distinct), and full if it's surjective (every natural transformation between the image functors comes from a morphism). The Yoneda embedding is both. The proof is the Yoneda lemma itself: natural transformations [C, Set](C(a, –), C(b, –)) are in bijection with C(b, a). Reversing the direction gives the contravariant version.
Scheme
; Fully faithful means: the set of natural transformations; between Y(a) and Y(b) is isomorphic to hom(a, b).;; Yoneda lemma: Nat(C(a,-), C(b,-)) โ C(b, a); (substitute F = C(b,-) into the Yoneda lemma); For our 3-object category:; Nat(Y(A), Y(B)) โ hom(B, A) = {} (empty โ no morphism B->A); Nat(Y(A), Y(C)) โ hom(C, A) = {} (empty); Nat(Y(B), Y(A)) โ hom(A, B) = {f} (one morphism); Check: morphisms in C match nat-trans count
(define (nat-trans-count a b)
(length (hom b a))) ; Yoneda: reversed!
(display "Nat(Y(A), Y(B)) count = ") (display (nat-trans-count 'A 'B))
(display " hom(B,A) = ") (display (hom 'B 'A)) (newline)
(display "Nat(Y(B), Y(A)) count = ") (display (nat-trans-count 'B 'A))
(display " hom(A,B) = ") (display (hom 'A 'B)) (newline)
(display "Nat(Y(A), Y(C)) count = ") (display (nat-trans-count 'A 'C))
(display " hom(C,A) = ") (display (hom 'C 'A)) (newline)
(display "Nat(Y(B), Y(C)) count = ") (display (nat-trans-count 'B 'C))
(display " hom(C,B) = ") (display (hom 'C 'B)) (newline)
; Bijection holds everywhere: the embedding is fully faithful.
Contravariant Yoneda: the co-Yoneda embedding
The dual version uses the contravariant hom-functor C(–, a). This embeds C into the presheaf category [Cop, Set]. The isomorphism becomes: Nat(C(–, a), C(–, b)) ≅ C(a, b). No reversal this time: the directions match.
Scheme
; Co-Yoneda embedding: Y^op(a) = C(-, a); This is a contravariant functor: given h: x -> y,; C(-, a) sends h to precomposition C(y, a) -> C(x, a).
(define (co-yoneda-embed a)
(lambda (x) (hom x a)))
; Display the contravariant embedding
(for-each
(lambda (a)
(display "Y^op(") (display a) (display "): ")
(for-each
(lambda (x)
(display x) (display "->")
(display ((co-yoneda-embed a) x)) (display " "))
objects)
(newline))
objects)
; Co-Yoneda: Nat(C(-,a), C(-,b)) โ C(a, b) (no reversal)
(newline)
(display "Nat(Y^op(A), Y^op(B)) โ hom(A,B) = ")
(display (hom 'A 'B)) (newline)
(display "Nat(Y^op(B), Y^op(C)) โ hom(B,C) = ")
(display (hom 'B 'C))
Python
# Co-Yoneda: Y^op(a) = C(-, a)def co_yoneda_embed(a):
return {x: hom(x, a) for x in ["A", "B", "C"]}
for a in ["A", "B", "C"]:
row = " ".join(f"{x}->{co_yoneda_embed(a)[x]}"for x in ["A","B","C"])
print(f"Y^op({a}): {row}")
# Co-Yoneda: Nat(C(-,a), C(-,b)) โ hom(a, b)print(f"\nNat(Y^op(A), Y^op(B)) โ hom(A,B) = {hom('A','B')}")
print(f"Nat(Y^op(B), Y^op(C)) โ hom(B,C) = {hom('B','C')}")
Preserving and reflecting isomorphisms
A fully faithful functor both preserves and reflects isomorphisms. If a ≅ b in C, then Y(a) ≅ Y(b) in [C, Set] (preservation). Conversely, if Y(a) ≅ Y(b), then a ≅ b (reflection). Two objects are isomorphic if and only if they "look the same from the outside" — they have the same pattern of incoming and outgoing morphisms.
Scheme
; Add an isomorphic copy: object D with iso: B <-> D; i: B->D, j: D->B, j.i = id-B, i.j = id-D
(define (hom2 x y)
(cond; Original category
((and (eq? x 'A) (eq? y 'A)) '(id-A))
((and (eq? x 'B) (eq? y 'B)) '(id-B))
((and (eq? x 'C) (eq? y 'C)) '(id-C))
((and (eq? x 'A) (eq? y 'B)) '(f))
((and (eq? x 'B) (eq? y 'C)) '(g))
((and (eq? x 'A) (eq? y 'C)) '(gf))
; D is isomorphic to B
((and (eq? x 'D) (eq? y 'D)) '(id-D))
((and (eq? x 'B) (eq? y 'D)) '(i))
((and (eq? x 'D) (eq? y 'B)) '(j))
; Composites through D
((and (eq? x 'A) (eq? y 'D)) '(if)) ; i . f
((and (eq? x 'D) (eq? y 'C)) '(gj)) ; g . j
(else '())))
(define objects2 '(A B C D))
; Y(B) and Y(D) should look the same (same hom-set sizes)
(display "Y(B): ")
(for-each (lambda (x) (display x) (display "->")
(display (length (hom2 'B x))) (display " ")) objects2)
(newline)
(display "Y(D): ")
(for-each (lambda (x) (display x) (display "->")
(display (length (hom2 'D x))) (display " ")) objects2)
(newline)
; Same profile => isomorphic functors => B โ D reflected back
(display "B โ D in C? hom(B,D)=") (display (hom2 'B 'D))
(display " hom(D,B)=") (display (hom2 'D 'B))
(display " Yes: i and j are mutual inverses.")
In Haskell: CPS is the Yoneda embedding
In Haskell, the Yoneda embedding becomes: forall x. (a -> x) -> (b -> x) ≅ b -> a. This is continuation-passing style. Given a function btoa :: b -> a, you construct a polymorphic function that takes any continuation a -> x and pre-composes it. Recovering btoa is just applying the identity continuation.
Scheme
; CPS encoding = Yoneda embedding in Hask; forall x. (a -> x) -> (b -> x) โ (b -> a);; Given btoa: b -> a, build the CPS version:; fromY k b = k (btoa b);; Recover btoa: fromY identity
(define (btoa b)
(+ b 10)) ; example: add 10; CPS-encode it: take any continuation k, apply after btoa
(define (from-y k)
(lambda (b) (k (btoa b))))
; Use with different continuations
(display "k=identity: ") (display ((from-y (lambda (x) x)) 5)) (newline)
(display "k=double: ") (display ((from-y (lambda (x) (* x 2))) 5)) (newline)
(display "k=show: ") (display ((from-y number->string) 5)) (newline)
; Recover the original function: apply k=identity
(display "recovered btoa(5) = ") (display ((from-y (lambda (x) x)) 5))
; 15 โ same as (btoa 5)
Python
# CPS = Yoneda embedding in programming# forall x. (a -> x) -> (b -> x) โ (b -> a)def btoa(b):
return b + 10def from_y(k):
"""CPS-encode btoa: take continuation k, pre-compose with btoa"""returnlambda b: k(btoa(b))
print(f"k=identity: {from_y(lambda x: x)(5)}")
print(f"k=double: {from_y(lambda x: x*2)(5)}")
print(f"k=str: {from_y(str)(5)}")
# Recover original: use identity as continuation
recovered = from_y(lambda x: x)
print(f"recovered btoa(5) = {recovered(5)}") # 15
Preorder example: the embedding as implication
In a preorder (where hom-sets are either empty or singletons), the Yoneda embedding becomes: a ≤ b if and only if for all x, x ≤ a implies x ≤ b. Knowing all the morphisms into an object completely determines its position in the order. This is the "behavioral" characterization: an object is defined by what maps into it.
Scheme
; Preorder: 1 โค 2 โค 3; hom(x,y) = {*} if x โค y, else {}
(define (hom-pre x y)
(if (<= x y) '(*) '()))
; Y(a) maps each x to hom(a, x)
(define (y-pre a)
(map (lambda (x) (list x (hom-pre a x))) '(123)))
(display "Y(1): ") (display (y-pre 1)) (newline)
(display "Y(2): ") (display (y-pre 2)) (newline)
(display "Y(3): ") (display (y-pre 3)) (newline)
; a โค b iff for all x, (x โค a) => (x โค b); Check: is 1 โค 2?
(display "1 โค 2? ")
(display (every (lambda (x)
(or (null? (hom-pre x 1)) ; x โค 1 is false, so implication holds
(not (null? (hom-pre x 2))))) ; x โค 2 is true
'(123)))
(newline)
; Check: is 3 โค 1?
(display "3 โค 1? ")
(display (every (lambda (x)
(or (null? (hom-pre x 3))
(not (null? (hom-pre x 1)))))
'(123)))
; #f โ 3 โค 3 but not 3 โค 1
Notation reference
Blog / Haskell
Scheme
Meaning
C(a, –)
(yoneda-embed a)
Covariant hom-functor (representable)
C(–, a)
(co-yoneda-embed a)
Contravariant hom-functor (presheaf)
Y : C → [C, Set]
(yoneda-embed a)
Yoneda embedding functor
[C, Set](C(a,–), C(b,–)) ≅ C(b,a)
(nat-trans-count a b)
Fully faithful: nat-trans = morphisms
forall x. (a→x)→(b→x) ≅ b→a
(from-y k)
CPS encoding (Haskell version)
a ≤ b ⇔ ∀x. x≤a ⇒ x≤b
(every ... '(1 2 3))
Preorder embedding as implication
Neighbors
Milewski chapters
๐ Chapter 14 โ The Yoneda Lemma: the isomorphism this embedding relies on
(next) Chapter 16 โ Limits and Colimits
Paper pages that use these concepts
๐ Leinster 2021 โ uses representable functors and the Yoneda perspective
๐ Capucci 2021 โ parametrised optics live in presheaf categories
The blog post works in Haskell, where the Yoneda embedding manifests as the polymorphic isomorphism forall x. (a -> x) -> (b -> x) ≅ b -> a. This page uses explicit finite categories in Scheme, which makes the hom-sets visible as concrete lists. The trade-off: you can see the bijection by counting, but you lose the polymorphic elegance. The blog post also discusses naturality of the Yoneda isomorphism in both arguments (forming a higher-order natural transformation between evaluation and hom-pairing). That machinery requires 2-categorical language and is omitted here. The preorder example is faithful to the original. The CPS example is the same construction Milewski gives, translated from Haskell tabulate/index style to explicit lambda application.
Ready for the real thing? Read the blog post. Start with the fully faithful proof, then trace the CPS encoding.
Yoneda embedding