Another infinite dice game

Suppose infinitely many people independently roll a fair die. Before they get to see the result, they will need to guess whether the die shows a six or a non-six. If they guess right, they get a cookie; if they guess wrong, an electric shock.

But here’s another part of the story. An angel has considered all possible sequences of fair die outcomes for the infinitely many people, and defined the equivalence relation ∼ on the sequences, where α ∼ β if and only if the sequences α and β differ in at most finitely many places. Furthermore, the angel has chosen a set T that contains exactly one sequence from each ∼-equivalence class. Before anybody guesses, the angel is going to look at everyone’s dice and announce the unique member α of T that is ∼-equivalent to the actual die rolls.

Consider two strategies:

1. Ignore what the angel says and say “not six” regardless.

2. Guess in accordance with the unique member α: if α says you have six, you guess “six”, and otherwise you guess “not six”.

When the two strategies disagree for a person, there is a good argument that the person should go with strategy (1). For without the information from the angel, the person should go with strategy (1). But the information received from the angel is irrelevant to each individual x, because which ∼-equivalence class the actual sequence of rolls falls into depends only on rolls other than x’s. And following strategy (1) in repeats of the game results in one getting a cookie five out of six times on average.

However, if everyone follows strategy (2), then it is guaranteed that in each game only finitely many people get a shock and everyone else gets a cookie.

This seems to be an interesting case where self-interest gets everyone to go for strategy (1), but everyone going for strategy (2) is better for the common good. There are, of course, many such games, such as Tragedy of the Commons or the Prisoner’s Dilemma, but what is weird about the present game is that there is no interaction between the players—each one’s payoff is independent of what any of the other players do.

(This is a variant of a game in my infinity book, but the difference is that the game in my infinity book only worked assuming a certain rare event happened, while this game works more generally.)

My official line on games like this is that their paradoxicality is evidence for causal finitism, which thesis rules them out.

Mereology, plural quantification and free lunches

It is sometimes claimed that arbitrary mereological fusions and plural quantification are a metaphysical free lunch, just a new way of talking without any deep philosophical (or at least metaphysical) commitments.

I think this is false.

Consider this Axiom of Choice schema for mereology:

1. If for every x and y such that ϕ(x) and ϕ(y), either x = y or x and y don’t overlap, and if every x such that ϕ(x) has a part y such that ψ(y), then there is a z such that for every x such that ϕ(x), there is common part y of x and z such that ψ(y).

Or this Axiom of Choice schema for pluralities:

2. If for all xx and yy such that ϕ(xx) and ϕ(yy) either xx and yy are the same or have nothing in common, then there are zz that have exactly one thing in common with every xx such that ϕ(xx).

If arbitrary mereological fusions and plural quantification are a metaphysical free lunch, just a handy way of talking, then whether (1) or (2) is correct is just a verbal question.

But (1) and (2) respectively imply mereological and plural Banach-Tarski paradoxes:

3. If z is a solid ball made of points, then it has five pairwise non-overlapping parts, of which the first two can be rigidly moved to be pairwise non-overlapping and compose another ball of the same size as z, and the last three can likewise be so moved.

4. If the xx are the points of a solid ball, then there are aa, bb, cc, dd and ee which have nothing pairwise in common and such that together they make up xx, and there are rigid motions that allow one to move aa and bb into pluralities that have nothing in common but make up a solid ball of the same size as xx and to move cc, dd and ee into pluralities that have nothing in common and make up another solid ball of the same size.

Conversely, assuming ZF set theory is consistent, there is no way to prove (3) and (4) if we do not have some extension to the standard axioms of mereology or plurals like the Axiom of Choice. The reason is that we can model pluralities and mereological objects with sets of points in three-dimensional space, and either (3) or (4) in that setting will imply the Banach-Tarski paradox for sets, while the Banach-Tarski paradox for sets is known not to be provable from ZF set theory without Choice.

But whether (3) or (4) is true is not a purely verbal question.

One reason it’s not a purely verbal question is intuitive. Banach-Tarski is too paradoxical for it or its negation to be a purely verbal thing.

