Self-Adaptation in Collective Adaptive Systems

Abstract

An adaptive system is currently on spot: collective adaptive system (CAS), which is inspired by the socio-technical systems. CASs are characterized by a high degree of adaptation, giving them resilience in the face of perturbations. In CASs, highest degree of adaptation is self-adaptation. The overarching goal of CAS is to realize systems that are tightly entangled with humans and social structures. Meeting this grand challenge of CASs requires a fundamental approach to the notion of self-adaptation. To this end, taking advantage of the categorical approach we establish, in this paper, a firm formal basis for modeling self-adaptation in CASs.

1 Introduction

The socio-technical structure of our community increasingly depends on systems, which are built as a collection of varied agents and are tightly coupled with humans and social interrelations. Their agents more and more need to be able to develop, cooperate and work all by themselves as a part of an artificial community. Hence, for such collective adaptive systems (CASs), one of major challenges is how to support self-adaptation in the face of changing interactions [7, 8]. In other words, how does a CAS understand relevant interrelations and then self-adapt to become better able to live in its interactions?

Dealing with this grand challenge of CASs requires a well-founded modeling and in-depth analysis on the notion of self-adaptation. With this aim, we develop a firm formal approach in which a collective of entities is able to self-adapt its configuration and self-optimize its performance in the face of changing interactions [9].

CASs focus on self-adaptation in preference to build systems. In this view, we see that rigorously approaching to self-adaptation requests fundamental research in all aspects of the self-adaptation. As a novel development for the self-adaptation, we consider to formalize aspects of the self-adaptation taking advantage of categorical language, whose content is presented in this paper.

2 Outline

The paper is a reference material for readers who already have a basic understanding of CAS and are now ready to know the novel approach for formalizing self-adaptation in CAS using categorical language.

Formalization is presented in a straightforward fashion by discussing in detail the necessary components and briefly touching on the more advanced components. Several notes explaining how to use the formal aspects, including justifications needed in order to achieve the particular results, are presented.

We attempt to make the presentation as self-contained as possible, although familiarity with the notion of self-adaptation in CAS is assumed. Acquaintance with the algebra and the associated notion of categorical language is useful for recognizing the results, but is almost everywhere not strictly necessary.

The rest of this paper is organized as follows: Sections 3 and 4 present the notions of collective adaptive systems (CASs) and self-adaptation, respectively. In Section 5, formal aspects of self-adaptation in CASs are developed in detail. In Section 6, we briefly discuss our development. Finally, a short summary is given in Section 7.

3 Collective adaptive systems (CASs)

We define collective adaptive systems (CASs) as the following among various definitions that have been offered by different researchers:

Definition 1

CASs are systems that consist of a collective of heterogeneous components, often called agents, that interact and adapt or learn.

Hence, CASs are characterized by a high degree of adaptation, giving them resilience in the face of perturbations. We see that, in CASs, highest degree of adaptation is self-adaptation and we are interested in approaches to this characteristic of CASs.

This definition is concerned with three major factors of CAS:

• A collective of heterogeneous agents is large enough to build up systems that are tightly entangled with humans and social structures. Their agents increasingly need to be able to evolve, collaborate and function as a part of an artificial society. More importantly, the agents interact dynamically, and their interactions are either physical or involving the exchange of information.

• Interactions are rich, non-linear and primarily, but not exclusively, with immediate neighbors. They can be recurrent, i.e. any interaction can feed back onto itself directly or after a number of intervening stages. CASs are dynamic networks of interactions

• Self-adaptation is the self-evolutionary process whereby a CAS becomes better able to live in its interactions.

4 Self-adaptation

An interesting aspect of CASs is that it makes distinction between self-adaptation (i.e. system-driven personalization and modifications) and self-adaptability (i.e. user-driven personalization and modifications). Self-adaptedness is the state of being self-adapted, i.e. the degree to which a CAS is able to live and reproduce in a given set of interactions. A self-adaptive trait is an aspect of the developmental pattern of the CAS which enables or enhances the probability of that CAS surviving and reproducing.

Formally, let self-* be the set of self-_’s. Each self-_ to be an element in self-* is called a self-* facet [6]. That is,

$$ \mathrm{self}-* = \{\mathrm{self}-\_\!\_\;|\; \mathrm{self}-\_\!\_ \mathrm{is\ a\ self-*~ facet}\} $$

(1)

