Talk:Axiom of determinacy

From Wikipedia, the free encyclopedia

I just dropped a passage on infinite logic and the axiom of determinacy. The particular version of infinite logic in which this can be done I'm not sure of. One exists obviously but it may be inconsistent. This is just because the axiom of determinacy may be inconsistent. Barnaby dawson 17:54, 24 Oct 2004 (UTC)

Cool, thanks for your additions! -- Schnee 20:34, 24 Oct 2004 (UTC)

[edit] Independence of independence from ZF

The article says:

It is also conceivable that the independence of AD is independent (i.e in some models of ZF you can resolve AD and in some you cannot).

Is that actually possible? -- Schnee 15:46, 31 Oct 2004 (UTC)

Yes it's possible that a model of ZF has non-standard integers that code for proofs that can't be expressed as normal integers. So a proof of AD's consistancy may require a non-standard integer and so depend on the model of ZF we're in (This would make the independence of AD independent). I don't think that current thinking rules this out as a possibility. It's weird isn't it :) Barnaby dawson 21:14, 31 Oct 2004 (UTC)

Yeah, and I'm not sure I understand that actually (which may be due to the fact that I'm an undergraduate who's only heard a few lectures about axiomatic set theory and the like - despite having an interest in these things, I'm really just a mathematical layman). I mean... if you consider all models of ZF (assuming that there are any at all ^_~), then you can divide them into two classes - those in which AD holds and those in which it doesn't. If one of those classes is empty, then by Gödel's completeness theorem, it follows that ZF implies AD or -AD (depending on which of them is empty). If neither is, then AD is independent of ZF. Or am I making a mistake here somewhere?

And also, different models of ZF with integers that fundamentally differ from those in other models shouldn't play a role here really; as long as the rules of deduction that you use for proofs (and that actually define just what formal proving is) don't change, what can and cannot be proven shouldn't change.

-- Schnee 21:56, 31 Oct 2004 (UTC)

The text contains: "The axiom of determinacy is independent of ZF (assuming that ZF is consistent); it does not follow from ZF (since AC is independent of ZF), but it is possible to construct models of ZF where AD holds (cf. Jech, Set theory)."

Two of these statements are false. Assuming consistency of ZF the axiom of determinacy cannot be proved to be independent of ZF (in ZF). This is because ZF+AD is eqiconsistent with ZF+"There exist infinitely many woodin cardinals". This implies the consistency of ZF. If ZF implied consistency of ZF+"infinitely many woodin cardinals" then ZF+"There exist infinitely many woodin cardinals" would imply its own consistency and would therefore be inconsistent. It is not possible to construct models of ZF where AD holds without futher large cardinal axioms. In fact (Jech, set theory) makes this point. As such I'm correcting the text. Barnaby dawson 12:26, 7 Nov 2004 (UTC)

OK, thanks. I don't actually had the Jech book for a reference myself; I was merely given this information by someone else. Goes to show you should only trust those claims you made up yourself, I guess. ;) -- Schnee 13:01, 7 Nov 2004 (UTC)

[edit] Notes on needed improvements

