Talk:Axiom of determinacy

Infinite logic

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)

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?

The axiom of choice vs. axiom of determinacy needs work. 1st of all, the proof is a variation of Cantor and should be mentioned as such. 2nd of all, many determinancies are not infinite - therefore an infinite game cannot be used to prove the difference between AC and AD. 146.115.82.167 (talk) 14:01, 4 May 2017 (UTC)

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)

The article no longer uses the term 'independence' at all. I just did a search of the article for 'indep' and it was not found. What it does say is "AD implies the consistency of ZF. Hence it is not possible to prove AD in ZF (a consequence of the incompleteness theorems)." (i.e., AD is independent). Since we can prove the independence of AD (assuming ZF is consistent), the independence of AD cannot itself be independent! If it were, there would be models of ZF in which AD is not independent, i.e., in which AD can be proven from ZF, which contradicts the fact that it is provably impossible to prove AD, so it cannot be proven in any model of ZF.

This means the class of models in which AD is false cannot be empty. In fact, in 1930 Gödel proved that if ZF is consistent, so is ZFC, i.e. there are models in which AC is true. In all such models AD is false, since AD is incompatible with AC.--Hccrle (talk) 09:23, 26 April 2008 (UTC)

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)

What is PA? To say it's possible PA can prove 0=1 is to say it's possible to prove PA is false, but what is it? Nowhere on this page or in the article is the term "PA" defined. Do you mean Peano's Arithmetic? Surely you jest. --Hccrle (talk) 10:06, 26 April 2008 (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 $\omega$" 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)

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)

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)

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)

I also found the article very confusing until I had a look at that link. What I'm going to do is change the link on the word "games" in the third sentence (the statement of the axiom itself) to point to that link instead of to "game theory". After all, what that link does is explain what sort of game this axiom is talking about, and that was just the missink link I needed to understand it. 91.105.63.245 (talk) 19:57, 20 April 2008 (UTC)

Actually I don't agree with the link to game theory. Game theory is almost exclusively about games of imperfect information -- games of perfect information (at least, with only two players) are considered kind of trivial from a game-theoretic perspective. They may not be trivial in practice, of course, but the parts of them that are difficult are not interesting to game theorists qua game theorists. I can believe that the link to a section of determinacy may not have been ideal, but I think it's better than a link to game theory. --Trovatore (talk) 21:31, 20 April 2008 (UTC)

Whoops, now I see that we're in "violent agreement". Sorry about that -- I read the diffs backwards. --Trovatore (talk) 21:55, 20 April 2008 (UTC)

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)

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 $\aleph _{17}$, then at any given stage of the iteration, we have thus far made only (at most) $\aleph _{16}$ decisions, and each of these decisions assigns the winner for only one outcome. But there are, as you correctly observe, $\aleph _{17}$ 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)

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)

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)

On Types of Games That Are Determined

The article says:

It follows from the existence of sufficient large cardinals that ... and that AD holds in L(R).

How can this be when, in L(R), L(R)=L=V. Therefore in such models AC holds, so AD cannot also hold? --Hccrle (talk) 09:47, 26 April 2008 (UTC)

You have a false premise -- it's not true that L(R) satisfies V=L. For example L(R) contains 0#, and is able to see that 0# is not an element of L (but that it is an element of L(R)). --Trovatore (talk) 21:23, 26 April 2008 (UTC)

continuum hypothesis

It's probably worth talking about the CH issue a little on the discussion page, because it's not entirely simple.

For the purposes of this discussion (not for the article of course!) let's agree to use the term "weak CH" for the proposition every set of reals is either countable or equinumerous with the reals, and "strong CH" for $2^{\aleph _{0}}=\aleph _{1}$. This terminology passes at least the minimal sanity check that, over ZF, strong CH implies weak CH, but not vice versa. Over ZFC, the two propositions are equivalent.

Then over ZF, AD implies weak CH but is actually inconsistent with strong CH.

Normally in the literature no distinction is made between the two. But that's because the axiom of choice is part of the background in the default context. That's also true for the informal set theory of Cantor in the context in which CH was originally proposed (Cantor did not know of AC in its modern form, but proposed as "a law of thought" that every set can be wellordered).

So there doesn't seem to be any completely canonical choice for which of these (if either) should be called "the continuum hypothesis" in a context where AC fails. However I would argue that strong CH is the more natural one to call "the continuum hypothesis" from the point of view of a contemporary set theorist. Two examples of why:

• It's a natural thing to start with a model of, say, ZF+AD+V=L(R), and "force CH to be true" by adding a generic bijection between R and $\aleph _{1}$; the extension is then a model of ZFC.
• Strong CH has a simpler logical form than weak CH — this is maybe surprising on the face of it, because strong CH is harder for beginners to parse, but it's true. Strong CH says "there is a wellordering of R whose every proper initial segment is countable". That can be coded as saying that there exists a set of reals with a certain property, where to define the property you need quantify only over reals, so it's $\Sigma _{1}^{2}$. Weak CH on the other hand says that for every set of reals, if it's uncountable, then there is some bijection of it with R; that is, that there is some set of reals coding the bijection. So it's $\Pi _{2}^{2}$, strictly more complicated.

Hope this explains my edits to the lede. --Trovatore (talk) 21:00, 23 April 2009 (UTC)

This is not the place to discuss what continuum hypothesis is. Our article continuum hypothesis defines it as the "weak CH" (or actually, as "there is no cardinality strictly between $\aleph _{0}$ and $2^{\aleph _{0}}$" which is even weaker, it does not imply that every cardinality below continuum is comparable with $\aleph _{0}$). If you think this is inappropriate, you should raise it on Talk:Continuum hypothesis, not here. I find it quite silly and confusing to talk about a "weak form of CH" when it is actually stronger than what the reader finds after clicking the link to continuum hypothesis.

Whatever the definition of CH is, I tried to clarify the issue by formulating exactly what the AD implies in the sentence, but you removed it, I wonder what was the rationale for that. — Emil J. 10:05, 24 April 2009 (UTC)

Wikipedia articles stand on their own. It's irrelevant what the linked article says.

(or, maybe more important — of course, the linked continuum hypothesis article is talking in the default set-theoretic context, which includes the axiom of choice. That means that the definition given there is fine, there. But in this article we necessarily step outside of that context.)

However the point about the inline explanation is well-taken. --Trovatore (talk) 18:01, 24 April 2009 (UTC)

Measurablility?

The article currently states:

the axiom of determinacy implies that all subsets of the real numbers are Lebesgue measurable

This begs the question: what about the Banach-Tarski paradox? what about the Vitali sets? I guess that the statement "incompatible with CH" takes care of these, but a more explicit development would be nice. linas (talk) 16:30, 8 May 2010 (UTC)

Because AD implies that all sets of reals are measurable, it immediately follows that it refutes Banach-Tarski and the existence of the Vitali set. I suppose that would be worth mentioning. (Note that just because AD is incompatible with AC does not in itself imply that AD refutes Banach-Tarski or the Vitali set.) --Trovatore (talk) 17:26, 8 May 2010 (UTC)

Hmm, actually, on rethinking it, I suppose I don't see an immediate argument from the measurability of all subsets of R to the measurability of all subsets of R³, which is what you need to directly refute Banach-Tarski. But AD certainly proves the measurability of all subsets of R³, and the argument is going to be essentially identical to the proof for subsets of R. --Trovatore (talk) 18:37, 8 May 2010 (UTC)

Herrlich has this quote in his book (ISBN 3540309896), in the section on AD:

“ If a model of ZF satisfies AD, then this model is closer to physical reality than any model of ZFC. For example, the Banach–Tarski paradoxical decomposition of a ball is impossible.

V.W. Marek and J. Mycielski

”

The paper cited is V.W. Marek and J. Mycielski. Foundations of mathematics in the twentieth century. Amer. Math. Monthly, 108:449–468, 2001

Help requested at extensive-form games

By the way, can someone (meaning Trovatore almost surely) look at the infinite action spaces section of Extensive-form game (the game described here is of that kind). Herrlich says that omega-long games and games where the action sets have omega cardinality are "complementary", but I'm not sure what that entails for the determinatness of perfect games of finite length but with infinite action spaces of various cardinalities. Tijfo098 (talk) 06:23, 27 March 2011 (UTC)

I have responded at that article's talk page. --Trovatore (talk) 09:50, 27 March 2011 (UTC)

Something is wrong here...

There's considerable discussion here, so I'll try to keep this concise: tic tac toe is a game which is determined and where either neither player has a winning strategy, or (if winning is redefined to mean "not losing") both players have a winning strategy. But it's simple to define a game where a winning strategy is not possible: Consider a game where each player has one move, and that move is to determine if the other player wins. — Preceding unsigned comment added by 159.54.131.7 (talk) 14:58, 25 November 2011 (UTC)

I'll respond briefly, though technically, according to WP:TALK, we shouldn't be having this discussion here. If you need more detail, you can ask a question on WP:RD/Math.

The two points are separate, so let's treat them separately.

First, the axiom of determinacy in its usual form considers only games where there are no draws, so tic tac toe is out. It's easy to add considerations for draws, but you do have to make some small modifications.

Second, the game that you propose appears to be a win for the first player. Player I says "player II loses" and the game is over. Or have I missed something? You understand that the players can't both move at once, right? --Trovatore (talk) 19:35, 25 November 2011 (UTC)