Thus, self-adaptation is a facet of self-*, that is, self-adaptation is a member of self-*. In other words, using categorical language, this is written as

CASs are self-adaptive in that the individual and collective behavior mutate and self-organize corresponding to interactions. Self-adaptation indicates that CAS is a mimicry of socio-technical systems.

5 Self-adaptation in CASs

Self-adaptation is achieved when CASs are constructed. In this way, we start with considering CASs by categorical approach in this paper. CASs we want to abstract are intuitionally multiple partial morphism applications, such as

(2)

where

• All indexes $i \in T\ (= \mathbb {N} \cup \{0\})$ refer to times,

• s is a self-adaptedness representing a state of CAS in the set, denoted by CAS, of states. s _i is the state s at the time i,

• σ is an interaction in the set, denoted by I n t e r, of interactions. σ _i is interaction σ at the time i, which makes change of the state s _i to become s _i+1.

The representation of Eq. 2 can be understood as

$$ \ldots\;s_{2}(s_{1}(s_{0}())) = \ldots\;s_{2}(s_{1}(\sigma_{0})) = \ldots\;s_{2}(\sigma_{1}) =\ldots\;\sigma_{2} $$

(3)

The self-adaptation in Eq. 2 can also be descriptively drawn as

(4)

or, in another representation

(5)

Note that in Eqs. 5 and 5, we want to represent the above-mentioned self-adaptation of CAS based on interaction where each step of the self-adaptation is an application of unary partial morphism on for all i in T.

The self-adaptation, in Eqs. 5 and 5, describes self-evolutionary process of CASs including the self-adaptation steps to change configurations of the system.

Definition 2 (Configuration of CAS)

We define a configuration of CAS at a self-adaptation step to be a member of the set C A S×I n t e r ^i∈T, where I n t e r ^i∈T stands for

$$ Inter^{i\in T} = \underbrace{\textit{Inter} \times \textit{Inter} \times {\ldots} \times \textit{Inter}}_{i \text{times}} $$

(6)

As we know, when we combine sets by multiplication, each set is a factor and the resulting set is the product. Hence, each set I n t e r is a factor of the resulting set I n t e r ^i∈T, CAS and I n t e r ^i∈T are two factors of the set C A S×I n t e r ^i∈T. The definition of multiplication of sets is very natural. Just remember that a product is not just a set, but a set with two morphisms as in

• When i=2 then I n t e r ²={<σ ₁,σ ₂>|σ ₁,σ ₂∈I n t e r} is obtained by

  

• When i=3 then I n t e r ³={<<σ ₁,σ ₂>,σ ₃>|σ ₁,σ ₂,σ ₃∈I n t e r} is obtained by

  

Specially, we have

• If i=0 then I n t e r ⁰={}

• If i=1 then I n t e r ¹=I n t e r={σ ₁|σ ₁∈I n t e r}

We hope that these diagrams seem suggestive to readers. Our aim is to learn to use them as precise tools of understanding and reasoning, not merely as intuitive guides.

The self-adaptation paradigm, which we want to approach to, is based on mapping a configuration to another. Let us see the following examples

• Example 1: A specific self-adaptation can be specified by the following morphism:

  $$ \textit{Self}-A: {(\textit{CAS} \times \textit{Inter})\longrightarrow \textit{CAS}} $$

  (7)

  (i.e., Self−A:(CAS×Inter ¹)→(CAS×Inter ⁰) or denoted by Self−A(C A S×I n t e r,C A S))

• Example 2: Another specific self-adaptation can be specified by

  $$ \textit{Self}-A:(\textit{CAS} \times \textit{Inter})\longrightarrow(\textit{CAS} \times \textit{Inter}) $$

  (8)

  (i.e., Self−A:(CAS×Inter ¹)→(CAS×Inter ¹) or denoted by Self−A(CAS×Inter,CAS×Inter))

