# Ologs: a categorical framework for knowledge representation

David I. Spivak  Mathematics, MIT, Cambridge, MA 02139<EMAIL_ADDRESS>and  Robert E. Kent  Ontologos<EMAIL_ADDRESS>
###### Abstract.

In this paper we introduce the olog, or ontology log, a category-theoretic
model for knowledge representation (KR). Grounded in formal mathematics, ologs
can be rigorously formulated and cross-compared in ways that other KR models
(such as semantic networks) cannot. An olog is similar to a relational
database schema; in fact an olog can serve as a data repository if desired.
Unlike database schemas, which are generally difficult to create or modify,
ologs are designed to be user-friendly enough that authoring or reconfiguring
an olog is a matter of course rather than a difficult chore. It is hoped that
learning to author ologs is much simpler than learning a database definition
language, despite their similarity. We describe ologs carefully and illustrate
with many examples. As an application we show that any primitive recursive
function can be described by an olog. We also show that ologs can be aligned
or connected together into a larger network using functors. The various
methods of information flow and institutions can then be used to integrate
local and global world-views. We finish by providing several different avenues
for future research.

This project was supported by Office of Naval Research grant: N000141010841
and a generous contribution by Clark Barwick, Jacob Lurie, and the
Massachusetts Institute of Technology Department of Mathematics

###### Contents

  1. 1 Introduction
  2. 2 Types, aspects, and facts
  3. 3 Instances
  4. 4 Communication between ologs
  5. 5 More expressive ologs I
  6. 6 More expressive ologs II
  7. 7 Further directions

##  1\. Introduction

Scientists have a pressing need to organize their experiments, their data,
their results, and their conclusions into a framework such that this work is
reusable, transferable, and comparable with the work of other scientists. In
this paper, we will discuss the “ontology log” or olog as a possibility for
such a framework. Ontology is the study of what something is, i.e the nature
of a given subject, and ologs are designed to record the results of such a
study. The structure of ologs is based on a branch of mathematics called
category theory. An olog is roughly a category that models a given real-world
situation.

The main advantages of authoring an olog rather than writing a prose
description of a subject are that

  * •

an olog gives a precise formulation of a conceptual world-view,

  * •

an olog can be formulaically converted into a database schema,

  * •

an olog can be extended as new information is obtained,

  * •

an olog written by one author can be easily and precisely referenced by
others,

  * •

an olog can be input into a computer and “meaningfully stored”, and

  * •

different ologs can be compared by functors, which in turn generate automatic
terminology translation systems.

The main disadvantage to using ologs over prose, aside from taking more space
on the page, is that writing a good olog demands a clarity of thought that
ordinary writing or conversation can more easily elide. However, the
contemplation required to write a good olog about a subject may have
unexpected benefits as well.

A category is a mathematical structure that appears much like a directed
graph: it consists of objects (often drawn as nodes or dots, but here drawn as
boxes) and arrows between them. The feature of categories that distinguishes
them from graphs is the ability to declare an equivalence relation on the set
of paths. A functor is a mapping from one category to another that preserves
the structure (i.e. the nodes, the arrows, and the equivalences). If one views
a category as a kind of language (as we shall in this paper) then a functor
would act as a kind of translating dictionary between languages. There are
many good references on category theory, including [LS], [Sic], [Pie], [BW1],
[Awo], and [Mac]; the first and second are suited for general audiences, the
third and fourth are suited for computer scientists, and the fifth and sixth
are suited for mathematicians (in each class the first reference is easier
than the second).

A basic olog, defined in Section 2, is a category in which the objects and
arrows have been labeled by English-language phrases that indicate their
intended meaning. The objects represent types of things, the arrows represent
functional relationships (also known as aspects, attributes, or observables),
and the commutative diagrams represent facts. Here is a simple olog about an
amino acid called arginine ([W]):

