Re: compactness in angels/devil problem

On Sat, 2 Feb 2008 21:45:49 -0800 (PST), pauldepstein@xxxxxxx wrote:

On Feb 2, 11:24 pm, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Fri, 1 Feb 2008 18:06:29 -0800 (PST), pauldepst...@xxxxxxx wrote:
On Feb 1, 10:06 pm, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Fri, 1 Feb 2008 01:29:08 -0800 (PST), pauldepst...@xxxxxxx wrote:
The literature on the angels-and-devilproblem often refers to a
"compactness argument" for passing from conclusions about finite
boards to conclusions about the infinite case.  What is this
"compactness argument" and which topology is the compactness concept
being applied to?

[long list of questions and clarifications snipped.]

Thanks for your post. The devil does always win on a finite board,
yes. Therefore an infinite board is always assumed to make the
problem interesting.

Aargh. You know, you'd save people time if you were a little
more careful about the questions you asked. Your post
began with

'The literature on the angels-and-devil problem often refers to a
"compactness argument" for passing from conclusions about finite
boards to conclusions about the infinite case.'

I spend some time thinking about this, I can't imagine what
sort of assertion about infinite boards following from the
corresponding assertion about finite boards you might be
referring to, and now you say that no, you were not talking
about finite boards!

Aargh.

Translation-invariance also tends to be assumed
in the literature I've read. Yes, you seem to be not misunderstanding
the rules.

Example of a "compactness argument" in this context (apologies for
omitting this from my previous post). Suppose that, for every N, the
angel is able to travel a distance of >= N from the origin. Then,
"by a compactness argument", we know that the angel can avoid being
trapped by the devil.

Ok. This makes sense, and it's clear that it follows from some sort
of compactness argument...

Ok. Say a "position" is defined by the current position of the
queen together with the set of squares that the devil has eaten
so far. Let P be the set of all positions.

Let's define the "moves" the queen can make as relative to
the current position, and let M be the set of all possible
moves (if there are no eaten squares) plus the special
move "I concede". So for example in the case where the
queen is allowed to move like a king in standard chess
we'd have

M = {"one up", "one down", "one left", "one right", "I concede"}.

Now M is a finite set; give M the discrete topology, and M is
compact. Let X = M^P, the set of all mappings from P to M.
Then X is compact in the product topology, by the Tychonoff
theorem.

To simplify the exposition we note that since M is metrizable
and P is countable the topology on X is also metrizable, so
we can characterize various things in terms of sequences.
Note that if f_1, f_2, ... is a sequence of elements of X then
f_n -> f in X if and only if f_n(p) -> f(p) for every p in P
(this follows from the definition of the product topology).

Say a "strategy" is a rule that tells the queen what to do
in any position. So a strategy s is a function s : P -> M
with the property that for every position p in P,
s(p) is a legal move for the queen in position p.
(Note that there _is_ a legal move in every position,
since "I concede" is always legal. Interesting
strategies s will not have s(p) = "I concede" unless
there is no other legal move from position p, but
never mind that - officially s(p) can be any legal
move.)

Let S be the set of all strategies. Note that S is a
subset of X, in fact S is precisely the set of all s in X
such that for every p in P, s(p) is a legal move from position
p.

This shows that S is a closed subset of X: Suppose that
s_1, s_2,... are elements of S and s_n -> s in X. Then
for every p, s_n(p) -> s(p). Since M is finite and each
s_n(p) is a legal move it follows that s(p) is a legal move,
hence s is in S.

Since S is a closed subset of X, S is compact.

Now let W_N be the set of all strategies s such that
if the queen follows strategy s then the queen is
guaranteed to move at least N squares from where
she starts, regardless of how the devil plays. We
are assuming that each W_N is nonempty.

It is clear that W_{N+1} is a subset of W_N. I
leave it to you to show that W_N is closed, hence
compact. So the intersection of all the W_N is
nonempty. But if s is in the intersection of the
W_N and the queen plays strategy s then for
every N the queen is guaranteed to get at least
N squares from where she starts.

Paul Epstein

David C. Ullrich
.

Relevant Pages

  • Re: compactness in angels/devil problem
    ... boards to conclusions about the infinite case. ... "compactness argument" and which topology is the compactness concept ... queen together with the set of squares that the devil has eaten ... Now M is a finite set; give M the discrete topology, ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... boards to conclusions about the infinite case. ... "compactness argument" and which topology is the compactness concept ... Now M is a finite set; give M the discrete topology, ... suppose that a given angel moves like a chess king. ...
    (sci.math)
  • Re: Limit Point Compactness
    ... > Subject: Re: Limit Point Compactness ... > However as usual topology is coarser than lower limit ...
    (sci.math)
  • Re: Compact vs Quasicompact
    ... He said that compactness also includes Hausdorfness. ... be universal in english texts, while the latter can still be found ... only Hausdorff topological spaces were considered; ... spaces found their way into mainstream topology it was not clear, ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... boards to conclusions about the infinite case. ... "compactness argument" and which topology is the compactness concept ...
    (sci.math)