Beyond Logical Approach to Systems Theory

Abstract

Logical Approach to Systems Theory (LAST) provides a “meta”-framework to describe and investigate explicitly and deeply the similarity of system models based on general and formal definitions of system models and their structures. The main theorem of LAST is F-morphism theorem. It substantially enhances the concept of “isomorphism” between system models of the same type to those of “different types” in the sense that they can be described in different types of languages. After considering the limitation of LAST by interpreting Gödel’s Incompleteness Theorem, it is clarified that the adaption and the structural change of a system would be beyond the description capability of LAST. Hence some new conceptual devices and effective models such as agent, internal model, and organizational learning are required to be developed. Agent-Based Organizational Cybernetics (AOC) could be a key model to describe the organizational learning that induces the adaptation and structural change of system models especially in social systems.

1 Introduction

This paper describes the essence of Logical Approach to Systems Theory (LAST) (Takahashi & Takahara, 1995), and the framework of agent-based organization cybernetics (AOC) for consideration for adaptation that includes internal model and organizational learning as the main concepts (Takahashi, 2006).

The similarity of systems models has been a central concept in systems theory as well as systems science. Basically, from the theoretical point of view, a system model is similar to another if a homomorphism can be defined between the two system models. The homomorphism theorem is one of the typical results on how isomorphic images can be constructed in terms of homomorphism. Though the homomorphism concept should be primally considered to give a similarity relation of systems models, it should be still clarified what properties are interpreted as similar between system models in the sense of “preserving” the properties by a homomorphism from one model to another, and how the system model should be expressed to define in a totally formal way the similarity by generalizing the homomorphism concept.

LAST will give an answer to these questions on general similarity.

LAST provides a “meta”-framework to describe and investigate explicitly and deeply the similarity of system models based on general and formal definitions of system models and their structures. Systems models are described in terms of model theory. Roughly speaking, the following relationship holds (Chang & Keisler, 1973):

$$ \mathrm{model}\ \mathrm{theory}=\mathrm{universal}\ \mathrm{algebra}+\mathrm{logic}. $$

Universal algebra is appropriate or proper for describing system models, especially general system models or abstract system models (Mesarovic & Takahara, 1975, 1989), each of which is expressed as a mathematical structure. Logic generally includes as the main body language, formation rules of formulas, deduction system, and satisfaction of formulas in a model. We sometimes use category theoretical formulation as well as universal algebra, which is often effective for the theory of general system models, when we consider a class of all systems satisfying some specific properties, for example, a class of all state space representations.

The main theorem of LAST is F-morphism theorem. It substantially enhances the concept of “isomorphism” between system models of the same type to those of “different types,” which means that the two models described in “different languages” can be isomorphic in terms of F-morphism. The relation of being “isomorphic” of system models is the basis of the similarity in systems science. Hence the F-morphism concept in LAST should be considered as fundamental for the similarity in systems science, as well as homomorphism as a specific case.

The logical approach also clarifies the distinction of what type of properties of systems can be described in the theory and what type of them cannot. In particular, the adaptation of systems and the structural change of a system would be beyond the description capability of LAST. We need to develop some new conceptual devices such as agent, internal model, and organizational learning. This chapter focuses on considering the adaptation of social systems and introduces the agent-based organization cybernetics (AOC) as a key model.

2 General Systems

In the most general sense, a system can be defined as a relation on some attributes V ₁, …, V _n, the relation which is expressed by S ⊂ V ₁ × ⋯ × V _n (Mesarovic & Takahara, 1975, 1989). Each set V _i represents the collection of alternative ways in which the corresponding object appears in the relation that defines the system. The object is identified in terms of a property and an attribute. A general form of an input-output system model is described as S ⊂ X × Y, where X is the set of input attributes of concerns and Y the set of output attributes of concern, respectively. Starting from this general definition of a system, we develop systems theory by introducing into the attributes some structures such as linearity, stationarity, and so on that are suitable to our interests in objects as systems. Our definition of a system model realizes this concept of a system in as a formal and general way as possible.

3 Logical Approach to Systems Theory: LAST

Logical Approach to Systems Theory (LAST) provides a second-order framework to describe and investigate explicitly and deeply both system models and structures of them from a model theoretic point of view (Takahashi, 1995). LAST is characterized by type-free representation, distinction between model and structure, and hierarchical structure expansion.

• 1. Type-free representation of system models. The representation is not only independent of any specific formalisms such as differential equations or automata, but also capable of clarifying possibly different types of system models constructed from multifaceted aspects in modeling.

• 2. Distinction of system models from their structures. The logical approach provides a language and formal framework to describe the properties of each system model, to define its structure and specify the class. The language is determined by the structure of a system model.

• 3. Hierarchical structure expansion. The relations of inclusion among classes of system models are given as hierarchical relations of the structures of system models. That is, when a class of system models is included in another, the structure of system models of the former class is obtained by expanding the other. The expanded structure inherits the antecedent.

LAST places its emphasis mainly on complex systems such as information systems or social systems as concrete instances rather than traditional topics in control theory. So complex is even a single information system that includes system models of various types coming from diversity of individual objects. The design of a complex system requires to deal with such variety of types of system models and to specify a class of system models of any type separately from the description of the system models. Thus exploring the inter-relations among system models to describe a complex system is expected as a key feature in LAST. The primary purpose of LAST is to provide an effective framework for using basic concepts in systems theory to describe complex systems. The use of model theory rather than usual set theory would make this purpose easily attainable. LAST aims at a practical device for designing complex systems as well as theoretical development on system models and structures.

3.1 Basic Concepts of LAST

There are at least four basic concepts to be understood in applying LAST. We will illustrate in the following sections each of the concepts in detail.

• 1. System model. As stated previously, system models are objects of study in systems theory. LAST provides a formal framework for representing a system model to reflect systems recognition of a model builder. The representation should be fully independent of the types of system models, while individual system models employed in individual systems theories have their own specified types. Thus we have to specify the language in such a way that not only system models, but their types can be described, that is, what the types of system models are should be clearly defined. LAST gives a natural and suitable way to satisfy such requirement.

• 2. Structure. Since every system in the reality is recognized only as a system model, the structure of a system is equivalent to that of a system model. If it is allowed to use the term “structure” in defining a system, we could define a system as follows: “A system is a whole entity having its own structure.”

  The concept of structure has been less well-defined than that of a system and rather controversial. However, in developing a meta-theory of systems, we cannot avoid making clear the concept of structure in a formal way. In our logical approach structure of a system model will be defined by a pair of a language to describe the system model and a set of formulas to specify the behavior of the system model. This definition comprehends essential parts of other definitions of structure.

• 3. Morphism. The morphism is a conceptual basis for considering similarities between system models. The similarity between two system models is often defined by some morphism between them, more precisely, by some homomorphism. The definition of similarity by homomorphism, however, depends on a particular representation or specification such as Mealy type automata used to describe the situation. Since morphism is both practically and conceptually significant as such in systems theory, we need to develop some general morphism independent from representation types so that it gives the similarity between system models not only of the same kind of type, but of different types. The type-freeness of representation of system models in LAST enables us to construct such a general morphism between system models of possibly different types including homomorphism as a truly special case. For example we can construct a general morphism from a finite automaton to a Petri net.

• 4. Universality. Since an aim of LAST is to develop a meta-theory concerning “inter-models,” we are interested in universal properties found in a class of system models or their structures rather than in individual models as instances. So far, some universal properties significant in systems theory have been examined. Here we will concentrate on the realization problem as universality, the problem which deals with how the minimal model in a given class of a structure can be constructed from a given set of input-output pairs. The algebraic specification is one of important examples of the realization as universality.

3.2 System Model

3.2.1 Definition of System Model

A system model is a whole entity with some interactions among its elements. A direct and natural representation idea of a system model is to express it as a mathematical structure that consists of a base set with relations and functions defined on it.

Definition 5.1 [System Model]

A system model $\mathfrak{M}$ is composed of:

• 1. A base set M;

• 2. A set of λ(i)-ary relations on M, {R _i| i ∈ I}, where λ is a function such that I → N ⁺ (positive integers);

• 3. A set of μ(j)-ary functions on M, {f _j| j ∈ J}, where μ is a function such that J → N (non-negative integers).

Here an n-ary relation or function has n arguments, written as R(a ₁, …, a _n), or f(a ₁, …, a _n). The function λ (or μ) means that the arity of a relation R _i (or f _j) depends on its index i (or j), written as R _i(a ₁, …, a _λ(i)) or f _j(a ₁, …, a _μ(j)). Nullary functions with no arguments are called constants. The pair 〈λ, μ〉 is called the type of $\mathfrak{M}$.

We write $\mathfrak{M}$ as follows:

$$ \mathfrak{M}=\left\langle M;\left\{{R}_i|i\in I\right\},\left\{{f}_j|j\in J\right\}\right\rangle . $$

We sometimes write $\mid \mathfrak{M}\mid$ to indicate the base set M.

This definition of a system model has very wide applicability. Most systems representations we are interested in can be reformulated in the above form. We illustrate below some typical and significant examples of system models.

Example 5.1 [Input-Output System Model]

A simple but quite important instance of system models is an input-output system model. Although we could describe it in some different representations, the following one is natural. An input-output system model is expressed by

$$ {M}_{I/O}=\left\langle X\cup Y;S,X,Y\right\rangle, $$

where S ⊂ X × Y, X is the set of inputs and Y the set of outputs.

Example 5.2 [Linear System Model]

A linear system model is a system model whose input set and output set are vector spaces and whose behavior has the linear property that S(x, y) and S(x′, y′) implies S(αx + βx′, αy + βy′) for any α and β in a field F over which the input and output sets are the vector spaces. The linearity of the input set is represented by the following system model: M _X = 〈F ∪ X; F, X, +, −,⁻¹,  ⋅ , 0_F, 1_F, 0_X〉, where X is the set of inputs, F a unary relation that is the set of scalars, 0_X the zero vector, 0_F the zero scalar, 1_F the unit element of F, + a binary function representing both scalar and vector addition, − a unary function representing the additive inverse, ⋅ a binary function representing scalar multiplication and multiplication of a vector by a scalar and ⁻¹ a unary function representing the multiplicative inverse. The linearity of the output set is similarly defined. A linear system model is defined as the union of, ${\mathfrak{M}}_Y$ and the input-output system model with the linear property of behavior, where the union of two system models ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ is the system model whose base set, functions, and relations are respectively the unions of the corresponding sets of the two system models.

