2
$\begingroup$

Let us consider the following two theorems by Gödel:

  1. Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$;

  2. For any consistent system F within which a certain amount of elementary arithmetic can be carried out, the consistency of F cannot be proved in $F$ itself.

Like others, probability theory is also an axiom-based system with 3 axioms and supports minimum arithmetic.

From the above information, it looks like probability theory also suffers from Gödel's incompleteness theorem. Can't it? If not, then where I am going wrong?

Thus is there a possibility that there may exist two statements in probability theory that contradict each other and the existence of unprovable facts?

$\endgroup$
5
  • 1
    $\begingroup$ 1) ... provided that the system is consistent and is "sufficently strong" to include some relevant parts of arithmetic. $\endgroup$ Feb 3, 2019 at 18:07
  • $\begingroup$ @MauroALLEGRANZA Yep, instead of that I kept some, since my question is on the possibility of point 2 over probability, it may not effect. $\endgroup$
    – hanugm
    Feb 3, 2019 at 18:09
  • 1
    $\begingroup$ Item 2) is formulated incorrectly. The point is that the proof of consistency cannot be carried out within the system itself. $\endgroup$ Feb 3, 2019 at 18:46
  • $\begingroup$ @AndrésE.Caicedo Edited... $\endgroup$
    – hanugm
    Feb 3, 2019 at 18:50
  • 2
    $\begingroup$ In Reverse Mathematics there has been the identification of an axiom known as WWKL with (Advanced) Probability theory consequences (like existence of fairness) which is independent of the base RCA system, in which basic probability can be formulated. Whether this relates to Godel's Theorems I don't currently know. $\endgroup$ Feb 5, 2019 at 20:52

1 Answer 1

1
$\begingroup$

This can't really be answered without specifying exactly what "probability theory" is. You say that it's an axiom-based system, but what are those axioms?

You mention that there are specifically three. Based on this I suspect you're referring to the Kolmogorov axioms, which roughly say:

  1. The expected value function $\mathsf{E}$ is non-negative.

  2. The maximum that $\mathsf{E}$ attains is exactly $1$, that is, the probability of the "trivial event" is $1$.

  3. $\mathsf{E}$ is countably additive.

Even ignoring some fundamental issues (see below), these axioms are obviously incomplete: they do not decide for example whether there is an event with probability strictly between $0$ and $1$, and this is definitely something we should be able to express. However, being incomplete is not the same as being susceptible to Godel's theorem: a theory can be incomplete for "non-Godelian reasons." What exactly "Godelian" means isn't clear, but certainly any Godelian theory should have the following property:

A computably axiomatizable theory is essentially undecidable iff every computably axiomatizable extension of that theory is incomplete.

For example, the theory of algebraically closed fields is incomplete (it doesn't pin down the characteristic of the field) but not essentially incomplete (for each $p$, the theory of algebraically closed fields of characteristic $p$ is computably axiomatizable and complete). Since there are very simple probability systems out there (e.g. consider a theory which admits only the always-happens and never-happens events), any reasonable implementation of the Kolmogorov axioms is not essentially incomplete. So in a precise sense, even though those axioms (modulo their issues - again, see below) are incomplete, they are not susceptible to Godel's theorem. The culprit, unsurprisingly, is expressive power.


This raises the question:

Is there a natural theory extending Kolmogorov's which is essentially undecidable?

At this point we do have to address the above-mentioned issues with the Kolmogorov axioms. There are two:

  • We need to say more about the codomain: presumably we at least want to say that $\mathsf{E}$ takes values in an ordered monoid, and we probably want to say more than that.

  • Axiom $3$ is not first-order - we either have to $(i)$ whip up a first-order approximation to it, $(ii)$ shift the "naive" context of probability theory (= event space + $\mathbb{R}$) to a richer one (= something with a set-theoretic apparatus allowing us to talk about arbitrary countable sets), or $(iii)$ work in a richer logic than first-order logic, such as $\mathcal{L}_{\omega_1,\omega}$.

I'll take these in reverse order.

Option $(iii)$ doesn't seem appropriate here, although I personally like it. Perhaps surprisingly, Godelian ideas don't go out the window altogether even when we leave the realm of first-order logic, so $(iii)$ actually is a priori something that could yield interesting results. However, it quickly becomes rather technical and I suspect it's not what's wanted here, so let's ignore it here.

Option $(ii)$ is arguably the best one here, but the set-theoretic apparatus we would need to bring into play will on its own be susceptible to Godel's incompleteness theorem (see e.g. here). So at this point we do get Godelian, but not for reasons related to the actual topic at hand.

This leaves $(ii)$ as the only real faithful option. So what we need to do now is $(a)$ identify whatever additional axioms we need to "make Kolmogorov work right," and in particular $(b)$ pin down a "first-order approximation" to Axiom $3$. The good news is that there's a natural approach to $(b)$, namely to work with a scheme of axioms addressing each first-order definable instance of the principle at hand separately. This is the approach taken for example in (first-order) $\mathsf{PA}$ and $\mathsf{ZFC}$ (consider induction and separation/replacement respectively), and is extremely flexible.

So this suggests the following framework for first-order probability theory:

  • We have two sorts, an event sort and a probability sort.

  • On the probability sort we have binary operations $+$ and $\times$, a binary relation $<$, and constants $0$ and $1$; and we have axioms asserting that these turn that sort into an ordered field.

  • On the event sort we have two binary operations $\cap$ and $\cup$, a binary relation $\subseteq$, and two constants $\emptyset$ and $\Omega$, and axioms asserting that this turns that sort into a Boolean algebra with bottom $\emptyset$ and top $\Omega$.

  • Connecting both sorts, we have a function $\mathsf{E}$: its domain is the event sort and its codomain is the probability sort. We add axioms saying that $ran(\mathsf{E})\subseteq [0,1]$, $ran(\Omega)=1$, and $ran(\emptyset)=0$; and axioms saying that $\mathsf{E}$ is $2$-additive (and hence finitely additive).

  • We have the countable completeness scheme asserting that there is no definable failure of countable completeness.

  • And finally, we leave the door open for additional structure and axioms. For example, maybe we want to say that for every event $X$ there is some $Y$ such that $\mathsf{E}(Y)={\mathsf{E}(X)\over 2}$; or maybe we want to view events as subsets of a vector space. Note that I'm even allowing additional sorts (e.g. if we want events to be subsets of a vector space, we'll also want a sort for vectors and a sort for scalars).

That last bulletpoint lets us frame the question more correctly in my opinion:

What are some natural additional structure/axioms which make the resulting probability theory essentially incomplete?

The point is that, since as mentioned above there are very simple $\sigma$-algebras, if we don't add any such additions then we certainly won't get essential incompleteness. (Crucially, the real numbers are less complicated than the naturals from the point of Godel, and indeed much of logic: the theory of real closed fields is decidable!)

The most natural candidates I can think of are additions which describe contexts where events are arithmetical in some sense. There are of course no interesting uniform probability measures when $\Omega=\mathbb{N}$, but there are very natural non-uniform ones (e.g. the binomial distribution). If we want to look at such a measure in the context of number theory, then we presumably want to put enough structure on the event space('s underlying set) to do number theory - and this immediately brings in Godel.

However, again we're seeing incompleteness for reasons unrelated to probability. So really the right question to ask is:

What are some natural additional structure/axioms which make the resulting probability theory essentially incomplete, but which do not automatically yield essential incompleteness on their own?

I know of no natural candidates for such a thing, but since probability isn't my area I'm not sure how much that's worth.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.