Tweak recommended

This article uses that the plays are integers, but the article on Determinacy uses natural numbers. Seems like it would be good to be consistent, even if they are the logically the same.

--Thomaso (talk) 16:02, 11 July 2012 (UTC)

I suppose there's something to that. We don't normally work terribly hard to ensure consistency between articles, but there's no point in confusing readers just for the fun of it.

(By the way, I tried to look up the Mycielski–Steinhaus article and couldn't get it, but the abstract suggests that their games played 0 and 1 — also equivalent, though it's not quite as obvious.) --Trovatore (talk) 09:39, 12 July 2012 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Axiom of determinacy. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Corrected formatting/usage for http://www.ams.org/journals/jams/1989-02-01/S0894-0347-1989-0955605-X/S0894-0347-1989-0955605-X.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 04:41, 27 May 2016 (UTC)

Naming: Determinacy vs Determinateness

I have noticed that the original versions (Mostowski45, Mycielski64, Jech77, Herrlich06) talk of an axiom of determinateness. The only proper literature I found so far on axiom of determinacy is Jech05, there the author actually uses both names from what I dug up without a real preference or explanation of one over the other. Wouldn't the naming axiom of determinateness be more historically accurate? In my opinion it also makes it easier to distinguish between determinacy as a property of finite games and determinateness as an axiom of infinite games. Pinky Suavo (talk) 18:34, 21 March 2017 (UTC)

"Determinateness" is the older name, but in my experience that's not what people call it in more modern work. --Trovatore (talk) 19:50, 21 March 2017 (UTC)

Second proof of incompatibility with AC

Hello. I have added a second proof of incompatibility with AC. In my opinion, this addition adds to the article beyond the existing proof using the well-ordering of the continuum. (Speaking for myself only, I barely understand that proof.) This addition could make this article more understandable to non-experts. This has connections with other strategy-stealing arguments. My direct knowledge of this proof is from https://www.youtube.com/watch?v=Kj5RCs1FHcc (apologies if improper citation), a video by math PhD Youtube: SackVideo. (I otherwise do not know him.) He offered the citation "Proposition 28.1 of The Higher Infinite by Akihiro Kanamori," which I do not have access to. I quote Sack: "This argument actually shows something slightly stronger than AD and AC are incompatible: It shows that AD implies there are no non-principal ultrafilters over ω. (In the video, we use AC to construct a non-principal ultrafilter. However, the existence of a non-principal ultrafilter is weaker than AC.)" This could maybe be added to this article, but I will not do so due to lack of familiarity.

2600:1700:2CC1:6C20:7439:48EF:47E3:7A0A (talk) 19:10, 23 August 2023 (UTC)

Name for Vitali-type equivalence relation in second proof?

In the "2d proof" mentioned in the comment immediately above, added on 23 Aug 2023, I see this text:

Observe the equivalence relation on $\{0,1\}^{\omega }$ such that two sequences are equivalent if and only if they differ in a finite number of terms. This partitions the set into equivalence classes, and let T be the set of equivalence classes (such that T has the cardinality of the continuum). Define $\{0,1\}^{\omega }\rightarrow T$ that takes a sequence to its equivalence class.

Does this equivalence relation have a name? I realized earlier today that this equivalence relation is more or less exactly the same thing as the Vitali set. The correspondence is "obvious": The Vitali set asks you to consider equivalence classes of reals that differ by a rational. The above asks you to consider equivalence classes of reals that differ by a dyadic rational. But the rationals and the dyadic rationals are in one-to-one correspondence, via the Minkowski question mark function. So these are constructing the same thing.

Just to be extra-super clear about what I am saying, above: the $\{0,1\}^{\omega }$ is of course the Cantor space, and it can be mapped onto the reals in the usual way, as infinite binary string expansions. Infinite binary strings that differ in a finite number of places map to reals that differ by a dyadic rational (since dyadic rationals are in one-to-one correspondence with finite-length binary strings.) So the equivalence relation is just $\{0,1\}^{\omega }/\mathbb {D}$ with $\mathbb {D}$ the dyadic rationals, while the Vitali set is just $\{0,1\}^{\omega }/\mathbb {Q}$ (and Vitali also asks you to pick one and only one representative from each equivalence class). And $\mathbb {D}$ and $\mathbb {Q}$ are in 1-1 correspondence via Minkowski question mark. There's a third article talking about this construction: the article on the infinite parity function describes the same thing (but badly) although it does mention there are uncountably many different infinite parity functions (one assignment per equivalence class).

