Categorical algebra

Free diagrams in a category.

A free diagram in a category is a diagram whose shape is a free category. Examples include the empty diagram, pairs of objects, discrete diagrams, parallel morphisms, spans, and cospans. Limits and colimits are most commonly taken over free diagrams.

Cospan of morphisms in a category.

A common special case of Multicospan. See also Span.

Discrete diagram: a diagram whose only morphisms are identities.

Abstract type for free diagram of fixed shape.

Multicospan of morphisms in a category.

A multicospan is like a Cospan except that it may have a number of legs different than two. A limit of this shape is a pullback.

Multispan of morphisms in a category.

A multispan is like a Span except that it may have a number of legs different than two. A colimit of this shape is a pushout.

Parallel morphims in a category.

Parallel morphisms are just morphisms with the same domain and codomain. A (co)limit of this shape is a (co)equalizer.

For the common special case of two morphisms, see ParallelPair.

Pair of parallel morphisms in a category.

A common special case of ParallelMorphisms.

Span of morphims in a category.

A common special case of Multispan. See also Cospan.

SquareDiagram(top, bottom, left, right)

creates a square diagram in a category, which forms the 2-cells of the double category Sq(C). The four 1-cells are given in top, bottom, left, right order, to match the GAT of a double category.

Bundle together legs of a multi(co)span.

For example, calling bundle_legs(span, SVector((1,2),(3,4))) on a multispan with four legs gives a span whose left leg bundles legs 1 and 2 and whose right leg bundles legs 3 and 4. Note that in addition to bundling, this function can also permute legs and discard them.

The bundling is performed using the universal property of (co)products, which assumes that these (co)limits exist.

Limits and colimits in a category.

Abstract type for colimit in a category.

The standard concrete subtype is Colimit, although for computational reasons certain categories may use different subtypes to include extra data.

Abstract type for limit in a category.

The standard concrete subtype is Limit, although for computational reasons certain categories may use different subtypes to include extra data.

Colimit in a category.

Limit in a category.

Colimit of a diagram.

To define colimits in a category with objects Ob, override the method colimit(::FreeDiagram{Ob}) for general colimits or colimit(::D) with suitable type D <: FixedShapeFreeDiagram{Ob} for colimits of specific shape, such as coproducts or coequalizers.

See also: limit

Compute pullback as composite of product and equalizer.

Compute pushout as composite of coproduct and coequalizer.

Limit of a diagram.

To define limits in a category with objects Ob, override the method limit(::FreeDiagram{Ob}) for general limits or limit(::D) with suitable type D <: FixedShapeFreeDiagram{Ob} for limits of specific shape, such as products or equalizers.

See also: colimit

Pullback of a pair of morphisms with common codomain.

To implement for a type T, define the method limit(::Cospan{T}) and/or limit(::Multicospan{T}) or, if you have already implemented products and equalizers, rely on the default implementation.

Pushout of a pair of morphisms with common domain.

To implement for a type T, define the method colimit(::Span{T}) and/or colimit(::Multispan{T}) or, if you have already implemented coproducts and coequalizers, rely on the default implementation.

Universal property of (co)limits.

Compute the morphism whose existence and uniqueness is guaranteed by the universal property of (co)limits.

See also: limit, colimit.

Coequalizer of morphisms with common domain and codomain.

To implement for a type T, define the method colimit(::ParallelPair{T}) or colimit(::ParallelMorphisms{T}).

Copairing of morphisms: universal property of coproducts/pushouts.

To implement for coproducts of type T, define the method universal(::BinaryCoproduct{T}, ::Cospan{T}) and/or universal(::Coproduct{T}, ::Multicospan{T}) and similarly for pushouts.

Coproduct of objects.

To implement for a type T, define the method colimit(::ObjectPair{T}) and/or colimit(::DiscreteDiagram{T}).

Unique morphism out of an initial object.

To implement for a type T, define the method universal(::Initial{T}, ::SMulticospan{0,T}).

Unique morphism into a terminal object.

To implement for a type T, define the method universal(::Terminal{T}, ::SMultispan{0,T}).

Equalizer of morphisms with common domain and codomain.

To implement for a type T, define the method limit(::ParallelPair{T}) and/or limit(::ParallelMorphisms{T}).

Factor morphism through (co)equalizer, via the universal property.