Another is a reason that I gave in a previous post with a similar argument. Whether the Banach-Tarski paradox holds for sets is not a purely verbal question. But assuming that the Axiom of Separation can take formulas involving mereological terminology or plural quantification, each of (3) and (4) implies the Banach-Tarski paradox for sets.

Unifying Separation and Choice

Let's round out Axiom of Choice Week. :-)

It’s occurred to me that there is a somewhat pleasant way to integrate the Axioms of Separation and Choice into one axiom schema.

Let’s say that a formula F(x,y) is a partial equivalence (is that the right term?) provided that it’s symmetric and transitive. Now consider this schema (understood to be universally closed over all free variables in F other than x and y):

• If F(x,y) is a partial equivalence, then for any set a there is a subset b such that for every x ∈ b we have F(x,x), and for any x ∈ a such that F(x,x), there is a unique y ∈ b such that F(x,y).

We might call this the Axiom (Schema) of Representatives.

To get the Axiom of Separation, given a formula G(x), let F(x,y) be the formula G(x) ∧ y = x. To get the Axiom of Choice, if c is a set of nonempty disjoint sets, let F(x,y) be ∃d ∈ c(x∈d∧y∈d) and let a = ⋃c (so we need the Union Axiom).

So what?

Nothing earthshaking.

But, first, while there is an advantage to keeping axioms separate for purposes of proving independence results, the more unified our axiomatic system is, the less ad hoc it looks. Unifying Separation and Choice can make us less suspicious about Choice, for instance.

Second, the Axiom Schema of Representatives has nice analogues in some other contexts than set theory. It seems to directly generalize to classes, for instance. Moreover, it extends very nicely to plural quantification to integrate Plural Comprehension with a version of Choice:

• If F(x,y) is a partial equivalence, then there are bs such that (i) for every x among the bs we have F(x,x), and (ii) for any x such that F(x,x), there is a unique y among the bs such that F(x,y).

I don’t know if there is a natural way to extend this to mereology.

One might complain that partial equivalence is less natural than equivalence. I don’t think so. First, it is defined by two instead of three conditions, which makes it seem more natural. Second, examples of partial equivalence relations tend to be more natural than examples of full equivalence relations if our domain is all of reality. For instance, “same color”, “same shape”, “same size”, “same species”, etc., are all partial equivalence relations, since only things with color are the same color as themselves, only things with shape are the same shape as themselves, etc. To form full equivalences, one needs to stipulate awkward relations like “same color or both colorless”.

Fusion and the Axiom of Choice

Assume classical mereology. Then for any formula that has a satisfier, there is a fusion of all of its satisfiers. More precisely, if ϕ is a formula with z not a free variable in ϕ, then the universal closure of the following under all free variables is true:

1. ∃xϕ → ∃zF_ϕ, x(z)

where F_ϕ, x(z) says that z is a fusion of the satisfiers of ϕ with respect to the variable x (there is more than one account of what exactly the “fusion” is). This is the fusion axiom schema.

Stipulate that a region of physical space is a fusion of points.

Question: Is there a nonmeasurable region of (physical) space?

Assuming the language for formulas in our classical mereology is sufficiently rich, the answer is positive. For simplicity, suppose that physical space is Euclidean (the non-Euclidean case is handled by working in a small neighborhood which is diffeomorphic to a neighborhood of a Euclidean space). Let ψ be the isomorphism between the points of physical space and the mathematical space R³. Let ϕ be the formula ψ(x) ∈ y. Applying (1), we conclude that for any subset a of R³, there is a set of points of physical space that correspond to a under ψ. If we let a be one of the standard nonmeasurable subsets of R³, we get an affirmative answer to our question.

But now we have an interesting question:

2. What grounding or explanatory relation is there between the existence of a nonmeasurable region of physical space and the existence of a nonmeasurable subset of mathematical space?

The two simplest options are that one is explanatorily prior to the other. Let’s explore these.

Suppose the existence of a nonmeasurable physical region depends on the existence of the nonmeasurable set. Well, it is a bit strange to think of a concrete object—a region of physical space—as partly grounded in the existence of a set. This doesn’t sound quite right to me.