(7) $\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{\parbox{72.26999pt}{\raggedright an amino acid found in
dairy\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
A}}{{\framebox{\parbox{36.135pt}{arginine}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$hasisis$\textstyle{\stackrel{{\scriptstyle
E}}{{\framebox{\parbox{65.04256pt}{\raggedright an electrically-charged side
chain\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
X}}{{\framebox{\parbox{65.04256pt}{an amino
acid}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$hashashas$\textstyle{\stackrel{{\scriptstyle
R}}{{\framebox{a side chain}}}}$$\textstyle{\stackrel{{\scriptstyle
N}}{{\framebox{\parbox{72.26999pt}{an amine
group}}}}}$$\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{\parbox{72.26999pt}{a carboxylic acid}}}}}$

The idea of representing information in a graph is not new. For example the
Resource Descriptive Framework (RDF) is a system for doing just that [CM]. The
key difference between a category and a graph is the consideration of paths,
and that two paths from $A$ to $B$ may be declared identical in a category
(see [Spi3]). For example, we can further declare that in Diagram (7), the
diagram

(12)

commutes, i.e. that the two paths
$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{R}$
are equivalent, which can be translated as follows. Let $A$ be a molecule of
arginine. On the one hand $A$, being an amino acid, has a side chain; on the
other hand $A$ has an electrically-charged side-chain, which is of course a
side chain. We seem to have associated two side-chains to $A$, but in fact
they both refer to the same physical thing, the same side-chain. Thus, the two
paths $A\rightarrow R$ are deemed equivalent. The fact that this equivalence
may seem trivial is not an indictment of the category idea but instead
reinforces its importance — we must be able to indicate obvious facts within a
given situation because what is obvious is the most essential.

While many situations can be modeled using basic ologs (categories), we often
need to encode more structure. For this we will need so-called sketches. An
olog will be defined as a finite limit, finite colimit sketch (see [BW2]),
meaning we have the ability to encode objects (“types”), arrows (“aspects”),
commutative diagrams (“facts”), as well as finite limits (“layouts”) and
finite colimits (“groupings”).

Throughout this paper, whenever we refer to “the author” of an olog we am
referring to the fictitious person who created it. We will refer to ourselves,
David Spivak and Robert Kent, as “we” so as not to confuse things.

######  Warning 1.0.1.

The author of an olog has a world-view, some fragment of which is captured in
the olog. When person A examines the olog of person B, person A may or may not
“agree with it.” For example, person B may have the following olog

a marriage includesincludes a mana woman

which associates to each marriage a man and a woman. Person A may take the
position that some marriages involve two men or two women, and thus see B’s
olog as “wrong.” Such disputes are not “problems” with either A’s olog or B’s
olog, they are discrepancies between world-views. Hence, throughout this
paper, a reader R may see a displayed olog and notice a discrepancy between
R’s world-view and our own, but R should not worry that this is a problem.
This is not to say that ologs need not follow rules, but instead that the
rules are enforced to ensure that an olog is structurally sound, rather than
that it “correctly reflects reality,” whatever that may mean.

###  1.1. Plan of this paper

In this paper, we will define ologs and give several examples. We will state
some rules of “good practice” which help one to author ologs that are
meaningful to others and easily extendable. We will begin in Section 2 by
laying out the basics: types as objects, aspects as arrows, and facts as
commutative diagrams. In Section 3, we will explain how to attach “instance”
data to an olog and hence realize ologs as database schemas. In Section 4, we
will discuss meaningful constraints betweeen ologs that allow us to develop a
higher-dimensional web of information called an information system, and we
will discuss how the various parts of such a system interact via information
channels. In Sections 5 and 6, we will extend the olog definition language to
include “layouts” and “groupings”, which make for more expressive ologs; we
will also describe two applications, one which explicates the computation of
the factorial function, and the other which defines a notion from pure
mathematics (that of pseudo-metric spaces). Finally, in Section 7, we will
discuss some possible directions for future research.

For the remainder of the present section, we will explain how ologs relate to
existing ideas in the field of knowledge representation.

###  1.2. The semantic advantage of ologs: modularity

The difference between ologs and prose is modularity: small conceptual pieces
can form large ideas, and these pieces work best when they are reusable. The
same phenomenon is true throughout computer science and mathematics. In
programming languages, modularity brings not only vast efficiency to the
writing of programs but enables an “abstraction barrier” that keeps the ideas
clean. In mathematics, the most powerful results are often simple lemmas that
are reusable in a wide variety of circumstances.

Web pages that consist of prose writing are often referred to as information
silos. The idea is that a silo is a “big tube of stuff” which is not organized
in any real way. Links between web pages provide some structure, but such a
link does not carry with it a precise method to correlate the information
within the two pages. Similarly in science, one author may reference another
paper, but such a reference carries very little structure — it just points to
a silo.

Ologs can be connected with links which are much richer than the link between
two silos could possibly be. Individual concepts and connections within one
olog can be “functorially aligned” with concepts and connections in another. A
functor creates a precise connection between the work of one author and the
work of another so that the precise nature of the comparison is not left to
the reader’s imagination but explicitly specified. The ability to incorporate
mathematical precision into the sharing of ideas is a central feature of
ologs.

###  1.3. Relation to other models

There are many languages for knowledge representation (KR). For example, there
are database languages such as SQL, ontology languages such as RDF and OWL,
the language of Semantic Nets, and others (see [Bor]). One may ask what makes
the olog concept different or better than the others.

The first response is that ologs are closely related to the above ideas.
Indeed, all of these KR models can be “categorified” (i.e. phrased in the
language of category theory) and related by functors, so that many of the
ideas align and can be transferred between the different systems. In fact, as
we will make clear in Section 3, ologs are almost identical to the categorical
model of databases presented in [Spi2].

However, ologs have advantages over many existing KR models. The first
advantage arises from the notion of commutative diagrams (which allow us to
equate different paths through the domain, see Section 2.3) and of limits and
colimits (which allow us to lay out and group things, see Sections 5 and 6).
The additional expressivity of ologs give them a certain semantic clarity and
interoperability that cannot be achieved with graphs and networks in the usual
sense. The second advantage arises from the notion of olog morphisms, which
allow the definition of meaningful constraints between ologs. With this in
hand, we can integrate a set of similar ologs into a single information
system, and go on to define information fusion. This will be discussed further
Section 4.

In the remainder of this section we will provide a few more details on the
relationship between ologs and each of the above KR models: databases,
RDF/OWL, and semantic nets. The reader who does not know or care much about
other systems of knowledge representation can skip to Section 1.4.

####  1.3.1. Ologs and Databases

A database is a system of tables, each table of which consists of a header of
columns and a set of rows. A table represents a type of thing $T$, each column
represents an attribute of $T$, and each row represents an example of $T$. An
attribute is itself a “type of thing”, so each column of a table points to
another table.

The relationship between ologs and databases is that every box $B$ in an olog
represents a type of thing and every arrow $B\rightarrow X$ emanating from $B$
represents an attribute of $B$ (whose results are of type $X$). Thus the boxes
and arrows in an olog correspond to tables and their columns in a database.
The rows of each table in a database will correspond to “instances” of each
type in an olog. Again, this will be made more clear in Section 3 or one can
see [Spi2] or [Ken5].

The point is that every olog can serve as a database schema, and the schemas
represented by ologs range from simple (just objects and arrows) to complex
(including commutative diagrams, products, sums, etc.). However, whereas
database schemas are often prescriptive (“you must put your data into this
format!”), ologs are usually descriptive (“this is how I see things”). One can
think of an olog as an interface between people and databases: an olog is
human readable, but it is also easily converted to a database schema upon
which powerful applications can be put to work. Of course, if one is to use an
olog as a database schema, it will become prescriptive. However, since the
intention of each object and arrow is well-documented (as its label), schema
evolution would be straightforward. Moreover, the categorical structure of
ologs allows for functorial data migration by which one can transfer the
instance data from an older schema to the current one (see [Spi2]).

####  1.3.2. Ologs and RDF / OWL

In [Spi2], the first author explained how a categorical database can be
converted into an RDF triple store using the Grothendieck construction. The
main difference between a categorical database schema (or an olog) and an RDF
schema is that one cannot specify commutativity in an RDF schema. Thus one
cannot express things like “the woman parent of a person $x$ is the mother of
$x$.” Without this expressivity, it is hard to enforce much rigor, and thus
RDF data tends to be too loose for many applications.

OWL schemas, on the other hand, can express many more constraints on classes
and properties. We have not yet explored the connection, nor compared the
expressive power, of ologs and OWL. However, they are significantly different
systems, most obviously in that OWL relies on logic where ologs rely on
category theory.

####  1.3.3. Semantic Nets

On the surface, ologs look the most like semantic networks, or concept webs,
but there are important differences between the two notions. First, arrows in
a semantic network need not indicate functions; they can be relations. So
there could be an arrow $\ulcorner$a
father$\urcorner$$\xrightarrow{\textnormal{has}}$$\ulcorner$a child$\urcorner$
in a semantic network, but not in an olog (see Section 2.2.3 for how the same
idea is expressible in an olog). There is a nice category of sets and
relations, often denoted Rel, but this category is harder to reason about than
is the ordinary category of sets and functions (often denoted ${\bf Set}$).
Thus, as mentioned above, semantic networks are categorifiable (using Rel),
but this underlying formalism does not appear to play a part in the study or
use of semantic networks. However, some attempt to integrate category theory
and neural nets has been made, see [HC].

Moreover, commutative diagrams and other expressive abilities held by ologs
are not generally part of the semantic network concept (see [Sow1]). For these
reasons, semantic networks tend to be brittle: minor changes can have
devastating effects. For example, if two semantic networks are somehow synced
up and then one is changed, the linkage must be revised or may be altogether
broken. Such a disaster is often avoided if one uses categories: because
different paths can be equivalent, one can simply add new ideas (types and
aspects) without changing the semantic meaning of what was already there. As
section 4.4 demonstates with an extended example, conceptual graphs, which are
a popular formalism for semantics nets, can be linearized to ologs, thereby
gaining in precision and expressibility.

###  1.4. Acknowledgements

####  1.4.1. David Spivak’s acknowledgments

I would like to thank Mathieu Anel and Henrik Forssell for many pleasant and
quite useful conversations. I would also like to thank Micha Breakstone for
his help on understanding the relationship between ologs and linguistics.
Finally I would like to thank Dave Balaban for helpful suggestions on this
document itself.

####  1.4.2. Robert Kent’s acknowledgments

I would like to thank the participants in the Standard Upper Ontology working
group for many interesting, spirited, rewarding and enlightening discussions
about knowledge representation in general and ontologies in particular; I
especially want to thank Leo Obrst, Marco Schorlemmer and John Sowa from that
group. I want to thank Jon Barwise for leading the development of the theory
of information flow. I want to thank Joseph Goguen for leading the development
of the theory of institutions, and for pointing out the common approach to
knowledge representation used by both the Information Flow Framework and the
theory of institutions.

##  2\. Types, aspects, and facts

In this section we will explain basic ologs, which involve types, aspects, and
facts. A basic olog is a category in which each object and arrow has been
labeled by text; throughout this paper we will assume that text to be written
in English.

The purpose of this section is to show how one can convert a real-world
situation into an olog. It is probably impossible to explain this process
precisely in words. Instead, we will explain mainly by example. We will give
“rules of good practice” that lead to good ologs. While these rules are not
strictly necessary, they help to ensure that the olog is properly formulated.
As the Dalai Lama says, “Learn the rules so you know how to break them
properly.”

###  2.1. Types

A type is an abstract concept, a distinction the author has made. We represent
each type as a box containing a singular indefinite noun phrase. Each of the
following four boxes is a type:

(17)

Each of the four boxes in (17) represents a type of thing, a whole class of
things, and the label on that box is what one should call each example of that
class. Thus $\ulcorner$a man$\urcorner$ does not represent a single man, but
the set of men, each example of which is called “a man”111In other words,
types in ologs are intentional, rather than extensional — the label on a type
describes its intention. The extension of a type will be captured by instance
data; see Section 3 .. Similarly, the bottom right-hand box in (17) represents
an abstract type of thing, which probably has more than a million examples,
but the label on the box indicates a common name for each such example.

Typographical problems emerge when writing a text-box in a line of text, e.g.
the text-box a man seems out of place here, and the more in-line text-boxes
one has in a given paragraph, the worse it gets. To remedy this, we will
denote types which occur in a line of text with corner-symbols, e.g. we will
write $\ulcorner$a man$\urcorner$ instead of a man.

####  2.1.1. Types with compound structures

Many types have compound structures; i.e. they are composed of smaller units.
Examples include

(20)

It is good practice to declare the variables in a “compound type”, as we did
in the last two cases of (20). In other words, it is preferable to replace the
first box above with something like

$\stackrel{{\scriptstyle}}{{\framebox{\parbox{57.81621pt}{a man $m$ and a
woman $w$}}}}\hskip 14.45377pt\textnormal{or}\hskip
14.45377pt\stackrel{{\scriptstyle}}{{\framebox{\parbox{79.49744pt}{\raggedright
a pair $(m,w)$ where $m$ is a man and $w$ is a woman\@add@raggedright}}}}$

so that the variables $(m,w)$ are clear.

######  Rules of good practice 2.1.1.

A type is presented as a text box. The text in that box should

  1. (i)

begin with the word “a” or “an”;

  2. (ii)

refer to a distinction made and recognizable by the author;

  3. (iii)

refer to a distinction for which instances can be documented;

  4. (iv)

not end in a punctuation mark;

  5. (v)

declare all variables in a compound structure.

The first, second, and third rules ensure that the class of things represented
by each box appears to the author as a well-defined set; see Section 3 for
more details. The fourth and fifth rules encourage good “readability” of
arrows, as will be discussed next in Section 2.2.

We will not always follow the rules of good practice throughout this document.
We think of these rules being followed “in the background” but that we have
“nicknamed” various boxes. So $\ulcorner$Steve$\urcorner$ may stand as a
nickname for $\ulcorner$a thing classified as Steve$\urcorner$ and
$\ulcorner$arginine$\urcorner$ as a nickname for $\ulcorner$a molecule of
arginine$\urcorner$.

###  2.2. Aspects

An aspect of a thing $x$ is a way of viewing it, a particular way in which $x$
can be regarded or measured. For example, a woman can be regarded as a person;
hence “being a person” is an aspect of a woman. A man has a height (say, taken
in inches), so “having a height (in inches)” is an aspect of a man. In an
olog, an aspect of $A$ is represented by an arrow $A\rightarrow B$, where $B$
is the set of possible “answers” or results of the measurement. For example
when observing the height of a man, the set of possible results is the set of
integers, or perhaps the set of integers between 20 and 120.

(23) (26)

We will formalize the notion of aspect by saying that aspects are functional
relationships.222In type theory, what we here call aspects are called
functions. Since our types are not fixed sets (see Section 3), we preferred a
term that was less formal. Suppose we wish to say that a thing classified as
$X$ has an aspect $f$ whose result set is $Y$. This means there is a
functional relationship called $f$ between $X$ and $Y$, which can be denoted
$f\colon X\rightarrow Y$. We call $X$ the domain of definition for the aspect
$f$, and we call $Y$ the set of result values for $f$. For example, a man has
a height in inches whose result is an integer, and we could denote this by
$h\colon M\rightarrow{\bf Int}$. Here, $M$ is the domain of definition for
height and ${\bf Int}$ is the set of result values.

A set may always be drawn as a blob with dots in it. If $X$ and $Y$ are two
sets, then a a function from $X$ to $Y$, denoted $f\colon X\rightarrow Y$ can
be presented by drawing arrows from dots in blob $X$ to dots in blob $Y$.
There are two rules:

  1. (i)

each arrow must emanate from a dot in $X$ and point to a dot in $Y$;

  2. (ii)

each dot in $X$ must have precisely one arrow emanating from it.

Given an element $x\in X$, the arrow emanating from it points to some element
$y\in Y$, which we call the image of $x$ under $f$ and denote $f(x)=y$.

Again, in an olog, an aspect of a thing $X$ is drawn as a labeled arrow
pointing from $X$ to a “set of result values.” Let us concentrate briefly on
the arrow in (23). The domain of definition is the set of women (a set with
perhaps 3 billion elements); the set of result values is the set of persons (a
set with perhaps 6 billion elements). We can imagine drawing an arrow from
each dot in the “woman” set to a unique dot in the “person” set. No woman
points to two different people, nor to zero people — each woman is exactly one
person — so the rules for a functional relationship are satisfied. Let us now
concentrate briefly on the arrow in (26). The domain of definition is the set
of men, the set of result values is the set of integers
$\\{20,21,22,\ldots,119,120\\}$. We can imagine drawing an arrow from each dot
in the “man” set to a single dot in the “integer” set. No man points to two
different heights, nor can a man have no height: each man has exactly one
height. Note however that two different men can point to the same height.

####  2.2.1. Invalid aspects

We tried above to clarify what it is that makes an aspect “valid”, namely that
it must be a “functional relationship.” In this subsection we will present two
arrows which on their face may appear to be aspects, but which on closer
inspection are not functional (and hence are not valid as aspects).

Consider the following two arrows:

(29) (32)

A person may have no children or may have more than one child, so the first
arrow is invalid: it is not functional because it does not satisfy rule (2)
above. Similarly, if we drew an arrow from each mechanical pencil to each
piece of lead it uses, it would not satisfy rule (2) above. Thus neither of
these is a valid aspect.

Of course, in keeping with Warning 1.0.1, the above arrows may not be wrong
but simply reflect that the author has a strange world-view or a strange
vocabulary. Maybe the author believes that every mechanical pencil uses
exactly one piece of lead. If this is so, then $\textnormal{$\ulcorner$a
mechanical
pencil$\urcorner$}\xrightarrow{\textnormal{uses}}\textnormal{$\ulcorner$a
piece of lead$\urcorner$}$ is indeed a valid aspect! Similarly, suppose the
author meant to say that each person was once a child, or that a person has an
inner child. Since every person has one and only one inner child (according to
the author), the map $\textnormal{$\ulcorner$a
person$\urcorner$}\xrightarrow{\textnormal{has as inner
child}}\textnormal{$\ulcorner$a child$\urcorner$}$ is a valid aspect. We
cannot fault the author for such a view, but note that we have changed the
name of the label to make its intention more explicit.

####  2.2.2. Reading aspects and paths as English phrases

Each arrow (aspect) $X\xrightarrow{f}Y$ can be read by first reading the label
on its source box (domain of definition) $X$, then the label on the arrow $f$,
and finally the label on its target box (set of result values) $Y$. For
example, the arrow

(11) $\textstyle{\stackrel{{\scriptstyle}}{{\framebox{a
book}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has as first
author$\textstyle{\stackrel{{\scriptstyle}}{{\framebox{a person}}}}$

is read “a book has as first author a person”, a valid English sentence.

Sometimes the label on an arrow can be shortened or dropped altogether if it
is obvious from context. We will discuss this more in Section 2.3 but here is
a common example from the way we write ologs.

(16) $\textstyle{\stackrel{{\scriptstyle
A}}{{\framebox{\parbox{86.72377pt}{\raggedright a pair $(x,y)$ where $x$ and
$y$ are
integers\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{x}$$\scriptstyle{y}$$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{an integer}}}}$$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{an integer}}}}$

Neither arrow is readable by the protocol given above (e.g. “a pair $(x,y)$
where $x$ and $y$ are integers $x$ an integer” is not an English sentence),
and yet it is obvious what each map means. For example, given the pair
$(8,11)$ which belongs in box $A$, application of arrow $x$ would yield $8$ in
box $B$. The label $x$ can be thought of as a nickname for the full name
“yields, via the value of $x$,” and similarly for $y$. We do not generally use
the full name for fear that the olog would become cluttered with text.

One can also read paths through an olog by inserting the word “which” after
each intermediate box. For example the following olog has two paths of length
3 (counting arrows in a chain):

(21)
---
a childisa personhas as parentshas, as
birthday$\textstyle{\stackrel{{\scriptstyle}}{{\framebox{\parbox{57.81621pt}{\raggedright
a pair $(w,m)$ where $w$ is a woman and $m$ is a
man\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$w$a
womana dateincludesa year

The top path is read “a child is a person, which has as parents a pair $(w,m)$
where $w$ is a woman and $m$ is a man, which yields, via the value of $w$, a
woman.” The reader should read and understand the content of the bottom path.

####  2.2.3. Converting non-functional relationships to aspects

There are many relationships that are not functional, and these cannot be
considered aspects. Often the word “has” indicates a relationship — sometimes
it is functional as in $\textnormal{$\ulcorner$a
person$\urcorner$}\xrightarrow{\textnormal{ has }}\textnormal{$\ulcorner$a
stomach$\urcorner$}$, and sometimes it is not, as in $\textnormal{$\ulcorner$a
father$\urcorner$}\xrightarrow{\textnormal{has}}\textnormal{$\ulcorner$a
child$\urcorner$}$. (Obviously, a father may have more than one child.) A
quick fix would be to replace the latter by $\textnormal{$\ulcorner$a
father$\urcorner$}\xrightarrow{\textnormal{has}}\textnormal{$\ulcorner$a set
of children$\urcorner$}$. This is ok, but the relationship between
$\ulcorner$a child$\urcorner$ and $\ulcorner$a set of children$\urcorner$ then
becomes an issue to deal with later. There is another way to indicate such
“non-functional” relationships.

In mathematics, a relation between sets $A_{1},A_{2}$, and so on through
$A_{n}$ is defined to be a subset of the Cartesian product

$R\subseteq A_{1}\times A_{2}\times\cdots\times A_{n}.$

The set $R$ represents those sequences $(a_{1},a_{2},\ldots,a_{n})$ that are
so-related. In an olog, we represent this as follows

|
---|---
$\textstyle{\framebox{$R$}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\framebox{$A_{1}$}}$$\textstyle{\framebox{$A_{2}$}}$$\textstyle{\cdots}$$\textstyle{\framebox{$A_{n}$}}$

For example,

---
$\textstyle{\stackrel{{\scriptstyle R}}{{\framebox{\parbox{115.63243pt}{a
sequence $(p,a,j)$ where $p$ is a paper, $a$ is an author of $p$, and $j$ is a
journal in which $p$ was
published}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p}$$\scriptstyle{a}$$\scriptstyle{j}$$\textstyle{\stackrel{{\scriptstyle
A_{1}}}{{\framebox{a paper}}}}$$\textstyle{\stackrel{{\scriptstyle
A_{2}}}{{\framebox{an author}}}}$$\textstyle{\stackrel{{\scriptstyle
A_{3}}}{{\framebox{a journal}}}}$

Whereas $A_{1}\times A_{2}\times A_{3}$ includes all possible triples
$(p,a,j)$ where $a$ is a person, $p$ is a paper, and $j$ is a journal, it is
obvious that not all such triples are found in $R$. Thus $R$ represents a
proper subset of $A_{1}\times A_{2}\times A_{3}$.

######  Rules of good practice 2.2.1.

An aspect is presented as a labeled arrow, pointing from a source box to a
target box. The arrow text should

  1. (i)

begin with a verb;

  2. (ii)

yield an English sentence, when the source-box text followed by the arrow text
followed by the target-box text is read;

  3. (iii)

refer to a functional dependence: each instance of the source type should give
rise to a specific instance of the target type;

###  2.3. Facts

In this section we will discuss facts and their relationship to “path
equivalences.” It is such path equivalences, which exist in categories but do
not exist in graphs, that make category theory so powerful. See [Spi3] for
details.

Given an olog, the author may want to declare that two paths are equivalent.
For example consider the two paths from $A$ to $C$ in the olog

(26) $\textstyle{\stackrel{{\scriptstyle A}}{{\framebox{a
person}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has
as parents has as mother $\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{\parbox{57.81621pt}{\raggedright a pair $(w,m)$ where $w$ is a
woman and $m$ is a
man\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\checkmark}$$w$$\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{a woman}}}}$

We know as English speakers that a woman parent is called a mother, so these
two paths $A\rightarrow C$ should be equivalent. A more mathematical way to
say this is that the triangle in Olog (26) commutes.

A commutative diagram is a graph with some declared path equivalences. In the
example above we concisely say “a woman parent is equivalent to a mother.” We
declare this by defining the diagonal map in (26) to be the composition of the
horizontal map and the vertical map.

We generally prefer to indicate a commutative diagram by drawing a check-mark,
$\checkmark$, in the region bounded by the two paths, as in Olog (26).
Sometimes, however, one cannot do this unambiguously on the 2-dimensional
page. In such a case we will indicate the commutative diagrams (fact) by
writing an equation. For example to say that the diagram

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{h}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{C\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\textstyle{D}$

commutes, we could either draw a checkmark inside the square or write the
equation $f;g=h;i$ above it. Either way, it means that “$f$ then $g$” is
equivalent to “$h$ then $i$”.

####  2.3.1. More complex facts

Recording real-world facts in an olog can require some creativity. Whereas a
fact like “the brother of ones father is ones uncle” is recorded as a simple
commutative diagram, others are not so simple. We will try to show the range
of expressivity of commutative diagrams in the following two examples.

######  Example 2.3.2.

How would one record a fact like “a truck weighs more than a car”? We suggest
something like this:

---
$\textstyle{\stackrel{{\scriptstyle B_{1}}}{{\framebox{a
truck}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\scriptstyle{\checkmark}$$\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{\parbox{43.36243pt}{a physical
object}}}}}$$\textstyle{\stackrel{{\scriptstyle A}}{{\framebox{a truck $t$ and
a car
$c$}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{t}$$\scriptstyle{c}$$\scriptstyle{t\mapsto
x,\;\;c\mapsto y}$$\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{\parbox{79.49744pt}{a pair $(x,y)$ where $x$ and $y$ are
physical objects and $x$ weighs more than
$y$}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{x}$$\scriptstyle{y}$$\textstyle{\stackrel{{\scriptstyle
B_{2}}}{{\framebox{a
car}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\scriptstyle{\checkmark}$$\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{\parbox{43.36243pt}{a physical object}}}}}$

where both top and bottom commute. This olog exemplifies the fact that simple
sentences sometimes contain large amounts of information. While the long map
may seem to suffice to convey the idea “a truck weighs more than a car,” the
path equivalences (declared by check-marks) serve to ground the idea in more
basic types. These other types tend to be useful for other purposes, both
within the olog and when connecting it to others.

####  2.3.3. Specific facts at the olog level

Another fact one might wish to record is that “John Doe’s weight is 150 lbs.”
This is established by declaring that the following diagram commutes:

(33) |  |  |
---|---|---|---
John Doe$\scriptstyle{\checkmark}$has as weight (in pounds)is150isa personhas
as weight (in pounds)a real number

If one only had the top line, it would be less obvious how to connect its
information with that of other ologs. (See Section 4 for more on connecting
different ologs).

Note that the top line in Diagram (33) might also be considered as existing at
the “data level” rather than at the “olog level.” In other words, one could
see John Doe as an “instance” of $\ulcorner$a person$\urcorner$, rather than
as a type in and of itself, and similarly see 150 as an instance of
$\ulcorner$a real number$\urcorner$. This idea of an olog having a “data
level” is the subject of the Section 3.

######  Rules of good practice 2.3.4.

A fact is the declaration that two paths (having the same source and target)
in an olog are equivalent. Such a fact is either presented as a checkmark
between the two paths (if such a check-mark is unambiguous) or by an equation.
Every such equivalence should be declared; i.e. no fact should be considered
too obvious to declare.

##  3\. Instances

The reader at this point hopefully sees an olog as a kind of “concept map,”
and it is one, albeit a concept map with a formal structure (implicitly coming
from category theory) and specific rules of good practice. In this section we
will show that one can also load an olog with data. Each type can be assigned
a set of instances, each aspect will map the instances of one type to
instances of the other, and each fact will equate two such mappings. We give
examples of these ideas in Section 3.1.

In Section 3.2, we will show that in fact every olog can also serve as the
layout for a database. In other words, given an olog one can immediately
generate a database schema, i.e. a system of tables, in any reasonable data
definition language such as that of SQL. The tables in this database will be
in one-to-one correspondence with the types in the olog. The columns of a
given table will be the aspects of the corresponding type, i.e. the arrows
whose source is that type. Commutative diagrams in the olog will give
constraints on the data.

In fact, this idea is the basic thesis in [Spi2], even though the word olog
does not appear in that paper. There it was explained that a category
${\mathcal{C}}$ naturally can be viewed as a database schema and that a
functor $I\colon{\mathcal{C}}\rightarrow{\bf Set}$, where ${\bf Set}$ is the
category of sets, is a database state. Since an olog is a drawing of a
category, it is also a drawing of a database schema. The current section is
about the “states” of an olog, i.e. the kinds of data that can be captured by
it.

###  3.1. Instances of types, aspects, and facts

Recall from Section 2 that basic ologs consist of types, displayed as boxes;
aspects, displayed as arrows; and facts, displayed as equations or check-
marks. In this section we discuss the instances of these three basic
constructions. The rules of good practice (2.1.1, 2.2.1, and 2.3.4) were
specifically designed to simplify the process of finding instances.

####  3.1.1. Instances of types

According to Rules 2.1.1, each box in an olog contains text which should refer
to a distinction made and recognizable by the author for which instances can
be documented. For example if my olog contains a box

(34) $\displaystyle\stackrel{{\scriptstyle}}{{\framebox{\parbox{93.95122pt}{a
pair $(p,c)$ where $p$ is a person, $c$ is a cat, and $p$ has petted $c$}}}}$

then I must have some concept of when this situation occurs. Every time I
witness a new person-cat petting, I document it. Whether this is done in my
mind, in a ledger notebook, or on a computer does not matter; however using a
computer would probably be the most self-explanatory. Imagine a computer
program in which one can create ologs. Clicking a text box in an olog results
in it “opening up” to show a list of documented instances of that type. If one
is reading the CBS news olog and clicks on the box $\ulcorner$an episode of 60
Minutes$\urcorner$, he or she should see a list of all episodes of the TV show
“60 Minutes.” If we wish to document a new person-cat petting incident we
click on the box in (34) and add this new instance.

####  3.1.2. Instances of aspects

According to Rules 2.2.1, each arrow in an olog should be labeled with text
that refers to a functional relationship between the source box and the target
box. A functional relationship $f\colon A\rightarrow B$ between finite sets
$A$ and $B$ can always be written as a 2-column table: the first column is
filled with the instances of type $A$ and the second column is filled with
their $f$-values, which are instances of type $B$.

For example, consider the aspect

(35) $\displaystyle\framebox{a
moon}\xrightarrow{\textnormal{orbits}}\framebox{a planet}$

We can document some instances of this relationship using the following table:

(43)

Clearly, this table of instances can be updated as more moons are discovered
by the author (be it by telescope, conversation, or research).

The correspondence between aspect (35) and Table (43) makes it clear that
ologs can serve to hold data which exemplifies the author’s world-view. In
Section 3.2, we will show that ologs (which have many aspects and facts) can
serve as bona fide database schemas.

####  3.1.3. Instances of facts

Recall the following olog:

$\textstyle{\stackrel{{\scriptstyle A}}{{\framebox{a
person}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has
as parentshas as mother$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{\parbox{57.81621pt}{\raggedright a pair $(w,m)$ where $w$ is a
woman and $m$ is a
man\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
✓ $w$$\textstyle{\stackrel{{\scriptstyle C}}{{\framebox{a woman}}}}$

and consider the following instances of the three aspects in it:

has as parents
---
a person | a pair $(w,m)$ …
Cain | (Eve, Adam)
Abel | (Eve, Adam)
Chelsey | (Hillary, Bill)
$w$
---
a pair $(w,m)$ … | a woman
(Eve, Adam) | Eve
(Hillary, Bill) | Hillary
(Margaret, Samuel) | Margaret
(Emily, Kris) | Emily
has as mother
---
a person | a woman
Cain | Eve
Abel | Eve
Chelsey | Hillary

When we declare that the diagram in (26) commutes (using the check-mark), we
are saying that for every instance of $\ulcorner$a person$\urcorner$ (of which
we have three: Cain, Abel, and Chelsey), the two paths to $\ulcorner$a
woman$\urcorner$ give the same answers. Indeed, for Cain the two paths are:

  1. (i)

Cain $\mapsto$ (Eve, Adam) $\mapsto$ Eve;

  2. (ii)

Cain $\mapsto$ Eve;

and these answers agree. If one changed any instance of the word “Eve” to the
word “Steve” in one of the tables in (LABEL:dia:instances_of_facts), some pair
of paths would fail to agree. Thus the “fact” that the diagram in (26)
commutes ensures that there is some internal consistency between the meaning
of parents and the meaning of mother, and this consistency must be born out at
the instance level.

All of this will be formalized in Section 3.2.2.

###  3.2. The relationship between ologs and databases

Recall from Section 3.1.1 that we can imagine creating an olog on a computer.
The user creates boxes, arrows, and compositions, hence creating a category
${\mathcal{C}}$. Each text-box $x$ in the olog can be “clicked” by the
computer mouse, an action which allows the user to “view the contents” of $x$.
The result will be a set of things, which we might call $I(x)\in{\bf Set}$,
whose elements are things of type $x$. So clicking on the box $\ulcorner$a
man$\urcorner$ one sees $I(\textnormal{$\ulcorner$a man$\urcorner$})$, the set
of everything the author has documented as being a man. For each aspect
$f\colon x\rightarrow y$ of $x$, the user can see a function from the set
$I(x)$ to $I(y)$, perhaps as a 2-column table as in
(LABEL:dia:instances_of_facts).

The type $x$ may have many aspects, which we can put together into a single
multi-column table. Its columns are the aspects of $x$, and its rows are the
elements of $I(x)$. Consider the following olog, taken from [Spi2] where it
was presented as a database schema.

(51) |
---|---
employeeworks inmanagerfirst namelast namedepartmentsecretarynamestring

The type $\ulcorner$Employee$\urcorner$ has four aspects, namely manager
(valued in $\ulcorner$Employee$\urcorner$), works in (valued in
$\ulcorner$department$\urcorner$), and first name and last name (valued in
$\ulcorner$string$\urcorner$). As a database, each type together with its
aspects form a multi-column table, as in the following example.

######  Example 3.2.1.

We can convert Olog (51) into a database schema. Each box represents a table,
each arrow out of a box represents a column of that table. Here is an example
state of that database.

(108)

Note that every arrow $f\colon x\rightarrow y$ of Olog (51) is represented in
Database (108) as a column of table $x$, and that every cell in that column
can be found in the Id column of table $y$. For example, every cell in the
“works in” column of table employee can be found in the Id column of table
department.

The point is that ologs can be drawn to represent a world-view (as in Section
2), but they can also store data. Rules 1,2, and 3 in 2.1.1 align the
construction of an olog with the ability to document instances for each of its
types.

####  3.2.2. Instance data as a set-valued functor

Let ${\mathcal{C}}$ be an olog. Section 3 so far has described instances of
types, aspects, and facts and how all of these come together into a set of
interconnected tables. The assignment of a set of instances to each type and a
function to each aspect in ${\mathcal{C}}$, such that the declared facts hold,
is called an assignment of instance data for ${\mathcal{C}}$. More precisely,
instance data on ${\mathcal{C}}$ is a functor ${\mathcal{C}}\rightarrow{\bf
Set}$, as in Definition 3.2.3.

######  Definition 3.2.3.

Let ${\mathcal{C}}$ be a category (olog) with underlying graph
$|{\mathcal{C}}|$, and let ${\bf Set}$ denote the category of sets. An
instance of ${\mathcal{C}}$ (or an assignment of instance data for
${\mathcal{C}}$) is a functor $I\colon{\mathcal{C}}\rightarrow{\bf Set}$. That
is, it consists of

  * •

a set $I(x)$ for each object (type) $x$ in ${\mathcal{C}}$,

  * •

a function $I(f)\colon I(x)\rightarrow I(y)$ for each arrow (aspect) $f\colon
x\rightarrow y$ in ${\mathcal{C}}$, and

  * •

for each fact (path-equivalence or equation) 333If we let
$f=f_{1}{\,;\,}f_{2}{\,;\,}\cdots{\,;\,}f_{n}$ and
$f^{\prime}=f^{\prime}_{1}{\,;\,}f^{\prime}_{2}{\,;\,}\cdots{\,;\,}f^{\prime}_{m}$,
then we often write $(f=f^{\prime})\colon i\rightarrow j$ to denote the fact
that these paths are equivalent.

$f_{1}{\,;\,}f_{2}{\,;\,}\cdots{\,;\,}f_{n}=f^{\prime}_{1}{\,;\,}f^{\prime}_{2}{\,;\,}\cdots{\,;\,}f^{\prime}_{m}$

declared in ${\mathcal{C}}$, an equality of functions

$I(f_{1}){\,;\,}I(f_{2}){\,;\,}\cdots{\,;\,}I(f_{n})=I(f^{\prime}_{1}){\,;\,}I(f^{\prime}_{2}){\,;\,}\cdots{\,;\,}I(f^{\prime}_{m}).$

For more on this viewpoint of categories and functors, the reader can consult
[Spi3].

##  4\. Communication between ologs

The world is inherently heterogeneous. Different individuals 444By an
individual we mean either an individual person acting on their own, a
community acting as a single entity, a software agent, etc. Later in this
section we will use the notion of a community acting as a distributed
collection of linked, yet independent, individuals. in the world naturally
have different world-views — each individual has its own perspective on the
world. The conceptual knowledge (information resources) of an individual
represents its world-view, and is encoded in an ontology log, or olog,
containing the concepts, relations, and observations that are important to
that individual. An olog is a formal specification of an individual’s world-
view in a language representing the concepts and relationships used by that
individual. In addition to the formulation of an expressive language, a
specification needs to contain axioms (facts) that constrain the possible
interpretations of that language.

Since the ologs of different individuals are encoded in different languages,
the important need to merge disparate ologs into a more general representation
is difficult, time-consuming and expensive. The solution is to develop
appropriate communication between individuals to allow interoperability of
their ologs. Communication can occur between individuals when there is some
commonality between their world-views. It is this commonality that allows one
individual to benefit from the knowledge and experience of another. In this
section we will discuss how to formulate these channels of communication,
thereby describing a generalized and practical technique for merging ologs.

The mathematical concept that makes it all work is that of a functor. A
functor is a mapping from one category to another that preserves all the
declared structure. Whereas in Definition 3.2.3 we defined a functor from an
olog to $\mathrmbf{Set}$, here we will be discussing functors from one olog to
another.

Suppose we have two ologs, ${\mathcal{C}}$ and ${\mathcal{D}}$, that represent
the world-views of two individuals. A functor
$F\colon{\mathcal{C}}\rightarrow{\mathcal{D}}$ is basically a way of matching
each type (box) of ${\mathcal{C}}$ to a type of ${\mathcal{D}}$, and each
aspect (arrow) in ${\mathcal{C}}$ to an aspect (or path of aspects) in
${\mathcal{D}}$. Once ologs are aligned in this way, communication can occur:
the two individuals know what each other is talking about. In fact,
mathematically we can show that instance data held in ${\mathcal{C}}$ can be
transformed (in coherent ways) to instance data held in ${\mathcal{D}}$, and
vice versa (see [Spi2]). In simple terms, once individuals understand each
other in a certain domain (be it social, mathematical, etc.), they can
communicate their views about it.

While the basic idea is not hard, the details can be a bit technical. This
section is written in a more formal and logical style, and is decidedly more
difficult than the others. For this section only, we assume the reader is
familiar with the notion of fibered categories, colimits in the category ${\bf
Cat}$ of categories, etc. We return to our more informal style in Section 5,
where we discuss how an individual can author a more expressive olog.

###  4.1. Categories and their presentations

We never defined categories in this paper, but we defined ologs and said that
the two notions amounted to the same thing. Thus, we implied that a category
consists of the following: a set of objects, a set of arrows (each pointing
from one object to another), and a congruence relation on paths.555A
congruence relation on paths is an equivalence relation on paths that respects
endpoints and is closed under composition from left and right (see the axioms
in 115). This differs from the standard definition of categories (see [Mac]),
which replaces our congruence relation with a composition rule and
associativity law (obtained by taking the categorical quotient). One could say
that an olog is a presentation of a category by generators (objects and
arrows) and relations (path congruences). Any category can be resolved and
presented in such a way, which we will call a specification. Likewise any
functor can be resolved and presented as a morphism between specifications.
666We take an agnostic approach to foundations here. With the presentation
form, we show how categories and functors are definable in terms of sets and
functions, indicating how category theoretic concepts could be defined in
terms of set theory. However, we fully understand that $\mathbf{Set}$, the
category of sets and functions, is but one example of a topos, indicating how
set theoretic concepts could be defined in terms of category theory.

In fact, this presentation form for categories (and the analogous one for
functors) is preferable for our work on communication between ologs, because
it separates the strictly graphical part of an olog (its types and aspects,
regarded as the olog language) from the propositional part (its facts,
regarded as the olog formalism). This presentation form is standard in the
institutions [GB] and information flow [BS] communities, since it separates
the mechanism of flow from the content of flow; in this case the formal
content. Our work here applies the general theories of institutions and
information flow to the specific logical system that underlies categories and
functors,777For the expert, this refers to the sketch logical system Sk, in
its various manifestations. demonstrating how this logical system can be used
for knowledge representation. Using the presentation forms for categories and
functors, we show how communication between individuals is effected by the
flow of information along channels.

###  4.2. The architecture underlying information systems

We think of a community of people, businesses, etc. in terms of the ologs of
each individual participant together with the information channels that
connect them. These channels are functors between ologs, which allow
communication to occur. The heterogeneity of multiple differing world-views
connected through such links can lead to a flexibility and robustness of
interaction. For example, heterogeneity allows for multiple schemas to be
employed in the design of database systems in particular, and multiple
languages to be employed in the design of knowledge representation systems in
general.

For any olog, consider the underlying graph of types and aspects. We regard
this graph as being the language of the olog, 888Section 4.4 indicates how
natural languages can be encoded into ologs. with the facts of the olog being
a subset of all the possible assertions that one can make within this
language. Any two ologs with the same underlying graph of types and aspects
have the same language, and since the facts of each olog are expressed in the
same language, they can be “understood” by each other without translation. As
such, we think of the collection of all ologs with the same language
(underlying graph) as forming a homogeneous context, with the ologs ordered in
a specialization-generalization hierarchy.

Whereas an olog represents (the world-view of) a single individual, an
information system (of ologs) represents a community of separate, independent
and distributed individuals. Here we consider an information system to be a
diagram of ologs of some shape $\mathrmbf{I}$; that is, a collection of ologs
and constraints indexed by a base category $\mathrmbf{I}$. The parts of the
system represent either the ologs of the various individuals in the system or
common grounds needed for communication between the individuals. Each part of
the system specifies its world-view as facts expressed in terms of its
language. The system is heterogeneous, since each part has a separate language
for the expression of its world-view. The morphisms between the parts are the
alignment (constraint) links defining the common grounds.

As will be made clear in a moment, there is an underlying distributed system
consisting of the language (underlying graph) for each component part of the
information system and a translation (graph morphism) for each alignment link.
We can think of this distributed system as an underlying system of languages
linked by translating dictionaries. This distributed system determines an
information channel with core language (graph) and component translation links
(graph morphisms) along which the specifications of each component part can
flow to the core. We can think of this core as a universal language for the
whole system and the channel as a translation mechanism from parts to whole.
At the core, the direct flow of the component specifications are joined
together (unioned) and allowed to interact through entailment. The result of
this interaction can then be distributed back to the component parts, thereby
allowing the separate parts of an information system to interoperate.

In this section, we will make all this clear and rigorous. As mentioned above,
we will work with category presentations (here called specifications) rather
than categories. We will discuss the homogeneous contexts called fibers in
detail and give the axioms of satisfaction. We will then discuss how morphisms
between graphs (the translating dictionaries between the ologs) allow for
direct and inverse information flow between these homogeneous fiber contexts.
Finally, we discuss specifications (also known as theories) and the lattice of
theories construction for ontologies.

In Section 4.3 we will discuss how the information in ologs can be aligned by
the use of common grounds. This alignment will result in the creation of
information systems, which are systems of ologs connected together along
functors. We will discuss how to take the information contained in each olog
of a heterogeneous system and integrate it all into a single whole, called the
fusion olog. Finally we will discuss how the consequence of bringing all this
information together, and allowing it to interact, can be transferred back to
each part of the system (individual olog) as a set of local facts entailed by
remote ologs, allowing for a kind of interoperability between ologs. In
Section 4.4 we will discuss conceptual graphs and their relationship to ologs.

####  4.2.1. Fibers

A graph $G$ contains types as nodes and aspects as edges. The graphs
underlying an olog is considered its language. Any category $\mathcal{C}$ has
an underlying graph $|\mathcal{C}|$. In particular, $|\mathrmbf{Set}|$ is the
graph underlying the category of sets and functions. Olog (12) has an
underlying graph containing the three types $\ulcorner$person$\urcorner$,
$\ulcorner$person-pair$\urcorner$ and $\ulcorner$woman$\urcorner$ and the
three aspects ‘has a parent’, ‘woman’ and ‘has as mother’. Olog (17) has an
underlying graph containing the three types $\ulcorner$employee$\urcorner$,
$\ulcorner$department$\urcorner$, and $\ulcorner$string$\urcorner$ and the six
aspects ‘manager’, ‘works in’, ‘secretary’, ‘name’, ‘first name’ and ‘last
name’. Let $\mathrmbfit{eqn}(G)$ denote the set of all facts (equations) that
are possible to express using the types and aspects of $G$. A
$G$-specification is a set $E\subseteq\mathrmbfit{eqn}(G)$ consisting of some
of the facts expressible in $G$. The singleton set with the one fact that “the
female parent of a person is his/her mother” is a specification for the graph
of Olog (12). The set with the two facts that “the manager has the same
department as any employee” and “the secretary of a department is an employee
in that department” is a specification for the graph of Olog (17). Let
$\mathrmbfit{spec}(G)$ denote the collection of all $G$-specifications ordered
by inclusion $E_{1}\subseteq E_{2}$.

####  4.2.2. Satisfaction

It will be useful here to define an instance of a graph $G$, instead of an
instance of a category $\mathcal{C}$. An instance of a graph populates the
graph by assigning instance data to it. An instance of a graph $G$ is a graph
morphism $D\colon G\rightarrow|\mathrmbf{Set}|$ mapping each type $x$ in $G$
to a set $D(x)$ of instances and mapping each aspect $e\colon x\rightarrow y$
in $G$ to an instance function $D(e)\colon D(x)\rightarrow D(y)$. Using
database terminology, we also call $D$ a key diagram, since it gives the set
of row identifiers (primary keys) of tables and the cell contents defined by
key maps.

A key diagram $D\colon G\rightarrow|\mathrmbf{Set}|$ satisfies (is a model of)
a $G$-fact $\epsilon\in\mathrmbfit{eqn}(G)$ (see Definition 3.2.3), symbolized
$D\models_{G}\epsilon$, when we have an equality of functions
$D^{\ast}(\epsilon_{0})=D^{\ast}(\epsilon_{1})$. We also say that $\epsilon$
(holds in) is true when interpreted in $D$. An identity $(f=_{G}f)\colon
i\rightarrow j$ holds in all key diagrams (hence, is a tautology), and vice-
versa for any set $A\in|\mathrmbf{Set}|$ a constant key diagram
$\Delta(A)\colon G\rightarrow|\mathrmbf{Set}|$ satisfies any fact
$\epsilon\in\mathrmbfit{eqn}(G)$. A key diagram $D\colon
G\rightarrow|\mathrmbf{Set}|$ satisfies (is a model of) a $G$-specification
$E$, symbolized $D\models_{G}E$, when it satisfies every fact in the
specification. For any graph $G$, a $G$-specification $E$ entails a $G$-fact
$\epsilon$, denoted by $E\vdash_{G}\epsilon$, when any model of the
specification satisfies the fact. The consequence
$E^{\scriptscriptstyle\bullet}$ of a $G$-specification $E$ is the set of all
entailed equations. The consequence operator $(-)^{\scriptscriptstyle\bullet}$
is a closure operator, and the consequence of a specification is a congruence.
For any $G$-specification $E$, entailment satisfies the following axioms.

(115) (basic) If $E$ contains the equation $\epsilon$, then $E$ entails
$\epsilon$. (reflexive) $E$ entails the equations $(f=_{G}f)\colon
i\rightarrow j$ for any path $f\colon i\rightarrow j$. (symmetric) If $E$
entails the equation $(f_{1}=_{G}f_{2})\colon i\rightarrow j$, then $E$
entails the equation $(f_{2}=_{G}f_{1})\colon i\rightarrow j$. (transitive) If
$E$ entails the two equations $(f_{1}=_{G}f_{2})\colon i\rightarrow j$ and
$(f_{2}=_{G}f_{3})\colon i\rightarrow j$, then $E$ entails the equation
$(f_{1}=_{G}f_{3})\colon i\rightarrow j$. (compositional) If $E$ entails the
two equations $(f_{1}=_{G}f_{2})\colon i\rightarrow j$ and
$(g_{1}=_{G}g_{2})\colon j\rightarrow k$, then $E$ entails the equation
$(f_{1}{\,;\,}g_{1}=_{G}f_{2}{\,;\,}g_{2})\colon i\rightarrow k$. (bi-closed)
If $E$ entails the equation $(g_{1}=_{G}g_{2})\colon j\rightarrow k$, then $E$
entails the equations $(f{\,;\,}g_{1}=_{G}f{\,;\,}g_{2})\colon i\rightarrow k$
and $(g_{1}{\,;\,}h=_{G}g_{2}{\,;\,}h)\colon j\rightarrow l$ for any left
composable path $f\colon i\rightarrow j$ and any right composable path
$h\colon k\rightarrow l$.

These are converted to inference rules in Table 1. To construct
$E^{\scriptscriptstyle\bullet}$, we first take the reflexive, symmetric, and
transitive closure $E^{\ast}$ of $E$ (so that $E^{\ast}$ is a
$G$-specification and also the smallest equivalence relation containing $E$),
and then we get $E^{\scriptscriptstyle\bullet}$ by closing up under
composition on left and right. We extend specification inclusion with the
entailment order, where $E_{1}\leq_{G}E_{2}$ when $E_{1}$ entails each
equation in $E_{2}$; that is, when $E_{1}^{\scriptscriptstyle\bullet}\supseteq
E_{2}$ or equivalently when $E_{1}^{\scriptscriptstyle\bullet}\supseteq
E_{2}^{\scriptscriptstyle\bullet}$. The statement “$E_{1}\leq_{G}E_{2}$”
asserts that $E_{1}$ is at least as specialized as $E_{2}$. The entailment
order ${\langle{\mathrmbfit{spec}(G),\leq_{G}}\rangle}$, which is a
specialization-generalization order, represents a local version of the
“lattice of theories” construction of Sowa [Sow2] (see Section 4.2.5). The
opposite entailment order
$\mathrmbfit{fbr}(G)={\langle{\mathrmbfit{spec}(G),\geq_{G}}\rangle}$ is
called the fiber order.999For consistency in discussion, we follow the
terminology of formal concept analysis [GW], information flow [BS] and the
theory of institutions [GB]. This includes the polarity induced by concept
lattices and the directionality of infomorphisms. In the lattice101010This is
a complete preorder, loosely called a “lattice”. $\mathrmbfit{spec}(G)$, the
meet is union $\wedge=\cup$ and the join is intersection $\vee=\cap$; whereas
in the lattice $\mathrmbfit{fbr}(G)$, the join is union $\vee=\cup$ and the
meet is intersection $\wedge=\cap$. Any specification $E$ is entailment
equivalent to its consequence $E\cong E^{\scriptstyle\bullet}$. A
specification $E$ is closed when it is equal to its consequence
$E=E^{\scriptstyle\bullet}$. There is a one-one correspondence between closed
$G$-specifications and categories over graph $G$. The conceptual intent of a
key diagram $D$, implicit in satisfaction, is the closed specification
$\mathrmbfit{int}(D)$ consisting of all facts satisfied by the key diagram.
Hence, $D\models_{G}E$ iff $E\subseteq\mathrmbfit{int}(D)$ iff
$\mathrmbfit{int}(D)\leq_{G}E$.111111This is the first step in the
algebraization of Tarski’s “semantic definition of truth” [Ken4].

####  4.2.3. Elementary flow

A graph morphism $H\colon G_{1}\rightarrow G_{2}$ maps the types and aspects
of $G_{1}$ to the types and aspects of $G_{2}$. Graph morphisms are the
translations between ologs. A functor
$\mathcal{F}\colon\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ has an underlying
graph morphism
$|\mathcal{F}|\colon|\mathcal{C}_{1}|\rightarrow|\mathcal{C}_{2}|$. For any
graph morphism $H\colon G_{1}\rightarrow G_{2}$, there is a fact function
$\mathrmbfit{eqn}(H)\colon\mathrmbfit{eqn}(G_{1})\rightarrow\mathrmbfit{eqn}(G_{2})$
that maps a $G_{1}$-equation $(f_{1}=_{G_{1}}f^{\prime}_{1})\colon
i_{1}\rightarrow j_{1}$ to the $G_{2}$-equation
$(H^{\ast}(f_{1})=_{G_{2}}H^{\ast}(f^{\prime}_{1}))\colon H(i_{1})\rightarrow
H(j_{1})$, and a key diagram functor
$\mathrmbfit{dgm}(H)\colon\mathrmbfit{dgm}(G_{2})\rightarrow\mathrmbfit{dgm}(G_{1})$
that maps a key diagram $D_{2}\colon G_{2}\rightarrow|\mathrmbf{Set}|$ to the
key diagram $H\circ D_{2}\colon G_{2}\rightarrow|\mathrmbf{Set}|$.121212The
composition of graph morphisms is written in diagrammatic order. The fact
function is the fundamental unit of information (formal) flow for ologs, and
the key diagram functor is the fundamental unit of semantic flow for
ologs.131313This is so, at the abstraction of institutions [Ken3]. Formal flow
is adjoint to semantic flow — satisfaction is invariant under flow:
$\mathrmbfit{dgm}(H)(D_{2})\models_{G_{1}}\epsilon_{1}$ iff
$D_{2}\models_{G_{2}}\mathrmbfit{eqn}(H)(\epsilon_{1})$ for any graph morphism
$H\colon G_{1}\rightarrow G_{2}$, source fact $\epsilon_{1}$ and target
diagram $D_{2}$. Specifications can be moved along graph morphisms by
extending the fact (equation) function. For any graph morphism $H\colon
G_{1}\rightarrow G_{2}$, define the direct flow operator
$\mathrmbfit{dir}(H)={\wp}\mathrmbfit{eqn}(H):\mathrmbfit{spec}(G_{1})\rightarrow\mathrmbfit{spec}(G_{2})$141414The
symbol $\wp$ denotes the power-set operator. and the inverse flow operator
$\mathrmbfit{inv}(H)=\mathrmbfit{eqn}(H)^{-1}((\mbox{-})^{\scriptscriptstyle\bullet}):\mathrmbfit{spec}(G_{2})\rightarrow\mathrmbfit{spec}(G_{1})$.
Direct and inverse flow are adjoint monotonic functions
${\langle{\mathrmbfit{dir}(H)\dashv\mathrmbfit{inv}(H)}\rangle}\colon\mathrmbfit{fbr}(G_{1})\rightarrow\mathrmbfit{fbr}(G_{2})$
w.r.t. fiber order: $\mathrmbfit{dir}(H)(E_{1})\geq_{G_{2}}E_{2}\text{
\text@underline{iff} }E_{1}\geq_{G_{1}}\mathrmbfit{inv}(H)(E_{2})$. For any
graph morphism $H\colon G_{1}\rightarrow G_{2}$, any $G_{1}$-specification
$E_{1}$, and any $G_{2}$-specification $E_{2}$, entailment satisfies the
following axioms.

(direct flow) |  If $E_{1}$ entails the equation $(f=_{G_{1}}f^{\prime})\colon i\rightarrow j$, then $\mathrmbfit{dir}(H)(E_{1})$ entails the equation $(H^{\ast}(f_{1})=_{G_{2}}H^{\ast}(f^{\prime}_{1}))\colon H(i_{1})\rightarrow H(j_{1})$.
---|---
(inverse flow) |  If $E_{2}$ entails the equation $(H^{\ast}(f)=_{G_{2}}H^{\ast}(f^{\prime}))\colon H(i)\rightarrow H(j)$, then $\mathrmbfit{inv}(H)(E_{2})$ entails the equation $(f=_{G_{1}}f^{\prime})\colon i\rightarrow j$.

These are converted to inference rules in Table 1. A graph morphism $H\colon
G_{1}\rightarrow G_{2}$ defines a consequence operator
${(\mbox{-})}^{{\scriptscriptstyle\blacklozenge}_{H}}=\mathrmbfit{dir}(H)\circ\mathrmbfit{inv}(H)$
on the fiber preorder $\mathrmbfit{fbr}(G_{1})$, where
$E_{1}\geq_{G_{1}}E_{1}^{\scriptstyle\bullet}\geq_{G_{1}}E_{1}^{{\scriptscriptstyle\blacklozenge}_{H}}$.

####  4.2.4. Specifications

A specification $\mathcal{S}={\langle{G,E}\rangle}$ is an indexed notion
consisting of a graph $G$ and a $G$-specification $E\in\mathrmbfit{spec}(G)$.
It is sometimes convenient to use the symbol ‘$\mathcal{S}$’ in place of
‘$E$’; for example, to say that “$\mathcal{S}\in\mathrmbfit{spec}(G)$”. A
category $\mathcal{C}$ can be resolved and presented as a specification
$\mathrmbfit{spec}(\mathcal{C})={\langle{G,E}\rangle}$ consisting of the
underlying graph $G=|\mathcal{C}|$ containing the types and aspects of
$\mathcal{C}$ and the collection $E$ of all facts that hold in $\mathcal{C}$.
In the other direction, any specification $\mathcal{S}$ induces a (quotient)
category $\mathrmbfit{cat}(\mathcal{S})$. Olog (12) and Olog (17) are
described as specifications in Section 4.2.1. A specification morphism
$H\colon{\langle{G_{1},E_{1}}\rangle}\rightarrow{\langle{G_{2},E_{2}}\rangle}$
is a graph morphism $H\colon G_{1}\rightarrow G_{2}$ that preserves
entailment: $E_{1}\vdash_{G_{1}}\epsilon_{1}$ implies
$E_{2}\vdash_{G_{2}}\mathrmbfit{eqn}(H)(\epsilon_{1})$ for any
$\epsilon_{1}\in\mathrmbfit{eqn}(G_{1})$; or equivalently that satisfies the
adjointness conditions, $\mathrmbfit{dir}(H)(E_{1})\geq_{G_{2}}E_{2}\text{
\text@underline{iff} }E_{1}\geq_{G_{1}}\mathrmbfit{inv}(H)(E_{2})$. Being a
graph morphism, it maps types to types and aspects to aspects. Moreover, it
also maps facts in $E_{1}$ to facts in $E_{2}$; that is, it preserves all the
declared structure. A functor
$\mathcal{F}\colon\mathcal{C}_{1}\rightarrow\mathcal{C}_{2}$ can be resolved
and presented as a specification morphism
$\mathcal{F}\colon\mathrmbfit{spec}(\mathcal{C}_{1})\rightarrow\mathrmbfit{spec}(\mathcal{C}_{2})$.
Hence, the presentation form for a functor does exactly what the functor does.
The fibered category of specifications $\mathrmbf{Spec}$ has specifications as
objects and specification morphisms as morphisms. Thus, it is defined in terms
of information flow. There is an underlying graph functor
$\mathrmbfit{gph}\colon\mathrmbf{Spec}\rightarrow\mathrmbf{Gph}$ from
specifications to graphs ${\langle{G,E}\rangle}\mapsto G$. The subcategory
over any fixed graph $G$ is the fiber $\mathrmbfit{fbr}(G)$; because of the
opposite orientation, we say that “the category of specifications points
downward in the concept lattice”. Throughout this section we identify ologs
with specifications and olog morphisms with specification morphisms.

####  4.2.5. The lattice of theories construction

Sowa’s “lattice of theories” construction (LOT) describes a modular framework
for ontologies [Sow2]. The Olog formalism follows the approach to LOT
described in [IFF2].151515The IFF term ‘theory’ is replaced by the Olog term
’specification’ or ’olog’. In the Olog formalism, LOT is locally represented
by the entailment preorders $\mathrmbfit{spec}(G)$, and globally represented
by the category of specifications $\mathrmbf{Spec}$. We follow the discussion
in section 6.5 “Theories, Models and the World” of Sowa [Sow2]. From each olog
(specification) in the “lattice of theories”, the entailment ordering defines
paths to the more generalized ologs above and the more specialized ologs
below. Sowa defines four ways for moving along paths from one olog to another:
contraction, expansion, revision and analogy.

Contraction:

Any olog can be contracted or reduced to a smaller, simpler olog, moving
upward in the preorder $\mathrmbfit{spec}(G)$, by deleting one or more facts.

Expansion:

Any olog can be expanded, moving downward in the preorder
$\mathrmbfit{spec}(G)$, by adding one or more facts.

Revision:

A revision step is composite, moving crosswise in the preorder
$\mathrmbfit{spec}(G)$; it uses a contraction step to discard irrelevant
details, followed by an expansion step to added new facts.

Analogy:

Unlike contraction and expansion, which move to nearby ologs in an entailment
preorder $\mathrmbfit{spec}(G)$, analogy moves to an olog in a remote
entailment preorder in the category $\mathrmbf{Spec}$ via the flow along an
underlying graph morphism $H\colon G_{1}\rightarrow G_{2}$ by systematically
renaming the types and aspects that appear in the facts: any olog $E_{1}$ in
$\mathrmbfit{spec}(G_{1})$ is moved (by systematic renaming) to the olog
$\mathrmbfit{dir}(H)(E_{1})$ in $\mathrmbfit{spec}(G_{2})$.

According to Sowa, the various methods used in nonmonotonic logic and the
operators for belief revision correspond to movement through the lattice of
theories.

###  4.3. Alignment and integration of information systems

####  4.3.1. Common ground

Given the world-views of two individuals, as represented by ologs
$\mathcal{S}_{1}={\langle{G_{1},E_{1}}\rangle}$ and
$\mathcal{S}_{2}={\langle{G_{2},E_{2}}\rangle}$, there is little hope that one
of them completely contains the other (even after allowing for renaming of
types and aspects), and there is correspondingly little chance of finding a
meaningful olog morphism between the two. Instead, in order to communicate the
two individuals could attempt to find a common ground, a third olog
$\mathcal{S}={\langle{G,E}\rangle}$ and meaningful morphisms161616Roughly
speaking, an olog morphism $F\colon\mathcal{C}\rightarrow\mathcal{D}$ is
meaningful when for each type $X$ in ${\mathcal{C}}$, every intended instance
of $X$ in ${\mathcal{C}}$ would be considered an instance of $F(X)$ by the
author of ${\mathcal{D}}$ (in which case we say the intention for types is
respected), and in a similar way the intention for aspects is respected.
Precisely speaking, if $I\colon{\mathcal{C}}\rightarrow{\bf Set}$ and
$J\colon{\mathcal{D}}\rightarrow{\bf Set}$ are instance data for
${\mathcal{C}}$ and ${\mathcal{D}}$, then $F$ is meaningful relative to $I$
and $J$ if one can exhibit a natural transformation $\mu\colon I\Rightarrow
F\circ J$ as in [Spi2]. $H_{1}\colon\mathcal{S}\rightarrow\mathcal{S}_{1}$ and
$H_{2}\colon\mathcal{S}\rightarrow\mathcal{S}_{2}$.171717A common ground olog
is also called a reference ontology in knowledge representation. This
connection is a 1-dimensional knowledge network
$\mathcal{S}_{1}\xleftarrow{H_{1}}\mathcal{S}\xrightarrow{H_{2}}\mathcal{S}_{2}$
of shape $\bullet\leftarrow\bullet\rightarrow\bullet$ called a span (in
$\mathrmbf{Spec}$), where each node is an olog and each edge is a morphism
between ologs. The requirements of this span are that
$\mathrmbfit{dir}(H_{1})(E)\geq_{G_{1}}E_{1}$ and
$\mathrmbfit{dir}(H_{2})(E)\geq_{G_{2}}E_{2}$, two requirements involving
local flow. Equivalently, that
$E\geq_{G}\mathrmbfit{inv}(H_{1})(E_{1})\vee_{G}\mathrmbfit{inv}(H_{2})(E_{2})$.
The latter precise expression can be rendered in natural language as “the
world-view of the common ground is contained in the combined world-views of
the two individuals”. The various local direct/inverse flows allow world-views
to be compared. Such a common ground can be expanded and improved over time.
The basic idea is that one individual can attempt to explain a new idea (type,
aspect or fact) to another in terms of the common ground. Then the other
individual can either interpret this idea as they already have, learn from it
(i.e. freely add it to their olog), or reject it. We view an olog morphism
$H_{1}\colon\mathcal{S}_{1}\rightarrow\mathcal{S}_{2}$ as an atomic constraint
(alignment) link between $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$.181818This is
so, at the abstraction of institutions [Ken3]. We view a common ground span
$\mathcal{S}_{1}\xleftarrow{H_{1}}\mathcal{S}\xrightarrow{H_{2}}\mathcal{S}_{2}$
as a molecular constraint between $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$,
which is weakest when $\mathcal{S}=\emptyset$ and strongest when
$\mathcal{S}_{1}=\mathcal{S}=\mathcal{S}_{2}$.

####  4.3.2. Systems of ologs

In the general case, more than two individuals will share a common ground. For
example, companies that do business together may have a common-ground olog as
part of a legal contract; or, the various participants at a conference will
have some common understanding of the topic of that conference. In fact, for
any finite set of ologs
$\mathbb{X}=\\{{\mathcal{S}}_{1},{\mathcal{S}}_{2},\ldots,{\mathcal{S}}_{n}\\}$,
there should be a common ground world-view (even if empty), say
$\mathcal{S}_{\mathbb{X}}$. If $\mathbb{Y}\subseteq\mathbb{X}$ is a subset,
then there should be a map
$\mathcal{S}_{\mathbb{X}}\rightarrow\mathcal{S}_{\mathbb{Y}}$ because any
common understanding held by the individuals in $\mathbb{X}$ is held by the
individuals in $\mathbb{Y}$. For example, the triangular-shaped diagram

(126)

represents three individuals $\\{1,2,3\\}$, their ologs
$\\{{\mathcal{S}}_{1},{\mathcal{S}}_{2},{\mathcal{S}}_{3}\\}$, their pair-wise
commonality ologs
$\\{{\mathcal{S}}_{12},{\mathcal{S}}_{13},{\mathcal{S}}_{23}\\}$, and their
three-way commonality olog ${\mathcal{S}}_{123}$. This diagram, which stands
for the interaction between individuals $\\{1,2,3\\}$, does not stand alone,
but is part of an intricate web of other ologs and alignment constraints. In
particular, individuals 1 and 3 may be part of some different interacting
group, say of individuals $\\{1,3,6,7\\}$, and hence the right edge of the
diagram would be part of some tetrahedron-shaped diagram with vertices
$\\{1,3,6,7\\}$. If we take the point-of-view that “a collection of ologs
representing the world-views of various individuals” is a system, then we can
think of the ologs as being the types of that system, the morphisms connecting
the ologs as being the aspects of that system, with the shape of a system
being its underlying graph. In essence, we can apply ologs to themselves. In
the system represented by diagram (126), there are seven types
$\\{{\mathcal{S}}_{1},{\mathcal{S}}_{2},{\mathcal{S}}_{3},{\mathcal{S}}_{12},{\mathcal{S}}_{13},{\mathcal{S}}_{23},{\mathcal{S}}_{123}\\}$
and nine aspects
$\\{\cdots,{\mathcal{S}}_{123}\rightarrow{\mathcal{S}}_{13},\dots\\}$, and the
shape looks like this

---

In addition, we can introduce certain facts to represent the meaning of that
system and then enforce those facts.

A distributed system is a diagram (functor)
$\mathcal{G}\colon\mathrmbf{I}\rightarrow\mathrmbf{Gph}$ of shape
$\mathrmbf{I}$ within the ambient category $\mathrmbf{Gph}$. As such, it
consists of an indexed family $\\{G_{n}\mid n\in\mathrmbf{I}\\}$ of graphs
together with an indexed family $\\{G_{e}\colon G_{n}\rightarrow
G_{m}\mid(e\colon n\rightarrow m)\in\mathrmbf{I}\\}$ of graph morphisms. Let
$\mathrmbf{Dist}(\mathrmbf{I})$ denote the collection of distributed systems
of shape $\mathrmbf{I}$. An information system is a diagram
$\mathcal{S}\colon\mathrmbf{I}\rightarrow\mathrmbf{Spec}$ of shape
$\mathrmbf{I}$ within the ambient category $\mathrmbf{Spec}$. As such, it
consists of an indexed family
$\\{\mathcal{S}_{n}={\langle{G_{n},E_{n}}\rangle}\mid n\in\mathrmbf{I}\\}$ of
ologs together with an indexed family
$\\{\mathcal{S}_{e}\colon\mathcal{S}_{n}\rightarrow\mathcal{S}_{m}\mid(e\colon
n\rightarrow m)\in\mathrmbf{I}\\}$ of olog morphisms. Some of these ologs
might represent the world-views of various individuals, whereas others could
be common grounds; also included might be portals between individual ologs and
common grounds, as in the CG example of Section 4.4. Let
$\mathrmbf{Info}(\mathrmbf{I})$ denote the collection of information systems
of shape $\mathrmbf{I}$. An information system $\mathcal{S}$ with component
ologs $\mathcal{S}_{n}={\langle{G_{n},E_{n}}\rangle}$ has an underlying
distributed system $\mathcal{G}$ of the same shape with component graphs
$G_{n}$ for $n\in\mathrmbf{I}$. For any distributed system $\mathcal{G}$, let
$\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$ denote the collection of
information systems over $\mathcal{G}$ of shape $\mathrmbf{I}$. There is a
pointwise entailment order
$\mathcal{S}\leq^{\mathrmbf{I}}_{\mathcal{G}}\mathcal{S}^{\prime}$ on
$\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$ when component ologs satisfy
the same entailment ordering $E_{n}\leq_{G_{n}}E^{\prime}_{n}$ for
$n\in\mathrmbf{I}$, and by taking the coproduct there is a pointwise
entailment order on
$\mathrmbf{Info}(\mathrmbf{I})=\coprod_{\mathcal{G}\in\mathrmbf{Dist}(\mathrmbf{I})}\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$.
A constant distributed system $\Delta(G)\in\mathrmbf{Dist}(\mathrmbf{I})$ is a
distributed system $\Delta(G)\colon\mathrmbf{I}\rightarrow\mathrmbf{Gph}$ with
the same language $G$ for any index $n\in\mathrmbf{I}$. Any constant
distributed system defines join and meet monotonic functions
$\bigvee^{\mathrmbf{I}}_{G},\bigwedge^{\mathrmbf{I}}_{G}:\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(G))\rightarrow\mathrmbfit{fbr}(G)$
mapping an information system
$\mathcal{S}\in\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(G))$ to the join and
meet ologs $\bigvee\mathcal{S}=\bigcup_{n\in\mathrmbf{I}}E_{n}$ and
$\bigwedge\mathcal{S}=\bigcap_{n\in\mathrmbf{I}}E_{n}$ in
$\mathrmbfit{fbr}(G)$. The join monotonic function is adjoint to the constant
monotonic function
$\Delta^{\mathrmbf{I}}_{G}:\mathrmbfit{fbr}(G)\rightarrow\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(G))$
that distributes an olog $\mathcal{S}^{\prime}\in\mathrmbfit{fbr}(G)$ to the
various locations $n\in\mathrmbf{I}$ forming a constant information system
$\Delta(\mathcal{S}^{\prime})\in\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(G))$,
since $\bigvee\mathcal{S}\geq_{G}\mathcal{S}^{\prime}$ iff
$\mathcal{S}\geq^{\mathrmbf{I}}_{\Delta(G)}\Delta(\mathcal{S}^{\prime})$ for
any system $\mathcal{S}\in\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(G))$ and any
olog $\mathcal{S}^{\prime}\in\mathrmbfit{fbr}(G)$.

####  4.3.3. System morphisms

Just as ologs are linked by morphisms, information systems are also linked by
morphisms. For these there is the new complication of shape. In this paper we
define fixed-shape system moorphisms, but a more general definition would
allow the shape to vary. A distributed system morphism
$\theta\colon\mathcal{G}\Rightarrow\mathcal{G}^{\prime}$ in
$\mathrmbf{Dist}(\mathrmbf{I})$ consists of a collection $\\{\theta_{n}\colon
G_{n}\rightarrow G^{\prime}_{n}\mid n\in\mathrmbf{I}\\}$ of component graph
morphisms, which are systematically coordinated in the sense that they satisfy
the naturality conditions $G_{e}\circ\theta_{m}=\theta_{n}\circ
G^{\prime}_{e}$ for any indexing link $e\colon n\rightarrow m$ in
$\mathrmbf{I}$. A direct flow operator
$\mathrmbfit{dir}_{\mathrmbf{I}}(\theta):\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})\rightarrow\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G}^{\prime})$
along $\theta$ can be define, which maps an information system
$\mathcal{S}\in\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$ to an
information system
$\mathrmbfit{dir}_{\mathrmbf{I}}(\theta)(\mathcal{S})\in\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G}^{\prime})$
defined by
$\mathrmbfit{dir}_{\mathrmbf{I}}(\theta)(\mathcal{S})_{n}=\mathrmbfit{dir}(\theta_{n})(E_{n})$
for $n\in\mathrmbf{I}$.191919Well-defined, since
$\mathrmbfit{dir}(G^{\prime}_{e})(\mathrmbfit{dir}(\theta_{n})(E_{n}))=\mathrmbfit{dir}(\theta_{m})(\mathrmbfit{dir}(G_{e})(E_{n}))\geq_{m}\mathrmbfit{dir}(\theta_{m})(E_{m})$.
An inverse flow operator
$\mathrmbfit{inv}_{\mathrmbf{I}}(\theta):\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G}^{\prime})\rightarrow\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$
can similarly be defined. Direct and inverse flow are adjoint monotonic
functions
${\langle{\mathrmbfit{dir}_{\mathrmbf{I}}(\theta)\dashv\mathrmbfit{inv}_{\mathrmbf{I}}(\theta)}\rangle}:\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})\rightarrow\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G}^{\prime})$,
since
$\mathrmbfit{dir}_{\mathrmbf{I}}(\theta)(\mathcal{S})\geq^{\mathrmbf{I}}_{\mathcal{G}^{\prime}}\mathcal{S}^{\prime}$
iff
$\mathcal{S}\geq^{\mathrmbf{I}}_{\mathcal{G}}\mathrmbfit{inv}_{\mathrmbf{I}}(\theta)(\mathcal{S}^{\prime})$.
An information system morphism
$\theta\colon\mathcal{S}\Rightarrow\mathcal{S}^{\prime}$ in
$\mathrmbf{Info}(\mathrmbf{I})$ consists of a collection
$\\{\theta_{n}\colon\mathcal{S}_{n}\rightarrow\mathcal{S}^{\prime}_{n}\mid
n\in\mathrmbf{I}\\}$ of component olog morphisms, which are systematically
coordinated and preserve alignment in the sense that they satisfy the
naturality conditions
$\mathcal{S}_{e}\circ\theta_{m}=\theta_{n}\circ\mathcal{S}^{\prime}_{e}$ for
any indexing link $e\colon n\rightarrow m$ in $\mathrmbf{I}$; equivalently,
$\theta$ is a morphism between the underlying distributed systems
$\theta\colon\mathcal{G}\Rightarrow\mathcal{G}^{\prime}$ and the direct flow
of $\mathcal{S}$ is at least as general as $\mathcal{S}^{\prime}$:
$\mathrmbfit{dir}_{\mathrmbf{I}}(\theta)(\mathcal{S})\geq^{\mathrmbf{I}}_{\mathcal{G}^{\prime}}\mathcal{S}^{\prime}$.
The ordering
$\mathcal{S}\geq^{\mathrmbf{I}}_{\mathcal{G}}\mathcal{S}^{\prime}$ is an
information system morphism
$\theta\colon\mathcal{S}\Rightarrow\mathcal{S}^{\prime}$ with identity
component translations $\theta_{n}=\mathrmit{id}_{G_{n}}$ for each index
$n\in\mathrmbf{I}$.

####  4.3.4. Channels

We continue with our systems point-of-view. Since we have represented the
whole system as a diagram $\mathcal{S}$ of parts (ologs) $\mathcal{S}_{n}$
with part-part relations (alignment constraints)
$\mathcal{S}_{n}\rightarrow\mathcal{S}_{m}$, we also want to represent the
whole system as an olog $\mathcal{C}$ with part-whole relations
$\mathcal{S}_{n}\rightarrow\mathcal{C}$.202020The theory of part-whole
relations is called mereology. It studies how parts are related to wholes, and
how parts are related to other parts within a whole. An information channel
${\langle{\gamma\colon\mathcal{M}\Rightarrow\Delta(C),C}\rangle}$ consists of
an indexed family $\\{\gamma_{n}\colon G_{n}\rightarrow C\mid
n\in\mathrmbf{I}\\}$ of graph morphisms called flow links with a common target
graph $C$ called the core of the channel. A channel
${\langle{\gamma,C}\rangle}$ covers a distributed system $\mathcal{G}$ of
shape $\mathrmbf{I}$ when the part-whole relationships respect the alignment
constraints (are consistent with the part-part relationships):
$\gamma_{n}=G_{e}\circ\gamma_{m}$ for each indexing morphism $e\colon
n\rightarrow m$ in $\mathrmbf{I}$. A covering channel is a distributed system
morphism $\gamma\colon\mathcal{G}\Rightarrow\Delta(C)$ in
$\mathrmbf{Dist}(\mathrmbf{I})$ from distributed system $\mathcal{G}$ to
constant distributed system
$\Delta(C)\colon\mathrmbf{I}\rightarrow\mathrmbf{Gph}$. Such a channel defines
a direct flow operator
$\mathrmbfit{dir}_{\mathrmbf{I}}(\gamma):\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})\rightarrow\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(C))$
and an inverse flow operator
$\mathrmbfit{inv}_{\mathrmbf{I}}(\gamma):\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(C))\rightarrow\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$.
For any two covering channels ${\langle{\gamma^{\prime},C^{\prime}}\rangle}$
and ${\langle{\gamma,C}\rangle}$ over the same distributed system
$\mathcal{G}$, a refinement
$H\colon{\langle{\gamma^{\prime},C^{\prime}}\rangle}\rightarrow{\langle{\gamma,C}\rangle}$
is a graph morphism between cores $H\colon C^{\prime}\rightarrow C$ that
respects the part-whole relationships of the two channels:
$\gamma^{\prime}_{n}\circ H=\gamma_{n}$ for $n\in\mathrmbf{I}$. In such a
situation, we say the channel ${\langle{\gamma^{\prime},C^{\prime}}\rangle}$
is a refinement of the channel ${\langle{\gamma,C}\rangle}$. A channel
${\langle{\iota,\coprod\mathcal{G}}\rangle}$ is a minimal
cover212121Information flow terminology [BS]. or optimal(ly refined covering)
channel of a distributed system $\mathcal{G}$ when it covers $\mathcal{G}$ and
for any other covering channel ${\langle{\gamma,C}\rangle}$ there is a unique
refinement $[\gamma,C]\colon\coprod\mathcal{G}\rightarrow C$ from
${\langle{\iota,\coprod\mathcal{G}}\rangle}$ to ${\langle{\gamma,C}\rangle}$.

####  4.3.5. System flow

In order to represent an information system
$\mathcal{S}=\\{\mathcal{S}_{n}\xrightarrow{\mathcal{S}_{e}}\mathcal{S}_{m}\\}$
as a single olog $\coprod\mathcal{S}$, called the fusion of $\mathcal{S}$,
with part-whole relations $\mathcal{S}_{n}\rightarrow\coprod\mathcal{S}$, we
follow the colimit theorem of [TBG] by recognizing the following three
properties.

  * •

Optimal channels exist for any distributed system $\mathcal{G}$.

  * •

$\mathrmbfit{fbr}(G)$ is a complete preorder for any graph $G$, loosely called
a “lattice”.

  * •

For any graph morphism $H\colon G_{1}\rightarrow G_{2}$, direct and inverse
flow are adjoint monotonic functions
${\langle{\mathrmbfit{dir}(H),\mathrmbfit{inv}(H)}\rangle}\colon\mathrmbfit{fbr}(G_{1})\rightarrow\mathrmbfit{fbr}(G_{2})$.

Let $\mathcal{G}\in\mathrmbf{Dist}(\mathrmbf{I})$ be a distributed system of
shape $\mathrmbf{I}$ with optimal channel
${\langle{\iota,\coprod\mathcal{G}}\rangle}$. The optimal core
$\widehat{\mathcal{G}}=\coprod\mathcal{G}$ is called the sum of the
distributed system $\mathcal{G}$, and the optimal channel components (graph
morphisms) $\\{\iota_{n}\colon G_{n}\rightarrow\coprod\mathcal{G}\mid
n\in\mathrmbf{I}\\}$ are called flow links. There is a direct system flow
monotonic function (see Figure 1)
$\mathrmbfit{dir}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}=\mathrmbfit{dir}_{\mathrmbf{I}}(\iota)\cdot{\vee^{\mathrmbf{I}}_{\hat{\mathcal{G}}}}\colon\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})\rightarrow\mathrmbfit{fbr}(\widehat{\mathcal{G}})$.
Direct system flow has two steps: (i) direct (fixed shape) system flow of an
information system along the optimal channel
($\mathrmbf{Dist}(\mathrmbf{I})$-morphism)
$\iota\colon\mathcal{G}\Rightarrow\Delta(\widehat{\mathcal{G}})$ and (ii)
lattice join combining the contributions of the parts into a whole. In the
opposite direction, there is an inverse system flow monotonic function (see
Figure 1)
$\mathrmbfit{inv}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}={\Delta^{\mathrmbf{I}}_{\hat{\mathcal{G}}}}\cdot\mathrmbfit{inv}_{\mathrmbf{I}}(\iota)\colon\mathrmbfit{fbr}(\widehat{\mathcal{G}})\rightarrow\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$.
Inverse system flow has two steps: (i) mapping an olog with core language
$\widehat{\mathcal{G}}$ to a constant information system over
$\Delta(\widehat{\mathcal{G}})$ with shape $\mathrmbf{I}$ by distributing the
olog to the locations $n\in\mathrmbf{I}$, and (ii) inverse (fixed shape)
system flow of this constant information system back along the optimal channel
$\iota\colon\mathcal{G}\Rightarrow\Delta(\widehat{\mathcal{G}})$. Direct
system flow is adjoint to inverse system flow
${\langle{\mathrmbfit{dir}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}\dashv\mathrmbfit{inv}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}}\rangle}\colon\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})\rightarrow\mathrmbfit{fbr}(\widehat{\mathcal{G}})$,
since the composition components are adjoint. For any distributed system
$\mathcal{G}\in\mathrmbf{Dist}(\mathrmbf{I})$ with optimal core
$\widehat{\mathcal{G}}=\coprod\mathcal{G}$, any information system
$\mathcal{S}\in\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$, and any olog
$\widehat{\mathcal{S}}\in\mathrmbfit{fbr}(\widehat{\mathcal{G}})$, entailment
satisfies the following axioms.

