Re: compactness in angels/devil problem

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?

What's the angels-and-devils problem?

Quite possibly the compactness being referred to is from
logic: If S is a collection of formulas and every finite subset
of S has a model then S has a model.

I could tell you what compact toplogy that's connected
with, at least in the case of propositional logic, but it
will take a little space. So first tell me what the d/a problem
is and what sort of assertions about the problem you're
talking about - the theorem I have in mind could be irrelevant.

Thank you,

Paul Epstein

David C. Ullrich

Hi David,

Informal version of angels/deviltheory:   The angel is on a square
chessboard which is infinite in all directions (Z x Z in other
words).  For each square of the chessboard, there is a finite set of
squares which the angel can visit on the next move (you get a
different problem or question for each rule determining the finite
set).  Thedeviland the angel take alternate moves.  Thedevilmoves
by eating one non-occupied square and therefore preventing the angel
landing on it.  Can thedevilrun the angel out of moves?  (As stands,
not a meaningful problem because I haven't given a rule determining
the angel's possible moves.)

I'm not sure - I think the idea is that there are no constraints on
thedevil'smove, on any turn he can eat any square he wants?
I'll assume yes until you say.

It's not clear to me right away whether the Compactness Theorem
from logic is relevant, although I suspect one could set something
up so it is. It does seem like there's some sort of compactness
that _is_ relevant.

But: You've answered my first question but not the second:
What sort of assertion do people make, that they claim follows
for an infinite board because it's true for every finite board?

The reason I ask is this: It's clear that, for example, "thedevil
always wins" is _always_ true on any finite board (unless I'm
misunderstanding the rules): Thedevileats a new square
each move, and at some point there are no uneaten squares
left. But it's not clear that thedevilalways wins on any
infinite board (and for example if the queen could move
as in chess, which of course contradicts the fact that she
can only move to finitely many squares, then it's clear
that thedevilnever wins on an infinite board.)

So my best guess as to what sort of assertion you're
talking about makes no sense, hence my confusion:
My best guess would be "If the queen can win on
any finite board then the queen can win on an
infinite board", but that makes no sense really since
the queen can _never_ win on a finite board. Similarly
for other guesses.

Yet another question: Is the queen's rule "translation-
invariant"? I suspect the answer's yes because that's the
only sort of rule you had in mind, but it seems like it
may be important so we need to know for sure.

What I mean by the question: A translation-invariant
rule would be defined by a fixed set of offsets from the
current position, for example "two squares up, or
one up and two to the right, or one down and one left"
would be a translation-invariant rule.

While for example "move like a king if you're
currently on a white square, move like a knight
if you're currently on a black square" would be
a rule that's not translation-invariant.

I have good guesses for the answers to most of my
question, except for the one about what sort
of assertion we're talking about...

Concrete example:  Suppose the angel moves like a king in the version
of chess played in the US, England, Eastern Europe and elsewhere (in
fact, the most globally widespread version of chess.)  Then thedevil
can trap the angel.

Yes, David, thank you so much for your offer of explaining the related
topological notion of compactness. I keenly await.  (But don't neglect
the backgammon.)

Paul Epstein

David C. Ullrich- Hide quoted text -

- Show quoted text -

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. 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.

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 ... The angel is on a square ... The devil and the angel take alternate moves. ...
    (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: compactness in angels/devil problem
    ... "compactness argument" and which topology is the compactness concept ... Informal version of angels/devil theory: The angel is on a square ... The devil and the angel take alternate moves. ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... chessboard which is infinite in all directions. ... the angel take alternate moves. ... The devil moves by eating one ... non-occupied square and therefore preventing the angel landing on it. ...
    (sci.math)
  • Re: compactness in angels/devil problem
    ... Informal version of angels/devil theory: The angel is on a square ... chessboard which is infinite in all directions. ... For each square of the chessboard, there is a finite set of squares ... The devil moves by eating one ...
    (sci.math)