What about the other way around? This challenges the fairly popular doctrine that complex things entities are a free lunch given simples. For if the existence of the nonmeasurable region is prior to the existence of an abstract set, it seems that we actually have quite a significant metaphysical “effect” of this complex object.

Moreover, if the existence of the nonmeasurable region is not grounded in the existence of nonmeasurable set, whether or not there is grounding running the other way, we have a difficult question of why there is in fact a nonmeasurable region. Without relying on nonmeasurable sets, it doesn’t seem we can get the nonmeasurable region out of the axioms of classical mereology. It seems we need some sort of a mereological Axiom of Choice. How exactly to formulate that is difficult to say, but one version that is enough for our purposes would be that given any formula ρ(x,y) that expresses a non-empty equivalence relation on the simples satisfying ϕ, there is an object z such that if ϕ(x) then there is exactly one simple x′ such that ρ(x,x′) and x′ is a part of z, and every object that meets z meets some simple satsifying ϕ.

But my intuition is that a mereological Axiom of Choice would badly violate the doctrine that complex objects are a free lunch. If all we had in the way of complex-object-forming axioms were reflexivity, transitivity and fusion, then it would not be crazy to say that complex objects are a fancy way of talking about simples. But the “indeterministic” nature of the Axiom of Choice does not, I think, allow one to say that.

Modality and the Axiom of Choice

Suppose that the set theory of our world is a Solovay model, where we don’t have the Axiom of Choice (AC), and where every subset of the reals is Lebesgue measurable. Now imagine that God picks out a line in space, and defines the Vitali equivalence relation for points on that line (where two points are equivalent if and only if the distance between them is a rational number). It is then surely within God’s power to create a particle of some unexemplified type T at exactly one point in every equivalence class. There is nothing incoherent about that! But if God did that, then there would surely be a set of the points containing a particle of type T. And that set would be a nonmeasurable Vitali set.

So what?

Well, prima facie, there are three possibilities about the existence of nonmeasurable sets:

1. Necessarily, there are no nonmeasurable sets.

2. Necessarily, there are nonmeasurable sets.

3. It is contingent whether there are nonmeasurable sets.

My argument strongly suggests that if there are no nonmeasurable sets, it is nonetheless possible that there are nonmeasurable sets. Hence, (1) is ruled out.

So we have an argument for the disjunction of (2) and (3).

Now, I think a lot of people have the intuition that mathematical facts are necessary. If so, then (3) is ruled out. They will see this as an argument for (2).

I don’t see it that way myself: I am quite open to contingent mathematical truths.

More generally, the argument shows that:

4. For any set of disjoint nonempty subsets of the reals, it is possible that there is a choice function.

Again, if the existence of pure sets is not a contingent matter, we conclude AC is true for all subsets of the reals.

An odd thought about ZFC

The axioms of ZFC set theory can be divided into (a) the positive axioms, that say that a set with certain properties exist, and (b) two negative axioms that deny the existence of certain sets (Extensionality: given any set, there is no other set with the same members; Regularity: no irregular sets).

The positive axioms divide further into two classes: (i) those that are obvious special cases of naive set theory’s Axiom of Comprehension, and (ii) the Axiom of Choice.

Here is an alternate intellectual history thought experiment. Suppose we never discovered the contradiction in naive set theory or anything like it, maybe because we had a psychological block against thinking about non-self-membered sets, applying Cantor’s Theorem to the universal set, etc. The Axiom of Choice would continue to have an intuitive plausibility, and the “mathematical need” for it, say in the case of the Hahn-Banach Theorem, would likely still arise. And so we would be pulled to adopt it.

This makes me think this. The other positive axioms of ZFC (i.e., the positive axioms of ZF) have an ad hoc feel to them. They are special cases of Comprehension, carefully chosen to both give enough applications of Comprehension and to avoid contradiction (we hope). I feel that much of the plausibility of the other positive axioms of ZFC comes from their being special cases of the highly intuitive—but incoherent—Axiom of Comprehension. And that’s a little suspicious.