(direct flow) |  If $E_{n}$ entails the equation $(f=_{G_{n}}f^{\prime})\colon i\rightarrow j$, then $\mathrmbfit{dir}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}(\mathcal{S})$ entails the equation $(\iota_{n}^{\ast}(f)=_{\hat{\mathcal{G}}}\iota_{n}^{\ast}(f^{\prime}))\colon\iota_{n}(i)\rightarrow\iota_{n}(j)$ for any $n\in\mathrmbf{I}$.
---|---
(inverse flow) |  If $\widehat{\mathcal{S}}$ entails the equation $(\iota_{n}^{\ast}(f)=_{\hat{\mathcal{G}}}\iota_{n}^{\ast}(f^{\prime}))\colon\iota_{n}(i)\rightarrow\iota_{n}(j)$, then $\mathrmbfit{inv}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}(\widehat{\mathcal{S}})_{n}$ entails the equation $(f=_{G_{n}}f^{\prime})\colon i\rightarrow j$ for any $n\in\mathrmbf{I}$.

These are converted to inference rules in Table 1.

$\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$$\mathrmbfit{info}_{\mathrmbf{I}}(\Delta(\widehat{\mathcal{G}}))$$\mathrmbfit{fbr}(\widehat{\mathcal{G}})$$\coprod\mathcal{S}$$\ni$$\mathcal{S}$$\in$$\in$$\mathcal{S}^{\scriptscriptstyle\blacklozenge}$$\mathrmbfit{dir}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}$$\mathrmbfit{inv}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}$$\mathrmbfit{dir}_{\mathrmbf{I}}(\iota)$$\mathrmbfit{inv}_{\mathrmbf{I}}(\iota)$$\vee^{\mathrmbf{I}}_{\hat{\mathcal{G}}}$$\Delta^{\mathrmbf{I}}_{\hat{\mathcal{G}}}$$\dashv$$\dashv$
Figure 1. System Flow