(mostly notes to myself, but everyone can see what I'm thinking and argue with me/do it first).

It is possible that the axiom of determinacy can be proved false without the use of the axiom of choice.

The above is true in some formal sense; not a serious possibility. It's also true in some formal sense that it's possible PA can prove 0=1.

It's not the same at all. It is quite possible that the Axiom of determinacy is false. And postulating the consistency of the axiom of determinacy it isn't at all like postulating the consistency of PA. We can't get the consistency of the axiom of determinacy without postulating very large cardinals which are also suspect. Barnaby dawson 14:40, 11 July 2005 (UTC)

The large cardinals are not really that suspect, these days. AD is of course definitely false, not just possibly, because AC is true, but it's not a significant possibility that AD is inconsistent with ZF.--Trovatore 16:03, 11 July 2005 (UTC)

We might state that this is the view of most mathematicians working in set theory but the quoted sentence should remain. Barnaby dawson 17:18, 11 July 2005 (UTC)

Perhaps neutral language would say something like "It is not possible to prove in ZF that ZF is consistent with AD", without comment on whether this outcome is philosophically "possible" --Trovatore 17:33, 11 July 2005 (UTC)

Yup. Done. Barnaby dawson 21:01, 11 July 2005 (UTC)

Need section on consequences of AD. The blurb about AD implying measurability and p.o.B for sets of reals is not prominent enough, and lots of things are left out.

Need section on fragments of AD that follow from large cardinals.

This will now be in Determinacy#Determinacy_and_large_cardinals; no need to duplicate it here.

--Trovatore 17:16, 3 September 2005 (UTC)

Proof that AC==>~AD -- maybe move to WikiProofs?

Again I disagree. It might be better to put a more intuitive proof. But this proof is pretty vital to the article. AD is non standard (although important) and that should be clear. Barnaby dawson 14:40, 11 July 2005 (UTC)

Well, it's just a bit long. The fact that AD is inconsistent with AC follows directly from the facts mentioned elsewhere about AD implying regularity properties for sets of reals. That would leave more room to (i) define games better, (ii) say more about where AD fits in the scheme of things, and (iii) more about its consequences, without making the article too long and unfocused.--Trovatore 16:03, 11 July 2005 (UTC)

Update: (i), (ii), and some of (iii), will now be handled in Determinacy. For thoughts on aspects of (iii) that should still be handled in Axiom of determinacy, see #Additions still needed to this article below. --Trovatore 17:16, 3 September 2005 (UTC)

I think an elementary proof is much more appropriate on wikipedia. I know one involving an intuitive and simple game. I may work on that later this week. Barnaby dawson 17:18, 11 July 2005 (UTC)

I think we can afford to make this article significantly longer without any trouble. I agree with points (i), (ii) and (iii) although sadly I don't yet know enough to help out much (I could help out with (i)).

By the way I can't seem to find this wikiproofs that you speak of. Doesn't turn up on google. I can find the meta discussion page concerning it though. Looks like a great idea I should add. Barnaby dawson 21:01, 11 July 2005 (UTC)

Definition of AD is not entirely clear -- an example of a "two-player game of perfect information of length ω" should be given.

Update: See Determinacy#Basic notions for this. Perhaps not necessary to duplicate that content in this article. --Trovatore 17:16, 3 September 2005 (UTC)

References are a bit quirky; Jech is the only standard ref. Give some others. --Trovatore 07:09, 11 July 2005 (UTC)

Update: this is better now. --Trovatore 17:16, 3 September 2005 (UTC)

[edit] New Determinacy article

I've written (well, started) a new Determinacy article, intended to be the central reference point for the new Category:Determinacy, that treats determinacy in a more general context than just the axiom of determinacy. It is not intended to supplant this article, but to complement it. However it's possible that there's some content in Axiom of determinacy that really belongs in Determinacy, now that it exists -- I'll think about this later. Maybe. --Trovatore 05:15, 2 September 2005 (UTC)

Actually, I don't think any content needs to be moved out of Axiom of determinacy. The "types of games that are determined" content will probably be redundantly treated in Determinacy, but it's short and has expository value, so it's OK where it is. Mainly there's content that I thought needed to be added to Axiom of determinacy, that now ought to go in Determinacy instead. --Trovatore 05:19, 2 September 2005 (UTC)

[edit] Additions still needed to this article

A list of a few things that come to mind that still need to be added, and belong in this article, not in the little Axiom of determinacy subsection of the Determinacy article. (That subsection isn't written yet, but is expected to say what AD is, that it is provably false from ZFC, that it's true in L(R) (assuming large cardinals), and then point to this article for more detailed information).

1. Consequences of AD for the alephs (e.g. ℵ₁ and ℵ₂ are measurable, ℵ_n for finite n≥3 are all singular with cofinality ℵ₂.
2. Nonexistence of an uncountable wellordered sequence of distinct reals, or even distinct countable sets of reals.
3. The coding lemma (should probably have its own article, but there should be a blurb here).
4. The projective ordinals, such as δ¹₃ (idem).
5. Models of AD, beyond L(R).

--Trovatore 16:45, 3 September 2005 (UTC)

[edit] Template:Technical

Okay, I don't understand this article. At all. In fact, I don't think I understand a single sentence beyond the first. Of course, I'm a layman, so I can't expect to understand it fully without some set theory courses (unless it's a bit more basic than I think), but I could at least have some idea of a) what it implies for easily-understandable concepts, b) what direct or indirect practical applications it may have, and c) how important it is in its field, probably in addition to at least some other stuff. Surely this concept is no more advanced than, say, quantum chromodynamics (at least the latter has a much fancier name ;)), but the latter has an introduction that's mostly understandable to high-school graduates. —Simetrical (talk) 03:25, 26 December 2005 (UTC)

You must have gone to an unusual high school, but yes, I agree that this article could use a better intro (and not just from an accessibility point of view). Take a look at Determinacy#Basic notions and see if that helps any, and if there's anything from there you think might be imported to this article. --Trovatore 21:42, 28 December 2005 (UTC)

[edit] Choice

Is there something known about what weaker forms of AC are consistent with AD? I would really like to see wether DC or something even stronger is compatible with AD or not, or is it undecidable that it is undecidable to decide? XD Scineram 15:48, 1 September 2006 (UTC)

Yes, Kechris proved that: if AD holds, then AD+DC holds in L(R). It is not easy. Kope 16:27, 1 September 2006 (UTC)

[edit] Why AC contradicts the AD

In the point 2 of that paragraph it is stated: "The set of possible outcomes of this strategy which we have already decided on has cardinality less than the continuum. (By choice of well ordering and the fact that we only decide on one outcome per strategy)"

If the outcome of the strategy considered actually depends upon what the other player does at infinitely many points in the game, then I understand that the cardinality of possible outcomes of the strategy considered will be equal to continuum. Correct me if I am wrong. -- Leocat 17:55, 29 October 2006 (UTC)

No, you're right. But the proof is also right, just a bit unclearly written, I think. The set asserted to have cardinality less than c is "the set of possible outcomes of this strategy which we have already decided on". Here to "decide on" an outcome means to decide which player wins that outcome.

The language of the proof clearly needs a cleanup. Once you've followed the proof, maybe you'd volunteer to clean it up; you would know what parts of it were unclear to you on a first reading, which should give you a leg up. --Trovatore 19:26, 29 October 2006 (UTC)

I still see the cardinality of possible outcomes of the strategy that we have decided on as continuum, if the outcome depends upon what the other player does at infinitely many points in the game. -- Leocat 21:26, 29 October 2006 (UTC)

You're getting hung up on "possible outcomes" whereas you should be focusing on "what we have decided". We're taking the strategies one at a time, in order type c. So for example if c is , then at any given stage of the iteration, we have thus far made only (at most) decisions, and each of these decisions assigns the winner for only one outcome. But there are, as you correctly observe, possible outcomes consistent with the strategy we're currently considering. That's how we know there's an outcome (consistent with the strategy being considered) to which we haven't currently assigned a winner. We assign a winner in such a way that the strategy being considered loses, and move on.

When we get to the end, we've refuted all possible strategies. Therefore there is no winning strategy for the game, for either player, and thus AD is false. --Trovatore 06:03, 30 October 2006 (UTC)

Let the players be Alice and Bob. For each of Alice's strategies, we choose a sequence of moves by Bob which leads to an outcome (one of the continuum many) which has not yet been decided. Then we decide that in favor of Bob. Consequently, that strategy of Alice's will not be a winning strategy. Similarly, for each of Bob's strategies, we pick a sequence of moves for Alice which lead to an as yet undetermined outcome. We decide that outcome in favor of Alice. Thus Bob's strategy is not a winning strategy. Since neither player has a winning strategy, the game is not determined. Got it? JRSpriggs 08:28, 30 October 2006 (UTC)

A set A of sequences is determined if there exists an absolutely winning strategy for one of the players, say for Alice. The question is not what happens when Alice does not follow the winning strategy. If she does, then you cannot choose a sequence of moves by Bob to make him win. -- Leocat 19:59, 31 October 2006 (UTC)

Not sure I take your point. The idea of the proof is to construct such a set A, for which there is no winning strategy. This is done by making sure that, for any strategy Alice might try, there's a play by Bob that defeats it, and mutatis mutandis. --Trovatore 20:17, 31 October 2006 (UTC)

To Leocat: You seem to be assuming that we are given a fixed game. On the contrary, to disprove the axiom of determinacy, we are using the axiom of choice to help us "construct" a game which is not determined. The only difficulty in the construction is the possibility that, when trying to defeat Alice's strategies, we might run out of sequences of moves for Bob; or, when trying to defeat Bob's strategies, we might run out of sequences of moves for Alice. We can use the axiom of choice to order the strategies and outcomes in a way that allows us to avoid running out. JRSpriggs 10:18, 1 November 2006 (UTC)

[edit] part 2

To JRSpriggs: You "refute" each strategy, but this refutation is only conditional - you have to specify countably many further conditions to make Alice win or lose. When all of these conditions are specified, it may turn out that one of the "refuted" strategies is a winning strategy. -- Leocat 10:31, 1 November 2006 (UTC)

See Determinacy#Winning strategies. You do not appear to understand what is meant by "strategy". A strategy for Alice is a function from the set of all possible finite sequences of moves by Bob to Alice's next move following the last move in that sequence. So given a strategy for Alice and an ω-sequence of moves by Bob, we get the entire play of the game, i.e. all the moves of Alice and Bob. There is nothing left to do, but decide who won. There are no "further conditions" to specify. JRSpriggs 11:47, 1 November 2006 (UTC)

I have no problem with the concept of strategy. The statement: "If you give me a strategy S then we considered that strategy at some time t = t(S)" is the source of misunderstanding. It should be stated that the "time axis" here is the long line whose length is continuum. -- Leocat 18:57, 1 November 2006 (UTC)

There are two different notions of time here, which may be causing confusion. One notion is the time in the play of the game: Alice's first move, Bob's first move, Alice's second move, Bob's second move, etc.. This time may be indexed by natural numbers. The other notion of time is a stage in the construction of the game: deciding an outcome to refute Alice's first strategy, deciding an outcome to defeat Bob's first strategy, deciding an outcome to refute Alice's second strategy, etc.. This time may be indexed by ordinals less than the initial ordinal of the continuum. The sentence you quoted refers to this second notion of time. JRSpriggs 07:41, 2 November 2006 (UTC)

I claim that the AD is simply false and can be disproved without AC, so it does not matter that you can construct a proof that uses AC. Let Bob have an almost-winning strategy SB0 which simply produces the sequence of zeros. Let it win against every Alice's strategy except SA0 which can consist in producing a sequence containing all prime numbers. Let SA0 lose against SB1 (which can be producing a sequence containing all powers of 2) and let SB1 lose in all other cases. This simple procedure defines a game that is not determined. -- Leocat 17:55, 3 November 2006 (UTC)

I'm not sure what the game is, that you claim to have defined. What we know is that

ALICE  a0  a1  a2  a3  ...
BOB       0   0   0   0 ...

is a win for Bob, no matter what a0, a1, a2... are, except for the single case

ALICE  2   3   5   7  ...
BOB      0   0   0   0 ...

which is a win for Alice. Also we know that

ALICE  2    3   5    7  ...
BOB      1    2   4    8 ...

is a win for Bob. But to know what the game is we need to know who wins an arbitrary outcome, and you haven't told us who wins anything that doesn't fit into one of the above three cases. --Trovatore 18:21, 3 November 2006 (UTC)

Oh, I guess you have given one further piece of information, which is that

ALICE  a0    a1   a2    a3  ...
BOB       1     2    4    8 ...

is always a win for Alice, except in the third case above. We're still not close to defining a game. --Trovatore 18:23, 3 November 2006 (UTC)

You are right. I will take another look at the proof. -- Leocat 18:56, 3 November 2006 (UTC)

I think you should consider all pairs of strategies and make sure that for every strategy there is one that wins against it. This is not very clear from the presented proof. Also, the statement in point 2 about cardinality is false in all cases of strategies that actually depend upon what the other player does at infinitely many points. -- Leocat 19:28, 3 November 2006 (UTC)

[edit] Leocat's latest changes

Hi Leocat,

I appreciate that you're trying to improve the proof, which has been in need of it for quite some time. But your latest changes are problematic as they stand.

• First of all, there's no need to iterate through pairs of strategies. Given a strategy for (say) Alice, all you need to find is one play by Bob that beats it. There's no need to consider all of Bob's possible strategies.
• Also, it's not clear what you mean by

3. Decide that this sequence belongs to A, i.e. s1(T) won against s2(T).

• The problem is that you may already have decided that the sequence is not in A. That's because the same sequence may have been generated by two different strategies, already considered earlier.
• Finally, I think the "two notions of time" thing is confusing. I would just avoid talking about "time" entirely. To the extent that I do think of it in terms of "time", I would consider the individual plays of the game to be instantaneous—we aren't really considering anything happening sequentially within an individual game. --Trovatore 06:52, 7 November 2006 (UTC)

1) There is a need to consider all of Bob's strategies, because we have to make sure that every Bob's strategy will lose against a properly chosen strategy of Alice and vice versa. 2) I think you are right that a given sequence may have been already generated by a different pair of strategies and then it would have been already decided whether it belongs to A or not. I do not see a solution of this problem at the moment. -- Leocat 18:43, 7 November 2006 (UTC)

1. Yes, you do have to consider every strategy of Bob's. But you don't have to consider all pairs of strategies for Alice and strategies for Bob. It's enough to alternate between strategies for Alice and strategies for Bob, making sure you refute each such individual strategy. Pairs of strategies never come up.
2. The proof you modified had a correct solution to this, though it was admittedly not very clearly worded. I think you should go back and look at it and figure out what it was saying. --Trovatore 18:57, 7 November 2006 (UTC)

What are closed sets or Borel sets of INTEGERS? -- Leocat 16:26, 8 November 2006 (UTC)

Answering the question literally -- the integers are usually given the discrete topology, so every set of integers is closed and Borel.

Trying to read your mind a bit -- when we speak of games whose payoff set is closed, or Borel, we're not talking about sets of integers, but rather sets of sequences of integers. These are given the product topology. A basic open set is defined by specifying finitely much of the sequence, and taking all possible extensions.

Now to the more serious matter: Your proof is still not correct (though it's an improvement over your previous effort). Your second step

2. Go through the entire game, generating a sequence {a(1),a(2),...,a(t),...}.

cannot be carried out, because we don't know what the second player played. You can remedy that by specifying what the second player played, but you need to make sure that the sequence that results is not one for which you've already made an A-or-not-A decision. The cardinality argument of the original proof, or something fulfilling the same function, is going to be needed. --Trovatore 21:50, 8 November 2006 (UTC)

I guess my choice of symbols did not make it clear what I meant - so I changed it to make it clear that we are talking about sequences generated by our procedure together with the currently considered strategy. -- Leocat 10:55, 10 November 2006 (UTC)

So step 2 is not as clear as it could be, but much worse is step 7:

Keep repeating with further strategies if there are any, making sure that sequences already considered do not become generated again.

How do you propose to "make sure" of that? --Trovatore 05:09, 11 November 2006 (UTC)

You can start with the set of all sequences and keep choosing elements from it without returning them. If you choose an element {a(1),a(2),a(3),...,a(n),...} you will use it e.g. to make the sequence {c(1),d(2),c(3),d(4),...} by assigning c(1)=a(1),c(3)=a(2),...,c(2n-1)=a(n),... . -- Leocat 16:04, 11 November 2006 (UTC)

I take it this is when refuting a strategy for the second player, correct? But how do you know that you haven't used the sequence {a(1),a(2),a(3),...} already? --Trovatore 20:26, 11 November 2006 (UTC)

Let G be the set of all sequences of natural numbers. We start from this set and every time we choose a sequence we obtain a smaller set, which does not contain any of the sequences that have already been chosen. But this still does not solve the problem. -- Leocat 15:50, 12 November 2006 (UTC)

You're right, it doesn't. The point is, how do you know you don't exhaust G, before you get to the end of the construction? There is a way to handle this; it was there in the original proof. --Trovatore 20:28, 12 November 2006 (UTC)

There always exists a bijection between sets of the same cardinality, so I do not think it is a problem that you exhaust G before you get to the end of the construction. The problem is to keep constructing sequences and making decisions regarding their membership in A without contradicting yourself. I believe it can be done. I do not see the solution of this problem in the original proof. Also, the cardinality argument in step 2 of the original proof is false, as I already pointed out. -- Leocat 18:09, 15 November 2006 (UTC)

No, it was correct; you didn't understand it. Not entirely your fault, as it wasn't clearly written. But it's a key point, and you won't have a correct proof until you do understand it. How do you know you don't exhaust G by the end of the construction? Hint: At any given point in the construction, what do you know about the part of G that has been used? --Trovatore 18:33, 15 November 2006 (UTC)

At any given point in the construction we know that the cardinality of the part of G that has been used is less than continuum. But I do not see how it helps in making sure that we dot generate any sequence more than once. -- Leocat 14:54, 20 November 2006 (UTC)

How big is G? --Trovatore 18:11, 20 November 2006 (UTC)

At any stage in the construction of the game G, there are continuum many outcomes (sequences of moves for both Alice and Bob), but the subset of them which have been designated as wins for Alice or wins for Bob is less than the continuum. If we project this onto the sequence of Bob's moves (in the process of refuting Alice's strategies), we see that there are continuum many sequences of moves for Bob, but the subset which have been used is less than continuum many. So we are free to choose a sequence for Bob which has not yet been used; and use it to refute Alice's current strategy. Since the moves for Bob are different than any already designated, the entire outcome (both Alice's moves and Bob's moves) must be different. Similarly when choosing sequences of moves for Alice to refute Bob's current strategy. At the end, any outcomes not yet designated may arbitrarily be designated as wins for (say) Alice. Then all strategies of either player have been refuted and the game is not determined.

If we did not know that the number of outcomes already designated was less than the continuum, we could not be sure that we could choose a sequence of moves for Bob with which to refute Alice's current strategy. So we could not be sure that it was not a winning strategy for Alice. So the game might be determined. JRSpriggs 08:28, 21 November 2006 (UTC)

Things are a little bit more difficult: just because we choose a different sequence of Bob's moves each time we refute Alice's strategy does not guarantee that we do not generate a sequence more than once, because a given sequence of Bob's moves could have been already generated when refuting a Bob's strategy. But there is a simple solution to this problem: each time we refute a strategy, we take projections of the generated sequence onto Bob's moves and onto Alice's moves and we take away both of these sequences from the set of sequences that have not been used yet. -- Leocat 10:20, 21 November 2006 (UTC)

You are misinterpreting what I said. I meant that ALL outcomes whether from refuting Alice or refuting Bob would be projected before each selection of a new sequence to refute one of their strategies. So your "correction" is already incorporated in my answer. JRSpriggs 11:20, 21 November 2006 (UTC)