Example 5.3 [Discrete Event System Specification (DEVS) Model]

The DEVS formalism provides a means of constructing simulation models and a formal representation of discrete event systems capable of mathematical manipulation just as differential equations serve this role for continuous systems (Zeigler, 1990). A DEVS model described in the DEVS formalism consists of a time base, inputs, states, outputs, and functions for determining next states and outputs given current states and inputs:

$$ {M}_{\mathrm{DEVS}}=\left\langle X\cup S\cup Y\cup R\cup \left\{\infty \right\};X,S,Y,{\delta}_{\mathrm{int}},{\delta}_{\mathrm{ext}},\lambda, {t}_{\mathrm{a}},Q,T\right\rangle, $$

where X is a set of external event types, S a set of sequential state, Y a set of external event types generated as outputs, T the time base, t _a the time advance function from S to the non-negative reals with infinity:${t}_{\mathrm{a}}:S\to {R}_{0,\infty}^{+}$, Q the total state set defined by Q = {(s, e)| s ∈ S, 0 ≤ e ≤ t _a(s)}, δ _int the internal transition function: δ _int : S → S, δ _ext the external transition function: δ _ext : Q × X → S, and λ the output function:λ : Q → Y.

Some essential behavior of a system specified by DEVS, such as the property of the output function that generates an external output just before an internal transition takes place, should be considered to be included implicitly in ${\mathfrak{M}}_{\mathrm{DEVS}}$.

3.2.2 Language for Describing Systems Properties

The systems properties are the properties possessed by a system model such as linearity, stationarity, or causality. To investigate properties of these systems properties, which can be called the meta-treatment of system models, we introduce a formal language to describe systems properties. The use of the formal language characterizes LAST. In this section we give only the formal framework of the language.

Definition 5.2 [Language for a System Model]

The language for a system model $\mathfrak{M}$ consists of:

• 1. λ(i)-ary predicate letters R _i for each i ∈ I, where λ is a function such that I → N ⁺ (positive integers);

• 2. μ(j)-ary function symbols f _j for each j ∈ J, where μ is a function such that J → N (non-negative integers).

We write $\mathfrak{L}\left(\mathfrak{M}\right)$ also as $\mathfrak{L}\left(\mathfrak{M}\right)=\left\langle \left\{{\mathbf{R}}_i|i\in I\right\},\left\{{\mathbf{f}}_j|j\in J\right\}\right\rangle$.

〈λ, μ〉 is also said to be the type of $\mathfrak{L}\left(\mathfrak{M}\right)$. There is the one-to-one correspondence, denoted by Cor, between the boldface symbols in $\mathfrak{L}\left(\mathfrak{M}\right)$ and the light face symbols for the relations and functions in $\mathfrak{M}$, i.e., Cor(R _i) = R _i for each i ∈ I and Cor(f _j) = f _j for each j ∈ J. Then $\mathfrak{M}$ is said to be a realization of the language $\mathfrak{L}\left(\mathfrak{M}\right)$ or model for $\mathfrak{L}\left(\mathfrak{M}\right)$. The languages for two system models of the same type are, up to alphabetic variants, identical. Therefore every system model of the same type as a system model $\mathfrak{M}$ is a realization of the language $\mathfrak{L}\left(\mathfrak{M}\right)$.

For example, an input-output system model,

$$ {\mathfrak{M}}_{I/O}=\left\langle X\cup Y;S,X,Y\right\rangle $$

and all the system models of the same type as this system model are realizations of the language,

$$ \mathfrak{L}\left({\mathfrak{M}}_{I/O}\right)=\left\langle \mathbf{S},\mathbf{X},\mathbf{Y}\right\rangle . $$

We should notice that for language we customarily use boldface symbols with the same alphabets as a system model, for example, S and S, so as not to confuse language with system models. This usage is only for the sake of convenience. However, we should notice that a language, e.g., $\mathfrak{L}\left({\mathfrak{M}}_{I/O}\right)$, is purely syntactic construct. Other models than ${\mathfrak{M}}_{I/O}$, e.g.,${\mathfrak{M}}^{\prime }=\left\langle Z;T,V,W\right\rangle$, can be also realizations of $\mathfrak{L}\left({\mathfrak{M}}_{I/O}\right)$, even if they have no property of an input-output system model. The desirable properties that every input-output system model should have are specified not only as a language but as a structure of the system model.

To describe systems properties, we need “grammar” that distinguishes “right sentences” from wrong sentences. In our logical approach, we assume that the properties of a system can be expressed as first-order sentences in first-order language that plays the role of the “grammar.” The first-order language consists of the primitive symbols such as variables, logical connectives, quantifiers, identity symbols, parentheses and comma with the language $\mathfrak{L}\left(\mathfrak{M}\right)$ for a system model, the formation rules of the terms, the atomic formulas and the well-formed formulas. The set of terms of the language $\mathfrak{L}\left(\mathfrak{M}\right)$, denoted by $\mathrm{Term}\left(\mathfrak{L}\left(\mathfrak{M}\right)\right)$, is recursively defined from the language $\mathfrak{L}\left(\mathfrak{M}\right)$. Similarly the set of atomic formulas, denoted by $\mathrm{Atom}\left(\mathfrak{L}\left(\mathfrak{M}\right)\right)$ and that of well-formed formulas, denoted by $\mathrm{Form}\left(\mathfrak{L}\left(\mathfrak{M}\right)\right)$, are recursively defined from the language.

The logical connectives and universal quantifier as primitive symbols have no proper meanings such as “and,” “not,” and “for all.” These intended meanings are realized only when these symbols are interpreted in a specific system model. This realization is called satisfaction. We will usually use other symbols, say x, y, z, as individual variables. A term that has no variable is called a closed term. In first-order logic some abbreviations such as ∃v, ϕ ∨ ψ, ϕ → ψ, and so on will be defined in the standard manner. Although the abbreviations actually intend to have the meanings of “for some (or there exist),” “or,” and “imply” respectively, these meanings are only realized in a system model. Other logical concepts such as the scope of the quantifier, a bound variable, a free variable, and so on are introduced in the language, which can be found in the standard textbook of logic. A formula $\phi \in \mathrm{Form}\left(\mathfrak{L}\left(\mathfrak{M}\right)\right)$ is said to be a sentence of $\mathfrak{L}\left(\mathfrak{M}\right)$ if ϕ has no free variables. $\mathrm{Sent}\left(\mathfrak{L}\left(\mathfrak{M}\right)\right)$ denotes the set of sentences.

In our logical approach every systems property of an individual system model is expressed by a sentence. For example, an input-output system model ${\mathfrak{M}}_{I/O}$ has a basic systems property: “every element of the system is a pair of an input and an output.” This property can be expressed by the following sentence: (∀xy)(S(x, y) → X(x)∨Y(y)). In ordinary mathematical notations, i.e., in set-theoretical language, this sentence means that S ⊂ X × Y. As another example, an input-output system of function-type (Mesarovic & Takahara, 1989) can be expressed as: (∀x ∈ X → (∃ ! y ∈ Y)S(x, y)), where the notation ∃ ! x ϕ(x) is the abbreviation of the sentence that means “there uniquely exists x such that ϕ(x).”

We have noticed that a systems property is expressed by a sentence. Conversely, a sentence should be interpreted as a systems property in a system model so that the sentence obtains a concrete meaning in the system model.

Let us consider a system model ${\mathfrak{M}}_{\mathrm{S}}=\left\langle \left\{a,b,c\right\};S,X,Y\right\rangle$, where S = {(a, b), (a, c), (b, c)} and X = Y = {a, b}. Is a formula S(x, y) → X(x) ∨ Y(y) true in this system model? If we assign a and b to the variables x and y respectively, the formula is true in that model. However if c to y, then it is not true. To judge the truth of a formula containing some free variables, we need to assign an element of the base set of a system model to each variable. As will be stated later, since a sentence has no free variable, we can judge its truth without depending on the assignment of variables.

For example, a sentence (∀xy)(S(x, y) → X(x) ∨ Y(y)) is not true in the system model ${\mathfrak{M}}_{\mathrm{S}}$, so this model is not an input-output system model. An assignment to each variable is defined by an assignment function. Given a system model $\mathfrak{M}$ with a base set M, an assignment function ρ (or briefly assignment) is a function of the set V of variables to M. Then for a given assignment, sentences in terms of the language of the system model are interpreted into the system model. This interpretation is defined as the denotation of a term in $\mathfrak{L}\left(\mathfrak{M}\right)$. Each variable x is replaced by the element ρ(x) ∈ M and each function symbol is replaced by the corresponding function. A denotation with respect to a given assignment can be regarded as a function of terms to the base set of a system model.

The concept that a systems property holds in a system model is defined as the satisfaction of formulas.

Definition 5.3 [Satisfaction]

A formula ϕ holds in $\mathfrak{M}$ with an assignment function ρ, or ρ satisfies ϕ in $\mathfrak{M}$, written $\mathfrak{M}\models \phi \left[\rho \right]$, is defined recursively:

• 1. $\mathfrak{M}\models {\mathbf{R}}_{\mathbf{i}}\left({t}_1,\dots, {t}_{\lambda (i)}\right)$ if and only if $\left\langle {t}_1^d\left[\rho \right],\dots, {t}_{\lambda (i)}^d\left[\rho \right]\right\rangle \in {R}_i$;

• 2. $\mathfrak{M}\models \neg \phi \left[\rho \right]$ if and only if it is not the case that $\mathfrak{M}\models \phi \left[\rho \right]$;

• 3. $\mathfrak{M}\models {\phi}_1\wedge {\phi}_2\left[\rho \right]$ if and only if $\mathfrak{M}\models {\phi}_1\left[\rho \right]$ and $\mathfrak{M}\models {\phi}_2\left[\rho \right]$;

• 4. $\mathfrak{M}\models \forall \mathbf{x}\phi \left[\rho \right]$ if and only if ⊨ϕ[ρ(y/x)] for any y ∈ M.

3.3 Structure