Normally one thinks of the Axiom of Choice as the most suspicious of ZFC’s axioms. But here we have a source of suspicion for axioms of ZFC that does not affect Choice.

Well, maybe. Maybe an enemy of Choice could say that both Choice and Comprehension are the fruit of the poisonous tree of principles of plenitude.

Full conditional probabilities and the Axiom of Choice

Here’s a claim that turns out to be equivalent to the Axiom of Choice:

1. Given any non-empty set Ω and a collection M of [0,∞]-valued finitely additive measures on the powerset of Ω such that for any non-empty E ⊆ Ω there is a μ ∈ M with 0 < μ(E) < ∞, there is a full conditional probability P on the powerset of Ω definable in terms of the measures in M in the sense that for each non-empty E there is a μ ∈ M such that 0 < μ(E) < ∞ and for all A we have P(A|E) = μ(A∩E)/μ(E).

The easy direction of proof is from (1) to AC. Let M be the collection of all the finitely additive probability measures on Ω that assign probability one to some singleton. Clearly M has the desired properties. Now, for any non-empty E ⊆ Ω, there will be a μ ∈ M such that P(A|E) = μ(A∩E)/μ(E) and 0 < μ(E) < ∞. Thus, the point at which μ is concentrated must be in E. Moreover, it is clear that for each E, the measure μ must be unique. Let f(E) be the point at which μ is concentrated. This is a choice function for all subsets of Ω. Since Ω is an arbitrary non-empty set, we have AC.

The other direction follows by the method of proof of Lemma 3 here.

Domination and uniform spinners

About a decade ago, I offered a counterexample to the following domination principle:

1. Given two wagers A and B, if in every state B is at least as good as A and in at least one state B is better than A, then one should choose B over A.

But perhaps (1) is not so compelling anyway. For it might be that it’s reasonable to completely ignore zero probability outcomes. If a uniform spinner is spun, and on A you get a dollar as long as the spinner doesn’t land at 90^∘ and on B you get a dollar no matter what, then (1) requires you to go for B, but it doesn’t seem crazy to say “It’s almost surely not going to land at 90^∘, so I’ll be indifferent between A and B.”

But now consider the following domination principle:

2. Given two wagers A and B, if in every state B is better than A, then one should choose B over A.

This seems way more reasonable. But here is a potential counterexaple. Consider a spinner which uniformly selects a point on the circumference of a circle. Assume x is any irrational number. Consider a function u such that u(z) is a real number for any z on the circumference of the circle. Imagine two wagers:

• A: After the spinner is spun and lands at z, you get u(z) units of utility

• B: After the spinner is spun, the spinner is moved exactly x degrees counterclockwise to yield a new landing point z′, and you get u(z′) units of utility.

Intuitively, it seems absurd to think that B could be preferable to A. But it turns out that given the Axiom of Choice, we can define a function u such that:

3. For any z on the circumference of the circle, if z′ is the result of rotating z by x degrees counterclockwise around the circle, then u(z′) > u(z).

And then if we take the states to be the initial landing points of the spinner, B always pays strictly better than A, and so by the domination principle (2), we should (seemingly absurdly) choose B.

Remarks:

• The proof of the existence of u requires the Axiom of Choice for collections of countable sets of reals). In my Infinity book, I argued that this version of the Axiom of Choice is true. However, arguments similar to those in the book’s Axiom of Choice chapter suggest that the causal finitist has a good way out of the paradox by denying the implementability of the function u.

• Some people don’t like unbounded utilities. But we can make sure that u is bounded if we want (if the original function u is not bounded, then replace u(z) by arctan u(z)).

• Of course the function u is Lebesgue non-measurable. To see this, replacing u by its arctangent if necessary, we may assume u is bounded. If u were measurable and bounded, it would be integrable, and its Lebesgue integral around the circle would be rotation invariant, which is impossible given (3).

