Infinitary Proof Systems for Non-Compact Probabilistic Logics

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 29 papers17 conceptsfrozen 2026-10-04

In classical logic, we rely on a property called compactness: if a set of statements is inconsistent, there must be some finite subset that is also inconsistent. This property is the bedrock of standard automated reasoning. It ensures that if something is logically necessary, we can prove it using a finite sequence of steps.

However, when we move into the realm of probability, time, and causality, compactness often vanishes. This creates a "completeness gap" where our standard logical tools can no longer derive all the truths hidden within our assumptions. Recent research has focused on bridging this gap using infinitary inference rules and specialized lattice-theoretic frameworks.

The Problem of Non-Compactness

To understand why compactness fails, consider a simple probabilistic statement: "The probability of event $A$ is greater than zero." Now, imagine an infinite set of statements asserting that the probability of $A$ is less than $1/n$ for every possible integer $n$.

Any finite collection of these statements is perfectly consistent—you can always find a tiny positive number that satisfies them. But the infinite set implies the probability must be exactly zero, which contradicts our first statement. As Adam Bjorndahl and Joseph Halpern point out in From Type Spaces to Probability Frames and Back, via Language, this non-compactness makes it difficult to build "canonical models" that represent every possible hierarchy of agent beliefs.

Infinitary Rules as a Solution

If the problem is that finite sets of premises cannot capture the behavior of infinite sequences, the solution is to allow rules with an infinite number of premises.

Dragan Doder and Zoran Ognjanovic demonstrate this in A Probabilistic Logic for Reasoning about Uncertain Temporal Information. To reason about events over infinite time horizons, they employ infinitary inference rules. These rules allow a system to conclude a statement (like "the probability is zero") only after verifying an infinite list of premises (like "the probability is less than $1/n$ for all $n$"). This approach achieves strong completeness, meaning the logic can derive every valid conclusion even from infinite sets of assumptions.

Reasoning Across the Causal Hierarchy

This challenge extends directly into causal inference. Duligur Ibeling and Thomas Icard mapped out the logical foundations of Judea Pearl’s "Ladder of Causation" in Probabilistic Reasoning Across the Causal Hierarchy. They found that while the three levels of the hierarchy (association, intervention, and counterfactuals) are axiomatizable, they still suffer from non-compactness.

When we add more practical tools to these logics, such as summation operators for marginalizing variables, the complexity increases. Milan Mossé, along with Ibeling and Icard, showed in On Probabilistic and Causal Reasoning with Summation Operators that these operators can even lead to undecidability if the ranges of variables are not restricted. Again, they turn to infinitary proof systems to establish completeness in these expressive but non-compact environments.

Maintaining Logical Consistency

The loss of compactness doesn't just affect how we prove things; it affects how we change our minds. In classical belief revision, we assume that the set of things we believe is "logically closed"—if you believe $A$ and $A \implies B$, you must believe $B$.

In Belief Change and Non-Monotonic Reasoning Sans Compactness, Jandson S. Ribeiro, Abhaya Nayak, and Renata Wassermann reveal that in non-compact logics, standard axioms fail to guarantee this closure. A system could theoretically infer an infinite set of facts but fail to infer their necessary logical consequences. To fix this, they propose new axioms that explicitly enforce logical closure, ensuring that belief revision remains consistent even when the underlying logic is "leaky" due to a lack of compactness.

Specialized Inference for Independence

Because a single, universal set of finite axioms for all probabilistic implications is mathematically impossible, researchers also look for specialized frameworks. Dirk Van Gucht and Marc Gyssens explored this in On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach. By treating conditional independence as a lattice-theoretic problem, they provide a way to navigate specific subclasses of independence statements where inference is still tractable, bypassing the impossibility of a general finite solution.

By moving beyond finite, compact systems, this body of work provides the rigorous mathematical scaffolding needed to reason about the infinite complexities of probability, time, and cause-and-effect.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 6 papers
  2. Version 1 · 2026-10-04 · 9 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_logical_compactness_1141bc0e,
  title = {logical compactness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logical-compactness/rdr_1141bc0ecc5a44c592a0d655d7856f4e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_infinitary_proof_systems_for_non_compact_1141bc0e_v1,
  title = {Infinitary Proof Systems for Non-Compact Probabilistic Logics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinitary-proof-systems-for-non-compact-probabilistic-logics/rdr_1141bc0ecc5a44c592a0d655d7856f4e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}