The structure of a system model characterizes the system model in the sense that the structure determines to which class of systems the system model pertain. In this sense if a system model is expressed by a collection of some differential equations, we can say that the matrices of the coefficients of the differential equations give a structure of the system model. However, from systems viewpoints, a class of system models should be specified not by the form of differential equations, but by a set of systems properties. Hence the structure of a system model should have at least the following features.

First, the structure of a system model generates its properties or behavior to be recognized.

Second, the representation of structure is based on a hierarchical construction. For example, the structure of an input-output linear system model is “hierarchically” constructed from both a linear structure and an input-output structure, in the sense that the input-output linear structure explicitly “inherits” the properties from the linear and input-output structure.

Third, the structure distinguishes the properties of the class of system models satisfying it from those of an individual system model in the class.

One way to fulfill the above requirements is to adopt a “language” that expresses systems properties, and to represent the structure as “axioms.” This means that we should abstract basic properties from a class of system models as axioms that are common characteristics of the class. Thus the structure of a “family system” in the previous section is abstracted from concrete family models. For example, we can abstract some axioms such that every father is a male, every mother is a female, father and mother are married, all brothers have the same father and mother, and so on. The language such as “father,” “male,” “every,” “is-a,” etc., and some “grammar” to make legal sentences should be chosen before axioms are described. Then the axioms are expressed by some sentences in that language. We should notice that this example of the structure of family does not include all families at all; a family that has brothers whose mothers are different is not included.

A language and axioms are chosen from a systems viewpoint that reflects our current interest. In this sense the structure of a system model expresses fundamental interactions we recognize as the system model does. Thus a modeling process contains as its essential part some stages of specifying language and constructing axioms. Consequently the structure of a system model is defined as a pair, $\left(\mathfrak{L};\Sigma \right)$, of language $\mathfrak{L}$ to define the system model and a set of axioms Σ to describe the class to which the system model pertains. In LAST every structure is defined in a formal language such as first-order language. Use of other formal languages than first-order is not restricted in LAST. We notice that there are some advantages and disadvantages of the use of first-order language.

The formal description of a structure of a system model has some technically outstanding advantages as well as conceptual ones. It enables us to point out what a systems property of a given system model is, and to distinguish the system properties from system models that “satisfy” the properties. This relation is provided as satisfaction relation that is one of the main characteristics of LAST: type-free representation. Thus we can construct and specify a class of system models without depending on the concrete descriptions of individual system models.

The formal definition of the structure of a system is defined below.

Definition 5.4 [Structure of a System]

Let $\mathfrak{M}$ be a system model, $\mathfrak{L}\left(\mathfrak{M}\right)$ the language for $\mathfrak{M}$, and Σ a set of sentences of $\mathfrak{L}\left(\mathfrak{M}\right)$, where $\mathfrak{M}\models \Sigma$. Then the structure of a system as a prototype of the system model $\mathfrak{M}$ is defined by $\left(\mathfrak{L}\left(\mathfrak{M}\right);\Sigma \right)$.

A given system model necessarily determines $\mathfrak{L}\left(\mathfrak{M}\right)$, unique up to alphabetic invariants. We should notice that $\mathfrak{L}\left(\mathfrak{M}\right)$ is a collection of “symbols,” therefore the role of $\mathfrak{L}\left(\mathfrak{M}\right)$ in the systems recognition is to point out the names and types of the relations that are identified in the system we recognize.

On the other hand, Σ provides the rules how elements in a system model interact. Therefore the properties of a system implied by the structure of the system are expressed as the formulas derived from Σ; $T\left(\Sigma \right)=\left\{\phi \in \mathrm{Sent}\left(\mathfrak{L}\left(\mathfrak{M}\right)\right)|\Sigma \vdash \phi \right\}$ is the whole of the properties characterized by the structure of the system, $\left(\mathfrak{L}\left(\mathfrak{M}\right);\Sigma \right)$. If Σ is complete, the properties satisfied by a system model having the structure $\left(\mathfrak{L}\left(\mathfrak{M}\right);\Sigma \right)$ accord with the properties of a system implied by $\left(\mathfrak{L}\left(\mathfrak{M}\right);\Sigma \right)$); that is, let $\mathrm{Th}\left(\mathfrak{M}\right)=\left\{\phi \in \mathrm{Sent}\left(\mathfrak{L}\left(\mathfrak{M}\right)\right)|\mathfrak{M}\models \phi, \mathfrak{M}\models \Sigma \right\}$, then $\mathrm{Th}\left(\mathfrak{M}\right)=T\left(\Sigma \right)$. Notice that it follows from the definition that $\left(\mathfrak{L}\left(\mathfrak{M}\right);\Sigma \right)$ cannot be uniquely determined for one system model $\mathfrak{M}$ since we can take another Σ as axioms for which $\mathfrak{M}$ is a model. This means that there may be plenty of system models satisfying a given structure $\left(\mathfrak{L}\left(\mathfrak{M}\right);\Sigma \right)$. For example, many models satisfy the Peano’s Axioms well known as a structure of the natural number. They are not necessarily isomorphic to the natural numbers (Chang & Keisler, 1973).

As an example we define below the structure of input-output system.

Definition 5.5 [The Structure of Input-Output System]

The structure of input-output system model is defined by (${\mathfrak{L}}_{I/O}$;Σ_I/O):

$$ {\mathfrak{L}}_{I/O}=\left\{\mathbf{X},\mathbf{Y},\mathbf{S}\right\}, $$

where

• X, Y: unary relation symbols,

• S: a binary relation symbol;

$$ {\Sigma}_{I/O}=\left\{{\phi}_{I/O}\right\}, $$

where ϕ _I/O ≡ (∀xy)(S(x, y) → X(x) ∧ Y(y)).

An input-output system model M _I/O = 〈X ∪ Y; S, X, Y〉 is a realization of ${\mathfrak{L}}_{I/O}$ and model for Σ_I/O.

3.4 Morphism

One of the most important purposes of systems science is to investigate the similarity between system models. The similarity can be divided into two types: structural similarity and behavioral similarity. So far, fixing the type of models, we have studied structural similarity in systems theory using modeling morphisms defined especially between input-output system models. However, as will be made clear in the subsequent discussions, these modeling morphisms are defined not in a general way in which we can deal with structural similarity between any system models, but in a specific way based only on homomorphisms. This section is devoted to the development of a general theory of structural similarity between system models.

3.4.1 Morphisms for Models of the Same Type

In this section we investigate morphisms between system models of the same type, following the three cases mentioned in the previous section.

3.4.1.1 Preservation of Generator: Homomorphism

A morphism between system models of the same type is usually given by a homomorphism, which preserves only atomic formulas as the generators of the language.

Definition 5.6 [Homomorphism]

Let ${\mathfrak{M}}_1=\left\langle {M}_1;\left\{{R_i}^1|i\in I\right\},\left\{{f_j}^1|j\in J\right\}\right\rangle$ and ${\mathfrak{M}}_2=\left\langle {M}_2;\left\{{R_i}^2|i\in I\right\},\left\{{f_j}^2|j\in J\right\}\right\rangle$. Notice that ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ are of the same type. A function h : M ₁ → M ₂ is called a homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ if for any i ∈ I, j ∈ J, a ₁, …, a _λ(i), a ₁, …, a _μ(j), a ∈ M ₁, $\left({a}_1,\dots, {a}_{\lambda (i)}\right)\in {R}_i^1$ implies $\kern0.5em \left(h\left({a}_1\right),\dots, h\left({a}_{\lambda (i)}\right)\right)\in {R}_i^2$ and $h\left({f}_j^1\left({a}_1,\dots, {a}_{\mu (j)}\right)\right)={f}_j^2\left(h\left({a}_1\right),\dots, h\left({a}_{\mu (j)}\right)\right)$.

A bijective (i.e., one-to-one and onto) homomorphism is called an isomorphism.

From Definition, we can see that a homomorphism preserves only the atomic formulas, which is viewed as the generators of the language for a system model. In systems theory, the concept of a homomorphism is defined as a modeling morphism between input-output system models.

Definition 5.7 [Modeling Morphism] (Mesarovic & Takahara, 1975, 1989)

Let S ⊂ X × Y and S ^′ ⊂ X ^′ × Y ^′ be input-output system models. Let h _x : X → X ^′ and h _y : Y → Y ^′ be functions. h = (h _x, h _y) : S → S ^′ is called a modeling morphism of S to S ^′ if for any (x, y) ∈ X × Y, (x, y) ∈ S implies (h _x(x), h _y(y)) ∈ S ^′.

For example, let us consider input-output system models $\mathfrak{M}=\left\langle X\cup Y;S,X,Y\right\rangle$ and ${\mathfrak{M}}^{\prime }=\left\langle {X}^{\prime}\cup {Y}^{\prime };{S}^{\prime },{X}^{\prime },{Y}^{\prime}\right\rangle$, where S, S ^′: binary relations on X ∪ Y and X, X ^′, Y, Y ^′: unary relations on X ∪ Y. Suppose that $\mathfrak{M}$ and ${\mathfrak{M}}^{\prime }$ satisfy S(X, Y) → X(X) ∧ Y(Y) and S ^′(X, Y) → X ^′(X) ∧ Y ^′(Y), respectively. Then a homomorphism h of $\mathfrak{M}$ to ${\mathfrak{M}}^{\prime }$ is regarded as a modeling morphism of S to S ^′. Notice that from the definition of a homomorphism, h(x) ∈ X ^′ for any x ∈ X and h(y) ∈ Y ^′ for any y ∈ Y.

3.4.1.2 Preservation of Σ: Σ-Homomorphism

Next we consider homomorphisms preserving axioms Σ. Recall that the axioms Σ provide the structure of a system.

Grätzer defined such homomorphisms as Σ-homomorphisms (Grätzer, 1979). By a Σ-homomorphism the axioms Σ are preserved in a homomorphic image. We formulate a Σ-homomorphism directly based on this idea. This definition is different from Grätzer’s original definition that uses the concept of Φ − l inverse.

Let h be a homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$. The homomorphic image of h in ${\mathfrak{M}}_2$ is a submodel of ${\mathfrak{M}}_2$ whose domain is $h\left({\mathfrak{M}}_1\right)$. We write $h\left({\mathfrak{M}}_1\right)$ to indicate the homomorphic image of h in ${\mathfrak{M}}_2$ as follows.

