\documentstyle[theapa,jair,twoside,url,11pt]{article}
%\documentstyle[chicagob,url,11pt]{article}
\input{defn}
\input{bghkmac}



\newcommand{\Cond}{\rightarrow}
\newcommand{\Poss}{\mbox{Poss}}
\newcommand{\Pl}{\mbox{Pl}}
\newcommand{\sR}{\rhd}
\newcommand{\intension}[2]{[\![ #2 ]\!]_{ #1}}
\newcommand{\LPhi}{\cal L}
\renewcommand{\world}{w}
\newcommand{\worldw}{w}
\newcommand{\worldu}{u}
\newcommand{\worldv}{v}
\newcommand{\Worlds}{W}
\newcommand{\WorldsU}{U}
\newcommand{\WorldsV}{V}
\newcommand{\succs}{\succ^s}
\newcommand{\succeqs}{\succeq^s}
\newcommand{\best}{{\rm best}}


\jairheading{7}{1997}{1--24}{2/97}{7/97}
\ShortHeadings{Relative Likelihood in Partially-Ordered Preferential Structures}{Halpern}
\firstpageno{1}



\begin{document}

\title{Defining Relative Likelihood in Partially-Ordered Preferential
Structures}
\author{\name Joseph Y.\ Halpern \email halpern@cs.cornell.edu\\
\addr   Cornell University, Computer Science Department\\
   Ithaca, NY 14853\\
   http://www.cs.cornell.edu/home/halpern
}

\maketitle

\begin{abstract}
Starting with a likelihood or preference order on worlds,
we extend it to a likelihood ordering on sets of worlds
in a natural way, and examine the resulting logic.
Lewis earlier considered such a notion
of relative likelihood in the context of studying counterfactuals,
but he assumed a total preference order on worlds.
Complications arise when examining partial orders that are not
present for total orders.  There are subtleties involving the
exact approach to lifting the order on worlds to an order on
sets of worlds.  In addition, the axiomatization of the logic
of relative likelihood in the case of partial orders gives insight
into the connection between relative likelihood and default reasoning.
\end{abstract}


\section{Introduction}
A {\em preference order\/} $\succeq$ on a set $W$ of worlds is a
reflexive, transitive relation on $W$.
%A partially (pre)ordered by a reflexive, transitive relation $\succeq$.
%\footnote{A partial order $R$ is typically assumed to be reflexive,
%transitive, and {\em anti-symmetric}
%(so that if $(a,b) \in R$ and $(b,a) \in R$, then
%$a=b$).  We are not assuming that $\succeq$ is anti-symmetric here,
%which is why it is a {\em preorder}.}
%semantics to conditional logic \cite{Lewis73} and nonmonotonic logic
%\cite{KLM}.
Various readings have been given to the $\succeq$ relation in the
literature; $u \succeq v$ has been interpreted as ``$u$ at least as
preferred or desirable as $v$'' \cite{KLM,DSW} (it is this reading that
leads to the
term ``preferential structure''), ``$u$ at least as normal (or typical)
as $v$'' \cite{Boutilier94AIJ1}, and ``$u$ is no more remote from
actuality than $v$'' \cite{Lewis73}.
In this paper, we focus on one other interpretation, essentially
also considered by Lewis \citeyear{Lewis73}.  We interpret $u \succeq v$
as meaning ``$u$ is at least as likely as $v$''.%
\footnote{There is a tradition, starting with Lewis \citeyear{Lewis73},
of
taking $u \preceq v$, rather than $u \succeq v$, to mean that $u$ is as
preferred or as desirable as $v$.  This last reading historically comes
from the interpretation of the preferred world as being less far from
actuality.  Since there seems to be a split in the reading in the
literature, and $\succeq$ has traditionally been taken to mean ``at least
as likely'' in the literature on qualitative probability
\cite{Fine,Gardenfors}, we take this reading here.}
%joe2
Interestingly, all these readings seem to lead to much the same
properties.

In the literature, preference orders have been mainly used
to give semantics to conditional logics \cite{Lewis73} and,
more recently, to nonmonotonic logic \cite{KLM}.  The basic modal
operator in these papers has been a conditional $\Cond$, where
$p \Cond q$ is interpreted as ``in the most preferred/normal/likely
worlds satisfying $p$, $q$ is the case''.  However, if we view
$\succeq$ as representing likelihood, then it seems natural to define a
binary operator $\gg$ on formulas such that $\phi \gg \psi$ is interpreted
as ``$\phi$ is more likely than $\psi$''.  Lewis \citeyear{Lewis73}
in fact did define such an operator, and showed how it related
to $\Cond$.  However, he assumed that $\succeq$ was {\em total};
%{\em total\/} preorder on worlds, not a partial preorder.
that is, he assumed that for all worlds $w, w' \in
W$, either $w \succeq w'$ or $w' \succeq w$.
But in many cases in preferential or likelihood reasoning, it seems
more appropriate to allow the preference order to be partial.
It may well be that an agent finds two situations incomparable as
%partial preorder rather than a total preorder.
far as normality or likelihood goes.  For example, one situation may be
better in one dimension but worse in another.

As we show in this paper, there are some subtleties involved
in starting with a {\em partial\/} preference order on
worlds.  What we are ultimately interested is not an ordering on worlds,
but an ordering on {\em sets\/} of worlds.  To make sense of a statement
like $\phi \gg
\psi$, we need to compare the relative likelihood of the set
of worlds satisfying $\phi$ to that of
the set satisfying $\psi$.
\commentout{
Notice that for technical reasons (that
should shortly become clear), we take as our basic primitive a strict
comparison (``more likely'') rather than the nonstrict version (``at
least as likely'').  Given a preference order $\succeq$ on worlds, it is
easy
to define a strict order $\succ$ on worlds: $u \succ v$ if $u \succeq
v$ and  not($v \succeq u$).  Moreover, it is straightforward to extend
$\succeq$ and $\succ$ to preorders $\succeqs$ and $\succs$ on sets of
worlds.  (The superscript $s$ is for ``set''.)
%joe1: Emil change
%Roughly speaking,
We say that $U \succeqs V$ if for every
world $v \in V$, there is a world $u \in U$ such that $u \succeq v$;
we can similarly define $\succs$, using $\succ$.}
Unfortunately, there are many possible ways of extending a preference
order on worlds to one on sets of worlds.  We focus here on two
particular choices, which both agree with the definition given by Lewis
in the case that the preference order on worlds is total, but differ in
general.  We define $\gg$ using the definition that allows us to make
the most interesting to work in default reasoning.

%Define $U \succ' V$ if $U \succeqs V$ and not($V \succeqs U$).  An
%obvious question is whether $\succ'$ and $\succs$ are equivalent.
%It is not hard to show that they are if $\succeq$, the original
%preorder
%on worlds, is a total preorder.  (This is precisely the case considered
%by Lewis.)  On the other hand, it is also not hard to construct a
%counterexample showing that, in general, they
%are different.  While $U \succs V$ implies $U \succ' V$, the converse
%does not always hold.
%While both $\succs$ and $\succ'$ are reasonable
%notions, using $\succs$ allows us to make more interesting connections
%to conditional logic, so
%that is what we focus on in this paper.

We then turn our attention to axiomatizing
%More interesting observations arise when we try to axiomatize
the likelihood operator.  Lewis provided an axiomatization for the
%joe3
%case of total preorders; we provide one here for the case of partial
%case of total preference orders; we provide one here for the case where
case where
the preference order is partial.  The key axioms used by
Lewis were transitivity:
$$(\phi_1 \gg \phi_2) \land (\phi_2 \gg \phi_3) \rimp (\phi_1 \gg
\phi_3),$$
and the {\em union property}:
$$(\phi_1 \gg \phi_2) \land (\phi_1 \gg \phi_3) \rimp (\phi_1 \gg
(\phi_2 \lor \phi_3)).$$
This latter property is characteristic of possibility logic
\cite{DuboisPrade88}.  In the partially ordered case, these axioms do
not suffice.  We need the following axiom:
$$((\phi_1 \lor \phi_2) \gg \phi_3) \land ((\phi_1 \lor \phi_3) \gg
\phi_2) \rimp  (\phi_1 \gg (\phi_2 \lor \phi_3)).$$
It is not hard to show that this axiom implies transitivity and the
union property (in the presence of the other axioms), but it is not
equivalent to them.  Interestingly, it is the property captured by this
axiom that was isolated in \cite{FrH5Full} as being the key feature needed
for a likelihood ordering on sets to be appropriate for doing default
reasoning in the spirit of \cite{KLM}.  Thus, by
%joe2
%allowing the generality of partial preorders,
considering preference orders that are partial,
we are able to clarify the connections between $\gg$,
$\Cond$, and default reasoning.

The rest of this paper is organized
as follows.  In Section~\ref{partial}, we consider how to go from an
%partial preorder on worlds to a partial
%preorder on sets of worlds, focusing
%on the differences between partial and total preorders.
ordering on worlds to one on sets of worlds, focusing on the differences
between total and partial preference orders.   In
Section~\ref{logic}, we present a logic for reasoning about relative
likelihood and provide a natural complete axiomatization for it.  In
Section~\ref{comparison}, we relate our results to other work on
relative likelihood, as well as to work on conditional logic and
nonmonotonic reasoning.  We conclude in Section~\ref{conclusion}.
Proofs of the technical results can be found in Appendix~\ref{proofs}.

\section{From Preorders on Worlds to Preorders on Sets of Worlds}\label{partial}
We capture the likelihood ordering on a set $\Worlds$ of possible worlds
by a {\em partial preorder\/}---that is, a
reflexive and transitive relation---$\succeq$ on $\Worlds$.%
\footnote{A partial order $R$ is typically assumed to be reflexive,
transitive, and {\em anti-symmetric}
(so that if $(a,b) \in R$ and $(b,a) \in R$, then
$a=b$).  We are not assuming that $\succeq$ is anti-symmetric here,
which is why it is a {\em preorder}.}
We typically write $\world' \succeq \world$ rather than
$(\world', \world) \in \, \succeq$.  As usual, we often write $u \preceq
v$ rather than
$v \succeq u$, and take $u \succ v$ to be an abbreviation for
$u \succeq v$ and not($v \succeq u$), and $u \prec v$ to be an
abbreviation for $v \succ u$.  The relation $\succ$ is a {\em strict
partial order\/}, that is, it is an irreflexive (for all $w$, it is
not the case that $w \succ w$) and
transitive relation on $W$.  We say that $\succ$ is the strict partial
order {\em determined by\/} $\succeq$.

As we said in the introduction, we think of $\succeq$ as providing a
likelihood, or preferential, order on the worlds in $\Worlds$.
Thus, $w \succeq w'$ holds if $w$ is at least as
likely/preferred/normal/close to actuality
as $w'$.
Given this interpretation, the fact that $\succeq$ is
assumed to be a partial preorder is easy to justify.
For example, transitivity just says that if $\worldu$ is at least
as likely
as $\worldv$, and $\worldv$ is at least as likely as $\worldw$, then
$\worldu$ at least as likely as $\worldw$.
Notice that since $\succeq$ is a {\em partial\/} preorder, there may be
some pairs of worlds $w$ and $w'$ that are incomparable according to
$\succeq$.  Intuitively, we may not be prepared to say that either one
is likelier than the other.  We say that $\succeq$ is a {\em total
preorder\/} (or {\em connected}, or a {\em linear preorder}) if for all
worlds $w$ and $w'$, either $w \succeq w'$ or $w' \succeq w$.

Since we have added likelihood to the worlds, it seems reasonable to
also add likelihood to the language, to allow us to say ``$\phi$ is
more likely than $\psi$'', for example.
But what exactly should this
mean?  Although having $\succeq$ in our semantic model allows us to say
that one world is more likely than another, it does not immediately tell
us how to say that a set of worlds is more likely than another set.
But, as we observed in the introduction, this is just what we need to
make sense of ``$\phi$ is more likely than $\psi$''.

How should we extend a likelihood ordering on worlds to one on sets of
worlds?  Clearly we want to do so in a way that preserves the ordering
on worlds.  That is, using $\rhd$ to denote the ordering sets, we would
certainly expect that $u \succeq v$ would imply $\{u\} \rhd \{v\}$.  We
could impose a few other minimal requirements, but they certainly would
not be enough to uniquely determine an ordering on sets.
For example, here are two general approaches;
to distinguish them, we put subscripts on $\rhd$.
\begin{enumerate}
\item Define $\rhd_1$ so that $U \rhd_1 V$ if for all $u \in U$ and all
$v \in V$,
we have $u \succeq v$.  We can define a strict partial order in this
spirit
in two distinct ways.
\begin{enumerate}
\item By considering the analogous procedure to that used to get
$\succ$ from $\succeq$: We define $\rhd_2$ so that $U \rhd_2 V$ if $U
\rhd_1 V$ and not($V
\rhd_1 U)$.  We call this the {\em standard method\/} below.
\item By replacing $\succeq$ in the definition of $\rhd_1$ by $\succ$:
We define $\rhd_3$ so that $U \rhd_3 V$ if for all $u \in U$ and all $v
\in V$, we have $u \succ v$.  We call this the {\em alternative
method}.
\end{enumerate}
\item  Define $\rhd_4$ so that $U \rhd_4 V$
if for all $v \in V-U$, there is some $u \in U-V$ such that $u \succeq
v$.  Note that this approach focuses on the symmetric difference between
$U$ and $V$.  There are again two ways of getting a
strict partial order.
\begin{enumerate}
\item The standard method gives us $U
\rhd_5 V$ if $U \rhd_4 V$ and not($V \rhd_4 U$).
\item The alternative method gives us $U \rhd_6 V$ if for all $v \in
V-U$ there is some $u \in U-V$ such that $u \succ v$.
\end{enumerate}
\end{enumerate}
The first approach ($\rhd_1$) was used by Doyle, Shoham, and Wellman
\citeyear{DSW}
in defining a logic of relative desire, starting with a preference order
on worlds.  Unfortunately, as
they themselves point out, these
relations are too weak to allow us to make important distinctions.
They go on to define other notions of comparison,
but these are more tuned to their applications, and not in the spirit of
the notions we are considering here.

The second approach (typically $\rhd_4$ and $\rhd_5$) has been widely
used in various applications in the literature.  For example,
\begin{itemize}
\item
Dershowitz and Manna \citeyear{DM79} use it to define on ordering on
multisets, which is then used to provide a technique for proving program
termination.
\item Przymusinski \citeyear{Przym87} uses it to order models of
a database.
\item Brass \citeyear{Brass91}, Cayrol, Royer, and
Saurel \citeyear{CRS92}, Delgrande
\citeyear{Delgrande94}, and Geffner \citeyear{geffner92} all use it
to help model various aspects of default reasoning.
\end{itemize}

In this paper, we focus on a variant of the second approach,
essentially due to Lewis \citeyear{Lewis73},
which has interesting connections to default reasoning.
Roughly speaking, we take
$\WorldsU$ to be more likely than $\WorldsV$ if for every world
in $\WorldsV$, there is a more likely world in $\WorldsU$.

To make this precise,
%joe1: Emil change
%first assume that $\Worlds$ is finite.
if $\WorldsU, \WorldsV \subseteq \Worlds$, we
write $\WorldsU \succeqs \WorldsV$ if for
every world $\worldv \in \WorldsV$, there is a world
$\worldu \in \WorldsU$ such that $\worldu \succeq \worldv$.  It is easy
to check that $\succeqs$
%joe1:
%defined on finite sets
is a partial preorder,
that is, it is reflexive and transitive.
(The superscript $s$ is for ``set''.)
Moreover, if $\succeq$
is a total preorder, then so is $\succeqs$.
Finally, as
we would expect, we have $\worldu \succeq \worldv$ iff $\{\worldu\}
\succeqs
\{\worldv\}$, so the $\succeqs$ relation on sets of worlds can be viewed
as a generalization of the $\succeq$ relation on worlds.

We can then apply both the standard method and the alternative method to
define a strict partial order.  The standard method gives us the
relation $\succ'$,
%defined in the introduction,
where $U \succ' V$ holds if $U \succeqs V$ and not($V \succeqs U$).
The alternative method gives us the relation $\succs$ defined
on finite sets by taking
$U \succs V$ to hold if $U$ is nonempty, and for every world $\worldv
\in \WorldsV$, there
is a world $\worldu \in \WorldsU$ such that $\worldu \succ \worldv$.
(The reasons that $U$ is taken to be nonempty and that the definition is
restricted to finite sets are discussed below.)

How do these various approaches compare?  Clearly $U \rhd_1 V$
implies $U \succeqs V$, although the converse does not hold in general;
$\rhd_1$ is a very weak ordering.  As a consequence, $\rhd_2$ and
$\succ'$ are incomparable, as are $\rhd_3$ and $\succs$.
Similar remarks apply to $\rhd_4$.
Again, it is easy to see that $U \rhd_4 V$ implies $U \succeqs V$.  On
the other hand, the two notions are not equivalent.  For example,
suppose $v \succ v'$.  Then $\{v\} \succeqs \{v,v'\}$, but we do not
have $\{v\} \rhd_4 \{v,v'\}$.

Why are we focusing on $\succeqs$, $\succ'$, and $\succs$ here, rather
than $\rhd_1$--$\rhd_6$ (or some other notion)?
>From a likelihood viewpoint, they all seem to be reasonable; our
intuitions regarding extending likelihood from worlds to sets of worlds
do not seem to be that well developed.
It may be possible to motivate $\succeqs$ as the finest relation
extending $\succeq$ that has certain properties, but that was not in
fact our motivation here.  Rather, our interest is motivated by the deep
connections between $\succ'$ and $\succs$ and certain approaches to
nonmonotonic reasoning.  Having said that, many of the questions that we
consider here could perfectly well be explored using
$\rhd_1$--$\rhd_6$.  With that apology, we do not discuss
$\rhd_1$--$\rhd_6$ further in this paper, except for the odd remark.

We have explained that there are two methods for getting a strict
partial order on sets of worlds from a partial order on worlds.   But
are the standard method and the alternative method really so different?
It is easy to see that
$u \succ v$ iff $\{u\} \succs \{v\}$ iff $\{u\} \succ' \{v\}$.  
(This is true for $\rhd_2$, $\rhd_3$, $\rhd_5$, and $\rhd_6$ as well.)
Thus,
$\succs$ and $\succ'$ agree on singleton sets and extend the $\succ$
relation on worlds.  Moreover, both $\succs$ and $\succ'$ are strict
partial orders on finite sets.  (The requirement that $U$ must be
nonempty in the definition of $U \succs V$ is there to ensure that we do
not have $\emptyset \succs \emptyset$; strictly speaking, we should
have also added it to the definitions of $\rhd_3$ and $\rhd_6$ to
ensure that they were strict partial orders.)
As shown in Lemma~\ref{agree},
$\succ'$ and $\succs$ are in fact identical if the
underlying preorder $\succeq$ on worlds is a total preorder.
However, as the following
example shows, $\succs$ and $\succ'$ are not identical in general.

\xam\label{inequivalent} Suppose $\Worlds = \{w_1, w_2\}$, and
$\succeq$ is such that $w_1$ and $w_2$ are incomparable.  Then
it is easy to see that $\{w_1,w_2\} \succ' \{w_1\}$.  However, it is not
the case that $\{w_1,w_2\} \succs \{w_1\}$, since there is no
element of $\{w_1, w_2\}$ that is strictly more likely than $w_1$.%
\footnote{We remark that similar results hold for $\rhd_5$ and $\rhd_6$.
They are identical if the underlying order on worlds is a total
preorder, and this example can also be used to show that they differ if
the underlying order is partial.}
\exam


Notice that we were careful to define $\succ$ as we did only on finite
sets.  The following example illustrates why:

\xam\label{infinite}
Let $\Worlds_\infty =  \{w_0, w_1, w_2, \ldots\}$, and suppose that
$\succeq$ is such that
$$w_0 \prec w_1 \prec w_2 \prec \ldots$$
Then it is easy to see that if we were to apply the definition of
$\succs$ to infinite sets, then we would have $\Worlds_\infty \succs
\Worlds_\infty$, and $\succs$ would not be irreflexive.%
\footnote{Similar problems arise for $\rhd_6$ when dealing with infinite
sets, and the solution for $\succs$ described in
Definition~\ref{domination} can be applied to $\rhd_6$ as well.}
\exam

The approach for extending the definition of $\succs$ to infinite sets
is essentially due to Lewis \citeyear{Lewis73} (who did it for the case
of total preorders). The idea is to say that in order
to have $U \succs V$, it is not enough that for every element $v$ in $V$
there is some element $u$ in $U$ that is more likely than $v$.
This definition is what allows $\Worlds_\infty \succ \Worlds_\infty$
in Example~\ref{infinite}.  Notice that in the finite case,
it is easy to see that if $U \succs V$, then for every element $v$ in $V$,
there must some $u \in U$ such that, not only do we have $u \succ v$,
but $u$ {\em dominates\/} $V$ in that for no $v' \in V$ do we have $v'
\succ u$.  It is precisely this domination condition that does not hold
in Example~\ref{infinite}.  This observation provides the motivation for
the official definition of
%$\succeqs$ and
$\succs$, which applies in
both finite and infinite domains.

\dfn\label{domination} Suppose $\succeq$ is a partial preorder on $W$,
$U, V \subseteq W$, and  $w \in W$.  We say that $w$ {\em dominates\/}
$V$ if for no $v \in V$ is it the case that $v \succ w$.
(Notice that if
$\succeq$ is a total preorder, this is equivalent to saying that $w \succeq
v$ for all $v \in V$.)
%We say $w$
%{\em
%strictly dominates\/} $V$ if
%for no $v \in V$ is it the case that $v \succeq w$.  (For total
%preorders, this amounts to saying that $w \succ v$ for all $v \in V$.)
%joe1: Emil change
%We write $U \succeqs
%V$ if,  for all $v
%\in V$, there
%exists $u \in U$ such that $u \succeq v$ and $u$ dominates $V$.
We write $U \succs V$ if  $U$ is nonempty and, for all $v
\in V$, there
exists $u \in U$ such that $u \succ v$ and $u$ dominates $V$.
%joe1: Emil change
%Finally, we define $U \succ' V$ if $U \succeqs V$ and not($V
%\succeqs U$).
\edfn

%joe1:
%It is easy to see that these definitions of $\succeqs$, $\succs$, and
It is easy to see that this definition of $\succs$
agrees with our
earlier definitions if $U$ and $V$ are finite.

We now collect some properties of $\succs$, $\succ'$, and $\succeqs$.
To do this, we need a few definitions.
We say that a relation $\rhd$ on
$2^\Worlds$ (not necessarily a preorder) is {\em qualitative\/} if
$(V_1 \union V_2) \sR V_3$ and $(V_1 \union V_3) \sR V_2$ implies $V_1
\sR (V_2 \union V_3)$.  We say that $\rhd$ {\em satisfies the union
property\/} if $V_1 \sR V_2$ and $V_1 \sR V_3$ implies $V_1 \sR
(V_2 \union V_3)$.
We say that $\rhd$ is {\em orderly\/} if
$U \sR V$, $U' \supseteq U$, and $V' \subseteq V$ implies
$U' \sR V'$.
We provide some intuition for these properties following
Proposition~\ref{precproperties}, after showing how they
help us characterize $\succs$, $\succ'$, and $\succeqs$.
% We start by showing that orderly
%qualitative relations always have the union property and are transitive.

\lem\label{qualitative} If $\rhd$ is an orderly qualitative relation
on $2^{\Worlds}$, then $\rhd$ is transitive and satisfies the union
property.
\elem

\prf See Appendix~\ref{proofs}. \eprf

The converse to Lemma~\ref{qualitative} does not hold.
Indeed, an orderly strict partial order on $2^W$ may satisfy the union
property and still not be qualitative.
For example, suppose $W = \{a,b,c\}$, and we have
$\{a,b\} \sR \{c\}$, $\{a,c\} \sR \{b\}$, $\{a,b,c\} \sR \{b\}$,
$\{a,b,c\} \sR \{c\}$, and $\{a,b,c\} \sR \{b,c\}$.  It can easily
be checked that $\rhd$ is an orderly strict partial order that
satisfies the union property, but is not qualitative.

With these definitions in hand, we can state the key properties of the
relations we are interested in here.
\pro\label{precproperties}
\begin{itemize}
\item[(a)] If $\succeq$ is a partial preorder on $\Worlds$, then
$\succeqs$ is an orderly partial preorder on $2^{\Worlds}$ that
satisfies the union property.
\item[(b)] If $\succeq$ is a partial preorder on $\Worlds$, then
$\succ'$ is an orderly strict partial order on $2^{\Worlds}$.
\item[(c)] If $\succ$ is a strict partial order on $\Worlds$, then
$\succs$ is an orderly qualitative strict partial order on $2^{\Worlds}$.
\end{itemize}
\epro

\prf See Appendix~\ref{proofs}. \eprf

%There are several observations worth making regarding this result.
We can now discuss how to interpret the properties we have been
considering in light of this result.

To the extent that we think of $\rhd$ as meaning ``more likely than'',
then orderliness is a natural property to require.  If $U$ is more
likely than $V$, then certainly any superset of $U$ should be more
likely than any subset of $V$.  It is thus not surprising that all three
of the relations we have defined are orderly.

Clearly the union property generalizes to arbitrary finite unions.
That is, if $\rhd$ satisfies the union property and $A \rhd B_i$, $i =
1, \ldots, n$, then $A \rhd B_1 \union \ldots \union B_n$.  In
particular, if $\worldu \succeq
\worldv_j$ for $j = 1, \ldots, N$, then $\{\worldu\} \succeqs
\{\worldv_1, \ldots, \worldv_N\}$,
no matter how large $N$ is, and similarly if we replace $\succeq$ by
$\succ$ (since the fact that $\succs$ is qualitative means that it
satisfies the union property, by Lemma~\ref{qualitative}).
This is very different from
probability, where sufficiently many
``small'' probabilities eventually can dominate a ``large'' probability.
This suggests that $\worldu \succ \worldv$ should perhaps be interpreted
as ``$\worldu$ is {\em much\/} more likely than $\worldv$''.
More generally, if $\rhd$ satisfies the union property, then $U \rhd V$
can be interpreted as meaning that $U$ is much more likely than $V$.
In this sense, the notion of
likelihood corresponding to $\succs$ or $\succeqs$
is closer to possibility \cite{DuboisPrade88}
than probability, since the relation ``more possible than'' satisfies
the union property.

Note that, in general, $\succ'$ does {\em not\/} satisfy
the union property.  In Example~\ref{inequivalent}, we
have $\{w_1,w_2\} \succ' \{w_1\}$
and $\{w_1,w_2\} \succ' \{w_2\}$, but we do not have $\{w_1,w_2\} \succ'
\{w_1,w_2\}$.

The qualitative property is somewhat more difficult to explain intuitively.
Of the three relations we are
considering, only the $\succs$ relation satisfies it.  The fact that
$\succ'$ does not satisfy it follows from Lemma~\ref{qualitative},
together with the observation that
$\succ'$ does not satisfy the union property.
Example~\ref{inequivalent} also shows that $\succeqs$ is not
qualitative, since if it were, we could conclude from $\{w_1,w_2\}
\succeqs \{w_2\}$ (taking $V_1 = \{w_1\}$ and $V_2 = V_3 = \{w_2\}$
in the definition of qualitative) that $\{w_1\} \succeqs \{w_2\}$, a
contradiction.
Our interest in the qualitative property stems
from the fact that, in a precise sense, it is the property that
characterizes $\succs$.  It first arose in \cite{FrH5Full}, where it was
shown to be the key property required of a generalization of probability
called {\em plausibility\/} to capture default reasoning.  This is
discussed in more detail in Section~\ref{comparison}.
%This example also shows that $\succeqs$ is not
%qualitative, since if it were, we could conclude from $\{w_1,w_2\}
%\succeqs \{w_2\}$ (taking $V_1 = \{w_1\}$ and $V_2 = V_3 = \{w_2\}$
%in the definition of qualitative) that $\{w_1\} \succeqs \{w_2\}$, a
%contradiction.

If $\succeq$ is a total preorder, then we get further connections between
these notions.  Before we discuss the details, we need to define the
analogue of total preorders in the strict case.
A relation $\rhd$ on an arbitrary set $\Worlds'$ (not necessarily
of the form $2^\Worlds$) is {\em modular\/} if
$w_1 \sR w_2$ implies that, for all $w_3$, either $w_3 \sR w_2$ or
$w_1 \sR w_3$.
Modularity is the ``footprint'' of a total preorder
on the strict order determined by it.  This is made precise in the
following lemma.

\lem\label{modular} If $\succeq$ is a total preorder, then the strict
partial order $\succ$ determined by $\succeq$ is modular.
Moreover, if $\rhd$ is a modular, strict partial order on $\Worlds$,
then there is a total preorder $\succeq$ on $\Worlds$ such that
$\rhd$ is the strict partial order determined by $\succeq$. \elem

\prf See Appendix~\ref{proofs}. \eprf

Modularity is preserved when we lift
the preorder from $W$ to $2^W$.

\lem\label{modular1} If $\succ$ is a modular relation on $W$, then
$\succs$ is a modular relation on $2^W$. \elem

\prf See Appendix~\ref{proofs}. \eprf

Although we showed that the converse to Lemma~\ref{qualitative} does not
hold in general for strict partial orders, it does hold for orders that
are modular.

\lem\label{modular2} If $\rhd$ is a modular strict partial order and
satisfies the union property, then $\rhd$ is qualitative. \elem

\prf See Appendix~\ref{proofs}. \eprf

As shown in \cite{FrH5Full}, there is a connection between
nonmonotonic reasoning, conditional logic, and the qualitative
property.  (This is discussed in Section~\ref{comparison}.)
This relationship is best understood by considering $\succs$, rather
than $\succeqs$ or $\succ'$, which is why we focus on $\succs$ here.
Lewis \citeyear{Lewis73} was able to use
$\succ'$ because he focused on total preorders.  The following lemma makes
this precise.

\lem\label{agree} If $\succeq$ is a total preorder, then $\succs$ and
$\succ'$ agree.
In general, $U \succs V$ implies $U \succ' V$, but the converse does not
hold. \elem

\prf See Appendix~\ref{proofs}. \eprf

We close this section by considering when a preorder on $2^W$ can
be viewed as being generated by a preorder on $W$.  This result turns
out to play a key role in our completeness proof, and emphasizes
the role of the qualitative property.

\thm\label{key}
Let $\F$ be a finite algebra of subsets of $W$ (that is, $\F$ is a
set of subsets of $W$ that is closed under union and complementation and
contains $W$ itself) and let $\rhd$ be an orderly qualitative relation on
$\F$.
\begin{itemize}
\item[(a)] If $\rhd$ is a total preorder on $\F$,
then there is a total preorder $\succeq$ on $W$ such that $\rhd$ and
$\succeqs$ agree on $\F$ (that is, for $U, V \in \F$, we have
$U \sR V$ iff $U \succeqs V$).
\item[(b)] If $\rhd$ is a strict partial order and each nonempty set in
$\F$ has at least $2^{\log(|\F|)^{\log(|\F|)}}$
elements, then there is a partial
preorder $\succeq$ on $W$ such that $\rhd$ and $\succs$ agree on $\F$.
\end{itemize}
\end{theorem}
\prf An {\em atom\/} of $\F$ is a minimal nonempty element of $\F$.
Since $\F$ is finite, it is easy to see that every element of $\F$
can be written as a union of atoms, and the atoms are disjoint.
Part (a) is easy: for each $w \in W$, let $A_w$ be the unique atom
in $\F$ containing $w$.  Define $\succeq$ on $W$ so that
$v \succeq w$ iff $A_v \sR A_w$.  It is easy to see that if $\rhd$ is
a total preorder on $\F$, then $\succeq$ is a total preorder on $W$ and
$\rhd$ agrees with $\succeqs$ on $\F$.  The proof of (b) is considerably
more difficult; see Appendix~\ref{proofs} for details.
\eprf

It is not clear that the requirement that the sets in $\F$ have at least
$2^{\log(|\F|)^{\log(|\F|)}}$ elements is necessary.  However, it
can be
shown that
Theorem~\ref{key}(b) does not hold without some assumptions
on the cardinality of elements in $\F$.   For example, suppose that
the atoms of $\F$ are $A$, $B$, and $C$.
Let $\rhd$ be defined
so that $(B \union C) \sR A$, $W \sR A$,
$X \sR \emptyset$ for all nonempty $X \in \F$, and these are the only
pairs of sets that are in the $\rhd$ relation. It is
easy to see that $\rhd$ is an orderly, qualitative, strict partial order.
However, if $W = \{a,b,c\}$, $A = \{a\}$, $B = \{b\}$,
and $C = \{c\}$, there is no ordering $\succ$ on $W$ such that $\succs$
and $\rhd$ agree on $\F$: it is easy to see that such an ordering $\succ$
must make $a$, $b$, and $c$ incomparable.  But if they are incomparable,
we cannot have $\{b,c\} \succs \{a\}$.  On the other hand, if we allow
$C$ to have two elements, by taking $W = \{a,b,c,d\}$, $A = \{a\}$,
$B=\{b\}$, and $C = \{c,d\}$, then there is an ordering $\succ$ such
that $\succs = \rhd$: we simply take $a \succ c$ and $b \succ d$.

\section{A Logic of Relative Likelihood}\label{logic}
We now consider a logic for reasoning about relative likelihood.
Let $\Phi$ be a set of primitive propositions.
A {\em basic likelihood formula (over $\Phi$)} is one of the form
$\phi \gg \psi$, where $\phi$ and $\psi$ are propositional formulas over
$\Phi$.  We read $\phi \gg \psi$ as ``$\phi$ is more likely than
$\psi$''.  Let $\LPhi$ consist of Boolean combinations of basic
likelihood
formulas.  Notice that we do not allow nesting of likelihood in $\LPhi$,
nor do we allow purely propositional formulas.  There would no
difficulty extending the syntax and semantics to deal with them, but
this would just obscure the issues of interest here.

A {\em preferential structure\/} (over $\Phi$) is a tuple $M =
(\Worlds,\mbox{$\succeq,$}\pi)$, where
$\Worlds$ is a (possibly infinite) set of possible worlds, $\succeq$ is
a partial preorder on $\Worlds$, and $\pi$ associates with each world in
$\Worlds$ a truth assignment to the primitive propositions in $\Phi$.
Notice that there may be two or more worlds with the same truth
assignment.
As we shall see, in general, we need to have this, although in the case
of total preorders, we can assume without loss of generality that there is
at most one world associated with each truth assignment.

We can give semantics to formulas in $\LPhi$ in preferential structures
in a straightforward way.  For a propositional formula $\phi$, let
$\intension{M}{\phi}$ consist of the worlds in $M$ whose truth
assignment satisfies $\phi$.  We then define
$$M \sat \phi \gg \psi \mbox{ if $\intension{M}{\phi} \succs
\intension{M}{\psi}$.}$$
We extend $\sat$ to Boolean combinations of basic formulas in the
obvious way.

Notice that $M \sat \neg(\neg \phi \gg \false)$ iff
$\intension{M}{\neg \phi} = \emptyset$ iff $\intension{M}{\phi} = W$.
Let $K \phi$ be an
abbreviation
for $\neg (\neg \phi \gg \false)$.  It follows that $M \sat K \phi$ iff
$\phi$ is true at all possible
worlds.%
\footnote{$K$ was defined by Lewis \citeyear{Lewis73}, although he wrote
$\Box$ rather than $K$.}

With these definitions, we can provide a sound and complete
axiomatization for this logic of relative likelihood.
Let AX consist of the following axioms and inference rules.

\begin{itemize}
\item[L1.]
All substitution instances of tautologies of propositional calculus
\item[L2.]
$\neg (\phi \gg \phi)$
\item[L3.]
$((\phi_1 \lor \phi_2) \gg \phi_3) \land ((\phi_1 \lor \phi_3) \gg
\phi_2) \rimp (\phi_1 \gg (\phi_2 \lor \phi_3))$
\item[L4.]
$(K(\phi \rimp \phi') \land K(\psi' \rimp \psi) \land (\phi \gg \psi))
\rimp \phi' \gg \psi'$
%joe: another lehmann typo
%From $\varphi$ infer $K_i\varphi$\ \
%joe: Lehmann bug
%rom $\varphi$ infer $K\varphi$\ \
\item[Gen.] $K \phi$, \  for all propositional tautologies $\phi$
%joe
%(Knowledge Generalization)
(Generalization)
\item[MP.]
>From $\varphi$ and $\varphi\rimp\psi$
infer $\psi$\ \  (Modus ponens)
\end{itemize}

L2, L3, and L4 just express the fact that $\succs$ is
%joe!
%irreflexive, orderly, and qualitative, respectively; this is made
irreflexive, qualitative, and orderly, respectively; this is made
precise in the proof of the following result.
The axiom Gen is the analogue of the inference rule ``From $\phi$ infer
$K \phi$'', typically known as generalization.  We do not have this
inference rule here, since our language does not allow nested
occurrences of $\gg$.  Thus, for an arbitrary formula $\phi$, the formula
$K \phi$ is not in our language.  It is in our language only if $\phi$
is propositional; the axiom takes care of this case.

\thm\label{complete1} AX is a sound and complete axiomatization of the
language $\LPhi$ with respect to preferential structures. \ethm

\prf The validity of L1 is immediate.  It is clear that the fact that
$\succs$ is irreflexive and qualitative, as shown in
Proposition~\ref{precproperties}, implies that L2 and L3 are valid.
To see that L4 corresponds to orderliness, note that
if $M \sat K(\phi \rimp \phi') \land K(\psi' \rimp \psi)$ and $\phi \gg
\psi$, then  $\intension{M}{\phi} \subseteq \intension{M}{\phi'}$,
$\intension{M}{\psi'} \subseteq \intension{M}{\psi}$, and
$\intension{M}{\phi} \succs \intension{M}{\psi}$.  Since $\succs$ is
orderly, it follows that $\intension{M}{\phi'} \succs
\intension{M}{\psi'}$, so $M \sat
\phi' \gg \psi'$.  Thus, L4 is valid.  It is also clear that MP and Gen
preserve validity.  Thus, the axiomatization is sound.

The completeness proof starts out, as is standard for completeness
proofs in modal logic, with the observation that it suffices to show
that a consistent formula is satisfiable.  That is, we must show that
every formula
$\phi$ for which it is not the case that $\neg \phi$ is provable from
AX is satisfiable in some preferential structure $M$.  However, the
standard modal logic techniques of constructing a {\em canonical\/}
model (see, for example, \cite{HC}) do not seem to work in this case.
Finding an appropriate partial preorder on worlds is nontrivial.  For
this we
use (part (b) of) Theorem~\ref{key}.  See Appendix~\ref{proofs} for the details.
\eprf

What happens if we start with a total preorder?  Let AX$^M$ consist of AX
together with the obvious axiom expressing modularity:
\begin{itemize}
\item[L5.] $(\phi_1 \gg \phi_2) \rimp ((\phi_1 \gg \phi_3) \lor (\phi_3
\gg
\phi_2))$
\end{itemize}

We say that a preferential structure is {\em totally preordered\/} if it
has
the form $(W, \succeq, \pi)$, where $\succeq$ is a total preorder on $W$.

\thm\label{complete2} AX$^M$ is a sound and complete axiomatization of
the language
$\LPhi$ with respect to totally preordered preferential structures. \ethm
\prf For soundness, we just have to check that L5 is valid in totally
ordered preferential structures.  This is straightforward and left to
the reader.  The completeness proof uses Theorem~\ref{key} again, but is
simpler than the proof of completeness in Theorem~\ref{complete1}.
We leave details to Appendix~\ref{proofs}. \eprf

We remark that in light of Proposition~\ref{modular2}, we can replace
L4 in AX$^M$ by axioms saying that $\gg$ is transitive and satisfies the
union property, namely:
\begin{itemize}
\item[L6.] $(\phi_1 \gg \phi_2) \land (\phi_2 \gg \phi_3) \rimp (\phi_1
\gg \phi_3)$
\item[L7.]  $((\phi_1 \gg \phi_2) \lor (\phi_1 \gg \phi_3)) \rimp
(\phi_1 \gg (\phi_1 \lor \phi_2))$
\end{itemize}
The result is an axiomatization that is very similar to that given by
Lewis \citeyear{Lewis73}.

In the proof of Theorem~\ref{complete1}, when showing that a consistent
formula $\phi$ is satisfiable, the structure constructed may have
more than one world with the same truth assignment.  This is necessary,
as the following example shows.  (We remark that this observation
is closely
related to the cardinality requirements in Theorem~\ref{key}(b).)
\xam\label{nonunique} Suppose $\Phi = \{p,q\}$.  Let $\phi$ be the
formula
$(p \gg (\neg p \land q)) \land \neg ((p \land q) \gg (\neg p \land q))
\land
\neg ((p \land \neg q) \gg (\neg p \land q))$.  It is easy to see that
$\phi$ is satisfied
in a structure consisting of four worlds, $w_1, w_2, w_3, w_4$, such
that $w_1 \succ w_3$, $w_2 \succ w_4$, $p \land q$ is true at $w_1$,
$p \land \neg q$ is true at $w_2$, and $\neg p \land q$ is true at both
$w_3$ and $w_4$.  However, $\phi$ is not satisfiable in any
structure where there is at most one world satisfying $\neg p \land q$.
For suppose $M$ were such a structure, and let $w$ be the world in $M$
satisfying $\neg p \land q$.  Since $M \sat p \gg (\neg p \land q)$, it
must be the case that $\intension{M}{p} \succs \{w\}$.  Thus, there must
be a world $w' \in \intension{M}{p}$ such that $w' \succ w$.  But $w'$
must satisfy one of  $p \land q$ or $p \land \neg q$, so $M \sat ((p
\land q) \gg (\neg p \land q)) \lor ((p \land \neg q) \gg (\neg p \land
q))$, contradicting the assumption that $M \sat \phi$. \exam

It is not hard to see that the formula $\phi$ of Example~\ref{nonunique}
is not satisfiable in a totally preordered preferential structure.  This is
not an accident.

\pro\label{oneworld} If a formula is satisfiable in a totally preordered
preferential
structure, then it is satisfiable in a totally preordered preferential
structure with at most one world per truth assignment. \epro

\prf See Appendix~\ref{proofs}. \eprf

The results of this and the previous section help emphasize the
differences between totally preordered and partially preordered structures.

\section{Related Work}\label{comparison}
The related literature basically divides into two groups (with
connections between them): (a) other approaches to relative likelihood
and (b) work on conditional and nonmonotonic logic.

We first consider relative likelihood.
G\"ardenfors~\citeyear{Gardenfors}
considered a logic of relative likelihood, but he took as primitive
a total preorder on the sets in $2^W$, and focused on connections with
probability.  In particular, he added axioms to ensure that, given a
preorder $\succeqs$ on $2^W$, there was
a probability function $\Pr$ with the property that (in our notation) $U
\succeqs V$ iff $\Pr(U) \ge \Pr(V)$.  Fine \citeyear{Fine} defines a
qualitative notion $\preceq$ of {\em comparative probability}, but like
G\"ardenfors, assumes that the preorder on sets is primitive, and is
largely concerned with connections to probability.

Halpern and Rabin \citeyear{HRab} consider a logic of likelihood where
absolute statements about likelihood can be made ($\phi$ is likely,
$\psi$ is somewhat likely, and so on), but there is no notion of
relative likelihood.

Of course, there are many more quantitative
notions of likelihood, such as
probability, possibility \cite{DuboisPrade88}, ordinal conditional
functions (OCFs) \cite{spohn:88},
and Dempster-Shafer belief functions \cite{Shaf}.  The ones closest
to the relative likelihood considered here are possibility and
OCFs.
Recall that a possibility measure $\Poss$ on $W$ associates with each
world its {\em possibility}, a number in $[0,1]$, such that for $V
\subseteq W$, we have $\Poss(V) = \sup\{\Poss(v): v \in V\}$, with the
requirement that $\Poss(W) = 1$.
Clearly a possibility measure places a total preorder on sets,
and satisfies the union property, since $\Poss(A \union B) =
\max(\Poss(A),\Poss(B))$.
The same is true for OCFs; we refer the reader to \cite{spohn:88}
for details.
Fari\~{n}as del
Cerro and Herzig \citeyear{FarinasHerzig91}
define a logic QPL (Qualitative Possibilistic
Logic) with a modal operator $\ge$, where $\phi \ge \psi$
is interpreted as
$\Poss(\intension{ }{\phi}) \le \Poss(\intension{ }{\psi})$.
Clearly, $\phi \ge \psi$ essentially corresponds to
$\psi \gg \phi$.
They provide a complete axiomatization for their logic, and prove that
it is equivalent to Lewis' logic.%
\footnote{Actually, the axiomatization given in \cite{FarinasHerzig91}
is not quite complete as stated; to get completeness,
we must replace their axiom QPL4---$\true \ge \phi$---by  the axiom
$\phi \ge \false$ [Luis Fari\~{n}as del Cerro, private communication, 1996].}
Not surprisingly, an analogue of $AX^M$ is also complete for the
logic.
Further
discussion of the logic can be found in \cite{BendovaHajek}.
We discuss other connections between possibility measures, OCFs,
and our logic
below, in the context of conditionals.

%Finally, we should mention the work of Doyle, Shoham, and Wellman
%\citeyear{DSW}.  They define a logic of relative desire, starting with
%a preference order on worlds.  They extend this to a preference order
%on sets, but in a much different way than we do.  Using $\ge$ for their
%notion, they define $U \ge V$ if $u \succeq v$ for every $u \in U$ and
%$v \in V$; a strict notion $>$ can be similarly defined.  It is easy to
%see that $U > V$ is not equivalent to $U \ge V$ and not($U \ge V$), even
%if $\succeq$ is a total preorder, although it implies it.  Clearly, $U
%\ge V$ implies $U \succeqs V$ and $U > V$ implies $U \succs V$, but the
%converse does not hold.  The requirements for $\ge$ and $>$ are
%significantly stronger than those for $\succeqs$ and $\succs$.  As
%Doyle, Shoham, and Wellman themselves point out, these
%relations are too weak to allow us to make important distinctions.
%They
%go on to define other notions of comparison, but these are incomparable
%to the notions considered here, and are more tuned to their
%applications.

We now turn our attention to conditional logic.  Lewis's main goal in
considering preferential structures was to capture a
counterfactual conditional $\Cond$, where $\psi \Cond \phi$ is
read as ``if $\psi$ were the case, then $\phi$ would be true''
as in ``if kangaroos
had no tails, then they would topple over''.  He takes this to be true
at a world $w$ if, in all the worlds ``closest'' to $w$ (where
closeness
is defined by a preorder $\succeq$) where kangaroos don't have tails,
it is the case that kangaroos topple over.%
\footnote{To really deal appropriately with counterfactuals, we require
not one preorder $\succeq$, but a possibly different preorder
$\succeq_w$ for each world $w$, since the notion of closeness in general
depends on the actual world.  We ignore this issue here, since it is
somewhat tangential to our concerns.}

More abstractly, in the case where $W$ is finite, for a subset $V
\subseteq W$, let
$\best(\WorldsV) = \{v \in \WorldsV: v' \succ v \mbox{ implies } v' \notin
\WorldsV\}$.  Thus, $\best(\WorldsV)$ consists of all worlds $v \in
\WorldsV$ such that no world $v' \in \WorldsV$ is considered more likely
than $v$.  (We take $\best(\emptyset) = \emptyset$.)

If $W$ is finite, we define
$$(M,w) \sat \psi \Cond \phi \mbox{ if $\best(\intension{M}{\psi})
\subseteq \intension{M}{\phi}$.}$$
Thus,
$\psi \Cond \phi$ is true
exactly if $\phi$ is true at the most likely (or closest) worlds where
$\phi$ is true.

For infinite domains, this definition does not
quite capture our intentions.  For example, in Example~\ref{infinite},
we have $\best(\Worlds_\infty) = \emptyset$. It follows that if $M =
(\Worlds_\infty,\succeq,\pi)$, then
$M \sat \true \Cond \neg p$ even if $\pi$ makes $p$ true at every world
in $\Worlds_\infty$.
We certainly would not want to say that ``if $\true$ were the case, then
$p$ would be false'' is true if $p$ is true at all the worlds in
$W_\infty$! The solution here is again a generalization of Lewis's
definition in the case of totally ordered worlds, and
 is much like that for $\succs$ in infinite domains.
We say  $M \models \psi \Cond\phi$ if for all
%joe
%$u \in \intension{M}{\psi}$,
%there exists a world $v \in \intension{M}{\psi \land \phi}$ such that $v
$u \in \intension{M}{\neg \phi \land \psi}$,
there exists a world $v \in \intension{M}{\phi \land \psi}$ such that $v
\succ u$ and $v$  dominates $\intension{M}{\neg \phi  \land
\psi}$.  This definition agrees with the definition given above
for the case of finite $W$.
\lem\label{agreefin} If $W$ is finite, then
$\best(\intension{M}{\psi}) \subseteq \intension{M}{\phi}$ iff for all
$u \in \intension{M}{\neg \phi \land \psi}$,
there exists a world $v \in \intension{M}{\phi \land \psi}$ such that $v
\succ u$ and $v$  dominates $\intension{M}{\neg \phi  \land \psi}$.
\elem

\prf See Appendix~\ref{proofs}. \eprf

Lewis \citeyear{Lewis73} argues that this definition of $\Cond$
captures many of our intuitions for counterfactual reasoning.
We can give $\Cond$ another interpretation, perhaps more natural if we
are thinking in terms of likelihood.
We often  want to say that $\phi$ is more likely than
not---in $\LPhi$, this can be expressed as $\phi \gg \neg \phi$.  More
generally, we might want to say that {\em relative to $\psi$}, or
{\em conditional on $\psi$ being the case}, $\phi$ is more likely than
not.  By this we mean that if we restrict to worlds where $\psi$ is
true, $\phi$ is more likely than not, that is, the worlds where $\phi
\land \psi$ is true are more likely than the worlds where $\neg \phi
\land \psi$ is true.

Let us define $\psi \Cond' \phi$ to be an abbreviation for
$K \neg \psi \lor (\phi \land \psi \gg \neg \phi \land \psi)$.  That
is,
$\psi \Cond' \phi$ is true vacuously in a structure $M$ if $\psi$ does
not hold in any world in $M$; otherwise, it holds if $\phi$ is more
likely than not in the worlds satisfying $\psi$.


Although the intuition for $\Cond'$ seems, on the
surface, quite different from that for $\Cond$, especially in finite
domains, it is almost immediate from their formal definitions
that they are equivalent.  (This connection between $\Cond$ and $\Cond'$
was already observed by Lewis \citeyear{Lewis73} in the case of total
proeorders.)

\lem\label{equiv} For all structures $M$, we have $M \sat \psi
\Cond \phi$ iff $M \sat \psi \Cond' \phi$. \elem

\prf This is almost immediate from the definitions.  See Appendix~\ref{proofs}
for details. \eprf

Given Lemma~\ref{equiv}, we can write $\Cond$ for both $\Cond$ and
$\Cond'$.  The lemma also allows us to apply the known results for
conditional logic to the logic of relative likelihood defined here.  In
particular, the results of \cite{FrH3} show that the validity problem
for the logic of Section~\ref{logic} is co-NP complete, no harder than
that of propositional logic, for the case of both partial and
total preorders.%
\footnote{We remark that there are also well known axiomatizations for
various conditional logics \cite{Burgess81,FrH3,Lewis73}.  These do not
immediately give us a complete axiomatization for the logic of relative
likelihood considered here, since we must find axioms
in the language with $\gg$, not in the language with $\Cond$.}

More recently, $\Cond$ has been used to capture nonmonotonic default
reasoning \cite{KLM,Boutilier94AIJ1}.  In this case, a statement like
$\Bird \Cond \Fly$
is interpreted as ``birds typically fly'', or ``by default, birds fly''.
The semantics does not change: $\Bird \Cond \Fly$ is true if in the most
likely worlds satisfying $\Bird$, $\Fly$ holds as well.
%As Dubois and
%Prade \citeyear{DuboisPrade:Defaults91} have shown, we can also give
%semantics to $\Bird \Cond \Fly$ using possibility theory.
%Possibility measures put a total order
%on subsets of $W$, where $U \succeqs V$ if $\Poss(U) \ge \Poss(V)$.
Dubois and Prade~\citeyear{DuboisPrade:Defaults91}
have shown that possibility
can be used to give semantics to defaults as well, where $\psi \Cond
\phi$ is interpreted as $\Poss(\psi) = 0$ or $\Poss(\phi \land \psi) >
\Poss(\phi \land \neg \psi)$.  Of course, this is just the
analogue of the definition of $\Cond$ in terms of $\succs$.
Goldszmidt and Pearl \citeyear{Goldszmidt92}
have shown that a similar approach
works if we use Spohn's OCFs.

These results are clarified and unified in \cite{FrH5Full}.  Suppose
we start with some mapping $\Pl$ of sets to a partially ordered space
with minimal element $\bot$ (such a mapping is called a {\em
plausibility measure\/} in \cite{FrH5Full}).  Define $\psi \Cond \phi$
as $\Pl(\phi) = \bot$ or $\Pl(\psi \land \phi) > \Pl(\psi \land \neg
\phi)$.  Then it is shown that $\Cond$ satisfies the {\em KLM
properties}---the properties isolated by Kraus, Lehmann, and
Magidor \citeyear{KLM} as forming the core of default reasoning---%
if and only if $\Pl$ is qualitative, at least when restricted to
disjoint sets.%
\footnote{That is, if $V_1$, $V_2$, and $V_3$ are {\em disjoint\/} sets,
we require that if $\Pl(V_1 \union V_2) > \Pl(V_3)$ and $\Pl(V_1 \union
V_3) > \Pl(V_2)$, then $\Pl(V_1) > \Pl(V_2 \union V_3)$.  The
result also requires the assumption that if $\Pl(U) = \Pl(V) = \bot$,
then $\Pl(U \union V) = \bot$.}
Since $\succeqs$, $\Poss$, and OCFs give rise to qualitative orders
on $2^W$, it is no surprise that they should all lead to logics that
satisfy the KLM properties.

We remark we can also start with $\Cond$, and then define $\gg$ in
terms of $\Cond$.  There are, in fact, three related ways of
doing so.
Define $\phi \gg' \psi$ to be an abbreviation for
$((\phi \lor \psi) \Cond (\phi \land \neg \psi)z) \land \neg ((\phi \lor \psi) \Cond \psi)$;
define $\phi \gg'' \psi$ to be an abbreviation for
$\neg(\phi \Cond \psi) \land ((\phi \lor \psi) \Cond \neg \psi)$; define
$\phi \gg''' \psi$ to be an abbreviation for 
$\neg(\phi \Cond \false) \land ((\phi \lor \psi) \Cond (\phi \land \neg
\psi))$. 

\pro\label{equivalences} For all structures $M$, the following are equivalent:
\begin{itemize}
\item[(a)] $M \sat \phi \gg \psi$
\item[(b)] $M \sat \phi \gg' \psi$
\item[(c)] $M \sat \phi \gg'' \psi$.
\item[(d)] $M \sat \phi \gg''' \psi$.
\end{itemize}
\epro
The first translation is essentially due to
Kraus, Lehmann, and Magidor \citeyear{KLM}, the second is
essentially due to Freund \citeyear{Freund:InjDisj}, and the third is
due to Lewis \citeyear{Lewis73}.  Since the
equivalences are so close to those already in the literature, we omit
the proof of this result here.  Using these equivalences
and results of \cite{KLM}, Daniel Lehmann [private correspondence, 1996]
has provided an alternate proof for Theorem~\ref{complete1}.  See the
remarks after the proof of that theorem in Appendix~\ref{proofs} for a few more
details.


\section{Conclusion}\label{conclusion}
We have investigated a notion of relative likelihood starting with
a preferential ordering on worlds.  This notion was earlier studied by
Lewis \citeyear{Lewis73} in the case where the preferential order is a
total preorder; the focus of this paper is on the case where the
preferential order is a partial preorder.
Our results show that there are significant differences between the
totally ordered and partially ordered case.  By focusing on the
partially ordered case, we bring out the key role of the qualitative
property (Axiom L3), whose connections to conditional logic were already
observed in \cite{FrH5Full}.

\newpage

\acks{Many interesting and useful discussions
on plausibility with Nir Friedman formed the basis for this paper; Nir
also pointed
out the reference \cite{DSW}.  Daniel Lehmann, Emil Weydert, and the
referees of the paper
also provided useful comments. A preliminary version of this paper
appears in {\em Uncertainty in Artificial Intelligence, Proceedings of
the Twelfth Conference}, 1996, edited by E. Horvitz and F. Jensen.
Most of this work was carried out while the author was at the
IBM Almaden Research Center.  IBM's support is gratefully acknowledged.
The work was also supported in part by NSF under
grants IRI-93-03109 and IRI-96-25901, and by the Air Force Office of
Scientific Research under contract F49620-96-1-0323.}

\appendix
\section{Proofs}\label{proofs}
We repeat the statements of the results we are proving here for the
convenience of the reader.

\bigskip
\olem{qualitative} If $\rhd$ is an orderly qualitative relation
on $2^{\Worlds}$, then $\rhd$ is transitive and satisfies the union
property.
\eolem

%\medskip

\prf Suppose $\rhd$ is an orderly qualitative relation.  To see that $\rhd$
is transitive, suppose $V_1 \sR V_2$ and $V_2 \sR V_3$.  Since $\rhd$ is
orderly, it follows that $(V_1 \union V_3) \sR V_2$ and
%joe1: typo spotted by Lehmann
%$(V_1 \union V_2) \sR V'_3$.
$(V_1 \union V_2) \sR V_3$.
Since $\rhd$ is qualitative, it follows that $V_1 \sR (V_2 \union V_3)$.
>From the fact that $\rhd$ is orderly, we get that $V_1 \sR V_3$.
Thus, $\rhd$ is transitive, as desired.

To see that $\rhd$ satisfies the union property, suppose $V_1 \sR V_2$
and $V_1 \sR V_3$. Since $\rhd$ is orderly, we have that $(V_1 \union
V_3) \sR V_2$ and $(V_1 \union V_2) \sR V_3$.  Using the fact that
$\rhd$ is qualitative, we get that $V_1 \sR (V_2 \union V_3)$.  Hence,
$\rhd$ satisfies the union property. \eprf

\bigskip

\opro{precproperties}
\begin{itemize}
\item[(a)] If $\succeq$ is a partial preorder on $\Worlds$, then
$\succeqs$ is an orderly partial preorder on $2^{\Worlds}$ that
satisfies the union property.
\item[(b)] If $\succeq$ is a partial preorder on $\Worlds$, then
$\succ'$ is an orderly strict partial order on $2^{\Worlds}$.
\item[(c)] If $\succ$ is a strict partial order on $\Worlds$, then
$\succs$ is an orderly qualitative strict partial order on $2^{\Worlds}$.
\end{itemize}
\eopro

%\medskip

\prf We prove part (c) here; the proof of parts (a) and (b) is similar
in spirit, and is left to the reader.   The fact that $\succs$ is an
orderly strict partial order is straightforward, and is also left to the
reader.  To see that $\succs$ is qualitative, suppose
$V_1 \union V_2 \succs V_3$ and $V_1 \union V_3 \succs
V_2$.  Let $v \in V_2 \union V_3$.  We must show that there is some
$v' \in V_1$ that  dominates $V_2 \union V_3$ such that
$v' \succ v$.  Suppose without loss of generality that $v \in V_2$
(an identical argument works if $v \in V_3$).  Since $V_1 \union V_3
\succs V_2$, there is some $u \in V_1 \union V_3$ that
dominates $V_2$ such that $u \succ v$.  If $u$  dominates $V_3$,
then it clearly  dominates $V_2 \union V_3$ and it must be in
$V_1$,
so we are done.  Thus, we can assume that $u$ does not  dominate
$V_3$, so there is some element $u' \in V_3$ such that $u' \succ u$.
Since $V_1 \union V_2 \succs V_3$, there must be some $v' \in V_1 \union
V_2$ such that $v'$  dominates $V_3$ and $v' \succ u'$.  Since
$u$  dominates $V_2$ and $u' \succ u$, it follows that $u$
 dominates $V_2$.  Since $v' \succ u'$, we have that $v'$
dominates $V_2$.  Hence, $v'$  dominates $V_2 \union
V_3$.  It follows that $v'$ cannot be in $V_2$, so it must be in $V_1$.
Thus, we have an element in $V_1$, namely $v'$, such that $v' \succ v$
and $v'$ dominates $V_2 \union V_3$, as desired.  \eprf

\bigskip

\olem{modular} If $\succeq$ is a total preorder, then the strict partial
order $\succ$ determined by $\succeq$ is modular.
Moreover, if $\rhd$ is a modular, strict partial order on $\Worlds$,
then there is a total preorder $\succeq$ on $\Worlds$ such that
$\rhd$ is the strict partial order determined by $\succeq$. \eolem

%\medskip

\prf Suppose $\succeq$ is a total preorder.  To see that $\succ$
is modular, suppose that $w_1 \succ w_2$.  Given an arbitrary $w_3$,
if $w_3 \succeq w_1$, it follows from the transitivity of $\succeq$
that $w_3 \succ w_2$.  On the other hand, if it is not the case
that $w_3 \succeq w_1$, then $w_1 \succ w_3$.  Thus, we have that
either $w_3 \succ w_2$ or $w_1 \succ w_3$, so $\succ$ is modular.

Now suppose that $\rhd$ is a modular strict partial order on $W$.
Define $\succeq$ so that $w \succeq v$ either if $w \sR v$
or if neither $w \sR v$ nor $v \sR w$ hold.  Clearly, $\succeq$ is
reflexive.  To see that it is transitive, suppose that $v_1 \succeq
v_2$ and $v_2 \succeq v_3$.  There are three cases:  (1) If
$v_1 \sR v_2$, then since $\rhd$ is modular, we have that
either $v_1 \sR v_3$
or $v_3 \sR v_2$.  We cannot have $v_3 \sR v_2$, for then we would
not have $v_2 \succeq v_3$.  Thus, we must have $v_1 \sR v_3$, and
hence $v_1 \succeq v_3$.  (2) If $v_2 \sR v_3$, then using modularity
again, we get that either $v_1 \sR v_3$ or $v_2 \sR v_1$.  Again,
we cannot have $v_2 \sR v_1$, so we must have $v_1 \sR v_3$, and so
we also have $v_1 \succeq v_3$.
(3) If neither $v_1 \sR v_2$ nor $v_2 \sR v_3$ hold, then we claim
that neither $v_1 \sR v_3$ nor $v_3 \sR v_1$ hold.  For if
$v_1 \sR v_3$, then by modularity, we must have either $v_1 \sR v_2$
or $v_2 \sR v_3$.  And if $v_3 \sR v_1$, then either $v_3 \sR v_2$
or $v_2 \sR v_1$, which contradicts the assumption that $v_1 \succeq
v_2$ and $v_2 \succeq v_3$.  Thus, we can again conclude that
$v_1 \succeq v_3$.  Thus, $\succeq$ is transitive.
Finally, it is almost immediate from the definition
that $\rhd$ is the strict partial order determined by $\succeq$.  \eprf

\bigskip

\olem{modular1} If $\succ$ is a modular relation on $W$, then
$\succs$ is a modular relation on $2^W$. \eolem

%\medskip

\prf Suppose $\succ$ is modular.  We want to show that $\succs$ is
modular.  So suppose that $V_1 \succs V_2$, and it is not the case that
$V_1 \succs V_3$.  We must show that $V_3 \succs V_2$.  Since it is not
the case that $V_1 \succs V_3$, there must be some $v^* \in V_3$ such
that for all $u \in V_1$, we do not have $u \succ v^*$.  Now suppose
$v \in V_2$.  We claim that $v^* \succ v$.  To see this, note that since
$V_1 \succs V_2$, there must be some $u^* \in V_1$ such that $u^* \succ
v$.  Since $\succ$ is modular, we have that
either $u^* \succ v^*$ or $v^*
\succ v$.  Since, by choice of $v^*$, we do not have
$u^* \succ v^*$, we must
have $v^* \succ v$.  It follows that $V_3 \succs V_2$. \eprf

\bigskip

\olem{modular2} If $\rhd$ is a modular strict partial order and
satisfies the union property, then $\rhd$ is qualitative. \eolem

%\medskip

\prf Suppose that $\rhd$ is modular strict partial order that satisfies
the union property.  To see that $\rhd$ is qualitative, suppose
that $(V_1 \union V_2) \sR V_3$ and $(V_1 \union V_3) \sR V_2$.
Since $\rhd$ is modular, it follows that either $(V_1 \union V_2)
\sR V_1$ or $V_1 \sR V_3$.  If $(V_1 \union V_2) \sR V_1$,
then, using the fact that $\rhd$ satisfies the union property and
$(V_1 \union V_2) \sR V_3$, we get that $(V_1 \union V_2) \sR
(V_1 \union V_3)$.  Using transitivity, it follows that
$(V_1 \union V_2) \sR V_2$.  Using the union property again,
we get that $(V_1 \union V_2) \sR (V_1 \union V_2)$.  This contradicts
the assumption that $\rhd$ is irreflexive.  Thus,
we must have that $V_1 \sR V_3$.  A similar argument shows that
$V_1 \sR V_2$. Using the union property, we get that $V_1 \sR
(V_2 \union V_3)$, as desired.  \eprf

\bigskip

\olem{agree} If $\succeq$ is a total preorder, then $\succs$ and
$\succ'$ agree.
In general, $U \succs V$ implies $U \succ' V$, but the converse does not
hold. \eolem

\prf It is immediate from the definitions that $U \succs V$ implies $U
\succ' V$, and the fact that the converse does not hold is shown by
Example~\ref{inequivalent}.  To show that $\succs$ and $\succ'$ are
equivalent if $\succeq$ is a total preorder, suppose $U \succ' V$.  Clearly
$U$ is nonempty, since $V \succeqs \emptyset$ for all $V$.
We want to show that $U \succs V$, so we must show that for all $v \in
V$, there is some $u \in U$ that  dominates $V$ such that $u
\succ v$.
%joe
We actually show that there is some $u \in U$ such that $u \succ v'$
for all $v' \in V$.  Suppose not.  Then for every $u \in U$, there is
some $v_u$ such that we do not have $u \succ v_u$.  Since $\succeq$
is a total order, this means that $v_u \succeq u$.  But this, in
turn, means that $V \succeqs U$, contradicting our assumption that
$U \succs V$.
%Given $v \in V$, since $U \succeqs V$, there must be some $u
%\in U$ that dominates $V$ such that $u \succeq v$.  If
%$u \succ v$, then we are done.  If not, then $v \succeq u$.
%Since it is not the case
%that $V \succeq U$, there must be some $u' \in U$ such that it is not
%the case that $v \succeq u'$.  Since $\succeq$ is a total order,
%we must have $u' \succ v$.  Since $v \succeq u$, we also have $u' \succ
%u$.  Since $u$ dominates $V$, so does $u'$.  It follows that $U \succs
%V$, as desired. \eprf
Since there is a $u \in U$ such that $u \succ v$ for all $v \in V$,
it easily follows that $u^*$ dominates $V$ and that $U \succs V$,
as desired. \eprf

\bigskip

\othm{key}
Let $\F$ be a finite algebra of subsets of $W$ (that is, $\F$ is a
set of subsets of $W$ that is closed under union and complementation and
contains $W$ itself) and let $\rhd$ be an orderly qualitative relation on
$\F$.
\begin{itemize}
\item[(a)] If $\rhd$ is a total preorder on $\F$,
then there is a total preorder $\succeq$ on $W$ such that $\rhd$ and
$\succeqs$ agree on $\F$ (that is, for $U, V \in \F$, we have
$U \sR V$ iff $U \succeqs V$).
\item[(b)] If $\rhd$ is a strict partial order and each nonempty set in
$\F$ has at least $2^{\log(|\F|)^{\log(|\F|)}}$
elements, then there is a partial
preorder $\succeq$ on $W$ such that $\rhd$ and $\succs$ agree on $\F$.
\end{itemize}
\eothm

\prf Part~(a) was already proved in the main text, so we prove part (b)
here.

We proceed as follows.
We say that a pair $(A,X)$
is {\em minimal pair of $\rhd$\/} if $X \sR A$ and there is no
$X' \subset X$ (``$\subset$'' is used here to denote strict subset) such
that $X' \sR A$.
The minimal pairs in an ordered relation determine it.  Indeed, the
following stronger result holds.
\lem\label{minpair}
If $\rhd$ and $\rhd'$ are two orderly qualitative relations on $\F$
such that for each minimal pair $(A,X)$ of $\rhd$ we have $X \sR A$, and
for each minimal  pair $(A',X')$ of $\rhd'$ we have $X' \, \rhd' \, A'$, then
$\rhd = \rhd'$.
\elem
\prf Suppose the assumptions of the lemma holds and that
$X\sR Y$; we must show that $X \, \rhd' \, Y$.  Suppose $A$ is
an atom such that $A \subseteq Y$.  Since $\rhd$ is orderly, we must have
$X \sR A$.  Let $X'$ be a minimal subset of $X$ such that $X' \sR A$.  Since
$\F$ is finite, such an $X'$ must exist.  Thus, $(A,X')$ is a minimal
pair of $\rhd$.  By assumption, we have $X' \, \rhd' \, A$.  Since
$\rhd'$ is orderly, we also have $X \, \rhd' \, A$.  Thus, we have $X \, \rhd' \,
A$ for each atom $A \subseteq Y$.  Since $\rhd'$ is qualitative, it also
satisfies the union property, and hence $X \, \rhd' \, Y$ as desired.  By
symmetry, it follows that $\rhd = \rhd'$.  \eprf

A {\em minimal-pair tree\/} for $\rhd$ is a rooted tree
whose nodes are
labeled by atoms such that the following conditions are satisfied:
\begin{enumerate}
\item If a node in the tree labeled $B$ is an immediate successor of a
node labeled $A$, then there must be a minimal pair
$(A,X)$ of $\rhd$ such that $B \subseteq X$.
\item If there is a node $t$ in the tree labeled $A$ and a minimal pair
of $\rhd$ of
the form $(A,X)$, then there must be some atom $B \subseteq X$ such that
a node labeled $B$ is an immediate successor of $t$.
%and the edge between $A$ and $B$ is labeled by $X$.
\item There does not exist a path in the tree such that two nodes in
the path have the same label.
\item A node does not have two distinct successors with the same label.
\end{enumerate}
A minimal-pair tree is {\em rooted at $A$} if the root of the tree is
labeled by the atom $A$.

Since a subset of $\F$ can be written in a unique way as the union of
atoms, there is a 1-1 correspondence between subsets of $\F$ and sets of
atoms.  Thus, there are exactly $\log(|\F|)$ atoms.   Because of the
third condition, a path in the tree can have length
at most $\log(|\F|)$.  Since all the atoms on the path must be distinct,
%for each element $X \in \F$, the number of edges
%labeled $X$ is at most the number of atoms whose union is $X$, and is
%thus at most $\log(|\F|)$.
it follows that there are at most $\log(|\F|)! \le \log(|\F|)^{\log(|\F|)}
(= |\F|^{\log\log(|\F|)})$ possible paths in a tree
rooted at $A$.
We can identify a tree with the set of its paths, which means that
there are at most $2^{\log(|\F|)!} \le 2^{\log(|\F|)^{\log(|\F|)}}$
possible trees rooted at an atom $A$.

We now label each element in $W$ with a minimal-pair tree in such a
way that every element of atom $A$ is labeled by a tree rooted
at $A$, and every minimal-pair tree rooted at $A$ is the label of
some element of $A$.  Since we have assumed that $A$ has at
least $2^{\log(|\F|)^{\log(|\F|)}}$ elements, there is such a
labeling.
Let $L(w)$ be the label of node $w$.
We define $\succ$ on $W$ so that $w' \succ w$ iff
$L(w')$ is a proper subtree of $L(w)$.
Clearly $\succ$ is a strict partial order.

We claim that $\rhd$ agrees with $\succs$.  By Lemma~\ref{minpair}, it
suffices to show that if $(A,X)$ is a
minimal pair of $\rhd$, then $X \succs A$, and if $(A,X)$ is a minimal pair
of $\succs$, then $X \sR A$.
So suppose $(A,X)$ is a minimal pair of $\rhd$.  We want to show that
$X \succs A$.  Let $w \in A$, and suppose that $L(w) = T$.
Thus, $T$ is a minimal-pair tree rooted at $A$.
The construction of minimal-pair trees guarantees that there is
a successor of the root in tree $T$ labeled $B$ for some atom $B
\subseteq X$.
Consider the subtree of $T$ rooted at $B$.  This is a minimal-pair tree
rooted at $B$, and hence must be the label of some $w' \in B \subseteq X$.
Thus, $w' \succ w$.  It follows that $X \succs A$.

Now suppose that $(A,X)$ is a minimal pair of $\succs$.  We want to show
that $X \sR A$. Suppose not.  As
we show below, this means that there exists a minimal-pair tree $T$
rooted at $A$ such that no node in $T$ is labeled by an atom contained
in $X$. Let $w$ be
an element of $A$ with $L(w) = T$.  By construction, there is no element
$w'$ of $X$ such that $w' \succ w$.  Thus, we do not have $X \succs A$,
contradicting our initial assumption.

It remains to show that there exists a minimal-pair tree $T$ rooted at
$A$ such that no node in $T$ is labeled by an atom contained in $X$.
Clearly, we cannot have $X' \sR A$ for
some $X' \subset X$, for then, by the preceding argument, we would have
$X' \succs A$, and $(A,X)$ would not be a minimal pair of $\succs$.  It
follows that if $(A,Y)$ is a minimal pair of $\rhd$, then we must have $Y-X
\ne \emptyset$.

Two general fact about orderly, qualitative relations will be useful in
our construction:
\lem\label{fact1} If $\rhd'$ is a qualitative relation on
$\F$ and $Y \, \rhd' \, X$, then $(Y - X) \, \rhd' \, X$. \elem

\prf Notice that $(Y- X) \union X \, \rhd' \, X$.
Since $\rhd'$
is qualitative, it follows that $(Y-X) \, \rhd' \, X$ (take both $V_2$ and
$V_3$ in the definition of qualitative to be $X$).

%\lem\label{fact1.5} $A \inter X = \emptyset$.  \elem
%\prf.  Since $(A,X)$ is a minimal pair of $\succs$, we know that $X
%\succs A$.  By Lemma~\ref{fact1}, we also have $X-A \succs A$.
%Since $(A,X)$ is a minimal pair, the result follows.  \eprf.

\lem\label{fact1.5} If $\rhd'$ is an orderly, qualitative relation such
that $(X_1 \union X_2) \, \rhd' \, X_3$ and $X' \, \rhd' \, X_2$, then
$(X_1 \union X') \, \rhd' \, X_3$. \elem

\prf Since $\rhd'$ is orderly, our assumptions imply that $(X_1 \union X'
\union X_2) \, \rhd' \, X_3$ and that $(X_1 \union X' \union X_3) \, \rhd' \,
X_2$.  Since $\rhd'$ is qualitative, it follows that $(X_1 \union X') \sR
(X_2 \union X_3)$.  The result follows using the fact that $\rhd'$ is orderly
again. \eprf

 We start by constructing a tree whose nodes are labeled by atoms and
whose root is labeled by $A$.  We proceed in
$\log(|\F|)+1$ stages.  At each stage, we have a tree whose nodes are
labeled by atoms.  At stage 0, we just take a single node labeled by
$A$.  Suppose we have constructed a tree whose nodes are labeled by
atoms and whose root is labeled by
$A$ at stage $k < \log(|\F|)$.  For stage $k+1$, for each leaf $t$ in
the stage-$k$ tree, if $t$ is labeled by $B$, then for each atom $C$,
if there is a minimal pair $(B,Y)$ of $\rhd$ with $C \subseteq Y$, we
add a successor to $t$ labeled $C$.  We call the tree constructed at the
end of stage $\log(|\F|)$ the {\em full tree for $A$}.

We next mark nodes in the full tree in
stages.  At the $k$th stage, for each atom $B$, we mark an unmarked node
$t$ labeled $B$ if one of the following three conditions holds:
(1) $B \subseteq X$, (2) there is an ancestor of $t$ in the tree also
labeled $B$, (3)
there is a minimal pair $(B,Y)$ of $\rhd$ and all the successors of $t$
with a label contained in $Y$
were marked at an earlier stage.  If there are no unmarked nodes
satisfying one of these three conditions at stage $k$, then the marking
process stops.  Otherwise, we continue to stage $k+1$.  Since there are
only finitely many nodes, this marking process is guaranteed to
terminate.

Our goal is to show that, at the end of the marking process, the root of
the full tree is unmarked.  For if this is the case,
let $T$ be the subtree of the
full tree consisting of all the unmarked nodes all of whose ancestors are
unmarked. It is easy to check that $T$ is a
minimal-pair tree and our marking procedure guarantees that no node in
$T$ is labeled by an atom contained in $X$, so we are done.

To see that the root of the full tree is
unmarked, we proceed as follows:
Define a {\em 0-cover\/} for a node $t$ in the full tree
to be just $t$ itself.  Suppose we have defined a $k$-cover for $t$.
A set $Z$ of nodes is a {\em $(k+1)$-cover\/} for $t$ if there exists a
$k$-cover $Z'$ for $t$ such that for some node $t'$ in $Z'$ labeled
$B$ and some minimal pair $(B,Y)$ of $\rhd$, we have that $Z$ consists
of all the nodes in
$Z'$ except for $t'$, together with all the successors of $t'$
that are labeled by an atom contained in $Y$.
An easy argument by induction on $k$ shows the following.

\lem\label{fact2} If $Z$ is a $k$-cover for a node $t$ labeled $C$ and
$k > 0$, then there exist a set $Y$ such that $(C,Y)$ is a minimal pair
of $\rhd$, successors $t_1, \ldots, t_m$ of $t$ in the full tree,
atoms $D_1, \ldots, D_m$ such that $Y = \union_{i=1}^m D_i$ and $D_i$
is the label of $t_i$, $i = 1, \ldots, m$, and a partition $Z_1, \ldots,
Z_m$ of $Z$ into disjoint subsets such that
$Z_i$ is a $k_i$-cover for $t_i$, $i=1,
\ldots, m$, for some $k_i < k$. \elem

Given a set $Z$, let $U^n_Z$ consist of the
union of the atoms labeling the nodes of $Z$ still unmarked at the
$n$th stage (we take $U^0_Z$ to be the union of the atoms labeling the
nodes in $Z$); given a node $t$, let $V_{t}$
consist of the union of the atoms $D$ labeling ancestors of $t$ such
that $t$ or some descendent of $t$ has the label $D$.

The key fact is the following result.
\lem\label{fact3} If $Z$ is a $k$-cover for a node $t$ labeled $C$ and
$k >
0$, then $(U^n_Z \union V_{t} \union X) \sR C$.  \elem

\prf We proceed by induction on $k$, with a subinduction on $n$.  If $k
= 1$, then there is some
set $Y$ such that $(C,Y)$ is a minimal pair of $\rhd$ and the nodes in $Z$
are labeled by the atoms contained in $Y$.  Since $(C,Y)$ is a minimal
pair of $\rhd$, we have that $Y \sR C$. Since
$\rhd$ is orderly, $(Y \union V_{t} \union X) \sR C$.  By definition,
$U_Z^0 = Y$, so this takes care of the case $n=0$.  Suppose $n > 0$ and
$(U_Z^{n-1} \union V_t \union X) \sR C$.  For the inductive step, it
suffices to show that that if
\begin{equation}\label{eq1}
(Y' \union V_{t} \union X) \sR C
\end{equation}
and $D$ is the label of a node $t'$ in $Z$
marked at stage $n$, then
\begin{equation}\label{eq2}
((Y' - D) \union V_{t} \union X) \sR C.
\end{equation}
So suppose that (\ref{eq1}) holds and $D$ is the label of $t'$.
We must consider how $t'$ was marked.  If $D \subseteq X$ then
(\ref{eq2}) is immediate.  If there is an ancestor of $t'$
also labeled $D$, then $D \subseteq V_{t'}$, and, since $k=1$, we have
$V_{t'} \subseteq V_{t} \union C$.  Thus, since $\rhd$ is
orderly, it follows that
\begin{equation}\label{eq3}
((Y' - D) \union V_{t} \union X \union C) \sR C,
\end{equation}
so (\ref{eq2}) follows from
Lemma~\ref{fact1}.  Finally,
suppose there is some minimal pair $(D,Y'')$ of $\rhd$ such that all the
successors
of $t'$ labeled by an atom in $Y''$ are marked by stage $n-1$.  Let $Z'$
consist of the successors of $t'$ labeled by atoms contained in $Y''$.
$Z'$ is a 1-cover for $t'$.
Since $U^{n-1}_{Z'} = \emptyset$, it follows from the
induction hypothesis that $(V_{t'} \union X) \sR D$.
Again, since $V_{t'} \subseteq V_{t} \union C$, (\ref{eq3}) follows
orderliness and Lemma~\ref{fact1.5}, and the desired (\ref{eq2})
follows from Lemma~\ref{fact1}.

Now suppose $k>1$.
Let $Y, D_1, \ldots, D_m, Z_1, \ldots, Z_m, t_1, \ldots, t_m$ be the
sets and nodes
guaranteed to exist by Lemma~\ref{fact2}.   Since $Z_i$ is a $k_i$-cover
for $t_i$ for some $k_i < k$, by the induction hypothesis,
$(U^{n}_{Z_i} \union V_{t_i} \union X) \sR D_i$.  Since $U^{n}_{Z_i}
\subset U^n_Z$ and $V_{t_i}
\subseteq V_t \union C$, by
orderliness, we have that $(U^n_Z \union V_t \union X \union C) \sR
D_i$. Since
$\rhd$ is qualitative, we have that $(U^n_Z \union V_t \union X \union C)
\sR (\union_i D_i)$.  Since $\union_i D_i = Y$ and $Y \sR C$,
(\ref{eq3}) now follows, and again (\ref{eq2})
follows from Lemma~\ref{fact1}.
\eprf


Finally, suppose, by way of contradiction, that the root $r$ of the
full tree is marked, say at stage $n$ of the marking process.
Lemma~\ref{fact1} assures us that $A \inter X =
\emptyset$, since $(A,X)$ is a minimal pair of $\succs$, so condition
(1) of the marking process does not
apply.   Since $r$ has no ancestors, condition (2) does not apply
either.  Thus, there must be some minimal pair $(A,Y)$ of $\rhd$
such that all the nodes in the set $Z$ consisting of the successors of
$r$ in the full tree that are labeled by
atoms contained in $Y$ are marked by stage $n-1$.
Thus, we $U^{n-1}_Z =
\emptyset$. Since $V_r =
\emptyset$ and $Z$ is a 1-cover for $r$,
by Lemma~\ref{fact3}, it follows that $X \sR A$,
contradicting our original assumption.
\eprf

\bigskip

For the completeness theorems (Theorems~\ref{complete1}
and~\ref{complete2}) it is convenient to start by proving
Theorem~\ref{complete2}, since it is simpler, and contains the key ideas
for the proof of Theorem~\ref{complete1}.

\bigskip


\othm{complete2} AX$^M$ is a sound and complete axiomatization of
the language
$\LPhi$ with respect to totally preordered preferential structures.
\eothm

\prf Soundness was proved in the main text, so we just consider
completeness here.  Suppose that
$\phi$ is consistent with AX$^M$.  We want to show that that $\phi$ is
satisfiable in a totally preordered preferential structure.
Let $\phi_1, \ldots, \phi_m$ be the basic likelihood formulas that are
subformulas of $\phi$.  By definition, $\phi$ is
a Boolean combination of these formulas.
Define an {\em atom over $\phi$\/} to be a
conjunction of the form $\psi_1 \land \ldots \land \psi_m$, where
$\psi_i$ is either $\phi_i$ or $\neg \phi_i$.
Using straightforward
propositional reasoning (L1 and MP), it is straightforward to show that
$\phi$ is provably equivalent to the disjunction of the consistent atoms
over $\phi$.  Thus, since $\phi$ is consistent, some atom over $\phi$,
say $\sigma$, is consistent.  We now construct a totally
ordered preferential structure
satisfying $\sigma$.  Clearly this structure will satisfy $\phi$ as well.

Let $p_1, \ldots,p_n$ be the primitive propositions in $\Phi$
that appear in $\phi$.  Let $\Sigma$ consist of all the $N = 2^n$ truth
assignments to these primitive propositions.  We take $W = \Sigma$ and
let $\F$ consist of all subsets of $\Sigma$.
We define a total preorder $\rhd$ on $\F$ as follows.  Notice that to
each set $V$ in $\F$, there corresponds a propositional formula
$\phi_V$ that is made true precisely by the truth assignments in
the subset $V'$ of $\Sigma$ that corresponds to $V$.
To be precise, given a truth assignment $\alpha$, let $\phi_\alpha$
consist of the conjunction $q_1 \land \ldots \land q_n$, where $q_i$ is
$p_i$ if $\alpha(p_i) = {\bf true}$, and $\neg p_i$ otherwise.  Let
$\phi_V$ be the disjunction of the formulas $\phi_\alpha$ for $\alpha
\in V'$.  (We take the empty disjunction to be the formula $\false$.)
Notice for future reference that $\phi_{V_1 \union V_2}$ is provably
equivalent to $\phi_{V_1} \lor \phi_{V_2}$.
Conversely, for every
propositional formula $\psi$ that mentions only the primitive
propositions in $\{p_1,\ldots,p_n\}$, there is a corresponding subset
$A_\psi$ in $\F$ that consists of all truth assignments that make
$\psi$ true.

We define a binary relation $\rhd$ on $\F$ as follows: $V  \sR V'$ iff
$AX \vdash \sigma \rimp (\phi_V \gg \phi_{V'}) $.
We claim that $\rhd$ is a modular, qualitative, strict partial order on
$\F$.  The fact that $\rhd$ is irreflexive follows easily from L2;
the fact that it is orderly follows from L4; the fact that it is
qualitative follows from L3; transitivity follows from the fact that $\rhd$
is qualitative and orderly, by Lemma~\ref{qualitative}; modularity
follows from L5. All these arguments are straightforward.
We prove the fact that $\rhd$ is qualitative here, and leave the remaining
arguments to the reader.

Suppose $V_1, V_2, V_3 \in \F$, $(V_1 \union V_2) \sR V_3$, and $(V_1
\union V_3) \sR V_2$.  Our assumptions and the definition of $F$
imply that $AX \vdash \sigma \rimp ((\phi_{V_1} \lor \phi_{V_2}) \gg
\phi_{V_3})$ and
that $AX \vdash \sigma \rimp ((\phi_{V_1} \lor \phi_{V_3}) \gg
\phi_{V_2})$.  By L3 and straightforward propositional reasoning, we
get that
$AX \vdash \sigma \rimp (\phi_{V_1} \gg (\phi_{V_2} \lor
\phi_{V_2}))$, so that $V_1 \sR (V_2 \union V_3)$, as desired.

By Lemma~\ref{modular}, there is a total preorder $\rhd'$ on $\F$ such that
$\rhd$ is the strict partial order determined by $\rhd'$.   By
Theorem~\ref{key}(a), there is total preorder
$\succeq$ on $W$ such that $\rhd'$ and $\succeqs$ agree on $\F$.  Since
$\succ'$
is the strict partial order determined by $\succeqs$, it follows that
$\succ'$ and $\rhd$ agree.  Since $\succeq$ is a total preorder, by
Lemma~\ref{agree}, $\succs$ and $\rhd$ agree.
Let $M = (W,\succeq,\pi)$.  We now claim that for each formula $\phi_j$
that is one of the basic likelihood formulas that is a subformula of
$\phi$, we $M \sat \phi_i$ iff $\phi_j$ is a conjunct of $\sigma$.
For suppose $\phi_j$ is of the form $\psi
\gg \psi'$.  If $\phi_j$ is a conjunct of $\sigma$, then clearly
$AX \vdash \sigma \rimp (\psi \gg \psi')$.  Thus, $A_\psi \sR
A_{\psi'}$ by definition, so $A_\psi \succs A_{\psi'}$ by construction.
Since $A_\psi$ and $A_{\psi'}$ consist of the worlds in $W$ where $\psi$
and $\psi'$, respectively, are true, it follows that $(M,w) \sat \psi
\gg \psi'$.  On the other hand, if $\neg \phi_j$ is a conjunct of
$\sigma$, then we have $AX \vdash \sigma \rimp \neg(\psi \gg \psi')$.
We must have $(M,w) \sat \neg (\psi \gg \psi')$, for if $(M,w) \sat \psi
\gg \psi'$, the same arguments as those above would imply that $A_\psi
\sR A_{\psi'}$, and so $AX \vdash \sigma \rimp \psi \gg \psi'$,
contradicting the consistency of $\sigma$.

Thus, $M$ satisfies $\sigma$, and hence $\phi$. \eprf

\bigskip

\othm{complete1} AX is a sound and complete axiomatization of the
language $\LPhi$ with respect to preferential structures. \eothm

\prf Again, soundness is proved in the main text, so we just consider
completeness.  The ideas are much in the spirit of the proof of
Theorem~\ref{complete2}.  We again
take $\Sigma$ to consist of all the $N = 2^n$ truth
assignments to these primitive propositions.  However, since we plan to
apply part~(b) of Theorem~\ref{key}, we no longer take $W = \Sigma$.
Rather, we take $W$ to consist of
$2^{n^{n}}$ copies of the truth assignments in $\Sigma$.  More
precisely, let $W$ consist of the $N2^{n^{n}}$ worlds of the
form $w_\alpha^i$, such that $i = 1, \ldots, 2^{n^{n}}$ and
$\alpha \in \Sigma$.  Let $\F$ consist of all subsets of $W$ that
correspond to subsets of $\Sigma$; that is, $V \in \F$ iff there exists
some $V' \subseteq \Sigma$ such that $V = \{w_\alpha^i:\  i
= 1, \ldots, 2^{n^{n}},\ \alpha \in V'\}$.  Clearly, $\F$
is a finite algebra with $N$ elements, and each nonempty set in
$\F$ has at least $2^{\log(|\F|)^{\log(|\F|)}}$ elements.

We define a strict partial order $\rhd$ on $\F$ just as in the proof of
Theorem~\ref{complete1}: $V \sR V'$ iff
$AX \vdash \sigma \rimp \phi_V \gg \phi_{V'}$.
As before, $\rhd$ is an orderly qualitative strict partial
order on $\F$.  It is not necessarily modular, since we no longer have
L5.

By Theorem~\ref{key}(b), there is a partial preorder $\succeq$ on
$W$ such that $\rhd$ and $\succs$ agree on $\F$.  Let $M =
(W,\succeq,\pi)$, where $\pi(w_\alpha^i) = \alpha$.
Just as in the proof of Theorem~\ref{complete2},
we can now show that $M \sat \sigma$.  \eprf.

\bigskip

As we noted earlier, Daniel Lehmann has
found another proof for Theorem~\ref{complete1}, using results from
\cite{KLM}.  To show that a formula in $\LPhi$ that is
consistent with AX is satisfiable, he first translates it to a formula
of conditional logic (using Proposition~\ref{equivalences}).  It then
follows from the representation theorem of \cite{KLM} that this
translated formula is satisfiable in a preferential structure.  The
original formula is then satisfiable in the same structure.  This
proof allows us to avoid using Theorem~\ref{key} altogether.  However,
we feel that Theorem~\ref{key} gives insight into the connection between
partial orders on worlds and partial orders on sets of worlds, and thus
is of interest in its own right.

\bigskip

\opro{oneworld} If a formula is satisfiable in a totally
preordered preferential
structure, then it is satisfiable in a totally preordered preferential
structure with at most one world per truth assignment. \eopro

\prf This follows immediately from the completeness proof of
Theorem~\ref{complete2}; the structure constructed in that proof
has one world per truth assignment. \eprf

\bigskip

\olem{agreefin} If $W$ is finite, then
$\best(\intension{M}{\psi}) \subseteq \intension{M}{\phi}$ iff for all
$u \in \intension{M}{\neg \phi \land \psi}$,
there exists a world $v \in \intension{M}{\phi \land \psi}$ such that $v
\succ u$ and $v$  dominates $\intension{M}{\neg \phi  \land \psi}$.
\eolem
\prf Suppose
$\best(\intension{M}{\psi}) \subseteq \intension{M}{\phi}$.  If
$u \in \intension{M}{\neg \phi \land \psi}$, then we cannot have $u \in
\best(\intension{M}{\psi})$, since $\best(\intension{M}{\psi}) \subseteq
\intension{M}{\phi}$.  Since $W$ is finite, there exists a world
$v \in \best(\intension{M}{\psi})$ such that $v \succ u$.  Since $v \in
\best(\intension{M}{\psi})$, we have that $v$ dominates
$\intension{M}{\neg \phi \land \psi}$. Conversely, suppose that for all
$u \in \intension{M}{\neg \phi \land \psi}$,
there exists a world $v \in \intension{M}{\phi \land \psi}$ such that $v
\succ u$ and $v$  dominates $\intension{M}{\neg \phi  \land \psi}$.  If
$u \in \best(\intension{M}{\psi})$, then we must have $u \in
\intension{M}{\phi}$, for if not, there exists a world $v \in
\intension{M}{\phi \land \psi}$ such that $v \succ u$, contradicting the
assumption that $u \in \best(\intension{M}{\phi})$. \eprf


\bigskip

\olem{equiv} For all structures $M$, we have $M \sat \psi
\Cond \phi$ iff $M \sat \psi \Cond' \phi$. \eolem

\medskip

\prf
Suppose $M \sat \psi \Cond \phi$.  By definition, this means that for
all
$u \in \intension{M}{\neg \phi \land \psi}$,
there exists a world $v \in \intension{M}{\phi \land \psi}$ such that $v
\succ u$ and $v$  dominates $\intension{M}{\neg \phi  \land
\psi}$.  It immediately follows that (a) if $\intension{M}{\phi
\land \psi} = \emptyset$ then
$\intension{M}{\neg \phi \land \psi} = \emptyset$ and (b) if
$\intension{M}{\phi \land \psi} \ne
\emptyset$, then by definition we have $M \sat \phi \land \psi \gg \neg
\phi \land \psi$.  It follows from (a)
that if $\intension{M}{\phi \land \psi} = \emptyset$ then
$\intension{M}{\psi} =\emptyset$, so
$M \sat K \neg \psi$, and from (b) that if
$\intension{M}{\phi \land \psi} \ne \emptyset$ then
$M \sat \phi \land \psi \gg \neg \phi \land \psi$.
Thus,
$M \sat K \neg \psi \lor (\phi \land \psi \gg \neg \phi \land \psi)$; \ie
$M \sat \psi \Cond' \psi$.

The converse follows equally easily.
Suppose $M \sat \psi \Cond' \phi$.  Clearly if $M \sat K \neg \psi$ then
we trivially have that for all
$u \in \intension{M}{\neg \phi \land \psi}$,
there exists a world $v \in \intension{M}{\phi \land \psi}$ such that $v
\succ u$ and $v$  dominates $\intension{M}{\neg \phi  \land
\psi}$.  On the other hand, if $M \sat \phi \land \psi \gg \neg \phi
\land \psi$, then it follows by definition that for all
$u \in \intension{M}{\neg \phi \land \psi}$,
there exists a world $v \in \intension{M}{\phi \land \psi}$ such that $v
\succ u$ and $v$  dominates $\intension{M}{\neg \phi  \land \psi}$.
Either way we have $M \sat \psi \Cond \phi$.
\eprf




\vskip 0.2in
\bibliographystyle{theapa}
%\bibliographystyle{chicago}
\bibliography{z,refs,joe}
\end{document}