It remains to prove the existence of u. Let ∼ be the relation for points on the (circumference of the circle) defined by z ∼ z′ if the angle between z and z′ is an integer multiple of x degrees. This is an equivalence relation, and hence it partitions the circle into equivalence classes. Let A be a choice set that contains exactly one element from each of the equivalence classes. For any z on the circle, let z₀ be the point in A such that z₀ ∼ z. Let u(z) be the (unique!) integer n such that rotating z₀ counterclockwise around the circle by an angle of nx degrees yields z. Then for any z, if z′ is the result of rotating z′ by x degrees around the circle, then u(z′) = u(z) + 1 > u(z) and so we have (3).

"The whole is bigger than the part"

Some people don’t like Cantorian ways of comparing the sizes of sets because they want to have a “whole is bigger than the (proper) part” principle, denying which they consider to be counterintuitive.

Suppose that there is a relation ≤ which provides a way of comparing the sizes of sets of real numbers (or just the sizes of countable sets of real numbers) such that:

1. the comparison satisfies the “the whole is bigger than the part” principle, so that if A is a proper subset of B, then A < B

2. there are no incommensurable sets: given any A and B, at least one of A ≤ B and B ≤ A holds

3. the relation ≤ is transitive and reflexive.

Then the Banach-Tarski paradox follows from (a)–(c) without any use of the Axiom of Choice: there is a way to decompose a ball into a finite number of pieces and move them around to form two balls of the same size as the original. And Banach-Tarski feels like a direct violation of the "whole is bigger" principle!

Thus, intuitive as the “whole is bigger” principle is, the price of being able to compare the sizes of sets of real numbers in conformity with the principle is quite high. I suspect that most people who think that denying the “whole is bigger” principle also think Banach-Tarski is super problematic.

For our next observation, let’s add one more highly plausible condition:

4. the relation ≤ is weakly invariant under reflections of the real line: for any reflection ρ, we have A ≤ B if and only if ρA ≤ ρB.

Proposition: Conditions (a)–(d) are contradictory.

So, I think we should deny that, in the context of comparing the number of elements of a set, the whole is bigger than the proper part.

Proof of Proposition: Write A ∼ B iff A ≤ B and B ≤ A. Then I claim we have A ∼ ρA for any reflection ρ. For otherwise we either have A < ρA or ρA < A by (b). If we have A < ρA, then we also have ρA < ρ²A by (d), and since ρ²A = A, we have ρA < A, a contradiction. If we have ρA < A, then we have ρ²A < ρA by (d), and hence A < ρA, again a contradiction.

Since any translation τ can be made out of two reflections, it follows that A ∼ τA as well. Let τ be translation by one unit to the right. Then {0, 1, 2, ...} ∼ τ{0, 1, 2, ...} = {1, 2, 3, ...}, which contradicts (a).

A tension in some of my recent work

Here is a tension in some recent work of mine. In Chapter 6 of Infinity, Causation, and Paradox, I argue that (a) the Axiom of Choice for countable sets of reals (ACCR) is true, and (b) this version of the Axiom of Choice plus causal infinitism implies a nasty paradox, so we should accept causal finitism instead. The argument for ACCR makes use of the premise that mathematical entities exist necessarily. But in “Might All Infinities Be The Same Size?”, I argue that for all we know, some mathematical entities exist contingently. Thus, the latter paper undercuts the argument of Chapter 6 of the book.

Fortunately, the argument of Chapter 6 of the book looks like it might be fixable. The argument for ACCR proceeded as follows:

1. For any set of non-empty countable sets of reals, it is metaphysically possible that there is a choice function.

2. If possibly there is a choice function, then necessarily there is a choice function.

The argument for (1) is elaborate, but it is (2) that the considerations in my article block.

But we can try to proceed as follows. The paradox in Chapter 6 of the book requires a choice function for a particular collection of non-empty countable sets of reals (reals generatable by a certain infinitary coin-tossing process). By (1), there is a possible world w′ where that particular collection of sets does have a choice function. So it seems all we need to do is to run the paradox in w′, and we should be done.

There are probably other areas in Chapter 6 where some tweaking (or more than that!) is needed to make things work with mathematical contingentism, and hence my cautious wording.

Product spaces for hyperreal and full conditional probabilities

I think the following is a consequence of a hyperreal variant of the Horn-Tarski extension theorem for measures on boolean algebras:

Claim: Suppose that <Ω_i, F_i, P_i> for i ∈ I is a finitely additive probability space with values in some field R^* of hyperreals. Then, assuming the Axiom of Choice, there is a hyperreal-valued finitely additive probability space <Ω, 2^Ω, P> where Ω = ∏_i ∈ IΩ_i and where the Ω_i-valued random variables π_i given by the natural projections of Ω to Ω_i are independent and have the distributions given by the P_i.

Note that the values of P might be in a hyperreal field larger than R^*.

Given the Claim, and given the well-known correspondences between hyperreal-valued probabilities and full conditional real-valued probabilities, it follows that we can define meaningful product-space conditional real-valued probabilities.

It would be really nice if the product-space conditional probabilities were unique in the special case where F_i is the power set of Ω_i, or at least if they were close enough to uniqueness to define the same real-valued conditional probabilities.

For a particularly interesting case, consider the case where X and Y are generated by uniform throws of a dart at the interval [0, 1], and we have a regular finitely additive hyperreal-valued probability on [0, 1] (regular meaning that all non-empty sets have positive measure). Let Z be the point (X, Y) in the unit square.

Looking at how the proof of the Horn-Tarski extension theorem works, it seems to me that for any positive real number r, and any non-trivial line segment L along the x = y diagonal in the square [0, 1]², there is a product measure P satisfying the conditions of the Claim (where P₁ and P₂ are the uniform measures on [0, 1]) such that P(L)=rP(H), where H is the horizontal line segment {(x, 0):x ∈ [0, 1]}. For instance, if L is the full diagonal, we would intuitively expect P(L)=2^1/2P(H), but in fact we can make P(L)=100000P(H) or P(L)=P(H)/100000 if we like. It is clear that such a discrepancy will generate different conditional probabilities.

I haven’t checked all the details yet, so this could be all wrong.

But if it is right, here is a philosophical upshot. We would expect there to be a unique canonical product probability for independent random variables. However, if we insist on probabilities that are so fine-grained as to tell infinitesimal differences apart, then we do not at present have any such unique canonical product probability. If we are to have one, we need some condition going beyond independence.

This is part of a larger set of claims, namely that we do not at present have a clear notion of what “uniform probability” means once we make our probabilities more finegrained than classical real-valued probability.

Putative Sketch of Proof of Claim: Embedding R^* in a larger field if necessary, we may assume that R^* is |2^Ω|-saturated. Define a product measure on the cylinder subsets of Ω as usual. The proof of the Horn-Tarski extension theorem for measures on boolean algebras looks to me like it works for |B|-saturated hyperreal-valued probability measures where B is the boolean algebra, and completes the proof of our claim.

Something that has no reasonable numerical epistemic probability

I think I can give an example of something that has no reasonable (numerical) epistemic probability.

Consider Goedel’s Axiom of Constructibility. Goedel proved that if the Zermelo-Fraenkel (ZF) axioms are consistent, they are also consistent with Constructibility (C). We don’t have any strong arguments against C.

Now, either we have a reasonable epistemic probability for C or we don’t.

If we don’t, here is my example of something that has no reasonable epistemic probability: C.

If we do, then note that Goedel showed that ZF + C implies the Axiom of Choice, and hence implies the existence of non-measurable sets. Moreover, C implies that there is a well-ordering W on the universe of all sets that is explicitly definable in the language of set theory.

Now consider some physical quantity Q where we know that Q lies in some interval [x − δ, x + δ], but we have no more precise knowledge. If C is true, let U be the W-smallest non-measurable subset of [x − δ, x + δ].

Assuming that we do have a reasonable epistemic probability for C, here is my example of something that has no reasonable epistemic probability: C is false or Q is a member of U.

A really weird place in conceptual space regarding infinity

Here’s a super-weird philosophy of infinity idea. Maybe:

1. The countable Axiom of Choice is false,

2. There are sets that are infinite but not Dedekind infinite, and

3. You cannot have an actual Dedekind infinity of things, but

4. You can have an actual non-Dedekind infinity of things.