$$ h\left({\mathfrak{M}}_1\right)=\left\langle h\left({M}_1\right);\left\{{R}_i^2\cap h{\left({M}_1\right)}^{\lambda (i)}|i\in I\right\},\left\{{f}_j^2\parallel h{\left({M}_1\right)}^{\mu (j)}|j\in J\right\}\right\rangle, $$

where ${f}_j^2\parallel h{\left({M}_1\right)}^{\mu (j)}$ denotes the restriction of ${f}_j^2$ to h(M ₁)^μ(j).

By the property of a homomorphism, ${f}_j^2\parallel h{\left({M}_1\right)}^{\mu (j)}$ is well-defined.

We define a Σ-homomorphism as a homomorphism whose homomorphic image preserves Σ.

Definition 5.8 [Σ-Homomorphism]

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be system models of the same type, and ${\mathfrak{M}}_1\models \Sigma$ and ${\mathfrak{M}}_2\models \Sigma$. A homomorphism h of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ is called a Σ-homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$, if $h\left({\mathfrak{M}}_1\right)\models \Sigma$.

Our definition of Σ-homomorphism is slightly weaker than Grätzer’s definition using the concept of Φ − l inverse. His definition requires that any “inverse” elements should be preserved. A homomorphism that has the Φ − l inverses is defined as a strong Σ-homomorphism. The axioms Σ are preserved in the homomorphic image on h in ${\mathfrak{M}}_2$ by a strong Σ-homomorphism h. So the homomorphic image of a strong Σ-homomorphism h, $h\left({\mathfrak{M}}_1\right)$, is a model of Σ, i.e., $h\left({\mathfrak{M}}_1\right)\models \Sigma$.

3.4.1.3 Preservation of $\mathrm{Th}\left(\mathfrak{M}\right)$: S-Homomorphism

That two system models are isomorphic or of the same structure implies that in a sense the properties of the two system models are equivalent. A usual homomorphism preserves the primitive properties, i.e., the generators. In this section we will define a homomorphism as an S-homomorphism that preserves all sentences satisfied in a system model ($\mathrm{Th}\left(\mathfrak{M}\right)$). Furthermore we will show that an induced homomorphism is an S-homomorphism, which is well known as the homomorphism theorem. From this theorem we can see that every morphism for the structural similarity should be an S-homomorphism.

Definition 5.9 [S-Homomorphism]

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be system models of the same type, and $h:{\mathfrak{M}}_1\to {\mathfrak{M}}_2$ a homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$. Then h is called an S-homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ if for any sentence ϕ of $\mathfrak{L}\left({\mathfrak{M}}_1\right)$

$$ {\mathfrak{M}}_1\models \phi \kern1em \mathrm{if}\kern0.5em \mathrm{and}\kern0.5em \mathrm{only}\kern0.5em \mathrm{if}\kern0.5em h\left({\mathfrak{M}}_1\right)\models \phi . $$

From the definition we can immediately see that an S-homomorphism is a Σ-homomorphism. We should notice that if every sentence that holds in ${\mathfrak{M}}_1$ holds in $h\left({\mathfrak{M}}_1\right)$ as well, then h is already an S-homomorphism. Indeed if a sentence ϕ holds in $h\left({\mathfrak{M}}_1\right)$ and does not hold in ${\mathfrak{M}}_1$, then ¬ϕ holds in ${\mathfrak{M}}_1$. Thus, by the above condition, ¬ϕ holds in $h\left({\mathfrak{M}}_1\right)$, which is a contradiction.

Let $h:{\mathfrak{M}}_1\to {\mathfrak{M}}_2$ be a homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$. Then we define the quotient system model with respect to h, written by ${\mathfrak{M}}_1/h$:

$$ {\mathfrak{M}}_1/h=\left\langle {M}_1/h;\left\{{R}_i^1/h|i\in I\right\},\left\{{f}_j^1/h|j\in J\right\}\right\rangle, $$

where ${\mathfrak{M}}_1=\left\langle {M}_1;\left\{{R_i}^1|i\in I\right\},\left\{{f_j}^1|j\in J\right\}\right\rangle$ and ${\mathfrak{M}}_2=\left\langle {M}_2;\left\{{R_i}^2|i\in I\right\},\right.$ $\left.\left\{{f_j}^2|j\in J\right\}\right\rangle$; M ₁/h is the partitioned set of M ₁ by the equivalence relation defined by:

$$ a\equiv b\kern1em \mathrm{if}\kern0.5em \mathrm{and}\kern0.5em \mathrm{only}\kern0.5em \mathrm{if}\kern0.5em h(a)=h(b)\kern0.5em \mathrm{for}\kern0.5em \mathrm{any}\kern0.5em a,b\in {M}_1, $$

$s\left(\left[{a}_1\right],\dots, \left[{a}_{\lambda (i)}\right]\right)\in {R}_i^1/h$ if and only if $\left(h\left({a}_1\right),\dots, h\left({a}_{\lambda (i)}\right)\right)\in {R}_i^2$, ${f}_j^1/h\left(\left[{a}_1\right],\dots, \left[{a}_{\mu (j)}\right]\right)=\left[{f}_j^1\left({a}_1,\dots, {a}_{\mu (j)}\right)\right]$.

[a _i] denotes the equivalence class of a _i.

The quotient system model, ${\mathfrak{M}}_1/h$, is obviously well-defined. The well-known homomorphism theorem can be considered as a theorem by which an S-homomorphism, h ^#, is induced.

Theorem 5.1 [Homomorphism Theorem]

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be system models of the same type, and h a homomorphism of ${\mathfrak{M}}_1$ onto ${\mathfrak{M}}_2$ . Then a map

$$ {h}^{\#}:{\mathfrak{M}}_1/h\to {\mathfrak{M}}_2 $$

is an S-homomorphism, where h ^# is defined by:

$$ {h}^{\#}\left(\left[a\right]\right)=h(a)\kern0.5em \mathrm{for}\kern0.5em \mathrm{any}\kern0.5em \left[a\right]\in {M}_1/h $$

h ^# is called the induced homomorphism of h.

A difference between the well-known homomorphism theorem in the usual form in algebra and this theorem is that theorem shows that the induced isomorphism h ^# is an S-homomorphism preserving sentences. One of the reasons why the concept of a homomorphism is important is because an S-homomorphism h ^# can be constructed from a homomorphism h.

3.4.2 Morphisms for Models of Different Types

In this section we consider morphisms between system models of different types. Since a homomorphism as seen in the previous section can be defined only for system models of the same type, the concept of a homomorphism is not applicable to the class of system models of different types. We, therefore, introduce a new morphism, called F-morphism, which is a generalization of homomorphism and can be applied to the class of system models of different types as well as of the same type.

In this section we also consider the three cases for the preservation of properties—generators, Σ, and $\mathrm{Th}\left(\mathfrak{M}\right)$. We will show F-morphism theorem as a theorem corresponding to the homomorphism theorem.

3.4.2.1 Preservation of Generator: F-Morphism

First we define a basic interpretation function and a basic morphism. An F-morphism is defined recursively by using these functions.

Definition 5.10 [Basic Interpretation Function]

Let ${\mathfrak{M}}_1=\left\langle {M}_1;\left\{{R_i}^1|i\in {I}_1\right\}\right.,$ $\left.\left\{{f_j}^1|j\in {J}_1\right\}\right\rangle$ and ${\mathfrak{M}}_2=\left\langle {M}_2;\left\{{R_i}^2|i\in {I}_2\right\},\left\{{f_j}^2|j\in {J}_2\right\}\right\rangle$ be system models of possibly different types.

Then a function Bas of $\mathfrak{L}\left({\mathfrak{M}}_1\right)$ to the set of formulas of $\mathfrak{L}\left({\mathfrak{M}}_2\right)$ is said to be a basic interpretation function of $\mathfrak{L}\left({\mathfrak{M}}_1\right)$ to $\mathfrak{L}\left({\mathfrak{M}}_2\right)$ if the following conditions are satisfied.

• 1. For every relation symbol ${{\mathbf{R}}_i}^1\in \mathfrak{L}\left({\mathfrak{M}}_1\right)$, Bas(R _i ¹) is a λ ₁(i)-ary formula of $\mathfrak{L}\left({\mathfrak{M}}_1\right)$;

• 2. For every function symbol ${{\mathbf{f}}_i}^1\in \mathfrak{L}\left({\mathfrak{M}}_1\right)$, Bas(f _i ¹) is a (μ ₁(j) + 1)-ary formula of $\mathfrak{L}\left({\mathfrak{M}}_2\right)$.

A basic interpretation function associates a formula of the second system model with each symbol of the language of the first one. The association is intended to give “interpretation” of the first system model to the second one. The basic interpretation function works as a meaningful interpretation only when a basic morphism with it is defined as follows.

Definition 5.11 [Basic Morphism]

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be as above and Bas be a basic interpretation function of $\mathfrak{L}\left({\mathfrak{M}}_1\right)$ to $\mathfrak{L}\left({\mathfrak{M}}_2\right)$.

A function I _O of M ₁ to M ₂ is said to be a basic morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ with Bas if the following conditions are satisfied.

• 1. For every relation symbol ${\mathbf{R}}_{\mathbf{i}}^{\mathbf{1}}\in \mathfrak{L}\left({\mathfrak{M}}_1\right)$ and every assignment ρ, if ${\mathfrak{M}}_1\models {\mathbf{R}}_{\mathbf{i}}^{\mathbf{1}}\left({\mathbf{x}}_{\mathbf{1}},\dots, {\mathbf{x}}_{{\boldsymbol{\uplambda}}_{\mathbf{1}}\left(\mathbf{i}\right)}\right)\left[\rho \right]$, then ${\mathfrak{M}}_2\models \mathrm{Bas}\left({\mathbf{R}}_{\mathbf{i}}^{\mathbf{1}}\right)\left({\mathbf{x}}_{\mathbf{1}},\dots, {\mathbf{x}}_{{\boldsymbol{\uplambda}}_{\mathbf{1}}\left(\mathbf{i}\right)}\right)\left[{I}_{\mathrm{O}}\circ \rho \right]$ _, where I _O ∘ ρ denotes the composition of I _O andρ;

• 2. For every function symbol ${\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\in \mathfrak{L}\left({\mathfrak{M}}_1\right)$ and every assignment ρ, if ${\mathfrak{M}}_1\models \left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\left({\mathbf{x}}_{\mathbf{1}},\dots, {\mathbf{x}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)}\right)={\mathbf{x}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)+\mathbf{1}}\right)\left[\rho \right]$, then ${\mathfrak{M}}_2\models \mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)\left({\mathbf{x}}_{\mathbf{1}},\dots, {\mathbf{x}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)+\mathbf{1}}\right)$ $\left[{I}_{\mathrm{O}}\circ \rho \right],$ and satisfies the following condition expressing that $\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)$ is a function: ${\mathfrak{M}}_2\models \left(\forall {\mathbf{x}}_{\mathbf{1}}\dots {\mathbf{x}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)}\right)\left(\exists {\mathbf{x}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)+\mathbf{1}}\right)\left(\forall {\mathbf{y}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)+\mathbf{1}}\right)\left(\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)\right.$ $\left.\left({\mathbf{x}}_{\mathbf{1}},\dots, {\mathbf{x}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)}, {\mathbf{y}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)+\mathbf{1}}\right)\leftrightarrow {\mathbf{x}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)+\mathbf{1}}={\mathbf{y}}_{{\boldsymbol{\upmu}}_{\mathbf{1}}\left(\mathbf{j}\right)+\mathbf{1}}\right)$.

