Kan Extensions

Left and right Kan extensions in enriched categories.

kan_extensions

Kan extensions: generalized (re)indexing of morphisms.

The left Kan extension of a morphism R: A → B along a map p: A → A' produces a morphism Lan_p(R): A' → B via:

(Lan_p R)(a', b) = ⋁{a : p(a) = a'} R(a, b)

The right Kan extension uses meet (⋀) instead of join (⋁):

(Ran_p R)(a', b) = ⋀{a : p(a) = a'} R(a, b)

Marginalization is a special case: left Kan extension along a projection π: A₁×...×Aₙ → A_{i₁}×...×A_{iₖ}.

This module provides:

ObjectMap (abstract) — maps between finite sets
├── Projection       — π: A₁×...×Aₙ → some subset of components
└── Inclusion        — ι: A → A + B (coproduct injection)

left_kan()  — left Kan extension
right_kan() — right Kan extension

ObjectMap

Bases: ABC

An abstract deterministic map between finite sets.

Represents a function p: A → A' at the element level, used as the map along which to compute Kan extensions.

source abstractmethod property

source: SetObject

The source object A.

target abstractmethod property

target: SetObject

The target object A'.

apply abstractmethod

apply(source_idx: tuple[int, ...]) -> tuple[int, ...]

Map a source index to a target index.

PARAMETER	DESCRIPTION
source_idx	An element of A as a multi-index. TYPE: tuple[int, ...]

RETURNS	DESCRIPTION
tuple[int, ...]	The corresponding element of A'.

Source code in src/quivers/enriched/kan_extensions.py

@abstractmethod
def apply(self, source_idx: tuple[int, ...]) -> tuple[int, ...]:
    """Map a source index to a target index.

    Parameters
    ----------
    source_idx : tuple[int, ...]
        An element of A as a multi-index.

    Returns
    -------
    tuple[int, ...]
        The corresponding element of A'.
    """
    ...

fiber_indices

fiber_indices(target_idx: tuple[int, ...]) -> list[tuple[int, ...]]

Return all source indices that map to the given target index.

PARAMETER	DESCRIPTION
target_idx	An element of A'. TYPE: tuple[int, ...]

RETURNS	DESCRIPTION
list[tuple[int, ...]]	All a ∈ A such that p(a) = target_idx.

Source code in src/quivers/enriched/kan_extensions.py

def fiber_indices(self, target_idx: tuple[int, ...]) -> list[tuple[int, ...]]:
    """Return all source indices that map to the given target index.

    Parameters
    ----------
    target_idx : tuple[int, ...]
        An element of A'.

    Returns
    -------
    list[tuple[int, ...]]
        All a ∈ A such that p(a) = target_idx.
    """
    result: list[tuple[int, ...]] = []
    for src_idx in itertools.product(*(range(s) for s in self.source.shape)):
        if self.apply(src_idx) == target_idx:
            result.append(src_idx)
    return result

Projection

Projection(product: ProductSet, keep_indices: tuple[int, ...])

Bases: ObjectMap

Projection from a product to a subset of its components.

Given ProductSet(A₁, ..., Aₙ), projects onto the components at the specified indices: π(a₁, ..., aₙ) = (a_{i₁}, ..., a_{iₖ}).

PARAMETER	DESCRIPTION
product	The source product set. TYPE: ProductSet
keep_indices	Indices of the components to keep (0-based). TYPE: tuple[int, ...]

Source code in src/quivers/enriched/kan_extensions.py

def __init__(self, product: ProductSet, keep_indices: tuple[int, ...]) -> None:
    if not isinstance(product, ProductSet):
        raise TypeError(
            f"Projection requires ProductSet, got {type(product).__name__}"
        )
    n = len(product.components)
    for idx in keep_indices:
        if not 0 <= idx < n:
            raise ValueError(f"component index {idx} out of range [0, {n})")
    self._product = product
    self._keep_indices = keep_indices
    self._drop_indices = tuple((i for i in range(n) if i not in keep_indices))
    kept = [product.components[i] for i in keep_indices]
    if len(kept) == 1:
        self._target = kept[0]
    else:
        self._target = ProductSet(components=tuple(kept))
    self._dim_offsets: list[int] = []
    offset = 0
    for comp in product.components:
        self._dim_offsets.append(offset)
        offset += comp.ndim

source property

source: ProductSet

The source product set.

target property

target: SetObject

The target (projected) set.

keep_indices property

keep_indices: tuple[int, ...]

Indices of the kept components.

drop_indices property

drop_indices: tuple[int, ...]

Indices of the dropped (marginalized) components.

apply

apply(source_idx: tuple[int, ...]) -> tuple[int, ...]

Project by keeping only the selected component indices.

Source code in src/quivers/enriched/kan_extensions.py

def apply(self, source_idx: tuple[int, ...]) -> tuple[int, ...]:
    """Project by keeping only the selected component indices."""
    result: list[int] = []
    for comp_idx in self._keep_indices:
        comp = self._product.components[comp_idx]
        offset = self._dim_offsets[comp_idx]
        for d in range(comp.ndim):
            result.append(source_idx[offset + d])
    return tuple(result)

Inclusion

Inclusion(coproduct: CoproductSet, component_index: int)

Bases: ObjectMap

Coproduct inclusion ι_k: Aₖ → A₁ + ... + Aₙ.

