In classical logic, we rely on a comforting property called compactness. It states that if an infinite set of premises is unsatisfiable, there must be some finite subset that is already unsatisfiable. Compactness guarantees that logical proofs can always be written down in a finite number of steps: if a conclusion follows from an infinite sea of data, a finite subset of that data is sufficient to guarantee it.
But when we step out of pure discrete logic and enter the world of continuous quantities—such as probabilities, infinite time horizons, or numerical weights—this guarantee shatters. We enter the realm of non-compact logics, where an infinite premise entailment gap emerges, fundamentally altering how we must design automated reasoning systems.
Why Quantitative Reasoning Breaks Compactness
To build intuition for why compactness fails when numbers are involved, consider an infinite set of assumptions asserting that the probability of an event $\phi$ is positive but arbitrarily small:
$$ \Gamma = \{ P(\phi) \le \frac{1}{n} \mid n \in \mathbb{N}^+ \} \cup \{ P(\phi) > 0 \} $$
Is the entire set $\Gamma$ satisfiable? No. The only real number that is less than or equal to $1/n$ for every positive integer $n$ is exactly $0$, which directly contradicts the requirement that $P(\phi) > 0$.
However, if you take any finite subset of $\Gamma$, it is perfectly satisfiable. If we only look at a subset bounded by some maximum integer $N$ (for example, $n = 1000$), we can simply set $P(\phi) = 1/(N+1)$, satisfying every formula in that finite subset.
This is the core mechanism of non-compactness: finite consistency no longer guarantees infinite consistency. As Fausto Barbero et al. point out in Strongly complete axiomatization for a logic with probabilistic interventionist counterfactuals, a system can fail to formally conclude that a probability is zero even if it is given an infinite list of premises bounding it below every positive fraction.
This failure is not an isolated mathematical quirk; it occurs across diverse formalisms that attempt to ground real-world uncertainty:
- Causal Hierarchies: When formalizing Judea Pearl's structural causal models across association, intervention, and counterfactuals, Duligur Ibeling et al. demonstrated in Probabilistic Reasoning Across the Causal Hierarchy that probabilistic causal logics lack compactness, meaning they cannot seamlessly derive valid conclusions from unbounded sets of assumptions.
- Weighted Transition Systems: In cyber-physical systems where transitions carry real-valued costs or resource constraints, Mikkel Hansen et al. showed in A Complete Approximation Theory for Weighted Transition Systems and Reasoning About Bounds in Weighted Transition Systems that reasoning about upper and lower bounds introduces non-compactness, complicating automated verification tools.
- Multi-Agent Epistemic Spaces: When modeling what agents believe about other agents' beliefs, Adam Bjorndahl et al. noted in From Type Spaces to Probability Frames and Back, via Language that infinite collections of belief statements can be inconsistent despite every finite sub-collection being consistent.
The Consequences: Weak vs. Strong Completeness
Why do logicians care so deeply about compactness? Because its loss breaks the bridge between weak completeness and strong completeness.
- Weak completeness means that if a formula is universally valid (true in all possible models), it can be proven from an empty set of premises.
- Strong completeness means that if a formula logically follows from an arbitrary, potentially infinite set of premises, it can be proven from that set.
In compact logics, weak completeness automatically scales up to strong completeness. In non-compact logics, that bridge is broken. You can have a system capable of proving isolated truths, but entirely incapable of reasoning safely from infinite streams of data or infinite time horizons. For instance, in temporal logics tracking uncertain events over an infinite future, Dragan Doder et al. in A Probabilistic Logic for Reasoning about Uncertain Temporal Information emphasize that special care must be taken to balance logical rules to achieve strong completeness under $\sigma$-additive semantics.
Furthermore, the absence of compactness breaks fundamental reasoning properties like logical closure—the expectation that if a system infers a set of facts, it must also be able to infer their logical consequences. As Jandson S. Ribeiro et al. show in Belief Change and Non-Monotonic Reasoning Sans Compactness, standard axioms for non-monotonic inference fail to guarantee logical closure in non-compact settings. This allows for catastrophic failure modes where a system derives an infinite set of facts but fails to conclude their necessary implications, requiring explicit closure requirements to maintain consistency. A similar vulnerability in argument compilation is identified by Leila Amgoud et al. in Compilation of Logical Arguments, where highly productive systems can fail to be closed under deduction.
Restoring Strong Completeness via Infinitary Rules
To restore strong completeness, researchers must bypass the limitations of finite deductions. The most powerful tool for doing so is the introduction of infinitary proof systems.
Instead of requiring a proof to proceed via a strictly finite sequence of steps, an infinitary rule allows a conclusion to be drawn from a countable infinity of premises simultaneously.
In Strongly complete axiomatization for a logic with probabilistic interventionist counterfactuals, the authors utilize this exact mechanism to resolve non-compactness. By allowing a rule that takes an infinite sequence of decreasing probability bounds as premises, the system can formally derive that a probability must be zero in a single step:
$$\frac{\alpha \to P(\phi) \le \frac{1}{n} \quad \text{for all } n \in \mathbb{N}^+}{\alpha \to P(\phi) = 0}$$
Similarly, Mikkel Hansen et al. in Reasoning About Bounds in Weighted Transition Systems discuss incorporating infinitary axioms related to the Archimedean property to force strong completeness in weighted systems.
Finally, when standard canonical model constructions fail because infinite sets of consistent formulas cannot be realized, alternative structural approaches are required. As the authors demonstrate in From Type Spaces to Probability Frames and Back, via Language, model construction can be anchored on satisfiability within existing structures, ensuring well-defined representations of agent belief hierarchies even when standard logical compactness fails.
Key Foundational Work
A Complete Approximation Theory for Weighted Transition Systems (2016) — contributed 2 concept elements to this direction.
A Probabilistic Logic for Reasoning about Uncertain Temporal Information (2015) — contributed 1 concept elements to this direction.