$\mathrm{Bas}\left({\mathbf{R}}_{\mathbf{i}}^{\mathbf{1}}\right)$ and $\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)$ are called basic interpretations of ${\mathbf{R}}_{\mathbf{i}}^{\mathbf{1}}$ and ${\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}$. The identity= is interpreted as the identity of $\mathfrak{L}\left({\mathfrak{M}}_2\right)$, that is, $\mathrm{Bas}\left({=}_{\mathfrak{L}\left({\mathfrak{M}}_1\right)}\right)\equiv {=}_{\mathfrak{L}\left({\mathfrak{M}}_2\right)}$.

Definition 5.12 [F-morphism]

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be as in Definition of Basic Morphism]. An F-morphism, $I:{\mathfrak{M}}_1\to {\mathfrak{M}}_2$, is a pair of functions 〈I _O, I _F〉, where I _O is a basic morphism of with Bas and I _F is a function of the set of formulas of ${\mathfrak{M}}_1$ to the set of the formulas of ${\mathfrak{M}}_2$, which is defined as follows.

For any formula Φ of ${\mathfrak{M}}_1$

• 1. If Φ is an atomic formula of the form f _j(u ₁, …, u _μ(j)) = x or x = f _j(u ₁, …, u _μ(j)), then

  $$ {I}_{\mathrm{F}}\left(\Phi \right)=\left\{\begin{array}{ll}\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}\right)\left({u}_1,\dots, {u}_{\mu (j)},\mathbf{x}\right),& \mathrm{if}\kern0.5em T\left(\Phi \right)\kern0.5em \mathrm{is}\kern0.5em \mathrm{the}\kern0.5em \mathrm{empty}\kern0.5em \mathrm{set}\\ \left(\exists {\mathbf{x}}_{{\mathbf{k}}_{\mathbf{1}}}\dots {\mathbf{x}}_{{\mathbf{k}}_{\mathbf{m}}}\right)\\\times\left(\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}\right)\left({\mathbf{x}}_{\mathbf{1}},\dots, {\mathbf{x}}_{\boldsymbol{\upmu} \left(\mathbf{j}\right)},\mathbf{x}\right)\right.\\\times\left.\wedge \left(\wedge \left({I}_F\left({\mathbf{x}}_{{\mathbf{k}}_{\mathbf{i}}}={u}_{k_i}\right)|{u}_{k_i}\right.\right.\right.\\\hspace*{-2pt}\left.\left.\left.\in T\left(\Phi \right)\right)\right)\right),& \mathrm{if}\kern0.5em T\left(\Phi \right)=\left\{{u}_{k_1},\dots, {u}_{k_m}\right\}\end{array}\right., $$

  where every ${\mathbf{x}}_{{\mathbf{k}}_{\mathbf{p}}}$ is a variable not occurring in Φ, and x _i is u _i for $u_{i}\notin T(\varPhi)$.

• 2. If Φ is an atomic formula P(t ₁, …, t _n) other than of the form in (1), then

  $$ {I}_{\mathrm{F}}\left(\Phi \right)=\left\{\begin{array}{ll}\mathrm{Bas}\left(\mathbf{P}\right)\left({u}_1,\dots, {u}_n\right),& \mathrm{if}\kern0.5em T\left(\Phi \right)\kern0.5em \mathrm{is}\kern0.5em \mathrm{the}\kern0.5em \mathrm{empty}\kern0.5em \mathrm{set}\\ \left(\exists {\mathbf{x}}_{{\mathbf{k}}_{\mathbf{1}}}\dots {\mathbf{x}}_{{\mathbf{k}}_{\mathbf{m}}}\right)\\\times\left(\mathrm{Bas}\left(\mathbf{P}\right)\left({\mathbf{x}}_{\mathbf{1}},\dots, {\mathbf{x}}_n\right)\right.\\\left.\wedge \left(\wedge \left({I}_F\left({\mathbf{x}}_{{\mathbf{k}}_{\mathbf{i}}}={u}_{k_i}\right)|{u}_{k_i}\right.\right.\right.\\\hspace*{-2pt}\left.\left.\left.\in T\left(\Phi \right)\right)\right)\right),& \mathrm{if}\kern0.5em T\left(\Phi \right)=\left\{{u}_{k_1},\dots, {u}_{k_m}\right\}\end{array}\right., $$

  where every ${\mathbf{x}}_{{\mathbf{k}}_{\mathbf{p}}}$ is a variable not occurring in P, and x _i is u _i for $u_{i}\notin T(\varPhi)$.

• 3. Otherwise,

  $$ {I}_{\mathrm{F}}\left(\neg \Phi \right)=\neg \left({I}_{\mathrm{F}}\left(\Phi \right)\right), \vspace*{-1pc}$$
  $$ {I}_{\mathrm{F}}\left({\Phi}_1\wedge {\Phi}_2\right)=\left({I}_{\mathrm{F}}\left({\Phi}_1\right)\right)\wedge \left({I}_{\mathrm{F}}\left({\Phi}_2\right)\right), \vspace*{-1pc}$$
  $$ {I}_{\mathrm{F}}\left(\forall \mathbf{x}\Phi \right)=\left(\forall \mathbf{x}\right)\left({I}_{\mathrm{F}}\left(\Phi \right)\right). $$

Since T(Φ) eventually becomes empty, I _F is well-defined.

Let us consider an example of F-morphisms.

Example 5.4

We can define an F-morphism of (N; ≤) to (N; +), where N is the set of natural numbers, ≤ the linear ordering on N and + addition. If we define Bas by Bas(≤) = (∃z)(x + z = y) and I _O by the identity, then 〈I _O, I _F〉 with Bas is an F-morphism of (N; ≤) to (N; +).

We should notice that the function I _F is “automatically” defined according to the definition if I _O with Bas is already defined. Furthermore it is clear that if (N; ≤) ⊨ ϕ, then(N; +) ⊨ I _F(ϕ). For example, let ϕ be a sentence (∀xyz)(x ≤ y ∧ y ≤ z → x ≤ z). Then

$$ {\displaystyle \begin{array}{c}{I}_{\mathrm{F}}\left(\phi \right)={I}_{\mathrm{F}}\left(\left(\forall \mathbf{x}\mathbf{yz}\right)\left(\mathbf{x}\le \mathbf{y}\wedge \mathbf{y}\le \mathbf{z}\to \mathbf{x}\le \mathbf{z}\right)\right)\\ {}=\left(\forall \mathbf{x}\mathbf{yz}\right)\left({I}_{\mathrm{F}}\left(\mathbf{x}\le \mathbf{y}\right)\wedge {I}_{\mathrm{F}}\left(\mathbf{y}\le \mathbf{z}\right)\to {I}_{\mathrm{F}}\left(\mathbf{x}\le \mathbf{z}\right)\right)\\ {}=\left(\forall \mathbf{x}\mathbf{yz}\right)\left(\left(\exists {\mathbf{z}}_{\mathbf{1}}\right)\left(\mathbf{x}+{\mathbf{z}}_{\mathbf{1}}=\mathbf{y}\right)\wedge \left(\exists {\mathbf{z}}_{\mathbf{2}}\right)\left(\mathbf{x}+{\mathbf{z}}_{\mathbf{2}}=\mathbf{y}\right)\to \left(\exists {\mathbf{z}}_{\mathbf{3}}\right)\left(\mathbf{x}+{\mathbf{z}}_{\mathbf{3}}=\mathbf{y}\right)\right).\end{array}} $$

So (N; +) ⊨ I _F(ϕ).

Example 5.5 [Automaton]

A Moore type automaton, M _r = (A, B, C, ϕ _r, λ _r) with A, B, C: finite sets, ϕ _r : C × A → C and λ _r : C → B, is regarded as equivalent to a Mealy type automaton, M _e = (A, B, C, ϕ _e, μ _e) with A, B, C: finite sets, ϕ _e : C × A → C and μ _e : C × A → B. Let

$$ \mathrm{Moore}=\left\langle A\cup B\cup C;A,B,C,{\hat{\phi}}_r,{\hat{\lambda}}_r\right\rangle $$

and

$$ \mathrm{Mealy}=\left\langle A\cup B\cup C;A,B,C,{\hat{\phi}}_e,{\hat{\mu}}_e\right\rangle, $$

where A, B, C: unary relations, ${\hat{\phi}}_{\mathrm{r}},{\hat{\lambda}}_{\mathrm{r}},{\hat{\phi}}_{\mathrm{e}},{\hat{\mu}}_{\mathrm{e}}$: arbitrary extensions of ϕ _r, λ _r, ϕ _e, μ _e respectively, and ${\hat{\phi}}_{\mathrm{r}}={\hat{\phi}}_{\mathrm{e}},{\hat{\mu}}_{\mathrm{e}}\left(c,a\right)={\hat{\lambda}}_{\mathrm{r}}\left({\hat{\phi}}_{\mathrm{r}}\left(c,a\right)\right)$ for any c, a ∈ A ∪ B ∪ C.

Then we can define an F-morphism of Mealy to Moore as follows.

$$ {I}_{\mathrm{O}}:\mathrm{the}\kern0.5em \mathrm{identity}\Big\}, \vspace*{-1pc}$$