Information flow can be used to compute the fusion olog for an information
system and to define the consequence of an information system. Fusion is
direct system flow, and consequence is the composition of direct and inverse
system flow. Let $\mathcal{S}\in\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$
be any information system. The fusion
$\coprod\mathcal{S}=\mathrmbfit{dir}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}(\mathcal{S})={\langle{\coprod\mathcal{G},\bigvee_{n\in\mathrmbf{I}}\mathrmbfit{dir}(\iota_{n})(E_{n})}\rangle}\in\mathrmbfit{fbr}(\widehat{\mathcal{G}})$
is an olog that represents the whole system in a centralized fashion
[Ken2],[Ken3]. The consequence
$\mathcal{S}^{\scriptscriptstyle\blacklozenge}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}=\mathrmbfit{inv}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}(\mathrmbfit{dir}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}(\mathcal{S}))=\mathrmbfit{inv}_{{\langle{\mathrmbf{I},\mathcal{G}}\rangle}}(\coprod\mathcal{S})=\\{\mathrmbfit{inv}(\iota_{n})(\coprod\mathcal{S})\mid
n\in\mathrmbf{I}\\}\in\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$ is an
information system that represents the whole system in a distributed fashion
[Ken3]. It is inverse flow of the fusion olog along the optimal channel,
transfering the entailed facts of the whole system to the component parts.

