
\documentstyle[theapa,jair,twoside,url,11pt]{article}
%\documentstyle[12pt,chicagob]{article}
%\input{spage}
%\input{defn}
%\input{bghkmac}
 %  THEOREM-LIKE ENVIRONMENTS

 \newtheorem{THEOREM}{Theorem}[section]
 \newenvironment{theorem}{\begin{THEOREM} \hspace{-.85em} {\bf :} }%
			 {\end{THEOREM}}
 \newtheorem{LEMMA}[THEOREM]{Lemma}
 \newenvironment{lemma}{\begin{LEMMA} \hspace{-.85em} {\bf :} }%
		       {\end{LEMMA}}
 \newtheorem{COROLLARY}[THEOREM]{Corollary}
 \newenvironment{corollary}{\begin{COROLLARY} \hspace{-.85em} {\bf :} }%
			   {\end{COROLLARY}}
 \newtheorem{PROPOSITION}[THEOREM]{Proposition}
 \newenvironment{proposition}{\begin{PROPOSITION} \hspace{-.85em} {\bf :} }%
			     {\end{PROPOSITION}}
 \newtheorem{DEFINITION}[THEOREM]{Definition}
 \newenvironment{definition}{\begin{DEFINITION} \hspace{-.85em} {\bf :} \rm}%
			     {\end{DEFINITION}}
 \newtheorem{CLAIM}[THEOREM]{Claim}
 \newenvironment{claim}{\begin{CLAIM} \hspace{-.85em} {\bf :} \rm}%
			     {\end{CLAIM}}
 \newtheorem{EXAMPLE}[THEOREM]{Example}
 \newenvironment{example}{\begin{EXAMPLE} \hspace{-.85em} {\bf :} \rm}%
			     {\end{EXAMPLE}}
 \newtheorem{REMARK}[THEOREM]{Remark}
 \newenvironment{remark}{\begin{REMARK} \hspace{-.85em} {\bf :} \rm}%
			     {\end{REMARK}}
 %\newenvironment{proof}{\noindent {\bf Proof:} \hspace{.677em}}%
 %                      {}

 %theorem
 \newcommand{\thm}{\begin{theorem}}
 %lemma
 \newcommand{\lem}{\begin{lemma}}
 %proposition
 \newcommand{\pro}{\begin{proposition}}
 %definition
 \newcommand{\dfn}{\begin{definition}}
 %remark
 \newcommand{\rem}{\begin{remark}}
 %example
 \newcommand{\xam}{\begin{example}}
 %corollary
 \newcommand{\cor}{\begin{corollary}}
 %proof
 \newcommand{\prf}{\noindent{\bf Proof:} }
 %end theorem
 \newcommand{\ethm}{\end{theorem}}
 %end lemma
 \newcommand{\elem}{\end{lemma}}
 %end proposition
 \newcommand{\epro}{\end{proposition}}
 %end definition
 \newcommand{\edfn}{\bbox\end{definition}}
 %end remark
 \newcommand{\erem}{\bbox\end{remark}}
 %end example
 \newcommand{\exam}{\bbox\end{example}}
 %end corollary
 \newcommand{\ecor}{\end{corollary}}
 %end proof
 \newcommand{\eprf}{\bbox\vspace{0.1in}}
 %begin equation
 \newcommand{\beqn}{\begin{equation}}
 %end equation
 \newcommand{\eeqn}{\end{equation}}
 % white box
 \newcommand{\wbox}{\mbox{$\sqcap$\llap{$\sqcup$}}}
 %black box
 \newcommand{\bbox}{\vrule height7pt width4pt depth1pt}
 \newcommand{\qed}{\eprf}
 \newcommand{\clm}{\begin{claim}}
 \newcommand{\eclm}{\end{claim}}
 % (not)member of
 \let\member=\in
 \let\notmember=\notin
 % \sub will be used for subscript.
 \newcommand{\sub}{_}
 % \su will be used for superscript.
 \def\su{^}
 %right arrow
 \newcommand{\rarrow}{\rightarrow}
 %left arrow
 \newcommand{\larrow}{\leftarrow}
 %bold face lower-case letters
 %for bold Greek symbols in math mode (with \boldsymbol{\sigma}, etc.)
 \newcommand{\boldsymbol}[1]{\mbox{\boldmath $\bf #1$}}
 \newcommand{\bolda}{{\bf a}}
 \newcommand{\boldb}{{\bf b}}
 \newcommand{\boldc}{{\bf c}}
 \newcommand{\boldd}{{\bf d}}
 \newcommand{\bolde}{{\bf e}}
 \newcommand{\boldf}{{\bf f}}
 \newcommand{\boldg}{{\bf g}}
 \newcommand{\boldh}{{\bf h}}
 \newcommand{\boldi}{{\bf i}}
 \newcommand{\boldj}{{\bf j}}
 \newcommand{\boldk}{{\bf k}}
 \newcommand{\boldl}{{\bf l}}
 \newcommand{\boldm}{{\bf m}}
 \newcommand{\boldn}{{\bf n}}
 \newcommand{\boldo}{{\bf o}}
 \newcommand{\boldp}{{\bf p}}
 \newcommand{\boldq}{{\bf q}}
 \newcommand{\boldr}{{\bf r}}
 \newcommand{\bolds}{{\bf s}}
 \newcommand{\boldt}{{\bf t}}
 \newcommand{\boldu}{{\bf u}}
 \newcommand{\boldv}{{\bf v}}
 \newcommand{\boldw}{{\bf w}}
 \newcommand{\boldx}{{\bf x}}
 \newcommand{\boldy}{{\bf y}}
 \newcommand{\boldz}{{\bf z}}
 %bold face upper-case letters
 \newcommand{\boldA}{{\bf A}}
 \newcommand{\boldB}{{\bf B}}
 \newcommand{\boldC}{{\bf C}}
 \newcommand{\boldD}{{\bf D}}
 \newcommand{\boldE}{{\bf E}}
 \newcommand{\boldF}{{\bf F}}
 \newcommand{\boldG}{{\bf G}}
 \newcommand{\boldH}{{\bf H}}
 \newcommand{\boldI}{{\bf I}}
 \newcommand{\boldJ}{{\bf J}}
 \newcommand{\boldK}{{\bf K}}
 \newcommand{\boldL}{{\bf L}}
 \newcommand{\boldM}{{\bf M}}
 \newcommand{\boldN}{{\bf N}}
 \newcommand{\boldO}{{\bf O}}
 \newcommand{\boldP}{{\bf P}}
 \newcommand{\boldQ}{{\bf Q}}
 \newcommand{\boldR}{{\bf R}}
 \newcommand{\boldS}{{\bf S}}
 \newcommand{\boldT}{{\bf T}}
 \newcommand{\boldU}{{\bf U}}
 \newcommand{\boldV}{{\bf V}}
 \newcommand{\boldW}{{\bf W}}
 \newcommand{\boldX}{{\bf X}}
 \newcommand{\boldY}{{\bf Y}}
 \newcommand{\boldZ}{{\bf Z}}
 %double turnstile
 \newcommand{\sat}{\models}
 \newcommand{\dtur}{\models}
 %single turnstile
 \newcommand{\infers}{\vdash}
 \newcommand{\stur}{\vdash}
 %fat right arrow
 \newcommand{\rimp}{\Rightarrow}
 %fat left arrow
 \newcommand{\limp}{\Leftarrow}
 %fat double arrow
 \newcommand{\dimp}{\Leftrightarrow}
 %big or
 \newcommand{\bor}{\bigvee}
 %big and
 \newcommand{\band}{\bigwedge}
 %union
 \newcommand{\union}{\cup}
 %intersection
 \newcommand{\inter}{\cap}
 %bold letters
 \newcommand{\xx}{{\bf x}}
 \newcommand{\yy}{{\bf y}}
 \newcommand{\uu}{{\bf u}}
 \newcommand{\vv}{{\bf v}}
 \newcommand{\FF}{{\bf F}}
 \newcommand{\natnum}{{\sl N}}
 %\newfont{\sqi}{cmssqi8}
 \newcommand{\IR}{\mbox{$I\!\!R$}}
 \newcommand{\IP}{\mbox{$I\!\!P$}}
 \newcommand{\IN}{\mbox{$I\!\!N$}}
 \newcommand{\IC}{\mbox{$C\!\!\!\!\raisebox{.75pt}{\mbox{\sqi I}}$}}
 %Use $\IC \;\;$
 % multivalued arrow
 \newcommand{\marrow}{\hbox{$\rightarrow$ \hskip -10pt
		       $\rightarrow$ \hskip 3pt}}
 % phi
 \renewcommand{\phi}{\varphi}
 %\renewcommand{\Diamond}{{\bf Large \diamond}}
 \newcommand{\Circ}{\mbox{{\small $\bigcirc$}}}
 \newcommand{\lt}{<}
 \newcommand{\gt}{>}
 \newcommand{\all}{\forall}
 \newcommand{\infinity}{\infty}
 %binomial coefficient:
 \newcommand{\bc}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array} \right)}
 \newcommand{\cross}{\times}
 \newcommand{\bigfootnote}[1]{{\footnote{\normalsize #1}}}
 \newcommand{\medfootnote}[1]{{\footnote{\small #1}}}
 \newcommand{\bd}{\bf}

 % Joe's Section

 \newcommand{\imp}{\Rightarrow}

 %\H, \L, \O, \P and \S already taken; but we're redefining \P anyway
 \newcommand{\A}{{\cal A}}
 \newcommand{\B}{{\cal B}}
 \newcommand{\C}{{\cal C}}
 \newcommand{\D}{{\cal D}}
 \newcommand{\E}{{\cal E}}
 \newcommand{\F}{{\cal F}}
 \newcommand{\G}{{\cal G}}
 %\newcommand{\H}{{\cal H}}
 \newcommand{\I}{{\cal I}}
 \newcommand{\J}{{\cal J}}
 \newcommand{\K}{{\cal K}}
 %\newcommand{\L}{{\cal L}}
 \newcommand{\M}{{\cal M}}
 \newcommand{\N}{{\cal N}}
 %\newcommand{\O}{{\cal O}}
 \newcommand{\Ocal}{{\cal O}}
 \newcommand{\Hcal}{{\cal H}}
 \renewcommand{\P}{{\cal P}}
 \newcommand{\Q}{{\cal Q}}
 \newcommand{\R}{{\cal R}}
 %\newcommand{\S}{{\cal S}}
 \newcommand{\T}{{\cal T}}
 \newcommand{\U}{{\cal U}}
 \newcommand{\V}{{\cal V}}
 \newcommand{\W}{{\cal W}}
 \newcommand{\X}{{\cal X}}
 \newcommand{\Y}{{\cal Y}}
 \newcommand{\Z}{{\cal Z}}

 \newcommand{\Kone}{{\cal K}_1}
 \newcommand{\abs}[1]{\left| #1\right|}
 \newcommand{\set}[1]{\left\{ #1 \right\}}
 \newcommand{\Ki}{{\cal K}_i}
 \newcommand{\Kn}{{\cal K}_n}
 \newcommand{\st}{\, \vert \,} %vertical bar with space around it
 \newcommand{\stc}{\, : \,} %colon with space around it
 \newcommand{\la}{\langle}
 \newcommand{\ra}{\rangle}
 \newcommand{\<}{\langle}
 \renewcommand{\>}{\rangle}
 \newcommand{\lang}{\mbox{${\cal L}_n$}}
 \newcommand{\langd}{\mbox{${\cal L}_n^D$}}

 %\renewcommand{\Box}{\mathbin{\vcenter{\hrule
 %    \hbox{\vrule \kern .6em
 %          \vbox to .6em{}\vrule}\hrule}}\hspace{.17ex}}
 \newtheorem{nlem}{Lemma}
 \newtheorem{Ob}{Observation}
 \newtheorem{pps}{Proposition}
 \newtheorem{defn}{Definition}
 \newtheorem{crl}{Corollary}
 \newtheorem{cl}{Claim}
 \newcommand{\pf}{\par\noindent{\bf Proof}~~}
 \newcommand{\eg}{e.g.,~}
 \newcommand{\ie}{i.e.,~}
 \newcommand{\vs}{vs.~}
 \newcommand{\cf}{cf.~}
 \newcommand{\etal}{et al.\ }
 \newcommand{\resp}{resp.\ }
 \newcommand{\respc}{resp.,\ }
 \newcommand{\comment}[1]{\marginpar{\scriptsize\raggedright #1}}
 \newcommand{\wrt}{with respect to~}
 \newcommand{\re}{r.e.}
 \newcommand{\nind}{\noindent}
 \newcommand{\distributed}{distributed\ }
 \newcommand{\bn}{\bigskip\markright{NOTES}
 %\nind{\bf Notes:} \ }
 %\newcommand{\bn}{
 \section*{Notes}}
 \newcommand{\Exer}{
 \bigskip\markright{EXERCISES}
 %\nind{\bf Exercises} \ }
 \section*{Exercises}}
 \newcommand{\DG}{D_G}
 \newcommand{\Sm}{{\rm S5}_m}
 \newcommand{\Smc}{{\rm S5C}_m}
 \newcommand{\Smi}{{\rm S5I}_m}
 \newcommand{\Smic}{{\rm S5CI}_m}
 \newcommand{\Martin}{Mart\'\i n\ }
 \newcommand{\ol}{\setlength{\itemsep}{0pt}\begin{enumerate}}
 \newcommand{\eol}{\end{enumerate}\setlength{\itemsep}{-\parsep}}
 \newcommand{\ul}{\setlength{\itemsep}{0pt}\begin{itemize}}
 \newcommand{\dl}{\setlength{\itemsep}{0pt}\begin{description}}
 \newcommand{\edl}{\end{description}\setlength{\itemsep}{-\parsep}}
 \newcommand{\eul}{\end{itemize}\setlength{\itemsep}{-\parsep}}
 \newtheorem{fthm}{Theorem}
 \newtheorem{flem}[fthm]{Lemma}
 \newtheorem{fcor}[fthm]{Corollary}
 \newcommand{\slidehead}[1]{
 \eject
 \Huge
 \begin{center}
 {\bf #1 }
 \end{center}
 \vspace{.5in}
 \LARGE}

 %chck macros
 \newcommand{\subG}{_G}
 \newcommand{\If}{{\bf if}}

 \newcommand{\attime}{{\tt \ at\_time\ }}
 \newcommand{\hatell}{\skew6\hat\ell\,}
 \newcommand{\Then}{{\bf then}}
 \newcommand{\Until}{{\bf until}}
 \newcommand{\Else}{{\bf else}}
 \newcommand{\Repeat}{{\bf repeat}}
 \newcommand{\cA}{{\cal A}}
 \newcommand{\cE}{{\cal E}}
 \newcommand{\cF}{{\cal F}}
 \newcommand{\cI}{{\cal I}}
 %\newcommand{\IcR}{{\cal I}_{\cal R}}
 %\newcommand{\IRca}{{\cal I}_\Rca}
 %\newcommand{\Rca}{{\cR_{ca}}}
 \newcommand{\cN}{{\cal N}}
 \newcommand{\cR}{{\cal R}}
 \newcommand{\cS}{{\cal S}}
 \newcommand{\BN}{B^{\scriptscriptstyle \cN}}
 \newcommand{\BS}{B^{\scriptscriptstyle \cS}}
 \newcommand{\cW}{{\cal W}}
 \newcommand{\EG}{E_G}
 \newcommand{\CG}{C_G}
 \newcommand{\CN}{C_\cN}
 \newcommand{\ES}{E_\cS}
 \newcommand{\EN}{E_\cN}
 \newcommand{\CS}{C_\cS}
 %\newcommand{\RP}{{\cR_P}}
 %\newcommand{\IRP}{{\cal I}_\RP}
 %\newcommand{\RSBA}{{\cR_{\it sba}}}
 %\newcommand{\IRSBA}{{\cal I}_\RSBA}

 \newcommand{\attack}{\mbox{{\it attack}}}
 \newcommand{\attacking}{\mbox{{\it attacking}}}
 \newcommand{\delivered}{\mbox{{\it delivered}}}
 \newcommand{\exist}{\mbox{{\it exist}}}
 \newcommand{\decide}{\mbox{{\it decide}}}
 \newcommand{\clean}{{\it clean}}
 \newcommand{\diff}{{\it diff}}
 \newcommand{\Failed}{{\it failed}}
 %\newcommand{\RF}{\cR_{\scriptscriptstyle {\cal F}}}
 %\newcommand\eqdef{\buildrel {\rm def}\over =}
 \newcommand\eqdef{=_{\rm def}}
 \newcommand{\true}{\mbox{{\it true}}}
 \newcommand{\false}{\mbox{{\it false}}}

 %book macros
 \newcommand{\DN}{D_{\cN}}
 \newcommand{\DS}{D_{\cS}}
 \newcommand{\tyme}{{\it time}}
 \newcommand{\fp}{f}

 %chguide macros
 \newcommand{\Kax}{{\rm K}_n}
 \newcommand{\Kaxc}{{\rm K}_n^C}
 \newcommand{\Kaxd}{{\rm K}_n^D}
 \newcommand{\Tax}{{\rm T}_n}
 \newcommand{\Taxc}{{\rm T}_n^C}
 \newcommand{\Taxd}{{\rm T}_n^D}
 \newcommand{\fourax}{{\rm S4}_n}
 \newcommand{\fouraxc}{{\rm S4}_n^C}
 \newcommand{\fouraxd}{{\rm S4}_n^D}
 \newcommand{\fiveax}{{\rm S5}_n}
 \newcommand{\fiveaxc}{{\rm S5}_n^C}
 \newcommand{\fiveaxd}{{\rm S5}_n^D}
 \newcommand{\Dax}{{\rm KD45}_n}
 \newcommand{\Daxc}{{\rm KD45}_n^C}
 \newcommand{\Daxd}{{\rm KD45}_n^D}
 \newcommand{\LP}{{\cal L}_n}
 \newcommand{\LCP}{{\cal L}_n^C}
 \newcommand{\LDP}{{\cal L}_n^D}
 \newcommand{\LCDP}{{\cal L}_n^{CD}}
 \newcommand{\MP}{{\cal M}_n}
 \newcommand{\MPr}{{\cal M}_n^r}
 %\newcommand{\MPrt}{{\cal M}_n^{rt}}
 \newcommand{\MPrt}{\M_n^{\mbox{\scriptsize{{\it rt}}}}}
 %\newcommand{\MPrst}{{\cal M}_n^{rst}}
 \newcommand{\MPrst}{\M_n^{\mbox{\scriptsize{{\it rst}}}}}
 %\newcommand{\MPelt}{{\cal M}_n^{elt}}
 \newcommand{\MPelt}{\M_n^{\mbox{\scriptsize{{\it elt}}}}}
 \renewcommand{\lang}{\mbox{${\cal L}_{n} (\Phi)$}}
 \renewcommand{\langd}{\mbox{${\cal L}_{n}^D (\Phi)$}}
 \newcommand{\fiveaxdu}{{\rm S5}_n^{DU}}
 \newcommand{\LPD}{{\cal L}_n^D}
 \newcommand{\fiveaxu}{{\rm S5}_n^U}
 \newcommand{\fiveaxcu}{{\rm S5}_n^{CU}}
 \newcommand{\LPU}{{\cal L}^{U}_n}
 \newcommand{\LPCU}{{\cal L}_n^{CU}}
 \newcommand{\LDPU}{{\cal L}_n^{DU}}
 \newcommand{\LCPU}{{\cal L}_n^{CU}}
 \newcommand{\LPDU}{{\cal L}_n^{DU}}
 \newcommand{\LPCDU}{{\cal L}_n^{\it CDU}}
 \newcommand{\Cn}{\C_n}
 %\newcommand{\CSn}{\I_n^{cs}(\Phi)}
 %\newcommand{\CSn}{\I_n^{oa}(\Phi)}
 %\newcommand{\CSnm}{\I_n^{oa}}
 %\newcommand{\CSnp}{\I_n^{cs}(\Phi')}
 \newcommand{\CSnp}{\I_n^{oa}(\Phi')}
 %\newcommand{\CSc}{\C_n^{cs}(\Phi)}
 \newcommand{\CSc}{\C_n^{oa}(\Phi)}
 %\newcommand{\Ccs}{\C_n^{cs}}
 \newcommand{\Ccs}{\C_n^{oa}}
 %ron
 %\newcommand{\CSAX}{CS$_{{{n}},\Phi}$}
 %\newcommand{\CSAXN}{CS$_{{{n}},\Phi}'$}
 \newcommand{\CSAX}{OA$_{n,\Phi}$}
 \newcommand{\CSAXN}{OA$_{n,{\Phi}}'$}
 %\newcommand{\IKB}{\I_n^{KB}}
 \newcommand{\untill}{U}
 \newcommand{\until}{\, U \,}
 \newcommand{\amp}{{\rm a.m.p.}}
 \newcommand{\commentout}[1]{}
 \newcommand{\msgc}[1]{ @ #1 }
 \newcommand{\Camp}{{\C_n^{\it amp}}}
 \newcommand{\bi}{\begin{itemize}}
 \newcommand{\ei}{\end{itemize}}
 \newcommand{\be}{\begin{enumerate}}
 \newcommand{\ee}{\end{enumerate}}
 \newcommand{\rarrowr}{\stackrel{r}{\rightarrow}}
 \newcommand{\ack}{\mbox{\it ack}}
 \newcommand{\Gz}{\G_0}
 \newcommand{\denselist}{\itemsep 0pt\partopsep 0pt}
 \def\seealso#1#2{({\em see also\/} #1), #2}

  \newenvironment{oldthm}[1]{\par\noindent{\bf Theorem #1:} \em \noindent}{\par}
  \newenvironment{oldlem}[1]{\par\noindent{\bf Lemma #1:} \em \noindent}{\par}
  \newenvironment{oldcor}[1]{\par\noindent{\bf Corollary #1:} \em \noindent}{\par}
  \newenvironment{oldpro}[1]{\par\noindent{\bf Proposition #1:} \em \noindent}{\par}
  \newcommand{\othm}[1]{\begin{oldthm}{\ref{#1}}}
  \newcommand{\eothm}{\end{oldthm} \medskip}
  \newcommand{\olem}[1]{\begin{oldlem}{\ref{#1}}}
  \newcommand{\eolem}{\end{oldlem} \medskip}
  \newcommand{\ocor}[1]{\begin{oldcor}{\ref{#1}}}
  \newcommand{\eocor}{\end{oldcor} \medskip}
  \newcommand{\opro}[1]{\begin{oldpro}{\ref{#1}}}
  \newcommand{\eopro}{\end{oldpro} \medskip}


  %general miscellanous
  \newcommand{\world}{W}
  \newcommand{\WN}{\W_N}
  \newcommand{\Winf}{\W^*}
  \newcommand{\tends}{\rightarrow}
  \newcommand{\tendsto}{\tends}
  \newcommand{\ninfty}{{N \rightarrow \infty}}
  \newcommand{\nworldsv}[1]{{\it \#worlds}^{#1}}
  \newcommand{\nworlds}{{{\it \#worlds}}_{N}^{\epsvec}}
  \newcommand{\nwrldPnt}[1]{\nworlds[#1]}
  \newcommand{\nworldsarg}[1]{\nworlds[#1]}
  \newcommand{\binco}[2]{{{#1}\choose{#2}}}
  \newcommand{\closure}[1]{{\overline{#1}}}
  \newcommand{\balpha}{\bar{\alpha}}
  \newcommand{\bbeta}{\bar{\beta}}
  \newcommand{\bgamma}{\bar{\gamma}}
  \newcommand{\half}{\frac{1}{2}}
  \newcommand{\bQ}{\overline{Q}}
  %FB4: added
  \newcommand{\Vector}[1]{{\langle #1 \rangle}}
  %algorithms
  \newcommand{\Algzeroone}{\mbox{\em Compute01}}
  \newcommand{\Algcompute}{\mbox{{\em Compute-Pr}$_\infty$}}


  % probabilities
  \newcommand{\Prinfv}[1]{{\Pr}^{#1}_\infty}
  \newcommand{\PrNv}[1]{{\Pr}^{#1}_N}
  \newcommand{\Prinf}{{\Pr}_\infty}
  \newcommand{\PrN}{{\Pr}_N}
  \newcommand{\pN}{\PrN (\phi | \KB)}
  \newcommand{\IPrinf}{{\Box\Diamond\Prinf}}
  \newcommand{\PPrinf}{{\Diamond\Box\Prinf}}
  \newcommand{\prNw}{{\Pr}_{N}^{\epsvec}}
  \newcommand{\prNwi}{{\Pr}_{N^i}^{\epsvec^i}}
  \newcommand{\priw}{{\Pr}_{\infty}}
  \newcommand{\beliefprob}[1]{\Pr(#1)} %daphne1 - changed macro
  \newcommand{\Prinfeps}{{{\Pr}_\infty^{\epsvec}}}
  \newcommand{\PrNeps}{{{\Pr}_N^{\epsvec}}}
  \newcommand{\Pinf}[2]{{\Pi_\infty^{#1}[#2]}}

  % vocabularies
  \newcommand{\infvocab}{\Omega}
  \newcommand{\infunvocab}{\Upsilon}
  \newcommand{\vocab}{\Phi}
  \newcommand{\nonunaryvocab}{\vocab}
  \newcommand{\unvocab}{\Psi}

  % languages
  \newcommand{\cL}{{\cal L}}
  \newcommand{\cLne}{{\cal L}^-}
  \newcommand{\finitelang}{\cL_i^d(\Phi)}
  \newcommand{\fLd}{\cL_d^d(\Phi)}
  \newcommand{\cLd}{\cL_{\mbox{\em \scriptsize$d$}}(\Phi)}
  \newcommand{\Laeq}{{\cal L}^{\aeq}}
  \newcommand{\Leq}{{\cal L}^{=}}
  \newcommand{\Lunaeq}{\Laeq_1}
  \newcommand{\Luneq}{\Leq_1}


  %formulas
  \newcommand{\KB}{{\it KB}}
   %GHK1a
  \newcommand{\phieven}{\phi_{\mbox{\footnotesize\it even}}}
  \newcommand{\phiodd}{\phi_{\mbox{\footnotesize\it odd}}}
  \newcommand{\KBM}{\KB_{\boldM}}
   %GHK1b
  \newcommand{\Pstar}{P^*}
  \newcommand{\barP}{\neg P}
  \newcommand{\barQ}{\neg Q}
  \newcommand{\maxarity}{\rho}
  \newcommand{\Init}{\mbox{\it Init\/}}
  \newcommand{\Rep}{\mbox{\it Rep\/}}
  \newcommand{\Acc}{\mbox{\it Acc\/}}
  \newcommand{\Comp}{\mbox{\it Comp\/}}
  \newcommand{\Step}{\mbox{\it Step\/}}
  \newcommand{\Univ}{\mbox{\it Univ\/}}
  \newcommand{\Exis}{\mbox{\it Exis\/}}
  \newcommand{\Between}{\mbox{\it Between\/}}
  \newcommand{\Count}{\mbox{\it count\/}}
  \newcommand{\phiq}{\phi_Q}
  \newcommand{\propform}{\beta}
  \newcommand{\allphi}{\ast}
  \newcommand{\ID}{\mbox{\it ID}}
  \newcommand{\atomdesc}{{\psi_*}}
  \newcommand{\rigid}{\mbox{\it rigid}}
  \newcommand{\abdesc}{\widehat{D}}
  \newcommand{\KBtwo}{\theta}
  \newcommand{\psits}{\psi[\KBtwo,\abdesc]}
  \newcommand{\psitsnohat}{\psi[\KBtwo,D]}
  %BGHK
  \newcommand{\KBfly}{\KB_{\mbox{\scriptsize \it fly}}}
  \newcommand{\KBchirps}{\KB_{\mbox{\scriptsize \it chirps}}}
  \newcommand{\KBmagpie}{\KB_{\mbox{\scriptsize \it magpie}}}
  \newcommand{\KBhep}{\KB_{\mbox{\scriptsize \it hep}}}
  \newcommand{\KBnixon}{\KB_{\mbox{\scriptsize \it Nixon}}}
  \newcommand{\KBel}{\KB_{\mbox{\scriptsize \it likes}}}
  \newcommand{\KBtax}{\KB_{\mbox{\scriptsize \it taxonomy}}}
  \newcommand{\KBarm}{\KB_{\mbox{\scriptsize \it arm}}}
  \newcommand{\KBlate}{\KB_{\mbox{\scriptsize \it late}}}
  \newcommand{\KBp}{{\KB'}}
  \newcommand{\KBflyp}{\KB_{\mbox{\scriptsize \it fly}}'}
  \newcommand{\KBpp}{{\KB''}}
  \newcommand{\KBdef}{\KB_{\mbox{\scriptsize \it def}}}
  \newcommand{\KBdishep}{\KB_{\mbox{\scriptsize \it $\lor$hep}}}

  %GHK2
  \newcommand{\canKB}{\widehat{\KB}}
  \newcommand{\canxi}{\widehat{\xi}}
  \newcommand{\KBfo}{\KB_{\it fo}}
  \newcommand{\KBconst}{\psi}
  \newcommand{\KBprop}{\KBp}


  %predicates
  \newcommand{\quak}{\mbox{\it Quaker\/}}
  \newcommand{\repub}{\mbox{\it Republican\/}}
  \newcommand{\pac}{\mbox{\it Pacifist\/}}
  \newcommand{\Nixon}{\mbox{\it Nixon\/}}
  \newcommand{\Winner}{\mbox{\it Winner\/}}
  \newcommand{\Child}{\mbox{\it Child\/}}
  \newcommand{\Boy}{\mbox{\it Boy\/}}
  \newcommand{\Tall}{\mbox{\it Tall\/}}
  \newcommand{\Elephant}{\mbox{\it Elephant\/}}
  \newcommand{\Gray}{\mbox{\it Gray\/}}
  \newcommand{\Yellow}{\mbox{\it Yellow\/}}
  \newcommand{\Clyde}{\mbox{\it Clyde\/}}
  \newcommand{\Tweety}{\mbox{\it Tweety\/}}
  \newcommand{\Opus}{\mbox{\it Opus\/}}
  \newcommand{\Bird}{\mbox{\it Bird\/}}
  \newcommand{\Penguin}{{\it Penguin\/}}
  \newcommand{\Fish}{\mbox{\it Fish\/}}
  \newcommand{\Fly}{\mbox{\it Fly\/}}
  \newcommand{\Warmblooded}{\mbox{\it Warm-blooded\/}}
  \newcommand{\White}{\mbox{\it White\/}}
  \newcommand{\Red}{\mbox{\it Red\/}}
  \newcommand{\Winged}{\mbox{\it Winged\/}}
  \newcommand{\Giraffe}{\mbox{\it Giraffe\/}}
  \newcommand{\Visible}{\mbox{\it Easy-to-see\/}}
  \newcommand{\Bat}{\mbox{\it Bat\/}}
  \newcommand{\Blue}{\mbox{\it Blue\/}}
  \newcommand{\Fever}{\mbox{\it Fever\/}}
  \newcommand{\Jaun}{\mbox{\it Jaun\/}}
  \newcommand{\Hep}{\mbox{\it Hep\/}}
  \newcommand{\Eric}{\mbox{\it Eric\/}}
  \newcommand{\Alice}{\mbox{\it Alice\/}}
  \newcommand{\Tom}{\mbox{\it Tom\/}}
  \newcommand{\Lottery}{\mbox{\it Lottery\/}}
  \newcommand{\Zookeeper}{\mbox{\it Zookeeper\/}}
  \newcommand{\Fred}{\mbox{\it Fred\/}}
  \newcommand{\Likes}{\mbox{\it Likes\/}}
  \newcommand{\Day}{\mbox{\it Day\/}}
  \newcommand{\Nextday}{\mbox{\it Next-day\/}}
  \newcommand{\Sleepslate}{\mbox{\it To-bed-late\/}}
  \newcommand{\Riseslate}{\mbox{\it Rises-late\/}}
  \newcommand{\TS}{\mbox{\it TS\/}}
  \newcommand{\EEJ}{\mbox{\it EEJ\/}}
  \newcommand{\FC}{\mbox{\it FC\/}}
  \newcommand{\Dodo}{\mbox{\it Dodo\/}}
  \newcommand{\Ab}{\mbox{\it Ab\/}}
  \newcommand{\Chirps}{\mbox{\it Chirps\/}}
  \newcommand{\Swims}{\mbox{\it Swims\/}}
  \newcommand{\Magpie}{\mbox{\it Magpie\/}}
  \newcommand{\Moody}{\mbox{\it Moody\/}}
  \newcommand{\SomeMorning}{\mbox{\it Tomorrow\/}}
  \newcommand{\Animal}{\mbox{\it Animal\/}}
  \newcommand{\Sparrow}{\mbox{\it Sparrow\/}}
  \newcommand{\Turtle}{\mbox{\it Turtle\/}}
  \newcommand{\Older}{\mbox{\it Over60\/}}
  \newcommand{\Patient}{\mbox{\it Patient\/}}
  \newcommand{\Black}{\mbox{\it Black\/}}
  \newcommand{\Ray}{\mbox{\it Ray\/}}
  \newcommand{\Reiter}{\mbox{\it Reiter\/}}
  \newcommand{\Drew}{\mbox{\it Drew\/}}
  \newcommand{\McDermott}{\mbox{\it McDermott\/}}
  \newcommand{\Emu}{\mbox{\it Emu\/}}
  \newcommand{\Canary}{\mbox{\it Canary\/}}
  \newcommand{\BlueCanary}{\mbox{\it BlueCanary\/}}
  \newcommand{\FlyingBird}{\mbox{\it FlyingBird\/}}
  \newcommand{\UL}{\mbox{\it LeftUsable\/}}
  \newcommand{\UR}{\mbox{\it RightUsable\/}}
  \newcommand{\BL}{\mbox{\it LeftBroken\/}}
  \newcommand{\BR}{\mbox{\it RightBroken\/}}
  \newcommand{\Ticket}{\mbox{\it Ticket\/}}
  \newcommand{\BlueEyed}{{\mbox{\it BlueEyed\/}}}
  \newcommand{\Jaundice}{{\it Jaundice\/}}
  \newcommand{\Hepatitis}{{\it Hepatitis\/}}
  \newcommand{\HeartDisease}{{\mbox{\it Heart-disease\/}}}
  \newcommand{\bJ}{{\overline{J}\,}}
  \newcommand{\bH}{{\overline{H}\,}}
  \newcommand{\bB}{{\overline{B}\,}}
  \newcommand{\Prem}{{\mbox{\it Child\/}}}
  \newcommand{\David}{{\mbox{\it David\/}}}
  \newcommand{\Son}{{\mbox{\it Son\/}}}	% changed


  %miscellaneous  GHK1a+b
  \newcommand{\ceslim}{Ces\`{a}ro limit}
  \newcommand{\Sigmad}{\Sigma^d_i}
  \newcommand{\Liogonkii}{Liogon'ki\u\i}
  \newcommand{\Vstar}{{\modfrag_*}}
  \newcommand{\moddesc}{\psi \land \modfrag}
  \newcommand{\sumact}{\Degr_2}
  \newcommand{\degree}{\Degr_1}
  \newcommand{\Active}{\alpha}
  \newcommand{\ActiveAtoms}{\boldA}
  \newcommand{\named}{n}
  \newcommand{\aactive}{a}
  \newcommand{\degr}{\delta}
  \newcommand{\chsize}{f}
  \newcommand{\chconst}{g}
  \newcommand{\Chconst}{G}
  \newcommand{\Degr}{\Delta}
  \newcommand{\frags}{\M}
  \newcommand{\const}{H}
  \newcommand{\modfrag}{\V}
  \newcommand{\AD}{\A}
  \newcommand{\Named}{\nu}
  \newcommand{\bit}{b}
  \newcommand{\guess}{\gamma}
  \newcommand{\bxor}[1]{\dot{\bor}}
  \newcommand{\weight}{\omega}
  %\newcommand{\arity}{r}
  \newcommand{\arity}{{\it arity}}
  \newcommand{\assigned}{\leftarrow}
  \newcommand{\snum}[2]{{{#1} \brace {#2}}}


  %proportions & approximate equality
  \newcommand{\eps}{\tau}
  \newcommand{\vareps}{\varepsilon}
  \newcommand{\varepsvec}{{\vec{\vareps}}}
  \newcommand{\xtuple}{\vec{x}}
  \newcommand{\ctuple}{{\vec{c}\,}}
  \newcommand{\uvec}{{\!{\vec{\,u}}}}
  \newcommand{\ucom}{u}
  %FB4 I don't know why you set pvec, pcom to be u! But I needed a pvec,
  %so I changed it. Please beware if using this for files other than
  %BGHK!
  %\newcommand{\pvec}{{\!{\vec{\,u}}}}
  \newcommand{\pvec}{{\!{\vec{\,p}}}}
  %\newcommand{\pcom}{u}
  \newcommand{\pcom}{p}
  \newcommand{\vvec}{\vec{v}}
  \newcommand{\wvec}{\vec{w}}
  \newcommand{\xvec}{\vec{x}}
  \newcommand{\yvec}{\vec{y}}
  \newcommand{\zvec}{\vec{z}}
  \newcommand{\zerovec}{\vec{0}}

  \newcommand{\epscom}{\eps}
  \newcommand{\epsvec}{{\vec{\eps}\/}}
  \newcommand{\prop}[2]{{||{#1}||_{{#2}}}}
  \newcommand{\aeq}{\approx} %``Approximate'' connectives
  \newcommand{\app}{\approx}
  \newcommand{\alt}{\prec}
  \newcommand{\aleq}{\preceq}
  \newcommand{\agt}{\succ}
  \newcommand{\ageq}{\succeq}
  \newcommand{\altne}{\prec}
  \newcommand{\naeq}{\not\approx}
  \newcommand{\cprop}[3]{{\|{#1}|{#2}\|_{{#3}}}}
  \newcommand{\Bigcprop}[3]{{\Bigl\|{#1}\Bigm|{#2}\Bigr\|_{{#3}}}}


  %miscellaneous BGHK
  \newcommand{\reals}{\IR}
  \newcommand{\qsep}{\,}
  \newcommand{\perm}{\pi}
  \newcommand{\val}{V}
  \newcommand{\rwent}{\mbox{$\;|\!\!\!\sim$}_{\mbox{\scriptsize \it rw}}\;}
  \newcommand{\notrwent}{\mbox{$\;|\!\!\!\not\sim$}_{\mbox{\scriptsize\it rw}}\;}
  \newcommand{\dempster}{\delta}
  \newcommand{\dentails}{{\;|\!\!\!\sim\;}}
  \newcommand{\notdentails}{{\;|\!\!\!\not\sim\;}}
  \newcommand{\dentailssub}[1]{\dentails\hspace{-0.4em}_{
	    \mbox{\scriptsize{\it #1}}}\;}
  \newcommand{\notdentailssub}[1]{\notdentails\hspace{-0.4em}_{
	    \mbox{\scriptsize{\it #1}}}\;}
  \newcommand{\default}{\rightarrow}

  %miscellaneous GHK2
  \newcommand{\vecof}[1]{{\pi({#1})}}
  \newcommand{\PIN}[2]{{\Pi_N^{#1}[#2]}}
  \newcommand{\SS}[2]{{S^{#1}[#2]}}
  \newcommand{\SSc}[2]{{S^{#1}[#2]}}
  \newcommand{\SSzero}[1]{\SS{\zerovec}{#1}}
  \newcommand{\SSczero}[1]{\SSc{\zerovec}{#1}}
  \newcommand{\SSpos}[1]{\SS{\leq \zerovec}{#1}}
  \newcommand{\Sol}{{\it Sol}}
  \newcommand{\poscon}{\gamma}
  \newcommand{\constraints}{\Gamma}
  \newcommand{\constpos}{\constraints^{\leq}}
  %\newcommand{\vareps}{\varepsilon}
  \newcommand{\propspace}{\Delta^K}
  \newcommand{\mept}{\vvec}
  \newcommand{\mecoord}{v}
  \newcommand{\mepts}{{\Q}}
  \newcommand{\OS}{{\cal O}}
  \renewcommand{\S}{{\cal S}}
  \newcommand{\meval}{{\rho}}
  \newcommand{\meptmin}{{\uvec^{\ast}_{\mbox{\scriptsize min}}}}
  \newcommand{\sizeof}[1]{{\sigma(#1)}}
  \newcommand{\mesize}{{\sigma^{\ast}}}
  \renewcommand{\pf}{\alpha}
  \newcommand{\ps}{\beta}
  \newcommand{\Atoms}{\AD}
  \newcommand{\limNstar}{{\lim_{N \rightarrow \infty}}^{\!\!\!*}\:}
  \newcommand{\probf}[2]{F_{[#1|#2]}}
  \newcommand{\probfun}[1]{F_{[#1]}}
  \newcommand{\Prmu}[1]{{\mu}_{#1}}
  \newcommand{\foversion}[1]{\xi_{#1}}
  \newcommand{\fly}{\mbox{\it fly\/}}
  \newcommand{\bird}{\mbox{\it bird\/}}
  \newcommand{\yellow}{\mbox{\it yellow\/}}
  \newcommand{\propconsts}{\Lambda}
  \newcommand{\alldiff}{\chi^{\neq}}
  \newcommand{\unaryD}{D^1}
  \newcommand{\nonunD}{D^{> 1}}
  \newcommand{\eqD}{D^{=}}






 \renewcommand{\bbox}{\wbox}
 %\renewcommand{\citeyear}{\shortcite}
 \newcommand{\Bel}{\mbox{Bel}}
 \newcommand{\Belo}{\mbox{Bel}_0}
 \newcommand{\Belod}{\mbox{Bel}_0}
 %\setcounter{secnumdepth}{3}


 \jairheading{10}{1999}{67--85}{6/98}{2/99}
 \ShortHeadings{A Counterexample to Theorems of Cox and Fine}{Halpern}
 \firstpageno{67}


 \begin{document}


 %\begin{titlepage}
 \title{A Counterexample to Theorems of Cox and Fine}
 \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
 }
 %\date{\today}
 \maketitle
 %\thispagestyle{empty}

 \begin{abstract}
 Cox's well-known theorem justifying the use of probability is shown
 not to hold in finite domains.
 The counterexample also suggests that Cox's assumptions are
 insufficient to prove the result even in infinite domains.
 The same  counterexample is used
 to disprove a result of Fine on comparative conditional probability.
 \end{abstract}
 %\vfill
 %\noindent
 %{\bf Content areas:} mathematical foundations, probabilistic reasoning\\
 %{\bf Word count:} 5690\\
 %{\bf Tracking Number: A627}\\
 %This paper is not being submitted to any other conferences.
 %\vfill
 %This paper has also been submitted to AAAI '96.  The decision about
 %withdrawal (if relevant) will be made by March 12, 1996.
 %\end{titlepage}


 \section{Introduction}
 One of the best-known and seemingly most compelling justifications
 of the use of probability is given by Cox \citeyear{Cox}.
 Suppose we have a function $\Bel$ that associates a
 real number with each pair $(U,V)$ of subsets of a domain
 $W$ such that
 $U \ne
 \emptyset$.  We write $\Bel(V|U)$ rather than $\Bel(U,V)$, since we
 think of $\Bel(V|U)$ as the credibility or likelihood of $V$ given $U$.%
 \footnote{Cox writes $V|U$ rather than $\Bel(V|U)$, and takes $U$ and
 $V$ to be propositions in some language rather than events, \ie subsets
 of a given
 set.  This difference is minor---there are well-known mappings from
 propositions to events, and vice versa.  I use events here since they
 are more standard in the probability literature.}
 Cox further assumes that $\Bel(\overline{V}|U)$
 is a function
 of $\Bel(V|U)$ (where $\overline{V}$ denotes the complement of $V$ in
 $W$), that is, there is a function $S$
 %(satisfying conditions discussed below)
 such that
 \begin{description}
 \item[A1.] $\Bel(\overline{V}|U) = S(\Bel(V|U))$ if $U \ne \emptyset$,
 \end{description}
 and that
 $\Bel(V \inter V'|U)$ is a function of
 $\Bel(V'|V \inter U)$ and $\Bel(V|U)$, that is, there is a function $F$
 %(satisfying conditions discussed below)
 such that
 \begin{description}
 \item[A2.] $\Bel(V \inter V'|U)
 = F(\Bel(V'| V \inter U), \Bel(V|U))$ if $V \inter U \ne \emptyset$.
 \end{description}

 Notice that if $\Bel$ is a probability function, then we can take
 $S(x) = 1-x$ and $F(x,y) = xy$.  Cox makes much weaker assumptions:
 he assumes that $F$ is twice differentiable, with a continuous
 second derivative, and that $S$ is twice differentiable.
 Under these assumptions, he shows that
 $\Bel$ is isomorphic to a probability distribution in the sense that
 there is a continuous one-to-one onto
 function $g: \IR \rightarrow \IR$ such
 that $g \circ \Bel$ is a probability distribution on $W$, and
 \begin{equation}\label{eq7}
 g(\Bel(V|U)) \times g(\Bel(U)) = g(\Bel(V \inter U)) \mbox{ if $U \ne
 \emptyset$,}
 \end{equation}
 where $\Bel(U)$ is an abbreviation for $\Bel(U|W)$.

 Not surprisingly, Cox's result has attracted a great deal of interest,
 particularly in the maximum entropy community and, more recently, in the
 AI community. For example
 \begin{itemize}
 \item Cheeseman \citeyear{Cheeseman88} has called it the
 ``strongest argument for use of standard (Bayesian)
 probability theory''.  Similar sentiments are expressed by Jaynes
 \citeyear[p.~24]{Jaynes}; indeed, Cox's Theorem is one of the
 cornerstones of Jaynes' recent book \citeyear{Jaynes97}.
 \item Horvitz, Heckerman, and Langlotz \citeyear{HHL}
 used it as a basis for comparison of probability and other
 nonprobabilistic approaches to reasoning about uncertainty.
 \item Heckerman \citeyear{Heck88} used it as a basis for providing an
 axiomatization for belief update.
 \end{itemize}
 The main contribution of this paper is to show (by means of an
 explicit counterexample) that Cox's result does not hold in
 finite domains, even under strong assumptions
 on $S$ and $F$ (stronger than those made by Cox and those made
 in all papers proving variants of Cox's results).  Since finite
 domains are arguably those of most interest in AI applications,
 this suggests that arguments for
 using probability based on Cox's result---and other justifications
 similar in spirit---must be taken with a grain
 of salt, and their proofs carefully reviewed.
 Moreover, the counterexample suggests that Cox's assumptions are
 insufficient to prove the result even in infinite domains.

 It is known that some assumptions regarding $F$ and $S$ must be made
 to prove Cox's result.
 Dubois and Prade \citeyear{DP90} give an example of a
 function $\Bel$, defined on a finite domain,
 that is not isomorphic to a probability distribution.  For this choice
 of $\Bel$, we can take $F(x,y) = \min(x,y)$ and $S(x) = 1-x$.  Since
 $\min$ is not twice differentiable,
 Cox's assumptions  block the Dubois-Prade example.

 Other authors have made different assumptions.
 Acz\'el \citeyear[Section 7 (Theorem 1)]{Aczel}
 does not make any assumptions
 about $F$, but he does
 make two other assumptions, each of which block the Dubois-Prade
 example.  The first is that the $\Bel(V|U)$ takes on every value in some
 range  $[e,E]$, with $e < E$.  In the
 Dubois-Prade example, the domain is finite, so this
 certainly cannot hold.  The
 second is that if $V$ and $V'$ are disjoint, then there is a
 continuous function
 $G: \IR^2 \rightarrow \IR$, strictly increasing in each argument,
 such that
 \begin{description}
 \item[A3.] $\Bel(V \union V'|U) = G(\Bel(V|U),\Bel(V'|U))$.
 \end{description}
 With these assumptions, he gives a proof much in the spirit of that of
 Cox to show that $\Bel$ is essentially a probability distribution.
 Dubois
 and Prade point out that, in their example, there is no function
 $G$ satisfying A3 (even if we drop the requirement that $G$ be
 continuous and strictly increasing in each argument).%
 \footnote{In fact, Acz\'el allows there to be a different function $G_U$
 for each set $U$ on the right-hand side of the conditional.  However,
 the Dubois-Prade example does not even satisfy this weaker condition.}

 Reichenbach \citeyear{Reichenbach:Theory.Of.Probability} earlier
 proved a result similar to Acz\'el's, under somewhat stronger
 assumptions.  In particular, he assumed A3, with $G$ being $+$.

 Other variants of Cox's result have also been considered in the
 literature.  For example, Heckerman \citeyear{Heck88} and
 Horvitz, Heckerman, and Langlotz \citeyear{HHL} assume that
 $F$ is continuous and strictly increasing in each argument and $S$ is
 continuous and strictly decreasing.  Since $\min$ is not strictly
 continuous in each argument, it fails this restriction too.%
 \footnote{Actually, the restriction that $F$ be strictly increasing in
 each argument is a little too strong.  If $e = \Bel(\emptyset)$, then
 it can be shown that $F(e,x) = F(x,e) = e$ for all $x$, so that $F$
 is not strictly increasing if one of its arguments is $e$.}
 Aleliunas \citeyear{Aleliunas} gives yet another collection of
 assumptions and claims that they suffice
  to guarantee that $\Bel$ is essentially a
 probability distribution.
 %None of these authors make any assumptions
 %about the cardinality of the range of $\Bel$.

 The first to observe potential problems with Cox's result is Paris
 \citeyear{Paris94}.  As he puts it, ``Cox's proof is not,
 perhaps, as rigorous as some pedants might prefer and when an attempt is
 made to fill in all the details some of the attractiveness of the
 original is lost.''  Paris provides a rigorous proof of the result,
 assuming that the range of $\Bel$ is contained in $[0,1]$ and using
 assumptions similar to those of Horvitz, Heckerman, and
 Langlotz.  In particular, he assumes that $F$ is continuous and strictly
 increasing in $(0,1]^2$ and that $S$ is decreasing.
 However, he makes
 use of one additional assumption that, as he himself says, is not
 very appealing:
 \begin{description}
 \item[A4.] For all $0 \le \alpha, \beta, \gamma \le 1$ and $\epsilon >
 0$, there
 are sets $U_1 \supseteq U_2 \supseteq U_3 \supseteq U_4$ such that $U_3
 \ne \emptyset$, and each of
 $|\Bel(U_4|U_3) - \alpha|$, $|\Bel(U_3|U_2)
 - \beta|$, and $|\Bel(U_2|U_1) - \gamma|$
 is less than $\epsilon$.
 \end{description}
 Notice that this assumption forces the range of $\Bel$ to be dense
 in $[0,1]$.  This means that, in particular, the domain $W$
 on which $\Bel$ is defined cannot be finite.

 Is this assumption really necessary?  Paris suggests that Acz\'el needs
 something like it.  (This issue is discussed in further detail below.)
 The counterexample of this paper gives further evidence.  It shows
 that Cox's result fails in finite domains, even if we assume that
 the range of $\Bel$ is in $[0,1]$,
 $S(x) = 1-x$ (so that, in particular, $S$ is twice differentiable and
 monotonically decreasing), $G(x,y) = x+y$, and $F$ is infinitely
 differentiable and strictly increasing on $(0,1]^2$.
 We can further assume that $F$ is commutative, $F(0,x) = F(x,0) = 0$,
 and that $F(x,1) = F(1,x) = x$.
 The example emphasizes the point that the applicability of Cox's
 result is far narrower than was previously believed.
 It remains an open question as to whether there
 is an appropriate strengthening of the assumptions that
 does give us Cox's result in finite settings.
 There is further discussion of this issue in Section~\ref{discussion}.


 In fact, the example shows even more.
 In the course of his proof, Cox claims to show that $F$ must be an
 associative function, that is, that $F(x,F(y,z)) = F(F(x,y),z)$.
 %Paris makes heavy use of A3 in proving this.
 %Our proof shows that A4 really is needed.
 For the $\Bel$ of the counterexample, there can be no
 associative function $F$
 satisfying A2.   It is this observation that is the key to showing that
 there is no probability distribution isomorphic to $\Bel$.

 What is going on here?  Actually, Cox's proof
 just shows that $F(x,F(y,z)) = F(F(x,y),z)$ only for those triples
 $(x,y,z)$ such that, for some sets $U_1$, $U_2$, $U_3$, and
 $U_4$, we have $x =
 \Bel(U_4|U_3 \inter U_2 \inter U_1)$, $y = \Bel(U_3|U_2 \inter
 U_1)$, and $z = \Bel(U_2|U_1)$.  If the set of such triples
 $(x,y,z)$ is dense in $[0,1]^3$, then we conclude by continuity that
 $F$ is associative.  The content of A4 is precisely that the set of such
 triples is dense in $[0,1]^3$.  Of course, if $W$ is finite, we cannot
 have density.  As my counterexample shows, we do not in general
 have associativity in finite domains.  Moreover, this
 lack of associativity can
 result in the failure of Cox's theorem.

 A similar problem seems to exist in Acz\'el's proof (as already
 observed by Paris \citeyear{Paris94}).
 While Acz\'el's proof does not involve showing that $F$ is
 associative, it does involve showing that $G$ is associative.
 Again, it is not hard to show that $G$ is associative for appropriate
 triples, just as is the case for $F$.  But it seems that Acz\'el also
 needs an assumption that guarantees that the appropriate set of triples
 is dense, and it is not clear that his assumptions do in fact guarantee
 this.%
 \footnote{I should stress that my counterexample is not a
 counterexample to Acz\'el's theorem, since he explicitly assumes
 that the range of $\Bel$ is infinite.  However, it does point out
 potential problems with his proof, and certainly shows that his
 argument does not apply to finite domains.  Acz\'el is in fact aware of
 the problems with his proof [private communication, 1996].  He later
 proved
 results in a similar spirit with the aid of a requirement of
 {\em nonatomicity\/} \cite[pp.~5--6]{AczelDaroczy}, which is in fact a
 stronger requirement than A4, and thus also requires the domain to be
 infinite.}
 As shown in Section~\ref{reichsec}, the problem also arises in
 Reichenbach's proof.


 The counterexample to Cox's theorem, with slight modifications, can also
 be used to show that
 another well-known result in the literature is not completely correct.
 In his seminal book on probability and qualitative
 probability \citeyear{Fine},
 Fine considers a non-numeric notion of {\em comparative (conditional)
 probability}, which allows us to say ``$U$ given $V$ is at least as
 probable as $U'$ given $V'$'', denoted $U|V \succeq U'|V'$.
 Conditions on $\succeq$ are given
 that are claimed to force the existence of (among other things)
 a function $\Bel$ such that $U|V \succeq U'|V'$ iff $\Bel(U|V) \ge
 \Bel(U'|V')$ and
 an associative function $F$
 satisfying A2.
 (This is Theorem 8 of Chapter II in \cite{Fine}.)
 %However, the comparative conditional probability induced by the
 %$\Bel$ function in my example satisfies all of Fine's
 %conditions, yet there is no associative $F$ satisfying~A2.
 However, the $\Bel$ defined in my counterexample to Cox's theorem
 can be used to give a counterexample to this result as well.

 Interestingly, this is not the first time a similar error has been noted
 in the use of functional equations.  Falmagne \citeyear{Falmagne81}
 gives another example (in a case involving a utility model of choice
 behavior) and mentions that he knows ``of at least two similar examples
 in the psychological literature''.


 The remainder of this paper is organized as follows.  In the next
 section there is a more detailed discussion of the problem in
 Cox's proof.
 The counterexample
 to Cox's theorem is given in Section~\ref{counterexample}.  The
 following section shows that it is also a counterexample to Fine's
 theorem.  Section~\ref{discussion} concludes with some discussion,
 particularly of assumptions under which Cox's theorem might hold.

 \section{The Problem With Cox's Proof}\label{reichsec}
 To understand the problems with Cox's proof, I actually consider
 Reichenbach's proof, which is similar in spirit Cox's proof
 (it is actually even closer to Acz\'el's proof),
 but uses some additional assumptions, which makes it easier to explain
 in detail.  Acz\'el, Cox, and Reichenbach all make critical use of
 functional equations in their proof, and they make the same (seemingly
 unjustified) leap at corresponding points in their proofs.

 In the notation of this paper, Reichenbach \citeyear[pp.
 65--67]{Reichenbach:Theory.Of.Probability} assumes (1) that the
 range of $\Bel(\cdot|\cdot)$ is a subset of
 $[0,1]$, (2) $\Bel(V|U) = 1$ if $U \subseteq V$,
 (3) that if $V$ and
 $V'$ are disjoint, then $\Bel(V \union V'|U) = \Bel(V|U) + \Bel(V'|U)$
 (thus, he assumes that A3 holds, with $G$ being $+$), and (4) that A2
 holds with a function $F$ that
 is differentiable.  (He remarks that the result holds
 even without assumption (4), although the proof is more complicated;
 Acz\'el in fact does not make an assumption like (4).)

 Reichenbach's proof proceeds as follows:  Replacing $V'$ in A2 by
 $V_1 \union V_2$, where $V_1$ and $V_2$ are disjoint, we get that
 \begin{equation}\label{reich1}
 \Bel(V \inter (V_1 \union V_2)|U) = F(\Bel(V_1 \union V_2|V \inter
 U),\Bel(V|U)).
 \end{equation}
 Using the fact that $G$ is $+$, we immediately get
 \begin{equation}\label{reich2}
 \Bel(V \inter (V_1 \union V_2)|U)  =
 \Bel(V \inter V_1|U) + \Bel(V \inter V_2|U)
 \end{equation}
 and
 \begin{equation}\label{reich2.5}
 \begin{array}{l}
 F(\Bel(V_1 \union V_2|V \inter U),\Bel(V|U)) \\
 \ \ \ =
 F(\Bel(V_1|V \inter U) + \Bel(V_2|V \inter U), \Bel(V|U))
 \end{array}
 \end{equation}
 Moreover, by A2, we also have, for $i = 1,2$,
 \begin{equation}\label{reich3}
 \Bel(V \inter V_i|U) = F(\Bel(V \inter V_i|V \inter U),\Bel(V|U)).
 \end{equation}
 Putting together (\ref{reich1}), (\ref{reich2}), (\ref{reich2.5}),
 and (\ref{reich3}), we
 get that
 \begin{equation}\label{reich4}
 \begin{array}{ll}
 F(\Bel(V \inter V_1|V \inter U),\Bel(V|U)) \, +
 F(\Bel(V \inter V_2|V \inter U),\Bel(V|U))\\
 \ \ \ = F(\Bel(V \inter V_1|V \inter U) + \Bel(V \inter V_2|V \inter
 U),\Bel(V|U)).
 \end{array}
 \end{equation}

 Taking $x = \Bel(V \inter V_1|V \inter U)$, $y =
 \Bel(V \inter V_2|V \inter U)$, and $z = \Bel(V|U)$ in (\ref{reich4}),
 we get the functional equation
 \begin{equation}\label{reich5}
 F(x,z) + F(y,z) = F(x+y,z).
 \end{equation}

 Suppose that we assume (as Reichenbach implicitly does) that this
 functional equation holds
 for all $(x,y,z) \in P = \{(x,y,z) \in [0,1]^3: x+y \le 1\}$.
 The rest of the proof now
 follows easily. First, taking $x=0$ in (\ref{reich5}), it follows that
 $$F(0,z) + F(y,z) = F(y,z),$$
 from which we get that
 $$F(0,z) = 0.$$
 Next,
 fix $z$ and let $g_{z}(x) = F(x,z)$.  Since $F$ is, by assumption,
 differentiable, from (\ref{reich5}) we have that
 $$g'_z(x) = \lim_{y \rightarrow 0}(F(x+y,z)
 - F(x,z)/y) = \lim_{y \rightarrow 0} F(y,z)/y.$$
 It thus follows that $g'_z(x)$ is a constant, independent of $x$.
 Since the constant may depend on $z$, there is some function $h$
 such that $g'_z(x) = h(z)$.  Using the fact that $F(0,z) = 0$,
 elementary calculus tells us that
 $$g_z(x) = F(x,z) = h(z)x.$$
 Using the assumption that for all $U,V$, we have $\Bel(V|U) = 1$ if $U
 \subseteq V$, we get that
 $$\begin{array}{l}
 \Bel(V|U) = \Bel(V \inter V|U)
 = F(\Bel(V|V \inter U),\Bel(V|U)) =
 F(1,\Bel(V|U)).\end{array}$$
 Thus, we have that
 $$F(1,z) = h(z) = z.$$
 We conclude that $F(x,z) = xz$.

 Note, however, that this conclusion depends in a crucial way on the
 assumption that the functional equation (\ref{reich5}) holds for all
 $(x,y,z) \in P$.%
 \footnote{Actually, using the continuity of $F$, it suffices that
 the functional equation holds for a set of triples which is dense
 in $P$.}
 In fact, all that we can conclude
 from (\ref{reich4}) is that it holds for all $(x,y,z)$ such
 that there exist $U$, $V$, $V_1$, and $V_2$, with $V_1$ and $V_2$
 disjoint, such that
 $x = \Bel(V \inter V_1|V \inter U)$, $y =
 \Bel(V \inter V_2|V \inter U)$, and $z = \Bel(V|U)$.

 Let us say that a
 triple that satisfies this condition is
 %joe1
 %{\em acceptable}.
 {\em R-constrained} (since it must satisfy certain constraints
 imposed by the $F$ and $G$ functions; the $R$ here is for Reichenbach,
 to distinguish this notion from a similar one defined in the next
 section.)
 %Similarly, we say that a pair $(x,y)$ is constrained if there
 %exist sets $U$, $V$, and $V_1$ such that $x
 As I mentioned earlier, Acz\'el also assumes that
 $\Bel(V|U)$ takes on all values in $[e,E]$, where $e =
 \Bel(\emptyset|U)$ and $E = \Bel(U|U)$.  (In Reichenbach's formulation,
 $e=0$ and $E=1$.)  There are two ways to interpret this assumption.
 The weak interpretation is that for each $x \in [0,1]$, there exist $U,
 V$ such that $\Bel(V|U) = x$.  The strong interpretation is that for
 each $U$ and $x$, there exists $V$ such that $\Bel(V|U)
 = x$.  It is not clear which interpretation is intended by Acz\'el.
 Neither one obviously suffices to prove that every triple in $P$ is
 R-constrained,
 although it does seem plausible that it might follow from the second
 assumption.

 In any case, neither Acz\'el nor Reichenbach
 see a need to check that Equation~(\ref{reich5})
 holds throughout $P$.  (Nor does Cox for his analogous functional
 equation, nor do the authors of more recent and polished presentations
 of Cox's result, such as Jaynes \citeyear{Jaynes97} and Tribus
 \citeyear{Tribus69}.)
 However, it turns out to be
 quite necessary to do this.  Moreover, it is clear that if $W$ is
 finite, there are only finitely tuples in $P$ that are
 R-constrained,
 and it is not the case that all of $P$ is.  As we shall see in the next
 section, this observation has serious consequences as far as all these
 proofs are concerned.

 \section{The Counterexample to Cox's Theorem}\label{counterexample}
 %For our counterexample, we define a function $\Bel$ on events (that is,
 %on subsets of points in a finite space), not on propositions, since we
 %usually think of probability distributions as being functions on
 %events,
 %not propositions.  However, as is well known, the translation from
 %events to propositions and vice versa is trivial: We can
 %identify a proposition with the set of truth assignments that
 %satisfy it; conversely, we can identify a set with the proposition
 %saying ``one of the elements in the set is chosen''.  Under these
 %identifications, negation of propositions becomes complementation of
 %sets, and conjunction becomes intersection.
 The goal of this section is to prove
 \thm\label{cox}
 There is a function $\Belo$, a finite domain $W$, and functions $S$, $F$,
 and $G$ satisfying A1, A2, and A3 respectively such that
 \begin{itemize}
 \item $\Belo(V|U) \in [0,1]$ for $U \ne \emptyset$,
 \item $S(x) = 1-x$ (so that $S$ is strictly decreasing and infinitely
 differentiable),
 \item $G(x,y) = x + y$ (so that $G$ is strictly increasing in each
 argument and is infinitely differentiable),
 \item $F$ is infinitely differentiable, nondecreasing
  in each argument in
 $[0,1]^2$, and strictly increasing in each argument in
 $(0,1]^2$.  Moreover, $F$ is commutative, $F(x,0) = F(0,x) = 0$, and
 $F(x,1) = F(1,x) = x$.
 \end{itemize}
 However, there is no one-to-one onto
 function $g: [0,1] \rightarrow [0,1]$
 satisfying (\ref{eq7}).
 \ethm

 Note that the hypotheses on $\Belo$, $S$, $G$, and $F$ are at least as
 strong as those made in all the other variants of Cox's result, while
 the assumptions on $g$ are weaker than those made in the variants.
 For example, there is no requirement that $g$
 be continuous or increasing nor that $g \circ \Belo$ is a
 probability distribution (although Paris and Acz\'el both prove that,
 under their assumptions, $g$ can be taken to satisfy all these
 requirements).  This serves to make the counterexample quite strong.

 \bigskip

 The proof of Theorem~\ref{cox} is constructive.
 Consider a domain $W$ with 12 points: $w_1, ..., w_{12}$.  We associate
 with each point $w \in W$ a weight $f(w)$, as follows.
 %$$\begin{array}{llll}
 %f(w_1) = 3    &f(w_4) = 5 \times 10^4   &f(w_7) = 3 \times 10^8
 %&f(w_{10}) = 3 \times 10^{18}\\
 %f(w_2) = 2    &f(w_5) = 6 \times 10^4   &f(w_8) = 8 \times 10^8
 %&f(w_{11}) = 2 \times 10^{18}\\
 %f(w_3) = 6    &f(w_6) = 8 \times 10^4   &f(w_9) = 8 \times 10^8
 %&f(w_{12}) = 14 \times 10^{18}
 $$\begin{array}{ll}
 f(w_1) = 3    &f(w_4) = 5 \times 10^4\\
 f(w_2) = 2    &f(w_5) = 6 \times 10^4\\
 f(w_3) = 6    &f(w_6) = 8 \times 10^4\\ \\
 f(w_7) = 3 \times 10^8 &f(w_{10}) = 3 \times 10^{18}\\
 f(w_8) = 8 \times 10^8 &f(w_{11}) = 2 \times 10^{18}\\
 f(w_9) = 8 \times 10^8 &f(w_{12}) = 14 \times 10^{18}
 \end{array}
 $$
 For a subset $U$ of $W$, we define $f(U) = \sum_{w \in U} f(w)$.
 Thus, we can define a probability distribution $\Pr$ on $W$ by taking
 $\Pr(U) = f(U)/f(W)$.

 Let $f'$ be identical to $f$, except that $f'(w_{10}) = (3 - \delta)
 \times 10^{18}$ and $f'(w_{11}) = (2+\delta) \times 10^{18}$, where
 $\delta$ is defined below.  Again, we extend $f'$ to subsets of $W$ by
 defining $f'(U) = \sum_{w \in U} f'(w)$.  Let $W' =
 \{w_{10},w_{11},w_{12}\}$.   If $U \ne \emptyset$, define
 $$\Belo(V|U) =
 \left\{ \begin{array}{ll}
 f'(V \inter U)/f(U) &\mbox{if $W' \subseteq U$}\\
 f(V \inter U)/f(U) &\mbox{otherwise.}
 \end{array} \right.
 $$
 $\Belo$ is clearly very close to $\Pr$.  If $U \ne \emptyset$, then
 it is easy to see that
 $|\Belo(V|U) - \Pr(V|U)| = |f'(V \inter U) - f(V \inter U)|/f(U) \le
 \delta$.
 We choose $\delta > 0$ so that
 \begin{equation}\label{eq0}
 \mbox{if $\Pr(V|U) > \Pr(V'|U')$, then $\Belo(V|U) > \Belo(V'|U')$.}
 \end{equation}
 Since the range of $\Pr$ is finite, all sufficiently small $\delta$
 satisfy~(\ref{eq0}).

 The exact choice of weights above is not particularly important.  One
 thing that is important though  is the following collection of
 equalities:
 \begin{equation}\label{eq2}
 \begin{array}{l}
 \Pr(w_1|\{w_1,w_2\}) = \Pr(w_{10}|\{w_{10},w_{11}\}) = 3/5\\
 \Pr(\{w_1,w_2\}|\{w_1,w_2,w_3\}) = \Pr(w_4|\{w_4,w_5\}) = 5/11\\
 \Pr(\{w_4,w_5\}|\{w_4,w_5,w_6\}) =
 \Pr(\{w_7,w_8\}|\{w_7,w_8,w_9\}) = 11/19\\
 \Pr(w_4|\{w_4,w_5,w_6\}) =
 \Pr(\{w_{10},w_{11}\}|\{w_{10},w_{11},w_{12}\}) = 5/19\\
 \Pr(w_1|\{w_1,w_2,w_3\}) = \Pr(w_7|\{w_7,w_8\})  = 3/11.
 \end{array}
 \end{equation}
 It is easy to check that exactly the same equalities hold if we replace
 $\Pr$ by $\Belo$.

 We show that $\Belo$ satisfies the requirements of Theorem~\ref{cox} by
 a sequence of lemmas.  The first lemma is the key to showing that
 $\Belo$ cannot be isomorphic to a probability function.  It uses the
 fact (proved in Lemma~\ref{Cox5}) that if $\Belo$ were isomorphic to a
 probability function, then there would have to be a function $F$
 satisfying A2 that is associative.
 Although, as is shown in Lemma~\ref{Cox3},
 the function $F$ satisfying A2 can be taken
 to be infinitely differentiable and increasing in each argument, the
 equalities in (\ref{eq2}) suffice to guarantee that it
 cannot be taken to be associative, that is, we do not in general have
 $$F(x,F(y,z)) = F(F(x,y),z).$$
 Indeed, there is no associative function $F$ satisfying
 A2, even if we drop the requirements that $F$ be
 differentiable or increasing.

 \lem\label{Cox4} For $\Belo$ as defined above, there is no
 associative function $F$ satisfying A2.
 \elem
 \prf Suppose there were such a function $F$.  From (\ref{eq2}),
 we must have that
 $$\begin{array}{ll}
 &F(5/11,11/19)\\
 =&
 F(\Belod(w_4|\{w_4,w_5\}),\Belod(\{w_4,w_5\}|\{w_4,w_5,w_6\}))\\
 = &\Belod(w_4|\{w_4,w_5,w_6\}) = 5/19\end{array}$$
 and that
 $$\begin{array}{ll}
 &F(3/5,5/11)\\
 =&
 F(\Belod(w_1|\{w_1,w_2\}),\Belod(\{w_1,w_2\}|\{w_1,w_2,w_3\}))\\
 =& \Belod(w_1|\{w_1,w_2,w_3\}) = 3/11.\end{array}$$
 It follows that $$F(3/5,F(5/11,11/19)) = F(3/5,5/19)$$ and that
 $$F(F(3/5,5/11),11/19) = F(3/11,11/19).$$
 Thus, if $F$ were associative, we would have
 $$F(3/5,5/19) = F(3/11,11/19).$$
 On the other hand, from (\ref{eq2}) again, we see that
 $$\begin{array}{ll}
 &F(3/5,5/19)\\
 =&F(\Belod(w_{10}|\{w_{10},w_{11}\}),\Belod(\{w_{10},w_{11}\}|\{w_{10},w_{11},w_{12}
 \}))\\
 = &\Belod(w_{10}|\{w_{10},w_{11},w_{12}\}) = (3-\delta)/19,
 \end{array}$$
 while
 $$\begin{array}{ll}
 &F(3/11,11/19)\\
 =&F(\Belod(w_7|\{w_7,w_8\}),\Belod(\{w_7,w_8\}|\{w_7,w_8,w_9\}))\\
 = &\Belod(w_7|\{w_7,w_8,w_9\}) = 3/19.\end{array}$$
 It follows that $F$ cannot be associative. \eprf

 To understand how Lemma~\ref{Cox4} relates to our discussion in
 Section~\ref{reichsec} of the problems with Reichenbach's proof, we
 say $(x,y,z)$ is a {\em constrained triple \/} if there exist
 sets $U_1 \supseteq U_2 \supseteq U_3 \supseteq U_4$ with $U_3 \ne
 \emptyset$ such that $x =
 \Belo(U_4|U_3)$, $y = \Belo(U_3|U_2)$, and $z = \Belo(U_2|U_1)$.
 It is easy to see that A2 forces $F$ to be associative on constrained
 triples, since if $w = \Belo(U_3|U_1)$ and $w' = \Belo(U_4|U_2)$, by
 A2, we have
 $F(x,F(y,z)) = F(x,w) = \Belo(U_4|U_1)$ and $F(F(x,y),z) = F(w',z) =
 \Belo(U_4,U_1)$.
 A4 says that the set of constrained triples is dense in $[0,1]^3$.

 We similarly define $(x,y)$ to be a {\em constrained pair\/} if
 there exist sets $U_1
 \supseteq U_2 \supseteq U_3$ with $U_2 \ne \emptyset$
 such that $x = \Belo(U_3|U_2)$ and $y =
 \Belo(U_2|U_1)$.   We say that $(U_1,U_2,U_3)$ {\em corresponds\/} to
 the constrained pair $(x,y)$.  (Note that there may be more than one
 triple of sets
 corresponding to a constrained pair.)  If $(U_1,U_2,U_3)$ corresponds to 
 the constrained pair $(x,y)$ and $F$ satisfies A2, then we
 must have $F(x,y) = \Belo(U_3|U_1)$.   Note that both $(3/5,5/11)$ and
 $(5/11,11/19)$ are constrained pairs, although the triple
 $(3/5,5/11,11/19)$ is not constrained. It is this fact that we use in
 Lemma~\ref{Cox4}.

 The next lemma shows that $\Belo$ cannot be
 isomorphic to a probability function.
 %although $\Belo$ is very close to the probability function $\Pr$
 %(in the sense that $|\Belo(V|U) - \Pr(V|U)| \le \delta$).
 \lem\label{Cox5}
 For $\Belo$ as defined above,
 there is no one-to-one onto function $g: [0,1] \rightarrow [0,1]$
 satisfying~(\ref{eq7}).
 \elem

 \prf Suppose there were such a function $g$.  First note that
 $g(\Belo(U)) \ne 0$ if $U \ne \emptyset$.  For if $g(\Belo(U)) = 0$, then
 it follows from~(\ref{eq7}) that for all $V \subseteq U$, we have
 $$g(\Belo(V)) = g(\Belo(V|U)) \times g(\Belo(U)) = g(\Belo(V|U)) \times 0 =
 0.$$
 Thus, $g(\Belo(V)) = g(\Belo(U))$ for all subsets $V$ of $U$.  Since the
 definition of $\Belo$ guarantees that $\Belo(V) \ne \Belo(U)$ if $V$ is a
 strict subset of $U$, this contradicts the assumption that $g$ is
 one-to-one.  Thus, $g(\Belo(U)) \ne 0$ if $U \ne \emptyset$.
 It now follows from (\ref{eq7}) that if $U \ne \emptyset$,
 then
 \begin{equation}\label{eq8}
 g(\Belo(V|U)) = g(\Belo(V \inter U))/g(\Belo(U)).
 \end{equation}

 Now define $F(x,y) = g^{-1}(g(x) \times g(y))$.
 %joe
 We show that $F$ defined in this way satisfies A2 and is associative.
 This will give us a contradiction to Lemma~\ref{Cox4}.

 To see that $F$ satisfies A2, notice that, by
 applying the
 observation above repeatedly, if $V \inter U \ne \emptyset$, we get
 $$\begin{array}{ll}
 &F(\Belod(V'| V
 \inter U), \Belod(V|U))\\
 = &g^{-1}((g(\Belo(V'|V \inter U))
 \times g(\Belod(V|U))\\
 = &g^{-1}((g(\Belo(V' \inter V \inter U))/g(\Belo(V \inter U))) \times
 (g(\Belo(V \inter U))/g(\Belo(U))))\\
 = &g^{-1}(g(\Belo(V' \inter V \inter U))/  g(\Belo(U)))\\
 = &g^{-1}(g(\Belo(V' \inter V|U)))\\
 = &\Belo(V' \inter V|U).
 \end{array}$$
 Thus, $F$ satisfies A2.

 To see that $F$ is associative, note that
 $$\begin{array}{ll}
 F(F(x,y),z) &= g^{-1}(g(g^{-1}(g(x) \times g(y))) \times g(z))\\
 &= g^{-1}(g(x) \times g(y) \times g(z))\\
 &= g^{-1}(g(x) \times g(g^{-1}(g(y) \times g(z))))\\
 &= F(x,F(y,z)).
 \end{array}
 $$

 This gives us the desired contradiction to Lemma~\ref{Cox4}.
 It follows that
 $\Belo$ cannot be isomorphic to a probability function.  \eprf

 Despite the fact that $\Belo$ is not isomorphic to a probability
 function, functions $S$, $F$, and $G$ can be defined that satisfy A1,
 A2, and A3, respectively, and all the other requirements stated in
 Theorem~\ref{cox}.  The argument for $S$ and $G$ is easy; all the work
 goes into proving that an appropriate $F$ exists.

 \lem\label{Cox1}  There exists an infinitely differentiable, strictly
 decreasing
 function $S: [0,1] \rightarrow [0,1]$ such that $\Belod(\overline{V}|U) =
 S(\Belod(V|U))$ for all sets $U, V \subseteq W$ with $U \ne \emptyset$.
 In fact, we can take $S(x) = 1-x$.
 \elem
 \prf  This is immediate from the observation that $\Belod(\overline{V}|U) =
 1 - \Belod(V|U)$ for $U, V \subseteq W$. \eprf

 \lem\label{Cox2}  There exists an infinitely differentiable function
 $G: [0,1]^2 \rightarrow [0,1]$, increasing in each argument, such that
 if $U,V,V' \subseteq W$,
 $V \inter V' = \emptyset$, and $U \ne \emptyset$, then
 $\Belod(V \union V'|U)
 = G(\Belod(V|U),\Belod(V',U))$.  In fact,
 we can take $G(x,y) = x+y$.
 \elem
 \prf  This is immediate from the definition of $\Belo$. \eprf

 Thus, all that remains is to show that an appropriate $F$ exists.  The
 key step is provided by the following lemma, which essentially shows
 that there is a well defined $F$ that is increasing.

 \lem\label{keylemma}
 If $U_2 \inter U_1 \ne \emptyset$ and $V_2
 \inter V_1 \ne \emptyset$, then
 \begin{itemize}
 \item[(a)]
 if  $\Belod(V_3| V_2 \inter V_1) \le
 \Belod(U_3| U_2 \inter U_1)$  and
 $\Belod(V_2| V_1) \le
 \Belod(U_2| U_1)$,
 then  $\Belod(V_3 \inter V_2|V_1) \le \Belod(U_3 \inter U_2|U_1)$,
 \item[(b)]
 if  $\Belod(V_3| V_2 \inter V_1) <
 \Belod(U_3| U_2 \inter U_1)$,
 $\Belod(V_2| V_1) \le
 \Belod(U_2| U_1)$, $\Belo(U_3|U_2 \inter U_1) > 0$, and $\Belo(U_2|U_1) >
 0$, then  $\Belod(V_3 \inter V_2|V_1) < \Belod(U_3 \inter U_2|U_1)$,
 \item[(c)]
 if  $\Belod(V_3| V_2 \inter V_1) \le
 \Belod(U_3| U_2 \inter U_1)$,
 $\Belod(V_2| V_1) <
 \Belod(U_2| U_1)$, $\Belo(U_3|U_2 \inter U_1) > 0$, and $\Belo(U_2|U_1) >
 0$, then  $\Belod(V_3 \inter V_2|V_1) < \Belod(U_3 \inter U_2|U_1)$,
 \end{itemize}
 \elem

 \prf First observe that
 if  $\Belod(V_3| V_2 \inter V_1) \le
 \Belod(U_3| U_2 \inter U_1)$  and
 $\Belod(V_2| V_1) \le
 \Belod(U_2| U_1)$, then
 from (\ref{eq0}), it follows that
 $\Pr(V_3|V_2 \inter V_1) \le \Pr(U_3|U_2 \inter U_1)$ and
 $\Pr(V_2|V_1) \le \Pr(U_2|U_1)$.  If we have either
 $\Pr(V_3|V_2 \inter V_1) < \Pr(U_3|U_2 \inter U_1)$ or
 $\Pr(V_2|V_1) < \Pr(U_2|U_1)$, then we have
 either $\Pr(V_3 \inter V_2|V_1) < \Pr(U_3 \inter U_2|U_1)$ or
 $\Pr(U_3|U_2 \inter U_1) = 0$ or $\Pr(U_2|U_1) = 0$.
 It follows that either $\Belo(V_3 \inter V_2|V_1) < \Belo(U_3 \inter
 U_2|U_1)$ (this uses (\ref{eq0}) again) or that $\Belo(V_3 \inter V_2|V_1)
 = \Belo(U_3 \inter U_2|U_1) = 0$.
 In either case, the lemma holds.

 Thus, it remains to deal with the case that $\Pr(V_3|V_2 \inter V_1) =
 \Pr(U_3|U_2 \inter U_1)$ and $\Pr(V_2|V_1) = \Pr(U_2|U_1)$, and hence
 $\Pr(V_3 \inter V_2|V_1) = \Pr(U_3 \inter U_2|U_1)$.  The details of
 this analysis are left to the appendix.  \eprf

 \lem\label{Cox3}
 %There exists an infinitely differentiable function $F: [0,1]^2
 %\rightarrow
 %[0,1]$, strictly increasing in each argument in $(0,1]^2$, satisfying
 %A2. \elem
 There exists a function $F: [0,1]^2 \rightarrow [0,1]$ satisfying
 all the assumptions of Theorem~\ref{cox} (with respect to $\Belo$).
 \elem
 \prf
 Define a partial function $F'$ on $[0,1]^2$ whose domain $D$ consists of
 all constrained pairs.
 For a constrained pair, we define $F'$ in the unique way required to
 satisfy A2. 
 {\em A priori}, $F'$ may not be well defined; it is
 possible that there exist triples $(U_1,U_2,U_3)$ and $(V_1,V_2,V_3)$
 that both correspond to $(x,y)$ (i.e., $x = \Belo(U_3|U_2) =
 \Belo(V_3|V_2)$ and $y = \Belo(U_2|U_1) = \Belo(V_2|V_1)$) such that
 $\Belo(U_3|U_1) \ne
 \Belo(V_3| V_1)$.  If this were the case, then $F'(x,y)$ would
 not be well defined.  However, Lemma~\ref{keylemma} says that this cannot
 happen.  Moreover, Lemma~\ref{keylemma} assures us that $F'$ is increasing on $D$,
 and strictly increasing as long as one of its arguments is not 0.
 Indeed, if there is a triple $(U_1,U_2,U_3)$ corresponding to $(x,y)$
 such that $\{w_{10}, w_{11}, w_{12}\} \not\subseteq U_1$, then we must
 have $F'(x,y) = xy$.

 The domain $D$ of $F'$ is finite.
 Let $D'$ be the commutative closure
 of $D$, so that $D'$ consists of $D$ and all pairs $(y,x)$ such that
 $(x,y)$ is in $D$.  Extend $F'$ to a commutative function $F''$ on $D'$
 by defining $F''(y,x) = F'(x,y)$ if $(x,y) \in D$.
 $F''$ is well defined because, as can easily be verified, if $(x,y)$ and
 $(y,x)$ are both in
 $D$, one of $x$ or $y$ must be 1, and $F'(x,1) = F'(1,x) = x$.
 Clearly $F''$ is commutative.  It is also increasing.  For suppose
 $(x,y), (x',y') \in D'$, $x \le x'$, and $y \le y'$.  If both $(x,y)$
 and $(x',y')$ are in $D$, we must have $F''(x,y) \le F''(x',y')$, since
 $F'$ is increasing.  Similarly, if both $(y,x)$ and $(y',x')$ are in
 $D$, we must have $F''(x,y) = F'(y,x) \le F'(y',x') = F''(x',y')$.
 Finally, if $(x,y)$ and  $(y',x')$ are in $D$,
 a straightforward check over all possible elements in $D$
 shows that this can happen only if the
 triples $(U_1,U_2,U_3)$ and $(V_1,V_2,V_3)$ corresponding to $(x,y)$ and
 $(y',x')$ are such that $\{w_{10},w_{11},w_{12}\}$ is not a subset of
 either $U_1$ or $V_1$.  It follows that $F'(x,y) = xy$ and $F'(y',x') =
 x'y'$, so again we get that $F''$ is increasing.  A similar argument
 shows that $F''$ is strictly increasing as long as one of its arguments
 is not 0.

 It is straightforward to extend $F''$ to
 a  commutative, infinitely  differentiable, and increasing
 function $F$ defined on all
 of $[0,1]^2$, which is strictly increasing on $(0,1]^2$, and satisfies
 $F(x,1) = F(1,x) = x$ and $F(x,0) = F(0,x) = 0$.  We proceed as follows.
 We first extend $F''$ so that it is defined for all pairs $(x,y) \in
 [0,1]^2$ such that $x \ge y$ so that it has the required properties.
 If $x < y$, we then define so that $F(x,y) = F(y,x)$.  Since $F''$ is
 commutative, this definition agrees with $F''(x,y)$ for $x < y$.
 Clearly $F$ is commutative and infinitely differentiable.
 To see that $F$ is increasing, suppose that $x
 \le x'$ and $y \le y'$.  Just as in the case of $F''$, it is immediate
 that $F$ is increasing if both $x \ge y$ and $x' \ge y'$ or both $x < y$
 and $x' < y'$.  Otherwise, suppose $x \ge y$ and $y' \ge x'$.  Then
 we have $y \le x \le x' \le y'$.  Since $F$ is increasing on $\{(x,y): x
 \ge y \}$, we have $F(x,y) \le F(x',y) \le F(x',x') \le F(y',x') =
 F(x',y')$.  A similar argument shows that $F$ is strictly increasing
 unless one its arguments is 0.  Finally, $F$ clearly
 satisfies A2, since (by construction) $F'$ does, and A2 puts constraints
 only on the domain of $F'$.  \eprf

 Theorem~\ref{cox} now follows from Lemmas~\ref{Cox5}, \ref{Cox1},
 \ref{Cox2}, and \ref{Cox3}.


 \section{The Counterexample to Fine's Theorem}
 Fine is interested in what he calls {\em comparative conditional probability}.
 Thus, rather than associating a real number with each ``conditional
 object'' $V|U$, he puts an ordering $\succeq$ on such objects.
 As usual, $V|U \succ V'|U'$ is taken to be an abbreviation for
 $V|U \succeq V'|U'$ and not($V'|U' \succeq V|U$).

 Fine is interested in when such an ordering is induced by a
 real-valued belief function with reasonable properties.  He says that a
 real-valued function $P$
 on such objects {\em agrees with\/} $\succeq$ if $P(V|U) \ge P(V'|U')$
 iff $V|U \succeq V'|U'$.
 Fine then considers a number of axioms that $\succeq$ might satisfy.
 For our purposes, the most relevant are the ones Fine denotes QCC1,
 QCC2, QCC5, and QCC7.

 QCC1 just says that $\succeq$ is a linear order:
 \begin{description}
 \item[QCC1.] $V|U \succeq V'|U'$ or $V'|U' \succeq V|U$.
 \end{description}

 QCC2
 says that $\succeq$ is transitive:
 \begin{description}
 \item[QCC2.] If $V_1|U_1 \succeq V_2|U_2$ and $V_2|U_2 \succeq V_3|U_3$,
 then $V_1|U_1 \succeq V_3|U_3$.
 \end{description}

 QCC5 is a technical condition
 involving
 notions of order topology.  The relevant definitions are omitted
 here  (see \cite{Fine}
 for details), since QCC5, as Fine observes,
 holds vacuously in finite domains
 (the only ones of interest here).
 \begin{description}
 \item[QCC5.] The set $\{V|U\}$ has a countable basis in
 the order topology induced by $\succ$.
 \end{description}

 Finally, QCC7 essentially says that $\succeq$ is increasing, in the
 sense of Lemma~\ref{keylemma}.
 \begin{description}
 \item[QCC7.] \
 \begin{itemize}
 \item[(a)]
 If  $V_3| V_2 \inter V_1 \succeq
 U_3| U_2 \inter U_1$ and
 $V_2| V_1 \succeq
 U_2| U_1$
 then  $V_3 \inter V_2|V_1 \succeq U_3 \inter U_2|U_1$.
 \item[(b)]
 If  $V_3| V_2 \inter V_1 \succeq
 U_2| U_1$ and
 $V_2| V_1 \succeq
 U_3| U_2 \inter U_1$
 then  $V_3 \inter V_2|V_1 \succeq U_3 \inter U_2|U_1$.
 \item[(c)]
 If  $V_3| V_2 \inter V_1 \succ
 U_3| U_2 \inter U_1$,
 $V_2| V_1 \succeq
 U_2| U_1$, and $V_2|V_1 \succ \emptyset|W$,
 then  $V_3 \inter V_2|V_1 \succ U_3 \inter U_2|U_1$.
 \end{itemize}
 \end{description}

 Fine then claims the following theorem:

 \medskip

 \noindent {\bf Fine's Theorem:} \cite[Chapter II, Theorem 8]{Fine}
 {\em If $\succeq$ satisfies QCC1, QCC2, QCC5, then there exists some
 agreeing function $P$.  There exists a function $F$ of two variables
 such that
 \begin{enumerate}
 \item $P(V \inter V'|U) = F(P(V'|V \inter U),P(V|U))$,%
 \footnote{Fine
 assumes that $P(V \inter V'|U) = F(P(V|U),P(V'|V \inter U))$.
 I have reordered the arguments here for consistency with
 Cox's theorem.}
 \item $F(x,y) = F(y,x)$,
 \item $F(x,y)$ is increasing in $x$ for $y > P(\emptyset|W)$,
 \item $F(x,F(y,z)) = F(F(x,y),z)$,
 \item $F(P(W|U),y) = y$,
 \item $F(P(\emptyset|U),y) = P(\emptyset|U)$.
 \end{enumerate}
 iff $\succeq$ also satisfies QCC7.
 }

 \medskip

 The only relevant clauses for our purposes are
 Clause (1), which is  just A2, and
 Clause (4), which says that $F$ is associative.  As
 Lemma~\ref{Cox4} shows, there is no associative function satisfying A2
 for $\Belo$.  As I now show, this means that Fine's
 theorem does not quite hold either.

 Before doing so, let me briefly touch on
 a subtle issue regarding the domain
 of $\succeq$.  In the counterexample
 of the previous section,  $\Belo(V|U)$ is
 defined as long as $U \ne \emptyset$.
 Fine does not assume that the $\succeq$ relation is
 necessarily defined on all objects $V|U$ such that $U, V \subseteq W$
 and $U \ne \emptyset$.  He assumes that there is an algebra
 $\F$ of subsets of $W$ (that is, a set of subsets closed under finite
 intersections and complementation) and a subset $\F'$ of $\F$ closed
 under finite intersections and not containing the empty set such that
 $\succeq$ is defined on conditional objects $V|U$ such that $V \in \F$
 and $U \in \F'$.  Since $\F'$ is closed under intersection and does not
 contain the empty set, $\F'$ cannot contain disjoint sets.  If $W$ is
 finite, then the only way a collection $\F'$ can meet Fine's restriction
 is if there is some nonempty set $U_0$ such that all elements in $\F'$
 contain $U_0$.  This restriction is clearly too strong to the
 extent that comparative conditional probability is intended to generalize
 probability.  If $\Pr$ is a probability function, then it
 certainly makes sense to compare $\Pr(V|U)$ and $\Pr(V'|U')$ even
 if $U$ and $U'$ are disjoint sets.  Fine [private communication, 1995]
 suggested that it might be better to constrain QCC7 so that we do not
 condition on events $U$ that are equivalent to $\emptyset$
 (where $U$ is equivalent to $\emptyset$ if $\emptyset \succeq U$
 and $U \succeq \emptyset$).  Since the only event equivalent to
 $\emptyset$ in the counterexample of the previous section is
 $\emptyset$ itself, this means that the counterexample can
 be used without change.  This is what is done in the proof below.
 I show below how to modify
 the counterexample so that it satisfies Fine's original restrictions.

 \thm  There exists an ordering $\succeq$ satisfying QCC1, QCC2, QCC5,
 and QCC7, such that for every function $P$ agreeing with $\succeq$,
 there is no associative function $F$ of two variables such that
 $P(V \inter V')|U) = F(P(V'|V \inter U),P(V|U))$.  \ethm

 \prf Let $W$ and $\Belo$ be as in the
 counterexample in the previous section.  Define $\succeq$ so that $\Belo$
 agrees with $\succeq$.  Thus, $V|U \succeq V'|U'$ iff $\Belo(V|U) \ge
 \Belo(V'|U')$.  Clearly $\succeq$ satisfies QCC1 and QCC2.  As was
 mentioned earlier, since $W$ is finite, $\succeq$ vacuously satisfies
 QCC5.  Lemma~\ref{keylemma} shows that $\succeq$ satisfies parts (a) and
 (c) of QCC7.
 To show that $\succeq$ also satisfies part (b) of QCC7, we must
 prove that if $\Belo(V_3|V_2 \inter V_1) \ge \Belo(U_2|U_1)$
 and $\Belo(V_2|V_1) \ge \Belo(U_3|U_2 \inter U_1)$, then
 $\Belo(V_3 \inter V_2|V_1) \ge \Belo(U_3 \inter U_2|U_1)$.
 The proof of this is almost identical to that of Lemma~\ref{keylemma};
 we simply exchange the roles of $\Pr(V_2|V_1)$ and $\Pr(V_3|V_2 \inter
 V_1)$ in that proof.  I leave the details to the reader.
 Lemma~\ref{Cox4} shows that there is no associative function
 $F$ satisfying
 A2 for $\Belo$.  All that was used in the proof was the fact that
 $\Belo$ satisfied the inequalities of (\ref{eq2}).  But these
 equalities must hold for any function agreeing with $\succeq$.
 Thus, exactly the
 same proof shows that if $P$ is any function agreeing with
 $\succeq$, then there is no associative function
 $F$ satisfying $P(V \inter V'|U) = F(P(V'|V \inter U),P(V|U))$.  \eprf


 I conclude this section by briefly sketching
 how the counterexample can be modified
 so that it satisfies Fine's
 original restriction.  Redefine $W$ by adding one more
 element $w_0$.  Redefine $f$ and $f'$ so that $f(w_0) = f'(w_0) =
 10^{-5}$; in addition, redefine $f$ and $f'$ on $w_3$, $w_6$, $w_9$,
 and $w_{12}$, so as
 to decrease their weight by $10^{-5}$, the weight of $w_0$.  Thus,
 \begin{itemize}
 \item $f(w_3) = f'(w_3) = 6 - 10^{-5}$,
 \item $f(w_6) = f'(w_6) = 8 \times 10^4 - 10^{-5}$,
 \item $f(w_9) = f'(w_9) = 8 \times 10^8 - 10^{-5}$, and
 \item $f(w_{12}) = f'(w_{12}) = 14 \times 10^{18} - 10^{-5}$.
 \end{itemize}
 Finally, redefine $W'$ to be $\{w_0,w_{10},w_{11},w_{12}\}$.
 The definition of $\Belo$ in terms of $f$, $f'$, and $W'$ remains the
 same.
 With these redefinitions, the proofs of the previous section go through
 essentially unchanged.  In particular, the equalities in (\ref{eq2})
 now hold if we add $w_0$ to every set.
 Let $\F'$ consist of all subsets of $W$
 containing $w_0$.  Notice  that $\F'$ is closed under intersection and
 does not contain the empty set.
 The lack of associativity
 in Lemma~\ref{Cox4} can now be
  demonstrated by conditioning on sets in $\F'$.
 As a consequence, we get a counterexample to Fine's theorem even when
 restricting to conditional objects that satisfy his restriction.

 \section{Discussion}\label{discussion}
 Let me summarize the status of various results in the light of the
 counterexample of this paper:
 \begin{itemize}
 \item Cox's theorem as originally stated does not hold in finite domains.
 Moreover, even in infinite domains, the counterexample and the discussion
 in Section~\ref{reichsec} suggest that more assumptions are
 required for its correctness.  In particular,
 the claim in his proof that $F$ is associative does not follow.
 \item Although the counterexample given here is not a counterexample to
 Acz\'el's theorem, his assumptions do not seem strong enough to
 guarantee that the function $G$ is associative, as he claims it is.
 \item The variants of Cox's theorem stated by Heckerman \citeyear{Heck88},
 Horvitz, Heckerman, and Langlotz \citeyear{HHL}, and Aleliunas
 \citeyear{Aleliunas} all succumb to the counterexample.
 %No proof is
 %provided for these theorems, but, presumably, any attempt to prove them
 %would invoke associativity at some point.
 \item The claim that the function $F$ must be associative in
 Fine's theorem is incorrect.  Fine has an analogous result
 \cite[Chapter II, Theorem 4]{Fine} for unconditional comparative
 probability involving a function $G$ as in Acz\'el's theorem.
 This function too is claimed to be associative, and again, this
 does not seem to follow (although my counterexample  does not
 apply to that theorem).
 \end{itemize}

 Of course, the interesting question now is what it would take
 to recover Cox's theorem.  Paris's assumption A4
 suffices, as does the stronger assumption of nonatomicity (see Footnote
 4).  As we have observed, A4 forces the domain of $\Bel$
 to be infinite, as does the assumption that the range of $\Bel$ is all
 of $[0,1]$.  We can always extend a domain to an infinite---%
 indeed, uncountable---domain
 by assuming that we have an infinite collection
 of independent fair coins, and that we can talk about outcomes of
 coin tosses as well as the original events in the domain.
 (This type of ``extendibility'' assumption is fairly standard;
 for example, it is made by Savage \citeyear{Savage} in quite a different
 context.)  In such an extended
 domain, it seems reasonable to also assume that
 $\Bel$
 varies uniformly between 0 (certain falsehood) and 1 (certain truth).
 If we also assume A4 (or something like it), we can then recover
 Cox's theorem.
 Notice, however, that this viewpoint disallows a notion of belief
 that takes on only finitely many gradations.

 Another possibility is to observe that we are not interested in
 just one domain in isolation.  Rather, what
 we are interested in is a notion of belief $\Bel$ that applies
 uniformly to all domains.  Thus, even if $(U,V)$ and $(U',V')$ are pairs
 of subsets of different (perhaps even disjoint) domains, if $\Bel(V|U)$
 and $\Bel(V'|U')$ are both $1/2$, then
 we would expect this to denote the same relative strength of belief.
 In this setting, an analogue of A4 seems more reasonable.  That
 is, we can assume that for
 all $0 \le \alpha, \beta, \gamma \le 1$ and $\epsilon > 0$, there is
 some domain $W$ and  subsets $U_1$, $U_2$, $U_3$, and $U_4$ of $W$ such
 that the conclusion of A4 holds.
 If we further assume that the functions $F$, $G$, and $S$ are
 also uniform across domains (that is, that A1, A2, and A3 hold for the
 same choice of $F$, $G$, and $S$ in every domain),
 then we can again recover Cox's theorem.%
 \footnote{This point was independently observed by Jeff Paris [private
 communication, 1996].}

 The idea of having a notion of uncertainty that applies uniformly in
 all domains seems implicit in some discussion in
 that Jaynes' recent book on probability theory
 \citeyear{Jaynes97}.  Jaynes focuses almost exclusively on finite
 domains.%
 \footnote{Actually, Jaynes assigns probability to propositions, not sets,
 but, as noted earlier, there is essentially no difference between the
 two.}
 As he says ``In principle, every problem must start with such finite set
 probabilities; extensions to infinite sets is permitted only when this
 is the result of a well-defined and well-behaved limiting process from a
 finite set.'' To make sense of this limiting process, it seems that
 Jaynes must be assuming that the same notion of uncertainty applies in
 all domains.  Moreover, one can make arguments appealing to continuity
 that when we consider such limiting processes, we can always find subsets
 $U_1$, $U_2$, $U_3$, and $U_4$ in some sufficiently rich (but
 finite) extension of the original domain such that A4 holds.

 While this seems like perhaps the most reasonable additional
 assumptions required to get Cox's result, it does require us to
 consider many domains at once.   Moreover, it
 does not allow a notion of belief that has only finitely many
 gradations, let alone a notion of belief that allows some events to be
 considered incomparable in likelihood.%
 \footnote{Interestingly, Jaynes \citeyear[Appendix A]{Jaynes97}
 admits that having plausibility values
 be elements of a partially-ordered lattice may be a reasonable
 alternative to traditional probability theory.  Nir Friedman and I 
 \citeyear{FrH7,FrH5,FrH1Full} have
 recently developed such a theory and shown that it provides a useful
 basis for thinking about default reasoning and belief revision.}

 Suppose we really are interested in one particular finite domain,
 and we do not want to extend it or consider all other possible domains.
 What assumptions do we then need to get Cox's theorem?
 The counterexample given here could be
 circumvented by requiring that  $F$ be associative
 on all tuples (rather than
 just on the constrained triples).
 However, if we really are interested
 in a single domain, the motivation for making requirements on the
 behavior of $F$ on belief values that do not arise is not so clear.
 Moreover, it is far from clear that assuming that $F$ is associative
 suffices to prove the theorem.  For example,
 Cox's proof  makes use
 of various functional equations involving $F$ and $S$, analogous
 to the equation (\ref{reich5}) that appears in Section~\ref{reichsec}.
 These functional equations are easily seen to hold
 for certain tuples.  However, as we saw in Section~\ref{reichsec},
 the proof really requires that they hold for {\em all\/} tuples.
 Just assuming that $F$ is associative does not appear to suffice to
 guarantee that the functional equations involving $S$
 hold for all tuples.  Further assumptions appear necessary.

 Nir Friedman [private communication] has conjectured that the following
 condition, which says that essentially
 all beliefs are distinct, suffices:
 \begin{itemize}
 \item
 if $\emptyset \subset U \subset V$,
 $\emptyset \subset U' \subset V'$, and $(U,V) \ne (U',V')$, then
 $\Bel(U|V) \ne \Bel(U'|V')$.
 \end{itemize}
 Even if this condition suffices, note that it precludes, for example,
 a uniform probability distribution, and thus again seems unduly
 restrictive.

 Another possibly interesting line of research is that of characterizing
 the functions that satisfy Cox's assumptions.   As the example given here
 shows, the class of such functions includes functions that are not
 isomorphic to any probability function.  I conjecture that in fact it
 includes only functions that are in some sense ``close'' to a function
 isomorphic to a probability distribution, although it is not clear
 exactly how ``close'' should be defined (nor how interesting this class
 really is in practice).

 So what does all this say regarding the use of probability?  Not much.
 Although I have tried to argue here that Cox's justification of
 probability is not quite as strong as previously believed,
 and the assumptions underlying the variants of it need clarification,
 I am not trying to suggest that probability should be abandoned.
 There are many other justifications for its use.

 \section*{Acknowledgments}
 I'd like to thank Janos Acz\'el, Peter Cheeseman,
 Terry Fine, Ron Fagin, Nir Friedman,
 David Heckerman, Eric Horvitz, Christopher Meek, Jeff Paris, and the
 anonymous referees for useful comments on the paper.
 I'd also like to thank Judea Pearl for pointing out Reichenbach's
 work to me and Janos Acz\'el for pointing out Falmagne's paper.
 This work was largely carried out while I was at the IBM
 Almaden Research Center.  IBM's support is gratefully acknowledged.  The
 work was also supported in part by the NSF, under grants IRI-95-03109
 and IRI-96-25901, and the Air Force Office of Scientific Research
 (AFSC), under grant F94620-96-1-0323.   A preliminary version of this
 paper appears in {\em Proc. National Conference on Artificial
 Intelligence (AAAI '96), pp.~1313--1319}.


 \appendix
 \section{Proof of Lemma~\protect{\ref{keylemma}}}

 Recall that all that remains in the proof of Lemma~\ref{keylemma} is to
 deal with the case that $\Pr(V_3|V_2
 \inter V_1) =
 \Pr(U_3|U_2 \inter U_1)$ and $\Pr(V_2|V_1) = \Pr(U_2|U_1)$, and hence
 $\Pr(V_3 \inter V_2|V_1) = \Pr(U_3 \inter U_2|U_1)$.

 %First suppose that
 %\begin{equation}\label{eq5}
 %f(U_1) = f(V_1),\ f(U_1 \inter U_2) = f(V_1 \inter V_2),\ f(U_1
 %\inter U_2 \inter U_3) = f(V_1 \inter V_2 \inter V_3)
 %\end{equation}
 %It is easy to see that if (\ref{eq5}) holds, then all these expressions
 %remain equal if we replace $f$ by $f'$, and thus we must have
 %$\Belod(V_3 \inter V_2|V_1) \le \Belod(U_3 \inter U_2|U_1)$.
 %Thus, we can assume that~(\ref{eq5}) does not hold.
 %The details of this analysis are left to the full paper.
 %cut for UAI

 Before proceeding with the proof, it is useful
 to collect some general facts about $\Pr$.
 A set $U$ is said to be {\em standard\/} if $U$ is a subset of one
 of $\{w_1,w_2,w_3\}$, $\{w_4,w_5,w_6\}$, $\{w_7,w_8,w_9\}$, or
 $\{w_{10},w_{11},w_{12}\}$.
 A real number $a$ is said to be {\em relevant\/} if
 there exists some standard $U$ and some arbitrary $V$ such that
 $a = \Pr(V|U)$.
 %An exhaustive check shows that the only relevant numbers are
 %$0$, $1$, $1/2$, $1/3$, $2/3$,
 %$1/4$, $3/4$, $2/5$, $3/5$, $3/7$, $4/7$, $1/8$, $7/8$, $2/11$, $3/11$,
 %$5/11$, $6/11$, $8/11$,
 %$9/11$, $5/13$, $8/13$, $3/17$, $14/17$, $2/19$, $3/19$, $5/19$, $6/19$,
 %$8/19$, $11/19$, $13/19$, $14/19$, $16/19$, $17/19$.
 Notice that even if $U \ne \emptyset$ is nonstandard, then, taking $U'$
 to be the standard subset of $U$ which has the greatest weight,
 then $|\Pr(V|U) - \Pr(V|U')| < .002$.  (This is the reason that
 the weights are multiplied by factors such as $10^4$, $10^8$, and
 $10^{18}$.)  Thus, for any subsets $V$ and $U$ of $W$, we have that
 $\Pr(V|U)$ is close to a relevant number (where ``close'' means ``within
 .002'').

 Call a triple
 $(U, V, V')$ of subsets of $W$ {\em good\/} if
 $\Belod(V' \inter V|U) = \Belod(V'|V \inter U) \times \Belod(V|U)$.
 Clearly if both $(U_1,U_2,U_3)$ and $(V_1,V_2,V_3)$ are good, then
 the lemma holds.
 Notice that
 if $(U,V,V')$ is not good, then $U \supseteq \{w_{10},w_{11},w_{12}\}$
 and $f(V \inter \{w_{10},w_{11},w_{12}\}) \ne f'(V \inter
 \{w_{10},w_{11},w_{11}\})$, which means that $V \inter
 \{w_{10},w_{11},w_{12}\}$ must contain one of $w_{10}$ and $w_{11}$,
 but not both, and thus must be one of $\{w_{10}\}$, $\{w_{11}\}$,
 $\{w_{10},w_{12}\}$, or $\{w_{11},w_{12}\}$.

 Thus, we may as well assume that at least one of $(U_1,U_2,U_3)$ or
 $(V_1,V_2,V_3)$ is not good.
 In that case, I claim that one of the following must hold:
 \begin{itemize}
 \item
 $\Belo(V_3
 \inter V_2|V_1) = Bel(V_3|V_2 \inter V_1) = \Belo(U_3|U_2 \inter U_1)
 = \Belo(U_3 \inter U_2|U_1) = 0$
 \item $U_3 \inter U_2 \inter U_1 = U_2 \inter U_1$ and
 $V_3 \inter V_2 \inter V_1 = V_2 \inter V_1$
 \item $f(U_1) = f(V_1)$ and $f(U_1 \inter U_2) = f(V_1 \inter V_2)$
 \end{itemize}
 In the first case, we have already seen that the lemma holds.  In the
 second case,
 we have $\Belo(V_3 \inter V_2|V_1) = \Belo(V_2|V_1)$,
 $\Belo(U_3 \inter U_2|U_1) = \Belo(U_2|U_1)$, and $\Belo(V_3|V_2 \inter
 V_1) = \Belo(U_3|U_2 \inter U_1) = 1$, so the lemma is easily seen to
 hold.  Finally, in the third case, notice that since
 $\Pr(U_2 \inter U_3|U_1) = \Pr(V_2 \inter V_3|V_1)$, we must also have
 that $f(U_1 \inter U_2 \inter U_3) = f(V_1 \inter V_2 \inter V_3)$.
 Moreover, it is easy to see that all these equalities must hold if $f$
 is replaced by $f'$.  Again, the lemma immediately follows.

 To prove the claim,
 for definiteness, assume that $(U_1,
 U_2, U_3)$ is not good (an identical argument works if
 $(V_1,V_2,V_3)$ is not good).  From the characterization above of
 triples that are not good, it follows that
 $f(U_1 \inter U_2) = a \times 10^{18} + b$ and
 $f(U_1) = 19 \times 10^{18} + c$,
 where $a \in \{2,3,16,17\}$
 (depending on $U_2 \inter \{w_{10},w_{11},w_{12}\}$), and
 both $b, c < 20 \times 10^8$.  Clearly, the relevant number
 closest to $\Pr(U_2|U_1)$ is $a/19$.  Since $\Pr(V_2|V_1) =
 \Pr(U_2|U_1)$ by assumption, $\Pr(V_2|V_1)$ is also
 close to $a/19$.  Thus, we must have that $f(V_1 \inter V_2) =
 a \times 10^{k} + b'$ and $f(V_1) = 19 \times 10^{k} + c'$, where
 $k \in \{0,4,8,18\}$.  In fact, it is easy to see that $k$ is either
 8 or 18, since there are no relevant numbers of the form $a/19$
 (for $a \in \{2,3,16,17\}$) that are close to $\Pr(V|U)$ if
 $U \subseteq \{w_1,w_2,w_3,w_4,w_5,w_6\}$.
 In addition, if $k=18$, then $b',c' < 20 \times 10^8$, while if
 $k = 8$, then $b',c' < 20 \times 10^4$.
 By standard arithmetic manipulation, we have that
 $$10^{18}(ac' - 19b') + 10^k(19b - ac) + (bc' - b'c) = 0.$$
 If $k = 8$, then it is easy to see that we must have
 \begin{equation}\label{eq6}
 \mbox{$ac' - 19b' = 0$, $19b - ac = 0$ and $bc' - b'c = 0$,}
 \end{equation}
 while if
 $k = 18$, then we must have
 \begin{equation}\label{eq3}
 \mbox{$19(b - b') + a(c' - c) = 0$ and
 $bc' - b'c = 0$.}
 \end{equation}

 Now comes a case analysis.  First suppose that $k = 8$.
 %In that case,
 %a straightforward check shows that we must have $k = 8$ and
 %either $a = 3$ or $a = 16$; no other choices are possible.  Moreover, we
 Then we must
 have $b' = c' = 0$, since if $c' \ne 0$, then from (\ref{eq6}) we have
 that $b'/c' = a/19$,
 and it is easy to see that there do not exist sets $T_1$ and $T_2$ such
 that $f(T_1) = b'$, $f(T_2) = c'$, and $b'/c' = a/19$, with $b', c' \le
 20 \times 10^4$.  Thus, it follows that $\Pr(U_2|U_1) = \Pr(V_2|V_1) =
 a/19$.  Moreover, we must have $V_1 = \{w_7,w_8,w_9\}$ and $V_2 \inter
 V_1$ either $\{w_7\}$ or $\{w_8,w_9\}$, depending on $a$.  It follows
 that
 $\Pr(V_3| V_2 \inter V_1)$ must be one of $\{0,1/2,1\}$.  Since
 $\Pr(U_3|U_2 \inter U_1) = \Pr(V_3| V_2 \inter V_1)$, we must have that
 $\Pr(U_3|U_2 \inter U_1) \in \{0,1/2,1\}$.  Since $U_2 \inter U_1$
 contains exactly one of $w_{10}$ and $w_{11}$, it is easy to see that
 $\Pr(U_3|U_2 \inter U_1)$ cannot be $1/2$.  If $\Pr(U_3|U_2 \inter U_1)
 = \Pr(V_3|V_2 \inter V_1) = 0$, then $U_3 \inter U_2 \inter U_1 = V_3
 \inter V_2 \inter V_1 = \emptyset$, and we must have $\Belo(U_3 \inter
 U_2 | U_1) = \Belo(V_3 \inter V_2|V_1) = 0$, so the claim follows.
 On the other hand,
 if $\Pr(U_3|U_2 \inter U_1) = \Pr(V_3|V_2 \inter V_1) = 1$, then
 $U_3 \inter U_2 \inter U_1 = U_2 \inter U_1$ and $V_3 \inter V_2 \inter
 V_1 = V_2 \inter V_1$, and the claim again follows.

 Now suppose $k = 18$.
 If $c = c'$, then by~(\ref{eq3}), we must have that $b = b'$.
 It immediately follows that
 $f(U_1) = f(V_1)$ and $f(U_1 \inter U_2) = f(V_1 \inter V_2)$,
 so the claim holds.  Thus, we can suppose $c \ne c'$.  Suppose that
 $c \ne 0$ (an identical argument works if $c \ne 0$).  Then
 there exists some $x \ne 1$ such that $c = xc'$.  Since $bc' - b'c
 = 0$, it follows that $b = xb'$.  Substituting $xb'$ for $b$ and $xc'$
 for $c$ in (\ref{eq3}), we get that  $(1-x)b'/(1-x)c' = a/19$, from
 which it follows that $b'/c' = a/19$.
 Moreover, we also get that either $b = c =
 0$ or $b/c = a/19$.  It is easy to check that
 $a$ must be  either 3 or 16.
 If $b/c = a/19$, then we must have $b = b'$ and
 $c = c'$.  As we have seen, this suffices to prove the claim.  Thus, we
 can assume that $b = c = 0$.  But this means that $U_1 =
 \{w_{10},w_{11},w_{12}\}$, and that $U_1 \inter
 U_2$ is either $\{w_{10}\}$ or 

\bibliographystyle{theapa}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Acz\'el}{Acz\'el}{1966}]{Aczel}
Acz\'el, J. \BBOP1966\BBCP.
\newblock {\Bem Lectures on Functional Equations and Their Applications}.
\newblock Academic Press, New York.

\bibitem[\protect\BCAY{Acz\'el \BBA\ Daroczy}{Acz\'el \BBA\
  Daroczy}{1975}]{AczelDaroczy}
Acz\'el, J.\BBACOMMA\  \BBA\ Daroczy, Z. \BBOP1975\BBCP.
\newblock {\Bem On Measures of Information and Their Characterizations}.
\newblock Academic Press, New York.

\bibitem[\protect\BCAY{Aleliunas}{Aleliunas}{1988}]{Aleliunas}
Aleliunas, R. \BBOP1988\BBCP.
\newblock \BBOQ A summary of a new normative theory of probabilistic
  logic\BBCQ\
\newblock In {\Bem Proceedings of the Fourth Workshop on Uncertainty in
  Artificial Intelligence, {\rm Minneapolis, MN}}, \BPGS\ 8--14.
\newblock Also in R. Shachter, T. Levitt, L. Kanal, and J. Lemmer, editors,
  {\em Uncertainty in Artificial Intelligence 4,} pages 199--206.
  North-Holland, New York, 1990.

\bibitem[\protect\BCAY{Cheeseman}{Cheeseman}{1988}]{Cheeseman88}
Cheeseman, P. \BBOP1988\BBCP.
\newblock \BBOQ An inquiry into computer understanding\BBCQ\
\newblock {\Bem Computational Intelligence}, {\Bem 4\/}(1), 58--66.

\bibitem[\protect\BCAY{Cox}{Cox}{1946}]{Cox}
Cox, R. \BBOP1946\BBCP.
\newblock \BBOQ Probability, frequency, and reasonable expectation\BBCQ\
\newblock {\Bem American Journal of Physics}, {\Bem 14\/}(1), 1--13.

\bibitem[\protect\BCAY{Dubois \BBA\ Prade}{Dubois \BBA\ Prade}{1990}]{DP90}
Dubois, D.\BBACOMMA\  \BBA\ Prade, H. \BBOP1990\BBCP.
\newblock \BBOQ The logical view of conditioning and its application to
  possibility and evidence theories\BBCQ\
\newblock {\Bem International Journal of Approximate Reasoning}, {\Bem 4\/}(1),
  23--46.

\bibitem[\protect\BCAY{Falmagne}{Falmagne}{1981}]{Falmagne81}
Falmagne, J.~C. \BBOP1981\BBCP.
\newblock \BBOQ On a recurrent misuse of a classical functional equation
  result\BBCQ\
\newblock {\Bem Journal of Mathematical Psychology}, {\Bem 23\/}(2), 190--193.

\bibitem[\protect\BCAY{Fine}{Fine}{1973}]{Fine}
Fine, T.~L. \BBOP1973\BBCP.
\newblock {\Bem Theories of Probability}.
\newblock Academic Press, New York.

\bibitem[\protect\BCAY{Friedman \BBA\ Halpern}{Friedman \BBA\
  Halpern}{1995}]{FrH7}
Friedman, N.\BBACOMMA\  \BBA\ Halpern, J.~Y. \BBOP1995\BBCP.
\newblock \BBOQ Plausibility measures: a user's manual\BBCQ\
\newblock In {\Bem Proc.~Eleventh Conference on Uncertainty in Artificial
  Intelligence (UAI '95)}, \BPGS\ 175--184.

\bibitem[\protect\BCAY{Friedman \BBA\ Halpern}{Friedman \BBA\
  Halpern}{1996}]{FrH5}
Friedman, N.\BBACOMMA\  \BBA\ Halpern, J.~Y. \BBOP1996\BBCP.
\newblock \BBOQ Plausibility measures and default reasoning\BBCQ\
\newblock In {\Bem Proceedings, Thirteenth National Conference on Artificial
  Intelligence (AAAI '96)}, \BPGS\ 1297--1304.

\bibitem[\protect\BCAY{Friedman \BBA\ Halpern}{Friedman \BBA\
  Halpern}{1997}]{FrH1Full}
Friedman, N.\BBACOMMA\  \BBA\ Halpern, J.~Y. \BBOP1997\BBCP.
\newblock \BBOQ Modeling belief in dynamic systems. part {I}:
  {foundations}\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 95\/}(2), 257--316.

\bibitem[\protect\BCAY{Heckerman}{Heckerman}{1988}]{Heck88}
Heckerman, D. \BBOP1988\BBCP.
\newblock \BBOQ An axiomatic framework for belief updates\BBCQ\
\newblock In Lemmer, J.~F.\BBACOMMA\  \BBA\ Kanal, L.~N.\BEDS, {\Bem
  Uncertainty in Artificial Intelligence 2}, \BPGS\ 11--22. North-Holland,
  Amsterdam.

\bibitem[\protect\BCAY{Horvitz, Heckerman, \BBA\ Langlotz}{Horvitz
  et~al.}{1986}]{HHL}
Horvitz, E.~J., Heckerman, D., \BBA\ Langlotz, C.~P. \BBOP1986\BBCP.
\newblock \BBOQ A framework for comparing alternative formalisms for plausible
  reasoning\BBCQ\
\newblock In {\Bem Proceedings, Fifth National Conference on Artificial
  Intelligence (AAAI '86)}, \BPGS\ 210--214.

\bibitem[\protect\BCAY{Jaynes}{Jaynes}{1978}]{Jaynes}
Jaynes, E.~T. \BBOP1978\BBCP.
\newblock \BBOQ Where do we stand on maximum entropy?\BBCQ\
\newblock In Levine, R.~D.\BBACOMMA\  \BBA\ Tribus, M.\BEDS, {\Bem The Maximum
  Entropy Formalism}, \BPGS\ 15--118. MIT Press, Cambridge, Mass.

\bibitem[\protect\BCAY{Jaynes}{Jaynes}{1996}]{Jaynes97}
Jaynes, E.~T. \BBOP1996\BBCP.
\newblock {\Bem Probability Theory---The Logic of Science}.
\newblock Unpublished; available at http://bayes.wustl.edu.

\bibitem[\protect\BCAY{Paris}{Paris}{1994}]{Paris94}
Paris, J.~B. \BBOP1994\BBCP.
\newblock {\Bem The Uncertain Reasoner's Companion}.
\newblock Cambridge University Press, Cambridge, U.K.

\bibitem[\protect\BCAY{Reichenbach}{Reichenbach}{1949}]{Reichenbach:Theory.Of.%
Probability}
Reichenbach, H. \BBOP1949\BBCP.
\newblock {\Bem The Theory of Probability}.
\newblock University of California Press, Berkeley.
\newblock This is a translation and revision of the German edition, published
  as {\em Wahrscheinlichkeitslehre}, in 1935.

\bibitem[\protect\BCAY{Savage}{Savage}{1954}]{Savage}
Savage, L.~J. \BBOP1954\BBCP.
\newblock {\Bem Foundations of Statistics}.
\newblock John Wiley \& Sons, New York.

\bibitem[\protect\BCAY{Tribus}{Tribus}{1969}]{Tribus69}
Tribus, M. \BBOP1969\BBCP.
\newblock {\Bem Rational Descriptions, Decisions, and Designs}.
\newblock Pergammon Press, New York.

\end{thebibliography}
$\{w_{11},w_{12}\}$.
 It follows that the only possibilities for $\Pr(U_3|U_2 \inter U_1)$
 are $0$, $1/8$, $7/8$, or $1$.  It is easy to see that $\Pr(V_3|V_2
 \inter V_1)$ cannot be $1/8$ or $7/8$, while the cases where it is
 either 0 or 1 are easily taken care of, as above.

 This completes the proof of the claim and of the lemma.
 \eprf

 %\bibliographystyle{chicago}
 %\bibliography{z,refs,bghk,joe}

\end{document}