$$ \mathrm{Bas}\left({\hat{\phi}}_{\mathbf{e}}\right)={\hat{\phi}}_{\mathbf{r}}\left(\mathbf{x},\mathbf{y},\mathbf{z}\right),\vspace*{-1pc} $$

$$ \mathrm{Bas}\left({\hat{\boldsymbol{\upmu}}}_{\mathbf{e}}\right)=\left({\hat{\boldsymbol{\uplambda}}}_{\mathbf{r}}\left({\hat{\phi}}_{\mathbf{r}}\left(\mathbf{x},\mathbf{y}\right)\right)=\mathbf{z}\right),\vspace*{-1pc} $$

$$ \mathrm{Bas}\left(\mathbf{A}\right)=\mathbf{A},\kern1em \mathrm{Bas}\left(\mathbf{B}\right)=\mathbf{B},\kern1em \mathrm{Bas}\left(\mathbf{C}\right)=\mathbf{C}. $$

These definitions obviously satisfy the conditions of basic morphisms. The following corollary shows that an F-morphism is an extension of a homomorphism.

Corollary 5.1

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be system models of the same type, and h a homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ . Then h is a basic morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ , and 〈h, I _F〉 is an F-morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ , where I _F is a function uniquely determined by h in Definition of F-morphism.

From the definition of basic morphism we can see that an F-morphism preserves generators. Notice that it is necessary to give an interpretation I _F of the generators in defining an F-morphism, while in the case of a homomorphism I _F is trivially defined, and is not explicitly given in usual algebra.

3.4.2.2 Preservation of Σ: Σ_F-Morphism

In this section we will define an F-morphism preserving axioms Σ as a Σ_F-morphism. By a Σ_F-morphism, Σ is preserved in an image of an F-morphism. First we define the image of a basic morphism.

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be system models of possibly different types. Let $I=\left\langle {I}_{\mathrm{O}},{I}_{\mathrm{F}}\right\rangle :{\mathfrak{M}}_1\to {\mathfrak{M}}_2$ be an F-morphism. Then the image of a basic morphism, written $I\left({\mathfrak{M}}_1\right)$, is defined by:

$$ \begin{array}{lllll}I\left({\mathfrak{M}}_1\right)&=&\left\langle {I}_{\mathrm{O}}\left({M}_1\right);\left\{{R}_i^2\cap {I}_{\mathrm{O}}{\left({M}_1\right)}^{\lambda_2(i)}|i\in {I}_2\right\},\right.\\&&\left.\left\{{f}_j^2\parallel {I}_{\mathrm{O}}{\left({M}_1\right)}^{\mu_2(j)}|{f}_j^2\left({a}_1,\dots, {a}_{\mu_2(j)}\right)\in {I}_{\mathrm{O}}\left({M}_1\right)\right.\right.\\&&\times\left.\left.\mathrm{for}\kern0.5em \mathrm{any}\kern0.5em {a}_1,\dots, {a}_{\mu_2(j)}\in {I}_{\mathrm{O}}\left({M}_1\right),j\in {J}_2\right\}\right.\Big\rangle.\vspace*{-6pt}\end{array} $$

Notice that if there exists a j such that $f^{2}_{j}(a_{1},\ldots ,a_{\mu_{2}(j)})\notin I_{\mathrm{O}}M_{1}$ for ${a}_1,\dots, {a}_{\mu_2(j)}\in {I}_{\mathrm{O}}\left({M}_1\right)$, then $I\left({\mathfrak{M}}_1\right)$ is of a different type from ${\mathfrak{M}}_2$. An F-morphism is called an onto F-morphism if its basic morphism is onto.

Definition 5.13 [Σ_F-Morphism]

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be system models and I = 〈I _O, I _F〉 an F-morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$. Suppose${\mathfrak{M}}_1\models \Sigma$. Then I is called a Σ_F -morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ if

$$ I\left({\mathfrak{M}}_1\right)\models {I}_{\mathrm{F}}\left(\Sigma \right), $$

where I _F(Σ) = {I _F(Φ)| Φ ∈ Σ}.

A Σ_F-morphism is a kind of extension of a Σ_F-homomorphism. The following corollary says that a Σ_F-morphism between system models of the same type accords with a Σ-homomorphism.

Corollary 5.2

Let ${\mathfrak{M}}_1$ and ${\mathfrak{M}}_2$ be system models of the same type. Let $h:{\mathfrak{M}}_1\to {\mathfrak{M}}_2$ be a homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ . Suppose ${\mathfrak{M}}_1,{\mathfrak{M}}_2\models \Sigma$ . Then h is a Σ-homomorphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ if and only if 〈h, I _F〉 is a Σ_F -morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ .

3.4.2.3 Preservation of $\mathrm{Th}\left(\mathfrak{M}\right)$: S_F-Morphism

In this section we define a morphism between system models of different types, which preserves $\mathrm{Th}\left(\mathfrak{M}\right)$ of a system model. Furthermore we will show the F-morphism theorem corresponding to the homomorphism theorem in the case of the same type. The F-morphism theorem gives a relationship between an F-morphism and an S_F-morphism. Unless mentioned explicitly, in the sequel let ${\mathfrak{M}}_1$, ${\mathfrak{M}}_2$ be system models and I = 〈I _O, I _F〉 an F-morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$.

Definition 5.14 [S_F-Morphism]

An F-morphism I is called an S _F -morphism of ${\mathfrak{M}}_1$ to ${\mathfrak{M}}_2$ if for any sentence Φ of $\mathfrak{L}\left({\mathfrak{M}}_1\right)$, ${\mathfrak{M}}_1\models \Phi$ if and only if $I\left({\mathfrak{M}}_1\right)\models {I}_{\mathrm{F}}\left(\Phi \right)$.

From the definition an S_F-morphism is a Σ_F-morphism. In general, we can check whether an F-morphism is an S_F-morphism by the way based on a structural induction on sentences. However in most cases, they are more than routine tasks.

For an onto F-morphism I, we define the quotient system model with respect to I by:

$$ {\mathfrak{M}}_1/I=\left\langle {M}_1/{I}_{\mathrm{O}}:\left\{{R}_i^1/I|i\in {I}_1\right\},\left\{{f}_j^1/I|j\in {J}_1\right\}\right), $$

where M ₁/I _O is the partitioned set of M ₁ by the equivalence relation ${\equiv}_{I_{\mathrm{O}}}$ defined by:

$$ a{\equiv}_{I_{\mathrm{O}}}b\kern1em \mathrm{if}\kern0.5em \mathrm{and}\kern0.5em \mathrm{only}\kern0.5em \mathrm{if}\kern0.5em {I}_{\mathrm{O}}(a)={I}_{\mathrm{O}}(b)\kern0.5em \mathrm{for}\kern0.5em \mathrm{any}\kern0.5em a,b\in {M}_{\mathbf{1}}, \vspace*{-1.5pc}$$

$$ {R}_i^1/I\left(\left[{a}_1\right],\dots, \left[{a}_{\lambda_1(i)}\right]\right)\kern1em \mathrm{if}\kern0.5em \mathrm{and}\kern0.5em \mathrm{only}\kern0.5em \mathrm{if}\kern0.5em \mathrm{Bas}\left({R}_i^1\right)\left({I}_{\mathrm{O}}\left({a}_1\right),\dots, {I}_{\mathrm{O}}\left({a}_{\lambda_1(i)}\right)\right), \vspace*{-1.5pc}$$

$$ {f}_j^1/I\left(\left[{a}_1\right],\dots, \left[{a}_{\mu_1(j)}\right]\right)=\left[{f}_j^1\left({a}_1,\dots, {a}_{\mu_1(j)}\right)\right], $$

where [a] represents an equivalence class in M ₁/I _O by ${\equiv}_{I_{\mathrm{O}}}$.

The above definition of ${f}_j^1/I$ is well-defined. Indeed, suppose ${I}_{\mathrm{O}}\left({a}_1\right)={I}_{\mathrm{O}}\left({b}_1\right),\dots, {I}_{\mathrm{O}}\left({a}_{\mu_1(j)}\right)={I}_{\mathrm{O}}\left({b}_{\mu_1(j)}\right)$ and${f}_j^1\left({a}_1,\dots, {a}_{\mu_1(j)}\right)={c}_1$, ${f}_j^1\left({b}_1,\dots, {b}_{\mu_1(j)}\right)={c}_2$ hold in ${\mathfrak{M}}_1$. Then since I is an F-morphism, $\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)\left({I}_{\mathrm{O}}\left({a}_1\right),\dots, {I}_{\mathrm{O}}\left({a}_{\mu_1(j)}\right),{I}_{\mathrm{O}}\left({c}_1\right)\right)$ and $\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)\left({I}_{\mathrm{O}}\left({b}_1\right),\dots,\right.$ $\left.{I}_{\mathrm{O}}\left({b}_{\mu_1(j)}\right),{I}_{\mathrm{O}}\left({c}_1\right)\right)$ hold in ${\mathfrak{M}}_2$. Since $\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)$ is a function from the definition of basic morphism, we have I _O(c ₁) = I _O(c ₂).

The following is one of the main theorems about F-morphisms.

Theorem 5.2 [F-Morphism Theorem]

Let $I:{\mathfrak{M}}_1\to {\mathfrak{M}}_2$ be an onto F-morphism. Then

