Received: from barlaeus.ic.uva.nl by moose.cs.indiana.edu
(8.7.1/IUCS.1.39) id JAA16029; Tue, 2 Jan 1996 09:36:24 -0500 (EST)
Received: from ccsom.uva.nl (gaston.ccsom.uva.nl) by barlaeus.ic.uva.nl with SMTP id AA16078
(5.67b/IDA-1.4.4 for ); Tue, 2 Jan 1996 15:36:20 +0100
Received: from [145.18.81.176] by ccsom.uva.nl (5.x/SMI-SVR4)
id AA04831; Tue, 2 Jan 1996 15:35:57 GMT
Message-Id: <9601021535.AA04831@ccsom.uva.nl>
Date: Tue, 2 Jan 1996 16:41:56 -0800
To: ITALLC96@cs.Indiana.edu
From: office@gaston.ccsom.uva.nl (CCSOM office)
Subject: ITALLC96 Submission
Status: RO
Dear Organizers,
due to the closure of our office in the last days of the year I could not
send my submission before Jan 1.I do hope that it is not to late yet.The
abstract is in form of a LaTeX I also hope that this format is acceptable.
Yours sincerely
L. P\'olos
\documentstyle[12pt]{article}
\newtheorem{definition}{Definition}[section]
\newcommand{\rsit}{>\!>}
\newcommand{\lsit}{<\!<}
\newcommand{\rsem}{]\!]}
\newcommand{\lsem}{[\![}
\begin{document}
\title{\bf Situated Update Semantics}\\
\author{L\'{a}szl\'{o} P\'{o}los\\
CCSOM, University of Amsterdam\\
Oude Turfmarkt 151, 1012 GC Amsterdam
\\e-mail: laszlo@ccsom.nl}
\maketitle
The aim of the present paper is to develop a logic adequate to the
argumentation one typically sees in the context of theory
building\footnote{The work presented in this paper was supported by The
grant #PGS 50-334 of the Dutch National Science Foundation (NWO)}. I followed
a
straightforward methodology: First identify the requirements (desiderata) for
such a logic, then find a framework where these requirements can be
implemented, carry out the implementation an check how the logic looks like.
The organization of the present paper follows this methodology.
\begin{section}{Introduction}
The paper is structured as follows. In the introduction I spell out some
findings
about theory building in the social sciences relevant to logic, in order to
provide
motivations. This part concludes with the definitions of two languages that of
the theories and that of the test respectively. In the next section I
introduce some
basics of situation theory, and define an "epistemically twisted" version
of it. In
the third section I give a static (denotational) semantics and a dynamic
semantics
for the language of theories but only a dynamic semantics for the language of
tests. The paper concludes with the definition of a number of logical
consequence
relations, and with a list of interesting validities.
In the development of a theory one can identify constructive and destructive
phases. In the former one the theory extends, the explanatory power increases,
in the latter one the theory shrinks, unwanted parts are removed to prepare
the ground for reconstruction. In the present paper I am concerned with the
former phase and that is what I call theory {\em building}. In that process the
information content of the theory grows monotonicly.
\begin{subsection}{Sentences of a theory}
A theory might contain all sorts of non-textual information pieces.
Even though I admit that for several purposes those pieces of information can
be more efficient then texts, I see no particular reason why should these
elements be not describable in form of sentences of one language or another.
For the sake of simplicity I assume that the content of a theory is expressed in
form of sentences, and theory building operates on a set of sentences. The
elements of this set fall into two main categories theorems, and assumptions.
\begin{subsubsection}{Assumptions of a theory}
The assumptions of a theory are of three sorts. Some of the assumptions
characterize objects the theory in terms of already established notions.
These are
the definitions. To avoid circularity definitions should rest on some notions
undefined in the theory. Undefined notions cannot be arbitrary either. If they
originate from (a largely implicit) background knowledge and their
properties are
fixed by meta-considerations, or they are primitive concepts and their meaning
is limited by axioms. The sample of social science theories I looked
at\footnote{The sample was taken from organization and management theories
such as J.D. Thompson: Organizations in Action or Hannan's and Freeman's The
Population Ecology of Organizations} showed that FOL is sufficient to account
for the inferential properties of the assumptions I mentioned so far.
To constrain the meaning of some primitive notions is not the only function of
axioms. If a theory has some empirical content it cannot be completely
analytical,
i.e. it should explanations that are based on further axioms, domain specific
explanatory principles, such as {\it Organizations abhor uncertainty.} These
axioms are typically expressed in form of generic sentences. The generic form is
adequate because it captures the generality on the one side and the
possibility of
exceptions on the other side. How to find the formal counterpart for generic
sentences was a highly debated issue in formal semantics in the last decade. For
the purposes of the present paper I assume that generic sentences are composed
of two open formulae, antecedent and consequent. These formulae share all the
free variables, and a generic quantifier $\mathbf{Q}$ binds all free variables.
As for the semantics of generics sentences one has to consider that they allow
(unpredictable) exceptions. In preparation to these exceptions it is wise not to
infer from generic premises if it is not necessary. Therefore I assume that
these
generic sentences express deferred pieces of information, and their inherent
generality can be exploited in inferencing only in the presence of specific
triggers. Now the inferential properties of empirical generalizations are
to be
investigated in conjunction with that of the triggers. These triggers are
going to
be discussed in context of the predictions of a theory.
\begin {subsubsection}{Theorems of a theory}
The very purpose of a theory is to provide understanding, explanations, and
predictions. Those sentences that are explained or predicted are the
theorems and the assumptions provide the basis of the predictions or explana-
tions. Theories in progress have theorems of two sorts. Some of them are
strict,
their derivation does not require triggers, and once derived, they remain
persistent through further extensions of the theory. Strict theorems can
be used
as assumptions for deriving further theorems. Just like assumptions, strict
theorems constitute parts of the theory while the theory development is in the
constructive phase. But not all theorems are strict.
As the theory extends, more and more possibilities are excluded, what might
have been the case according to a previous stage of the theory, can not be
the case
according to a latter stage, what might have been a rational presumption could
become non-sensical. The derivation of these theorems are costly, because these
predictions are not persistent, they may vanish as the theory extends. They are
predictions of the theory but do not constitute part of the.The developer
of the
theory are interested to derive them, because she wishes to know not only how
the world, according to the theory, should look like, but also what might be the
case, what is likely to be the case. These wishes are behind the triggers
one uses to
fire the empirical generalizations of the theory. What triggers are
relevant in the
process of theory building?
\begin{paragraph}{Likely, presumably implies}
Suppose an attempt is made to derive that the elements of the sequence $a$
stand in the relation $R$, and the result is that within the given stage of the
theory it is neither provable, nor disprovable. In such a situation the
developer
of the theory might wish to know whether it is {\it likely} that the sequence of
individuals $a$ stand in the relation $R$ and if it is, {\it how likely} it is.
To satisfy her curiosity she needs a number of triggers: $a\mbox{ }is\mbox{
}likely_{n}\mbox{ }R$, where the smaller the lower index is the more
likely it is
that the relation holds. Facts are indeed most likely to be true, therefore
$a\mbox{ }is\mbox{ }likely_{0}\mbox{ }R$ can be interpreted that $a\mbox{
}is\mbox{ }R$.
If the developer of the theory is interested not in likely properties of
individual
sequences but in the relation between relations, the triggers she should use are
the $presumably$ $implies$ triggers. These triggers form pairs with the $likely$
triggers and are interpreted in the following manner: $R\mbox{ }presumab-
ly\mbox{ }implies_{n}\mbox{ }Q$ iff for any element a which is in the extension
of $R$ according to the theory it holds that $a\mbox{ }is\mbox{
}likely_{n}\mbox{ }Q$
\end{paragraph}
\begin{paragraph}{May and might}
Due to the long lasting influence of K.R. Popper\footnote{See for example
Popper, K.R. Logik der Forschung, or Conjectures and Refutations} all theory
developers are after falsifiable theories. A theory is meaningful only if
there are
possible state of affairs that make the theory false if they were true. To
find such
possible states of affairs one has to find out what $might$ (not) be the case,
according to a given stage of the theory.
Another natural interest of the theory builder is to find out whether the
empiri-
cal generalizations of the theory needs to be restricted. A restriction is
indeed
necessary if one sees a conflict between an established fact and some of the
empirical generalizations. Such a conflict becomes visible if something $may$
not be that case according to the theory but in fact it is the case. The
difference
between the $might$ and the $may$ triggers is that the former concerns only
with the strict assumptions whereas the latter takes the empirical
generalizations
into account too.
\end{paragraph}
\end{subsubsection}
\begin{subsection}{The languages}
To summarize the findings about sentences of a theory I define two languages,
the language of (social science) theories, and the languages of tests.
\begin{subsubsection}{The language of theories}
In the definition of this language I assume that a standard definition of the
language of FOL (LOFOL) is given, the notion of an open formula and that of a
free variable is known.
\begin{definition}
A string $\phi$ is a formula of the language of theories iff $\phi$ is a
formula
of LOFOL or $\phi$ is the form of $\mathbf{Q} x[A(x);B(x)]$ where $A(x)$ and $
B(x)$ are open formulae of LOFOL and they share all free variables. In
this case
$\phi$ is a closed formula.
\end{definition}
(Throughout this paper I use $x$ not only as a variable but as a sequence of
variables too. Occasionally I apply the same trick to individuals too.)
\end{subsubsection}
\begin{subsubsection}{The language of tests}
The language of tests consist of the formal counterparts of the triggers I
described
above.
\begin{definition}
Let $a$ be an n-long sequence of individual constants and $\phi (x) $ and $\psi
(x) $ two open formulae of LOFOL containing exactly the same $n$ free variables,
and let $k$ be a natural number. With these conditions the following strings are
formulae of the language of tests:
\begin{enumerate}
\item $a \mbox{ }is\mbox{ } likely \mbox{ }\phi (x)$
\item $a\mbox{ }is\mbox{ }likely_{k} \mbox{ }\phi (x)$
\item $a\mbox{ }might\mbox{ } be \mbox{ }\phi (x)$
\item $a\mbox{ }may\mbox{ } be \mbox{ }\phi (x)$
\item $\psi (x)\mbox{ }presumably\mbox{ } implies \mbox{ }\phi (x)$
\item $\psi (x)\mbox{ }presumably_{k}\mbox{ } implies \mbox{ }\phi (x)$
\end{enumerate}
\end{definition}
\end{subsubsection}
\end{subsection}
\end{section}
\begin {section}{Situation theory}
Situation theory is a sorted notation system. Some important sorts are:
relations, objects assignments, infons, situations, propositions, parameters,
types, sets, and extensions. In what follows I briefly summarize some relations
between these sorts and refer the reader to [Barwise-Cooper 1994] for more
details.
\begin{subsection}{Relations, object, assignments, and polarities}
In situation theory relations are objects equipped with a set of
argument places. The cardinality of this set is the arity ($\nu$ ) of the
relation.
Throughout this paper I assume that the arity is finite for all relations.
Situation theory is untyped i.e. anything that can be constructed within the
theory counts as an object.(For the of the present paper it is enough to
have set
many object available $\mathbf{OBJ}$.) Assignments are functions from natural
numbers to objects. There are two polarities $1$ and $0$ respectively.
\end{subsection}
\begin{subsection {Infons and situations}
If $\rho \in \mathbf {R}, \nu (\rho)=n $ and $\alpha : n
\longrightarrow \mathbf {OBJ}$ and $\pi \in \{0,1\}$ then
\[\lsit\rho,\alpha;\pi\rsit\] is an infon. Situations, they are characterized in
terms of the infons they support.
\end{subsection}
\begin {subsection}{Propositions }
If $\sigma$ is a situation and $\iota$ is an infon the fact that $\sigma$
supports
$\iota$ is expressed by $\sigma\models\iota$, and $\sigma\not\models\iota$.
We call both $\sigma\models\iota$, and $\sigma\not\models\iota$
propositions, and these propositions are negations of each other. Conjunction
and disjunction of propositions as well as the negation of a proposition are
propositions.
\end{subsection}
\begin{subsection}{Parameters, types, extensions, and truth}
Parameters form a subsort of the sort of objects ($ \mathbf{PAR}$). In the
present
paper I use parameters for one purpose only, to lambda abstract them form other
sorts to form new (functional) sorts. $\alpha$ is a parameter assignment
if it is a
function, such that $\alpha : n \longrightarrow {\mathbf PAR}$
Let $\alpha$ be a parameter assignment and $\pi$ be a proposition. $\lambda
\alpha [ \pi ]$ is a type. The set of types ($ \mathbf{TYPE}$ contains
furthermore
three primitive elements $ [UNIV,\mbox{ } INST, \mbox{ and } C}$ respectively.
Let $\alpha$ be a parameter assignment, $|DOM(\alpha )| = n $ and
$\pi$ be a proposition. The extension of the type $\lambda \alpha [ \pi ]$
is the
set $\mathbf {EXT} (\lambda \alpha [ \pi ])$. Some conditions for the exten-
sions are listed below.
$\mathbf {EXT} (\lambda\alpha [ \pi ])\subseteq \mathbf {OBJ}^{n}\]$\\
$\mathbf {EXT} (UNIV)\subseteq \mathbf {TYPE}\]$\\
$\mathbf {EXT} (C)\subseteq \mathbf {TYPE^{2}}\]$\\
The elements of the extensions of types are assignments. If $\alpha$ is an
assignment, $\tau$ is a type, and $\alpha$ can be an element of the
extension of
$\tau$\footnote{In standard situation theory this last condition is often
expressed as $\alpha$ is appropriate for $\tau$.} then $\alpha:\tau$ is a
proposition. To summarize, atomic propositions are either of the following two
forms: $\sigma\models\iota$ or $ \alpha:\tau $, and their truth-conditions
depend on their form. $\sigma\models\iota$ is true iff the situation $\sigma$
indeed supports the infon $\iota$ and $ \alpha:\tau $ is true iff $ \alpha$
is an
element of the extension of the type $\tau $.
\end{subsection}
\begin{subsection}{Contexts}
In situation theory it is the world that tells us what assignment belong to the
extension of a type, and what do not belong. In the context of theory building
one does not have access to this ultimate source of information. Instead it
is the
actual stage of the theory that tells us what assignments belong to the
extensions.
But a stage of a theory provides, for obvious reasons, only partial information
about the extensions. Of some assignments a stage of the theory indeed says that
the assignment is of a certain type, but in typical cases it does not
provide the
whole extension of the types. That the assignment $\alpha$ does not belong to
the (known) extension of $ \tau$, does not imply that the actual stage of the
theory is committed to the truth of the negated proposition $\neg (\alpha: \tau
)$. To indicate this commitment I introduce anti-extensions.
\begin{subsubsection}{Extensions and anti-extensions}
Due to the partiality of the information a stage of a theory provides, it
is useful to
introduce one additional notion, that of the anti-extension. Now, if a
stage of a
theory says that the assignment $\alpha$ is of the type $\tau$ that means that
the assignment $\alpha$ belongs to the extension of the type, if on the contrary
the stage of the theory says that the assignment $\alpha$ is {\em not} of
the type
$\tau$ that means that the assignment $\alpha$ belongs to the anti-extension of
the type. A stage of a theory is consistent iff for all types the
intersection of its
extension and anti-extension is empty. As the theory extends new assignments
might be added both to the extensions and the anti-extensions of the type.
The notion of a context is defined in two phases. First I define conjunctive
context, i.e. contexts created by simultaneous pieces of information. These
pieces
of information can be featured by the extensions and anti-extensions of types. A
context is a set of (alternative) conjunctive contexts.
\begin{definition}
Let ${\mathbf TYPE}$ be the set of types and $\mathbf {ASSIGN}$ be the set of
assignments. If $\gamma$ is a function from $\mathbf {TYPE}$ to the set of
assignment set pairs, i.e. to $(POW(\mathbf {ASSIGN}))^2$ then $\gamma$ is a
conjunctive context.
\end{definition}
\begin{definition}
A conjunctive context $\gamma$ is consistent if for all $\tau\in \mathbf
{TYPE}$, $\gamma(\tau)=\langle\epsilon,\eta\rangle$ it holds that
$\epsilon\bigcap\eta=\emptyset$
\end{definition}
\begin{definition}
$\Gamma$ is a context, if for all $\gamma \in \Gamma$, $\gamma$ is a
conjunctive context. A context $\Gamma$ is consistent iff there is a
$\gamma\in\Gamma$ such that $\gamma$ is consistent.
The absurd context is the singleton $\{\otimes\}$ where $\otimes (\tau)=
\langle\alpha_{\tau},\alpha_{\tau}\rangle$, and $\alpha_{\tau}$ it the set of
all assignments appropriate for $\tau$
\end{definition}
Now I describe the notion of "truth (and falsity) in a context". I start
with atomic
propositions. A proposition of the form $\sigma\models\iota$ is true if the
situation $\sigma$ indeed supports the infon $\iota$, and false otherwise.
Propositions of this kind are context independent. A proposition of the form
$\alpha : \tau$ is true in a context $\Gamma$ iff for all consistent
$\gamma\in\Gamma$ if $\gamma(\tau)=\langle\epsilon,\eta\rangle$ then
it holds that $\alpha\in\epsilon$. A proposition of the form $\alpha : \tau$ is
false in a context $\Gamma$ iff for all consistent $\gamma\in\Gamma$ if
$\gamma(\tau) =\langle\epsilon,\eta\rangle$ then $\alpha\in\eta$.
The truth and falsity of the negation of a proposition, as well as that of the
conjunction or disjunction of two propositions are defined as usual. IT is
useful
to have the following definition.
\begin{definition}
Let $\Gamma$ be a context and $\tau$ be a type. The extension of $\tau$ in
$\Gamma$ is the intersection of the first coordinates of the $\gamma(\tau)$s
for all $\gamma\in \Gamma$. The anti-extension of $\tau$ in $\Gamma$ is
the intersection of the second coordinates of the $\gamma(\tau)$s for all
$\gamma\in \Gamma$.
\end{definition}
\end{subsubsection}
\end{subsection}
\end{section}
\begin{section}{Two semantics for the language of theories}
In this section I give a two dimensional semantics for the language of theories.
Formulae in the present framework denote propositions of situation theory.
This is the static dimension of their meaning. Formulae also have context
change potential and this is the dynamic dimension of their meaning. These two
dimensions are in fact connected. Realizing the context change potential of a
formula the results in a context , that makes the proposition the formula
denotes
true.
To start the semantics I assume that the situation theoretic universe contains
three ``logical'' types of types, $INST, UNIV, CONST$ The first two of these are
types of types and the third one is a type of type pairs. Let an operation
$N$ is
defined such that $N$ on the set of types such that $N$ preserves arity and the
extension of a type $\tau$ is the anti-extension of the type $N(\tau)$ and the
extension of $N(\tau)$ is the anti-extension of the type $\tau$. I assume
furthermore that the language of theories and the situation theoretic
universe is
connected by an interpretation function $IP$ so that
\begin{enumerate}
\item If $a_{n}$ is a sequence of individual constant of LOFOL then
$IP(a_{n})=\alpha$ where $\alpha\in \mathbf {ASSIGN}$
\item If $x_{n}$ is a sequence of individual variable of LOFOL then
$IP(x_{n})=\xi$ is an assignment that assigns parameters to natural
numbers.
\item If $P^{n}$ is an n argument predicate constant of the language of
FOL then
$IP(P^{n})=\Pi$ where $\pi\in {\mathbf TYPE}\setminus\{INST, UNIV,
CONST\}$ such that an assignment $\alpha$ is appropriate for $\pi$ only is
$|DOM(\alpha)| = n$
\end{enumerate}
\begin{subsection}{Denotational semantics}
Let $\phi$ be a formula of the language of theories. $\lsem\phi\rsem$ is the
denotation of $\phi$. I define these semantic values inductively.
\begin{definition}
\begin{enumerate}
\item $\lsem P(a_{1},..,a_{n})) \rsem =
\langle\alpha_{1},...,\alpha_{n}\rangle
: \Pi$
\item $\lsem\neg (P(a_{1},..,a_{n})) \rsem
=\langle\alpha_{1},...,\alpha_{n}\rangle :N(\Pi)$
\item $\lsem A\wedge B \rsem =\lsem A \rsem \lsem \wedge B \rsem $
\item $\lsem A\vee B \rsem =\lsem A \rsem \lsem \vee B \rsem $
\item $\lsem\forall x[A(x)]\rsem =(\lambda (IP(x))[\lsem A(x)\rsem]): UNIV$
\item $\lsem\exists x[A(x)]\rsem =(\lambda (IP(x))[\lsem A(x) \rsem]): INST$
\item $\lsem\mathbf{Q}x(\A(x);\B(x))\rsem =\\
((\langle (\lambda (IP(x))[\lsem A(x) \rsem]),(\lambda (IP(x))[\lsem B(x)
\rsem])\rangle) : CONST)\\
\wedge ((\langle N((\lambda (IP(x))[\lsem B(x) \rsem]), N(\lambda
(IP(x))[\lsem A(x) \rsem])\rangle) : CONST )$
\end{enumerate}
\end{definition}
Comment: The last clause in this list means that a generically quantified
formula
of the language, an empirical generalization of the theory introduces {\em two}
constraints. The one of these can be paraphrased as ``$A$s are $B$s'' and the
other one as the ``not $B$s are not $A$s''.
\begin{definition}
Propositions either of the following two forms are called $\tau$ constraints
$\langle\theta,\tau\rangle : CONST$ or ($\langle\theta, N(\tau)\rangle :
CONST$ The former is called a positive $\tau$ constraint the latter one a
negative $\tau$ constraint.
\end{definition}
\end{subsection}
\begin{subsection}{Dynamic semantics}
The dynamic semantic tradition features sentence meanings in terms of context
change potentials. In the present paper context change potentials for the
language
of theories are presented in two dimensions.The first dimension covers the
effects of updating a context with a formula, and the second dimension deals
with the side-effects of the update process.
Let $\Gamma$ be a context, $ A$ a formula of the language of theories, and let
$\Gamma[A]$ denote the context $\Gamma$ is transformed to under the
influence of $A$. The formal definitions are somewhat lengthy so I live them to
the full paper.The ``effect dimension'' of context change potentials of the
formulae of the language of theories is defined so that it results in the
minimal
change in the context that is required to guarantee that the propositions
denoted
by the formulae become true after the update. These changes are fairly simple,
they boil down to add, if necessary, one or two new elements to the
extensions or
anti-extensions of the relevant types.
The side-effect dimension of updates make sure that types that are in fact
instantiated really belong to the extension of $\mathbf {INST}$, and all the
relevant instances of a universal type are taken care of.
\begin{definition}
The update of the context $\Gamma$ with the formula $A$ is
$\Gamma\uparrow A\uparrow $ such that it for all $\gamma\in
\Gamma\uparrow A\uparrow $ and for all $\tau\in TYPE$ there is a $\gamma^{-
}\in\Gamma [A] $ such that $\gamma (\tau) =\langle\epsilon,\eta\rangle$
and $\gamma^{-}(\tau)\langle\epsilon^{-},\eta^{-}\rangle$ implies that
$\epsilon^{-}\subseteq\epsilon,\eta^{-}\subseteq\eta$ and $\gamma$ respects
both the existential and the universal side-effects of A
\end{definition}
\end{subsection}
\end{section}
\begin{section}{Semantics for the language of tests}
In this, most important, part of the present paper the inferential properties of
empirical generalization are characterized in connection with the tests, the
triggers that fire them.
To give the formal semantics for the language of tests few more definitions are
needed.
\begin{definition}
A sequence of $\tau$ constraints $\langle C_1,...,C_n\rangle $ form a $\tau$
constraint chain in the context $\Gamma$ iff all of the propositions
$C_{1},...,C_{n}$ are true in $\Gamma$, and in case $C_{i}$ a positive $\tau$
constraint both $C_{i-1}$ and $C_{i+1}$ are negative $\tau$ constraints
($1