Re: theorems/problems with lots of quantifiers

From: Tim Mellor (timm_at_amsta.leeds.ac.uk)
Date: 09/07/04 

Date: 7 Sep 2004 09:26:00 -0700

Mitch Harris <harrisq@tcs.inf.tu-dresden.de> wrote in message news:<2q5dqdFr1envU1@uni-berlin.de>...
> Most mathematical theorems and conjectures seem to have low quantifier
> depth, that is, the nesting of quantifiers is not very deep.
>
> For example, if you formalize the fundamental thm of arithmetic, you
> get something like "for all integers n, there exists a unique
> factorization into primes".
>
> However, I would like to have some examples of not too obscure, fairly
> accessible problems (conjectures or thms) where it -is- nested deeply.
>
> For example, the pumping lemma for regular languages (notorious to
> students of automata/computability) has (at least) 4 quantifiers.
>
> I suppose I care more about "natural" problems rather than
> er..."unmotivated" ones.
>

How about, "there is a winning strategy for white in two moves" at some game
This is

There is some white move so that
For all black moves
White wins

Replace "two moves" by "fifty moves", or if you like "omega moves".

Relevant Pages