In
mathematics, specifically in
category theory, an
-coalgebra is a
structure defined according to a
functor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, an ...
, with specific properties as defined below. For both
algebras
In mathematics, an algebra over a field (often simply called an algebra) is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and additio ...
and
coalgebra In mathematics, coalgebras or cogebras are structures that are dual (in the category-theoretic sense of reversing arrows) to unital associative algebras. The axioms of unital associative algebras can be formulated in terms of commutative diagra ...
s, a functor is a convenient and general way of organizing a
signature
A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
. This has applications in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
: examples of coalgebras include
lazy,
infinite
Infinite may refer to:
Mathematics
*Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (group)
Infinite ( ko, 인피니트; stylized as INFINITE) is a South Ko ...
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...
s, such as
streams
A stream is a continuous body of surface water flowing within the bed and banks of a channel. Depending on its location or certain characteristics, a stream may be referred to by a variety of local or regional names. Long large streams ...
, and also
transition systems
Transition or transitional may refer to:
Mathematics, science, and technology Biology
* Transition (genetics), a point mutation that changes a purine nucleotide to another purine (A ↔ G) or a pyrimidine nucleotide to another pyrimidine (C ↔ ...
.
-coalgebras are
dual
Dual or Duals may refer to:
Paired/two things
* Dual (mathematics), a notion of paired concepts that mirror one another
** Dual (category theory), a formalization of mathematical duality
*** see more cases in :Duality theories
* Dual (grammatical ...
to
-algebras. Just as the class of all
algebras
In mathematics, an algebra over a field (often simply called an algebra) is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and additio ...
for a given signature and equational theory form a
variety, so does the class of all
-coalgebras satisfying a given equational theory form a covariety, where the signature is given by
.
Definition
Let
:
be an
endofunctor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, an ...
on a category
.
An
-coalgebra is an object
of
together with a
morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphis ...
:
of
, usually written as
.
An
-coalgebra
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "sa ...
from
to another
-coalgebra
is a morphism
:
in
such that
:
.
Thus the
-coalgebras for a given functor ''F'' constitute a category.
Examples
Consider the endofunctor
that sends a set to its
disjoint union
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...
with the singleton set
. A coalgebra of this endofunctor is given by
, where
is the so-called conatural numbers, consisting of the nonnegative integers and also infinity, and the function
is given by
,
for
and
. In fact,
is the terminal coalgebra of this endofunctor.
More generally, fix some set
, and consider the functor
that sends
to
. Then an
-coalgebra
is a finite or infinite
stream over the
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...
where
is the set of states and
is the state-transition function. Applying the state-transition function to a state may yield two possible results: either an element of
together with the next state of the stream, or the element of the singleton set
as a separate "final state" indicating that there are no more values in the stream.
In many practical applications, the state-transition function of such a coalgebraic object may be of the form
, which readily factorizes into a collection of "selectors", "observers", "methods"
. Special cases of practical interest include observers yielding attribute values, and mutator methods of the form
taking additional parameters and yielding states. This decomposition is dual to the decomposition of initial
-algebras into sums of 'constructors'.
Let ''P'' be the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is ...
construction on the category of sets, considered as a covariant functor. The ''P''-coalgebras are in bijective correspondence with sets with a binary relation.
Now fix another set, ''A''. Then coalgebras for the endofunctor ''P''(''A''×(-)) are in bijective correspondence with
labelled transition systems, and homomorphisms between coalgebras correspond to functional
bisimulation
In theoretical computer science a bisimulation is a binary relation between state transition systems, associating systems that behave in the same way in that one system simulates the other and vice versa.
Intuitively two systems are bisimilar if ...
s between labelled transition systems.
Applications
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, coalgebra has emerged as a convenient and suitably general way of specifying the behaviour of systems and data structures that are potentially infinite, for example classes in
object-oriented programming
Object-oriented programming (OOP) is a programming paradigm based on the concept of " objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of ...
,
streams
A stream is a continuous body of surface water flowing within the bed and banks of a channel. Depending on its location or certain characteristics, a stream may be referred to by a variety of local or regional names. Long large streams ...
and
transition systems
Transition or transitional may refer to:
Mathematics, science, and technology Biology
* Transition (genetics), a point mutation that changes a purine nucleotide to another purine (A ↔ G) or a pyrimidine nucleotide to another pyrimidine (C ↔ ...
. While
algebraic specification deals with functional behaviour, typically using inductive datatypes generated by constructors, coalgebraic specification is concerned with behaviour modelled by coinductive process types that are observable by selectors, much in the spirit of
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
. An important role is played here by
final coalgebras, which are complete sets of possibly infinite behaviours, such as streams. The natural logic to express properties of such systems is coalgebraic
modal logic.
See also
*
Initial algebra
In mathematics, an initial algebra is an initial object in the category of -algebras for a given endofunctor . This initiality provides a general framework for induction and recursion.
Examples
Functor
Consider the endofunctor sending ...
*
Coinduction
In computer science, coinduction is a technique for defining and proving properties of systems of concurrent interacting objects.
Coinduction is the mathematical dual to structural induction. Coinductively defined types are known as codata and ...
*
Coalgebra In mathematics, coalgebras or cogebras are structures that are dual (in the category-theoretic sense of reversing arrows) to unital associative algebras. The axioms of unital associative algebras can be formulated in terms of commutative diagra ...
References
B. Jacobs and J. Rutten, A Tutorial on (Co)Algebras and (Co)Induction. EATCS Bulletin 62, 1997, p.222-259
Jan J. M. M. Rutten: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1): 3-80 (2000){Dead link, date=November 2022 , bot=InternetArchiveBot , fix-attempted=yes .
*
ttps://www.cs.ru.nl/B.Jacobs/CLG/JacobsCoalgebraIntro.pdf B. Jacobs, Introduction to Coalgebra. Towards Mathematics of States and Observations(book draft)
Yde Venema: Automata and Fixed Point Logics: a Coalgebraic Perspective. Information and Computation, 204 (2006) 637-678
External links
CALCO 2009: Conference on Algebra and Coalgebra in Computer ScienceCALCO 2011
Category theory
Coalgebras