If this were true, you could have actual infinites, but you couldn’t have Hilbert’s Hotel.

Background: A set is Dedekind-infinite if and only if it is the same cardinality as a proper subset of itself. Given the countable Axiom of Choice, one can prove that every infinite set is Dedekind infinite. But we need some version of the Axiom of Choice for the proof (assuming ZF set theory is consistent). So without the Axiom of Choice, there might be infinite but not Dedekind-infinite sets (call them “non-Dedekind infinite”). Hilbert’s Hotel depends on the fact that its rooms form a Dedekind infinity. But a non-Dedekind infinity would necessarily escape the paradox.

Granted, this is crazy. But for the sake of technical precision, it’s worth noting that the move from the impossibility of Hilbert’s Hotel to the impossibility of an actual infinite depends on further assumptions, such as the countable Axiom of Choice or some assumption about how if actual Dedekind infinities are impossible, non-Dedekind ones are as well. These further assumption are pretty plausible, so this is just a very minor point.

I think the same technical issue affects the arguments in my Infinity, Causation and Paradox book (coming out in August, I just heard). In the book I pretty freely use the countable Axiom of Choice anyway.

Non-measurable sets and intuition

Here’s an interesting reason to accept the existence of non-measurable sets (and hence of whatever weak version of the Axiom of Choice that it depends on). A basic family of mathematical results in analysis says that most measurable real-valued functions on the real line are “close to” being continuous, i.e., that they can be approximated by continuous functions in some appropriate sense. But it is intuitive to think that there “should” be real-valued functions on the real line that are not close to being continuous—there “should” be functions that are very, very messy. So, intuitively, there should be non-measurable functions, and hence non-measurable sets.

Coin placing algorithms

Consider algorithms for sequentially placing a coin each day either in a heads or a tails configuration depending on how coins were placed on past days. For instance, the rule might say that if you placed heads yesterday, today you place tails, and if yesterday you placed tails, this time you place heads. The algorithm might depend on the date, too: maybe on Wednesdays you place heads if and only if you placed tails last Wednesday, but on all other days of the week you place heads.

Here's an interesting question about a coin-placing algorithm: Is it mathematically coherent to suppose that the algorithm had been running from eternity? For some algorithms, the answer is positive. Both of the algorithms I described above have that property. But not all algorithms are like that. For instance, here's an algorithm based on a comment by Ian: if infinitely many heads have been placed, place tails; otherwise, place heads. This algorithm could not have been running from eternity. [Proof: For suppose it was. Then either it would have placed infinitely many heads or not. Suppose it placed infinitely many heads up to today. Suppose that on some day n the last of the heads was placed. Then prior to day n there would have been infinitely many heads (since from that day to today only one heads was placed, namely on day n, as day n was the latest heads day), and so on day n tails was placed, which is a contradiction. So the algorithm would have placed only finitely many heads. But then prior to each day there would have been only finitely many tails, and so each day a heads should have been placed, whereas only finitely many were placed, so again we have a contradiction.]

Now here's a fun fact:

Theorem: If the algorithm only needs to check a finite number of past placements to determine a given day's placement, then there is a sequence of coin placements that goes back infinitely many days that fits with the algorithm.

In Ian's algorithm, the placement on each day of course depends on infinitely many past placements. [I find it moderately surprising that the proof doesn't use the Axiom of Choice. Basically, you generate first a sequence of finite sequences of heads or tails with the property that the sequence could be generated by applying the algorithm a finite number of times to some pre-given backwards-infinite sequence, and that the sequence is the alphabetically the smallest sequence (heads=H and tails=T) if we write right-to-left that has this property. Then we're guaranteed convergence in at any particular distance from the end of this sequence as the length goes to infinity. The result generalizes to any finite alphabet, not just heads/tails.]