To implement for equalizers of type T, define the method universal(::Equalizer{T}, ::SMultispan{1,T}). For coequalizers of type T, define the method universal(::Coequalizer{T}, ::SMulticospan{1,T}).

Initial object.

To implement for a type T, define the method colimit(::EmptyDiagram{T}).

Pairing of morphisms: universal property of products/pullbacks.

To implement for products of type T, define the method universal(::BinaryProduct{T}, ::Span{T}) and/or universal(::Product{T}, ::Multispan{T}) and similarly for pullbacks.

Product of objects.

To implement for a type T, define the method limit(::ObjectPair{T}) and/or limit(::DiscreteDiagram{T}).

Terminal object.

To implement for a type T, define the method limit(::EmptyDiagram{T}).

Computing in the category of finite sets and functions.

Function between finite sets.

The function can be defined implicitly by an arbitrary Julia function, in which case it is evaluated lazily, or explictly by a vector of integers. In the latter case, the function (1↦1, 2↦3, 3↦2, 4↦3), for example, is represented by the vector [1,3,2,3].

Function in FinSet defined by a callable Julia object.

To be evaluated lazily unless forced.

Function in FinSet represented explicitly by a vector.

The elements of the set are assumed to be {1,...,n}.

Finite set.

This generic type encompasses the category FinSet of finite sets and functions, through types FinSet{S} where S <: AbstractSet, as well as the skeleton of this category, through the type FinSet{Int}. In the latter case, the object FinSet(n) represents the set {1,...,n}.

Force evaluation of lazy function or relation.

Computing in the category of finite sets and relations, and its skeleton.

The rig of booleans.

This struct is needed because in base Julia, the product of booleans is another boolean, but the sum of booleans is coerced to an integer: true + true == 2.

Object in the category of finite sets and relations.

See also: FinSet.

Binary relation between finite sets.

A morphism in the category of finite sets and relations. The relation can be represented implicitly by an arbitrary Julia function mapping pairs of elements to booleans or explicitly by a matrix (dense or sparse) taking values in the rig of booleans (BoolRig).

Relation in FinRel defined by a callable Julia object.

Relation in FinRel represented by a boolean matrix.

Boolean matrices are also known as logical matrices or relation matrices.

Categories of C-sets and attributed C-sets.

Transformation between attributed C-sets.

A morphism of C-sets is a natural transformation: a transformation between functors C -> Set satisfying the naturality axiom for all morphisms in C. This struct records the data of a transformation; it does not enforce naturality.

The transformation has a component for every object in C. When C-sets have attributes, the data types are assumed to be fixed. Thus, the naturality axiom for data attributes is a commutative triangle, rather than a commutative square.

Is the transformation between C-sets a natural transformation?

Uses the fact that to check whether a transformation is natural, it suffices to check the naturality equation on a generating set of morphisms.

Pullback functorial data migration from one ACSet to another.

Note that this operation is contravariant: the data is transferred from X to Y but the functor, represented by two dictionaries, maps the schema for Y to the schema for X.

When the functor is the identity, this function is equivalent to copy_parts!.

Structured cospans.

This module provides a generic interface for structured cospans with a concrete implementation for attributed C-sets.

Structured cospan.

The first type parameter L encodes a functor L: A → X from the base category A, often FinSet, to a category X with "extra structure." An L-structured cospan is then a cospan in X whose feet are images under L of objects in A. The category X is assumed to have pushouts.

Structured cospans form a double category with no further assumptions on the functor L. To obtain a symmetric monoidal double category, L must preserve finite coproducts. In practice, L usually has a right adjoint R: X → A, which implies that L preserves all finite colimits. It also allows structured cospans to be constructed more conveniently from an object x in X plus a cospan in A with apex R(x).

See also: StructuredMulticospan.

Construct structured cospan in R-form.

Construct structured cospan in L-form.

Object in the category of L-structured cospans.

Structured multicospan.

A structured multicospan is like a structured cospan except that it may have a number of legs different than two.

See also: StructuredCospan.

Construct structured multicospan in R-form.

Create types for open attributed C-sets from an attributed C-set type.

The resulting types, for objects and morphisms, each have the same type parameters for data types as the original type.

See also: OpenCSetTypes.

Create types for open C-sets from a C-set type.

Returns two types, for objects, a subtype of StructuredCospanOb, and for morphisms, a subtype of StructuredMulticospan.

See also: OpenACSetTypes.