Re: compactness in angels/devil problem

On Feb 3, 10:47 pm, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Sat, 2 Feb 2008 21:45:49 -0800 (PST), pauldepst...@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- Hide quoted text -

- Show quoted text -

Thanks, David.

I may not have been quite as careless as you think. I assumed in my
original posting (completely wrongly, it turns out) that the general
mathematical community knew about the angels-and-devil problem. There
are indeed interesting questions about finite boards -- For example,
suppose that a given angel moves like a chess king. Put the angel in
the centre of a board which has sides of length 10^50 + 1. One can
then ask "Given that the devil moves first, can the angel always reach
the edge of the board?" When I said that an infinite board is always
assumed, what I meant was that an infinite board is always assumed
when the question "Who wins, devil or angel?" is asked. So the
"passing from finite to infinite boards" that I was talking about is
as follows: If no matter how large the finite board is, the centrally
placed angel makes its way to the edge of the board, then a notion of
compactness enables one to argue that the angel wins the infinite
game.

I'm having a bit of a problem digesting your argument -- I blame my
inexperience and lack of practice in these notions. I'm familiar with
Tychonoff's theorem and the product topology but it's not immediately
clear to me what the topology on the mappings from M to P looks like.
Admittedly, I haven't had very long to think about it. I will think
about this when I next have time and come back to this newsgroup if I
have more concrete questions about your argument.

Paul Epstein
.

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 ...  Thedeviland the angel take alternate moves. ... by eating one non-occupied square and therefore preventing the angel ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... "compactness argument" and which topology is the compactness concept ... Therefore an infinite board is always assumed to make the ... Now M is a finite set; give M the discrete topology, ... Since S is a closed subset of X, ...
    (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)
  • Re: compactness in angels/devil problem
    ... boards to conclusions about the infinite case. ... "compactness argument" and which topology is the compactness concept ... The angel is on a square ... The devil and the angel take alternate moves. ...
    (sci.math)