Posts Tagged ‘Axiom of Choice’


Supertask decision making

December 2, 2008

I have a little paper writing up the supertask puzzle I posted recently. I’ve added a second puzzle that demonstrates the same problem, but doesn’t use the axiom of choice (it’s basically just a version of Yablo’s paradox), and I’ve framed the puzzles in terms of failures of the deontic Barcan formulae.

Anyway – if anyone has any comments, I’d be very grateful to hear them!


A Paradox of Choice

November 19, 2008

I’ve been thinking about variations on the coin tossing puzzle I posted about a month or so back. This is one I find particularly weird, and seems to violate principles of free choice. You can have a two player game where both players have a winning strategy, but only one player can win. In particular, this implies that if one player follows her winning strategy, the other player can’t. So, although at every point in the game the second player is free to follow the strategy, she is not free to follow the strategy at every point in the game. (I intend there to be some kind of scope difference there.)

The games I am interested in are defined as follows. First I shall define a round: player one chooses 1 or 0, then player two chooses 1 or 0 (having heard player one’s choice.) Player one wins if player two chooses the same number as he did, player two wins if her number is different. Next, a game is a sequence of rounds. Player 2 wins if she wins every round, player 1 wins otherwise.

A strategy for one of these games is a function taking sequences of 1’s and 0’s (provided the order type of the sequences are initial segments of the game order type) to {0, 1}. A winning strategy for a player is a strategy \sigma, such that, if at each point in the game, s, you played \sigma(s) then you would win.

Now clearly player one does not have a winning strategy for any game that is a finite sequence of rounds – and indeed, this holds for any game that is a well founded sequences of rounds. Obviously, player two has a winning strategy, since she may always say the opposite to what player one says. Since on well founded games, only one player can have a winning strategy, player one never has a winning strategy.