Embeds the k-th component of a CoproductSet into the full set.

PARAMETER	DESCRIPTION
coproduct	The target coproduct set. TYPE: CoproductSet
component_index	Which component to include (0-based). TYPE: int

Source code in src/quivers/enriched/kan_extensions.py

def __init__(self, coproduct: CoproductSet, component_index: int) -> None:
    if not isinstance(coproduct, CoproductSet):
        raise TypeError(
            f"Inclusion requires CoproductSet, got {type(coproduct).__name__}"
        )
    n = len(coproduct.components)
    if not 0 <= component_index < n:
        raise ValueError(f"component_index {component_index} out of range [0, {n})")
    self._coproduct = coproduct
    self._component_index = component_index
    self._component = coproduct.components[component_index]
    self._offset = coproduct.offset(component_index)

source property

source: SetObject

The source component.

target property

target: CoproductSet

The target coproduct set.

apply

apply(source_idx: tuple[int, ...]) -> tuple[int, ...]

Embed into the coproduct with offset.

Source code in src/quivers/enriched/kan_extensions.py

def apply(self, source_idx: tuple[int, ...]) -> tuple[int, ...]:
    """Embed into the coproduct with offset."""
    (flat_idx,) = source_idx
    return (self._offset + flat_idx,)

left_kan

left_kan(morph: Morphism, along: ObjectMap, algebra: Algebra | None = None) -> ObservedMorphism

Left Kan extension of a morphism along an object map.

Computes: (Lan_p R)(a', b) = ⋁{a : p(a) = a'} R(a, b)

PARAMETER	DESCRIPTION
morph	The morphism R: A → B. TYPE: Morphism
along	The map p: A → A'. TYPE: ObjectMap
algebra	The enrichment algebra. Defaults to PRODUCT_FUZZY. TYPE: Algebra or None DEFAULT: None

RETURNS	DESCRIPTION
ObservedMorphism	The left Kan extension Lan_p(R): A' → B.

Source code in src/quivers/enriched/kan_extensions.py

def left_kan(
    morph: Morphism, along: ObjectMap, algebra: Algebra | None = None
) -> ObservedMorphism:
    """Left Kan extension of a morphism along an object map.

    Computes: (Lan_p R)(a', b) = ⋁{a : p(a) = a'} R(a, b)

    Parameters
    ----------
    morph : Morphism
        The morphism R: A → B.
    along : ObjectMap
        The map p: A → A'.
    algebra : Algebra or None
        The enrichment algebra. Defaults to PRODUCT_FUZZY.

    Returns
    -------
    ObservedMorphism
        The left Kan extension Lan_p(R): A' → B.
    """
    q = algebra if algebra is not None else PRODUCT_FUZZY
    target = along.target
    codomain = morph.codomain
    result_shape = (*target.shape, *codomain.shape)
    result = torch.full(result_shape, q.zero)
    source_tensor = morph.tensor.detach()
    for tgt_idx in itertools.product(*(range(s) for s in target.shape)):
        fiber = along.fiber_indices(tgt_idx)
        if not fiber:
            continue
        slices = torch.stack([source_tensor[src_idx] for src_idx in fiber])
        joined = q.join(slices, dim=0)
        result[tgt_idx] = joined
    return observed(target, codomain, result, algebra=q)

right_kan

right_kan(morph: Morphism, along: ObjectMap, algebra: Algebra | None = None) -> ObservedMorphism

Right Kan extension of a morphism along an object map.

Computes: (Ran_p R)(a', b) = ⋀{a : p(a) = a'} R(a, b)

PARAMETER	DESCRIPTION
morph	The morphism R: A → B. TYPE: Morphism
along	The map p: A → A'. TYPE: ObjectMap
algebra	The enrichment algebra. Defaults to PRODUCT_FUZZY. TYPE: Algebra or None DEFAULT: None

RETURNS	DESCRIPTION
ObservedMorphism	The right Kan extension Ran_p(R): A' → B.

Source code in src/quivers/enriched/kan_extensions.py

def right_kan(
    morph: Morphism, along: ObjectMap, algebra: Algebra | None = None
) -> ObservedMorphism:
    """Right Kan extension of a morphism along an object map.

    Computes: (Ran_p R)(a', b) = ⋀{a : p(a) = a'} R(a, b)

    Parameters
    ----------
    morph : Morphism
        The morphism R: A → B.
    along : ObjectMap
        The map p: A → A'.
    algebra : Algebra or None
        The enrichment algebra. Defaults to PRODUCT_FUZZY.

    Returns
    -------
    ObservedMorphism
        The right Kan extension Ran_p(R): A' → B.
    """
    q = algebra if algebra is not None else PRODUCT_FUZZY
    target = along.target
    codomain = morph.codomain
    result_shape = (*target.shape, *codomain.shape)
    result = torch.full(result_shape, q.unit)
    source_tensor = morph.tensor.detach()
    for tgt_idx in itertools.product(*(range(s) for s in target.shape)):
        fiber = along.fiber_indices(tgt_idx)
        if not fiber:
            continue
        slices = torch.stack([source_tensor[src_idx] for src_idx in fiber])
        met = q.meet(slices, dim=0)
        result[tgt_idx] = met
    return observed(target, codomain, result, algebra=q)