The consequence operator $(\mbox{-})^{\scriptscriptstyle\blacklozenge}$, which
is defined on information systems, is a closure operator on the complete
preorder $\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$, and by taking the
coproduct it is a closure operator on the complete preorder
$\mathrmbf{Info}(\mathrmbf{I})=\coprod_{\mathcal{G}\in\mathrmbf{Dist}(\mathrmbf{I})}\mathrmbfit{info}_{\mathrmbf{I}}(\mathcal{G})$
: (increasing) $\mathcal{S}\geq\mathcal{S}^{\scriptscriptstyle\blacklozenge}$,
(monotonic) $\mathcal{S}\geq\mathcal{S}^{\prime}$ implies
$\mathcal{S}^{\scriptscriptstyle\blacklozenge}\geq\mathcal{S}^{\prime\scriptscriptstyle\blacklozenge}$
and (idempotent)
$\mathcal{S}^{\scriptscriptstyle\blacklozenge\blacklozenge}=\mathcal{S}^{\scriptscriptstyle\blacklozenge}$.
222222By allowing system shape to vary, channels can be generalized to
morphisms of distributed systems. Then a notion of relative fusion (direct
system flow) can be defined in terms of left Kan extension, and a notion of
relative system consequence can be defined as the composition of direct
followed by inverse system flow. Pointwise entailment order $\leq$ on
$\mathrmbf{Info}(\mathrmbf{I})$ is only a preliminary order, since it does not
incorporate interactions between system component parts. System entailment
order $\preceq$ on $\mathrmbf{Info}(\mathrmbf{I})$ is defined by
$\mathcal{S}_{1}\preceq\mathcal{S}_{2}$ when
$\mathcal{S}_{1}^{\scriptscriptstyle\blacklozenge}\leq\mathcal{S}_{2}^{\scriptscriptstyle\blacklozenge}$;
equivalently,
$\mathcal{S}_{1}^{\scriptscriptstyle\blacklozenge}\leq\mathcal{S}_{2}$.
Pointwise order is stronger than system entailment order:
$\mathcal{S}_{1}\leq\mathcal{S}_{2}$ implies
$\mathcal{S}_{1}\preceq\mathcal{S}_{2}$. This is a specialization-
generalization order. Any information system $\mathcal{S}$ is entailment
equivalent to its consequence
$\mathcal{S}\cong\mathcal{S}^{\scriptscriptstyle\blacklozenge}$. An
information system $\mathcal{S}$ is closed when it is equal to its consequence
$\mathcal{S}=\mathcal{S}^{\scriptscriptstyle\blacklozenge}$.