Bizarrely, however, player on does have winning strategies on non-well founded games. Suppose they play on a backwards omega sequence, e.g. a move takes place at each 1/n hours past 12pm, and the game ends at 1pm. Then you divide the possible sequences that player two might play into equivalence classes according to whether they differ by at most finitely many moves. If player one picks a representative from each class, then at each point in the game he can work out what class he’s in, and he can play the same move that the representative sequence predicts player two will play. At the end he must have won all but finitely many moves (I discussed the strategy a bit more here.

So both player one and player two have a winning strategy. But clearly, they can’t both win – so it follows that at least one of them can’t follow their strategy in a given game. This is particularly weird, since at each point in the game they are free to follow their strategy – there’s nothing physically preventing them from them from doing so – but they are not free to to follow it at all of the moves.

This contradicts what I shall call the ‘free choice principle’, that if a rational agent is free and able to do something, and wants to do it, she will do it. For the game above we can formulate this as follows. Let \Diamond_i be read roughly as ‘player i (i = 1 or 0) is free to make it the case that’, and let P_in say ‘at round n, player i (i=1 or 0) follows his/her strategy’. Round n is the n’th round from the end of the game. The free choice principle reads:

  • \forall n (\Diamond_i P_in \rightarrow P_in)

If at a given round each player is free to follow their strategy, then each player does follow their strategy. We assume tacitly that the players we are concerned with want to follow their strategy, and are physically able to carry it out, etc… We may formulate the principle that at each point in the game, both players are free to follow their strategy as follows

  • \forall n\Diamond_i P_in

But this entails the impossible conclusion: \forall n (P_1n \wedge P_2n). At least one player has to lose.

As far as I can see, the premise that at each point in the game each player is free to play according to her strategy is fine. It’s been stipulated that nothing is preventing them from following the strategy, and there are no other relevant limitations.

So it has to be the principle of free choice that goes. There will be a round such that one of the two perfectly rational players wants to follow her strategy, intends to follow it, can follow it in the sense that nothing is preventing her, yet doesn’t follow it. Strange.


Help! My credences are unmeasurable!

September 29, 2008

This is a brief follow up to the puzzle I posted a few days ago, and Kenny’s very insightful post and the comments to his post, where he answers a lot of the pressing questions to do with the probability and measurability of various events.

What I want to do here is just note a few probabilistic principles that get violated when you have unmeasurable credences (mostly a summary of what Kenny showed in the comments), and then say a few words about the use of the axiom of choice.

Reflection. Bas van Fraassens’ reflection principle states, informally, that if you are certain that your future credence in p will be x, then your current credence in p should be x (ignoring situations where you’re certain you’ll have a cognitive mishap, and the problems to do with self locating propositions.) If pn says “I will guess the n’th coin toss from the end correctly”, then Kenny shows, assuming translation invariance (that Cr(p)=Cr(q) if p can be gotten from q by uniformly flipping the values of tosses indexed by a fixed set of naturals for each sequence in q) that once we have chosen a strategy, but before the coins are flipped, there will be an n such that Cr(pn) will be unmeasurable (so fix n to be as such from now on.) However, given reasonable assumptions, no matter how the coins land before n, once you have learned that the coins have landed in such and such a way, Cr(pn)=1/2. Thus you may be certain that you will have credence 1/2 in pn even though you’re credence in pn is currently unmeasurable.

Conglomerability. This says that if you have some propositions, S, which are pairwise incompatible, but jointly exhaust the space, then if your credence in p conditional on each element of S is in an interval [a, b], then your unconditional credence in p should be in that interval. Kenny points out that conglomerability, as stated, is violated here too. The unconditional probability of pn is unmeasurable, but the conditional probability of pn on the outcome of each possible sequence up to n, is 1/2. (In this case, it is perhaps best to think of the conditional credence as what you’re credence would be after you have learned the outcome of the sequence up to n.) You can generate similar puzzles in more familiar settings. For example what should your credence be that a dart thrown at the real line will hit the Vitali set? Presumably it should be unmeasurable. However, conditional on each of the propositions \mathbb{Q}+\alpha, \alpha \in \mathbb{R}, which partition the reals, the probability should be zero – the probability of hitting exactly one point from countably many.

The Principal Principle. States, informally, that if you’re certain that the objective chance of p is x, then you should set your credence to x (provided you don’t have any ‘inadmissible’ evidence concerning p.) Intuitively, chances of simple physical scenarios like pn shouldn’t be unmeasurable. This turns out to be not so obvious. It is first worth noting that the argument that your credence in pn is unmeasurable doesn’t apply to the chance of pn, because there are physically possible worlds that are doxastically impossible for you (i.e. worlds where you don’t follow the chosen strategy at guess n.) Secondly, although the chance in a proposition can change over time, so it could technically be unmeasurable before any coin tosses, but 1/2 before the nth coin toss, the way that chances evolve is governed by the physics of the situation — the Schrodinger equation, or what have you. In the example we described we said nothing about the physics, but even so, it does seem like we can consistently stipulate that the chance of pn remains constant at 1/2. In such a scenario we would have a violation of the principal principle – before the tosses you can be certain that the chance of pn is 1/2, but your credence in pn is unmeasurable. (Of course, one could just take this to mean you can’t really be certain you’re going to follow a given strategy in a chancy universe – some things are beyond your control.)

Anyway, after telling some people this puzzle, and the related hats puzzle, a lot of people seemed to think that it was the axiom of choice that’s at fault. To evaluate that claim requires a lot of care, I think.

Usually to say the Axiom of Choice is false, is to say that there are sets which cannot be well ordered, or something equivalent. And presumably this depends on which structure accurately fits the extension of sethood and membership, the extension of which is partially determined by the linguistic practices of set theorists (much like ‘arthritis’ and ‘beech’, the extension of ‘membership’ cannot be primarily determined by usage of the ordinary man on the street.) After all there are many structures that satisfy even the relatively sophisticated axioms of first order ZF, only some of which satisfy the axiom of choice.

If it is this question that is being asked, then the answer is almost certainly: yes, the axiom of choice is true. The structure with which set theorists, and more generally mathematicians, are concerned with is one in which choice is true. (It’d be interesting to do a survey, but I think it is common practice in mathematics not to even mention that you’ve used choice in a proof. Note, it is a different question whether mathematicians think the axiom of choice is true – I’ve found often, especially when they realise they’re talking to a “philosophy” student, they’ll be suddenly become formalists.)

But I find it very hard to see how this answer has *any* bearing on the puzzle here. What structure best fits mathematical practice seems to have no implications whatsoever on whether it is possible for an idealised agent to adopt a certain strategy. This has rather to do with the nature of possibility, not sets. What possible scenarios are concretely realisable? For example, can there be a concretely realised agent whose mental state encodes the choice function on the relevant partition of sequences? (Where a choice function here needn’t be a set, but rather, quite literally, a physical arrangement of concrete objects.) Or another example: imagine a world with some number of epochs. In each epoch there is some number of people – all of them wearing green shirts. Is it possible that exactly one person in each epoch wears a red shirt instead? Surely the answer is yes, whether any person wears a red shirt or not is logically independent of whether the other people in the epoch wear a red shirt. A similar possibility can be guaranteed by Lewis’s principle of recombination – it is possible to arbitrarily delete bits of worlds. If so, it should be possible that exactly one of these people exists in each epoch. Or, suppose you have two collection of objects, A and B. Is it possible to physically arrange these objects into pairs such that either every A-thing is in one of the pairs, or every B-thing is in one of the pairs. Providing that there are possible worlds are large enough to contain big sets, it seems the answer again is yes. However, all of these modal claims correspond to some kind of choice principle.

Perhaps you’ll disagree about whether all of these scenarios are metaphysically possible. For example, can there be spacetimes large enough to contain all these objects? I think there is a natural class of spacetimes that can contain arbitrarily many objects – those constructed from ‘long lines’ (if \alpha is an ordinal, a long line is \alpha \times [0, 1) under the lexigraphic ordering, which behaves much like the positive reals, and can be used to construct large equivalents of \mathbb{R}^4.) Another route of justification might be the principle that if a proposition is mathematically consistent, in that it is true in some mathematical structure, that structure should have a metaphysically possible isomorph. Since Choice is certainly regarded to be mathematically consistent, if not true, one might have thought that the modal principles to get the puzzle of the ground should hold.