• Example 3: Again, we can also specify another specific self-adaptation as

  $$ \textit{Self}-A:(\textit{CAS} \times \textit{Inter}^{n})\longrightarrow (\textit{CAS}\times \textit{Inter}) $$

  (9)

  (i.e., Self−A:(CAS×Inter ⁿ)→(CAS×Inter ¹) or denoted by Self−A(CAS×Inter ⁿ,CAS×Inter)

  and we can, in the completely same way, do for any other specific self-adaptation.

Definition 3 (Self-adaptation)

Generally, an arbitrary self-adaptation is specified by

$$ \textit{Self}-A:(\textit{CAS} \times \textit{Inter}^{i \in T}) \longrightarrow(\textit{CAS} \times \textit{Inter}^{j \in T}) $$

(10)

Now, let us investigate the following corollaries.

Corollary 1 (Self-adaptation in CASs)

Morphism Self-A in Eq. 10 defines self-adaptation in CASs

Proof

This stems from Eq. 10 and the fact that self-adaptation emerges through interactions in CASs. □

Morphism Self-A is called a self-adaptation. Morphism Self-A in Eq. 10 defines a set $\{\textit {Self}-A_{k \in \mathbb {N}}\}$ of mappings such that

$$ \textit{Self}-A_{k \in \mathbb{N}}:(\textit{CAS} \times \textit{Inter}^{i\in T})\longrightarrow(\textit{CAS} \times Inter^{j\in T}) $$

(11)

Corollary 2 (Self-adaptive traits in CASs)

Set {Self− $\mathrm {A}_{k \in \mathbb {N}}\}$ in Eq. 11 defines self-adaptive traits in CASs. Each mapping Self-A $_{k \in \mathbb {N}}$ is called a self-adaptive trait.

Proof

This originates as the result of the truth that self-adaptation is the set of self-adaptive traits. □

For further well-founded investigation, we can construct a category of the sets of CAS configurations and establish Self-A-algebras as described in the following corollaries.

Corollary 3 (Category of the sets of CAS configurations)

Sets of CAS configurations as in definition 2 define a category.

Proof

In fact, let Cat(CAS) be such a category of the sets of CAS configurations, whose structure is constructed as follows:

• Each set of configurations CAS×Inter ^i∈T defines an object. That is, Obj(Cat(CAS)) ={CAS×Inter ^i∈T}.

• Each Self−A defines a morphism. That is, Arc(Cat(CAS)) ={Self−A:(CAS×Inter ^i∈T)(CAS×Inter ^j∈T)}.

It is easy to check that identity in Eq. 30 and associativity in Eq. 31 on all Self−As are satisfied. □

Corollary 4 (Self-A -algebra(CAS))

Each morphism Self-A in the category Cat(CAS) defines an algebra, so-called Self-A-algebra(CAS).

Proof

This stems from definition of T-algebra, see Appendix, where functor T is defined such that T $= \biguplus \{\textit {Self}-A\}$. Note that the notation $\biguplus$ stands for disjoint union or coproduct. □

With the result of corollary 4, we obtain a compact formal definition of CAS as in

Definition 4 (CAS)

Each Self-A-algebra(CAS) defines a CAS

Both CAS and I n t e r may be infinite. If both CAS and I n t e r are finite, then we have a finite CAS, otherwise we have an infinite CAS.

At this point we can extend the representation of CASs in Eq. 2 to become extended CASs (ECASs) as follows

(12)

where

• All indexes i in T, s _i and σ _i are similar in meaning to the ones mentioned in Eq. 2

• x _i is a real number that can be thought of as the multiplicity (or weight) with which the self-adaptation from s _i to s _i+1 occurs.

Self-adaptation of ECASs in diagram (12) can be separated into two complementary parts as follows:

(13)

and

(14)

On the one hand, diagram (13) emphasizes for all i in T, in the self-adaptation. This allows us to discover conveniently sequence of σ _i as series of interactions. On the other hand, diagram (14) gives rise to , for all i in T, as weights of the series of interactions in the self-adaptation to support an evaluation of weight-based quantitative behaviors of the series of interactions.

Some first steps of the self-adaptation in Eq. 12 can also be descriptively drawn as

(15)

Diagram (15) is thought of as

• For the first step,

  $$s_{1} \in \{s_{1,1}, \ldots, s_{1,n}\} \subset \textit{CAS} $$

  and

  $$x_{0} \in \{x_{0,1}, \ldots, x_{0,n}\} \subset \mathbb{R} $$

• For the second step,

  $$s_{2} \in \{s_{2,1,1}, \ldots, s_{2,1,k}\} \cup {\ldots} \cup \{s_{2,n,1}, \ldots, s_{2,n,m}\} \subset \textit{CAS} $$

  and

  $$x_{1} \in \{x_{1,1,1}, \ldots, x_{1,1,k}\} \cup {\ldots} \cup \{x_{1,n,1}, \ldots, x_{1,n,m}\} \subset \mathbb{R} $$

and the meaning of Eq. 12 is viewed as the following morphism.

$$ \textit{Self}-A: (\textit{CAS} \times Inter)\longrightarrow(\textit{CAS} \longrightarrow \mathbb{R}) $$

(16)

The self-adaptation morphism Self-A in Eq. 16 is nondeterministic and this can be explained as follows: Self-A assigns to each configuration in CAS×Inter a morphism $\textit {CAS}\longrightarrow \mathbb {R}$ that can be seen as a kind of nondeterministic configuration (or so-called distributed configuration) and specifies for every state s ^′ in CAS a multiplicity (or weight) Self-A (<s,σ>)(s ^′) in $\mathbb {R}$.

This nondeterminism of self-adaptation makes extension in representation of the categorical models mentioned above. Let us see the following examples

• Example 4: A specific self-adaptation, which is specified by the following morphism, is an extension of Eq. 7:

  $$ \textit{Self}-A:(\textit{CAS} \times \longrightarrow \mathbb{R}) $$

  (17)

  (i.e., Self-A:$(\textit {CAS} \times \longrightarrow ((\textit {CAS} \times \textit {Inter}^{0})\longrightarrow \mathbb {R})$ or denoted by $\textit {Self}-A\ ((\textit {CAS} \times \textit {Inter}),(\textit {CAS} \longrightarrow \mathbb {R}))$)

• Example 5: The model in Eq. 8 extended for self-adaptation is specified by

  $$ \textit{Self}-A: (\textit{CAS} \times \textit{Inter}) \longrightarrow((\textit{CAS} \times Inter)\longrightarrow\mathbb{R}) $$

  (18)

  (i.e., Self-A:$(\textit {CAS} \times \textit {Inter}^{1}) \longrightarrow ((\textit {CAS} \times \textit {Inter}^{1}) \longrightarrow \mathbb {R})$ or denoted by $\textit {Self}-A ((\textit {CAS} \times \textit {Inter}),((\textit {CAS} \times \textit {Inter}) \longrightarrow \mathbb {R}))$)

• Example 6: Again, we specify another specific self-adaptation as an extension of Eq. 9 in

  $$ \textit{Self}-A: (\textit{CAS} \times \textit{Inter}^{n})\longrightarrow((\textit{CAS} \times \textit{Inter}) \longrightarrow \mathbb{R}) $$

  (19)

  (i.e., $\textit {Self}-A:(\textit {CAS} \times \textit {Inter}^{n}) \longrightarrow ((\textit {CAS} \times \textit {Inter}^{1})\longrightarrow \mathbb {R})$ or denoted by $\textit {Self}-A (\longrightarrow (\textit {CAS} \times \textit {Inter}^{n}),((\textit {CAS} \times \textit {Inter})\longrightarrow \mathbb {R}))$)and, in the completely same way, we do for an arbitrary self-adaptation as in

Definition 5 (Self-adaptation)

Generally, an arbitrary self-adaptation is specified by

$$\begin{array}{@{}rcl@{}} Self-A: (\textit{CAS} \times \textit{Inter}^{i\in T}) \longrightarrow((\textit{CAS} \times \textit{Inter}^{j\in T})\longrightarrow\mathbb{R})\\ \end{array} $$

(20)

We have the following corollaries.

Corollary 5 (Self-adaptation in ECASs)

Morphism Self-A in Eq. 20 defines self-adaptation in ECASs

Proof

This stems from Eq. 20 and the fact that self-adaptation emerges through interactions in ECASs. □

Morphism Self-A in Eq. 20 defines a set $\{\textit {Self}-A_{k \in \mathbb {N}}\}$ of mappings such that

$$ \{\textit{Self}-A_{k \in \mathbb{N}}\}:(\textit{CAS} \times \textit{Inter}^{i\in T})\longrightarrow((\textit{CAS} \times \textit{Inter}^{j\in T}) \longrightarrow\mathbb{R}) $$

(21)

Corollary 6 (Self-adaptive traits in ECASs)

Set $\{Self-A_{k \in \mathbb {N}}\}$ in Eq. 21 defines self-adaptive traits in ECASs. Each mapping Self-A $_{k \in \mathbb {N}}$ is called a self-adaptive trait.

Proof

This originates as the result of the truth that self-adaptation is the set of self-adaptive traits. □

Corollary 7 (Category of the sets of ECAS configurations)

Category Cat(CAS) equipped with structure $(\textit {CAS} \times \textit {Inter}^{i\in T})\longrightarrow ((\textit {CAS} \times \textit {Inter}^{j\in T})\longrightarrow \mathbb {R})$ defines a category Cat(ECAS) of the sets of ECAS configurations.

Proof

This result comes immediately from corollary 3. □

Corollary 8 (Self-A -algebra(ECAS))

Structure $(\textit {CAS} \times \textit {Inter}^{i\in T})\longrightarrow ((\textit {CAS} \times \textit {Inter}^{j\in T})\longrightarrow \mathbb {R})$ in the category Cat(ECAS) defines an algebra, so-called Self-A-algebra (ECAS).

Proof

This originates from definition on T-algebra in Appendix, where functor T is defined such that T $= \biguplus \{\textit {Self}-A\}$ (similar to corollary 4) with Self-A defined in Eq. 20. □

With this result of corollary 8, we obtain a compact formal definition of ECAS as in

Definition 6 (ECAS)

Each self-A-algebra(ECAS) defines an ECAS

Moreover, we have the following corollary to obtain a significant relationship between CASs and ECASs.

Corollary 9 (Relationship between CASs and ECASs)

CASs are just of specific ECASs. In other words, using categorical language,

Proof

In fact, by the self-adaptation morphism in Eq. 20 of ECASs, let f be the morphism $f: (\textit {CAS} \times \textit {Inter}^{j\in T}) \longrightarrow \mathbb {R}$, Conf be CAS×Inter ^j∈T and the finite set . Hence it follows that when but ∀c ^′≠c:f(c ^′)=0 (i.e., the set $\mathbb {R}(Conf)$ is a singleton set of configuration with weight of 1. Note that the notation ∃! is read as “exist only”) then Eq. 20 becomes the self-adaptation morphism of CASs as in Eq. 10. In other words, in the case, ECASs will become CASs. □

6 Discussions

The aim of this paper has been both to give an in-depth analysis as well as to present the new material on the notion of self-adaptation in both CASs and ECASs.

In the considered context, we apply the category theory, which deals in an abstract way with algebraic objects and relationships between them for specifying interaction behaviors in both CASs and ECASs. For modeling, analyzing and verifying the interaction behaviors, category theory is much better-approaching than other ones such as process algebras (or process calculi), FSM (Finite State Machine) or UML (Unified Modeling Language). In fact, the categorical approach becomes more powerful since process algebras and FSM are just of algebraic objects of category and UML is really a semi-formal approach. Categories were first described by Samuel Eilenberg and Saunders Mac Lane in 1945 [4], but have since grown substantially to become a branch of modern mathematics. Category theory spreads its influence over the development of both mathematics and theoretical computer science. The categorical structures themselves are still the subject of active research, including work to increase their range of practical applicability.

7 Conclusions

In this paper, we have rigorously approached to the notion of self-adaptation in both CASs and ECASs from which formal aspects of the self-adaptation emerge.

We have investigated configuration of both CASs and ECASs at every self-adaptation step as a member in the set C A S×I n t e r ^i∈T, then self-adaptation as a morphism from a configuration to another and, moreover, self-adaptation as a set of self-adaptive traits. By that way we have discovered some significant properties of the self-adaptation.

Appendices

Appendix

We recall some concepts from the category theory [1–5] used in this paper.

What is a category?

■ A category C can be viewed as a graph (O b j(C), A r c(C),s,t), where

• O b j(C) is the set of nodes we call objects,

• A r c(C) is the set of edges we call morphisms and

• s,t:A r c(C)→O b j(C) are two maps called source (or domain) and target (or codomain), respectively.

We write $f:\mathcal {X} \longrightarrow \mathcal {Y}$ when f is in A r c(C) and $s(f)=\mathcal {X}$ and $t(f)=\mathcal {Y}$.

An object in the category is an algebraic structure such as a set. We are probably familiar with some notations for finite sets: {Student A, Student B, Student C } is a name for the set whose three elements are Student A, Student B, Student C. Note that the order in which the elements are listed is irrelevant.

A morphism f in the category consists of three things: a set $\mathcal {X}$, called the source of the morphism; a set $\mathcal {Y}$, called the target of the morphism and a rule assigning to each element x in the source an element y in the target. This y is denoted by f(x), read “f of x”. Note that the morphism is also called the map, function, transformation, operator or arrow. For example, let $\mathcal {X}=\{$ Student A, Student B, Student C }, $\mathcal {Y}=\{$ Math, Physics, Chemistry, History } and let f assign each student his or her favorite subject. The following internal diagram is an illustration.

(22)

This states that the favorite subject of the Student C is History, written by f(Student C) =History, while Student A and Student B prefer Chemistry. There are some important properties of any morphism

• From each element in the source {Student A, Student B, Student C}, there is exactly one arrow leaving.

• To an element in the target {Math, Physics, Chemistry, History}, there may be zero, one or more arrows arriving.

It is possible that the source and target of the morphism could be the same set. The following internal diagram is an example.

(23)

and, in the case, the morphism is called an endomorphism whose representation is available as in

(24)

■ Associated with each object $\mathcal {X}$ in O b j(C), there is a morphism $1_{\mathcal {X}} = \mathcal {X} \longrightarrow \mathcal {X}$, called the identity morphism on $\mathcal {X}$, and to each pair of morphisms $f:\mathcal {X} \longrightarrow \mathcal {Y}$ and $g:\mathcal {Y} \longrightarrow \mathcal {Z}$, there is an associated morphism $f;g: \mathcal {X} \longrightarrow \mathcal {Z}$, called the composition of f with g. The representations in Eq. 25 include the external diagrams of identity morphism and composition of morphisms.

(25)

Here are the corresponding internal diagrams of the identity morphism.

(26)

Or

(27)

And here, the composition of morphisms is described in the internal diagram

(28)

Or, in the external diagram By the diagram (28), we can obtain answers for the question “What should each student support to his or her favorite classmate for subject?”. In fact, the answers are such as “Student A likes Student B, Student B likes Chemistry, so Student A should support Chemistry”, “Student B likes Student C, Student C likes History, so Student B should support History” and “Student C likes Student B, Student B likes Chemistry, so Student C should support Chemistry”.

The composition of two morphisms e and f means that e and f are combined to obtain a third morphism This is represented in the following internal diagram.

(29)

where, for example, e;f(Student B)=History is read as “the favorite subject of the favorite classmate of Student B is History”.■ The following equation must hold for all objects $\mathcal {X}$, $\mathcal {Y}$ in O b j(C) and morphism $f:\mathcal {X} \longrightarrow \mathcal {Y}$ in A r c(C):

$$ {\kern2pc}\text{\textit{Identity}}:\quad\quad\quad\quad 1_{\mathcal{X}};f = f = f;1_{\mathcal{Y}} $$

(30)

The following equation must hold for all objects $\mathcal {X}$, $\mathcal {Y}$ and $\mathcal {Z}$ in O b j(C) and morphisms $f:\mathcal {X} \longrightarrow \mathcal {Y}$, $g:\mathcal {Y} \longrightarrow \mathcal {Z}$ and $h:\mathcal {Z} \longrightarrow \mathcal {T}$ in A r c(C):

$$ {\kern2pc}\text{\textit{Associativity}}:\quad\quad (f;g);h = f;(g;h) $$

(31)

Isomorphism

A morphism $f:\mathcal {X} \longrightarrow \mathcal {Y}$ in the category C is an isomorphism if there exists a morphism $g: \mathcal {Y} \longrightarrow \mathcal {X}$ in that category such that $f;g = 1_{\mathcal {X}}$ and $g;f = 1_{\mathcal {Y}}$.

(32)

That is, if the following diagram commutes.

(33)

Element of a set

For any set A, x∈A iff (or x:1→A) where 1 denotes a singleton set. Focus on one element of {Math, Physics, Chemistry, History }, say {subject}, and call this set “1”. Let us see what the morphisms from 1 to {Math, Physics, Chemistry, History } are. There are exactly four of them.

(34)

(35)

(36)

(37)

By this way, we can write (or $2: 1 \longrightarrow \mathbb {N}$ ) for $2 \in \mathbb {N}$, (or $i: 1\longrightarrow \mathbb {N}$) for $i \in \mathbb {N}$ and so on.

Functor

Functor is a special type of mapping between categories. Functor from a category to itself is called an endofunctor. Note that the functors are also viewed as morphisms in a category, whose objects are smaller categories.

T-algebra

Let C be a category, $\mathcal {A}$ an object in O b j(C), T:C→C an endofunctor and f a morphism $\textsf {T}(\mathcal {A}) \stackrel {f}{\longrightarrow } \mathcal {A}$; then T-algebra is a pair $\langle \mathcal {A},f\rangle$. O b j(C) is called a carrier of the algebra and T a signature of the algebra.