%%%%%
%%%%%  THIS FILE MUST BE CALLED information.tex
%%%%%

\documentstyle[basics,amssymbols,st]{article}

\renewcommand{\labelp}[1]{\label{#1}}
\newcommand{\EE}{{\cal E}}
\begin{document}


\section{The Structure of Information}
\label{section-simple-infons}
\label{section-basic-infons}
\label{sec.structure-of-information}

Situation Theory has its fair share of neologisms, the most inspired
of which is surely the term {\em infon}, coined by Keith Devlin.  An infon
is an item of information.  The term is intended to be as
neutral as possible with regard to the form in which the information is
represented. The common item of information separately conveyed by the
statements made in the following little conversation is an example of
an infon.

\begin{trivlist}
\item[] Raymond: (to Paul, displaying an omelette) I have cooked this for
you.
\item[] Paul: (proudly, to Delia) Raymond cooked this omelette for me.
\item[] Delia: (to Albert) The chef cooked the omelette for Paul.
\end{trivlist}

Of course, much more information can be gleaned about the situation from
each of these statements, but that it is one in which the two people,
Raymond and Paul, and an omelette stand in a certain relationship, that of
Raymond having cooked the omelette for Paul, is information expressed by all
three.  The very same information may also be represented by other means, in
a film, or a cartoon-strip, for example, or in the minds of Raymond, Paul,
Delia and even Albert.

The first goal of this chapter is to show how information of this simple
form is modelled. To specify the structure of the infon in the example, we
must say which individuals are involved and how they are related.
We shall abbreviate `Raymond' and `Paul' to `\ob{R}' and `\ob{P}', and
introduce the name `\ob{O}' to refer to the omelette.  We use
`\ob{cooked}' to name the relation which holds between a cook, a guest and a
dish just in case the the cook has cooked the dish for the guest.
The infon of our example, which we name `\ob{I},' is the information that
\ob{R},\ob{P}, and \ob{O} stand in the relation \ob{cooked}. The individuals
\ob{R}, \ob{P}, and \ob{O} are called {\em arguments} of the infon \ob{I},
and the relation \ob{cooked}, is called the {\em relation} of \ob{I}.

By specifying the relation and arguments of an infon we have done a lot
toward characterizing everything of informational significance, but not
quite all. Care must be taken to  distinguish the information that Raymond
cooked the omelette for Paul from the information that Paul cooked the
omelette for Raymond.  For this purpose, we require the concept of a {\em
role}. In any infon involving the relation \ob{cooked} there
are three roles to be filled: that of the cook, the guest and the dish. In
the present case, the cook is \ob{R}, the guest is \ob{P}, and the dish
is \ob{O}, but if it were claimed that Paul cooked the omelette for Raymond,
then the roles of cook and guest would be reversed.  We say that an
individual is an {\em argument} of an infon if it fills one of its roles.
For example, the omelette \ob{O} is an argument of the infon \ob{I} by
virtue of  filling the \ob{dish} role of \ob{I}'s relation \ob{cooked}.

We may capture these intuitions by supposing that there are two basic
ingredients determining the structure of \ob{I}: that of
\ob{cooked} being the relation of \ob{I}, and that of the
three individuals \ob{R}, \ob{P}, and \ob{O} filling the
three roles of \ob{I}, which we name \ob{cook}, \ob{guest}, and \ob{dish},
respectively.   We introduce the predicates $\Rel$ and $\Arg$ to
express these structural relations, writing  $\Rel(\ob{cooked},\ob{I})$
to mean that \ob{cooked} is the relation of \ob{I},
and $\Arg(\ob{O},\ob{dish},\ob{I})$ to mean that \ob{O}, the
omelette, fills the \ob{dish} role of our infon \ob{I}.

More generally, we may say that simple infons of the kind we have been
considering are `structured' by the two relations, $\Rel$ and $\Arg$.  The
first of these, $\Rel$, determines the relation of the infon and the other,
$\Arg$,  determines which arguments fill which roles.  In fact, we
{\em define} a `simple infon' to be anything which has a relation or an
argument.  Similarly, a  `relation' is anything which is a relation {\em of}
some infon, and a `role' is anything which is filled by an argument in an
infon.   In other words,

\begin{tabular}{ll}
$\si$ is a {\em (simple) infon} & if $\exists r$
$\Rel(r,\si)$ or $\exists a,i$ $\Arg(a,i,\si)$. \\
$r$ is a {\em relation} & if $\exists \si$
$\Rel(r,\si)$. \\
$r$ is a {\em role} & if $\exists a,\si$
$\Arg(a,i,\si)$. \\
\end{tabular}

These definitions form the basis of the abstract account of
the structure of information that we will develop throughout this section.
The approach is `abstract' because  we consider any structure in which the
predicates `$\Rel$' and `$\Arg$' are defined to be a candidate model for the
theory of information, with the derived predicates `relation', `role'
and `infon' interpreted according to the above definitions.
Our approach will be to isolate various axioms which describe the central
properties of the concept of an `infon', as it has been formulated in
Situation Theory, and so home in on those models that have been proposed
in the literature.

\subsection{Relational Structures}
In all foundational theories one must be very careful to distinguish between the
terminologies of the meta-theory and object-theory. Situation Theory is
no exception, and special difficulties arises with the word `relation'.
Before going further it will prove useful to make some preliminary
definitions concerning relational structures.
The following is slightly non-standard but enables us to avoid certain
ambiguities with our use of `relation' and similar words.

A {\em (relational) signature} is a function $\fun{\nu}{S}{N}$ from
a finite set $S$ to the set $N$ of positive integers. The elements of $S$ are
called {\em primitive relations} and the number $\nu(R)$ associated with a
primitive relation $R$ is a called its {\em arity}. A {\em relational structure}
$\goth{A}$ of signature $\nu$ consists of a class $\univ{A}$, called the {\em
universe} of $\goth{A}$, and for each primitive relation $R$, a class
$\ext{R}{\goth{A}}$ of finite sequences of elements of $\univ{A}$, each of
length $\nu(R)$, called the {\em extension} of $R$ 
in $\goth{A}$.\footnote{We allow relational
structures whose universe is a proper
class because models of Situation Theory are often very large. The exact
meaning of the word `set' will be discussed below, but for the moment the
reader may assume that we are working with any theory of sets which
accounts for their mundane properties, supports a distinction
between `set' and `class', and allows collections of ordinary objects to
be called `sets'.}

For example, we may model the situation of Raymond having cooked an omelette
for Paul as a relational structure $\goth{N}$ of signature
$\fun{\nu}{\{\ob{cooked}\}}{N}$ defined by $\nu(\ob{cooked})=3$, with
universe $\univ{\goth{N}}=\{\ob{R},\ob{P},\ob{O}\}$ and
$\ext{\ob{cooked}}{\goth{N}}$ containing, at least, the sequence
$\ob{R}\ob{O}\ob{P}$.

In constructing $\goth{N}$ we will be forced to determine the complete
extension of \ob{cooked} and so include more information that was conveyed by
the conversation  between Raymond, Paul, Delia and Albert.  Presumably, none
of the sequences containing \ob{O} in the first or third position are
included in the extension of \ob{cooked} on grounds of absurdity, but if,
for example, the sequence $\ob{R}\ob{O}\ob{R}$ is included then
the situation modelled is one in which Raymond also cooked the omelette for
himself---in which case \ob{O} is clearly a two-person omelette.  If, on the
other hand, the sequence $\ob{R}\ob{O}\ob{P}$ is omitted from the
extension of \ob{cooked} then Paul has the feast to himself.  The
necessary overdetermination of this rather crude approach to modelling
information is one of the deficiencies which Situation Theory was designed
to overcome.

In discussing relational structures, we shall make use of the following
notational shorthand. The statement
$$\goth{A}:\relstr{A,R_1^{\nu_1},\ldots, R_n^{\nu_n}}$$
(which may be read as `$\goth{A}$ is {\em of type}
$\relstr{A,R_1^{\nu_1},\ldots, R_n^{\nu_n}}$') means that $\goth{A}$ is a
relational structure with universe $A$ and  primitive relations 
$R_1,\ldots,R_n$, with arities $\nu_1,\ldots,\nu_n$ respectively. For
example,  $\goth{N}:\relstr{\{R,P,O\},\ob{cooked}^3}$. Also,
we use names for the primitive relations of a structure to form
sentences about the structure as if they were predicates in a
formal language.  Given elements $a_1,\ldots,a_{\nu_i}$ of
$\univ{\goth{A}}$, the sentence
$$R_i(a_1,\ldots,a_{\nu_i})$$
when used to describe the structure $\goth{A}$, is true if and only if the
finite sequence $a_1,\ldots,a_{\nu_i}$ lies in $\ext{R_i}{\goth{A}}$.  For
example, the sentence `$\ob{cooked}(R,O,P)$' provides yet another way of
saying that Raymond cooked the omelette for Paul.

We also need to talk about specific elements of the universe of
a relational structure.  Given a set $C$, a relational structure {\em with
constants $C$} is a relational structure $\goth{A}$ together with an
element $\ext{c}{\goth{A}}$ of $\univ{\goth{A}}$ for each $c\in C$.
The effect of including constants in the definition of a relational structure
is a subtle one. It makes no difference to the truth or falsity of
descriptions of the structure, but plays a significant role in comparing two
ostensibly different structures to see if they are structurally identical,
or `isomorphic'.

Relational structures structures $\goth{A}$ and $\goth{B}$ both of
signature $\fun{\nu}{S}{N}$ and with constants $C$ are {\em isomorphic} if
there is a bijective function
$\fun{f}{\univ{\goth{A}}}{\univ{\goth{B}}}$ such that
\begin{enumerate}
\item for each $R\in S$ and
$a_1,\ldots,a_{\nu(R)}\in\univ{\goth{A}}$, \\
$R(a_1,\ldots,a_{\nu(R)})$ in $\goth{A}$ iff
$R(f(a_1),\ldots,f(a_{\nu(R)}))$ in $\goth{B}$
\item for each $c\in C$, $\ext{c}{\goth{B}}=f(\ext{c}{\goth{A}})$.
\end{enumerate}


\subsection{Simple Information Structures}


We are interested in relational structures in two quite different
ways. First, as in the example of $\goth{N}$, we use relational structure
to model the facts of a situation, and as a first attempt at providing a
mathematical model of the structure of the information it contains.
Second, and more significantly, we  our abstract approach to
Situation Theory proceeds by defining successive classes of relational structures,
which may be regarded as approximations to a suitable model for the theory as a 
whole.  An example of the second use is given by our first substantial 
definition.

\begin{defn}
A relational structure $\goth{A}$ of type $\relstr{A,\Rel^2,\Arg^3}$
(possibly with constants) is called a {\em (simple) information
structure} if it satisfies the following
conditions:

\stdax{information-str-1}{If $\Rel(r,\si)$ and $\Rel(r',\si)$ then $r=r'$.}
\stdax{information-str-2}{If $\Arg(a,i,\si)$ and $\Arg(b,i,\si)$ then $a=b$.}
\stdax{information-str-3} {No relation is a role.}
\stdax{information-str-4} {No role is an infon.}
\stdax{information-str-5} {No infon is a relation.}
\end{defn}

Axioms \axref{information-str-1} to \axref{information-str-5} are not
particularly stringent; they merely impose some discipline on the domain.
Together, they say nothing more than that the relations, roles and infons form
disjoint classes, and that infons may have at most one relation and at most
one argument filling each role.


The previously mentioned ambiguity in the word `relation' can be seen clearly
with the help of this definition.
\footnote{Other words we use, such as `role' and `argument', have a  similar 
ambiguity. }
The first use occurs when we use
it to talk about the relations of any relational structure.  For example, the 
theoretical predicates  `$\Rel$' and `$\Arg$'  refer to the  primitive 
{\em relations} of simple information structures.    Relations of this kind
will be dubbed `{\em external}'.  Any other relation between elements of a 
relational structure whose extension is determined by the meta-theory is 
also called `external'.  Examples include relations defined from 
primitive relations, such as the property of being a simple infon.
\footnote{Typically, an $n$-ary external relations is identified with its 
{\em graph}, the set, or  class, of sequences $\tuple{x_1,\ldots,x_n}$ of 
objects which stand in the  relation.  We make no such assumption here. A
meta-theory in which intensional distinctions are made between relations---as
they are in our  object-theory---is quite compatible with our approach.}

The second use of `relation' is governed by the extension of $\Rel$ in
a specific information structure.  Any element $r$ of the universe of
a simple information structure $\goth{A}$ is an {\em internal} relation
of $\goth{A}$ if $\Rel(r,\si)$ for some infon $\si$.  The ambiguity, once
understood, should not cause the reader any difficulty. Where necessary the
sense will be made clear using the adjectives `internal' and `external'.


Aside from illustrating ambiguities, simple information structures provide
our first, crude approximation to the models of Situation Theory.  Their
principal use is to show how ordinary relational structures, of any
signature, can be used to model simple infons.  Suppose, for example, 
we use the structure $\goth{N}$ to model the situation discussed by Raymond
and his friends.  There is a sense in which $\goth{N}$ gives us all we need
to know about the common informational content of the three culinary
pronouncements.  The relation of the infon, \ob{cooked}, is included as
a primitive relation of $\goth{N}$; the three roles of this relation,
\ob{cook}, \ob{guest}, and \ob{dish}, are modelled by the first, second, and
third positions in the sequences in the extension of \ob{cooked}; and the
arguments---Raymond, Paul and the omelette---are also directly included
in the universe of $\goth{N}$.  The thought  that we have thereby obtained a
simple information structure is made more precise in the following
set-theoretic construction.

\begin{con}
\labelp{con.standard}
Given a relational structure $\goth{M}$ of type
$\relstr{M,R_1^{\nu_1},\ldots,R_n^{\nu_n}}$,  possibly with constants, we
construct an information structure $\SInf{\goth{M}}$  as follows. First,  let
$$\begin{array}{lcl}
A_1 & \quadeq & \{1\}\times \{R_1,\ldots,R_n\}  \\
A_2 & \quadeq & \{2\}\times \bigcup_{1\leq i\leq n}\{1,\ldots,\nu_i\}\\
A_3 & \quadeq &  \set{\tuple{3,R_i,\al}}{1\leq i\leq n\;{\rm
and}\;\fun{\al}{\{1,\ldots,\nu_i\}}{M}}
\end{array}
$$
The basic idea is to model simple infons as pairs of the form
$\tuple{R_i,\al}$ in which  $\al$ is a function  from $\{1,\ldots,\nu_i\}$
to the universe of $\goth{M}$.  But we must be careful to keep relations,
roles and infons distinct, and so we also include the prefix indicating the
sort of object modelled: $1$ for relations, $2$ for roles, and $3$ for
simple infons.  We first define the information structure $\iSInf{\goth{M}}$ to
have universe $M\cup A_1\cup A_2\cup A_3$ and with $\Rel$ and
$\Arg$ defined as follows:
\begin{center}
\begin{tabular}{lcl}
$\Rel(r,\si)$   &  iff & $\exists R,\al$ such that $r=\tuple{1,R}$
                         and $\si=\tuple{3,R,\al}$,\\
$\Arg(a,i,\si)$ &  iff &  $\exists j,R,\al$ such that $i=\tuple{2,j}$, \\
                &      & $\si=\tuple{3,R,\al}$ and $\al(j)=a$.
\end{tabular}
\end{center}
The constants of $\iSInf{\goth{M}}$ include all the constants of
$\goth{M}$. In addition, we take each primitive relation $R$
of $\goth{M}$ to be a constant denoting $\tuple{1,R}$. It is a simple
matter to check that the resulting structure $\goth{A}$ satisfies axioms
\axref{information-str-1} to \axref{information-str-5}.

A minor complication arises because of the need to ensure that isomorphic
relational structures give rise to isomorphic information structures---we
don't want accidental features of the representation to encode more
information than there is in the original structure.  We would get
more if,
for example, $M$ happens to contain an element $m=\tuple{1,R}$ in
which $R$ is one of the primitive relations of $\goth{M}$.  In the
structure $\iSInf{\goth{M}}$, this pair plays two parts: that object $m$ of
$\goth{M}$ and that of the (internal) relation denoted by the constant $R$.

We overcome this difficulty by first making a copy of $\goth{M}$.  Let
$\goth{M}_0$ be the isomorphic copy of $\goth{M}$ in which each element
$m$ of $M$ is replaced by the pair $\tuple{0,m}$.  Now we define
$\SInf{\goth{M}}=\iSInf{\goth{M}_0}$.  Unlike $\iSInf{\goth{M}}$, the
structure $\SInf{\goth{M}}$ keeps the old elements distinct from the newly
constructed elements, and so our construction has the desired property of
preserving isomorphism: if $\goth{M}_1$ and $\goth{M}_2$ are isomorphic,
so are $\SInf{\goth{M}_1}$ and $\SInf{\goth{M}_2}$.\footnote{Note also that
the construction depends only on the type of the relational structure. If
$\goth{M}_1$ and $\goth{M}_2$ are  isomorphic
relational structures of the same type
then  indeed $\SInf{\goth{M}_1}=\SInf{\goth{M}_2}$.}
\end{con}

By way of example, consider the model $\goth{N}$ of omelette cooking, defined
earlier. The information structure $\SInf{\goth{N}}$ has individuals
$\tuple{0,\ob{R}}$, $\tuple{0,\ob{P}}$, and $\tuple{0,\ob{O}}$, copied from
$\goth{N}$, a single relation $\tuple{1,\ob{cooking}}$, three roles
$\tuple{2,1}$, $\tuple{2,2}$, and $\tuple{2,3}$, and infons
of the form $\tuple{3,\tuple{\ob{cooked},\al}}$, where $\al$ is a function
with domain $\{1,2,3\}$, taking values from $\{\tuple{0,\ob{R}},\;
\tuple{0,\ob{P}},\; \tuple{0,\ob{O}}\}$. The structure also
has a constant \ob{cooking} which denotes the (internal) relation
$\tuple{1,\ob{cooking}}$. The information that Raymond
cooked the omelette \ob{O} for Paul is modelled by the element
$\tuple{3,\tuple{\ob{cooked},\al}}$ in which $\al$ is the function with
domain $\{1,2,3\}$, with $\al(1)=\tuple{0,\ob{R}}$,
$\al(2)=\tuple{0,\ob{P}}$, and $\al(3)=\tuple{0,\ob{O}}$.

Various aspects of the construction of simple information structures  from
relation structures are artifacts of the set-theoretic tools used to
build them.  For example, the  choice of the numbers $0$ to $3$ as
indicators of the sort of object modelled is quite arbitrary.  In making
theoretical claims about the properties of these structures we must
therefore take care to focus only on the essential aspects of the
construction.  This is easily achieved by widening our study to include
all information structures isomorphic to one constructed from a relational
structure.

\begin{defn}
A simple information structure is {\em standard} if
it is isomorphic to $\SInf{\goth{M}}$ for some relational structure
$\goth{M}$.
\end{defn}

\label{sec.standard-infon-structure}


In the remainder of this section we shall study the standard structures in
some detail.  We shall see that some properties of the standard structures
reflect central intuitions about the structure of information, but
others reflect only the limitations of the construction.  By the end of the
section we shall have a list of axioms characterizing the class of standard
structures, and a number of alternative axioms designed to overcome their
limitations.\footnote{The axioms for standard information structures are
labelled  {\bf A1}, {\bf A2}, and so on. The alternatives to axiom {\bf
A{\em n}}  are labelled {\bf A{\em n}.1}, {\bf A{\em n}.2}, etc.
Some of the alternatives are weaker than the corresponding standard axioms,
generalizing some aspect of standard structures.  Others are stronger,
asserting the existence of objects not present in standard structures.}

\subsection{Roles}

Suppose $\goth{N}'$ is a relational structure of type
$\relstr{N',\ob{stir\mbox{-}fried}^2,\ob{braised}^2}$ and that $\ob{R}$ and
$\ob{P}$ are elements of $M$. Furthermore, let $\al_1$ and $\al_2$ be
functions  with domain $\{1,2\}$ and such that $\al_1(1)=\ob{R}$ and
$\al_2(1)=\ob{P}$. The information structure $\SInf{\goth{N}'}$ contains the
simple infons
$\si_1=\tuple{3,\ob{stir\mbox{-}fried}^2,\al_1}$ and
$\si_2=\tuple{3,\ob{braised}^2,\al_2}$. Thus, in
$\SInf{\goth{N}'}$, we have that
$$\mbox{
$\Arg(\tuple{0,\ob{R}},\tuple{2,1},\si_1)$ and
$\Arg(\tuple{0,\ob{P}},\tuple{2,1},\si_2)$.
}%%%% end of mbox above
$$
  The elements $\tuple{0,\ob{R}}$
and
$\tuple{0,\ob{P}}$ have the common property of filling the role
$\tuple{2,1}$.  What, if anything, does this signify?

In information structures constructed from relational structures in the
above way, roles are simply pairs of the form $\tuple{2,n}$, where $n$ is a
positive integer.  These roles are simply indices recording the relative
position of arguments in original relational structure, and it is
difficult to see how the identity of roles---mere indices---in different
infons can be  given much import.

But we must not be lead astray by the peculiarities of the coding used
in our constructions.  The statement that Raymond stir-fried
the frogs' legs and Paul braised the monkfish tells us, among many other
things, that both Raymond and Paul are cooks; at least, it tells us that they
played the role of cook in the events described.  It may be that we can
regard the role $\tuple{2,1}$ as one which is filled only by cooks.
No such information present in to the underlying structure
$\goth{N}'$, and so it would be a mistake to give this interpretation to
the role $\tuple{2,1}$ of $\SInf{\goth{N}'}$ simply because it happens to
be filled only by cooks.  Nonetheless, the possibility of giving roles some
independent significance has been opened up.

However, the behaviour of roles in standard information structures is
severely constrained.  The roles of
\ob{stir\mbox{-}fried} and \ob{braised} in $\goth{N}'$ are the same two,
$\tuple{2,1}$ and $\tuple{2,2}$, not because of any culinary subtleties,
but simply because both are binary relations, and so use the same numbers,
$1$ and $2$, to index their arguments.  This rather artificial limitations
of standard structures is captured by the following rather
artificial axiom.

\stdax{canonical-roles}
{If $\si$ has a role which is not a role of $\ta$, then every role of
$\ta$ is a role of $\si$.}

In effect, Axiom~\axref{canonical-roles} says that the sets of roles of
infons are linearly ordered by inclusion.  In moving away from standard
structures, this axiom is sure to be dropped.  Theoretical considerations
concerning roles have been studied in connection with the linguistic notion
of a `thematic role' by Engdahl (1991).  Another restriction obeyed in the
standard structures is that

\stdax{finite-roles}{each infon has only finitely many roles.}

Relations with infinite arities are conceivable, and perhaps of some
theoretical use, but it is important to be able to focus on those items of
information which are finitely expressible.  Indeed, it has been
proposed (Devlin 1991)  that the finiteness of infons is an
essential characteristic.  A much less reasonable restriction is that

\stdax{finite-relations}{There are only finitely many relations.}

This is satisfied by all standard information structures, but it should
be dropped when we generalize.

\subsection{Identity}
\labelp{sec.identity}

In all standard information structures, the following criterion of identity
is satisfied.
\stdax{identity}
{Suppose  $\si$ and $\ta$ are infons such that
for all $r$, $a$, and $i$,
\begin{enumerate}
\item $\Rel(r,\si)$ iff $\Rel(r,\ta)$, and
\item $\Arg(a,i,\si)$ iff $\Arg(a,i,\ta)$.
\end{enumerate}
Then $\si=\ta$.}

In many presentations of Situation Theory there is a further
condition, relating to the `polarity' of an infon.  The intuition is that
the information expressed by `Dave is short' and `Dave is not short' are
to be considered on an equal footing, and the latter is to be distinguished
from the information expressed by the denial of the first and  the assertion
of `It is not the case that Dave is short'.  The two infons have the same
relation (being short) and the same argument (Dave) filling the same role.

In most treatments of Situation Theory, this problem has been solved by
introducing an extra attribute  of infons, called {\em polarity}, which is
either positive or negative.  We could incorporate this proposal into the
present account in various ways. For example, we could introduce a a new
unary relation
$\ob{Pos}$ which holds of the positive infons only, and  axioms to  give the
modified identity conditions and to ensure that for every positive infon
there is a corresponding negative infon.  The approach adopted here is keep
our basic definitions uncluttered by matters of polarity and to leave the
proper treatment of negation to the logic of infons, which is discussed in
Section~\ref{sec.logic-of-facts}.

\labelp{sec.functional-notation}

Considerations of polarity aside, axiom \axref{identity} has found wide
support. Moreover, it allows us to introduce a convenient {\em functional
notation}.  For any
finite infon $\si$ there is a relation $r$ and a finite sequence
$\tuple{i_1,a_1},\ldots,\tuple{i_n,a_n}$ of role-argument pairs, such that
$\Rel(r,\si)$ and $\Arg(a_j,i_j,\si)$ for $1\leq j\leq n$ (and no
other pair $\tuple{i,a}$ is such that $\Arg(a,i,\si)$).  Given
Axiom~\axref{identity}, the identity of $\si$ is completely
determined by this information, and so we may write $\si$
unambiguously as
$$\infon{r;i_1\colon a_1,\ldots,i_n\colon a_n}$$
The set of role-argument pairs in a basic infon is called an {\em
assignment}.  Although confined by the linearity of text, the elements
of the assignment are intended to be unordered, so that, for example,
$\infon{r;i:a,j:b}$ and $\infon{r;j:b,i:a}$ denote the same infon---this
follows from Axiom~\axref{identity}, of course.

The functional notation and its variants is widely used. Indeed, it is tempting
to base the theoretical account on an infon-building {\em function} which maps
each pair consisting of a relation $r$ and an assignment
$\tuple{\tuple{i_1,a_1},\ldots,\tuple{i_n,a_n}}$ to the infon
$\infon{r;i_1\colon a_1,\ldots,i_n\colon a_n}$.  The problem with the
functional approach is that the infon-building function is not always properly
defined. Even in the standard structures, it is not the case that
every relation-assignment pair determines an infon; an infon will result
only if the length of assignment is the same as the arity of the relation.

Faced with partiality there are three natural responses.  The first
(Plotkin 1991), is to have an infon-building function which is total but does
not always deliver an infon.   The advantage is an uncomplicated model; the
disadvantage is the existence of many `pseudo-objects' in the
universe which serve no real purpose.  The second response (Plotkin (1991),
Barwise and Cooper (1991)) is to accept that the infon-building function is partial, and make
do  with a partial language (and logic) for describing situation-theoretic
objects.  The third response (Muskens (1995), Robin Cooper (1991) , and this chapter) is to
base the theory on relations instead of functions. The advantage is that
we may retain the services of classical logic and our models remain
uncomplicated. The disadvantage is that we must abandon the functional
notation, at least for theoretical purposes.

In less formal discussions we shall still use terms of the form
`$\infon{r;i:a,j:b}$', with the presupposition that there is an infon to which
the term refers. When the roles are clear from the  context, or are simply
numerical indices in the canonical order ($i=1$, $j=2$), we use the
abbreviated form `$\infon{r;a,b}$'.

\subsection{Arguments}
\label{section-arguments}

Standard information structures have the property that
\stdax{simple-arguments}
{no argument is an infon, relation or role.}

In other words, the information modelled  is of a purely `non-reflexive'
kind: no information {\em about} infons, relations, or roles is included.
This is a severe limitation whose removal has motivated a number of
important developments in Situation Theory.

One reason for rejecting axiom \axref{simple-arguments} in
favour of a more liberal framework is that there are a number of linguistic
expression that are often taken to express `higher-order'
information---information  about infons. Ascriptions of propositional
attitudes and conditionals are the obvious examples. For example, if $\si$
is the information that Albert is replete, then the  information that Delia
knows that Albert is replete may be thought  to involve some relation between
Delia and $\si$ (and possibly  other things).  A first candidate for
modelling this would be an infon  of the form
$\infon{\ob{knows};\ob{Delia},\si}$.  Likewise, if
$\tau$ is the information that Albert is snoring, then we might regard the
conditional `if Albert is snoring then he is replete' as expressing the
information $\infon{\mbox{if},\si,\tau}$.

A second reason for dropping Axiom~\axref{simple-arguments} is to allow
the modelling of information about situation-theoretic objects, such as
relations and infons, within the theory itself.  For example, we may model
the information that $\Rel(r,\si)$ (i.e., that $r$ is a relation of $\si$)
by the infon $\infon{\Rel;r,\si}$.

Recalling Construction~\ref{con.standard}, it is
easy to find the source of compliance with Axiom~\axref{simple-arguments}.
If $\goth{M}$ is a relational structure, the arguments of infons in
$\SInf{\goth{M}}$ are  all of the form  $\tuple{0,m}$ for some element $m$
of $\univ{\goth{M}}$, but any infon, relation or role is of the form
$\tuple{i,a}$ for some $i\neq 0$.  These sortal restrictions are built in
to the construction to ensure that isomorphic relational structures give
rise to isomorphic information structures.

The crucial step enforcing Axiom~\axref{simple-arguments} is the
copying of $\goth{M}$ to form $\goth{M}_0$ before applying the operation
$\mbox{SInf}^-$.  If we construct $\iSInf{\goth{M}}$ directly, the
restriction on arguments is removed and we may obtain non-standard
information structures.

To see how this can give us higher-order infons, suppose $\goth{M}$ is of
type $\relstr{M,R^1_1,R^2_2}$ and $M$ happens to contain an element
$\si=\tuple{3,R_2,\al}$, in which $\al$ is a function from $\{1,2\}$ to
$M$.  Then $\si$ is also included in the universe of $\iSInf{\goth{M}}$
and is at the same time
deemed to be an infon of that structure. But it is still an element
of $M$ and so may also appear as a argument to another infon. In
particular, if $\be$ is the function with domain $\{1\}$ and $\be(1)=\si$
then  $\tau=\tuple{3,R_1,\be}$ is  such a `higher-order' infon. (In the
functional notation, $\tau=\infon{R_1;\si}$.)  The best
we can do in $\SInf{\goth{M}}$ is the infon $\infon{R_1;\tuple{0,\si}}$,
which is not the same thing at all.


\rem{
Aside from containing higher-order infons, infon structures of the form
$\ob{SInf}^-$ are similar to standard infon structures in many respects.
This motivates the following definition.

\begin{defn}
A simple information structure is {\em quasi-standard} if
it is isomorphic to $\iSInf{\goth{M}}$ for some relational structure
$\goth{M}$.
\end{defn}

A degree of caution is needed in thinking about quasi-standard information
structures because the operation $\ob{SInf}^-$ does not have the expected
property of preserving isomorphisms. As a consequence we shall see that
properties of the class of quasi-standard information structures depend on
meta-theoretic assumptions about sets.

Of course, we should not rely on such serendipitous facts about the universe
of the underlying relational structure as the presence of an element which
just happens to have the right set-theoretic shape.
}
It is also worthwhile to iterate the $\iSInf{\goth{M}}$ construction.

\begin{con}\labelp{con.iterated}
Given a relational structure $\goth{M}$, we define an infinite sequence
$\goth{A}_0,\goth{A}_1,\goth{A}_2,\ldots$ of information structures as
follows.  Let $\goth{A}_0$ be $\goth{M}$, and for each integer
$n$, let $\goth{A}_{n+1}$ be  $\iSInf{\goth{A}_n}$.  Finally,
let $\goth{A}$ be the structure whose universe is the union of the
universes $\univ{\goth{A}_n}$ for positive integers $n$, and with
$\ext{\Rel}{\goth{A}}$ and $\ext{\Arg}{\goth{A}}$ defined to be the
unions, for all $n$, of $\ext{\Rel}{\goth{A}_n}$ and
$\ext{\Arg}{\goth{A}_n}$, respectively. It is simple to check that
$\goth{A}$ is an information structure. Moreover, it is
a fixed point of the construction:
$\iSInf{\goth{A}}=\goth{A}$.
\end{con}

The construction of `iterated' information structures is
respectable --- isomorphic relational  structures yield isomorphic information
structures --- yet it generates non-standard structures in which
Axiom~\axref{simple-arguments} fails.  In addition to the infons generated
from $\goth{M}$, the iterated structures contain many `situation-theoretic'
infons of the forms
$\infon{\Rel;r,\si}$ and $\infon{\Arg;a,i,\si}$. To include other
`higher-order' infons, we would need to add further clauses to the iterated
operation. For example, we could incorporate ascriptions of knowledge and
conditions by adding the following clauses to the definition of
$\iSInf{\goth{M}}$:

$$\begin{array}{lcl}
A_4 & = & 
\set{\tuple{4,\ob{knows},\al}}{\fun{\al}{\{1,2\}}{M}\;\rm{and}\;\exists
x,y\;\al(1)=\tuple{0,x},\; \al(2)=\tuple{3,y}}\\
A_5 & = & 
\set{\tuple{5,\ob{if},\al}}{\fun{\al}{\{1,2\}}{M}\;\rm{and}\;\exists
x,y\;\al(1)=\tuple{3,x},\; \al(2)=\tuple{3,y}}
\end{array}
$$

\subsection{Circularity}
\label{section-circularity}

Despite escaping Axiom~\axref{simple-arguments}, the
arguments of infons in iterated information structures are not entirely
without restriction.  The following axiom is satisfied by all
iterated information structures, as well as all standard ones.

\altax{foundation}
{There is no infinite sequence $a_0,a_1,a_2,\ldots$ such that, for
each integer $n$, $a_{n+1}$ is an argument of $a_n$.}

 Axiom~\axref{foundation} is a weakening
of Axiom~\axref{simple-arguments}, which disallows any such sequences, even
ones of the form $a_0, a_1, a_2$.
The Axiom of Foundation (in Set Theory) implies that 
Axiom~\axref{foundation} holds in standard structures. Any such
infinite sequence  would be an
infinitely descending sequence in the transitive closure of the membership
relation, contradicting Foundation.

Axiom~\axref{foundation} prevents a direct model of `circular' information.
For example, it is natural to  take the information expressed by
\begin{quote}
`The information expressed by this sentence is expressible in English'
\end{quote}
to be a simple infon $\si$
described as follows.  The relation of $\si$ should
be \ob{expressible\mbox{-}in\mbox{-}English}.
There should be a role $i$ so that
$\Arg(\si,i,\si)$, and $\si$ should have no other arguments.
Indeed, it might be even assumed that we have an {\em equation}
\begin{equation}
\si\quadeq 
\infon{\ob{expressible\mbox{-}in\mbox{-}English};\si}
\label{eq-circularity}
\end{equation}
 In any
information structure
containing this infon  $\si$, the infinite path
$\si,\si,\si,\ldots$ would be of kind  forbidden by  
Axiom~\axref{foundation}.

Once again, at this point we know that an infon like $\si$
cannot exist in any standard structure.  However, it is 
quite easy to build  non-standard structures with circular  
infons, and we discuss this below.  In line with our axiomatic
approach, we want an axiom which guarantees the existence
of  infons like $\si$.
%%%%%% solutions to equations  like  (\ref{eq-circularity}).

\begin{defn}
Let $I$ be the set of roles of  an information structure $\goth{A}$,
and let $Re$ be the set of relations.
An {\em infon description system for $\goth{A}$ } is a 
triple $\EE = \tuple{X,r, e}$, where $X$ is a set,
$r$ is a partial function from $X$ to $Re$,
and $e$ is a partial function 
from $X\times I$ to $\univ{\goth{A}} \cup X$.
A {\em solution to $\EE$} is a (total) function 
$s$ from $X$ to the infons of $\goth{A}$
 such that for all $x\in X$,
\begin{enumerate}
\item  $r(x)$ is defined iff  $\Rel(r(x),s(x))$.
\item
for all  roles  $i$ such that
$e(x,i)$ is defined and belongs to $X$, 
\begin{quote}
$\Arg(s(e(x,i)),  i, s(x))$. 
\end{quote} 
\label{sol2}  
\item  for all roles  $i$ such that
$e(x,i)$ is defined and belongs to $X - \univ{\goth{A}}$, 
\begin{quote}
$\Arg( e(x,i),  i, s(x))$.
\end{quote}
\label{sol3}  
\item   If $\Arg(a,i, s(x))$, then $a$ comes  from
either clause  (2) or (3).
\end{enumerate}
\end{defn}

As an example, $\EE$ might be an arbitrary singleton $\{x\}$
together with functions $r$ and $e$
given by  $r(x) = \ob{expressible\mbox{-}in\mbox{-}English}$
and $e(x,i) = x$.  Then a solution to $\EE$ would be
a function $s$ defined on $\{x\}$
giving an infon $s(x)$ which we will write as $\si$.
This infon $\si$ has  relation
$r(x)$
 so that $\Arg(\si,i,\si)$
and $\si$ has no other roles.


At this point we can state an axiom:

\altax{afazero}
{Every infon description system has a solution.}



We  digress to discuss
the uniqueness of solutions to infon description systems.
The easiest way to approach this is to consider what
would happen if we had two solutions to the system above.
This would give two distinct infons $\si$ and $\tau$ 
with all of the properties above.
The same intuitions which
justify Axiom~\axref{identity} suggest that $\si$ and $\ta$ must be the
same.  After all, it is difficult to see how one would choose between them
when modelling the information expressed in English, above.  To capture
these intuitions in full generality, we need the following definition.

\begin{defn} Given an information structure $\goth{A}$, a binary relation
$R$ on $A$, is  a {\em bisimulation} iff for all
$\si,\ta$ in $A$, if $R(\si,\ta)$ then
\begin{enumerate}
\item if either $\si$ or $\ta$ are not infons then $\si=\ta$,
\item if $\si$ and $\ta$ are infons then they have the same relation and
roles,
\item $\forall i,a,b$ if $\Arg(a,i,\si)$ and
$\Arg(b,i,\ta)$ then $R(a,b)$, and
\item $R(\ta,\si)$.
\end{enumerate}
For any elements $a,b$ in $A$, we say that $a$ is {\em   bisimilar} to $b$
iff there is a bisimulation $R$ such that $R(a,b)$. It is easy to show that
the relation of being bisimilar is itself a bisimulation, the largest
bisimulation in $\goth{A}$.
\end{defn}

This discussion leads to the following axiom:

\altax{bisim}
{If $a$ is bisimilar to $b$ then $a=b$.}

Further, if we adopt Axiom~\axref{bisim}, then it is natural to
strengthen Axiom~\axref{afazero} to
\altax{afafull}
{Every infon description system has a unique solution.}


\medskip

\rem{
Note that both axioms~\axref{foundation} and  \axref{bisim}, when
combined with Axiom~\axref{identity} extend the identity conditions
of the latter to infons having other infons as arguments.  However,
\axref{bisim} is the weaker of the two, works well even for hyperinfons.
It is now easy to see that in a structure
satisfying axiom \axref{bisim}, infons $\si=\infon{r;\si}$ and
$\ta=\infon{r;\ta}$ would be identical.
}


\rem{
Axioms \axref{foundation} and \axref{bisim} give complete, alternative
accounts of  the identity criterion for infons, but neither says anything
about their existence. Indeed, axioms \axref{information-str-1} to
\axref{identity} are consistent with the claim there there are no infons at
all, and this is not changed by the addition of \axref{foundation} or
\axref{bisim}. 
}




We now turn to the matter of getting models
satisfying axioms like  \axref{afafull}.
As we have seen, the most natural models are of the form
$\iSInf{\goth{M}}$ generated from a relational structure
$\goth{M}$.  However, by the Axiom of  Foundation
in set theory, each such structure satisfies
Axiom~\axref{foundation} and hence falsifies Axiom~\axref{afafull}.
However, suppose
 we drop the Axiom of Foundation from $ZFC$ and call the
result `$ZFC^-$'.   There is no longer any guarantee that the information
structure $\iSInf{\goth{M}}$ generated from a relational structure
$\goth{M}$ satisfies Axiom~\axref{foundation}.  Moreover, it is possible to
replace the Axiom of Foundation by other axioms which ensure that many such
structures exist.  In this setting, the most attractive candidate is the
Anti-foundation Axiom (AFA).
We defer a statement of AFA to
Section~\ref{section-afa} because we don't  need 
it  at this point.   For  more on it, 
see also  Aczel (1988), or Barwise and Moss (1996).

The key point is that assuming AFA, we can get 
standard structures satisfying Axiom~\axref{afafull}.
Indeed, we can get structures with the stronger
property that that the infons literally
{\em are} sets satisfying equations like
 (\ref{eq-circularity}) above. 
 We dub these  {\em hyperinfons}, and the sets in a universe
of set theory where AFA is assumed are called {\em hypersets}.
Note that we have made a rather radical move.
  Faced with a problem in our object-theory (how to obtain
models with circular infons)
 we
change part of our meta-theory --- in this case, the theory of sets. Put this
way, the strategy seems a bit like cheating, at least without some
independent motivation for  hypersets.  From a purely formal point of view
there is no problem at all. Aczel (1988) has shown that ZFC$^-$+AFA is
consistent relative to ZFC$^-$.
 Nonetheless, certain conceptual worries may
remain, especially because the existence of hypersets flies in the fact
of the cumulative (hierarchical) conception of sets which most
  of  us were taught to be a conceptual pillar of set theory.

There are other ways of thinking about sets, discussed
for example in Barwise and Etchemendy (1987), which may give us reason to
change our meta-theory.
Indeed, these other ways are special cases of the 
``structural view'' that we develop
in Section~\ref{section-structural-relations}
of this chapter.
The same view is behind the adoption of AFA in a number of
areas involving circularity 
(see Barwise (1989), and also Barwise and Moss 1996) for examples).
At this point, we want to make two comments on the issue:

First, AFA is only needed to get standard models with circular
infons.  It is possible to get other models directly.  However,
when one starts to build  such models, AFA comes out fairly naturally.
This shows that any ontological qualms one
might have about hypersets are quite irrelevant to the development of
Situation Theory.

Second, AFA not only makes the construction of such models
easier, it allows for the construction of models of
other axioms  of interest in this chapter.  We adopt 
AFA in out meta-theory for this reason, and also because
 its conceptual background fits in with our theory of
structural relations.  

\rem{
The exact role of AFA in Situation Theory is a subtle one.  The key point is
that we are interested in techniques for constructing information structures
with certain  abstract properties captured by axioms, of the kind we have
been discussing.  Constructions require raw materials---in this case, sets.
However, in uncovering the properties of our constructions, we need to
know something about the properties of the sets we use.  These properties
are are determined by our meta-theoretic conception of `set'.  Adopting AFA
instead of Foundation has the  effect of increasing the raw materials
available for our constructions. Instead of a universe of sets determined
by the traditional, `iterative' conception, abstractly presented by the
axioms of ZFC,  we have a slightly different universe of sets, presented by
the axioms of ZFC$^-$+AFA.  These sets are called `hypersets' by Barwise and
Etchemendy (1987).

Before we discuss hypersets and AFA in any detail, we will
examine their use in the current setting.
 For the time being, all we
need to know is that  hypersets of a certain kind exist.  Suppose that
$\iSInf{\goth{M}}$ is the (not necessarily standard)
 information structure  obtained
from  a relational structure $\goth{M}$ with the primitive relation
$\ob{expressible\mbox{-}in\mbox{-}English}$, and that for a variety of
values of $x$,
$\infon{\ob{expressible\mbox{-}in\mbox{-}English};x}$ is an infon of
$\iSInf{\goth{M}}$.
Now, this infon is really a set, namely the pair
$\tuple{3,\ob{expressible\mbox{-}in\mbox{-}English},\al_x}$ where $\al_x$ is the function
with domain $\{1\}$ and such that $f_x(1)=x$.  A consequence of  Foundation
is that there is no solution to the  equation
$$x=\infon{\ob{expressible\mbox{-}in\mbox{-}English};x}$$
So, if $\univ{\goth{M}}$ contains only ordinary sets, there is no infon
$\si$ in $\iSInf{\goth{M}}$ modelling the information expressed by our
example sentence.  On the other hand, according to AFA, there is exactly one
set, call it $\si$, which satisfies the equation. If
$\si$ is in the universe of $\goth{M}$, then it is also in the universe of
$\iSInf{\goth{M}}$, and so is an infon of $\iSInf{\goth{M}}$ of the
required form.
}

\subsection{Appropriateness}
\label{sec.appropriateness}

Let's say that  an object is {\em ordinary} if it is neither a role, nor an
infon, nor a relation. In standard structures,  for  each relation
$r$ of arity $n$ and each sequence
$a_1\ldots a_n$ of ordinary objects, the infon $\infon{r;1\colon
a_1,\ldots,n\colon a_n}$ exists.  We call this property of standard
structures  `generality'.  To state it precisely, we say that infons $\si$
and $\ta$ each with role $i$ are {\em $i$-variants} if  for each role $j\neq
i$ and each $a$, $\Arg(a,j,\si)$ iff $\Arg(a,j,\ta)$. With this
terminology, the principle of generality, which is respected by all standard
information structures, may be stated as follows.

\stdax{ordinary-generality}
{For each infon $\si$ with role $i$ and each ordinary object $a$, there is
an $i$-variant $\ta$ of $\si$ such that $\Arg(a,i,\si)$.}

There are reasons for thinking that Axiom~\axref{ordinary-generality} is both
too weak and too strong. It is too weak because it says nothing about
the appropriateness of arguments  that are not ordinary.  Removing the
restriction to ordinary objects, we get the following:

\altax{generality}
{For each infon $\si$  and with role $i$, and each object $a$, there is an
$i$-variant $\ta$ of $\si$ such that
$\Arg(a,i,\si)$.}

Axiom \axref{generality} is not satisfied by standard information
structures.  However,  the iterated structures of
Construction~\ref{con.iterated} obey a version of the axiom when restricted
to infons with relation
$\Rel$ or $\Arg$. 

The reason for thinking that axioms~\axref{ordinary-generality} and
\axref{generality} are both too strong is that they do not permit sortal
restrictions. For example, the information expressed by `Albert tasted the
{\em cr\`eme br\^ul\'ee}' presupposes that Albert is an agent, perhaps even
that he is subject of conscious experience.  Good evidence for this is
that the presupposition accompanies the claim that Albert did not taste the
{\em cr\`eme br\^ul\'ee}, and we would be surprised to the point of incomprehension if
we were told later that Albert is a Moulinex food processor.
Sortal presuppositions like these may be explained by supposing that the
argument roles of infons carry certain  restrictions on what can fill them.
The omelette \ob{O} of our original example simply cannot fill the role of
\ob{cook} played by Raymond, and vice versa. This may be
captured by ensuring that there is no infon $\ta$ such that
$\Arg(\ob{0},\ob{cook},\ta)$.  Since there is an infon $\si$ such that
$\Arg(\ob{R},\ob{cook},\ta)$	and \ob{O} is an ordinary object, this is
inconsistent with axiom \axref{ordinary-generality}.

We say that an object $a$ is an {\em appropriate filler} of role $i$ just in
case there is an infon $\si$ such that $\Arg(a,i,\si)$.  To allow for
role-linked sortal restrictions, we may
modify Axiom~\axref{ordinary-generality} to the principle of `sortal
generality':
\altax{sortal-generality}
{for each infon $\si$ with role $i$ and each appropriate filler $a$ of $i$,
there
is an $i$-variant $\ta$ of $\si$ such that $\Arg(a,i,\si)$.}
This is a great improvement.  In effect, we have associated a domain of
objects with each role---their appropriate fillers---and allowed
unrestricted replacement of one argument by any other argument in the
domain. In standard information structures, the domain of appropriate
fillers for each role is just the class of ordinary objects, but
other structures may have different domains for different roles.
The iterated structures of Construction~\ref{con.iterated} all satisfy
Axiom~\axref{sortal-generality}. They have two domains: roles of the
original structure may be filled by any ordinary object, and roles of
infons whose relation is $\Arg$ of $\Rel$ may be filled by any object at
all.

A theory of appropriateness, stating in general terms which arguments may be
fill which roles, has not yet been given.  Axiom \axref{sortal-generality}
accords with the way roles are usually thought to restrict their fillers,
but there may be restrictions on the formation of infons that are not
attributable to a single role.  For example, consider a sketch of two
people  standing side-by-side, and call the depicted relationship between
the people `$\ob{next\mbox{-}to}$'. It is arguable that 
$\ob{next\mbox{-}to}$ is not the
same as  the relation expressed by English preposition `next to' because any
picture of two people standing side-by-side presupposes that there are {\em
two} people rather than one.  We may analyze the difference by saying that
the two roles of $\ob{next\mbox{-}to}$ place a joint restriction on their
fillers,
namely, that they cannot be filled by the same argument.  This kind of
restriction is not permitted by Axiom~\axref{ordinary-generality} or by
axiom \axref{sortal-generality}.


\subsection{Partiality}
\label{sec.partiality}

In standard information structures every infon has a relation and a set of
roles determined by that relation.  This is captured by the
following two axioms.

\stdax{infons-have-relations}
{For each infon $\si$ there is a relation $r$ such that $\Rel(r,\si)$.}
\stdax{fixed-arity}
{If $\Rel(r,\si)$ and $\Rel(r,\ta)$ and $\Arg(a,i,\si)$ then for
some $b$, $\Arg(b,i,\ta)$.}

One reason for dropping these axioms is to allow infons
to be {\em unsaturated}. For example, suppose you overhear someone saying
`Mary saw Elvis in Tokyo' but a distracting noise prevents you
from hearing the word `Elvis'. The information  conveyed is
unsaturated because the filler of one of the roles is missing. We may
represent the unsaturated infon as
$\infon{\mbox{\ob{saw}; \ob{seer}: \ob{Mary},
\ob{location}: \ob{Tokyo}}}$, to be contrasted with the infon
$$\infon{\mbox{\ob{saw}; \ob{seer}: \ob{Mary}, \ob{seen}: \ob{Elvis},
\ob{location}: \ob{Tokyo}}}$$
which would have been conveyed had you heard the whole utterance.  The
coexistence of these infons is forbidden by Axiom~\axref{fixed-arity},
which must therefore be dropped if they are to be modelled successfully.
Another way in which an infon can be unsaturated is by lacking a
relation---consider, for example, the information conveyed if the word `saw'
had been obscured. This counts against Axiom~\axref{infons-have-relations}.

In the absence of the constraints of axioms~\axref{infons-have-relations}
and \axref{fixed-arity}, it is useful to define an ordering of infons that
captures the degree to which they are saturated.

\begin{defn} Infon $\ta$ is {\em part of} infon $\si$, written $\si\partof\ta$,
if
\begin{enumerate}
\item for all $r$, if $\Rel(r,\si)$ then $\Rel(r,\ta)$, and
\item for each role $i$ and object
$a$, if $\Arg(a,i,\si)$ then $\Arg(a,i,\ta)$.
\end{enumerate}
An infon $\si$ is {\em unsaturated} if there is another infon $\ta$ such
that $\si\partof\ta$. If there is no such infon, $\si$ is said to be {\em
saturated}.
\end{defn}

Despite our need to have unsaturated infons, there is something to be said
for the intuition that an infons {\em should} have a relation which
determines its roles.  We can recover the force of this idea by restricting
axioms~\axref{infons-have-relations} and
\axref{fixed-arity} to apply only to
saturated infons.

\altax{sat-infons-have-relations}
{Every saturated infon has a relation.}
\altax{sat-fixed-arity}
{For saturated infons, $\si$ and $\ta$, having the same relation, and for
each object $a$ and role $i$, if $\Arg(a,i,\si)$ then for some $b$,
$\Arg(b,i,\ta)$.}

In this way, we see that the standard structures are a
limiting special case. Axioms~\axref{infons-have-relations} and
\axref{fixed-arity} follow from \axref{sat-infons-have-relations} and
\axref{sat-fixed-arity} given the additional assumption that every infon is
saturated.

The  ordering $\partof$ is clearly a preorder of infons (reflexive and
transitive). In information structures satisfying
Axiom~\axref{identity} it is a partial order (reflexive, transitive,
and antisymmetric), and in standard structures it is trivial
($\si\partof\ta$ iff $\si=\ta$) because every infon is saturated.  The
properties of the information ordering in non-standard information
structures may be constrained by the assumptions we make concerning
the existence of upper bounds.

\begin{defn} Infons $\si$ and $\ta$ are {\em compatible} if
they have the same relation and for each role $i$ and objects $a$ and
$b$, if $\Arg(a,i,si)$ and $\Arg(b,i,\ta)$ then $a=b$.
They are {\em unifiable} if they
possess a least upper bound in the $\partof$ 
ordering.\footnote{I.e., if $\exists x$ such that
$\si\partof x$, $\ta\partof x$, and $\forall y$, if $\si\partof y$ and
$\ta\partof y$, then $x\partof y$.}
\end{defn}

For example, the information that Mary saw Elvis is compatible with
the information that Elvis was seen in Tokyo.  Moreover, it seems
reasonable to suppose that these two infons may be unified to produce
the information that Mary saw Elvis in Tokyo.\footnote{There is no
requirement that the unification of two infons is `entailed' by the
infons being unified; just that the unification of the two infons is
the least infon containing them.} This suggests the following unification
axiom.
\altax{unif}
{Every strictly compatible pair of infons is unifiable.}

Questions concerning the order of infons become a lot more
difficult to answer if the arguments of infons are also partial objects.
This is unavoidable if we wish to model `higher-order' infons, as
discussed in Section~\ref{section-arguments}.  
There are a variety of ways of extending the
order between infons by taking the order of arguments into account, but
none of them is entirely convincing.  Consider, for example, the idea that
if $a\partof a'$ then the infon $\infon{r;i\colon
a,j\colon b}$  is part of the infon $\infon{r;i\colon a',j\colon b}$.
This seems plausible at first, until one recalls the idea
that the information expressed by a conditional is an infon of the form
$\infon{\ob{if};\si,\ta}$.  If $\si\neq\si'$ then we would {\em not} wish
to say that $\infon{\ob{if};\si,\ta}$ is part  of $\infon{\ob{if};\si',\ta}$
even if  $\si\partof\si'$. Consequently, we shall stick to the above
definition, even for infons with other infons as arguments.

With discussions of unification, comparison with the literature on feature
structures (cf.~Rounds' chapter in this volume) is unavoidable.  
There is a strong
similarity between feature structures and information structures. Indeed, it is
easy to see how one can construct information structures using
features structures to model the infons. Conversely, one can use information
structures to model feature structures, by identifying features with roles
and values with arguments.  The order $\partof$ defined for infons is
relatively uninteresting when applied to feature structures, precisely
because it does not take into account the order of arguments.  Rounds (1991)
discusses the relationship between the two subjects.




\subsection{Representation Theorems}
\labelp{sec-representation}


In addition to the axioms discussed above, we need one more axiom to
account for the behaviour of constants in standard information structures.

\stdax{constants}
{Every relation but no role and no infon is denoted by a constant.}

This axiom is entirely artificial, and of little consequence to the general
theory.

\begin{thm}
A simple information structure is standard if and only if it satisfies the
axioms~\axref{information-str-1} to \axref{constants}.
\label{thm-T0}
\end{thm}
\begin{proof}
We have already seen that each of these axioms is satisfied by all standard
information structures. For the converse, let $\goth{A}$ be an information
structure satisfying the axioms, with constants $C$. We shall construct a
relational structure
$\goth{M}$ and an isomorphism
$\fun{f}{\univ{\goth{A}}}{\univ{\SInf{\goth{M}}}}$.

Let $R$ be the class of relations in $\goth{A}$, $I$ the
class of roles, $\Sigma$ the class of infons, and $M$ the class of ordinary
objects.  By axioms~\axref{information-str-3} to \axref{information-str-5},
these four classes are pairwise disjoint and exhaust the universe of
$\goth{A}$.

The class $R$ of relations is finite by Axiom~\axref{finite-relations}.  For
each $r$ in $R$, let
$$I_r\quadeq\set{i}{\exists
a,\si\;\Rel(r,\si)\;\mbox{and}\;\Arg(a,i,\si)}.$$
We shall show that $I_r$ is finite.  For each infon $\si$ of $\goth{A}$,
let $I_{\si}=\set{i}{\exists a\;\Arg(a,i,\si)}$. By
Axiom~\axref{fixed-arity}, for all infons $\si$ and $\ta$ such that
$\Rel(r,\si)$ and $\Rel(r,\ta)$, $I_{\si}=I_{\ta}$.  Thus for
each $\si$ having relation $r$, $I_r=I_{\si}$. Moreover, by
Axiom~\axref{finite-roles}, $I_{\si}$ is finite  for each infon $\si$, and so
$I_r$ is finite also.

Let $S\subseteq C$ be the class of those constants that denote relations in
$\goth{A}$. By  Axiom~\axref{constants}, $S$ is the same size as $R$.
This enables us to define a relational signature $\nu$ with primitive
relations $S$ and such that for each $R'$ in $S$, $\nu(R')$ is equal to the
size of $I_{\ext{R'}{\goth{A}}}$.  Let $\goth{M}$ be any
relational structure with signature $\nu$, universe $M$, and constants $C-S$,
each with the same denotation it has in $\goth{A}$ (which is possible,
because these constants denote ordinary objects, by
Axiom~\axref{constants}).  We shall construct an isomorphism
$f$ from $\goth{A}$ to $\SInf{\goth{M}}$.

First, we must enumerate the set $I$ of roles of $\goth{A}$.
By axioms~\axref{information-str-1} and
\axref{infons-have-relations},  for each infon $\si$ of $\goth{A}$ there is
a unique relation $r_{\si}$ such that $\Rel(r_{\si},\si)$. By the above,
$I_{\si}=I_{r_{\si}}$. But there are only a finite number
of relations (Axiom~\axref{finite-relations}), and so there are only a finite
number of sets of the form $I_{\si}$, even if the number of infons is
infinite. Moreover, by Axiom~\axref{canonical-roles}, these sets are
linearly ordered by inclusion. Consequently, there is an enumeration
$r_1,\ldots,r_n$ of $R$ such that $I_{r_k}\subseteq
I_{r_{k+1}}$, for for $1\leq k\leq n-1$. Now
$$I=I_{r_1}\cup\ldots\cup I_{r_n}=
I_{r_1}\cup\ldots\cup(I_{r_{k+1}}-I_{r_k})\cup\ldots\cup(I_{r_n}-I_{n-1}).$$
and so we may enumerate $I$ by enumerating each of the sets
$(I_{r_{k+1}}-I_{r_k})$ in order, and without repetition.  Let
$i_1,\ldots,i_N$ be such an enumeration. It has the property that for $1\leq
k\leq n$,
$I_{r_k}=\{i_1,\ldots,i_{\nu(r_k)}\}$.

Next, we must consider the arguments of infons. For each infon $\si$, we
have seen that $$I_{\si}=I_{r_{\si}}=\{i_1,\ldots,i_{\nu(r_{\si})}\}$$
and by Axiom~\axref{information-str-2}, for $1\leq k\leq n$, there is a
unique object $a_k$ such that $\Arg(a_k,i_k,\si)$.  By
Axiom~\axref{simple-arguments}, $a_k$ is ordinary and so is in $M$. Define
the function
$\fun{\al_{\si}}{\{1,\ldots,\nu(r_{\si})\}}{\{0\}\times M}$
by $\al_{\si}(k)=\tuple{0,a_k}$.

Now we are ready to define the function $f$ from $\univ{\goth{A}}$ to
$\univ{\SInf{\goth{M}}}$.

$$f(x) = \defbycases{
\tuple{0,x} & \mbox{if $x$ is in $M$} \\
\tuple{1,x} & \mbox{if $x$ is in $R$} \\
\tuple{2,k} & \mbox{if $x$ is in $I$ and $i_k=x$} \\
\tuple{3,\tuple{r_x,\al_x}} & \mbox{if $x$ is in $\Sigma$}}.$$

This is a good definition, because every element of  $\univ{\goth{A}}$ is
in exactly one of the classes $M$, $R$, $I$ or $\Sigma$, and for each $x$
in $I$ there is a unique $k$ such that $i_k=x$.  To show that $f$ is
one-one, suppose that $f(x)=f(y)$. We can show that $x=y$ by cases
according to whether $x$ and $y$ are in $M$, $R$, $I$ or $\Si$.  The only
non-trivial case is that in which $x$ and $y$ are infons. Then
$f(x)=\tuple{3,\tuple{r_x,\al_x}}$ and  $f(y)=\tuple{3,\tuple{r_y,\al_y}}$.
Thus, $r_x=r_y$ and $\al_x=\al_y$, and so by Axiom~\axref{identity},
$x=y$, as required.

To show that $f$ is onto the universe of $\SInf{\goth{M}}$, consider any
element $\tuple{j,x}$ of that universe. We need to find a $y$ such that
$f(y)=\tuple{j,x}$. The only non-trivial case is that in which
$j=3$. Then $x=\tuple{r,\al}$ for some relation $r$ and function
$\fun{\al}{\{1,\ldots,\nu(r)\}}{\{0\}\times M}$. For $1\leq k\leq\nu(r)$,
let $m_k$ be the element of $M$ for which $\al(k)=\tuple{0,m_k}$.  Now, $r$
is a relation, so there is some infon $\si$ of $\goth{A}$ such
that $\Rel(r,\si)$.  The roles of $\si$ are
those in the set $I_{\si}=\{i_1,\ldots,i_{\nu(r)}\}$ and so, applying
Axiom~\axref{ordinary-generality} repeatedly ($\nu(r)$ times), we obtain an
infon $\si'$ such that $\Arg(m_k,i_k,\si')$ for $1\leq k\leq\nu(r)$.
Spelling out the definition of $\al_{\si'}$ we see that this function is
just $\al$, so $\tuple{r_{\si'},\al_{\si'}}=\tuple{r,\al}=x$, and so
$f(\si')=\tuple{3,\tuple{r_{\si'},\al_{\si'}}}=\tuple{3,x}$, as required.

Finally, we must show that $f$ preserves the structure of $\goth{A}$.  This
follows from the following two chains of equivalences. Firstly for $\Rel$:
\begin{center}
$\Rel(f(r),f(\si))$ in $\SInf{\goth{M}}$ \\
$\Rel(\tuple{1,r},\tuple{3,\tuple{r_{\si},\al_{\si}}})$ in $\SInf{\goth{M}}$
\\
$r=r_{\si}$ \\
$\Rel(r,\si)$ in $\goth{A}$.
\end{center}
And then for $\Arg$:
\begin{center}
$\Arg(f(m),f(i),f(\si))$ in $\SInf{\goth{M}}$\\
$\Arg(\tuple{0,m},\tuple{2,k},\tuple{3,\tuple{r_{\si},\al_{\si}}})$ in
$\SInf{\goth{M}}$ and $i_k=i$\\
$\al_{\si}(k)=\tuple{0,m}$ and $i_k=i$ \\
$\Arg(m,i,\si)$ in $\goth{A}$.
\end{center}
That $f$ preserves the denotation of the constants in $C$ follows from
Axiom~\axref{constants} and the definition of $\SInf{\goth{M}}$.
\end{proof}



We close this section with representation result for 
another class of structures.

\begin{defn}
A {\em generalized standard information structure} is 
a structure $\goth{M}$ which satisfies
axioms \axref{bisim} and \axref{sortal-generality}.
\end{defn}

Note that the standard structures satisfy both of these
conditions; 
the importance of such  generalized structures will
emerge from our discussions  in the sequel.  We focus
on these now to highlight the importance of
\axref{bisim} and \axref{sortal-generality} and to
introduce work on bisimulations that will also be important.

\begin{thm}
Let $R$, $I$, and $Ord$ be   sets or classes.
Then there is a fixed generalized information structure
$\goth{M}$ with the following properties:
\begin{enumerate}
\item $R$, $I$, and $Ord$  are the  relations, roles, and ordinary
objects of $\goth{M}$, respectively.
\label{rro}
\item If $\goth{N}$ has the property of (\ref{rro}), then
$\goth{N}$ is isomorphic to a substructure of $\goth{M}$.
\end{enumerate} 
\end{thm}

Before turning to the proof, we have two remarks.
First, the result is a representation theorem: every
$\goth{N}$ using  the pre-specified collections
$R$, $I$, and $Ord$  is a substructure of a big
structure $\goth{M}$.  Second, the ideas behind the proof
are more important than the result itself.

\begin{proof}
We sketch the details.    We need only construct the
infons of $\goth{M}$.  For this,  we use {\em infon systems}.
These are systems of equations of the following form:
$$ x \quadeq \tuple{r,\set{\tuple{i_1,p_1}, \ldots, \tuple{i_k,p_k}, \ldots}}.$$
Here $r$ is a relation; the $i$'s are roles, and 
the $x$ on the left  is a fresh object which we call a variable.
Each $p_j$ must either be an ordinary object which is an appropriate filler
for the corresponding role $i_j$, or again a variable, say $y$
which also occurs on the left side of some equation in our system.
An infon system is a collection of such equations. 
 
A {\em pointed infon system} is a pair $\tuple{{\cal S},x}$, where
${\cal S}$ is an infon system and $x$ is one of the variables of $x$.
It is not hard to define a relation of bisimulation on the collection
of all
pointed systems.  One then considers pointed systems modulo
bisimulation.  This collection serves as the infons of $\goth{M}$;
the rest of the structure is easy to come by, as is the
verification that we have a generalized standard structure.
  To check the universality property
 fix some  appropriate structure $\goth{N}$.  
Each infon $\si$ of $\goth{N}$ gives rise to a pointed system,
hence to an element of $\goth{M}$.  This association is one-to-one,
using the assumption that $\goth{N}$ satisfies Axiom~\axref{bisim}.
\end{proof}


\end{document}