The whole effect of taking the system consequence may be greater than the sum
of its parts, in the sense that
$\mathcal{S}_{n}\geq_{n}\mathcal{S}_{n}^{{\scriptscriptstyle\blacklozenge}_{\iota_{n}}}\geq_{n}\bigvee_{m}\mathrmbfit{inv}(\iota_{n})(\mathrmbfit{dir}(\iota_{m})(\mathcal{S}_{m}))\geq_{n}\mathcal{S}^{\scriptscriptstyle\blacklozenge}_{n}$
for any $n\in\mathrmbf{I}$, since separate parts may have a productive
interaction at the channel core. A final part of an information system is a
part with no non-trivial constraint links from it. (The graphical subsystem
beneath) nonfinal parts are necessary for the alignment of information
systems, resulting in the equivalencing of types and aspects through
quotienting. However, because of the covering condition
$\iota_{n}=G_{e}\circ\iota_{m}$ and the entailment order
$\mathrmbfit{dir}(G_{e})(E_{n})\geq_{m}E_{m}$ for constraint links
$\mathcal{S}_{e}\colon\mathcal{S}_{n}\rightarrow\mathcal{S}_{m}$, only the
fact(ual) content of final parts of information systems are necessary to
compute the system fusion and consequence.

equivalence: | (reflexive) |  | $(f=_{G}f)\colon i\rightarrow j$
---
| (symmetric) |  |  $(f_{1}=_{G}f_{2})\colon i\rightarrow j$
---
$(f_{2}=_{G}f_{1})\colon i\rightarrow j$
| (transitive) |  |  $(f_{1}=_{G}f_{2})\colon i\rightarrow j$, $(f_{2}=_{G}f_{3})\colon i\rightarrow j$
---
$(f_{1}=_{G}f_{3})\colon i\rightarrow j$
algebra: | (compositional) |  |  $(f_{1}=_{G}f_{2})\colon i\rightarrow j$, $(g_{1}=_{G}g_{2})\colon j\rightarrow k$
---
$(f_{1}{\;;\;}g_{1}=_{G}f_{2}{\;;\;}g_{2})\colon i\rightarrow k$
| (bi-closed) |  |  $(g_{1}=_{G}g_{2})\colon j\rightarrow k$
---
$(f{\,;\,}g_{1}=_{G}f{\;;\;}g_{2})\colon i\rightarrow k$,
$(g_{1}{\;;\;}h=_{G}g_{2}{\,;\,}h)\colon j\rightarrow l$
morphic flow: | (direct) |  |  $(f_{1}=_{G_{1}}f^{\prime}_{1})\colon i_{1}\rightarrow j_{1}$
---
$(H^{\ast}(f_{1})=_{G_{2}}H^{\ast}(f^{\prime}_{1}))\colon H(i_{1})\rightarrow
H(j_{1})$
| (inverse) |  |  $(H^{\ast}(f_{1})=_{G_{2}}H^{\ast}(f^{\prime}_{1}))\colon H(i_{1})\rightarrow H(j_{1})$
---
$(f_{1}=_{G_{1}}f^{\prime}_{1})\colon i_{1}\rightarrow j_{1}$
system flow: | (direct) |  |  $(f=_{G_{n}}f^{\prime})\colon i\rightarrow j$
---
$(\iota_{n}^{\ast}(f)=_{\hat{\mathcal{G}}}\iota_{n}^{\ast}(f^{\prime}))\colon\iota_{n}(i)\rightarrow\iota_{n}(j)$
| (inverse) |  |  $(\iota_{n}^{\ast}(f)=_{\hat{\mathcal{G}}}\iota_{n}^{\ast}(f^{\prime}))\colon\iota_{n}(i)\rightarrow\iota_{n}(j)$
---
$(f=_{G_{n}}f^{\prime})\colon i\rightarrow j$
Table 1. Inference Rules

