HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, specifically in
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, an F-coalgebra is a
structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
defined according to a
functor In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
F, 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 addition ...
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 diagrams ...
s, a functor is a convenient and general way of organizing a
signature A signature (; from la, signare, "to sign") is a handwritten (and often 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 intent. The writer of a ...
. 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 Applied science, practical discipli ...
: 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), a South Korean boy band *''Infinite'' (EP), debut EP of American m ...
data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s, such as
streams A stream is a continuous body of water, body of surface water Current (stream), flowing within the stream bed, bed and bank (geography), banks of a channel (geography), channel. Depending on its location or certain characteristics, a stream ...
, and also transition systems. F-coalgebras are dual to F-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 addition ...
for a given signature and equational theory form a
variety Variety may refer to: Arts and entertainment Entertainment formats * Variety (radio) * Variety show, in theater and television Films * ''Variety'' (1925 film), a German silent film directed by Ewald Andre Dupont * ''Variety'' (1935 film), ...
, so does the class of all F-coalgebras satisfying a given equational theory form a covariety, where the signature is given by F.


Definition

Let :F : \mathcal\longrightarrow \mathcal 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, and ...
on a category \mathcal. An F-coalgebra is an object A of \mathcal 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, morphisms a ...
:\alpha : A \longrightarrow FA of \mathcal, usually written as (A, \alpha). An F-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 "same" ...
from (A, \alpha) to another F-coalgebra (B, \beta) is a morphism :f:A\longrightarrow B in \mathcal such that : Ff\circ \alpha = \beta \circ f. Thus the F-coalgebras for a given functor ''F'' constitute a category.


Examples

Consider the endofunctor X \mapsto X \sqcup \ : \mathbf \to \mathbf 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 (\overline,\alpha), where \overline= \ \sqcup \ is the so-called conatural numbers, consisting of the nonnegative integers and also infinity, and the function \alpha is given by \alpha(0) = \ast , \alpha(n) = n - 1 for n = 1, 2,\ldots and \alpha(\infty) = \infty . In fact, (\overline, \alpha) is the terminal coalgebra of this endofunctor. More generally, fix some set A, and consider the functor F: \mathbf \longrightarrow \mathbf that sends X to (X\times A)\cup\. Then an F-coalgebra \alpha : X \longrightarrow (X\times A)\cup\ = FX is a finite or infinite
stream A stream is a continuous body of water, body of surface water Current (stream), flowing within the stream bed, bed and bank (geography), banks of a channel (geography), channel. Depending on its location or certain characteristics, a 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 syll ...
where X is the set of states and \alpha is the state-transition function. Applying the state-transition function to a state may yield two possible results: either an element of A 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 X \rarr f_1 \times f_2 \times \ldots \times f_n, which readily factorizes into a collection of "selectors", "observers", "methods" X \rarr f_1, \, X \rarr f_2 \, \ldots \, X \rarr f_n. Special cases of practical interest include observers yielding attribute values, and mutator methods of the form X \rarr X^ taking additional parameters and yielding states. This decomposition is dual to the decomposition of initial F-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 po ...
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 system In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of state (computer science), states and transitions between states, ...
s, 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 i ...
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 Applied science, practical discipli ...
, 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 pr ...
,
streams A stream is a continuous body of water, body of surface water Current (stream), flowing within the stream bed, bed and bank (geography), banks of a channel (geography), channel. Depending on its location or certain characteristics, a stream ...
and transition systems. While
algebraic specification Algebraic specification is a software engineering technique for formally specifying system behavior. It was a very active subject of computer science research around 1980. Overview Algebraic specification seeks to systematically develop more effic ...
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 Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural language semantics. Modal logics extend other ...
.


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 t ...
*
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 diagrams ...


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 Science

CALCO 2011
Category theory Coalgebras