Cox's Theorem Revisited

Joseph Y. HalpernarXiv 1999 · arXiv

Introduction

Cox’s Theorem has long been regarded as the "holy grail" of Bayesian epistemology. It purports to provide a rigorous mathematical proof that any system of "common sense" reasoning about uncertainty must, by necessity, be equivalent to standard probability theory. For decades, this has served as a foundational pillar for the use of Bayesian methods in artificial intelligence and statistics. However, in this technical reassessment, Joseph Halpern demonstrates that the theorem is far more fragile than commonly believed. Halpern reveals that the transition from intuitive axioms to probabilistic measures requires highly restrictive—and arguably unnatural—mathematical assumptions, particularly when applied to the finite domains typical of modern AI.

The Core Axioms of Belief

In the mid-20th century, Richard Cox proposed that if one starts with a few primitive notions of belief, the rules of probability inevitably follow. Halpern’s analysis focuses on the two core axioms at the heart of this derivation:

  1. A1 (Negation): The belief in the negation of an event ("not V") is a function $S$ of the belief in the original event ("V").
  2. A2 (Conjunction): The belief in the conjunction of two events ("V and V’") is a function $F$ of the conditional belief of "V’ given V" and the belief in "V".

While these axioms appear intuitive, Halpern (building on work by researchers like Paris) notes a significant gap: these axioms alone are insufficient to guarantee a probability measure, especially in finite sets of possibilities.

The Challenge of Finite Domains

Most rigorous proofs of Cox’s Theorem rely on a "density" assumption. This assumption requires that for any three values in the range of the belief function, one can find subsets in the domain that exactly match those values. Effectively, this implies that the domain of discourse must be infinite.

This presents a major problem for computer science. Most AI applications operate on finite domains, yet the "density" requirement (often referred to as Par5 in the literature) is a dealbreaker for such systems. Halpern seeks to identify exactly what "mathematical baggage" is required to make Cox’s Theorem function in the absence of an infinite domain.

Key Theoretical Insights

Halpern’s investigation yields several critical insights into the structure of belief functions:

The Associativity Requirement

For the theorem to hold on finite domains, the function $F$ (handling conjunctions) must be associative—meaning $F(x, F(y, z)) = F(F(x, y), z)$—for all possible values in the range $[0, 1]$, not just the specific values the belief function happens to take. Halpern uses this paper to correct the historical record; while he previously claimed Cox was unaware of this need, he now acknowledges that Cox recognized the necessity of associativity, even if he did not fully justify why it should hold universally.

Theorem 2: The Counterexample

One of the paper's most significant contributions is Theorem 2. Halpern constructs a counterexample proving that a belief function can exist on a finite domain that satisfies the basic Cox axioms and is infinitely differentiable (smooth), yet remains fundamentally non-isomorphic to any probability measure. This proves that "smoothness" is not a substitute for the density assumption.

The "Finite Fixes"

Halpern proposes two primary ways to salvage the theorem for finite domains:

  • Theorem 3: This shows that if one assumes $F$ is associative and $S$ satisfies specific functional equations for all real numbers in the interval $[0, 1]$, the isomorphism to probability is recovered.
  • Theorem 5 (The Uniformity Approach): This suggests that if a belief function is defined uniformly across a large family of possible sets (rather than a single fixed domain), one can recover probability without requiring any single domain to be infinite.

Conclusion and Philosophical Implications

While Halpern provides the mathematical scaffolding necessary to support Cox’s Theorem in finite settings, he remains skeptical of the result's "inevitability." He argues that the assumptions required to fix the theorem—such as universal associativity over the entire real interval—are heavy-handed technical requirements rather than "common sense" intuitions.

Ultimately, the paper leaves the reader with a choice: one must either accept these strong mathematical constraints as foundational truths to keep the Bayesian framework intact, or acknowledge that probability theory may require a different, perhaps less "inevitable," justification for reasoning within finite-state systems.

Summary updated

BibTeX
@misc{halpern1999cox,
  author = {Joseph Y. Halpern},
  title = {{Cox's Theorem Revisited}},
  year = {1999},
  eprint = {cs/9911012},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/9911012},
}

Loading related content...

Figure