####  4.3.6. General examples

Here are some examples of system fusion/consequence.

  * •

An information system $\mathcal{S}$ with a constant underlying distributed
system, $G_{i}=G$ for all $n\in\mathrmbf{I}$, gathers together all the
component parts of the information system and forms their consequence. It has
identity flow links $\\{\iota_{n}=\mathrmit{id}_{G}\colon G\rightarrow
G=\coprod\mathcal{G}\mid n\in\mathrmbf{I}\\}$, component join fusion
$\coprod\mathcal{S}=\bigvee_{n\in\mathrmbf{I}}\mathcal{S}_{n}={\langle{G,\bigcup_{n\in\mathrmbf{I}}E_{n}}\rangle}$,
and constant system consequence
$\mathcal{S}^{\scriptscriptstyle\blacklozenge}_{n}=\left(\bigvee_{n^{\prime}\in\mathrmbf{I}}\mathcal{S}_{n^{\prime}}\right)^{\scriptscriptstyle\bullet}$
for all $n\in\mathrmbf{I}$.

  * •

A discrete information system
$\mathcal{S}=\\{\mathcal{S}_{n}={\langle{G_{n},E_{n}}\rangle}\mid
n\in\mathrmbf{I}\\}$ with no constraint links
$G_{e}\colon\mathcal{S}_{n}\rightarrow\mathcal{S}_{m}$ for $n\neq m$, has
coproduct injection flow links $\iota_{n}\colon
G_{n}\rightarrow\mbox{\Large$+$}_{n\in\mathrmbf{I}}\,G_{n}$, non-restricting
fusion, and inverse flow projecting back to individual component consequence
$\mathcal{S}^{\scriptscriptstyle\blacklozenge}_{n}=\mathcal{S}_{n}^{\scriptscriptstyle\bullet}$
for all $n\in\mathrmbf{I}$. No alignment (constraint) links means no
interaction.

  * •

An information system
$\mathcal{S}=\\{\mathcal{S}_{1}\xleftarrow{H_{1}}\mathcal{S}\xrightarrow{H_{2}}\mathcal{S}_{2}\\}$
consisting of a single common ground $\mathcal{S}={\langle{G,E}\rangle}$
between two component ologs $\mathcal{S}_{1}={\langle{G_{1},E_{1}}\rangle}$
and $\mathcal{S}_{2}={\langle{G_{2},E_{2}}\rangle}$, with underlying
distributed system (span)
$\mathcal{G}=\\{G_{1}\xleftarrow{H_{1}}G\xrightarrow{H_{2}}G_{2}\\}$, has
pushout injection flow links
$G_{1}\xrightarrow{\iota_{1}}\coprod\mathcal{G}\xleftarrow{\iota_{2}}G_{2}$,
direct image union fusion
$\coprod\mathcal{S}={\langle{\coprod\mathcal{G},\mathrmbfit{dir}(\iota_{1})(E_{1})\cup\mathrmbfit{dir}(\iota_{2})(E_{2})}\rangle}$,
and system consequence components
$\mathcal{S}^{\scriptscriptstyle\blacklozenge}_{n}={\langle{G_{n},\mathrmbfit{inv}(\iota_{n})(\mathrmbfit{dir}(\iota_{1})(E_{1})\cup\mathrmbfit{dir}(\iota_{2})(E_{2}))}\rangle}$
for $n=1,2$. The flow links will quotient any types and aspects that are
connected through the common ground allowing for the approprate interaction in
the fusion consequence
$(\mathrmbfit{dir}(\iota_{1})(E_{1})\cup\mathrmbfit{dir}(\iota_{2})(E_{2}))^{\scriptscriptstyle\bullet}$,
then the inverse flow will reconnect this with the component types and
aspects.

###  4.4. Conceptual graphs

The conceptual graph formalism (CG) for knowledge representation [Sow2], was
initially formulated to represent database systems (DBS), but is now used in
natural language processing (NLP) and first-order logic (FOL). Verbs in NLP
can often be represented relationally by star(-shaped conceptual) graphs. For
example, the sentence “John is going to Boston by bus” might be represented by
the conceptual graph

(131)

In a sentence of natural language, thematic roles are semantic descriptions of
the way (the entities described by) a noun phrase functions with respect to
(the action of) the verb. These entities are the participants in the occurrent
expressed by the verb. For the action of ‘going’ in the above sentence there
are three participants and hence three thematic roles. ‘John’ plays the role
of the agent of the action, a ‘Bus’ is the instrument used in the action and
‘Boston’ is the destination of the action. Translations using thematic roles
can be used to align two ontologies with respect to a common ground. A CG-
style translation of conceptual graph (131) would replace the verb relation
‘going’ with a concept ‘Go’ and replace the edges that form the signature of
the ‘going’ relation with binary relations for the three roles ‘agent’,
‘instrument’ and ‘destination’.

(138)

However, the case relations that semantically describe the thematic roles
should be viewed as functional in nature; that is, for any instance of the
action of a sentence’s verb there is a unique entity described by a noun
phrase of the sentence. When this semantics is respected, the translation to
thematic roles becomes a process of “linearization”, which is best described
abstractly as: (1) the identification of relation types with entity types, (2)
the translation of a sorted multiarity relation to a span of functions, one
function for each role, and (3) the functional interpretation of thematic
roles.

The Olog formalism, which also represents DBS and NLP, is a version of
equational logic. Both the Olog and CG formalisms were designed as graphical
representations. However, the CG formalism is binary and relational, whereas
the Olog formalism is unary and functional. The CG formalism is binary since
it has two kinds of type, concepts and relations; it is relational in the way
it interprets edges. The Olog formalism is unary since it has only one kind of
type, the abstract concept; it is functional in the way it interprets aspects
(edges). However, much of the semantics of the CG formalism can be transformed
to the Olog formalism by the process of linearization232323The linearization
process works for any binary/relational knowledge representation, such as CGs,
entity-relationship data modelling [JRW], relational database systems [Ken5]
or the Information Flow Framework [IFF1]. In the entity-relationship data
modelling, $n$-ary relationship links are replaced by $n$-ary spans of aspects
and attributes are included as types., thereby gaining in efficiency and
conciseness. For example, conceptual graph (131) can be linearized to the olog
graph242424$\ulcorner$1$\urcorner$ is the universal type to which all types
have a unique aspect.

(143)

Since olog aspects are interpreted functionally, the functional nature of
thematic roles is respected. In this manner, the olog formalism could be used
to replace the CG representation of ontologies. For example, a community
(acting as an individual) could build its ontology $\mathcal{C}$ from ground
up by aligning it with some top-level reference ontology $\mathcal{T}$ (such
as in the appendix of [Sow2]), thereby importing some formal semantics from
$\mathcal{T}$. The following fragment demonstrates how this works.

Assume that ontology $\mathcal{T}$ contains the concept of “spatial process”
as represented by the general concept type $\ulcorner$Spatial-
Process$\urcorner$ with aspects $\textnormal{$\ulcorner$Spatial-
Process$\urcorner$}\xrightarrow{\text{agent}}\textnormal{$\ulcorner$Agent$\urcorner$}$,
$\textnormal{$\ulcorner$Spatial-
Process$\urcorner$}\xrightarrow{\text{inst}}\textnormal{$\ulcorner$Vehicle$\urcorner$}$
and $\textnormal{$\ulcorner$Spatial-
Process$\urcorner$}\xrightarrow{\text{dest}}\textnormal{$\ulcorner$Location$\urcorner$}$.
At some stage assume that the community ontology $\mathcal{C}$ has specified
the concept type orderings
$\textnormal{$\ulcorner$Person$\urcorner$}\leq\textnormal{$\ulcorner$Agent$\urcorner$}$,
$\textnormal{$\ulcorner$Bus$\urcorner$}\leq\textnormal{$\ulcorner$Vehicle$\urcorner$}$
and
$\textnormal{$\ulcorner$City$\urcorner$}\leq\textnormal{$\ulcorner$Location$\urcorner$}$
with corresponding injective aspects
$\textnormal{$\ulcorner$Person$\urcorner$}\xrightarrow{\text{is}}\textnormal{$\ulcorner$Agent$\urcorner$}$,
$\textnormal{$\ulcorner$Bus$\urcorner$}\xrightarrow{\text{is}}\textnormal{$\ulcorner$Vehicle$\urcorner$}$
and
$\textnormal{$\ulcorner$City$\urcorner$}\xrightarrow{\text{is}}\textnormal{$\ulcorner$Location$\urcorner$}$.
At the next stage it could define a concept type $\ulcorner$C$\urcorner$ with
aspects
$\textnormal{$\ulcorner$C$\urcorner$}\xrightarrow{\text{person}}\textnormal{$\ulcorner$Person$\urcorner$}$,
$\textnormal{$\ulcorner$C$\urcorner$}\xrightarrow{\text{bus}}\textnormal{$\ulcorner$Bus$\urcorner$}$
and
$\textnormal{$\ulcorner$C$\urcorner$}\xrightarrow{\text{city}}\textnormal{$\ulcorner$City$\urcorner$}$,
and link it with the reference ontology concept $\ulcorner$Spatial-
Process$\urcorner$ by specifying a connecting aspect
$\textnormal{$\ulcorner$C$\urcorner$}\xrightarrow{\text{process}}\textnormal{$\ulcorner$Spatial-
Process$\urcorner$}$ and asserting the facts
‘$\mbox{person}{\;;\;}\mbox{is}=\mbox{process}{\;;\;}\mbox{agent}$’,
‘$\mbox{bus}{\;;\;}\mbox{is}=\mbox{process}{\;;\;}\mbox{vehicle}$’ and
‘$\mbox{city}{\;;\;}\mbox{is}=\mbox{process}{\;;\;}\mbox{location}$’.252525The
symbol ‘;’ denotes concatenation or formal composition. In the more expressive
ologs with joins (Section 5), the process concept of “going to city by bus”
can then be defined as the pullback of the “spatial process” concept: here,
the concept type $\ulcorner$Go$\urcorner$ with aspects
$\textnormal{$\ulcorner$Go$\urcorner$}\xrightarrow{\text{person}}\textnormal{$\ulcorner$Person$\urcorner$}$,
$\textnormal{$\ulcorner$Go$\urcorner$}\xrightarrow{\text{bus}}\textnormal{$\ulcorner$Bus$\urcorner$}$
and
$\textnormal{$\ulcorner$Go$\urcorner$}\xrightarrow{\text{city}}\textnormal{$\ulcorner$City$\urcorner$}$
is pulled back along the above injective aspects, resulting in the injective
aspect
$\textnormal{$\ulcorner$Go$\urcorner$}\xrightarrow{\text{is}}\textnormal{$\ulcorner$Spatial-
Process$\urcorner$}$ with corresponding concept type ordering
$\textnormal{$\ulcorner$Go$\urcorner$}\leq\textnormal{$\ulcorner$Spatial-
Process$\urcorner$}$. As a result, the concept $\ulcorner$C$\urcorner$ has the
new mediating aspect $\mbox{C}\xrightarrow{\text{going}}\mbox{Go}$, which
satisfies the fact ‘$\mbox{going}{\;;\;}\mbox{is}=\mbox{process}$’. In this
manner the community ontology $\mathcal{C}$ has been enlarged.