So what? Maybe nothing much. Still, it's an interesting difference between the finite and the infinite: it's always mathematically coherent to suppose algorithms with finite memory for history that ran for eternity but not always mathematically coherent to have algorithms ones that look infinitely far back that have done so. (Causal finitism, however, rules out both kinds. I wonder if that's a count against causal finitism? If so, not much of one, since metaphysical possibility implies mathematical coherence but not conversely.)

Cardinality and worlds

For every initial ordinal k, there is a possible world with exactly k photons. But there is no set of all initial ordinals (proof: suppose there is such a set; the union of the members of any set of ordinals is an ordinal; so the union of the initial ordinals is an ordinal; it must have the same cardinality as some initial ordinal in the set; but for any ordinal in the set, there is a larger one in the set). So there is no set of all possible worlds.

This argument doesn't use the Axiom of Choice and hence it improves on the argument I gave here.

Coin guessing using past data, once again

In my previous post, I showed that given a backwards infinite sequence of coin tosses, there is a simple strategy leveraging data about infinitely many past coin flips that guarantees that you guessed correctly infinitely often. I then suggested that this supports the idea that one can't leverage an infinite amount of past data, and that in turn supports causal finitism--the denial of the possibility of infinite causal histories. But there is a gap in that argument: Maybe there is some strategy that guarantees infinitely many correct guesses that doesn't require the guesser to make use of data about infinitely many past coin flips. If so, then the paradox doesn't have much to do with infinite amounts of data.

Fortunately for me, that gap can be filled (modulo the Axiom of Choice). Given the Axiom of Choice, it's a theorem that there is no strategy leveraging merely a finite amount of past data at each step that guarantees getting any guesses right. In other words, for every strategy that leverages a finite amount of past data, there is a sequence of coin flips such that that sequence would result in the guesser getting every guess wrong. The proof uses the Compactness Theorem for First-Order Logic.

Another impossibility result for finitely additive probabilities and invariance

Consider a countably infinite sequence of fair and independent coin tosses. Given the Axiom of Choice, there is no finitely additive probability measure that satisfies these conditions:

1. It is defined for all sets of outcomes.
2. It agrees with the classical probabilities where these are defined.
3. It is invariant under permutations of coins.

(Sketch of proof: Index the coins with members of the free group of rank two. The members of the group then induce permutations of coins, and hence act on the space of outcomes. The set of non-trivial fixed points under that action has classical probability zero. Throwing that out, we can use a standard paradoxical decomposition of the free group of rank two to generate a paradoxical decomposition of the rest of our space of results--here Choice will be used--and that rules out the possibility of a finitely additive probability measure.)

An aesthetic argument for the Axiom of Choice

The mathematics that supposes the Axiom of Choice is more beautiful than the mathematics that does not. So, the Axiom of Choice is probably true.

An Axiom of Choice strong enough to puzzle

All the main puzzles that follow from the Axiom of Choice (AC)--nonmeasurable sets, Banach-Taski and guessing future coin tosses--need only a weaker version of AC. One weaker version that suffices is this:

(*) There is a choice function for any partition of the interval (0,1) into non-empty countable sets.

Now imagine worlds with point-sized particles that never move, but can perish and come into existence. The world starts at time 0. Each particle has a lifetime between 0 and 1, exclusive. Some locations in the world are never occupied by a particle. Call these "vacant". At all other locations, a particle comes into existence at time 0. Two particles never occupy the same location at the same time. Call such worlds p-worlds.
For each non-vacant location x in a p-world w, there is an associated set L(w,x) of numbers in (0,1), where a number y is in L(w,x) iff some particle at x has lifetime of length y. I now need a crucial metaphysical plenitude assumption:

(**) For any set S such that (a) every member of S is a countable non-empty collection of members of (0,1) and (b) the cardinality of S is at most that of the continuum, there is a p-world w such for each A in S there is a unique location x in w such that L(w,x)=A.

In other words, any set S satisfying (a) and (b) is the set of sets of lifetime lengths for non-vacant locations in some p-world, without duplication.

Given the plenitude assumption, I get the version of AC needed for the paradoxes. For given a partition S of (0,1) into countable sets, there will be a p-world as in (**). Given a member A of S, there will be a unique location x such that L(w,x)=A. Let f(A) be the lifetime of the first particle at x in w. This is our choice function.

So the major paradoxes of AC follow from a plausible plenitude assumption about possible worlds.