Counterintuitions and the well-ordering theorem
in [Logic]
|
Prev: Solutions manual to Entrepreneurship 1e Bygrave Zacharakis
Next: Solutions manual for Engineering Mechanics Statics (12th Edition) by Russell C. Hibbeler
From: Bill Taylor on 26 Oct 2009 01:50 Herman Jurjus offers: > Simplistic subjective blather: > If i forget for a moment that ZFC+AD is inconsistent, > and i start with a clean sheet, so to say, and i give an honest > account of what i mean with all the notions involved > (N, set, game, sequence, etc.) then it becomes rather > uncontroversial to me that either player 1 can win, or he can't, > i.e. player 2 has some defense. The degree of 'reliability' that > this has (for me) is not less than that of the power set axiom > or AC (rather the opposite). I agree with all this. Daryl McCullough responds: > I know that you're not offering that as a mathematical argument, > but I would like to understand your intuitions here. > "Either player 1 has a winning strategy, or 2 has a defense" > needs a little more argument to be compelling, because of games > like "Rock, paper, scissors" with no strategy guaranteed to win. OUCH! Daryl, this is not up to your usual high debating standards. RockPS, like almost any game of incomplete information, has no "guaranteed winning strategy", as you say, but AD games are not of this type. The typical AD game is written *as if* it were a game of simultaneous choice with incomplete information, but it is not really so, OC - it is a perfectly well defined game of length omega where all moves are made with complete information. Such a game *definitely* should have a winning astrategy for one or other player! To repeat the general game, for those unfamiliar:- CONSECUTIVE DESCRIPTION ======================= Player one chooses a natural number; player two (aware of the first choice) chooses another natural number; player one (aware of both preceding choices) chooses a third natural number, and so on. The game thus produces a clearly defined sequence of natural numbers. If this sequence is a member of some pre-assigned set A, then player one wins. If this sequence is not a member of A, then player 2 wins. Thus the game is essentially defined/described by the set A, a subset of N^N. SIMULTANEOUS DESCRIPTION ======================== The two players simultaneously choose a "full strategy"; which consists of a function from finite sequences of integers, to integers. Player 1's "first move" is given by f_1(empty), player 2's "first move" is given by f_2(f_1(empty)), player 1's "2nd move" by f_1(f_1(empty), f_2(f_1(empty))), and so on. The winner is then determined as in the first case. ------------------------------------------------------- It is surely clear that these two descriptions are isomorphic. Indeed, the compementarity involved is faintly reminiscent of the wave(simultaneous)/particle(consecutive) description of quantum matter! :-) The first description makes it "intuitively clear" that the game should always be "determined", that is, have a winning strategy for one or the other player, as at every step it is a game of complete information. It is a theorem of game theory that if the game is sure to terminate before some particular number of moves, then it is determined. It is a theorem of set theory that all Baire sets A lead to a determined game. It seems very natural to a game player that ANY set A should lead to a determined game. Alas, it is a theorem of ZFC set theory that there are undetermined games, that is, undetermined sets A. (Of course, as is usual with such matters, no explicit example can ever possibly be produced!) It is known to be consistent with ZF, and even ZF + CC, that all such sets A are determined. To me, as a regular game player, it is AT LEAST as obvious that every game should be determined, as it is obvious that every countable cross-product should have a member, (CC); and both are a GREAT DEAL more intuitively obvious than that every set whatsoever should have a choice function. > What's the argument against the possibility that > (1) for every strategy for the first player, > there is a defense for the second player, and > (2) for every defense for the second player, > there is a strategy for the first player that beats it. These are intuitively contradictory. > I don't see any reason to believe that this CAN'T be the case. Viewing the simultaneous description, that may seem plausible; it is plausable either way - i.e. that 1&2 could both be true, or that they cannot. BUT, viewing the consecutive description, it is just plain impossible, as there would be a sequence that both players would win with. Intuitively. This is assuming the informal intuitive equivalence of "choosing a strategy once and for all" with "choosing each move as it comes according to what's seen already". This is an informal equivalence, so not susceptible of proof or disproof, but in view of the isomorphism of the two game descriptions, it seems (to me) to be unimpeachable! I think the conflict between AD and (full) AC is one of the starkest in math - much more convincing than the Banach decomposition paradox. -- Withering William ** They travel as waves but arrive as particles.
From: Herman Jurjus on 26 Oct 2009 02:41 Bill Taylor wrote: > Herman Jurjus offers: > >> Simplistic subjective blather: >> If i forget for a moment that ZFC+AD is inconsistent, >> and i start with a clean sheet, so to say, and i give an honest >> account of what i mean with all the notions involved >> (N, set, game, sequence, etc.) then it becomes rather >> uncontroversial to me that either player 1 can win, or he can't, >> i.e. player 2 has some defense. The degree of 'reliability' that >> this has (for me) is not less than that of the power set axiom >> or AC (rather the opposite). > > I agree with all this. > > Daryl McCullough responds: > >> I know that you're not offering that as a mathematical argument, >> but I would like to understand your intuitions here. >> "Either player 1 has a winning strategy, or 2 has a defense" >> needs a little more argument to be compelling, because of games >> like "Rock, paper, scissors" with no strategy guaranteed to win. > > OUCH! Daryl, this is not up to your usual high debating standards. > RockPS, like almost any game of incomplete information, has no > "guaranteed winning strategy", as you say, but AD games are > not of this type. > > The typical AD game is written *as if* it were a game of > simultaneous choice with incomplete information, but it is > not really so, OC - it is a perfectly well defined game of > length omega where all moves are made with complete information. > Such a game *definitely* should have a winning astrategy for > one or other player! > > To repeat the general game, for those unfamiliar:- > > CONSECUTIVE DESCRIPTION > ======================= > Player one chooses a natural number; player two (aware of > the first choice) chooses another natural number; player one > (aware of both preceding choices) chooses a third natural > number, and so on. The game thus produces a clearly defined > sequence of natural numbers. If this sequence is a member of > some pre-assigned set A, then player one wins. If this sequence > is not a member of A, then player 2 wins. > > Thus the game is essentially defined/described by the set A, > a subset of N^N. > > SIMULTANEOUS DESCRIPTION > ======================== > The two players simultaneously choose a "full strategy"; > which consists of a function from finite sequences of integers, > to integers. Player 1's "first move" is given by f_1(empty), > player 2's "first move" is given by f_2(f_1(empty)), player 1's > "2nd move" by f_1(f_1(empty), f_2(f_1(empty))), and so on. > > The winner is then determined as in the first case. > ------------------------------------------------------- > > It is surely clear that these two descriptions are isomorphic. > Indeed, the compementarity involved is faintly reminiscent > of the wave(simultaneous)/particle(consecutive) description > of quantum matter! :-) > > The first description makes it "intuitively clear" that > the game should always be "determined", that is, have > a winning strategy for one or the other player, as at > every step it is a game of complete information. > > It is a theorem of game theory that if the game is sure > to terminate before some particular number of moves, then it is > determined. It is a theorem of set theory that all Baire sets A > lead to a determined game. It seems very natural to a game > player that ANY set A should lead to a determined game. > > Alas, it is a theorem of ZFC set theory that there are > undetermined games, that is, undetermined sets A. > (Of course, as is usual with such matters, no explicit > example can ever possibly be produced!) > It is known to be consistent with ZF, and even ZF + CC, > that all such sets A are determined. > > To me, as a regular game player, it is AT LEAST as obvious > that every game should be determined, as it is obvious > that every countable cross-product should have a member, (CC); > and both are a GREAT DEAL more intuitively obvious than > that every set whatsoever should have a choice function. > >> What's the argument against the possibility that >> (1) for every strategy for the first player, >> there is a defense for the second player, and >> (2) for every defense for the second player, >> there is a strategy for the first player that beats it. > > These are intuitively contradictory. > >> I don't see any reason to believe that this CAN'T be the case. > > Viewing the simultaneous description, that may seem plausible; > it is plausable either way - i.e. that 1&2 could both be true, > or that they cannot. BUT, viewing the consecutive description, > it is just plain impossible, as there would be a sequence that > both players would win with. Intuitively. > > This is assuming the informal intuitive equivalence of > > "choosing a strategy once and for all" with > "choosing each move as it comes according to what's seen already". > > This is an informal equivalence, so not susceptible of proof > or disproof, but in view of the isomorphism of the two game > descriptions, it seems (to me) to be unimpeachable! > > I think the conflict between AD and (full) AC is one of > the starkest in math - much more convincing than > the Banach decomposition paradox. Full agreement. -- Cheers, Herman Jurjus
From: Butch Malahide on 26 Oct 2009 03:50 On Oct 26, 12:50 am, Bill Taylor <w.tay...(a)math.canterbury.ac.nz> wrote: > Herman Jurjus offers: > > > Simplistic subjective blather: > > If i forget for a moment that ZFC+AD is inconsistent, > > and i start with a clean sheet, so to say, and i give an honest > > account of what i mean with all the notions involved > > (N, set, game, sequence, etc.) then it becomes rather > > uncontroversial to me that either player 1 can win, or he can't, > > i.e. player 2 has some defense. The degree of 'reliability' that > > this has (for me) is not less than that of the power set axiom > > or AC (rather the opposite). > > I agree with all this. > > Daryl McCullough responds: > > > I know that you're not offering that as a mathematical argument, > > but I would like to understand your intuitions here. > > "Either player 1 has a winning strategy, or 2 has a defense" > > needs a little more argument to be compelling, because of games > > like "Rock, paper, scissors" with no strategy guaranteed to win. > > OUCH! Daryl, this is not up to your usual high debating standards. > RockPS, like almost any game of incomplete information, has no > "guaranteed winning strategy", as you say, but AD games are > not of this type. > > The typical AD game is written *as if* it were a game of > simultaneous choice with incomplete information, but it is > not really so, OC - it is a perfectly well defined game of > length omega where all moves are made with complete information. > Such a game *definitely* should have a winning astrategy for > one or other player! > > To repeat the general game, for those unfamiliar:- > > CONSECUTIVE DESCRIPTION > ======================= > Player one chooses a natural number; player two (aware of > the first choice) chooses another natural number; player one > (aware of both preceding choices) chooses a third natural > number, and so on. The game thus produces a clearly defined > sequence of natural numbers. If this sequence is a member of > some pre-assigned set A, then player one wins. If this sequence > is not a member of A, then player 2 wins. > > Thus the game is essentially defined/described by the set A, > a subset of N^N. > > SIMULTANEOUS DESCRIPTION > ======================== > The two players simultaneously choose a "full strategy"; > which consists of a function from finite sequences of integers, > to integers. Player 1's "first move" is given by f_1(empty), > player 2's "first move" is given by f_2(f_1(empty)), player 1's > "2nd move" by f_1(f_1(empty), f_2(f_1(empty))), and so on. > > The winner is then determined as in the first case. > ------------------------------------------------------- > > It is surely clear that these two descriptions are isomorphic. > Indeed, the compementarity involved is faintly reminiscent > of the wave(simultaneous)/particle(consecutive) description > of quantum matter! :-) > > The first description makes it "intuitively clear" that > the game should always be "determined", that is, have > a winning strategy for one or the other player, as at > every step it is a game of complete information. Can you explain why determinacy is intuitively clear when each move is choosing a natural number, but no longer clear when each move is choosing a countable ordinal? or a set of real numbers? What does your intuition say about the following game? First, White chooses a set X or real numbers; then Black chooses a real number x. Black wins if either X is empty or x is in X; White wins if X is nonempty and x is not in X. I'm sure you will agree, Bill, that neither player has a winning strategy. What gives?
From: Daryl McCullough on 26 Oct 2009 07:22 Bill Taylor says... >OUCH! Daryl, this is not up to your usual high debating standards. >RockPS, like almost any game of incomplete information, has no >"guaranteed winning strategy", as you say, but AD games are >not of this type. I disagree. The sort of games that are discussed in AD *are* games of incomplete information. Each player decides his strategy *before* seeing any moves by the other player. I should say, rather, there is no disadvantage to deciding your strategy ahead of time. A strategy, remember, is a rule for how you *respond* to moves by the other player. Any possible way that you could take into account the information about the actual moves the other player makes can be folded into the strategy you adopt at the very beginning. >The typical AD game is written *as if* it were a game of >simultaneous choice with incomplete information, but it is >not really so, OC - it is a perfectly well defined game of >length omega where all moves are made with complete information. You don't have complete information, because you don't know what strategy your opponent is going to follow. In a *finite* game, this lack of information is eliminable, because you can assume that your opponent will play optimally, and for finite games there always *is* a notion of an optimal strategy. The existence of an optimal strategy is a *theorem* of finite games, you have to prove it, you can't just assume it. The existence of a winning strategy on the part of one player or the other is provable for finite games using the fact that finite games are *well-founded*. You prove by induction (possibly transfinite induction) that one player or the other has a winning strategy. A finite game can be described as a well-founded tree, with the arcs labeled by moves. Once you take your first move, you have reduced the situation to a simpler game (set-theoretically, the tree has a lower rank in the set-theoretic universe). By induction on the rank of the tree, you can prove that every tree has a winning strategy for one player or the other. But infinite games correspond to non-well-founded trees. You can't get started to prove by induction that there is a winning strategy. >Such a game *definitely* should have a winning astrategy for >one or other player! Why? Here's a more mathematical description of the game: The players take turns picking natural numbers. This produces an infinite sequence x_1 x_2 .... There is a set W of infinite sequences of natural numbers that count as a "win" for the first player. At each move, the player is determining his next move from the finite sequence of naturals played so far. So a strategy is a function from finite sequences of naturals to naturals. Let play(f,g) be the infinite sequence resulting from the first player following strategy f and the second player following strategy g. The game has a winning strategy for the first player if: exists f, forall g, play(f,g) in W The game has a winning strategy for the second player if: exists g, forall f, play(f,g) not in W These two statements are *not* negations of each other. There is no reason necessarily to assume that one must be true or the other must be true. >To repeat the general game, for those unfamiliar:- > >CONSECUTIVE DESCRIPTION >======================= >Player one chooses a natural number; player two (aware of >the first choice) chooses another natural number; player one >(aware of both preceding choices) chooses a third natural >number, and so on. The game thus produces a clearly defined >sequence of natural numbers. If this sequence is a member of >some pre-assigned set A, then player one wins. If this sequence >is not a member of A, then player 2 wins. > >Thus the game is essentially defined/described by the set A, >a subset of N^N. > >SIMULTANEOUS DESCRIPTION >======================== >The two players simultaneously choose a "full strategy"; >which consists of a function from finite sequences of integers, >to integers. Player 1's "first move" is given by f_1(empty), >player 2's "first move" is given by f_2(f_1(empty)), player 1's >"2nd move" by f_1(f_1(empty), f_2(f_1(empty))), and so on. > >The winner is then determined as in the first case. >------------------------------------------------------- > >It is surely clear that these two descriptions are isomorphic. >Indeed, the compementarity involved is faintly reminiscent >of the wave(simultaneous)/particle(consecutive) description >of quantum matter! :-) > >The first description makes it "intuitively clear" that >the game should always be "determined", that is, have >a winning strategy for one or the other player, as at >every step it is a game of complete information. But *why* does a game of complete information imply that there is a winning strategy for one player or the other? That's a *theorem* that must be proved. >> I don't see any reason to believe that this CAN'T be the case. > >Viewing the simultaneous description, that may seem plausible; >it is plausable either way - i.e. that 1&2 could both be true, >or that they cannot. BUT, viewing the consecutive description, >it is just plain impossible, as there would be a sequence that >both players would win with. Intuitively. I don't see that. >This is assuming the informal intuitive equivalence of > >"choosing a strategy once and for all" with >"choosing each move as it comes according to what's seen already". > >This is an informal equivalence, so not susceptible of proof >or disproof, but in view of the isomorphism of the two game >descriptions, it seems (to me) to be unimpeachable! I think you can prove that there is no disadvantage to choosing a strategy once and for all, as opposed to one move at a time. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 26 Oct 2009 08:02
Bill Taylor says... >> I know that you're not offering that as a mathematical argument, >> but I would like to understand your intuitions here. >> "Either player 1 has a winning strategy, or 2 has a defense" >> needs a little more argument to be compelling, because of games >> like "Rock, paper, scissors" with no strategy guaranteed to win. > >OUCH! Daryl, this is not up to your usual high debating standards. >RockPS, like almost any game of incomplete information, has no >"guaranteed winning strategy", as you say, but AD games are >not of this type. Actually, could you explain in what sense chess or checkers are games of complete information, and rock/paper/scissors is *not*? In all cases, each player must make his move in ignorance of what move his opponent will make. There is no "hidden state" (such as the hidden playing cards in a game of cards), unless you count the intentions of your opponent as hidden state, in which case, all games are games of incomplete information. -- Daryl McCullough Ithaca, NY |