$$ {I}_{\mathrm{O}}^{\#}:{\mathfrak{M}}_1/I\to {\mathfrak{M}}_2 $$

is a one-to-one basic morphism, furthermore

$$ {I}^{\#}=\left\langle {I}_{\mathrm{O}}^{\#},{I}_{\mathrm{F}}^{\#}\right\rangle $$

is an S _F -morphism, where ${I}_{\mathrm{O}}^{\#}$ is defined by

$$ {I}_{\mathrm{O}}^{\#}\left(\left[a\right]\right)={I}_{\mathrm{O}}(a)\kern1em \mathrm{for}\kern0.5em \left[a\right]\in {M}_1/{I}_{\mathrm{O}} $$

and the basic interpretations are

$$ {\mathrm{Bas}}^{\#}\left({\mathbf{R}}_{\mathbf{i}}^{\mathbf{1}}/I\right)=\mathrm{Bas}\left({\mathbf{R}}_{\mathbf{i}}^{\mathbf{1}}\right)\kern1em \mathrm{for}\kern0.5em i\in {I}_1, \vspace*{-1.5pc}$$

$$ {\mathrm{Bas}}^{\#}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}/I\right)=\mathrm{Bas}\left({\mathbf{f}}_{\mathbf{j}}^{\mathbf{1}}\right)\kern1em \mathrm{for}\kern0.5em i\in {J}_1. $$

I ^# is called the induced F-morphism of I.

F-morphism enhances the concept of “isomorphism” between system models to those of different types, which means that the two models described in “different languages” are isomorphic in terms of F-morphism.

3.4.3 Application of F-Morphisms

A typical way to apply the F-morphism concept to concrete system models would be to construct an F-morphism between them. In this section, as an application of F-morphisms, we construct an F-morphism of a given finite automaton structure to a Petri net structure, and show the equivalence between a finite automaton and a Petri net. The equivalence means here that we can show that there is a Petri net that preserves all the properties of a given finite automaton. It is well known that Petri nets can represent finite automata (Peterson, 1981). The emphasis in this section, however, is on that the use of the F-morphism concept in considering the equivalence between a finite automaton and a Petri net reveals that each property of the finite automaton precisely (in a formal way) corresponds to some property of the Petri net, and the first-order sentences satisfied in the finite automaton are all preserved in the Petri net as corresponding sentences transformed by an F-morphism. Thus the F-morphism concept provides a formal meaning of “equivalence” between system models of different types, while the judgment of the equivalence “without F-morphisms” would depend fully on the intuition of a modeler constructing the correspondence between them.

3.4.3.1 Equivalence Between a Finite Automaton and a Petri Net

In this section we construct an F-morphism of a given finite automaton structure to a Petri net structure, and show that all the properties holding in the finite automaton also hold in the Petri net.

Definition 5.15

A finite automaton structure FA is the following system model.

$$ \mathrm{FA}=\left\langle A\cup B\cup C;A,B,C,\phi, \rho \right\rangle, $$

where

• A, B, C: unary relations

• ρ: binary functions such that

  • ϕ(a, b) ∈ C, if a ∈ C and b ∈ A

  • ϕ(a, b) = a, otherwise;

  • and ρ(a, b) ∈ B, if a ∈ C and b ∈ A

  • ρ(a, b) = a, otherwise.

The conditions on $a\notin C$ or $b\notin A$ for ϕ and ρ are imposed only to make the functions ϕ and ρ total, since the first-order language we use does not allow partial functions. However, since we will restrict the sentences to the extent as defined later, when we describe the properties of system models, we can regard ϕ and ρ intrinsically as ϕ : C × A → C and ρ : C × A → B.

Definition 5.16 [Petri Net Structure]

A Petri net structure PN is the following system model.

$$ \mathrm{PN}=\left\langle P\cup T\cup N;P,T,I,O,\hat{N}\right\rangle, $$

where

• P, T: unary relations

• N: the set of natural numbers

• $\hat{N}$: the set of constants corresponding to N

• I, O ⊂ P × T × N

P denotes the set of places and T the set of transitions. I(p, t, n) means that there are n arcs from the place p to the transition t. O(p, t, n) means that there are n arcs from the transition t to the place p.

There are some ways to construct PN that is considered to have an equivalent structure to FA (Peterson, 1981). Here following Peterson with some modification, we define PN considered as equivalent to FA. Then our aim is to construct an F-morphism between FA and PN, and to show that the constructed PN preserves all the properties satisfied in FA.

Definition 5.17

Given a finite automaton structure FA. We define the corresponding Petri net structure PN as follows.

$$ \mathrm{PN}=\left\langle P\cup T\cup N;P,T,I,O,\hat{N}\right\rangle, $$

where

• P = C ∪ A ∪ B;

• T = {t _i| i ∈ (C × A) ∪ A ∪ B};

• I = I ₁ ∪ I ₀,

where

• I ₁ = {(p, t _i, 1)| i = (c, a) ∈ C × A ∧ (p = c ∨ p = a)} ∪ {(p, t _i, 1)|i = p ∈ B},

• $I_{0} = \{(p,t_{i},0)|(p,t_{i},1)\notin I_{1},p\in P,t_{i}\in T\}$,

• O = O ₁ ∪ O ₀,

where

• O ₁ = {(p, t _i, 1)| i = (c, a) ∈ C × A ∧ (p = ϕ(c, a) ∨ ρ(c, a))} ∪ {(p, t _i, 1)| i = p ∈ A},

• $O_{0}= \{(p,t_{i},0)|(p,t_{i},1)\notin O_{1}, p\in P, t_{i}\in T\}$.

Definition 5.18

Let FA and PN be as in the above definitions, respectively. An F-morphism I = 〈I _O, I _F〉 : FA → PN is defined as follows.

• I _O: the inclusion map;

• I _F(A(x)) = (P(x) ∧ (∃t ∈ T)((∀p ∈ P)(I(p, t, 0) ∧ O(x, t, 1))));

• I _F(B(x)) = (P(x) ∧ (∃t ∈ T)((∀p ∈ P)(O(p, t, 0) ∧ I(x, t, 1))));

• I _F(C(x)) = (P(x) ∧  ¬ I _F(A(x)) ∧  ¬ I _F(B(x)));

• ${\displaystyle \begin{array}{l}\hspace*{-3pt}{I}_{\mathrm{F}}\left(\phi \left(\mathbf{x},\mathbf{y}\right)=\mathbf{z}\right)=\Big(\left({I}_{\mathrm{F}}\left(\mathbf{C}\left(\mathbf{x}\right)\right)\wedge {I}_{\mathrm{F}}\left(\mathbf{A}\left(\mathbf{y}\right)\right)\to \left(\exists \mathbf{t}\in \mathbf{T}\right)\left(\mathbf{I}\left(\mathbf{x},\mathbf{t},\mathbf{1}\right)\wedge \mathbf{I}\left(\mathbf{y},\mathbf{t},\mathbf{1}\right)\right.\right.\\\hspace*{-5pt}\left.\left.\wedge \mathbf{O}\left(\mathbf{z},\mathbf{t},\mathbf{1}\right)\wedge {I}_{\mathrm{F}}\left(\mathbf{C}\left(\mathbf{z}\right)\right)\right)\right)\wedge \left(\neg {I}_{\mathrm{F}}\left(\mathbf{C}\left(\mathbf{x}\right)\right)\vee \neg {I}_{\mathrm{F}}\left(\mathbf{A}\left(\mathbf{y}\right)\right)\to \mathbf{z}=\mathbf{x}\right)\Big);\end{array}}$

• ${\displaystyle \begin{array}{l}\hspace*{-3pt}{I}_{\mathrm{F}}\left(\rho \left(\mathbf{x},\mathbf{y}\right)=\mathbf{z}\right)=\Big(\left({I}_{\mathrm{F}}\left(\mathbf{C}\left(\mathbf{x}\right)\right)\wedge {I}_{\mathrm{F}}\left(\mathbf{A}\left(\mathbf{y}\right)\right)\to \left(\exists \mathbf{t}\in \mathbf{T}\right)\left(\mathbf{I}\left(\mathbf{x},\mathbf{t},\mathbf{1}\right)\wedge \mathbf{I}\left(\mathbf{y},\mathbf{t},\mathbf{1}\right)\right.\right.\\\hspace*{-5pt}\left.\left.\wedge \mathbf{O}\left(\mathbf{z},\mathbf{t},\mathbf{1}\right)\wedge {I}_{\mathrm{F}}\left(\mathbf{B}\left(\mathbf{z}\right)\right)\right)\right)\wedge \left(\neg {I}_{\mathrm{F}}\left(\mathbf{C}\left(\mathbf{x}\right)\right)\vee \neg {I}_{\mathrm{F}}\left(\mathbf{A}\left(\mathbf{y}\right)\right)\to \mathbf{z}=\mathbf{x}\right)\Big).\end{array}}$

This definition clearly satisfies the condition required for F-morphisms. Also we can see, as the following lemmas show, that the image of the above F-morphism preserves the structure of FA.

The following theorem shows a typical type of equivalence between PN and FA.

Theorem 5.3 [Equivalence of the Structures of Finite Automaton and Petri Net]

Let I = 〈I _O, I _F〉 be the F-morphism defined as in the above Definition. Then for any many-sorted sentence Φ of $\mathfrak{L}$(FA), FA ⊨ Φ if and only if PN ⊨ I _F(Φ).

This theorem implies that the structure of FA is embedded in PN constructed in Definition, and all the properties of FA are preserved there. We should notice that the dynamic behavior of PN by the transition of marking is implied by the relation O of PN, which can also represent the firing of the transitions.

4 Structure and Adaptation

4.1 Implications of Gödel’s Incompleteness Theorem for Structural Change

The definition of the structure of a system model implies that there are two ways to represent a change of the structure: the changes of the symbols $\mathfrak{L}$ and of the axioms Σ. Here we deal with the change of the axioms. Then we can naturally say that a system has changed its structure from Σ to Σ^′, if Σ^′ = Σ + {ψ}, where ψ nor ¬ψcannot be derived from Σ, i.e.,Σ ⊢ ψ nor Σ ⊢  ¬ ψ, under some deduction system.

This new property ψ cannot be recognized in the old structure Σ. Classical deduction systems such as first-order logic cannot deal with this situation effectively. Also in ordinal systems theory based on set theory without logical language and deduction system we hardly develop comprehensive consideration on this matter. We need to construct a meta-framework in which the structure of a system $\left(\mathfrak{L};\Sigma \right)$ can be referred an “object” and to extend the concept of system model by adding extra domain to it.

Gödel proved incompleteness theorem that there is a sentence that cannot be inferred from the logical system including the primitive recursive arithmetic (PRA) such as Peano’s axioms. From the Gödel’s incompleteness theorem, we see that there is a formula such that PRA ⊢ ϕ ↔  ¬  □ ϕ. The symbol □ expresses a modal operator and the formula □ϕ is interpreted to be “ϕ is provable” (Symoryński, 1985). Then ¬ □ ϕ means that ϕ is not provable. Furthermore ϕ ↔  ¬  □ ϕ means that “I am not provable.” This formula shows a self-referential sentence. Hence if the structure of a system includes PRA, the system has a property ϕ such that ϕ cannot be implied from the structure, and nor identified as behavior of the system.

As stated in the previous paragraph, if the structure of a system “moves” to a new structure that includes the old structure and the above self-referential sentence ϕ that is never proved from the old one, the system actually “change” its structure: the move from the structure Σ to Σ^′ = Σ + {ϕ} represents a structural change of the system.

4.2 Adaptation in Social System: Agent-Based Organizational Cybernetics

There are two kinds of adaptive behavior of a system: first-order adaptive behavior and second-order adaptive behavior. The first-order adaptive behavior seeks to make the system stable by regulating the gap between the goal of the system and the systems output observed. It is realized as a negative feedback mechanism, which can be formulated in the structure of the system, i.e., in LAST. The second-order adaptive behavior requires to change the field of systems behavior, which can be represented as the concept of positive feedback or second-order cybernetics. The second-order adaptive behavior cannot be described as any properties derived from the structure of the system. As seen in the above, the self-referential sentence plays a key role in the adaptation by the structural change. We need to introduce some new conceptual devices to describe models of the second-order adaptive behavior: agent, internal model, and organizational learning.

This section focuses on adaptation in social systems and provides the theoretical framework for describing it. Here a comprehensively hybrid model is introduced, which combines conventional organizational cybernetic framework and computational organization theoretic approach, especially agent-based computational learning model. The framework of organizational cybernetics includes no agent concept innately, but originally aims to contribute to the diagnosis of organizational failure based on Ashby’s law of variety (Espejo et al., 1996). On the other hand, computational organization theoretic approach contains agent-based task resolution processes in detail operational manner, but describes only a “flat” organization that has no hierarchical relationship between subsystems. The hybrid model presented here is comprehensive in understanding organizational learning in the sense that the learning process includes essentially the following steps: each agent resolves tasks in every functional layer in an organization; the results of the resolutions of tasks are unified to be organizational output performance; the organizational performance should be evaluated from environment; each agent change its internal model based on the evaluation results.

We call our newly developed approach Agent-based Organizational Cybernetics (AOC) (Takahashi, 2006). An organization considered in AOC is formulated to have four functional layers defined in organizational cybernetics: process, coordination, adaptation, and self-organization. The organizational cybernetic model has originally no concept of an agent. AOC introduces the concepts of agent and communication process among agents into each functional layer of an organizational cybernetic model. An agent is characterized by individual situatedness and internal model principle. The agent is defined as an autonomous decision-maker who constructs individually its internal model to describe its recognition of the situation surrounding it.

The basic features of AOC can be listed below.

• 1. Interaction between environment and decision-makers (from organizational cybernetic viewpoint).

• 2. An autonomous decision-maker makes a decision according to his decision principle.

• 3. An organization is structured in a multi-layer hierarchical form with some functional subsystems.

• 4. In each layer of the hierarchy, some agent groups are involved and interact one another.

• 5. Every agent has its own internal model that describes the situation surrounding the agent (called individual situatedness).

• 6. Every agent can learn its internal model and the organization can learn by sharing agents’ internal models. The process of learning represents single- and double-loop learnings in organizational learning.

AOC allows us to deal with organizational problems such as organizational learning in essentially operational manners. Results analyzed using AOC could suggest how we should effectively and operationally manage complex problems on the organization concerned. The principal target of AOC is to provide design criteria of prescription, especially which has not yet been validated in actual situations, on how an organization of concern should make a decision and take an action to adapt itself to a dynamically changing environment. AOC can also provide an effective way to evolve new design of functions working in an organization by re-combination of subsystems.

4.3 Components of Organizational Learning

The concept of organizational learning we use for our framework has similar aspects to the Argyris’ concept that individual learning processes are innately connected to organizational learning process. Our framework explicitly distinguishes individual levels of learning and organizational ones, and also does the levels of single-loop learning and double-loop one. We can see the explicit distinctions of the four types of learning loops.

The distinction by Argyris of single-loop learning and double-loop one is originated, as Argyris stated (Argyris & Schön, 1996), from similar notions in cybernetics developed by Ashby (1960). Based on organizational cybernetic approach, Espejo has provided a basis for the way how to apply the double-loop learning notion and process to actual organizations.

In AOC the concept of organizational learning, especially the learning-loop processes are realized in operational ways that each agent evaluates and revises its internal model. By actually implementing mechanisms of organizational learning in agents, the micro-macro problems can be explored effectively so as to tackle complex organizational systems.

The essential elements of organizational learning in AOC are the four learning loops: individual−/organizational- and single−/double-loop learning. AOC implements the learning processes as evaluating, revising, and sharing processes of internal models possessed by agents.

• 1. Individual single-loop learning.

  An agent builds its internal model to describe the environmental structure and the problem situation recognized, which includes some decision variables and decision criteria. The agent uses its internal model to optimize the decision variables. This learning does not enhance any ability to make organizational decisions.

• 2. Organizational single-loop learning.

  To achieve the given organizational goal, subgoals are specified to agents in inferior subsystems The values of the individual decision variables, which must be the results of the individual single-loop learning, are unified by the organization. The organization makes a decision based on the unified results.

• 3. Individual double-loop learning.

  Each agent evaluates its internal model, based on the results of the decision performed just before. Then the internal model is revised.

  This process of revising internal models by agents can be implemented effectively by using genetic algorithm (GA). The evaluation is defined by a fitness function that indicates what kind of information is available and how it should be utilized for the evaluation.

  After the evaluations of the internal models, applying GA operators such as selection, crossover, and mutation, the internal models are revised for the subsequent decisions.

• 4. Organizational double-loop learning.

  As the result of “good” individual double-loop learning, the agents share in the organization their good internal models that provide them with better decision capability and allow them to keep the organization viable.

5 Basis of Agent-Based Organizational Cybernetics

5.1 Hierarchical Organization Model in AOC

Combining the hierarchical model of organizational cybernetics and the agent model in computational organization theory, AOC consists of two basic models: hierarchical organization model and situated agent model.

A hierarchical organization model is a multi-layer system that has basically adaptive, coordination, and operational levels (Fig. 5.1).

Fig. 5.1

Basic hierarchical model in AOC

In AOC the function of each level is realized by a group of agents. Every agent belongs to one of the subsystems of the hierarchy. Each subsystem seeks a possibly different goal from other subsystems. Hence an agent is conducted based on the goal of the subsystem of which the agent is a member.

The adaptive level is composed of intelligence and institutional functions. In this level, based on environmental information observed by the intelligence function, the organization creates policy or strategy that could achieve a given organizational goal. If the organizational goal is recreated, the organization would go to a self-organization phase.

The coordination level has a function that determines coordination variables to control inferior subsystems in a decentralized manner. Coordination principles, which define how to coordinate the inferior subsystems, are essential to achieve a coordination goal.

In the operational level, agents determine decision variables autonomously, each of whom aims to optimize the process assigned to him. The processes interact with one another. The optimization process is given as a task resolution one, the result of which is reported to the superior subsystem, i.e., coordination level.

Computational Organization Theory has focused so far on models of the operational level. AOC formulates the operational level as a layer of the hierarchical subsystems of the overall organization model.

5.2 Situated Agent Model in AOC as Autonomous Decision-Maker

An agent concept in AOC as an autonomous decision-maker has basically the following features (Fig. 5.2).

• 1. An agent recognizes a process as a target of its decision-making, and builds its model internally, which is called an internal model.

  The internal model describes the behavior of the process and external inputs from environment, which can include agent’s recognition of the surrounding situation. An agent has its own internal model to describe the surrounding situation. Every agent is considered to be involved in its situation that is individually perceived by that agent. We call it individual situatedness.

• 2. An agent applies a decision principle to a problem concerning the process so that the agent evaluates options or alternatives to solve the problem.

Fig. 5.2

Situated agent model as decision-maker

The decision principle represents a criterion for preference ordering of the alternatives. It can be formally defined as a function from the class of problems to be solved into the ordering structures of preferences.

An eminent feature of AOC is to deal with, in an operational manner, micro-macro link problems such as a problem of the relationship between individual learning process of each agent and organizational one. An agent is typically a member of one of the autonomous decision groups defined in the multi-layers of an organization. The overall environment can be recognized as interpreted information from shared internal models of individually perceived situations.

5.3 Typical Internal Models

We here consider typical internal models in each hierarchical level.

A typical internal model that an agent in adaptive level has its recognition of the environmental structure, especially the recognition how the environment makes responses to an agent and the organization in the form of cost-profit function.

Another typical internal model in this level is the decision principle that an agent uses to make its decision. An internal model used in coordination level is the recognition of the process in which assigned tasks should be actually resolved.

In the operational level, a typical internal model can be how an agent recognizes tasks to be resolved as well as the task resolution process itself.

The point in considering learning problems in an organization is how each agent should evaluate its internal model, based on which the agent revises its internal model, i.e., the recognition of its individual situation and shares it among agents.

6 Conclusion: Beyond LAST

Logical Approach to Systems Theory (LAST) provides a way to investigate the similarity and structure of system models in type-free representation. Hence LAST clarifies the similarity of systems models in different representations as “isomorphic relation” with F-morphism. LAST explicitly gives the concept of the structure of a system model as a pair of the description language and the axioms characterizing the system model. Then LAST clarifies the distinction of what type of properties of systems can be described in the theory and what type of them cannot. Adaptation, which has been a central concern of systems theory, is a typical type of properties logical approaches hardly describe. One possibility of describing adaptation in logical frameworks would be to exploit modal logic, which could express the self-referential concept. Then the concepts of agent, internal model, and organizational learning would provide a breakthrough way to describe the adaptation of systems.

Agent-based organizational cybernetics involves as its significant part an adaptive mechanism in which agents revise intrinsically their own internal models and then share them with the other agents of the system through the organizational learning process the system constructs. The adaptive mechanism has been developed using many types of evolutionary computation algorithms such as genetic algorithm and so on. Tons of research results concerning them have been accumulated. Our future target would construct a way to formulate such adaptive processes as clearly as possible based on these outcomes, which would give a landscape beyond LAST.