$\mathcal{C}$$\mathcal{T}$CpersonbuscitygoingprocessGopersonbuscityis$\textstyle{{\cdot}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$Spatial-
Processagentinstdest$\textstyle{{\cdot}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$PersonisBusisCityis$\textstyle{{\cdot}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$AgentVehicleLocation
$\displaystyle\overset{\underbrace{\rule{300.0pt}{0.0pt}}}{\mbox{\Large\rule{0.0pt}{16.0pt}$\mathcal{P}$}}$

We assume that community ontology $\mathcal{C}$ and reference ontology
$\mathcal{T}$ are combined into a portal ontology $\mathcal{P}$ with portal
link $\mathcal{C}\xrightarrow{P}\mathcal{P}$ and alignment link
$\mathcal{T}\xrightarrow{A}\mathcal{P}$. If some other ontology
$\mathcal{C}^{\prime}$ is built up and aligned in the same fashion, then
$\mathcal{T}$ is being used as a common ground, and we have a ‘W’-shaped
information system

(148)

with portals $\mathcal{P}$ and $\mathcal{P}^{\prime}$ being the final parts.
This ‘W’-shaped information system uses the sketch institution Sk for ologs.
It can be compared to the ‘W’-shaped information system in [Ken1], which uses
the information flow IF institution for (local) logics.

##  5\. More expressive ologs I

In this section and the next (5 and 6) we will introduce limits and colimits
within the context of ologs. These will allow authors to build ologs that are
quite expressive. For example we can declare one type to be the union or
intersection of other types. We do not assume mathematical knowledge beyond
that of sets and functions, which were loosely defined in Section 2.2.
However, the reader may benefit by consulting a reference on category theory,
such as [Awo].

The basic ologs discussed in previous sections are based on the mathematical
notion of categories, whereas the olog presentation language we will discuss
in this section and the next are based on general sketches (see [Mak]). The
difference is in what can be expressed: in basic ologs we can declare types,
aspects, and facts, whereas in general ologs we can express ideas like
products and sums, as we will see below.

We will begin by discussing layouts, which will be represented categorically
by “finite limits”. As usual, the english terminology (layout) is not precise
enough to express the notion we mean it to express (limit). Intuitively, a
limit can be thought of as a system: it is a collection of units, each of a
specific type, such that these units have compatible aspects. These will
include types like $\ulcorner$a man and a woman with the same last
name$\urcorner$. In Section 6 we will discuss groupings, which will be
represented by colimits. These will include types like $\ulcorner$a thing that
is either a pear or a watermelon$\urcorner$.

###  5.1. Layouts

A dictionary might define the word layout as something like “a structured
arrangement of items within certain limits; a plan for such arrangement.” In
other words, we can lay out or specify the need for a set of parts, each of a
given type, such that the parts fit together well. This idea roughly
corresponds to the notion of limits in category theory, especially limits in
the category of sets. Given a diagram of sets and functions, its limit is the
set of ways to accordingly choose one element from each. For example, we could
have a type $\ulcorner$a car and a driver$\urcorner$, which category-
theoretically is a product, but which we are calling a “layout” — a compound
type whose parts are “laid out.” Of course, the term layout is insufficient to
express the precise meaning of limits, but it will have to do for now. To
understand limits, one really only need understand pullbacks and products.
These will be the subjects of Sections 5.2 and 5.3, or one can see [Awo] for
more details.

###  5.2. Pullbacks

Given three objects and two arrows arranged as to the left, the pullback is
the commutative square to the right:

Given:
$\textstyle{C\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\textstyle{D}$
the pullback is drawn:
$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{\prime}}$$\scriptstyle{g^{\prime}}$$\textstyle{C\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\textstyle{D.}$

We write $A=B\times_{D}C$ and say “$A$ is the pullback of $B$ and $C$ over
$D$.” The question is, what does it signify? We will begin with some examples
and then give a precise definition.

######  Example 5.2.1.

We will now give four examples to motivate the definition of pullback. In the
first example, (157), both $B$ and $C$ will be subtypes of $D$, and in such
cases the pullback will be their intersection. In the next two examples (166
and 175), only $B$ will be a subtype of $D$, and in such cases the pullback
will be the “corresponding subtype of $C$” (as should make sense upon
inspection). In the last example (184), neither $B$ nor $C$ will be a subtype
of $D$. In each line below, the pullback of the diagram to the left is the
diagram to the right. The reader should think of the left-hand olog as a kind
of problem to which the new box $A$ in the right-hand olog is a solution.

(157) $\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{\parbox{50.58878pt}{\raggedright a loyal
customer\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{\parbox{50.58878pt}{\raggedright a wealthy
customer\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{a customer}}}}$ $\textstyle{\stackrel{{\scriptstyle
A=B\times_{D}C}}{{\framebox{\parbox{65.04256pt}{\raggedright a customer that
is wealthy and
loyal\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$isis$\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{\parbox{50.58878pt}{\raggedright a loyal
customer\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{\parbox{50.58878pt}{\raggedright a wealthy
customer\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{a customer}}}}$ (166) $\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{blue}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{a
person}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$ has as
favorite color $\textstyle{\stackrel{{\scriptstyle D}}{{\framebox{a color}}}}$
$\textstyle{\stackrel{{\scriptstyle
A=B\times_{D}C}}{{\framebox{\parbox{65.04256pt}{\raggedright a person whose
favorite color is
blue\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is
has as favorite color $\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{blue}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{a
person}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$ has as
favorite color $\textstyle{\stackrel{{\scriptstyle D}}{{\framebox{a color}}}}$
(175) $\textstyle{\stackrel{{\scriptstyle C}}{{\framebox{a
woman}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{a dog}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
has as owner $\textstyle{\stackrel{{\scriptstyle D}}{{\framebox{a person}}}}$
$\textstyle{\stackrel{{\scriptstyle
A=B\times_{D}C}}{{\framebox{\parbox{65.04256pt}{\raggedright a dog whose owner
is a
woman\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is
has as owner $\textstyle{\stackrel{{\scriptstyle C}}{{\framebox{a
woman}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{a dog}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
has as owner $\textstyle{\stackrel{{\scriptstyle D}}{{\framebox{a person}}}}$
(184) $\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{\parbox{50.58878pt}{\raggedright a piece of
furniture\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{\parbox{50.58878pt}{\raggedright a space in our
house\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has$\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{a width}}}}$ $\textstyle{\stackrel{{\scriptstyle
A=B\times_{D}C}}{{\framebox{\parbox{79.49744pt}{\raggedright a pair $(f,s)$
where $f$ is a piece of furniture and $s$ is a space in our house, and where
$f$ and $s$ have the same
width\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$s$$f$$\textstyle{\stackrel{{\scriptstyle
C}}{{\framebox{\parbox{50.58878pt}{\raggedright a piece of
furniture\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{\parbox{50.58878pt}{\raggedright a space in our
house\@add@raggedright}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has$\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{a width}}}}$

See Example 5.2.3 for a justification of these, in light of Definition 5.2.2.

The following is the definition of pullbacks in the category of sets. For an
olog, the instance data are given by sets (at least in this paper, see Section
3), so this definition suffices for now. See [Awo] for more details on
pullbacks.

######  Definition 5.2.2.

Let $B,C,$ and $D$ be sets, and let $f\colon B\rightarrow D$ and $g\colon
C\rightarrow D$ be functions. The pullback of
$B\xrightarrow{f}D\xleftarrow{g}C$, denoted $B\times_{D}C$, is defined to be
the set

$B\times_{D}C:=\\{(b,c)\;|\;b\in B,c\in C,\textnormal{ and }f(b)=g(c)\\}$

together with the obvious maps $B\times_{D}C\rightarrow B$ and
$B\times_{D}C\rightarrow C$, which send an element $(b,c)$ to $b$ and to $c$,
respectively. In other words, the pullback of
$B\xrightarrow{f}D\xleftarrow{g}C$ is a commutative square

$\textstyle{B\times_{D}C\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{C\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\textstyle{D.}$

######  Example 5.2.3.

In Example 5.2.1 we gave four examples of pullbacks. For each, we will
consider $B\xrightarrow{f}D\xleftarrow{g}C$ to be sets and functions as in
Definition 5.2.2 and explain how the set $A$ follows that definition, i.e. how
its label fits with the set $B\times_{D}C=\\{(b,c)\;|\;b\in B,c\in
C,\textnormal{ and }f(b)=g(c)\\}$.

In the case of (157), the set $B\times_{D}C$ should consist of pairs $(w,l)$
where $w$ is a wealthy customer, $l$ is a loyal customer, and $w$ is equal to
$l$ (as customers). But if $w$ and $l$ are the same customer then $(w,l)$ is
just a customer that is both wealthy and loyal, not two different customers.
In other words, an instance of the pullback is a customer that is both loyal
and wealthy, so the label of $A$ fits.

In the case of (166), the set $B\times_{D}C$ should consist of pairs $(p,b)$
where $p$ is a person, $b$ is the color blue, and the favorite color of $p$ is
equal to $b$ (as colors). In other words, it is a person whose favorite color
is blue, so the label of $A$ fits. If desired, one could instead label $A$
with $\ulcorner$a pair $(p,b)$ where $p$ is a person, $b$ is blue, and the
favorite color of $p$ is $b$$\urcorner$.

In the case of (175), the set $B\times_{D}C$ should consist of pairs $(d,w)$
where $d$ is a dog, $w$ is a woman, and the owner of $d$ is equal to $w$ (as
people). In other words, it is a dog whose owner is a woman, so the label of
$A$ fits. If desired, one could instead label $A$ with $\ulcorner$a pair
$(d,w)$ where $d$ is a dog, $w$ is a woman, and the owner of $d$ is
$w$$\urcorner$.

In the case of (184), the set $B\times_{D}C$ should consist of pairs $(f,s)$
where $f$ is a piece of furniture, $s$ is a space in our house, and the width
of $f$ is equal to the width of $s$. This is fits perfectly with the label of
$A$.

####  5.2.4. Using pullbacks to classify

To distinguish between two things, one must find a common aspect of the two
things for which they have differing results. For example, a pen is different
from a pencil in that they both use some material to write (a common aspect),
but the two materials they use are different. Thus the material which a
writing implement uses is an aspect of writing implements, and this aspect
serves to segregate or classify them. We can think of three such writing-
materials: graphite, ink, and pigment-wax. For each, we will make a layout in
the olog below:

|  |  |
---|---|---|---
$\textstyle{\stackrel{{\scriptstyle
A_{1}=B\times_{D}C_{1}}}{{\framebox{\parbox{72.26999pt}{a writing implement
that uses
graphite}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$usesis$\textstyle{\stackrel{{\scriptstyle
C_{1}}}{{\framebox{graphite}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
A_{2}=B\times_{D}C_{2}}}{{\framebox{\parbox{72.26999pt}{a writing implement
that uses
ink}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$usesis$\textstyle{\stackrel{{\scriptstyle
C_{2}}}{{\framebox{ink}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
A_{3}=B\times_{D}C_{3}}}{{\framebox{\parbox{72.26999pt}{a writing implement
that uses pigment-
wax}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$usesis$\textstyle{\stackrel{{\scriptstyle
C_{3}}}{{\framebox{pigment-
wax}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$is$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{a writing
implement}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$uses$\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{a writing material}}}}$

One could also replace the label of box $A_{1}$ with “a pencil”, the label of
box $A_{2}$ with “a pen”, and the label of box $A_{3}$ with “a crayon”; in so
doing, the layouts at the top would define a pencil, a pen, and a crayon to be
a writing implement that uses respectively graphite, ink, and pigment-wax.

####  5.2.5. Building pullbacks on pullbacks

There is a theorem in category theory which states the following. Suppose
given two commutative squares

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\lrcorner}$$\textstyle{5\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{6}$

such that the right-hand square (3,4,5,6) is a pullback. It follows that if
the left-hand square (1,2,3,4) is a pullback then so is the big rectangle
(1,2,5,6). It also follows that if the big rectangle (1,2,5,6) is a pullback
then so is the left-hand square (1,2,3,4). This fact can be useful in
authoring ologs.

For example, the type $\ulcorner$a cellphone that has a bad battery$\urcorner$
is vague, but we can lay out precisely what it means using pullbacks:

$\textstyle{\stackrel{{\scriptstyle
A=B\times_{D}C}}{{\framebox{\parbox{72.26999pt}{a cellphone that has a bad
battery}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\stackrel{{\scriptstyle
C=D\times_{F}E}}{{\framebox{a bad
battery}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\stackrel{{\scriptstyle
E=F\times_{H}G}}{{\framebox{\parbox{36.135pt}{less than 1
hour}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\stackrel{{\scriptstyle
G}}{{\framebox{\parbox{36.135pt}{between 0 and
1}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\stackrel{{\scriptstyle
B}}{{\framebox{a
cellphone}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$has$\textstyle{\stackrel{{\scriptstyle
D}}{{\framebox{a
battery}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$ remains
charged for $\textstyle{\stackrel{{\scriptstyle
F}}{{\framebox{\parbox{43.36243pt}{a duration of
time}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$ in hours yields
$\textstyle{\stackrel{{\scriptstyle H}}{{\framebox{\parbox{43.36243pt}{a range
of numbers}}}}}$

The category-theoretic fact described above says that since $A=B\times_{D}C$
and $C=D\times_{F}E$, it follows that $A=B\times_{F}E$. That is, we can decuce
the definition “a cellphone that has a bad battery is defined as a cellphone
that has a battery which remains charged for less than one hour.” In other
words, $A=B\times_{F}E$.

###  5.3. Products

Given a set of types (boxes) in an olog, one can select one instance from
each. All the ways of doing just that comprise what is called the product of
these types. For example, if $A=\textnormal{$\ulcorner$a number between 1 and
10$\urcorner$}$ and $B=\textnormal{$\ulcorner$a letter between x and
z$\urcorner$}$, the product includes a total of 30 elements, including
$(4,z)$. We are ready for the definition.

######  Definition 5.3.1.

Given sets $A,B$, their product, denoted $A\times B$, is the set

$A\times B=\\{(a,b)\;|\;a\in A\textnormal{ and }b\in B\\}.$

There are two obvious projection maps $A\times B\rightarrow A$ and $A\times
B\rightarrow B$, sending the pair $(a,b)$ to $a$ and to $b$ respectively.

######  Example 5.3.2.