Strategy vs Tactics. was: Famous Quote
Bill Taylor
|> > " Strategy Is your Plan for What To Do, Tactics Is How You Accomplish It."
Or less wordily, more succinctly:
Strategy is what to do, tactics is how to do it.
Good for war, perhaps, though not so applicable to games.
|> "Strategy is how you get the girl into the back seat;
|> tactics is what you do when you get there."
Now THAT one I like! But as it's only for men, howbout this equally un-PC...
"Strategy is getting him up the aisle, tactics is getting him into the kitchen."
Then there's one of my great faves from the chess world...
"Tactics, is knowing what to do when there's something to do,
strategy is knowing what to do when there's nothing to do."
...which is somewhat similar to the very poignant...
"Strategy is when I don't know what I'm doing;
tactics is when I do know what I'm not doing."
...and the really rather profound...
"Tactics is about doing things right,
strategy is about doing the right things."
Finally, here is my quick and dirty list of 1-word comparisons,
which might perhaps be useful:-
tactics strategy
local global
short-term long-term
dynamic structural
engineering architecture
numerical geometrical
action ideas
execution planning
left-brain right-brain
routine intuition
calculation estimation
extension intension
method imagination
analytic synthetic
arithmetic geometry
algorithm creativity
cleverness wisdom
-----------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-----------------------------------------------------------------------------
Strategy is what you want... tactics is what you get.
-----------------------------------------------------------------------------
Gerry Myerson
mat...@math.canterbury.ac.nz (Bill Taylor) wrote:
> Gary Anderson <gande...@unl.edu> writes:
>
> |> > " Strategy Is your Plan for What To Do, Tactics Is How You
> |> > Accomplish It."
which led Bill to a nice discussion, which I have snipped, because
I want to change the subject (while neglecting to change the Subject:)
and talk about a different famous quote:
"In theory there is no difference between theory and practice.
In practice there is."
Now we've all heard/seen this one, or variations of it, but who
gets the credit for it? I ask because the March issue of the Notices
of the American Mathematical Society attributes it to Yogi Berra
(see page 304, and note that by referring to the AMS I've made this
post on-topic for this newsgroup).
Now, Yogi has said a lot of wonderful things, but I don't think this
is one of them; as Yogi said, "Half the things I said, I never said
them." Anyone know the proper attribution? or at least have a citation
predating Mr Berra?
Gerry Myerson (ge...@mpce.mq.edu.au)
Claude Chaunier
> tactics strategy
[a good list]
linguistics literature
physics metaphysics
lemma theory
day life span
glenn
Taylor) wrote:
>Gary Anderson <gande...@unl.edu> writes:
>
>|> > " Strategy Is your Plan for What To Do, Tactics Is How You Accomplish It."
>
>Or less wordily, more succinctly:
>
>Strategy is what to do, tactics is how to do it.
>
>Good for war, perhaps, though not so applicable to games.
In "Theory of Games and Economic Behavior" strategy is a complete plan
when the rules are known. Tactics (in a game) is the separate moves
which integrate up a specific strategy.
But in practice the rules are vaguely known. Thus 2 more levels are
needed, namely logistics and Politics. Thus the final hierarchy goes
as
Logistics
Tactics
Strategy
Politics
For a more concise definition of Politics and logistics drop a line.
--
glenn
John Savard
>Finally, here is my quick and dirty list of 1-word comparisons,
>which might perhaps be useful:-
> tactics strategy
How about:
weather climate
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
Fred Galvin
Why was this crossposted to only 7 newsgroups? How did you pick those
few out of the hundreds of games groups and dozens of military groups?
I'm not the net police, just curious. Hope you don't mind if I insert
some on-topic (for sci.math) content, by pointing out the technical
distinction between "strategy" and "tactic" in game-theoretic
topology, as introduced (I think, but I could be wrong) by Choquet.
This is from memory, so there may be mistakes here and there.
The so-called Banach-Mazur game on a topological space X (a
generalization of the classical Banach-Mazur game from the Scottish
Book) is played by two players called Alpha and Beta, as follows.
First Beta picks a nonempty open set B_1; then Alpha picks a nonempty
open set A_1 contained in B_1; then Beta picks a nonempty open set B_2
contained in A_1; and so on, until B_n and A_n have been picked for
every natural number n. Alpha wins if the intersection of all the
chosen sets is nonempty; Beta wins if it is empty. The space X is said
to be "weakly alpha-favorable" if Alpha has a winning *strategy*,
"alpha-favorable" if Alpha has a winning *tactic*. A "strategy" for
Alpha is a function s which determines Alpha's moves as a function of
the whole history, i.e., A_n = s(B_1, A_1, B_2, A_2, ..., B_{n-1}) or,
more simply (but equivalently) A_n = s(B_1, B_2, ..., B_{n-1}). A
"tactic", on the other hand, determines Alpha's next move as a
function of the current "position", i.e., A_n = s(B_n).
Fred Galvin
> The so-called Banach-Mazur game on a topological space X (a
> generalization of the classical Banach-Mazur game from the
> Scottish Book) is played by two players called Alpha and Beta, as
> follows. First Beta picks a nonempty open set B_1; then Alpha
> picks a nonempty open set A_1 contained in B_1; then Beta picks a
> nonempty open set B_2 contained in A_1; and so on, until B_n and
> A_n have been picked for every natural number n. Alpha wins if the
> intersection of all the chosen sets is nonempty; Beta wins if it
> is empty. The space X is said to be "weakly alpha-favorable" if
> Alpha has a winning *strategy*, "alpha-favorable" if Alpha has a
> winning *tactic*. A "strategy" for Alpha is a function s which
> determines Alpha's moves as a function of the whole history, i.e.,
> A_n = s(B_1, A_1, B_2, A_2, ..., B_{n-1}) or, more simply (but
> equivalently) A_n = s(B_1, B_2, ..., B_{n-1}).
I screwed up the indices: for B_{n-1} read B_n.
> A "tactic", on the other hand, determines Alpha's next move as a
> function of the current "position", i.e., A_n = s(B_n).
By the way, "tactics" are also called "positional strategies" or
"stationary strategies".
Bill Taylor
> Why was this crossposted to only 7 newsgroups? How did you pick those
> few out of the hundreds of games groups and dozens of military groups?
Fred! It's not like you to make underhand net-coppy remarks like this?
Anyway, it was already cross-posted to tons of newsgroups, (though not any
military ones I think), I just removed a lot of boring-looking ones and added
in sci.math coz I thought some of the one-liners had a bit of relevance here.
> technical distinction between "strategy" and "tactic" in game-theoretic
> topology, as introduced (I think, but I could be wrong) by Choquet.
Sounds entirely possible. Haven't heard of good old Choquet for a fair while.
I remember in my student days I had an office-mate who was dead keen on
Choquet's theorem... thought it the greatest thing since sliced bread.
The way he described it, it was - a striking link between alegbra, topology,
and measure theory. Nothing to do with the thread... I do but ramble on.
> The so-called Banach-Mazur game
I love the B-M game. It's at the basis of AD too, isn't it?
> First Beta picks a nonempty open set B_1; then Alpha picks a nonempty
> open set A_1 contained in B_1; then Beta picks a nonempty open set B_2
> contained in A_1; and so on, until B_n and A_n have been picked for
> every natural number n. Alpha wins if the intersection of all the
> chosen sets is nonempty; Beta wins if it is empty.
Lovely stuff. And well described, Fred.
> A "strategy" for
> Alpha is a function s which determines Alpha's moves as a function of
> the whole history, i.e., A_n = s(B_1, A_1, B_2, A_2, ..., B_{n}) or,
> more simply (but equivalently) A_n = s(B_1, B_2, ..., B_{n}).
> A "tactic", on the other hand, determines Alpha's next move as a
> function of the current "position", i.e., A_n = s(B_n).
OK, nice distinction. Somewhat similar to the distinction in Decision Theory
to that between a "behavioural strategy" and a "mixed strategy".
However, something is eluding me. I fully see the force of your parenthetical
"(but equivalently)", i.e. that one can drop out the previous own-decisions
from consideration; but I'm having trouvble seeing why there isn't a similar
"or equivalently" right down to just the last B_n only. In other words,
why isn't any strategy fully equivalnet to some tactic? It's hard to see
why on earth whatever B did in the past should have any further bearing
on what A does now (and in the future), once we know B's current move.
i.e. it seems intuitively obvious that the current best play would be
independent of the past, given the present, (kind of Markovian idea).
So pleae tell us Fred, why is there any advantage playing some strategy
over any tactic? Or is there in fact none.
Please put me out of my misery; (preferably without the use of firearms).
---------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
---------------------------------------------------------------------------------
Football reporter: Each game is unique and this one is no different to any other.
---------------------------------------------------------------------------------
Fred Galvin
> Fred Galvin <gal...@math.ukans.edu> writes:
>
> Fred! It's not like you to make underhand net-coppy remarks like
> this? Anyway, it was already cross-posted to tons of newsgroups,
> (though not any military ones I think), I just removed a lot of
> boring-looking ones and added in sci.math coz I thought some of
> the one-liners had a bit of relevance here.
My apologies. I don't usually pay attention to the headers, so when
this silly thread, which I'd seen previously on one of the chess
groups, popped up in sci.math, I figured wrongly that you had expanded
the list of newsgroups.
> > First Beta picks a nonempty open set B_1; then Alpha picks a nonempty
> > open set A_1 contained in B_1; then Beta picks a nonempty open set B_2
> > contained in A_1; and so on, until B_n and A_n have been picked for
> > every natural number n. Alpha wins if the intersection of all the
> > chosen sets is nonempty; Beta wins if it is empty.
>
> > A "strategy" for
> > Alpha is a function s which determines Alpha's moves as a function of
> > the whole history, i.e., A_n = s(B_1, A_1, B_2, A_2, ..., B_{n}) or,
> > more simply (but equivalently) A_n = s(B_1, B_2, ..., B_{n}).
> > A "tactic", on the other hand, determines Alpha's next move as a
> > function of the current "position", i.e., A_n = s(B_n).
>
> However, something is eluding me. I fully see the force of your
> parenthetical "(but equivalently)", i.e. that one can drop out the
> previous own-decisions from consideration; but I'm having trouvble
> seeing why there isn't a similar "or equivalently" right down to
> just the last B_n only. In other words, why isn't any strategy
> fully equivalnet to some tactic? It's hard to see why on earth
> whatever B did in the past should have any further bearing on what
> A does now (and in the future), once we know B's current move.
> i.e. it seems intuitively obvious that the current best play would
> be independent of the past, given the present, (kind of Markovian
> idea).
>
> So pleae tell us Fred, why is there any advantage playing some
> strategy over any tactic? Or is there in fact none.
Strange as it seems, there are topological spaces in which player
Alpha has a winning strategy but has no winning tactic. Yes, it is
counterintuitive. It was an unsolved problem for years, and then some
examples were given by Gabriel Debs, Strategies gagnantes dans
certains jeux topologiques, Fund. Math. 126 (1985), 93-105. If I
remember right, one of Debs' examples was the real line with the usual
topology strengthened by declaring all countable sets to be closed;
i.e., the open sets are of the form G\D where G is open in the usual
topology and D is countable.
Some general conditions under which strategies can be replaced by
tactics were formulated by Yhos and Telgarsky, Stationary strategies
in topological games, Topology Appl. 22 (1986), 51-69.
John R Ramsden
>
> mat...@math.canterbury.ac.nz (Bill Taylor) wrote, in part:
> >
> > Finally, here is my quick and dirty list of 1-word comparisons,
> > which might perhaps be useful:-
> >
> >
> > tactics strategy
>
> How about:
>
> weather climate
A couple more:
delegate representative
power authority
(No point asking an EU functionary to explain the differences though.
Adept though they are at twisting most words, for those pairs they
wouldn't understand the question.)
Cheers
---------------------------------------------------------------------------
John R Ramsden (j...@redmink.demon.co.uk)
---------------------------------------------------------------------------
The new is in the old concealed, the old is in the new revealed.
St Augustine.
---------------------------------------------------------------------------
David Rush
> In "Theory of Games and Economic Behavior" strategy is a complete plan
> when the rules are known. Tactics (in a game) is the separate moves
> which integrate up a specific strategy.
>
> But in practice the rules are vaguely known. Thus 2 more levels are
> needed, namely logistics and Politics. Thus the final hierarchy goes
> as
>
> Logistics
> Tactics
> Strategy
> Politics
Funny, I would have switched Logistics and Tactics. ISTM that
Logistics enables Tactics. Strategy must include Logistics. Politics
is the application of Strategy to change men's minds.
david rush
--
Property is theft.
-- What is Property? (Pierre-Joseph Proudhon)
Jason Stokes
>On 18 Apr 2001 06:06:42 GMT, mat...@math.canterbury.ac.nz (Bill
>Taylor) wrote:
>
>>Gary Anderson <gande...@unl.edu> writes:
>>
>>|> > " Strategy Is your Plan for What To Do, Tactics Is How You Accomplish
>>|> > It."
>>
>>Or less wordily, more succinctly:
>>
>>Strategy is what to do, tactics is how to do it.
>>
>>Good for war, perhaps, though not so applicable to games.
>
>
>In "Theory of Games and Economic Behavior" strategy is a complete plan
>when the rules are known. Tactics (in a game) is the separate moves
>which integrate up a specific strategy.
Strategy versus Tactics: It's one of those distinctions everyone draws, but
without having any clue what the actual distinction might be, except
strategy relates somehow, vaguely, to long-term planning, and tactics to
short term planning.
There are certainly people for whom "strategy" and "tactics" are
interchangeable terms, and you're not going to get much illumination from a
dictionary, so any debate on the meaning of the words is fairly pointless,
being a largely subjective matter anyway. The distinction is clearly not
very meaningful for me, since I recall only recently noticing someone using
a bad strategy in a game, saying "that's a bad strategy", later realising
that serious games nerds would have insisted I was talking about tactics,
not strategy in that particular case, and not caring.
Robert Jasiek
Jason Stokes wrote:
> Strategy versus Tactics: It's one of those distinctions everyone draws, but
> without having any clue what the actual distinction might be, except
> strategy relates somehow, vaguely, to long-term planning, and tactics to
> short term planning.
> There are certainly people for whom "strategy" and "tactics" are
> interchangeable terms, and you're not going to get much illumination from a
> dictionary, so any debate on the meaning of the words is fairly pointless,
> being a largely subjective matter anyway. The distinction is clearly not
> very meaningful for me
Definitions for either tactics or strategy could refer to all the
theoretically possible calculations and thus mean the same. OTOH,
tactics would be defined from the perspective of a single move
while strategy would be defined from the opposite perspective of
the entire calculation space.
When I speak of tactics and at the same do not mean the same as
strategy, then I refer to chains of single moves as far as a
player can calculate. When I speak of strategy and at the
same time do not mean the same as tactics, then I refer to
structures dividing the entire calculation space as far as I can
imagine construction of such structures. If I am realistic, then
I consider only a subspace of the entire calculation space,
construct structures dividing the subspace and if I have been
modest enough by choosing a small enough subspace, then the
dividing structures meet the structures of tactical calculation.
If I am weak, then my tactical structures are not big enough to
meet my strategic structures; if I am unreasonable, then my
strategic structures do not refer to a sufficiently small
subspace and therefore do not meet my tactical structures. OC,
usually I am weak and unreasonable:)
--
robert jasiek
Carmi Licht
The distinction between Strategy and Tactics is originally a
military one; Strategy is saying "Let's bomb their supply lines from the
air." whereas Tactics is saying "Use 12 F-15e's to bomb the supply line
at coordinates X-Y with mavericks."
Strategy is the plan formulated by generals whereas Tactics is
the more local planning and execution put down by Liutenants and
Seargents.
For example in chess; Strategy is to play aggressively, in your
opponents half, all pieces being defended; Tactics is to put THAT rook
where it's defended by the pawn and the bishop and has vantage towards
your opponnents king and rook.
Having said that, the line where Strategy becomes Tactics is
very hard to place, and since one does not succeed well without the
other then, semantics aside, does it really matter at all? Insofar as
games refer to Strategy and Tactics, they do not do so in the rules and
so, the distinction is moot in playing the game. As for commentary on
games, since every case would be explained anyway, it isn't so bad if
we occasionaly err in our ways.
Carmi Licht
Mahatma on duty
Bill Taylor
|> > > First Beta picks a nonempty open set B_1; then Alpha picks a nonempty
|> > > open set A_1 contained in B_1; then Beta picks a nonempty open set B_2
|> > > contained in A_1; and so on, until B_n and A_n have been picked for
|> > > every natural number n. Alpha wins if the intersection of all the
|> > > chosen sets is nonempty; Beta wins if it is empty.
|> >
|> > > A "strategy" for
|> > > Alpha is a function s which determines Alpha's moves as a function of
|> > > the whole history, i.e., A_n = s(B_1, A_1, B_2, A_2, ..., B_{n}) or,
|> > > more simply (but equivalently) A_n = s(B_1, B_2, ..., B_{n}).
|> > > A "tactic", on the other hand, determines Alpha's next move as a
|> > > function of the current "position", i.e., A_n = s(B_n).
|> > why isn't any strategy
|> > fully equivalnet to some tactic? It's hard to see why on earth
|> > whatever B did in the past should have any further bearing on what
|> > A does now (and in the future), once we know B's current move.
|> > i.e. it seems intuitively obvious that the current best play would
|> > be independent of the past, given the present,
|> Strange as it seems, there are topological spaces in which player
|> Alpha has a winning strategy but has no winning tactic. Yes, it is
|> counterintuitive.
It certainly is. Indeed, I was sure I could construct a proof that every
strategy *could* be replaced by some tactic; but it keeps slipping away
before I can grasp it properly, (as these infinitary examples so often do!)
Can you give us a bit of a hint as to how the example works, Fred?
One thing though - the counter-examples you mentioned do seem to involve
the topology of the thing intimately; and I can't see why that should be
so either. Suppose we modify the original game by allowing all choices to be
*any* old subsets of the previous choice. (We could generalize even further
and say the winning/losing intersections weren't just empty vs nonempty,
but might allow some other criteria, but let's ignore that one for now.)
Now is the modified game is still stratego-tactically inequivalent?
Are there any easier-to-comprehend counterexamples available now?
That is, we are just looking at abstract sets with no features but
cardinality; and playing the game on them. Is it easy to find any
simplish examples where there is a winning strategy but no winning tactic
for some player? Obviously they are equivalent for games on finite sets,
and I can see how to prove it for countable sets, ("empty" wins easily.)
But what about beyond that?
Can you help us out there Fred? Or anyone else?
Infinite game theory is a slippery business! I wish I knew more about it!
-----------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-----------------------------------------------------------------------------
All your base are belong to us.
-----------------------------------------------------------------------------
Bantari
Strategy is a nothing but crutch we need to cover for our
inability to read positions deep enough. :-)
--
________________________________________
-Bantari
e-mail: kapr...@yahoo666.com (remove the 666)
homepage: http://home.san.rr.com/rafgo
Fred Galvin
> Fred Galvin <gal...@math.ukans.edu> writes:
>
> |> Strange as it seems, there are topological spaces in which player
> |> Alpha has a winning strategy but has no winning tactic. Yes, it is
> |> counterintuitive.
>
> It certainly is. Indeed, I was sure I could construct a proof
> that every strategy *could* be replaced by some tactic; but it
> keeps slipping away before I can grasp it properly, (as these
> infinitary examples so often do!) Can you give us a bit of a hint
> as to how the example works, Fred?
Sure. Not right now, though. It's too late, and I have to get up and
go to work tomorrow. Of course, you could always go and read that
article by Gabriel Debs that I referred you to.
> One thing though - the counter-examples you mentioned do seem to
> involve the topology of the thing intimately; and I can't see why
> that should be so either. Suppose we modify the original game by
> allowing all choices to be *any* old subsets of the previous
> choice. (We could generalize even further and say the
> winning/losing intersections weren't just empty vs nonempty, but
> might allow some other criteria, but let's ignore that one for
> now.)
>
> Now is the modified game is still stratego-tactically
> inequivalent? Are there any easier-to-comprehend counterexamples
> available now? That is, we are just looking at abstract sets with
> no features but cardinality; and playing the game on them. Is it
> easy to find any simplish examples where there is a winning
> strategy but no winning tactic for some player? Obviously they
> are equivalent for games on finite sets, and I can see how to
> prove it for countable sets, ("empty" wins easily.) But what about
> beyond that?
I think you left something out of your definition of the game. If they
can pick *any* old sets, then "empty" wins by playing the empty set on
his first move. Did you mean to say that the chosen sets all have to
have cardinality k, the same as the starting set? In that case, you've
just asked part (1) of Problem 67 in the Scottish book, which was
posed by Banach on August 1, 1935; the answer is that "empty" has a
winning strategy (in fact a tactic), for *every* infinite cardinal k
(every *aleph* if you insist); the proof was given by J. Schreier,
Eine Eigenschaft abstrakter Mengen, Studia Math. 7 (1938), 155-156.
Bill Taylor
|> Did you mean to say that the chosen sets all have to
|> have cardinality k, the same as the starting set?
We'll say I meant that, to avoid me having to admit that I was thinking
fuzzily enough to be unsure exactly what I meant.
|> posed by Banach on August 1, 1935; the answer is that "empty" has a
|> winning strategy (in fact a tactic), for *every* infinite cardinal k
Yes, I can pretty much imagine how it might go. e.g. For the reals, Empty
just has to make sure a sufficiently big swathe gets chopped out every time,
which is not at all hard. At first it seemed as if this wouldn't be *quite*
a tactic, as the decision also depends on the "time" (= move number), and you
specified that a tactic had to have: dec_n(B_n) = s(B_n); not s(n, B_n).
However I think I can see how to get around that easily enough.
For any higher cardinality, we just have to do similarly - essentially
find a countable family of "swathes" so that their union equals the whole
space, which isn't too hard. Of course, there are many irritating details,
but I can't see any that look really difficult.
So I can see that the restriction to open sets in some intricate topolgy is
indeed an essential (type of) thing to *allow* that tactics =/= strategies;
but I'm still damned if I can see a way to *ensure* that it happens.
Awaiting your further comments with keen interest, Fred!
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
There is only the one universal Go game, played on one giant board.
And whenever we play, we are just resolving one small region of it.
-------------------------------------------------------------------------------
Fred Galvin
> Fred Galvin <gal...@math.ukans.edu> writes:
>
> |> Did you mean to say that the chosen sets all have to
> |> have cardinality k, the same as the starting set?
>
> We'll say I meant that, to avoid me having to admit that I was thinking
> fuzzily enough to be unsure exactly what I meant.
>
> |> posed by Banach on August 1, 1935; the answer is that "empty" has a
> |> winning strategy (in fact a tactic), for *every* infinite cardinal k
>
> Yes, I can pretty much imagine how it might go. e.g. For the
> reals, Empty just has to make sure a sufficiently big swathe gets
> chopped out every time, which is not at all hard.
Oh, oh. Are you using the AXIOM OF CHOICE, Bill? Without AC, that game
played on the continuum could be a win for "nonempty". Namely, in a ZF
model where every uncountable set of real numbers contains a perfect
set, "nonempty" has a winning tactic: play bounded perfect sets.
> At first it seemed as if this wouldn't be *quite* a tactic, as
> the decision also depends on the "time" (= move number), and you
> specified that a tactic had to have: dec_n(B_n) = s(B_n); not
> s(n, B_n).
A strategy of the form s(n, B_n) is called a "Markov strategy". You
will be glad to know that, in the case of the generalized Banach-Mazur
game BM(X) on a topological space X, if Alpha has a winning Markov
strategy, then he/she/it has a winning tactic. Of course that makes
the Debs examples even more paradoxical: Alpha has a winning strategy,
but does not even have a winning Markov strategy. By the way, if there
is a winning strategy for *Beta* in BM(X), then there is a winning
tactic; that's because the spaces where Beta has a winning strategy
are exactly the non-Baire spaces.
Many other special kinds of strategies have been studied, mainly by my
former student Marion Scheepers, who has published dozens of papers
about that kind of thing: k-tactics (you remember the opponent's last
k moves), Markov k-tactics (obvious), coding strategies (you know both
the opponent's last move and your own last move, which may contain a
coded message from your earlier self), etc.
> However I think I can see how to get around that easily enough.
>
> For any higher cardinality, we just have to do similarly -
> essentially find a countable family of "swathes" so that their
> union equals the whole space, which isn't too hard. Of course,
> there are many irritating details, but I can't see any that look
> really difficult.
I guess one irritating detail is, what do you do if your opponent
suddenly eliminates all but one of your swathes? Schreier's winning
tactic, which works on any *well-ordered* infinite set X, is quite
simple: presented with a set A, play the set of all elements of A
which have an immediate predecessor in A.
> So I can see that the restriction to open sets in some intricate
> topolgy is indeed an essential (type of) thing to *allow* that
> tactics =/= strategies; but I'm still damned if I can see a way to
> *ensure* that it happens.
I already told you what the topology is, and it's not all that
intricate: X is the real line, and the open sets are sets of the form
G\D where G is open in the usual topology and D is countable. (You may
complain that X is not a regular space. In the same paper, Debs also
gives an example of a Tychonoff space with the same property; if you
want to know about that, you will have to read the paper.) Here is a
winning strategy for Alpha. It's move n, and Beta has just chosen a
nonempty set B_n = (G_n)\(D_n), where G_n is open in the usual
topology of the reals, and D_n is countable, D_n = {x(n,0), x(n,1),
x(n,2), ...}. Alpha replies by playing A_n = (I_n)\(D_n), where I_n is
a finite open interval, closure(I_n) is contained in G_n, and I_n
contains none of the points x(i,j) where i and j are less than or
equal to n. Clearly, the intersection of all the I_n's is nonempty;
and if x is any point in the intersection of all the I_n's, then x
can't be in any of the D_n's, so it's in the intersection of all the
A_n's. Thus, Alpha has a winning strategy in BM(X). The proof that
Alpha has no winning tactic is somewhat more complicated, and I'm too
tired to do it now. But maybe you can already see why it won't be so
easy to replace the winning strategy described above with a winning
tactic. If not, you should try to find a winning tactic.
TO BE CONCLUDED
Fred Galvin
> Oh, oh. Are you using the AXIOM OF CHOICE, Bill? Without AC, that
> game played on the continuum could be a win for "nonempty".
> Namely, in a ZF model where every uncountable set of real numbers
> contains a perfect set, "nonempty" has a winning tactic: play
> bounded perfect sets.
What nonsense. Sure, you can have a ZF model where every uncountable
set of real numbers contains a perfect set. However, to get a tactic
out of that, you would need a CHOICE FUNCTION which chooses a perfect
subset for every uncountable set; and of course there is no such
function. I'll have to think about this more carefully, but it seems
to me that "nonempty" never has a winning strategy in that game,
choice or no choice. Which wouldn't mean, of course, that "empty" has
a winning strategy in those non-AC models; the game could be
undetermined. Even in AD models, because it's not the kind of game AD
applies to.
Fred Galvin
I hope I've got it right now; this choiceless set theory is too tricky
for me. We're talking about the game where Empty and Nonempty pick
alternate terms (doesn't matter who goes first) of a decreasing
infinite sequence of continuum-sized subsets of the real line; Empty
wins if the intersection is empty, Nonempty wins if it's nonempty. I
want to prove (in ZF) that Nonempty can't have a winning strategy.
Assume a winning strategy for Nonempty. Now, if X is any c-sized
subset of R, Empty could play X as his first move, and then apply a
canonical strategy to make sure that the intersection will contain at
most one point. (E.g., at the nth move he considers the nth rational
number r_n and eliminates everything to the left or everything to the
right of r_n, whichever leaves a set of size c.) Playing that way
against Nonempty's purported winning strategy will determing a unique
element of X. Thus we have a choice function on the collection of all
c-sized subsets of R. From that we can easily get a choice function on
the collection of all nonempty subsets of R, and so R can be
well-ordered; but then we can use the well-ordering to define a
winning strategy for Empty.
All right then, if my reasoning is correct, the game can't be a win
for Nonempty, AC or no AC. However, I don't see how to win it for
Empty, other than using a well-ordering of R. As far as I can see, the
game could be undetermined.
James Hunter
Fred Galvin wrote:
Most nonempty strategies choose that the empty set
is fiction to start with, so it's like an automatic win.
Fred Galvin
The so-called Banach-Mazur game on a topological space X (a
generalization of the classical Banach-Mazur game from the Scottish
Book) is played by two players called Alpha and Beta, as follows.
First Beta picks a nonempty open set B_1; then Alpha picks a nonempty
open set A_1 contained in B_1; then Beta picks a nonempty open set B_2
contained in A_1; and so on, until B_n and A_n have been picked for
every natural number n. Alpha wins if the intersection of all the
chosen sets is nonempty; Beta wins if it is empty. The space X is said
to be "weakly alpha-favorable" if Alpha has a winning *strategy*,
"alpha-favorable" if Alpha has a winning *tactic*. A "strategy" for
Alpha is a function s which determines Alpha's moves as a function of
the whole history, i.e., A_n = s(B_1, A_1, B_2, A_2, ..., B_n) or,
more simply (but equivalently) A_n = s(B_1, B_2, ..., B_n). A
"tactic", on the other hand, determines Alpha's next move as a
function of the current "position", i.e., A_n = s(B_n).
The following example of a topological space X, such that Alpha has a
winning strategy but not a winning tactic in BM(X), is due to Gabriel
Debs, Strategies gagnantes dans certains jeux topologiques, Fund.
Math. 126 (1985), 93-105. The space X is the real line topologized
with open sets of the form G\D where G is open in the usual topology
of the line and D is countable. I already posted a winning strategy
for Alpha in BM(X); now I will try to prove that Alpha has no winning
tactic. By a "rational inverval" I mean an open interval (in the usual
sense) with rational endpoints.
Let s be any tactic for Alpha in BM(X); we will show how Beta can
defeat it. If B is any nonempty open subset of X, then s(B) is a
nonempty open subset of B; say s(B) = g(B)\d(B), where g(B) is open in
the usual topology of the real line, and d(B) is countable. Let h(B)
be a rational interval contained in g(B).
LEMMA. Every interval I contains a rational interval j(I) such that,
for every countable set C (of real numbers), there is a countable set
D containing C such that h(I\D) = j(I).
PROOF. Assume the contrary for some interval I; that is, for every
rational interval J contained in I, there is a countable set C(J) such
that h(I\D) =/= J for every countable set D containing C(J). We get a
contradiction by letting D be the union of all the C(J)'s.
Define an infinite sequence of intervals I_1, I_2, ..., so that
length(I_n) < 1/n and closure(I_{n+1}) is contained in j(I_n). The
intersection of these intervals consists of a single point x.
And now, with Alpha committed to the tactic s, it's Beta to play and
win, as follows:
Beta finds a countable set D_1, containing x, and such that
h(I_1 \ D_1) = j(I_1), and plays B_1 = I_1 \ D_1.
Alpha plays A_1 = s(B_1) = g(B_1)\d(B_1), where d(B_1) is some
countable set.
Since I_2 is contained in j(I_1) = h(B_1), which is contained in
g(B_1), Beta can legally play B_2 = I_2 \ D provided D is a countable
set containing d(B_1). So, Beta finds a countable set D_2 containing
d(B_1) such that h(I_2 \ D_2) = j(I_2), and plays B_2 = I_2 \ D_2.
Continuing in this way, at move n Beta plays B_n = I_n \ D_n. Now, the
intersection of all the I_n's consists of the single point x, which
Beta eliminated on his first move; so the intersection of the B_n's is
empty, and Beta wins. Q.E.D.
A slight modification of this argument shows that Alpha does not have
a winning "Markov strategy", i.e., a winning strategy of the form A_n
= s(n, B_n).
David Libert
Earlier in the thread, Fred defined the Banach Mazur game for a
topological space. That definition did not require that the new moves
pick a stricly smaller subset of the preceding play. Then the
discussion of the original Scotch book problem on an abstract set
later in the thread grew from that.
If we consider the abstract version as allowing playing the same set
as the opponent's previous play, we can consider some examples. If we
play the abstract set game on a finite set, to maintain the
cardinality of the starting set, everyone must keep playing the
starting set. Since there is only one legal move in any position of
the game, each side has a unique strategy: just keep playing the
starting set, and this is a winning strategy for non-empty. (Provided
the starting set is non-empty, if it is empty then empty wins :-/ ).
So a less silly example. In a ZF model with an infinite Dedekind
finite set, the same comments apply, that discussion above really only
needed the starting set is Dedekind finite, so over ZF we can have an
infinite set with a winning strategy for non-empty.
(If we require each move pick a strict subset of the previous, the
game breaks down on the second move with no legal plays.)
So now in ZF consider Dedekind infinite starting sets. If we allow
players to repeat the last play of the opponent, ie subsets need not
be proper, then there is an example of a ZF model with Dedekind
infinite starting set A, in which non-empty wins by always repeating
the last move.
Namely, start with a ZFC model M. In there form a set A of
aleph_1 many atoms (for a Fraekel Mostowski model to be constructed).
The permutation group acting on these will be the full permutation
group (ie arbitrary bijections). We will use countable support, ie
countable subsets of A in M as support.
This produces a Fraenkel Mostowski ZFA (ZF with atoms) +
countable-AC model: countably many choices from arbitrary cardinality
index sets, with A an uncountable set s.t. every subset of A is
either countable or co-countable (ie the compliment in A of an
arbitrary set).
In this resulting model, any subset of A equipollent to A must be
co-countable in A. So if we play a strategy in the game of repeating
the last play always, the opponent produces as complete play a
sequence of co-countable subsets of A. The intersection of these is
the compliment of the union of their countable compliments. This
model has countable AC, so a countable union of countable sets is
countable, so the intersection of the played sets is co-countable in
A and hence non-empty, so this is a winning strategy for the
non-empty player.
This is a ZFA model, a model with atoms. There is the Jech Sochar
embedding theorem, which says for each Fraenkel Mostowski ZFA model
and for each ordinal alpha in the model, there is a symmetric forcing
ZF model which has an embedding of the atoms of the ZFA model and
alpha levels of powerset above the atoms into the ZF model, so that
alpha levels of powerset are preserved by the embedding.
Recognizing that our ZFA model had the game over A with non-empty
winning strategy goes on only a few powerset levels above atoms, so
there is a symmetric forcing ZF model doing the same.
By the way, I used countable support above so that omega injects
into the set of atoms A, hence A is Dedekind infinite. You could
also make a Fraenkel Mostowski model using finite suports, this
produces what is called an amorphous set: an infinite set with only
finite and co-finite subsets. Any amorphous set is Dedekind finite.
But the whole point of this first example was to have a Dedekind
infinite starting set, so I used countable support.
Next a further example.
For Dedekind finite starting sets, the definition of the game breaks
down on the second move if we require each player play a proper subset
of the opponent's last play. For Dedekind infinite sets, this extra
requirement still allows a reasonable game. The strategy of my last
example would not work for this version.
So what about a non-empty winning strategy in ZF which always makes
proper subsets of the last move?
I will show that ZF + there exists an amorphous set |- there is a
Dedekind infinite starting set with a winning strategy for non-empty.
As I noted above, ZFA Fraenkel Mostowski models with an amorphous set
can be produced as earlier but use finite support on atoms. And Jech
Sochar can get similar ZF models which preserve statements like the
existence of such a game.
This second example does everything the first one does, so you could
omit the countable support construction and just go with amorphous
sets. But I retain the countable support version, because it is
simpler in other ways. In the countable support version, I could just
take the starting set to be the set of atoms. If instead I use an
amorphous set of atoms, it is Dedekind finite, so can't be used
directly as the starting set. I must define a different Dedekind
infinite set for the game, instead of using only the original atoms.
So I retain the countable support version above, that only uses atoms.
But the extra complications of this new example get the extra
conclusion of a non-empty winning strategy that always plays strictly
smaller sets.
There is no such strategy for non-empty in the countable support
model. Namely the first move of such a strategy played would give a
function picking for each |A| sized subset of A a non-empty proper
subset. It can be shown that such functions don't have countable
support, and hence are not in the Fraenkel Mostowski model.
So to continue with the second example, work in ZF + B is an
amorphous set. I seek to define a new set and prove in this theory
that it has a non-empty winning strategy which always returns strict
subsets of the last play. From such a theorm in this theory, models
of the final conclusion can be constructed by Fraenkel Mostowski
finite support to get the amorphous set in a ZFA model, and Jech
Sochar to get a sufficiently similar ZF model.
So work in ZF, and assume B is amorphous. Let C be a denumerable
set, disjoint from B. Our starting set for the game will be
D = B union C.
Omega injects into D, since D includes C, so D is Dedekind infinite.
I will analyse the form of sets D' which are subsets of D, and
equipollent to D. Let B' = D' ^ B , C' = D' ^ C. So
D' = B' disjoint-union C'.
We assume there is f : D' -> D, a bijection.
I will consider how f acts on B' and C', in each case considering
which part of B' or C' is carried by f to the corresponding B or
C, and which part crosses over, ie B' elements carried into C, C'
elements carried into B.
First consider which C' elements are carried by f into B. If there
were infinitely many such C' elements, then since f is injective the f
image of these would be an infinite subset of B. B is amorphous, so
every subset is finite or co-finite. Since f"C' ^ B would be
infinite, therefore it must be co-finite in B. But the pre-image of
this set as a subset of C a countable set is countable, so this image
set would be countable, so B would be a countable set union a finite
set, ie B countable, contradicting B amorphous.
We got this contradiction from assuming infinitely many C' members
cross over to B under f.
So f on C' maps cofinitely-in-C' many C' members to C, and only
finitely many C' members to B.
Now consider f acting on B'. If f maps infinitely many B'
elements into C, then f"B' ^ C would be a denumerable subset of C,
so pulling backwards by f^-1, the preimage would be a denumerable
subset of B, and as above this is impossible: ie it is infinite,
hence co-finite (by B amorphous), and B amorphous can't have a
countable co-finite subset.
So f on B' also has only finitely many crossovers: B' elements
carried by f to C.
So f : D' -> D can be mostly thought of the union of two
restriction maps : B' -> B and C' -> C, with only finitely many
exceptional points of crossover in addition.
f is surjective onto D, and hence onto C. Only finitely C points
can have image coming from B', so infinitely many C points must have
f image coming from C'. We conclude C' must be infinite.
Ok, so for that last conclusion I only needed to include one
part above, how f acts on B'. I will leave both sections, as the
total description is more intuitive to picture. (Ie approximately
union B'->B and C'->C).
So, using a fixed omega listing of C, I can from the above define a
choice function on all D' : |D| sized subsets of D : the smallest
member of C', which must exist since C' is infinite and hence
non-empty.
Consider more about the form of D', a |D| sized subset of D. So
there is f as above, and f is onto D and hence onto B, but by
the other direction of the earlier discussion about f, only finitely
many B elements are hit by f acting on C', so since B is infinite
infinitely many elements of B are hit by f on B', in particular B'
is infinite.
Since B is amorphous, B' being an infinite subset of B must be
co-finite in B.
Now consider a decreasing sequence (by inclusion) of subsets D'i of
D, where each |D'i| = |D|. By the last comment, each of these D'i
only omits finitely many elements from B. Ie |B - B'i| finite for
each i, letting B'i be the "B'" for D'i.
Since the D'i sequence was decreasing, the B - B'i is an
increasing sequence (not necessarrily strictly increasing: I just
mean increasing i makes this a not necessarily proper superset of the
earlier ones).
Each of those B - B'i is finite, but we have a countable union of
them. Could this union be infinite?
If this was an infinite union, we could form the sequence of the
sets of the new elements added at step i in the union, so infinitely
many of these steps would have a nonempty set (since they union to the
original union), so form the subsequence of steps with non-empty sets
this way, and index it by omega again. So we would have an omega
sequence of non-empty finite disjoint subsets of B.
But unioning the even elements of this sequence, we get a subset of
B which is neither finite nor co-finite in B, contradicting B
amorphous.
The contradiction from assuming that the B - B'i sequence had
infinite union. So it has finite union.
In other words, the Di' sequence intersecting only throws out
finitely many elements from B, an infinite set.
So: any omega sequence of |D| sized subsets of D intersects to
non-empty, ie it only throws away finitely many from B.
So any play of the game in our ZF model must have non-empty
intersection.
So any strategy for non-empty is a winning strategy.
Now the trick is to define a strategy for non-empty that always
returns a strictly smaller set than the opponent's last play. In the
countable support example before, there are no such strategies, let
alone winning strategies, because they require too much choice.
But I started this noting that there is a choice function for D' :|D|
sized subsets of D: pick the least C' element according to a fixed
omega enueration of C.
So non-empty's strategy: apply that choice function to the
opponent's last play, and return
opponent's last play - {that chosen element}. This is throwing away
one element from C' in the opponent's last play, which I previously
noted had C' denumerable, so we can "Hilbert hotel" on the C' part
and get D' - {that choice} ~ D', ie identity on B' which wasn't
changed and shift on the "C'" parts. So this play has same
cardinality as the oppenent's, which was assumed |D|.
So this really defines a legal move in the game. So it is
strategy. And since it is a strategy, by the earlier comments it is a
winning strategy for non-empty.
So in the game allowing non-proper inclusions on D, this is still a
strategy where non-empty makes all inclusions proper. And in the game
requiring proper inclusions, this is a strategy.
By the way, my examples are using exotic starting sets. Fred just
posted to this thread a proof in ZF that non-empty has no winning
strategy for this game starting with the reals.
--
David Libert (ah...@freenet.carleton.ca)
1. I used to be conceited but now I am perfect.
2. "So self-quoting doesn't seem so bad." -- David Libert
3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig
Fred Galvin
> By the way, my examples are using exotic starting sets. Fred just
> posted to this thread a proof in ZF that non-empty has no winning
> strategy for this game starting with the reals.
A fallacious proof. I just can't get the hang of thinking in ZF.
Fred Galvin
> I hope I've got it right now; this choiceless set theory is too
> tricky for me. We're talking about the game where Empty and
> Nonempty pick alternate terms (doesn't matter who goes first) of a
> decreasing infinite sequence of continuum-sized subsets of the
> real line; Empty wins if the intersection is empty, Nonempty wins
> if it's nonempty. I want to prove (in ZF) that Nonempty can't have
> a winning strategy. Assume a winning strategy for Nonempty. Now,
> if X is any c-sized subset of R, Empty could play X as his first
> move, and then apply a canonical strategy to make sure that the
> intersection will contain at most one point. (E.g., at the nth
> move he considers the nth rational number r_n and eliminates
> everything to the left or everything to the right of r_n,
> whichever leaves a set of size c.) Playing that way against
> Nonempty's purported winning strategy will determing a unique
> element of X. Thus we have a choice function on the collection of
> all c-sized subsets of R. From that we can easily get a choice
> function on the collection of all nonempty subsets of R, and so R
> can be well-ordered; but then we can use the well-ordering to
> define a winning strategy for Empty.
Wrong again! I quietly assumed that, if a set of cardinality 2^aleph_0
is partitioned into two subsets, at least one of them will have
cardinality 2^aleph_0. I don't believe that can be proved without the
axiom of choice. :-(
Fred Galvin
However, the proof seems to be OK if we add to ZF the axiom "every
uncountable set of reals has cardinality 2^aleph_0". In particular, it
seems that Nonempty can't have a winning strategy in a ZF model where
every uncountable set of reals contains a perfect set; which is the
opposite of what I claimed in one of my earlier erroneous posts.
David Libert
>
> Wrong again! I quietly assumed that, if a set of cardinality 2^aleph_0
> is partitioned into two subsets, at least one of them will have
> cardinality 2^aleph_0. I don't believe that can be proved without the
> axiom of choice. :-(
I had thought it might help that the proof only requires that when a
continuum sized subset of the reals is partitioned by splitting according
to intervals one piece must be continuum sized.
But this special case is no easier: if the reals can be paritioned into
A and B, each of size strictly smaller than continuum, then make a
bijection of the reals with the positive reals. Look at the image of A
under this bijection, obtaining A' a subset of the positive reals.
Take the image of B under this bijection, but then flip that subset of
the positive reals around 0, ie take negatives elementwise, calling the
resulting subset of the negative reals B'.
Then A' union B' bijects with the positive reals, by identity on A' and
negative flip again on B', so A' union B' is equipollent to the positive
reals, ie to the continuum.
So A' union B' is a continuum sized subset of the reals which can be
partitioned into two strictly smaller peices just by dividing according to
inequalities with 0, ie partitioning by intersection A' union B' with
respective intervals from a partitioning.
So if there are bad examples there are also bad examples to even this
special form of partitioning.
Possibly relevant is the 1982 thesis listed in the Math Genealogy Project
at
http://hcoonce.math.mankato.msus.edu/html/id.phtml?id=31782
of Mark van Liere supervised by Leo Harrington and titled:
Splitting the Reals into Two Small Pieces .
Fred Galvin
Let DC stand for the Axiom of Dependent Choices, AD the Axiom of
Determinacy. Note that, in the theory ZF+DC+"every uncountable set of
real numbers contains a perfect set" (in particular, in ZF+AD+DC), the
game is provably undetermined: we've already seen that Nonempty has no
winning strategy; on the other hand, with DC, any fixed strategy for
Empty can be defeated by playing bounded perfect sets.
Hope I've finally got that right! Back to ZFC.
Daryl McCullough
>
>On Sun, 29 Apr 2001, Fred Galvin wrote:
>
>> On Sun, 29 Apr 2001, Fred Galvin wrote:
>>
>> > On Sat, 28 Apr 2001, Fred Galvin wrote:
Perhaps you and Fred should take your argument off-line?
8^)
--
Daryl McCullough
CoGenTex, Inc.
Ithaca, NY
Fred Galvin
> On Monday, 30 Apr 2001, Fred Galvin wrote:
> >
> >On Sun, 29 Apr 2001, Fred Galvin wrote:
> >
> >> On Sun, 29 Apr 2001, Fred Galvin wrote:
> >>
> >> > On Sat, 28 Apr 2001, Fred Galvin wrote:
>
> Perhaps you and Fred should take your argument off-line?
I'm sorry, Officer. I didn't mean to do that.
David Libert
well-orderable set has an empty winning strategy, so in particular in
ZFC empty wins the real game.
Fred has given results about what happens in various ZF cases. I
will give results about some more cases.
A difficult case which we can't rule out happening over ZF is the
reals partioning into sets A, B each of cardinality strictly less
than c = 2^Aleph_0.
I will give a ZF proof ruling out a trivial special case of this,
which will be useful below.
Though we presently don't see how to refute such A,B in ZF, ZF
does prove the special case:
2-partioning Claim: there are no A,B partitioning the reals
with A countable and |B| < c.
Working toward the proof of that, I will first prove in ZF:
Claim 1 : for C a countable set of reals, the set of all integer
translates of C is countable. Ie {c+n | c in C, n in Z} is
countable.
Proof of Claim 1: Surject C x Z onto the set of integer translates
by <c,n> |-> c+n. C x Z, a Cartesian product of countable sets is
countable. So our set, the image of a countable set, is countable.
Disjointness Claim: if C is a countable set of reals, there exists
D a denumerable set of reals, disjoint from C.
Proof of disjointness Claim: The set of all integer translates of C
is countable, so there is some real r not in the set of integer
translates of C. Then let D = the set of integer translates of r,
this is denumerable, and disjoint from C.
So with these above:
Proof of 2-partitioning Claim:
Suppose A is countable, and A,B partitions the reals. I seek to
prove |B| = c, which proves the claim.
A union B is isomorphic to the reals, and A is countable, so
pulling back the disjointness claim by the isomorphism, there is a
denumerable D, subset of A union B and disjoint from A, in other
words D subset of B.
I am now going to inject A union B into B. Make an omega
enumeration of D, send the D elements in B to the even enumerated D
elements in B, send B-D to B-D by the identity, send A
(countable) into the odd enumerated elements of D inside B.
So A union B injects into B, but A union B is all the reals, so
|B| = c as required.
QED 2-partitioning claim.
I will use this last claim to help analyse another choiceless model
w.r.t. the real game. Paul Cohen's _Set Theory and the Continuum
Hypothesis_ gives the Levy and Feferman model of ZF + the reals are a
countable union of countable sets.
1st Countable Partition Claim:
ZF + <Ai | in omega> partitions the reals into countable sets
|- empty has a winning strategy in the real game.
Proof of 1st Countable Partition Claim:
The simplest strategy for empty will be at empty's i'th step
to throw away the Ai elements in the opponent's last play.
The only problem is to see this is a legal move, it still has c
cardinality. But the opponent's play is assumed legal, so c sized, so
by the 2-partitioning claim, throwing away countably many from
continuum sized leaves continuum size.
This simple strategy allows for repeating the opponent's last play.
If you want a strategy which makes proper subsets, or if you defined
the game this way, find the least i with Ai nonempty intersection
with the last play, and throw those members away.
QED 1st countable partition claim.
In fact the only property I used of countable above, is that a two
partitioning A,B can't have A countable, ie two partitioning as in
the claim. By the same proof, any partitioning of the reals into
countably many sets, each of a cardinality which can't be in a two
partitioning, gives the corresponding empty strategy.
I will now give a more general discussion of these partioning
properties, as related to the real game.
For kappa a cardinal <= c, define a kappa-splitting to be a
partitioning of the reals into exactly kappa non-empty pieces, each of
cardinality strictly < c. (We don't require one uniform bound < c on
all sizes).
For kappa a cardinal < c, define kappa splits iff there is a
kappa-splitting.
ZF |- c splits, ie partition into singletons.
ZF |- 1 doesn't split: ie each piece is required < c size.
ZF proves:
Upward Claim: if kappa <= c and kappa splits, then for all
cardinals lambda s.t. kappa <= lambda <= c, lambda splits.
Proof of Upward Claim:
Let J be a set of reals of size lambda, let I be a subset of B of
size kappa.
Define an enumeration over i in I, A^0_i so that <A^0_i | i in I>
is a kappa splitting of the reals.
For j in J - I, let A^0_j = {}.
I an going to modify <A^0_j | j> by stages to eventually produce a
lambda splitting. The problem is we have all those {} 's, and the
final lambda splitting must have a lambda enumeration of non-empty
sets.
So we will modify by replacing empty slots by their own singletons,
then move those elements put into the singletons out of their previous
sets, to keep everything disjoint. This process must be repeated, but
will be shown to eventually stabilize.
For concreteness, I will first define <A^1_j | j in J> , from
<A^0_j | j in J> . I will do this by marking certain j in J as
being for singletons. For A^0_j 's nothing was so marked.
For each j in J, with A^0_j = {}, I newly mark at stage 1 those
j's as singletons. I define A^1_j = {j} for such newly marked j's.
For each unmarked j in J, I define
A^1_j = A^0_j - {j'| j' in J and j' marked at stage 1}.
So A^1_j 's are pairwise disjoint, and union to all reals.
Marked j's appear at their own singletons, unmarked j's appear at
their location from the A^0_j' union.
All the A^0_j = {} have now been adjusted to be nonempty, but in
doing so we may have created new empties, namely when we moved marked
j's out of old A^0_j' 's previously non-empty. If all members were
moved out, it may become empty.
So we do it again, defining A^2_j 's from A^1_j 's. We retain
all the step one markings. We add new ones for the A^1_j = {}.
Marked j's get their own singleton, like before.
The subtraction step, removing marked elements, only needs to be
performed on unmarked locations. Marked locations can never steal
from each other, because each has their own index in the singleton.
That was step 1 from 0 and step 2 from 1. Similarly successor steps:
inherit previous markeds, add new marks, and subtract from unmarkeds
all marked. You can say subtract all marked, or all new marked, the
result is the same, as the old marked were previously removed.
Define A^alpha_j for limit ordinals. The marked are the union of
the marked from all previous stages, those get singletons. Unmarked
get the intersection of all the A^alpha'_j at that location j for
smaller alpha'.
Then at a limit stage alpha, the A^alpha_j are pairwise disjoint
for distinct j, and they union to all the reals.
Possibly the limit process could create new empties, by the
intersection on the unmarkeds.
So the successor step after the limit will process those new empties.
So define this as a transfinite recursion, through all ordinals.
Each stage of this recursion defines its marked elements in J. This
is increasing in increasing ordinals. So we have an ordinally indexed
increasing sequence of sets by inclusion, all subsets of a fixed set
J.
Such a sequence can't have strict increases for unboundedly many
ordinals, else that would put a proper class of elements into J, a
set.
This step is true in ZF, and not with any assumption that J is
well-orderable.
So look at the stabilization of this marked set. So all later
stages of the recursion don't grow the marked set, in particular the
following successor step doesn't, meaning that there were no empties
at this step.
Every stage made a disjoint union to all reals. The only problem
with intermediate stages is they could have had empties. The
stabilization doesn't. So it is a partitioning of the reals, into
lambda many non-empty sets.
The marked locations are singletons, so < c cardinality.
The unmarked locations must be A^stabilizing-ordinal_i for i in
I, ie j in J - I were empty at 0 and so marked at 1. So these
unmarked locations i have A^stabilization_i subset A^0_i, and
|A^0_i| < c, by A^0_i coming from a kappa splitting.
QED Upward Claim.
So, in the Levy Feferman model above, omega splits.
The difficult case that we have not ruled out over ZF is 2 splits.
ZF proves:
Finite Claim: if n finite and n splits -> 2 splits.
(This is a sort of downward claim).
Proof of Finite Claim:
I noted above in ZF that 1 does not split. So n splits -> n>1.
The claim is trivial for n = 2, so I will prove it inductively for
n>2, assuming it inductively for n-1.
So suppose A1, A2, ... An is an n splitting.
If A1 union A2 has cardinality c, then A1,A2 is already a 2
splitting (after re-indexing), and we have 2 splits as required.
So suppose A1 union A2 is cardinality < c. (ie this is a subset
of reals, so if not cardinality c it is cardinality < c).
Then A1 union A2, A3, A4, ... An is an n-1 splitting, so n-1
splits.
By the induction hypothesis for n-1, n-1 splits -> 2 splits.
By modus ponens, therefore 2 splits.
QED Finite Claim
So from the Upward Calim and the Finite Claim, over ZF these
partition all cases: 2 splits, 2 doesn't split and omega splits,
omega doesn't split.
2 splits is the hard case. I don't know what happens here regarding
the real game. This the point Fred made.
The other two cases have information though.
ZF proves:
Omega Claim: if 2 does not split and omega splits,
then empty has a winning strategy in the real game.
Proof of Omega Claim:
This is basically the proof of the First Countable Partitioning
Claim, ie for the Levy Feferman model. At stage i throw away the Ai
elements.
You need to see what is left is size c, to have a legal move. In
the previous proof I used Ai countable. Now we make no such
assumption, but we do have Ai is size < c, so if removing Ai
elements from the oppenent's last play, sized c, left size < c, you
would have a 2 splitting, contra assumptions here.
QED Omega Claim.
And ZF proves about the last case:
Non-splitting Claim: if omega does not split,
then non-empty has no winning strategy in the real game.
Proof of Non-splitting Claim:
This is basically Fred's proof. Suppose for contradiction non-empty
has a winning strategy. We want to make a choice function for c
sized subsets of the reals.
The easiest case is empty plays first in the game, I will discuss
that first, and then return to the other case.
So given A a c sized subset of the reals, we define a play of
empty against the winning strategy for non-empty, which will pick a
real from A. Empty goes first, so pick A as first move.
Now empty wants to pick on the n'th move a play contained in some
interval of size 1/n, forcing the result to be at most a singleton.
So at move n, take non-empty's last play, and consider the
partitioning of it induced by intersecting it with respective members
of the partitioning of the reals by successive half open intervals of
length 1/n, with 0 as a closed left endpoint of an interval for
definiteness.
This is a disjoint union to non-empty's last play. The problem
previously with the proof was to get such a part to be size c.
Since we are now assuming omega doesn't split, at least one of
these must be sized c.
So pick the least one that is sized c according to simple definable
omega ordering of the partitioning of the reals into length 1/n
intervals. The corresponding part of non-empty's last play becomes
empty's next play.
So running this play against non-empty's winning strategy, we get a
singleton, and the member is the choice function value.
That is defining the choice function if empty played first.
If non-empty played first, observe non-empty's opening play by the
winning strategy, a play based on no input from empty. This is a
single c sized set. So reindex from reals to this set, carry each A
c sized subset of reals to a subset of this set via the bijection,
and make that the opening empty play, and proceed as before. Then map
the resulting element picked by the singleton backwards by the
bijection, to get a member of the original A.
So in either case we get the choice function, on c sized sets of
reals. Then proceed as before in Fred's proof, to conclude a
contradiction, from the assumption used above that non-empty had a
winning strategy.
QED Non-splitting Claim
Fred noted in ZFC empty always wins. Fred recently proved that
in ZF + DC + AD the real game is undetermined. I recently posted,
not regarding the real game but with other starting sets, ZF examples
where non-empty wins.
So together these have been examples of all cases: empty wins,
non-empty wins, undetermined.
We still don't have an example of non-empty wins the real game, or
a ZF proof that this can't happen.
With the results above, when 2 doesn't split: if omega splits then
empty wins, if omega doesn't split then at least non-empty has no
winning strategy.
So combining these, if 2 doesn't split then non-empty has no winning
strategy. Or Fred's original proof showed this directly.
So if there are any ZF models with non-empty having a winning
strategy they must be models where 2 splits. So constructing a ZF
model where non-empty has a winning strategy is at least as hard as
constructiong a ZF model where 2 splits.
One possibility might be to prove
ZF |- 2 splits -> non-empty has a winning strategy in the real game.
This might be easier than constructing a 2 split model directly.
Then if there is indeed such a model previously done it settles this.
But I don't know what to expect from 2 splits as hypothesis. 2
splits is incompatible with AD. Namely, from above a 2 splitting must
have both parts uncountable, but as Fred noted, from AD every
uncountable set of reals is size c, so 2 splittings are impossible.
Maybe 2 splits -> non-empty has no winning strategy in the real
game. Above I discussed that (~ 2 splits) -> this same, so in
other words we would have ZF |- no real non-empty w.s.
In fact, we can't even rule out 2 splits -> empty real w.s.
Fred got undetermined above, but that was from AD, and that would
make no contradiction against 2 splits -> empty real w.s. since I
noted above 2 split and AD are incompatible anyway.
Or even 2 split -> undetermined, or 2 split makes no implications
to any of the cases empty wins, non-empty wins, undetermined. All
those are not easy to rule out, as far as I see now.
Daryl McCullough
Fred says...
No, I was just kidding. It's an interesting topic.
Fred Galvin
> A difficult case which we can't rule out happening over ZF is the
> reals partioning into sets A, B each of cardinality strictly less
> than c = 2^Aleph_0.
>
> I will give a ZF proof ruling out a trivial special case of this,
> which will be useful below.
>
> Though we presently don't see how to refute such A,B in ZF, ZF
> does prove the special case:
>
> 2-partioning Claim: there are no A,B partitioning the reals
> with A countable and |B| < c.
I think the easiest way to see that is by using the fact that there's
a bijection between R and RxR. So suppose RxR is partitioned into two
subsets A and B. If A is countable, then A meets only countably many
horizontal lines, so B must contain a horizontal line, so B has
cardinality c.
In the same way, it's easy to see that, if R is partitioned into two
sets A and B, and if A is well-orderable, then at least one of A and B
has cardinality c.
Fred Galvin
> Fred recently proved that in ZF + DC + AD the real game is
> undetermined.
It was silly of me to mention AD; all I used was ZF + DC + "every
uncountable set of real numbers contains a perfect set", which is much
weaker than AD. E.g., if all sets of reals are Lebesgue measurable, or
if they all have the property of Baire, it follows in ZF + DC that
every uncountable set of reals contains a perfect set (I think).
David Libert
These are nice arguments. This is an interesting area, to see all these
tricks just working with sets having no structure on the elements.
This proof above suggests another point, not helpful for the game being
discussed, but an interesting observation to add to earlier discussion.
The relation between sets of being injectible is a reflexive transitive
relation, which forms the basis of the convention definition of
cardinality.
We could also discuss the surjectibility relation: reflexive and
transitive. For A and B sets, define A <=_s B iff there is a
surjection from B onto A. Another way to say in some sense B is "bigger"
than A.
So we could form S-cardinals, say by Scott's trick on the equivalence
relation of two directions of <=_s .
ZF proves for non-empty A: A injects into B -> B surjects onto A.
Namely send elements in B - image(injection) to arbirtrary constant, on
image(injection) take the inverse of the injection.
So ignoring {} and 0 as an awkward special case, in general S-cardinals
collapse normal cardinals: the equivalence classes of being S-equipollent
are unions of equivalence classes of being equipollent.
ZFC |- <= = <=_s
and so S-cardinals are exactly non-zero cardinals.
Ie: use AC to make a backwards injection from a surjection, by using a
choice function on the set of preimages of various elements in the
surjection range.
The methods to make ZF models with ~AC give examples of <=_s relations
that are not <=.
Or a famous one from AD: Aleph_1 <=_s reals, but
~(Aleph_1 <= reals).
So your R x R proof above also gives:
if A,B partitions the reals R
and A,B strictly smaller cardinality than R,
(ie R doesn't inject into either A or B)
then A and B each have the same S-cardinality as R
(ie: A and B each surject onto R).
Ie: reindex A and B as partition of RxR, then either A surjects onto R
by projection, or a slice avoids A and so in B so R injects into B.
So: we get a proof in ZF ruling out the surjective version of 2 splits:
if A,B partition R, then one of A or B has same S-cardinality as the
reals.
Ie: suppose A <_s R, which I haven't defined but means A <=_s R and
~(R <=_s A). So as above, since A doesn't surject onto R, therefore R
injects into B, so R <= B. But <= -> <=_s from before (injections
induce surjections) so R <=_s B.
Similarly B <_s R -> R <=_s A.
So there is no "2 S-splitting" where we use S-cardinals instead of
regular cardinals to define each piece strictly smaller than reals.
I doubt this is helpful for telling us anything about 2 splits, or
clearing up anything about the real game, but it is striking that this
apparently difficult question about 2 splitting corresponds to such an easy
S version.
Fred Galvin
Why the hell do you say that? It sounds like nonsense. I think you
better take a rest.