Saturday, November 23, 2013

The Axiom of Choice in some claims about probabilities

I spent the last week trying to get clear on the logical interconnections between a number of results about probabilities that are relevant to formal epistemology and that use a version of the Axiom of Choice in proof, such as:

  1. For every non-empty set Ω, there is an ordered field K and a K-valued probability function that assigns non-zero finitely additive probability to every non-empty subset of Ω.
  2. For every non-empty set Ω, there is a full finitely additive conditional probability on Ω (i.e., a Popper function with all non-empty subsets normal).
  3. The Banach-Tarski Paradox holds: one can decompose a three-dimensional ball into a finite number of pieces that can be moved around and made into two balls of the same size.
  4. There are Lebesgue non-measurable sets in the unit interval [0,1].
All of these results require some version of the Axiom of Choice. It turns out that there is a very simple map of their logical interconnections in Zermelo-Fraenkel (ZF) set theory:
  • BPI→(1)→(2)→(3)→(4),
where BPI is the Boolean Prime Ideal theorem, a weaker version of the Axiom of Choice.

The proof from BPI to (1) is standard--just let K be an ultrapower of the reals with an appropriate ultrafilter. That from (1) to (2) is almost immediate: just define the conditional probabilities via the ratio formula and take the standard part. Pawlikowski's proof of Banach-Tarski easily adapts to use (2) (officially, he uses Hahn-Banach). Finally, Foreman and Wehrung show in ZF that every subset of Rn is Lebesgue measurable iff every subset of [0,1] is. But it follows from (2) that not every subset of R3 is Lebesgue measurable.

This has important consequences. Without the Axiom of Choice, one can prove that either (a) there are sets that have no regular probabilities no matter what ordered field is chosen for the values and no full conditional probabilities, or (b) the Banach-Tarski Paradox holds and hence there are no rigid-motion-invariant probabilities on regions of three-dimensional space big enough to hold a ball. And in either case, Bayesianism has a problem.


grodrigues said...

Just in case it is useful:

According to Herrlich, "Axiom of Choice" pg. 134, diagram 5.25, we have

BPI => HB => Banach-Tarski => Non-Lebesgue measurable sets exist.

All the implications are proper with the possible exception of HB => Banach-Tarski.

Herrlich defers to Howard and Rubin, "Consequences of the axiom of choice" for some of the details (mostly, those that have to do with the construction of ZF models where one theorem or other does not hold) which is the standard monograph to check for this kind of stuff. There is website associated to the book where you can fill out forms and get back such info as all the equivalent versions of some choice principle and such like. The link is here.

A couple more random, potentially interesting notes.

(1) By Solovay and Shelah's results, ZF + AC + IC (existence of an inaccessible cardinal) is equiconsistent with ZF + DC (dependent choice) + LM (all subsets of R are Lebesgue measurable).

(2) BPI is equivalent to Tychonoff for compact Hausdorff spaces. The latter has a constructively valid proof; the catch is that the proof is made in the world of locales and to translate the proof to topological spaces, BPI is needed. Johnstone's book "Stone Spaces" is the go-to monograph for this kind of "pointless topology" (Johnstone himself wrote a paper whimsically titled "The point of pointless topology"). HBT, as some other analysis big guns like Gelfand-Naimark duality, itself have constructively valid versions and proofs in the context of topoi. Measure theory can also be done internally, and thus constructively, to a topos. This is an area of active research, but a starting reference is Mathew Jackson's phd thesis A sheaf theoretic approach to measure theory. Some of this stuff is "just" internalizing to a topos constructions with measure *algebras* (not spaces), for which the reference is Fremlin's vol.3 in his 5-volume opus dedicated to measure theory, also available online.

Alexander R Pruss said...

Thanks! I knew that BPI→HB is proper, but I didn't know that BT→Lebesgue Nonmeasurable Sets was. That's nice to know.

HB→BT seems to be proper (see here and put in 309 to be true and 52 to be false), which is unsurprising.

I haven't done anything with topoi since I was teenager. :-) Might be good to look at them again.

Alexander R Pruss said...

What I am currently most curious about is whether my (2) implies HB.

By the way, it would be interesting to see if some of the ways of translating pointless topology to topology could not be adapted to use HB instead of BPI, basically replacing ultrafilters with probability measures. (Here's what makes me wonder about this. A couple of days ago, I noticed that given HB, you can represent any boolean algebra as closed sets in a compact topological space (just represent A by all the probability measures with support in A). The embedding preserves meets but doesn't preserve negations. So you get a part of what BPI gives you with HB.)

Alexander R Pruss said...

Here's a sketch of the proof of 2 from HB:

By the ideal-filter duality, HB is equivalent to the claim for any boolean algebra and filter, there is a probability measure that makes every member of the filter have unit probability.

Let B be any boolean algebra. Let V be the set of all non-empty finite boolean subalgebras of B. For a in V, let a* be the filter { b in V : a subseteq b }. Let F be the filter on 2^V generated by all the a*. By Hahn-Banach, let mu be a measure on 2^V that makes every member of F have unit probability. Let 'R = R^V / ~, where f~g iff mu{ f = g } = 1.

Finally, for each U in V, let nu_U be the probability measure on the boolean algebra U that assigns equal weight to each atom of U.

Define an 'R-valued measure nu on B. Fix a in B. Then nu(a) is supposed to be an equivalence class of functions from V to R. We shall define a representative f_a in R^V. Fix U in V. If a is not in U, then let f_a(a)=1. If a is in U, then let f_a(a)=nu_U(a). Let nu(a) = [f_a]. Since {a}* in F, mu({a}*) = 1, so we can ignore the case where a is not in U for verifying additivity.

Write x < y for x and y in 'R iff mu { x < y } = 1. If 0 < y, then we can divide by y.

Define st:'R -> R cup {UND} (for any element UND not in R) by st([f]) = I_mu(f) if f is mu-almost surely bounded, where I_mu is the integral of f over V with respect to mu, and st([f]) = UND otherwise.

Note that nu(a) > 0 for any nonzero a in B, since f_a > 0 on {a}* and mu({a}*}=1. Thus, we can define
P(a|b) = st( mu(ab)/mu(b) ).

Alexander R Pruss said...

In the original version of the post I said that I thought I could prove that Hahn-Banach implies 1. But my proof is mistaken. Oops.