# Probability theory without deductive closure

Human knowledge is not deductively closed. Uncertainty can arise from that just as much as from lack of brute facts. (When a Harvard graduate was reported to have thought that the earth is farther from the sun in the winter than in the summer and that that's why seasons happen, I commented to someone that that was stupid because he ought to have known that when it's winter in the northern hemisphere, it's summer in the southern hemisphere and vice-versa. I was told that I was making the mistake of expected a person's knowledge to be deductively closed. I don't altogether agree, since those who make fun of Sarah Palin for (allegedly) not knowing that Africa is a continent were not really expecting all humans to be omniscient.; it's similar to that.)

But the conventional mathematical theory of probability is deductively closed. As a means of expressing uncertainty, its closure can be useful because in telling us how much uncertainty is justified, it can make us aware of logical connections we might have missed.

However, let's suppose you're wondering if some number with an almost unimaginably large number of digits is prime. (Say it's $5963$, which, unbeknownst to all humans, can be factored as $67\times89$.) After many years of work with supercomputers, you've ruled out the possibility of its divisibility by all primes up to and including $17$, which is the largest prime not exceeding its cube root. If I'm not mistaken, there are ways to estimate the sum of primes bigger than that but not bigger than the square root of the number to be factored (In the present example, $1/19 + 1/23 + 1/29 + 1/31 + 1/37 + 1/41 + 1/43 + 1/47 + 1/53 + 1/59 + 1/61 + 1/67 + 1/71 + 1/73 \approx 0.354$.) It seems reasonable to consider this a sort of upper bound on the probability that the large number considered is composite. But in a deductively closed system, that probability is $0$ or $1$, and if it's $1$, then $0.354$ is not an upper bound on it.

Is there any mathematically precise theory of probability without deductive closure?

• Excellent question and cursed be those that say otherwise. Apr 25 '16 at 18:33
• @PaulTaylor : Thank you. I'd say cursed be those who can't use language. Someone down-voted this without saying why. I wonder what such people think they accomplish? Do they think their behavior discourages what they consider bad questions, even though they leave the poster with no idea what's bad about it and hence with no way of doing better? $\qquad$ Apr 25 '16 at 23:41
• Paul's comment certainly discourages expressing a dissenting opinion, so to avoid getting into an argument, the downvoter may well feel it would be wiser to keep his/her mouth shut. And that's too bad. Apr 26 '16 at 0:06
• Should this be tagged math-philosophy? Apr 26 '16 at 1:21
• Boaz Barak has recently blogged about a computational approach to belief (in which deduction is computationally expensive) which may eventually serve as a suitable model for this sort of reasoning, although it is not yet fully formalised: windowsontheory.org/2016/04/13/… . Apr 26 '16 at 2:29

It seems to me that the various accounts and theories of formal representations of belief might be something approaching what you want.

Without deductive closure, it seems to me that the probability of an event depends on how that event is described, since deductively equivalent statements might have different probabilities. This seems to give the theory a somewhat intensional nature rather than extensional, where the theory you seem to envisage depends on an agent's knowledge, rather than assuming a perfect kind of knowledge that is capable of finding all deductively equivalent statements.

Meanwhile, if you follow the link, you will see that various philosophers have proposed various formal accounts, with varying levels of mathematical detail, of a theory for degrees-of-belief.

People are actively working on this, although maybe not many people. See, for example, Uniform coherence by Garrabrant, Fallenstein, Demski, and Soares, and the references therein. The abstract:

While probability theory is normally applied to external environments, there has been some recent interest in probabilistic modeling of the outputs of computations that are too expensive to run. Since mathematical logic is a powerful tool for reasoning about computer programs, we consider this problem from the perspective of integrating probability and logic. Recent work on assigning probabilities to mathematical statements has used the concept of coherent distributions, which satisfy logical constraints such as the probability of a sentence and its negation summing to one. Although there are algorithms which converge to a coherent probability distribution in the limit, this yields only weak guarantees about finite approximations of these distributions. In our setting, this is a significant limitation: Coherent distributions assign probability one to all statements provable in a specific logical theory, such as Peano Arithmetic, which can prove what the output of any terminating computation is; thus, a coherent distribution must assign probability one to the output of any terminating computation. To model uncertainty about computations, we propose to work with approximations to coherent distributions. We introduce uniform coherence, a strengthening of coherence that provides appropriate constraints on finite approximations, and propose an algorithm which satisfies this criterion.

I am not sure how your example of desired probabilistic properties of a given "large" and "complicated" number relates with deductive closure. However, it seems that such an example may have to do with attempts to define a notion of randomness of a given, specific (in the simplest case, binary) sequence, and then say something about "probabilistic properties" of such a sequence. If so, relevant may be the survey paper "ALGORITHMS AND RANDOMNESS" by A. N. KOLMOGOROV AND V. A. USPENSKII in THEORY PROBAB. APPL., Vol. 32, No. 3, pp. 389--412.

Let $\Omega:=\{0,1\}^{\mathbb N}$, the set of all binary sequences. A notion of a computable (probability) distribution $P$ on $\Omega$ is defined there. Then the notion of a binary sequence which is random relative to a given computable distribution is defined, in two equivalent ways. See page 399 in the mentioned paper. For a finite binary sequence $x=a_0, a_1,\cdots,a_n$, let $\pi(x; P)$ denote the conditional probability $P(\Gamma_{x,1})/P(\Gamma_x)$ relative to $P$ of $x$ being followed by $1$, where $\Gamma_x$ is the set of all binary sequences in $\Omega$ beginning with $x$ and $\Gamma_{x,1}$ is the set of all binary sequences in $\Omega$ beginning with $x,1=a_0, a_1,\cdots,a_n,1$.

Then at the top of page 400:

Here is a precise statement of Vovk’s theorem: Let $P'$ and $P''$ be arbitrary computable distributions on $\Omega$ and let $a_0,a_1,\cdots$ be a random sequence relative to $P'$ and $P''$ simultaneously. Then $\pi(a_0, a_1,\cdots,a_n; P')-\pi(a_0,a_1,\cdots,a_n; P'')\to0$ as $n\to\infty$. Thus $\pi(x; P')$ and $\pi(x; P'')$ are close to one another whenever the chain $x=a_0,a_1,\cdots,a_n$ is long and we are entitled to speak about the conditional probability of occurrence of a one after a specified beginning segment of zeros and ones -- the entire sequence viewed as a whole is random relative to some distribution (unknown to us!).

Until now, we have spoken only about the randomness of binary sequences. However the above algorithmic approach can be applied also to more general situations.

You might like Les Valiant's book "Probably Approximately Correct" which is an approach to explaining human knowledge that's also a busy topic in machine learning. It goes beyond lack of deductive closure to seeing how learning happens without much deduction at all. There's a related Wikipedia article: PAC learning.

If you model a human brain as a stochastic reasoning device, you can posit uncertainty as to whether the mechanism of the brain has, at some point in time, reached some logical conclusion and stored it for easy access. A device that must expend time/space to enumerate the deductive closure of its current knowledge base would at no finite time be deductively closed in a rich enough system. All this can be formalized within probability, although it requires some uncertainty about the reasoning device---whether that's inherent stochasticity or uncertainty about its initial configuration, say.