So I am seeing this construction in three different articles in 24 hours, and I'm wondering "does it have a name"? In my mind, I'm going to call it a "Vitali-type construction" but this is my personal neologism. Can anyone do better? 67.198.37.16 (talk) 05:54, 28 November 2023 (UTC)

Yes, that equivalence relation (usually on ${}^{\omega }\omega$ rather than ${}^{\omega }2$, but it doesn't make much difference) is known as $E_{0}$. It's very special in that it's the smallest Borel equivalence relation (in the order of Borel reducibility) that does not admit a Borel function giving a real-valued complete invariant for the equivalence relation. See this paper by Harrington, Kechris, and Louveau. --Trovatore (talk) 08:15, 28 November 2023 (UTC)

Thank you! Perhaps it would be appropriate to start an article on $E_{0}$? Or more directly, I'd be interested in such an article, even if its a stub. 67.198.37.16 (talk) 21:05, 28 November 2023 (UTC)

"... that does not admit a Borel function giving a real-valued complete invariant for the equivalence relation." I assume that should read "in the standard model of the reals" since presumably one can still consistently assign it a measure of epsilon in non-standard analysis. But perhaps all of my comments should be moved to StackExchange, instead of here. Noted. 67.198.37.16 (talk) 14:35, 29 November 2023 (UTC)

This is an enjoyable discussion and I wish you'd ask a question on WP:RD/Math, where we could continue it. But briefly, no, nonstandard analysis has no loopholes to offer here. --Trovatore (talk) 17:22, 29 November 2023 (UTC)

I'll ask when I figure out what the question really is; I will need to do more reading. In the meanwhile, I will conclude that the relevant keywords are the Glimm-Effros dichotomy, the Feldman–Moore theorem and the Lusin–Novikov uniformization theorem, with at least two of those redlinks, if not all three, being redirects to Countable Borel relation which states them. 67.198.37.16 (talk) 19:13, 1 December 2023 (UTC)

Thanks for pointing me to that last article. The right division of labor for articles in this area is a little hard to work out. I don't think I'd put so much of it into countable relations specifically (there's an article I started years ago on Borel equivalence relations, a little more than a stub, but I think it should probably host much of this content). Anyway it sounds like I should get in touch with OriSegel, except that he/she seems to have submitted that article for creation and then disappeared. --Trovatore (talk) 19:30, 1 December 2023 (UTC)

And while we're on the topic, the run-length encoding from Cantor space to Baire space, does it have a common name used in set theory? I call it "the Minkowski question mark function", because that is what it is after one projects Cantor/Baire down to the reals. But, before doing this projection, calling it the question mark is perhaps a mild neologism? 67.198.37.16 (talk) 22:29, 28 November 2023 (UTC)

Argh. Please excuse the rambling note; it's late-night and maybe I'm going batty; I keep wondering "where have I seen this before?" This Vitali-type construction is rampant in dynamical systems, isn't it? The generic case for discrete-time dynamical systems is that you have some time-step operator T and as it is iterated over time, it spits out a sequence of points $x_{1},x_{2},\cdots$ For large n, the generic cases are that either the $x_{n}$ settle down to a periodic orbit where they repeat, or they settle into a chaotic orbit given by some invariant measure. As a general rule, the pretense is to not care about the transient behavior, and only be interested in what the sequence is doing for large-n. So, for periodic orbits, you say "hey, consider the system that eventually settles down to a periodic orbit, and lump all the transients into an equivalence class, i.e. where eventually, the $x_{n}$ are all the same, except for a finite number of differences." Same deal for the chaotic orbits, although it is more subtle there. If the dynamical system is of a type where the $x_{n}\in \{0,1\}$, then the standard dynamical systems ploy of "just ignore the transients and lump them into an equivalence class" is exactly kind-of-ish this Vitali-set construction. Huh. And yeah, when a dynamical system has uncountably many of these equivalence classes, it is called an "anti-classification result" (because the hope of classifying behavior into a countable set of classes was dashed.) Anti-classification is not mysterious, though, it just says each different class is labeled by a single point in the Cantor set. Well, up to a finite number of differences. Huh. Who knew? Thank you for listening. I'm going to bed now, and will regret writing this the next morning. So it goes. 67.198.37.16 (talk) 08:10, 28 November 2023 (UTC)

Hi @Trovatore above you said "this is an enjoyable conversation"; sadly, I cannot continue it, my focus has gyrated to somewhere else. However, while closing out open browser tabs, I wanted to mention that I converted the above late-night ruminations into an 18-page PDF, here. It is an extended "homework exercise"; there is no ground-breaking content. I wanted to mention it as a closing remark. Unfortunately, I never had the chance to dig into Glimm–Effros dichotomy, etc. as I had hoped. Alas. Maybe later. 67.198.37.16 (talk) 18:31, 13 April 2024 (UTC)